PaperlayerView exact revision on arXiv

Source-linked AI summary

Taming the Infinite Chase: Query Answering under Expressive Integrity Constraints

Andrea Cali, Georg Gottlob, Michael Kifer

arXiv:1212.3357v2cs.LOcs.DB

TL;DR

The paper tackles query answering when TGDs produce potentially infinite chases, using guardedness-inspired classes and an EGD condition to retain decidability. It establishes tight complexity bounds and applies the results to established ontology formalisms, while noting a bounded-arity limitation for multiple-atom heads.

  • Problem

    The paper addresses the potentially non-terminating chase underlying query answering and containment under TGDs and EGDs.

  • Method

    It uses guarded and weakly guarded TGDs, structural chase properties, new algorithms, and a semantic condition for innocuous EGDs.

  • Results

    The paper proves decidability with tight complexity bounds for several TGD classes and shows that innocuous EGDs can be ignored for conjunctive-query answering and containment.

  • Takeaways & Limitations

    The resulting constraint classes subsume prior results and cover F-Logic Lite, DL-Lite, and EL.

  • Takeaways & Limitations

    For multiple-atom-head TGDs, extending the results is nontrivial in the bounded-predicate-arity case because auxiliary predicate arity may be unbounded.

Abstract

from arXiv · show

The chase algorithm is a fundamental tool for query evaluation and query containment under constraints, where the constraints are (sub-classes of) tuple-generating dependencies (TGDs) and equality generating depencies (EGDs). So far, most of the research on this topic has focused on cases where the chase procedure terminates, with some notable exceptions. In this paper we take a general approach, and we propose large classes of TGDs under which the chase does not always terminate. Our languages, in particular, are inspired by guarded logic: we show that by enforcing syntactic properties on the form of the TGDs, we are able to ensure decidability of the problem of answering conjunctive queries despite the non-terminating chase. We provide tight complexity bounds for the problem of conjunctive query evaluation for several classes of TGDs. We then introduce EGDs, and provide a condition under which EGDs do not interact with TGDs, and therefore do not take part in query answering. We show applications of our classes of constraints to the problem of answering conjunctive queries under F-Logic Lite, a recently introduced ontology language, and under prominent tractable Description Logics languages. All the results in this paper immediately extend to the problem of conjunctive query containment.

1 Introduction

The paper develops decidable query answering for broad classes of TGDs despite potentially infinite chases, derives tight complexity bounds, and gives a condition making EGDs harmless for conjunctive queries.

  • Motivation: The paper addresses query answering when chase procedures under TGDs and EGDs may generate infinite results.It targets a common issue in earlier constraint-based approaches rather than a single logical theory.
  • Guarded TGDs: Weakly guarded TGDs tame the infinite chase by ensuring its result has finite treewidth, yielding decidable Boolean conjunctive-query evaluation.The approach combines this structural property with generalized tree-model results.
  • Complexity: Query evaluation under weakly guarded TGDs is EXPTIME-hard with fixed TGDs and 2EXPTIME-hard when TGDs are part of the input.These lower bounds are established through Turing-machine simulations.
  • Complexity: The corresponding upper bounds are EXPTIME-complete for bounded predicate arities and 2EXPTIME-complete in general, even with fixed TGDs.The paper develops new algorithms because standard guarded-logic results do not apply directly.
  • Additional classes: For fixed dependency sets, Boolean query evaluation is NP-complete and atomic-query evaluation is in P; these bounds are optimal for general Boolean queries.Atomic queries therefore admit a polynomial-time result in this setting, while general Boolean queries cannot improve on NP.
  • Applications: The results extend to multiple-atom-head TGDs, subsume prior results, and cover F-Logic Lite, DL-Lite, and EL.The multiple-atom-head extension is nontrivial only for bounded predicate arity.
  • Scope of results: All complexity bounds are tight, and the results immediately extend from conjunctive-query answering to query containment.The paper distinguishes data complexity for fixed queries and TGDs from combined complexity for variable queries and TGDs.
  • EGDs: A semantic condition makes EGDs innocuous: they can be essentially ignored for conjunctive-query evaluation and containment testing.Innocuous EGDs eliminate atoms without introducing new ones.

2 Preliminaries

The paper formalizes TGDs, databases, conjunctive queries, query answering, and query containment, establishing chase-based characterizations and reductions among central problems.

  • Definitions: A conjunctive query is answered when a homomorphism maps its body to atoms in an instance.Boolean conjunctive queries have no output variables and are positive exactly when such a homomorphism exists.
  • Definitions: TGDs are first-order rules whose conjunctive body implies an existentially quantified conjunctive head.A TGD is satisfied when every homomorphism matching its body extends to one matching its head.
  • Chase and answering: Query answering under TGDs can be characterized by homomorphisms into the restricted chase.For ground answers, the query body maps into the restricted chase while the head maps to the requested tuple.
  • Problem relationships: Conjunctive query answering and query containment under TGDs are mutually logspace-reducible.The paper therefore transfers complexity results between these problems.
  • Chase properties: The oblivious and restricted chases are connected by homomorphisms and agree on Boolean query entailment.The oblivious chase is a universal solution, and Boolean queries hold on it exactly when they hold on the restricted chase.

3 Guarded and Weakly-Guarded TGDs: Decidability Issues

Guarded and weakly guarded TGDs impose syntactic restrictions that tame potentially infinite chases, yielding decidability while exposing a sharp boundary with unrestricted TGDs.

  • Definitions and decidability: Guarded and weakly guarded TGDs make conjunctive query answering decidable despite potentially non-terminating chases.Weak guards cover variables occurring in affected positions that do not also occur in non-affected positions.
  • Guardedness: A guarded TGD has a body atom containing all universally quantified variables, while a weak guard need cover only relevant affected-position variables.Affected positions are those where labeled nulls may appear during the chase.
  • Undecidability boundary: Unrestricted TGDs yield undecidable conjunctive query answering even with a fixed single-headed set containing one non-guarded rule and a ground atomic query.The reduction uses an infinite grid and guarded rules to simulate a universal Turing machine.
  • Structural properties: For weakly guarded TGDs, Boolean query answering is decidable through bounded structural properties of the chase.The paper establishes both chase acyclicity and a treewidth bound before proving decidability.
  • Structural properties: Weakly guarded chases have treewidth at most |dom(D)| + w, where w is the maximum predicate arity.The bound follows from [dom(D)]-acyclicity of the chase.

4 Complexity: Lower Bounds

The paper proves strong lower bounds for Boolean conjunctive query evaluation under weakly guarded TGDs by encoding alternating polynomial- and exponential-space computation.

  • Fixed TGDs: BCQ evaluation under fixed weakly guarded TGDs is EXPTIME-hard, and remains hard for fixed atomic ground queries.The reduction exploits the equality APSPACE = EXPTIME.
  • Unbounded arity: When predicate arity is unbounded, BCQ evaluation under weakly guarded TGDs is 2EXPTIME-hard.The reduction simulates an alternating exponential-space Turing machine, using a polynomial-time encoding.
  • Reduction encoding: The reduction represents ATM configurations, branching successors, tape symbols, cursor positions, states, and transitions using a fixed relational schema.The database stores the input and transition table, while TGDs generate and relate configurations.
  • Reduction encoding: Configuration-generation TGDs create two successor configurations for every configuration, encoding universal and existential computation branches.Additional rules propagate configuration validity and distinguish successor relations.
  • Reduction encoding: Transition TGDs update cursor, state, and tape contents while inertia rules preserve symbols on unaffected cells.Acceptance is represented by deriving accept(V) from configurations in the accepting state.

5 Complexity: Upper Bounds

The paper develops upper-bound algorithms for answering queries under weakly guarded TGDs, using squid decompositions, acyclicity, and chase abstractions. These results yield tight exponential and double-exponential complexity bounds.

  • 5.1 Squid Decompositions: An R-cover extends a Boolean conjunctive query with at most as many additional atoms as the query has body atoms, while preserving query satisfaction.Lemma 5.3 establishes equivalence between satisfying Q and satisfying some R-cover Q+.
  • 5.1 Squid Decompositions: Squid decompositions partition a mapped query into a cyclic head and an acyclic tentacle set.The head is mapped to the finite ground part of the chase, while tentacles are mapped to its potentially infinite acyclic part.
  • 5.1 Squid Decompositions: Acyclic chase witnesses can be reduced to at most 2|Q| atoms while retaining the image of Q and yielding a correspondingly small cover.The construction also preserves [A]-acyclicity, and eliminating atoms whose domain lies in A preserves that acyclicity.
  • 5.2 Clouds and the Complexity of Query Answering under WGTGDs: Query answering under weakly guarded TGDs is in exptime for bounded arity and in 2exptime for unbounded arity.The bounds follow from the Qcheck and Tcheck procedures together with chase-ground-part computation.
  • 5.2 Clouds and the Complexity of Query Answering under WGTGDs: The bounds are tight: Boolean conjunctive query answering is exptime-complete for bounded predicate arities and 2exptime-complete in general, with the same results for query containment.These completeness results hold even when the TGD set is fixed in the bounded-arity case.
  • 5.2 Clouds and the Complexity of Query Answering under WGTGDs: The framework generalizes weak guardedness by bounding the number of null values appearing in designated predicate positions with a computable function.Such positions are called f-bounded, and the resulting TGD sets are f-weakly guarded.

6 Guarded TGDs

The paper analyzes guarded TGDs using restricted chase abstractions and derives complexity classifications for chase computation and query answering. It also establishes matching hardness results, including for fixed databases.

  • 6.1 Complexity—Variable Database: Atomic or fixed-query answering is ptime-complete with bounded arity and schema size, exptime-complete for bounded arity, and 2exptime-complete in general.The 2exptime-completeness remains even when the schema size is bounded.
  • 6.1 Complexity—Variable Database: General conjunctive-query answering is np-complete when arity and schema size are bounded, exptime-complete for bounded arity, and 2exptime-complete otherwise.The latter bound remains when the schema size is bounded.
  • 6.1 Complexity—Variable Database: Boolean conjunctive-query answering under GTGDs is np-complete with bounded arity and schema size, exptime-complete for bounded arity, and 2exptime-complete in general.The bounded case remains np-complete even for a fixed TGD set.
  • 6.1 Complexity—Variable Database: Restricted clouds replace ordinary clouds in the membership proofs and support logarithmic-space configurations when arity and schema size are bounded.This yields ptime algorithms for atomic queries and an np algorithm for general queries in that setting.
  • 6.2 Complexity—Fixed Database: With a fixed database, query answering under GTGDs remains exptime-complete for bounded arity and 2exptime-complete for unbounded arity.For unbounded arity, 2exptime-completeness persists even with bounded schema size.

1. Initial configuration generation rules.

The rules encode the input string in the initial configuration and assign initial configuration properties through predicates derived from init(X).

  • For each tape cell, the rules add zeroi(X) or onei(X) according to whether the input contains 0 or 1 there.
  • The rule init(X) →existential(X) designates the initial configuration as existential without loss of generality.
  • Additional rules derive head1(X) and states0(X) from init(X) to define initial values.

2. Initial configuration rules.

The construction then creates two successor configuration identifiers for each configuration and adds rules that characterize those successors as configurations.

  • 2. Initial configuration rules.: Each configuration identifier generates two successor identifiers, whose configuration status is explicitly established by additional rules.This supports the subsequent simulation of alternating machine behavior.

3. Configuration generation rules.

Configuration rules generate successor configurations through binary next relations. Transition rules are generated for each transition in the finite control.

  • config(X) generates two successor configurations X1 and X2 through next(X, X1, X2).
  • A next relation from X to Y and Z derives config(Y) and config(Z).
  • Transition rules are generated for every transition in the finite control.

4. Transition rules.

Transition rules propagate machine states and tape-head positions across successor configurations. The construction uses a number of rules linearly bounded by the input length.

  • For each control transition, rules derive successor states states1(X1) and states2(X2) from next(X, X1, X2).
  • Head-position rules advance the head index across successor configurations.
  • 6n rules are added per transition rule, so the total construction is linear in the input-string size n.
  • Cells not under the head retain their values in successor configurations.

5. Inertia rules.

Inertia rules preserve tape contents for cells outside the current head position. They are expressed by copying one and blank cell predicates to successor configurations.

  • For j ≠ i, onej(X) implies onej(X1), while blankj(X) implies blankj(X1).
  • These rules implement persistence of tape-cell values at positions not under the head.
  • The rules connect each configuration to its immediate successors through next(X, X1, X2).

6. Configuration-type rules.

Configuration-type rules alternate existential and universal labels across immediate successors. Additional recursive rules specify when configurations are accepting.

  • Each successor of an existential configuration is labeled universal.
  • Each successor of a universal configuration is labeled existential.
  • Recursive rules state when a configuration is accepting.

7. Acceptance rules.

The construction simulates alternating exponential-space computation using guarded TGDs, vectorized tape indices, and acceptance rules for existential and universal configurations.

  • Acceptance rules: The construction initializes an accepting configuration with the ground fact accept.
  • Construction: Exponential tape positions are encoded as bit vectors, while auxiliary relations generate successor pairs and the guard relation g.
  • Construction: The construction uses vectorized predicates to represent exponentially indexed tape cells while retaining a constant number of predicates.
  • Construction: A second bit-vector argument carries pairs of distinct cell positions needed for inertia rules between nonadjacent tape cells.
  • Acceptance rules: Acceptance propagates from either successor for existential configurations and from both successors for universal configurations.
  • Acceptance rules: 2exptime-hardness follows because the guarded TGD construction faithfully simulates an alternating exponential-space machine and reduces acceptance to the query accept.

7 Polynomial Clouds Criterion

The Polynomial Clouds Criterion identifies weakly guarded TGD sets with polynomially many relevant cloud types, yielding tractable query answering for restricted queries and NP for general Boolean conjunctive queries.

  • Criterion: The Polynomial Clouds Criterion requires polynomially many cloud isomorphism types and polynomially bounded predecessor-cloud relationships.
  • Complexity: For fixed weakly guarded TGDs satisfying the criterion, atomic and fixed Boolean conjunctive queries are in P, while general Boolean conjunctive queries are in NP.
  • Algorithm: The algorithm stores canonical atoms and clouds, then checks query matches against the resulting cloud-store.
  • Limitation: The criterion is not syntactic, so its applicability may require semantic analysis rather than direct inspection of rule form.
  • Applications: Every guarded TGD set satisfies the criterion, and bounded-arity guarded TGD classes satisfy it as well.
  • Complexity: For bounded-treewidth and acyclic Boolean conjunctive queries, answering is in P under the criterion.
  • Exponential criterion: The Exponential Clouds Criterion gives an EXPTIME upper bound for atomic and non-atomic queries over its weakly guarded classes.

8 TGDs with Multiple-Atom Heads

Multiple-atom-head TGDs can generally be reduced to single-headed TGDs with auxiliary predicates, preserving query answers and extending the paper’s complexity results.

  • Extension: All complexity results for single-atom-head TGDs remain valid for TGDs with multiple-atom heads.
  • Transformation: A multi-atom rule is transformed by introducing a fresh predicate that records the shared head variables before deriving each head atom.
  • Correctness: The transformed and original chases differ only on auxiliary atoms, which cannot match predicates in the conjunctive query.
  • Complexity: The transformation is computable in logarithmic space, so the complexity extension is immediate except for bounded predicate arity.
  • Bounded arity: For bounded-arity WGTGDs, the transformed sets satisfy the Exponential Clouds Criterion, preserving an EXPTIME upper bound.

9 EGDs

Arbitrary EGDs can make query answering undecidable and disrupt infinite-chase behavior, but innocuous EGDs preserve the TGDs-only query-answering results when the chase does not fail.

  • Motivation: Combining TGDs with even simple EGDs such as keys and inclusion dependencies yields undecidable implication, query-answering, and containment problems.
  • Innocuous EGDs: An EGD is innocuous when its application only removes or identifies atoms without introducing new atoms.
  • Interaction: Innocuous EGD applications cannot trigger TGD applications that were impossible before equality enforcement.
  • Query answering: If EGDs are innocuous relative to TGDs and the fair chase is non-failing, query answering equals answering over the TGDs-only chase.
  • Failure checking: For weakly guarded TGDs with innocuous EGDs, chase failure is decidable by checking conflicting database constants in the TGDs-only chase.
  • Failure checking: For guarded or weakly guarded TGDs, checking chase failure has the same complexity as query answering without EGDs.
  • Complexity: Query answering with weakly guarded TGDs and innocuous EGDs is P-time reducible to answering under weakly guarded TGDs alone.

10 Applications

The paper applies its guarded constraint classes to ontology languages, including F-Logic Lite and tractable Description Logics, and establishes query-answering complexity for F-Logic Lite.

  • The results apply to Description Logic languages and object-oriented logic languages, including tractable DL families and F-Logic Lite.
  • F-Logic Lite: F-Logic Lite can be encoded using twelve TGDs and EGDs, with one innocuous EGD that does not interfere with query answering.The EGD is innocuous because it turns one atom into another, and generated labeled nulls occur only in the relevant data position.
  • Complexity: NP-hardness follows by reduction from 3-colorability, encoding graph edges as conjunctive-query atoms over a fixed database.The transformation from a graph to the query and database is polynomial.
  • F-Logic Lite: The F-Logic Lite rules form a weakly guarded set of TGDs after eliminating the innocuous EGD.The proof identifies affected positions and shows that every remaining rule is weakly guarded.
  • Complexity: NP-completeness holds for general conjunctive queries under F-Logic Lite rules, while fixed-size or atomic conjunctive queries are solvable in polynomial time.

11 Conclusions and Related Work

The paper identifies a broad decidable class of TGDs and EGDs for query answering and containment, connecting it to database dependencies and ontology formalisms. Related work contrasts this guarded approach with rewriting, chase termination, semantic characterizations, and EGD separability.

  • Conclusions: The paper identifies a large, non-trivial class of TGDs and EGDs with decidable conjunctive query answering and containment, together with complexity results.
  • Conclusions: The class subsumes earlier database dependency results and captures important ontology formalisms, including DL-Lite and EL.
  • Rewriting: DL-Lite query answering is first-order rewritable, allowing conjunctive queries and ontologies to be rewritten as SQL queries over the original database.
  • Rewriting: Rewriting techniques have also been developed for EL and more expressive description logics, including approaches combining rewriting with the chase.
  • Semantic characterizations: Semantic decidability characterizations include finite unification sets, bounded treewidth sets, and finite expansion sets; every weakly guarded TGD set is a bounded treewidth set.
  • Related work: The broader Datalog± framework uses TGDs and EGDs to support tractable query answering for more general ontology languages, with existential heads enabling value invention beyond plain Datalog.
  • Related work: Guardedness provides a decidability paradigm distinct from chase-termination restrictions, while frontier-guarded variants guard only variables shared between rule bodies and heads.
  • Related work: Separability captures cases where EGDs and TGDs do not interact, extending earlier work on functional and inclusion dependencies.
Loading 1212.3357v2…