Tractable Query Answering over Ontologies with Datalog+⁄−

We present a family of expressive extensions of Datalog, called Datalog±, as a new paradigm for query answering over ontologies. The Datalog± family admits existentially quantified variables in rule heads, and has suitable restrictions to ensure highly efficient ontology querying. In particular, we show that query answering under so-called guarded Datalog± is PTIME-complete in data complexity, and that query answering under so-called linear Datalog± is in AC0 in data complexity. We also show how negative constraints and a general class of key constraints can be added to Datalog while keeping ontology querying tractable. We then show that linear Datalog±, enriched with a special class of key constraints, generalizes the well-known DL-Lite family of tractable description logics. Furthermore, the Datalog± family is of interest in its own right and can, moreover, be used in various contexts such as data integration and data exchange. This work is a short version of [8].