Abstract
This work identifies the "computational sweet spot" for querying large-scale ontologies. It demonstrates that the $DL\text{-}Lite$ family of Description Logics represents the maximal expressivity allowed for translating complex semantic queries into standard SQL that executes efficiently on massive databases.
Introduction: The Challenge of Scale
In Semantic Web applications and Enterprise Data Integration, ontologies serve as conceptual models providing a unified view over vast data repositories. However, a fundamental tension exists: increasing the expressivity of the ontology typically degrades query performance.
This paper focuses on data complexity—the growth of query answering time relative to the size of the data (the ABox), while the schema (the TBox) remains fixed. The authors seek the boundary of First-Order (FO) rewritability. A logic is FO-rewritable if a query posed against the ontology can be automatically transformed into a standard SQL query. This allows leveraging highly optimized Relational Database Management Systems (RDBMS) to handle billions of records without specialized reasoning engines.
Methods: The $DLR\text{-}Lite_{\mathcal{A},\sqcap}$ Logic
The authors introduce $DLR\text{-}Lite_{\mathcal{A},\sqcap}$, a powerful member of the $DL\text{-}Lite$ family. This logic supports $n$-ary relations, inclusions, keys, and conjunctions. To illustrate these capabilities, the paper uses a running example involving Suppliers, Customers, and Products.
The core mechanism for query answering is the PerfectRef algorithm. It takes a Conjunctive Query (CQ) and the ontology's TBox rules to produce a Union of Conjunctive Queries (UCQ). This reformulated query can then be executed as a single SQL statement against a standard database, effectively separating the reasoning process from data processing.
Key Insights: Mapping the Complexity Cliff
The research establishes $DL\text{-}Lite$ as the "ceiling" for efficient query answering. Adding common logic constructs often leads to a "complexity cliff":
- Recursion: Introducing recursive rules (e.g., "the father of a human is a human") jumps complexity to NLOGSPACE, exceeding standard SQL capabilities.
- Disjunction: Allowing unions (e.g., "an employee is either a manager or a worker") makes the problem coNP-hard, rendering it intractable for massive datasets.
Key Results
The paper provides a definitive classification of data complexity for various Description Logic fragments, identifying exactly where the boundary of tractability lies.
As shown in the table above:
- $DLR\text{-}Lite_{\mathcal{A},\sqcap}$ remains within $AC^0$ complexity, the lowest possible class for query answering, ensuring high scalability.
- Adding qualified existentials on the left side of inclusions moves complexity to NLOGSPACE-complete.
- Combining conjunctions on the left with qualified existentials on the right reaches PTIME-complete, requiring Datalog-level power.
- Introducing negation or union results in coNP-complete complexity, the "hard wall" for large-scale data.
Limitations and Future Outlook
While FO-rewritability ensures scalability, the reformulated SQL queries can become extremely large (unions of many queries), potentially challenging standard SQL optimizers. Future research directions include optimizing the size and structure of reformulated queries and developing "ontology-aware" database techniques to better handle generated SQL.
Summary updated