Explainable Certain Answers

Giovanni Amendola, Leonid LibkinIJCAI 2018 · DOI

TL;DR

This paper tackles the challenge of defining "certain answers" to queries over incomplete databases. It introduces the concept of "explainable certain answers" by adding a requirement that the explanation for a possible world must also justify why an answer is considered certain. This new framework successfully justifies the widely used intersection-based notions of certainty in data management.

What Problem Does This Paper Address?

When dealing with databases that contain missing information (represented by null values), we often can't give a single, definitive answer to a query. Instead, the answer might vary depending on how those nulls are filled in. This leads to the idea of "possible worlds" – all the complete databases that could be formed from the incomplete one.

Traditionally, "certain answers" are defined in two main ways:

  1. Intersection-based: These are answers that hold true in every single possible world. This is like finding the common ground across all scenarios.
  2. Informativeness-based: This approach defines certainty based on how "informative" an answer is. A certain answer is the most informative one that is consistent with all possible worlds.

While the intersection-based approach is practical, its theoretical justification has been questioned. The informativeness-based approach, though theoretically appealing, faces significant practical hurdles: certain answers might not even exist, or they could be astronomically large, making them unusable. This paper aims to bridge this gap by providing a solid theoretical foundation for the practical intersection-based methods and addressing the limitations of the informativeness-based approach.

Methods

The core of the paper's contribution lies in introducing a novel framework based on explanations.

  • Action Structures: The authors define a general framework involving "actions" that can modify database objects. These actions are part of a monoid (meaning they can be composed, and there's an identity action). An "oblivious preorder" relates objects based on how actions affect their informativeness.
  • Explanation Structures: Within this framework, "explanations" are a special type of action. These explanations are designed to make objects more informative. A key idea is that for any incomplete object, there's a way to "complete" it using explanations, and once completed, further explanations don't change it.
  • Explainable Candidate and Certain Answers: The paper redefines "candidate answers" and "certain answers" by requiring that the explanation used to justify an answer must also be the same explanation that accounts for a possible world. A certain answer is then the maximal explainable candidate answer.
  • Relating to Existing Notions: The authors then apply this framework to standard Open World Assumption (OWA) and Closed World Assumption (CWA) semantics for relational databases. They show that under these semantics, the "explainable certain answers" precisely correspond to the intersection-based notions of certainty (like $\Box_{OWA}(Q, D)$ and $\Box_{CWA}(Q, D)$).

Datasets

Not discussed in the paper. The paper focuses on theoretical frameworks and general properties of relational databases rather than specific empirical evaluations on datasets.

Key Insights and Ideas

  • The "Why" Matters: The paper argues that simply knowing an answer is true in all possible worlds (intersection-based) or is the most informative (informativeness-based) isn't enough. The reason why it's true or informative is crucial. Explanations provide this missing "why."
  • Bridging Theory and Practice: The introduction of explainable answers successfully bridges the gap between the theoretically appealing but impractical informativeness-based approach and the practically useful but less theoretically grounded intersection-based approach.
  • Justification for Intersection-Based Answers: The paper provides a strong theoretical justification for the widely used intersection-based definitions of certain answers, showing they are not arbitrary but are the maximal explainable answers under standard database semantics.
  • Existence and Size: The paper highlights that while informativeness-based certain answers might not exist or could be prohibitively large, explainable certain answers (which align with intersection-based ones) are well-behaved: they exist and are of manageable (polynomial) size.

Key Results

  • For relational databases under both OWA and CWA semantics, explainable certain answers are precisely the intersection-based certain answers ($\Box_{OWA}(Q, D)$ and $\Box_{CWA}(Q, D)$).
  • Explainable candidate answers under OWA/CWA are exactly the subsets of the respective intersection-based certain answers.
  • The paper demonstrates that for arbitrary FO queries under OWA, informativeness-based certain answers may not exist.
  • Under CWA, informativeness-based certain answers exist but can be doubly exponentially large in the size of the database.
  • For UCQ≠ queries under OWA, informativeness-based answers can be exponentially large.

Limitations and Future Work

  • Other Semantics: The authors suggest extending their explanation framework to other semantics of incompleteness, such as weaker forms of CWA.
  • Application-Specific Explanations: Future work could explore how explanations arise directly in specific applications like data integration, data exchange, and ontology-based data access (OBDA).
  • Different Data Models: The paper focuses on relational databases. Extending the framework to other data models, such as graph databases and RDF (especially concerning blank nodes), is a promising direction.
  • Computational Properties: While the paper establishes the existence and size bounds for explainable certain answers, further investigation into their efficient computation would be valuable.

Summary updated

BibTeX
@inproceedings{amendola2018explainable,
  author = {Giovanni Amendola and Leonid Libkin},
  title = {{Explainable Certain Answers}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/233},
}
Figure