Counting Query Answers over a DL-Lite Knowledge Base

Diego Calvanese, Julien Corman, Davide Lanti, Simon RazniewskiIJCAI 2020 · DOI

TL;DR

This paper investigates the computational complexity of counting answers to queries over knowledge bases (KBs) that use DL-Lite, a family of description logics. The authors establish new bounds for this problem, showing that query shape significantly impacts tractability, and introduce a novel query rewriting technique for a specific DL-Lite variant.

What Problem Does This Paper Address?

In data management, counting the number of results for a query is a fundamental operation. This paper tackles this problem in the context of Ontology-Mediated Query Answering (OMQA) or Ontology-Based Data Access (OBDA). Here, a knowledge base (KB) combines explicit data (an ABox) with background knowledge (a TBox) expressed in description logics (DLs). The challenge arises when counting answers needs to consider both explicit data and the implicit information provided by the TBox, especially when the TBox includes number restrictions (e.g., "at least 3 children"). Existing work has shown that answering such queries can be computationally expensive (coNP-hard in data complexity). This paper aims to precisely characterize the complexity of counting answers by exploring how different DL-Lite variants and different query shapes (like connected, linear, or branching queries) affect this complexity, and to develop techniques for efficient query answering.

Methods

The paper delves into the data complexity of counting answers for Conjunctive Queries (CQs) over DL-Lite knowledge bases. Key methodological contributions include:

  • Complexity Analysis: The authors systematically analyze the computational complexity of the COUNT problem (deciding if a query has exactly k answers) for various DL-Lite variants and CQ shapes. They establish new lower bounds (P-hardness) and upper bounds (P, coNP, LOGSPACE) for these combinations.
  • Query Rewriting: A novel query rewriting technique, named PerfectRefcnt, is introduced. This algorithm transforms a DL-Lite query into a query in a target language (FO(COUNT)) that can be evaluated over the ABox alone. This rewriting is designed to capture the "anonymous contribution" of existential individuals implied by the TBox, a crucial aspect for count semantics.
  • Formalization: The paper adapts and uses the "count semantics" for query answering, which accounts for both explicit and existentially quantified individuals.

Datasets

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

Key Insights and Ideas

  • Query Shape Matters: The shape of a conjunctive query (connected, linear, branching, cyclic) significantly impacts the tractability of counting answers. For instance, disconnected or branching queries can lead to intractability even for simpler DLs, while linear and connected queries can be tractable.
  • Cyclicity Not Always Necessary for Intractability: The paper shows that disconnectedness or branching alone can be sufficient for coNP-hardness, suggesting that cyclicity, while often present in hard cases, isn't always the sole culprit.
  • Rewritability is Possible (with Caveats): For a specific DL-Lite variant (DL-LiteN-core) and certain query shapes (rooted, connected CQs), the paper demonstrates that queries can be rewritten into a form evaluable over the ABox. This is a significant step towards practical query answering.
  • The Challenge of Anonymous Contributions: The core difficulty in rewriting lies in capturing the "anonymous contribution" – how existentially quantified individuals implied by the TBox affect the count. The PerfectRefcnt algorithm is specifically designed to address this.

Key Results

  • P and coNP Bounds: The paper establishes new complexity bounds, including P and coNP lower bounds, and upper bounds in P and LOGSPACE for counting answers over various DL-Lite variants and query shapes.
  • Tractability for Specific Cases: Proposition 1 shows that COUNT is in P for DL-LiteposHN and connected, linear CQs. Proposition 12 shows COUNT is in LOGSPACE for DL-Litecore and rooted, connected CQs.
  • Intractability for General Cases: Proposition 2 demonstrates coNP-hardness for DL-Litepos and acyclic, linear, but disconnected CQs. Proposition 4 shows coNP membership for DL-LitecoreHN and arbitrary CQs.
  • Rewriting Algorithm: The PerfectRefcnt algorithm is presented as a correct rewriting technique for DL-LiteN-core and rooted, connected CQs, transforming them into a FO(COUNT) language.

Limitations and Future Work

  • Practical Algorithm: The authors acknowledge that their work is primarily theoretical and does not deliver a ready-to-use practical algorithm for counting answers over DL-Lite KBs.
  • Data Complexity Definition: The adopted definition of data complexity, which treats the integer k as part of the input size, might not fully capture scenarios where cardinality restrictions in the TBox (encoded in binary) grow with data size.
  • Rewritability for Role Subsumption: An open question is whether rewritability still holds for rooted queries and DL-LiteHN (which allows restricted role subsumption).
  • Arithmetic Operations in Rewriting: Future work could focus on developing rewritings that handle arithmetic operations and nested aggregations more efficiently, especially when cardinality restrictions are large.
  • Tightness of P-Membership: The paper poses an open question about whether the P-membership result for DL-LiteposHN and AQ/CQCL is tight, given the P-hardness result for AQ over a more expressive DL.

Summary updated

BibTeX
@inproceedings{calvanese2020counting,
  author = {Diego Calvanese and Julien Corman and Davide Lanti and Simon Razniewski},
  title = {{Counting Query Answers over a DL-Lite Knowledge Base}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/230},
}
Figure