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, extending causality concepts to Datalog queries. By establishing novel connections, the authors derive new complexity results for query causality and shed light on the view-update problem in databases.

What Problem Does This Paper Address?

Understanding why a particular query returns a specific result is crucial in data management, especially with the rise of big data and uncertain information. This is the domain of "query causality," which aims to identify the specific data tuples that are responsible for a query's outcome. While causality has been explored in databases, its connection to "abductive diagnosis" (finding the simplest explanation for an observation) and the "view-update problem" (how changes in base tables propagate to views) has been less clear. This paper aims to formalize these connections, particularly for Datalog queries (which include recursive queries), and leverage them to derive new computational insights.

Methods

The core of this work lies in establishing formal connections between different areas:

  • Query Causality and Abductive Diagnosis: The authors show that actual causes for query answers in Datalog can be precisely characterized in terms of abductive diagnoses. This involves reformulating query causality problems as Datalog abduction problems and vice-versa, enabling the transfer of results between these fields.
  • Query Causality and View-Update Problems: The paper connects query causality to the "delete-propagation" problem, a specific type of view-update scenario. They demonstrate how concepts like "most-responsible causes" relate to minimizing side-effects in source databases, and "view-conditioned causality" relates to ensuring view-side-effect-free updates.
  • Complexity Analysis: By leveraging these connections, the paper derives new complexity results for query causality, particularly for Datalog queries, showing they are NP-complete in data. They also identify tractable cases for specific query classes (e.g., guarded Datalog queries with bounded tree-width).

Datasets

Not discussed in the paper. The paper focuses on theoretical connections and complexity analysis using general database instances and query structures.

Key Insights and Ideas

  • Bridging Abduction and Causality: The most significant insight is the formal equivalence established between actual causes for Datalog query answers and abductive diagnoses. This means we can use well-understood abduction techniques to find query causes and vice-versa, opening up new avenues for research and application.
  • Datalog Causality is NP-Complete: Extending causality to Datalog queries, which are more expressive than simple conjunctive queries (e.g., allowing recursion), leads to a significant complexity jump. The paper proves that deciding tuple causality for Datalog queries is NP-complete in data.
  • View-Update as Causality: The paper elegantly frames aspects of the delete-propagation problem (a key view-update challenge) in terms of causality. This provides a new perspective on how to minimize changes in base tables while achieving desired view updates, by relating them to the strength of causes.
  • Tractable Cases Identified: Despite the general NP-completeness, the paper identifies specific scenarios (e.g., guarded Datalog queries with bounded tree-width) where causality problems become tractable, offering practical avenues for implementation.

Key Results

  • Mutual Characterizations: Precise connections and computational reductions are established between causality for Datalog queries and abductive diagnosis.
  • Datalog Causality Complexity: Deciding tuple causality for Datalog queries (including recursive ones) is shown to be NP-complete in data.
  • View-Conditioned Causality Complexity: The view-conditioned causality decision problem is NP-complete for conjunctive queries (CQs) and more general queries.
  • Delete-Propagation Complexity: Computing the size of a solution to the minimum source-side-effect problem is FPNP(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 are presented for monotone queries. Extending these to non-monotone queries would be a natural next step.
  • Complexity of Specific Query Classes: While some tractable cases are identified, further exploration into specific classes of Datalog queries and their causality complexity could be beneficial.
  • Practical Implementation: The paper lays the theoretical groundwork. Future work could focus on developing efficient algorithms and practical systems that leverage these connections for real-world database applications.
  • Integrity Constraints: The paper mentions that integrity constraints are not considered in this work, but notes their relevance 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