Answering Conjunctive Queries with Inequalities in DL-Liteℛ

Gianluca Cima, Maurizio Lenzerini, Antonella PoggiAAAI 2020 · DOI

TL;DR

This paper tackles the challenge of answering queries with inequality constraints in the DL-Liteℛ description logic, a common framework for ontology-based data access. The authors introduce two novel strategies to regain decidability and tractability, focusing on weakening either the ontology language or the query language, and provide tight complexity bounds for these scenarios.

What Problem Does This Paper Address?

Ontology-based data access (OBDA) systems aim to query large datasets using ontologies that describe the domain. DL-Liteℛ is a popular description logic for OBDA, known for its efficient query answering capabilities, particularly for Unions of Conjunctive Queries (UCQs). However, standard UCQs lack the expressive power to handle negation, specifically the "not equal" predicate. This limitation prevents expressing simple yet crucial queries, like finding all triangles in a graph.

While adding inequalities to queries (CQ=s) is desirable, it generally leads to undecidability in DL-Liteℛ. This paper addresses this fundamental problem by exploring ways to make query answering with inequalities decidable and, ideally, tractable. The authors investigate two main avenues: modifying the ontology language and restricting the query language.

Methods

The paper proposes two main strategies to overcome the undecidability of query answering with inequalities:

  1. Weakening the Ontology Language: The authors introduce DL-LiteRDFS, a sublanguage of DL-Liteℛ that extends RDFS with inequality axioms and disjointness axioms. This variant eliminates constructs that introduce incomplete information from existential quantifiers, aiming to simplify reasoning.
  2. Weakening the Query Language: The second strategy keeps DL-Liteℛ as the ontology language but restricts the query language. They define (U)CQs with bounded inequalities (UCQ=,b), where inequality predicates are only applied to individuals or distinguished variables, preventing their use with existentially quantified variables.

For reasoning, the paper utilizes a modified "chase" procedure, a standard technique in description logic reasoning, to construct a canonical interpretation (IO) that captures the semantics of the ontology. This interpretation is instrumental in deriving the complexity results.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Inequalities are a double-edged sword: While essential for expressiveness, inequalities drastically increase the complexity of query answering, often leading to undecidability.
  • Decidability through restriction: The paper demonstrates that by either simplifying the ontology language (DL-LiteRDFS) or restricting the query language (UCQ=,b), decidability and tractability can be recovered.
  • The power of bounded inequalities: The class of UCQ=,b queries over DL-Liteℛ ontologies retains AC0 data complexity, matching the efficiency of standard UCQs, which is a significant achievement.
  • Union's impact: The introduction of union operators in queries with inequalities can lead to a dramatic jump in complexity, from constant time to Πp2-hardness, even with a limited number of inequalities.
  • Canonical interpretation is key (but not always sufficient): The canonical interpretation (IO) is crucial for answering CQ=,b queries, but for more complex queries like UCQ=,b, it's not enough on its own, requiring further reasoning techniques.

Key Results

The paper establishes tight complexity bounds for query answering under the proposed strategies:

  • DL-LiteRDFS ontologies:
    • Answering UCQ=s is coNP-complete in data complexity and Πp2-complete in combined complexity.
  • Answering UCQ2,=s (queries with at most two inequalities per disjunct) is Πp2-hard in combined complexity.
  • Answering UCQ1,=s (queries with at most one inequality per disjunct) is PTIME-complete in data complexity and NP-complete in combined complexity.
  • DL-Liteℛ ontologies with UCQ=,b queries:
    • Answering CQ=,b is in AC0 in data complexity and NP-complete in combined complexity.
  • Answering UCQ=,b is in AC0 in data complexity and Πp2-complete in combined complexity.

Limitations and Future Work

The authors acknowledge several open questions and future research directions:

  • Minimum inequalities for hardness: Determining the exact minimum number of inequalities required for Πp2-hardness in combined complexity for DL-LiteRDFS ontologies remains an open conjecture (believed to be 2).
  • Extensions of DL-Liteℛ and UCQ=,b: Exploring extensions of these formalisms that maintain decidability and tractability is a promising avenue.
  • Decidability of CQ=s over DL-Litecore: The decidability of answering conjunctive queries with inequalities over DL-Litecore ontologies (a fragment of DL-Liteℛ) is still an open problem.
  • Connection to other problems: Further investigation into the relationship between query answering with inequalities and problems like query containment in databases and SPARQL semantics for OWL 2 QL is suggested.

Summary updated

BibTeX
@inproceedings{cima2020answering,
  author = {Gianluca Cima and Maurizio Lenzerini and Antonella Poggi},
  title = {{Answering Conjunctive Queries with Inequalities in DL-Liteℛ}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i03.5666},
}
Figure