Tractable Query Answering over Ontologies with Datalog+⁄−

Conference item

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

Authors: Calì, A; Gottlob, G; Lukasiewicz, T

• Publisher: CEUR−WS.org
• Host title: Proceedings of the 22nd International Workshop on Description Logics‚ DL 2009‚ Oxford‚ UK‚ July 27−30‚ 2009
• Volume: 477
• Publication date: 2009-01-01