Taming the Infinite Chase: Query Answering under Expressive Relational Constraints

By Andrea Calì, Georg Gottlob, Michael Kifer. Description Logics, 2008

486 citations recorded by the source corpus.

The chase algorithm is a fundamental tool for query evaluation and for testing query containment under tuple-generating dependencies (TGDs) and equality-generating dependencies (EGDs). So far, most of the research on this topic has focused on cases where the chase procedure terminates. This paper introduces expressive classes of TGDs defined via syntactic restrictions: guarded TGDs (GTGDs) and weakly guarded sets of TGDs (WGT-GDs). For these classes, the chase procedure is not guaranteed to terminate and thus may have an infinite outcome. Nevertheless, we prove that the problems of conjunctive-query answering and query containment under such TGDs are decidable. We provide decision procedures and tight complexity bounds for these problems. Then we show how EGDs can be incorporated into our results by providing conditions under which EGDs do not harmfully interact with TGDs and do not affect the decidability and complexity of query answering. We show applications of the aforesaid classes of constraints to the problem of answering conjunctive queries in F-Logic Lite, an object-oriented ontology language, and in some tractable Description Logics.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/48dae309e2372bbb1871edcd2ebbdc9ce620742d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Foundations of SPARQL query optimization (2008, background): “Although we borrow this definition from [ 4 ] our focus is different.”
On rules with existential variables: Walking the decidability line (2011, methodology): “In relationship with forward chaining, we introduce two new decidable classes implementing bts behavior: frontierguarded rules and their extension to weakly frontier-guarded sets of rules, which are generalizations of the classes defined in [12].”
A general datalog-based framework for tractable query answering over ontologies (2009, background): “A related paper is [12], where complexity issues of GTGDs as well as of another class, called weakly guarded TGDs, were first studied.”