Towards more expressive ontology languages: The query answering problem

Ontology reasoning finds a relevant application in the so-called ontology-based data access, where a classical extensional database (EDB) is enhanced by an ontology, in the form of logical assertions, that generates new intensional knowledge which contributes to answering queries. In this setting, queries are therefore answered against a logical theory constituted by the EDB and the ontology; more specifically, query answering amounts to computing the answers to the query that are entailed by the EDB and the ontology. In this paper, we study novel relevant classes of ontological theories for which query answering is both decidable and of tractable data complexity, that is, the complexity with respect to the size of the data only. In particular, our new classes belong to the recently introduced family of Datalog-based languages, called Datalog±. The basic Datalog± rules are (function-free) Horn rules extended with existential quantification in the head, known as tuple-generating dependencies (TGDs). We propose the language of sticky sets of TGDs (or sticky Datalog±), which are sets of TGDs with a restriction on multiple occurrences of variables in the rule-bodies. We establish complexity results for answering conjunctive queries under sticky sets of TGDs, showing, in particular, that queries can be compiled into domain independent first-order (and thus translatable into SQL) queries over the given EDB. We also present several extensions of sticky sets of TGDs, and investigate the complexity of query answering under such classes. In summary, we obtain highly expressive and effective ontology languages that unify and generalize both classical database constraints, and important features of the most widespread tractable description logics; in particular, the DL-Lite family of description logics.