Answering Conjunctive Queries with Safe Negation and Inequalities over RDFS Knowledge Bases

Gianluca Cima, Marco Console, Roberto Maria Delfino, Maurizio Lenzerini, Antonella PoggiAAAI 2025 · DOI

TL;DR

This paper tackles the challenge of querying knowledge bases (KBs) that use RDFS with disjointness axioms, specifically when queries involve negation and inequality. The authors provide a unified algorithm and establish tight complexity bounds, showing that even simple queries with two negations or inequalities can lead to high computational complexity (II-hardness).

What Problem Does This Paper Address?

Knowledge bases (KBs) are fundamental to many AI systems, storing and organizing information. To effectively use this information, AI systems need to query KBs. While simple queries are well-understood, expressing complex conditions like "individuals that don't have a certain property" (safe negation) or "two different individuals with specific characteristics" (inequality atoms) is crucial for real-world applications. However, adding these features to query languages, even for relatively simple ontology languages like DL-LiteRDFS (a fragment of RDFS with disjointness axioms), dramatically increases the computational difficulty of answering queries. Previous work showed that answering queries with inequalities was already hard (II-complete), but the exact complexity for queries with a fixed number of inequalities and safe negations remained an open question. This paper aims to provide a complete picture of the computational complexity of answering such queries over DL-LiteRDFS ontologies.

Methods

The paper introduces a unified algorithm for answering queries with safe negation and inequalities (UCQ¬s,≠) over DL-LiteRDFS ontologies. This algorithm establishes an upper bound of II in combined complexity and coNP in data complexity. To prove lower bounds and demonstrate the hardness of certain query types, the authors employ sophisticated reductions from known hard problems, specifically the ∀∃-CNF problem, to construct specific queries and ontologies. They analyze different combinations of safe negation and inequality atoms, systematically increasing their number to pinpoint the exact complexity thresholds. For queries with safe negation, they show that allowing up to one negated atom is manageable (NP-complete), but two negated atoms lead to II-hardness. Similarly, for inequalities, they confirm that two inequality atoms are sufficient for II-hardness. The paper also explores the impact of the Unique Name Assumption (UNA) on query answering, showing that for some query types, the complexity remains high even with UNA, while for others, it significantly decreases.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity analysis and uses constructed examples rather than real-world datasets.

Key Insights and Ideas

  • The "two is too many" principle: A key insight is that even a small number of negation or inequality atoms (specifically, two) can push the computational complexity of query answering to its theoretical limits (II-hardness) for DL-LiteRDFS ontologies. This highlights the significant impact of seemingly simple logical constructs on query processing.
  • DL-LiteRDFS as a sweet spot: While many expressive description logics become undecidable with negation and inequalities, DL-LiteRDFS, despite its expressiveness for representing RDFS semantics and data quality constraints, offers a decidable yet computationally challenging framework for these complex queries.
  • Bridging theory and practice: The paper provides tight complexity bounds, which are crucial for understanding the practical feasibility of implementing query answering systems for these types of queries. The results suggest that efficient query answering for complex queries might require specialized algorithms or careful query formulation.
  • Query containment implications: The findings on query answering complexity also have direct implications for query containment problems, a fundamental task in database management and knowledge representation.

Key Results

  • Unified Algorithm: An algorithm for answering UCQ¬s,≠ over DL-LiteRDFS ontologies is presented, achieving II upper bound in combined complexity and coNP in data complexity.
  • II-hardness for two inequalities: The paper confirms the conjecture that answering CQ≠2 (queries with at most two inequality atoms) over DL-LiteRDFS ontologies is II-hard in combined complexity.
  • II-hardness for two negations: Answering CQ¬s,2 (queries with at most two negated atoms) over DL-LiteRDFS ontologies is also shown to be II-hard in combined complexity.
  • NP-completeness for one negation: Queries with at most one negated atom (CQ¬s,1) can be answered in NP-complete combined complexity.
  • Query Containment: The problem of query containment for CQ≠1 vs. CQ≠2 is shown to be II-complete.
  • UNA Impact: The paper provides complexity results under the Unique Name Assumption (UNA), showing that for some query types, complexity remains high, while for others (like CQ≠), it becomes tractable.

Limitations and Future Work

  • Decidability of DL-Litecore: The authors note that the decidability of answering queries over DL-Litecore (a fragment of DL-LiteRDFS without role disjointness) remains an open problem.
  • Practical Implementation: While theoretical complexity is established, the paper suggests that implementing practical systems for these II-complete problems would likely involve leveraging techniques like Answer Set Programming (ASP) solvers.
  • Further Exploration of UNA: While some results under UNA are presented, further investigation into its impact on various query types and ontology fragments could be beneficial.
  • More Expressive Languages: Extending these analyses to more expressive description logics or ontology languages would be a natural next step.

Summary updated

BibTeX
@inproceedings{cima2025answering,
  author = {Gianluca Cima and Marco Console and Roberto Maria Delfino and Maurizio Lenzerini and Antonella Poggi},
  title = {{Answering Conjunctive Queries with Safe Negation and Inequalities over RDFS Knowledge Bases}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i14.33625},
}
Figure