Abstract
Description Logics (DLs) are the formal foundations of the standard web ontology languages OWL-DL and OWL-Lite. In the Semantic Web and other domains, ontologies are increasingly seen also as a mechanism to access and query data repositories. This novel context poses an original combination of challenges that has not been addressed before: (i) sufficient expressive power of the DL to capture common data modeling constructs; (ii) well established and flexible query mechanisms such as Conjunctive Queries (CQs); (iii) optimization of inference techniques with respect to data size, which typically dominates the size of ontologies. This calls for investigating data complexity of query answering in expressive DLs. While the complexity of DLs has been studied extensively, data complexity has been characterized only for answering atomic queries, and was still open for answering CQs in expressive DLs. We tackle this issue and prove a tight $\text{CONP}$ upper bound for the problem in $\mathcal{SHIQ}$, as long as no transitive roles occur in the query. We thus establish that for a whole range of DLs from $\mathcal{AL}$ to $\mathcal{SHIQ}$, answering CQs with no transitive roles has $\text{CONP}$-complete data complexity. We obtain our result by a novel tableaux-based algorithm for checking query entailment, inspired by the one in [19], but which manages the technical challenges of simultaneous inverse roles and number restrictions (which leads to a DL lacking the finite model property).
Introduction
Description Logics (DLs) serve as the formal foundation for the Web Ontology Language (OWL). While their reasoning capabilities are well-understood in terms of combined complexity—where the schema (TBox), data (ABox), and query all vary—the increasing use of ontologies to query large-scale data repositories necessitates a focus on data complexity.
Data complexity measures the computational cost relative to the size of the data, keeping the schema and query fixed. For expressive DLs like $\mathcal{SHIQ}$, which include inverse roles and number restrictions, data complexity for Conjunctive Queries (CQs) remained an open problem for years. This paper settles the question, proving that for $\mathcal{SHIQ}$, the data complexity of answering CQs is $\text{CONP}$-complete.
Methodology: Tableaux and Completion Forests
The primary difficulty in $\mathcal{SHIQ}$ is the lack of the finite model property. The combination of inverse roles and number restrictions can force models to be infinite. Traditional database techniques, which assume finite structures, are therefore insufficient.
The authors propose a novel tableaux-based algorithm that checks for query entailment by attempting to construct a counter-model. This process uses completion forests, which are collections of trees representing potential models for the knowledge base.
To ensure termination, the algorithm employs a sophisticated n-blocking condition. As illustrated in Figure 1, the structures $T_1$ and $T_2$ represent different stages of expansion or unraveling. By identifying repetitive patterns (blocks) within these trees, the algorithm can represent an infinite model using a finite structure. If a query cannot be mapped into this "unraveled" canonical model, it is not entailed. The algorithm effectively "unravels" the completion forest into an infinite tree-like structure that serves as a counter-example if the query is not satisfied.
Key Insights and Results
- The Complexity Gap: The paper shows that while $\mathcal{SHIQ}$ is highly expressive, the "hardness" added by the data volume is no worse than it is for much simpler logics like $\mathcal{ALC}$. The jump to EXPTIME in combined complexity is driven by the schema and query size, not the data size.
- Unified Bound: This result establishes a uniform $\text{CONP}$ complexity bound for a wide range of Description Logics, from the basic $\mathcal{AL}$ to the highly expressive $\mathcal{SHIQ}$.
- Algorithm Soundness: The work provides the first tableaux-style algorithm for this problem that is proven to be sound and complete even in the presence of inverse roles and number restrictions.
Limitations and Future Work
While this result is a major milestone, several challenges remain:
- Transitive Roles in Queries: The proof assumes that the Conjunctive Query itself does not contain transitive roles (though the underlying schema can). Answering queries with transitive roles remains a more difficult problem.
- Nominals: The logic $\mathcal{SHIQ}$ does not include nominals (specific individuals in the schema). Extending this to $\mathcal{SHOIQ}$ would require further tuning of the tableaux rules.
- Practical Implementation: Although $\text{CONP}$ is relatively low complexity for logic, it still implies non-determinism. Translating this theoretical algorithm into a high-performance engine for massive datasets remains a significant engineering challenge.
Summary updated