Data Complexity of Query Answering in Description Logics (Extended Abstract)

Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, Riccardo RosatiIJCAI 2015

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.

Example axioms in DLR-Lite for a supply chain scenario.

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.

Data complexity of query answering for different DL fragments.

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

BibTeX
@inproceedings{calvanese2015data,
  author = {Diego Calvanese and Giuseppe De Giacomo and Domenico Lembo and Maurizio Lenzerini and Riccardo Rosati},
  title = {{Data Complexity of Query Answering in Description Logics (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure