Skip to main content

Tractable Query Answering over Ontologies with Datalog+⁄−

Andrea Calì‚ Georg Gottlob and Thomas Lukasiewicz


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].

Book Title
Proceedings of the 22nd International Workshop on Description Logics‚ DL 2009‚ Oxford‚ UK‚ July 27−30‚ 2009
Bernardo Cuenca Grau and Ian Horrocks and Boris Motik and Ulrike Sattler
CEUR Workshop Proceedings