Introduction
In the field of Semantic Web and Artificial Intelligence, Description Logics (DLs) serve as the formal foundation for ontologies, enabling structured knowledge representation and automated reasoning. Traditionally, DLs operate under the Open-World Assumption (OWA), which posits that the absence of a fact in a knowledge base does not imply its falsehood, but merely that its truth value is unknown. However, real-world applications often encounter scenarios where certain information is known to be complete. For instance, a university database may contain an exhaustive list of all offered courses. In such cases, the Closed-World Assumption (CWA) is more appropriate.
This paper, originally presented at IJCAI-16, addresses the computational challenge of mixing these two paradigms—specifically, querying ontologies in the expressive logic $\mathcal{ALCHIO}$ when a subset of predicates is designated as "closed."
The Problem: Non-Monotonicity and Complexity
Integrating closed predicates into an otherwise open-world ontology introduces non-monotonicity: adding new information can invalidate previously held conclusions. This makes reasoning significantly more difficult than in standard DLs. Previous attempts to translate these complex queries into Datalog—a standard logic programming language—often resulted in programs of exponential size, rendering them impractical for large-scale applications.
Consider the assertions in the figure above. If Course is a closed predicate, the system must assume that $c_1$ and $c_2$ are the only courses in the domain. If GradCourse is open, $c_1$ might still be a graduate course even if it isn't explicitly stated. Managing these differing assumptions during query answering is the core difficulty addressed by the authors.
Methodology: The Marking Algorithm and Game Theory
The authors bridge the gap between expressive DLs and Datalog using a novel approach rooted in game theory. The reasoning process is conceptualized as a game between two players: "Bob the Builder," who tries to construct a valid model of the ontology, and "Sam the Spoiler," who searches for logical contradictions.
The algorithm proceeds in several stages:
- Core Interpretation: A "core" is defined to represent the individuals and relations explicitly present in the data (the ABox).
- The Marking Algorithm: The authors develop an algorithm that "marks" logical states (types) that are inherently contradictory or "bad" for the Builder. If any state required by the data is marked, the query is not entailed.
- Polynomial Rewriting: The primary contribution is the translation of this marking logic into a set of Datalog rules. By utilizing disjunction to non-deterministically "guess" the core interpretation and negation as failure (
not) to implement the marking logic, the authors achieve a rewriting that is only polynomially larger than the original ontology.
Key Results and Implications
The main theoretical result (Theorem 3) establishes that for any instance query in $\mathcal{ALCHIO}$ with closed predicates, a Datalog program can be constructed in polynomial time such that the certain answers are preserved.
Several key insights emerge from this work:
- Breaking the Horn Barrier: While most polynomial rewritings are restricted to "Horn" DLs (which lack disjunction), this method supports the more expressive $\mathcal{ALCHIO}$.
- Complexity Alignment: The underlying problem is EXPTIME-complete. The authors show that their Datalog program can be evaluated within this same complexity class, ensuring that the rewriting process itself does not introduce unnecessary computational overhead.
- Data Independence: The generated Datalog rules are independent of the specific database (ABox), allowing them to be reused across different datasets.
Limitations and Future Outlook
While this research represents a significant step forward, it focuses exclusively on instance queries (checking class membership for specific individuals). Extending this to Conjunctive Queries (CQs)—which involve complex joins—remains a challenge, as the problem complexity for this logic jumps to 2EXPTIME-hard.
Furthermore, while the rewriting is polynomially sized, the resulting disjunctive Datalog programs with negation are still computationally intensive. Future work will involve empirical evaluations to determine the practical performance of this approach on large-scale, real-world data and exploring optimizations for standard rule engines.
Summary updated