TL;DR
This paper introduces a novel framework for querying knowledge bases that combine both "open" (incomplete) and "closed" (complete) information. They analyze the complexity of answering queries under inconsistency-tolerant semantics (Consistent Query Answering) and standard semantics, providing new insights into how the mix of open and closed predicates impacts reasoning complexity.
What Problem Does This Paper Address?
In real-world data systems, we often deal with a mix of information: some facts are definitively known (closed-world assumption, CWA), while others are incomplete or can be extended (open-world assumption, OWA). For example, a company's employee list might be complete (closed), but their project assignments might be partially known (open). When combining these in knowledge bases with rules, inconsistencies can arise. This paper tackles the challenge of answering queries in such mixed-world scenarios, specifically when inconsistencies are present. They aim to provide a robust way to query these systems that accounts for both the certainty of closed predicates and the uncertainty of open ones, while also handling potential contradictions.
Methods
The core of this paper is the development of a formal framework that allows for the simultaneous presence of open and closed predicates within knowledge bases governed by existential rules. They propose and analyze two main reasoning semantics:
- OC-entailment: This represents standard skeptical reasoning in the presence of both open and closed predicates. It's essentially how one would reason if there were no inconsistencies.
- AR-entailment: This is an inconsistency-tolerant semantics, specifically "Consistent Query Answering" (CQA). It defines answers as those that hold true across all "repairs" of the knowledge base. A repair is a minimal modification of the database that resolves inconsistencies while adhering to the rules.
They investigate the data complexity (complexity with respect to the size of the database) of answering Unions of Conjunctive Queries (UCQs) under these semantics. Their analysis covers various classes of existential rules (acyclic, full, guarded, linear) and categorizes dependencies based on whether their heads contain open or closed predicates. They also introduce novel query rewriting techniques to establish complexity bounds.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and complexity results rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- The "Mixed-World" Challenge: Combining open and closed predicates significantly complicates reasoning. The paper shows that this mix often increases complexity compared to scenarios with only open or only closed predicates.
- Open vs. Closed Heads Matter: The position of open and closed predicates within the rules (i.e., in the head of a dependency) has a distinct impact on the complexity of both OC-entailment and AR-entailment.
- CQA as a Solution: Consistent Query Answering (AR-entailment) provides a principled way to handle inconsistencies, ensuring that answers are robust even when the knowledge base contains contradictions.
- Complexity Trade-offs: For certain classes of rules, the complexity of CQA (inconsistency-tolerant reasoning) matches that of standard reasoning (OC-entailment), suggesting that handling inconsistencies doesn't always incur an additional computational cost.
- Tractable Cases Identified: Despite the general increase in complexity, the authors identify specific scenarios (e.g., when open-head dependencies are in the AFL class) where CQA is tractable, even achieving first-order rewritability.
Key Results
The paper presents a comprehensive set of data complexity results for OC-entailment and AR-entailment, summarized in Tables 1 and 2. Key findings include:
- Increased Complexity: In many cases, the presence of both open and closed predicates leads to higher complexity classes (e.g., moving from AC⁰ to P or EXP).
- Specific Tractable Cases:
- OC-entailment for open-head dependencies in AFL combined with any closed-head dependencies is in AC⁰.
- AR-entailment for open-head dependencies in AFL combined with linear closed-head dependencies is in P.
- Hardness Results:
- QANSAR(AFL, A) is Π₂-hard.
- QANSAR(F, AFL) is coNP-hard.
- FO Rewritability: They demonstrate FO-rewritability for OC-entailment when open-head dependencies are in AFL and for AR-entailment when both open- and closed-head dependencies are in AFL.
Limitations and Future Work
- Undecidability: The paper notes that when the set of closed-head dependencies is C* (any set), OC-entailment becomes undecidable, which is a fundamental limitation.
- Further Complexity Analysis: The authors suggest extending their analysis to establish exact complexity bounds for cases that are currently left open.
- Description Logic Integration: They propose exploring how their framework for CQA can be applied to Description Logic knowledge bases, where intensional information is expressed via TBoxes.
- Orthogonal Classifications: Further refinement of the analysis by considering other classifications of dependencies or databases is suggested.
- Prototype Development: The authors express interest in further investigating tractable cases to support the development of CQA prototypes and tools.
Summary updated