Tractable Query Answering over Ontologies with Datalog+⁄−

Abstract

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