Advanced Processing for Ontological Queries

Andrea Calì, Georg Gottlob, Andreas Pieris

Research output: Contribution to journalArticlepeer-review


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. The ontological integrity constraints for generating this intensional knowledge can be specified in description logics such as DL-Lite. It was recently shown that these formalisms allow for very efficient query-answering. They are, however, too weak to express simple and useful integrity
constraints that involve joins. In this paper we introduce a more expressive formalism that takes joins into account, while still enjoying the same low query-answering complexity. In our framework, ontological constraints are expressed
by sets of rules that are so-called tuple-generating dependencies (TGDs). We propose the language of sticky sets of TGDs, which are sets of TGDs with a restriction on multiple occurrences of variables (including joins) in the rule bodies. 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 how sticky sets of TGDs can be combined with functional dependencies. In summary, we obtain a highly expressive and effective ontological modeling language that unifies and generalizes both classical database constraints and important features of the most widespread tractable description logics.
Original languageEnglish
Pages (from-to)554-565
Number of pages12
JournalProceedings of the VLDB Endowment
Issue number1
Publication statusPublished - 2010


Dive into the research topics of 'Advanced Processing for Ontological Queries'. Together they form a unique fingerprint.

Cite this