Oblivious and Semi-Oblivious Boundedness for Existential Rules

Pierre Bourhis, Michel Leclère, Marie-Laure Mugnier, Sophie Tison, Federico Ulliana, Lily GalloisIJCAI 2019 · DOI

TL;DR

This paper tackles the problem of "boundedness" in existential rule systems, a crucial property for efficient query answering in knowledge bases. The authors provide a characterization of boundedness for two specific chase variants (oblivious and semi-oblivious) by linking it to the decidability of chase termination and the existence of first-order rewritings. This work offers a deeper understanding of the relationship between these fundamental concepts and sheds light on their decidability and complexity.

What Problem Does This Paper Address?

In the realm of knowledge representation and reasoning, particularly in ontology-based query answering (OBQA), existential rules are a powerful tool for describing knowledge. These rules, similar to Datalog but allowing for existential quantifiers in their heads, enable reasoning about unknown individuals. A key challenge in working with these rules is that reasoning procedures, like the "chase" (a process of materializing entailed facts) or query rewriting, might not terminate.

To address this, researchers have focused on characterizing decidable and tractable classes of existential rules. Two important properties are:

  1. Chase Termination: Whether the chase procedure eventually stops for any given knowledge base.
  2. FO-Rewritability: Whether a query can be rewritten into an equivalent query that only uses first-order logic, allowing for efficient evaluation on a standard database.

While these properties have been studied individually, their interplay, especially concerning "boundedness," has been less explored. Boundedness is a stricter notion than termination, requiring that the chase procedure terminates within a depth independent of the initial data. This paper investigates the conditions under which existential rule sets are bounded, specifically for the oblivious and semi-oblivious chase variants, and how this relates to chase termination and FO-rewritability.

Methods

The paper's core contribution lies in establishing a characterization of boundedness for the oblivious (o-chase) and semi-oblivious (so-chase) variants of the chase procedure. The authors introduce and utilize the concept of "existential depth" for terms generated during the chase.

  • Existential Depth: This metric measures the number of times fresh variables (introduced by existential quantifiers) are generated to create a term. For the oblivious chase, this depth is shown to be preserved by embeddings, allowing them to bound the existential depth on a "critical instance" and, consequently, for any instance, provided the chase terminates.
  • Frontier Existential Depth: For the semi-oblivious chase, the standard existential depth is not sufficient. A modified notion, "frontier existential depth," is introduced, which focuses on the depth of terms appearing in the "frontier" (shared variables) of rules.
  • Linking Depth and Rank: The paper then connects these depth measures to the "rank" of the chase (the number of steps it takes to terminate). They prove that for FO-rewritable rule sets, the rank of a fact is bounded by a function of its existential depth and a constant derived from the FO-rewritability property.
  • Characterization of Boundedness: Ultimately, the authors show that for the oblivious chase, boundedness is equivalent to chase termination combined with FO-rewritability on full-atomic queries (FO-RAF). For the semi-oblivious chase, boundedness is equivalent to chase termination and general FO-rewritability (FO-R).

Datasets

Not discussed in the paper. The paper focuses on theoretical properties of rule sets and their interaction with abstract instances, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Boundedness is a strong property: It's not just about termination, but termination within a fixed depth, independent of the input data. This is crucial for practical query optimization.
  • Chase variants matter: The definition of "boundedness" and its relationship with other properties (like FO-rewritability) differ significantly between the oblivious and semi-oblivious chase variants. This highlights the nuanced nature of reasoning with existential rules.
  • Existential depth as a key metric: The introduction and analysis of existential depth (and its variant for so-chase) provide a novel way to understand and bound the complexity of the chase procedure.
  • FO-rewritability is essential for boundedness: The paper demonstrates that for both chase variants, FO-rewritability (in different forms) is a necessary condition for boundedness, alongside chase termination. This underscores the importance of query rewriting techniques.
  • Decidability implications: The theoretical characterizations lead to insights into the decidability and complexity of recognizing bounded rule sets, providing concrete complexity bounds for various classes of rules.

Key Results

  • Oblivious Chase: Boundedness is equivalent to chase termination and FO-rewritability on full-atomic queries (FO-RAF). For rule sets that guarantee chase termination, FO-R and FO-RAF coincide.
  • Semi-Oblivious Chase: Boundedness is equivalent to chase termination and general FO-rewritability (FO-R).
  • Decidability and Complexity: The paper establishes decidability results for boundedness for specific classes of rules (e.g., PSpace-complete for linear and sticky rules) and provides complexity bounds (e.g., 2Exptime for guarded rules).
  • k-boundedness: The problem of whether the chase terminates within k steps is shown to be decidable for both oblivious and semi-oblivious chases.

Limitations and Future Work

  • Undecidability: The paper notes that recognizing boundedness for general existential rulesets is undecidable, mirroring the situation for Datalog.
  • Specific Chase Variants: The characterizations are provided for the oblivious and semi-oblivious chases. The authors leave open the question of whether similar characterizations hold for other chase variants, such as the restricted and core chases.
  • FE-rules vs. General Rules: While FE-rules (fully-existential rules) have a simpler relationship between termination and boundedness for the oblivious chase, this simplification does not extend to the semi-oblivious chase. The paper suggests that for the so-chase, a transformation can be used to relate boundedness to the oblivious chase, offering a potential avenue for future research.
  • Complexity for FE-rules: The decidability of membership to BN° (boundedness for oblivious chase) for FE-rules remains an open question.

Summary updated

BibTeX
@inproceedings{bourhis2019oblivious,
  author = {Pierre Bourhis and Michel Leclère and Marie-Laure Mugnier and Sophie Tison and Federico Ulliana and Lily Gallois},
  title = {{Oblivious and Semi-Oblivious Boundedness for Existential Rules}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/219},
}
Figure