New Expressive Languages for Ontological Query Answering


  • Andrea Calì University of London, Birkbeck College
  • Georg Gottlob Oxford University
  • Andreas Pieris Oxford University


Ontology-based data access is a powerful form of extending database technology, where a classical extensional database (EDB) is enhanced by an ontology that generates new intensional knowledge which may contribute to answer a query. Recently, the Datalog+/- family of ontology languages was introduced; in Datalog+/-, rules are tuple-generating dependencies (TGDs), i.e., Datalog rules with the possibility of having existentially-quantified variables in the head. In this paper we introduce a novel Datalog+/- language, namely sticky sets of TGDs, which allows for a wide class of joins in the body, while enjoying at the same time a low query-answering complexity. We establish complexity results for answering conjunctive queries under sticky sets of TGDs, showing, in particular, that ontological conjunctive queries can be compiled into first-order and thus SQL queries over the given EDB instance. We also show some extensions of sticky sets of TGDs, and how functional dependencies and so-called negative constraints can be added to a sticky set of TGDs without increasing the complexity of query answering. Our language thus properly generalizes both classical database constraints and most widespread tractable description logics.




How to Cite

Calì, A., Gottlob, G., & Pieris, A. (2011). New Expressive Languages for Ontological Query Answering. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 1541-1546. Retrieved from



New Scientific and Technical Advances in Research