Epistemic Disjunctive Datalog for Querying Knowledge Bases

Gianluca Cima, Marco Console, Maurizio Lenzerini, Antonella PoggiAAAI 2023 · DOI

TL;DR

This paper introduces DataKlog, a novel query language for knowledge bases (KBs) that combines the expressive power of Disjunctive Datalog with a modal epistemic operator. This allows for recursive, disjunctive, and even non-monotonic queries while crucially avoiding undecidability by restricting interaction with the KB through the epistemic operator.

What Problem Does This Paper Address?

Querying knowledge bases (KBs) is a fundamental task in artificial intelligence. While simple query languages like Unions of Conjunctive Queries (UCQs) are well-understood, real-world scenarios often require more expressive features like recursion (similar to Datalog) and negation. However, adding these features to existing query languages often leads to undecidability, meaning there's no guaranteed algorithm to answer queries. This is particularly problematic when querying KBs represented in lightweight description logics (DLs) like DL-Lite. The authors aim to bridge this gap by proposing a new query language that can handle recursion, negation, and disjunction without sacrificing decidability, by carefully controlling how these features interact with the underlying KB.

Methods

The core innovation is the DataKlog query language. It builds upon Disjunctive Datalog but introduces a modal epistemic operator, denoted by 'K'. This operator signifies "is known to hold in the KB." The key idea is that recursive rules in DataKlog can only access information from the KB that is known to be true in all possible models of the KB. This epistemic constraint prevents the undecidability issues that arise from unrestricted recursion or negation interacting directly with the KB.

DataKlog has two main types of rules:

  1. Epistemic Rules: These rules use an EQL (Epistemic Query Language) formula in the body, which can involve the epistemic operator K. For example, ∀x.∃v.K(hasVariant(x, v)) → N(x) means "if it is known that patient x has some variant v, then x is a known patient (N)."
  2. Disjunctive Datalog Rules: These are standard Disjunctive Datalog rules, allowing for disjunction in the head and negation/inequalities in the body.

The paper also defines various fragments of DataKlog by restricting features like inequalities (I), negation (N), and disjunction (D), and compares their expressive power to other established query languages like UCQ and Datalog.

Datasets

Not discussed in the paper. The paper focuses on theoretical expressiveness and query answering complexity over generic knowledge bases (KBs) and their models, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Epistemic Operator as a Decidability Shield: The most crucial insight is how the epistemic operator 'K' acts as a "decidability shield." By forcing recursive rules to only query "known" facts, it circumvents the undecidability problems that plague unrestricted recursive queries over DL-based KBs.
  • Distinguishing "Known" vs. "Possible": DataKlog allows for a finer-grained distinction between what is known to be true for some elements and what is known to be true for known elements. This is a subtle but powerful capability not present in standard Datalog.
  • Expressive Power Without Undecidability: The paper demonstrates that DataKlog can express complex navigational queries and non-monotonic reasoning patterns that are otherwise undecidable, even over lightweight KBs.
  • Feature Minimality: The authors show that the combination of recursion, disjunction, and negation in DataKlog is "minimal" in the sense that removing any of these features can lead to a loss of expressive power.

Key Results

  • Decidability Guarantee: For any KB language L and embedded query language Q where Q queries over L KBs are decidable and L-range-restricted, DataKlog(Q) query answering is also decidable. This is a significant theoretical result.
  • Complexity Analysis: The paper provides tight upper bounds for the data complexity of DataKlog query answering, showing it can range from P-complete to coNP-complete and even Σ-complete, depending on the features of DataKlog used and the complexity of the embedded query language.
  • Expressiveness Comparisons:
    • DataKlog(CQ) is strictly more expressive than UCQ over trivial KBs.
  • Over DL-LiteRDFS KBs (which don't allow incomplete information), DataKlog(CQ) fragments are equivalent to UCQ or Disjunctive Datalog, showing the epistemic operator has less impact when the KB itself is "simpler."
    • Crucially, over DL-Litecore KBs (which do allow incomplete information), DataKlog(CQ) is strictly more expressive than Datalog, highlighting the power of the epistemic operator in richer KB settings.
  • The paper shows that semi-positive negation is essential for achieving certain coNP-hardness results in DataKlog.

Limitations and Future Work

  • Focus on FOL Embedded Queries: The current work primarily focuses on embedded query languages that are fragments of First-Order Logic (FOL). Future work aims to extend this to other query languages.
  • Semantics Exploration: The paper uses stable model semantics. Future work plans to investigate alternative semantics, such as well-founded and perfect model semantics.
  • Empirical Evaluation: While the theoretical results are strong, the paper does not include empirical evaluations on real-world datasets. This would be a natural next step to demonstrate practical applicability.
  • Specific KB Languages: The expressiveness results are often tied to specific KB languages (e.g., DL-Litecore, DL-LiteRDFS). Further exploration of DataKlog's capabilities over a wider range of KB formalisms would be valuable.

Summary updated

BibTeX
@inproceedings{cima2023epistemic,
  author = {Gianluca Cima and Marco Console and Maurizio Lenzerini and Antonella Poggi},
  title = {{Epistemic Disjunctive Datalog for Querying Knowledge Bases}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i5.25773},
}
Figure