TL;DR
This paper introduces a novel "mixed-world" reasoning framework for existential rules, combining "closed" predicates (fully known) with "open" predicates (partially known) under an active-domain semantics. While general reasoning is intractable, they identify a tractable "linear fragment" that captures significant expressive power and propose a fixpoint-based approximation for more complex rules.
What Problem Does This Paper Address?
Ontology-Mediated Query Answering (OMQA) aims to answer queries over data enriched with domain knowledge from an ontology. Traditionally, OMQA assumes an "open-world" view where unstated facts are unknown. However, real-world applications often have a mix of fully known information (e.g., sensor readings at specific times) and partially known information. This paper addresses this by proposing a "mixed-world" semantics where some predicates are treated as "closed" (their content is fully specified by the data) and others as "open" (interpreted under active-domain semantics, meaning only constants explicitly mentioned in the data are considered). This hybrid approach is motivated by scenarios like tracking individuals in a facility where some data is precise and other aspects are inferred.
Methods
The core contribution is the formalization of mixed-world reasoning with existential rules under active-domain semantics. They define "certain" (holds in all models) and "possible" (holds in at least one model) answers to queries. A key technical development is the analysis of a "linear fragment" of existential rules, where rule bodies contain at most one open predicate atom. For this fragment, they establish tractability results for satisfiability, certainty, and possibility. To handle more expressive, non-linear rules, they propose a fixpoint-based approximation method. This involves iteratively refining approximations of certain and possible facts by introducing new "closed" predicates representing these approximations and re-applying linear rules. They also explore the expressive power of their linear fragment, showing it can capture all PTIME queries over ordered databases.
Datasets
Not discussed in the paper. The paper focuses on theoretical framework development and complexity analysis, using abstract examples and reductions rather than specific datasets.
Key Insights and Ideas
- Hybrid Semantics is Practical: The paper demonstrates that a mixed-world approach, combining closed and open predicates with active-domain semantics, is a natural and useful way to model real-world scenarios where information completeness varies.
- Linearity is Tractable: The "linear fragment" of existential rules, a seemingly restrictive subset, turns out to be computationally tractable (PTIME-complete in data complexity) for key reasoning tasks. This is a significant finding, offering a practical sweet spot for reasoning.
- Approximation for Expressivity: For rules beyond the linear fragment, a fixpoint-based approximation technique is introduced. This allows for reasoning with more expressive rules by iteratively refining approximations, bridging the gap between tractability and expressivity.
- Active Domain Matters: The choice of active-domain semantics (considering only explicitly mentioned constants) significantly impacts decidability and complexity compared to classical semantics, often leading to more tractable results.
Key Results
- Intractability for General Rules: For general mixed-world existential rules under active-domain semantics, satisfiability and possibility of Boolean conjunctive queries (BCQs) are NP-complete in data complexity, while certainty is coNP-complete.
- Tractability for Linear Rules: For the linear fragment of existential rules (with extensions like negated closed atoms or disjunctive rule heads), satisfiability, possibility, and certainty of BCQs are PTIME-complete in data complexity.
- Expressive Power of Linear Fragment: The linear fragment, under certain and possible semantics, captures all PTIME queries over ordered databases.
- Fixpoint Approximation: The proposed fixpoint extension for linear rules provides a way to approximate reasoning for arbitrary existential rules, with tractability results for computing these approximations.
Limitations and Future Work
- Approximation Quality: The paper acknowledges that a key question for future work is to formally or experimentally analyze the quality of the fixpoint approximation.
- Combined Complexity: The authors suggest studying the combined complexity of reasoning for different rule classes.
- Domain Representation: Exploring the impact of fixed but succinctly represented domains is a future direction.
- Practical Efficiency: Developing more efficient PTIME algorithms that avoid constructing full maximal models is crucial for practical applications.
- Implicitly Defined Relations: Allowing for closed relations defined by computable functions (rather than explicitly listed facts) is another avenue for future research.
Summary updated