Reverse Engineering Queries in Ontology-Enriched Systems: The Case of Expressive Horn Description Logic Ontologies

Víctor Gutiérrez-Basulto, Jean Christoph Jung, Leif SabellekIJCAI 2018 · DOI

TL;DR

This paper introduces and analyzes the "query-by-example" (QBE) paradigm for ontology-enriched systems (OES). They develop characterizations, algorithms, and complexity bounds for finding queries that match positive examples while excluding negative ones, specifically for expressive Horn Description Logic ontologies. This work aims to make OES more accessible to non-expert users by enabling intuitive data exploration.

What Problem Does This Paper Address?

Ontology-enriched systems (OES) offer powerful ways to manage and query data by leveraging background knowledge from ontologies. However, accessing this data typically requires users to formulate queries in complex query languages, which is a significant barrier for non-expert users. This problem is analogous to the challenge faced in relational databases, where query-by-example (QBE) emerged as a solution. QBE allows users to provide examples of what they want (positive examples) and what they don't want (negative examples), and the system then reverse-engineers a query that satisfies these examples.

This paper tackles the problem of adapting and formalizing QBE for OES, specifically focusing on ontologies expressed in expressive Horn Description Logics (DLs) and using conjunctive queries (CQs) or unions of conjunctive queries (UCQs). The core question is: given an ontology and sets of positive and negative examples, does a query exist that retrieves all positive examples but none of the negative ones?

Methods

The authors introduce and study the Query-by-Example (QBE) problem for ontology-enriched systems. Their approach involves:

  • Formalizing QBE: They define the problem formally as QBE(L, Q), where L is the ontology language (Horn-ALCI, Horn-ALC) and Q is the query language (CQ, UCQ).
  • Model-Theoretic Characterizations: They leverage the concept of universal models of knowledge bases. The key idea is to adapt characterizations from relational databases by replacing the database with the universal model of the ontology-enriched system. This involves constructing and analyzing direct products of interpretations.
  • Algorithms and Complexity Analysis: Based on the characterizations, they develop decision procedures for QBE. A significant challenge is dealing with potentially infinite universal models. They exploit the regularity of universal models and introduce a concept called PHom (partial homomorphism) to handle this. They devise a mosaic-based elimination procedure to manage the complexity arising from these infinite structures.
  • Complexity Bounds: They establish tight complexity bounds for the QBE and QDEF (Query Definability) problems for various combinations of DLs and query languages. This includes proving 2-EXPTIME-completeness for Horn-ALCI with CQs/UCQs and CONEXPTIME-completeness for Horn-ALC with CQs.
  • Witness Query Size Analysis: They investigate the size of the queries that can be generated by QBE, showing that they can be double exponentially large in some cases, contrasting with relational databases.

Datasets

Not discussed in the paper. The paper focuses on theoretical foundations and complexity analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Bridging DL and Machine Learning: The paper frames QBE over knowledge bases as an instance of Inductive Logic Programming (ILP), highlighting the connection between symbolic reasoning (DLs) and learning.
  • Universal Models as the Key: The core insight for adapting QBE from relational databases to OES is the use of universal models of the knowledge base. This allows for a unified theoretical framework.
  • Infinite Models and Regularity: A major challenge is the potential infinitude of universal models. The paper's success hinges on exploiting the regularity of these models and developing techniques (like PHom and mosaic-based procedures) to handle them algorithmically.
  • Complexity Implications: The introduction of expressive DLs and inverse roles significantly increases the complexity of QBE compared to relational settings, leading to higher complexity classes like 2-EXPTIME.
  • Witness Query Size: The paper reveals that, unlike in relational databases, witness queries in OES can be double exponentially large, which has practical implications for usability.

Key Results

  • Complexity Results:
    • QBE(Horn-ALCI, CQ/UCQ) and QDEF(Horn-ALCI, CQ/UCQ) are 2-EXPTIME-complete.
  • QBE(Horn-ALC, CQ) and QDEF(Horn-ALC, CQ) are CONEXPTIME-complete.
  • QBE(Horn-ALC, UCQ) and QDEF(Horn-ALC, UCQ) are EXPTIME-complete.
  • Results for unrestricted signatures (QBEf) are also provided, showing some complexity drops for UCQs.
  • Witness Query Size: A lower bound of Ω(2^2^n) for the size of witness queries is established for Horn-ALC. For Horn-ALCI, a four-fold exponential upper bound is suggested.
  • Characterizations: Model-theoretic characterizations for QBE and QDEF are provided based on the universal model and homomorphisms.

Limitations and Future Work

  • Limitations:
    • The theoretical results, particularly the high complexity bounds and large witness query sizes, suggest that practical implementations might require approximations or heuristics.
  • The paper focuses on Horn DLs; extending to non-Horn DLs or Datalog≠ ontologies is noted as a challenging but important next step.
  • Future Work:
    • Investigate QBE for lightweight DLs (DL-Lite, EL) and regular path queries.
  • Develop interactive systems for QBE in OES that allow user interaction to refine queries.
  • Explore heuristics and approximations to manage the high complexity and large query sizes.
  • Study query conservative extensions (QCE) in the context of OES.
  • Connect QBE to learnability of queries and Inductive Logic Programming (ILP), potentially exploring active learning scenarios.
  • Extend the framework to background structures of small degree and local access to data.

Summary updated

BibTeX
@inproceedings{gutierrezbasulto2018reverse,
  author = {Víctor Gutiérrez-Basulto and Jean Christoph Jung and Leif Sabellek},
  title = {{Reverse Engineering Queries in Ontology-Enriched Systems: The Case of Expressive Horn Description Logic Ontologies}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/255},
}
Figure