Query-Answer Causality in Databases: Abductive Diagnosis and View Updates

Babak Salimi, Leopoldo E. Bertossi

TL;DR

This paper bridges the gap between query causality in databases and abductive diagnosis, and also connects it to the view-update problem. By establishing these novel links, the authors derive new complexity results for query causality and related areas, offering a more unified understanding of how to explain and manage data.

What Problem Does This Paper Address?

Understanding why a database query returns a certain result, or why data violates integrity constraints, is crucial for data management. This paper focuses on "query causality," which aims to identify the specific data tuples that "caused" a query's outcome. While causality has been explored in knowledge representation, its application to databases is relatively new. The authors tackle the challenge of extending query causality to more complex query types like Datalog (which allows recursion) and, importantly, connect it to two other established areas: abductive diagnosis (explaining observations based on hypotheses) and the view-update problem (how changes in base tables propagate to views). They aim to leverage the relationships between these fields to gain new insights and complexity results.

Methods

The paper establishes connections by formalizing relationships between concepts. For query causality and Datalog, they leverage the fact that Datalog queries can be viewed as logic programs. This allows them to map query causality problems to abductive diagnosis problems on these programs. Specifically, they show that actual causes for query answers correspond to relevant hypotheses in abductive diagnosis.

For the view-update problem, particularly "delete-propagation" (how deleting tuples from a view affects base tables), they connect different variants of this problem to query causality concepts. For instance, the "minimal source-side-effect" problem in delete-propagation is linked to finding "most responsible causes" in query causality, and the "view side-effect-free" problem is linked to "view-conditioned causality." These connections are established through formal definitions and propositions that demonstrate mutual reducibility between the problems.

Datasets

Not discussed in the paper. The paper focuses on theoretical connections and complexity results using abstract database instances and query definitions rather than specific datasets.

Key Insights and Ideas

  • Unifying Causality, Diagnosis, and View Updates: The paper's core contribution is demonstrating that these seemingly distinct areas in databases are deeply interconnected. This unification allows for cross-pollination of results and techniques.
  • Datalog Causality via Abduction: By framing query causality for Datalog queries as an abductive diagnosis problem, the authors extend causality analysis to recursive queries, a significant class of queries not fully covered by prior work.
  • View Updates as Causality Problems: The paper shows that different facets of the delete-propagation problem (a key aspect of view updates) can be precisely mapped to specific types of query causality (actual causes, most responsible causes, and view-conditioned causes). This provides a new perspective on how to solve view update challenges.
  • New Complexity Results: The established connections lead to novel complexity findings for query causality, particularly for Datalog queries (NP-complete in data), and for variants of the delete-propagation problem.

Key Results

  • Datalog Causality: Deciding tuple causality for boolean Datalog queries (including recursive ones) is NP-complete in data.
  • Tractable Datalog Causality: For guarded Datalog queries and databases with bounded tree-width, query causality becomes fixed-parameter tractable.
  • View-Conditioned Causality: The problem of deciding if a query answer has a view-conditioned cause is NP-complete for conjunctive queries (CQs) and unions of CQs (UCQs).
  • Delete-Propagation Complexity: Computing the size of a solution to the minimum source-side-effect problem is FP NP(log(n)) hard. However, for weakly linear queries, the minimum source-side-effect decision problem is tractable.

Limitations and Future Work

  • Focus on Monotone Queries: The causality definitions and many results in the paper are based on monotone queries. Extending these to non-monotone queries would be a significant future direction.
  • Data Complexity vs. Combined Complexity: While the paper explores both, the focus on data complexity for Datalog abduction and its implications for query causality is a key aspect. Further exploration of combined complexity for various scenarios could be valuable.
  • Practical Implementation: The paper is primarily theoretical. Investigating efficient algorithms and practical implementations for these causality and diagnosis problems in real-world database systems would be a natural next step.
  • Integrity Constraints: The paper mentions that integrity constraints are not explicitly considered but notes their connection to consistency-based diagnosis. Incorporating integrity constraints into the causality framework could lead to richer explanations.

Summary updated

Abstract

Causality has been recently introduced in databases, to model, characterize and possibly compute causes for query results (answers). Connections between query causality and consistency-based diagnosis and database repairs (wrt. integrity constrain violations) have been established in the literature. In this work we establish connections between query causality and abductive diagnosis and the view-update problem. The unveiled relationships allow us to obtain new complexity results for query causality -the main focus of our work- and also for the two other areas.
BibTeX
@inproceedings{salimi2015query,
  author = {Babak Salimi and Leopoldo E. Bertossi},
  title = {{Query-Answer Causality in Databases: Abductive Diagnosis and View Updates}},
  booktitle = {ACI @ UAI},
  year = {2015},
  url = {https://openreview.net/forum?id=uknbtaik5m},
}
Figure