Query Answering under Non-guarded Rules in Datalog+/-

Andrea Calì, Georg Gottlob, Andreas Pieris

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In ontology-based data access, an extensional database is enhanced by an ontology that generates new intensional knowledge which has to be considered when answering queries. In this setting, tractable data complexity (i.e., complexity w.r.t. the data only) of query answering is crucial, given the need to deal with large data sets. A well-known class of tractable ontology languages is the DL-lite family; however, in DL-lite it is impossible to express simple and useful integrity constraints that involve joins. To overcome this limitation, the Datalog+/- class of decidable languages uses tuple-generating dependencies (TGDs) as rules, thus allowing for conjunctions of atoms in the rule bodies, with suitable limitations to ensure decidability. In particular, sticky sets of TGDs allow for joins and variable repetition in rule bodies under certain conditions. In this paper we extend the notion of stickiness by introducing weakly-sticky sets of TGDs, which also generalize the well-known weakly-acyclic sets of TGDs. We investigate the complexity of query answering under such language, and in addition we provide novel complexity results on weakly-acyclic sets of TGDs. Moreover, we present the novel class of sticky-join sets of TGDs, which generalizes both sticky sets of TGDs and so-called linear TGDs, an extension of inclusion dependencies.
Original languageEnglish
Title of host publicationWeb Reasoning and Rule Systems - Fourth International Conference, RR 2010, Bressanone/Brixen, Italy, September 22-24, 2010. Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages17
ISBN (Electronic)978-3-642-15918-3
ISBN (Print)978-3-642-15917-6
Publication statusPublished - 2010

Publication series

NameSpringer Berlin Heidelberg
PublisherLecture Notes in Computer Science (LNCS)
ISSN (Print)0302-9743


Dive into the research topics of 'Query Answering under Non-guarded Rules in Datalog+/-'. Together they form a unique fingerprint.

Cite this