Answering Regular Path Queries Under Approximate Semantics in Lightweight Description Logics

Oliver Fernández Gil, Anni-Yasmin TurhanAAAI 2021 · DOI

TL;DR

This paper tackles the challenge of answering complex graph queries (C2RPQs) in knowledge bases with approximate semantics. They extend existing methods for graph databases to ontology-mediated query answering (OMQA) over lightweight description logics (DLs), providing algorithms and complexity analysis for these new capabilities.

What Problem Does This Paper Address?

Regular Path Queries (RPQs) are powerful for navigating graph-structured data, but can be too rigid. In real-world scenarios, data might be incomplete, inconsistent, or users might not know the exact structure, making exact queries yield no results. This paper addresses the need for approximate semantics for RPQs, allowing for "close enough" answers. While this has been explored for standard graph databases, it's less understood in the context of ontology-mediated query answering (OMQA). OMQA uses ontologies (formal knowledge bases) to enrich data, and typically assumes an "open world" where missing information doesn't imply falsehood. The paper specifically focuses on extending approximate RPQ answering to lightweight Description Logics (DLs) like ELH and DL-Lite, which are foundational for OWL 2 EL and OWL 2 QL profiles.

Methods

The core of the paper's approach is adapting the transducer-based approximation method. This involves using Weighted Finite-State Transducers (WFTs) to model "distortions" of query paths. A WFT can transform an input string (representing a path) into an output string, assigning a cost to this transformation.

The authors make two key extensions:

  1. From RPQs to C2RPQs: They first generalize the transducer-based approximate semantics from simple RPQs to Conjunctive Two-Way Regular Path Queries (C2RPQs). C2RPQs are more expressive, allowing conjunctions of path queries and traversal of edges in both directions.
  2. From Graph Databases to OMQA: They then extend this to the OMQA setting. This involves defining "certain approximate answers" which are answers that hold across all possible models of the knowledge base (ontology + data), but with an associated approximation cost. They leverage the concept of canonical models for DLs to make reasoning tractable.

For answering these queries, they develop algorithms that involve constructing weighted graphs based on the query, the transducer, and the canonical model of the knowledge base. They analyze the computational complexity of key reasoning problems, such as "T-entailment" (checking if a tuple is a certain approximate answer within a given cost threshold) and computing the exact approximation cost.

Datasets

Not discussed in the paper. The paper focuses on theoretical contributions and algorithmic development, using examples and theoretical knowledge bases rather than specific real-world datasets.

Key Insights and Ideas

  • Approximate Semantics for OMQA is Crucial: The paper highlights that for real-world applications, especially those involving ontologies, approximate query answering is not just a convenience but a necessity for obtaining meaningful results.
  • Transducers as a Flexible Tool: WFTs prove to be a versatile mechanism for defining and quantifying "acceptable" deviations from exact query paths, adaptable to various approximation needs.
  • Canonical Models Enable Tractability: The use of canonical models for lightweight DLs is key to making approximate query answering computationally feasible, by allowing reasoning over a finite, representative structure.
  • Generalizing "Certain Answers": The concept of "certain approximate answers" elegantly extends the standard notion of certain answers in OMQA, providing a robust way to handle uncertainty and approximation in knowledge bases.
  • Complexity Trade-offs: The paper provides a detailed complexity analysis, showing that while approximate answering can increase complexity, it remains manageable for lightweight DLs, often matching or closely following the complexity of exact query answering.

Key Results

The paper establishes the following:

  • Complexity Bounds:
    • For 2RPQs (a sub-case of C2RPQs), T-entailment is NL-complete (P-complete) in data (combined) complexity for DL-Lite, and P-complete for ELH.
  • For C2RPQs, T-entailment is PTime (PSpace) in data (combined) complexity for both DLs.
  • The cost computation problem is solvable in polynomial time for 2RPQs and polynomial (exponential) time for C2RPQs in data (combined) complexity.
  • Algorithmic Contributions: They devise algorithms for answering approximate 2RPQs and C2RPQs over ELH and DL-Lite knowledge bases, extending previous work on graph databases.
  • Flexibility: The proposed framework is parameterized by a distortion transducer and a combining function, allowing it to be adapted to different application requirements.

Limitations and Future Work

  • Expressiveness of DLs: The current work is focused on lightweight DLs (ELH, DL-Lite). Future work aims to extend these techniques to more expressive DLs like ELI and ALC. For ALC, the canonical model property does not hold, requiring different approaches.
  • Computational Complexity for More Expressive DLs: While ELI is expected to maintain similar data complexity, combined complexity is likely to inherit hardness from instance checking.
  • Alternative Approaches for ALC: For ALC, the authors suggest exploring the use of tree automata to represent KB models, in conjunction with query NFAs and transducers.
  • Practical Evaluation: The paper focuses on theoretical foundations and algorithmic design. A next step would be to implement these algorithms and evaluate them on real-world benchmarks.

Summary updated

BibTeX
@inproceedings{gil2021answering,
  author = {Oliver Fernández Gil and Anni-Yasmin Turhan},
  title = {{Answering Regular Path Queries Under Approximate Semantics in Lightweight Description Logics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i7.16787},
}
Figure