Source-linked AI summary
The Complexity of Causality and Responsibility for Query Answers and non-Answers
Alexandra Meliou, Wolfgang Gatterbauer, Katherine F. Moore, Dan Suciu
TL;DR
The paper addresses how to identify causes and rank their responsibility for query answers and non-answers beyond lineage alone. It adapts formal causality definitions to conjunctive queries and finds that causality is tractable, while responsibility has a query-dependent PTIME/NP-hard dichotomy with a max-flow algorithm for tractable cases.
Problem
Lineage explains query answers and non-answers but generally contains more information than the causes, motivating formal cause and responsibility measures.
Method
The paper adapts Halpern, Pearl, and Chockler’s causality definitions to Why-So and Why-No conjunctive queries and analyzes data complexity using contingency sets.
Results
Causality for conjunctive queries is always in PTIME and relationally computable; responsibility has a PTIME/NP-hard dichotomy without self-joins, with PTIME cases reduced to max flow.
Takeaways & Limitations
Causality can be retrieved efficiently with a relational query, whereas responsibility provides a harder but useful ranking of candidate causes.
Takeaways & Limitations
For conjunctive queries with self-joins, the paper proves NP-hardness in general but does not establish a complete dichotomy.
Abstract
from arXiv · showhide
An answer to a query has a well-defined lineage expression (alternatively called how-provenance) that explains how the answer was derived. Recent work has also shown how to compute the lineage of a non-answer to a query. However, the cause of an answer or non-answer is a more subtle notion and consists, in general, of only a fragment of the lineage. In this paper, we adapt Halpern, Pearl, and Chockler's recent definitions of causality and responsibility to define the causes of answers and non-answers to queries, and their degree of responsibility. Responsibility captures the notion of degree of causality and serves to rank potentially many causes by their relative contributions to the effect. Then, we study the complexity of computing causes and responsibilities for conjunctive queries. It is known that computing causes is NP-complete in general. Our first main result shows that all causes to conjunctive queries can be computed by a relational query which may involve negation. Thus, causality can be computed in PTIME, and very efficiently so. Next, we study computing responsibility. Here, we prove that the complexity depends on the conjunctive query and demonstrate a dichotomy between PTIME and NP-complete cases. For the PTIME cases, we give a non-trivial algorithm, consisting of a reduction to the max-flow computation problem. Finally, we prove that, even when it is in PTIME, responsibility is complete for LOGSPACE, implying that, unlike causality, it cannot be computed by a relational query.
1. INTRODUCTION
The paper adapts formal causality and responsibility to explain surprising query answers and non-answers, distinguishing useful causes from large lineages. It proves tractable causality for conjunctive queries and a complexity dichotomy for responsibility.
- Framework: The paper adapts Halpern, Pearl, and Chockler’s formal notions of causality and responsibility to database queries.Responsibility measures degree of causality and ranks candidate causes by their relative contributions.
- Motivation: Users need causes of surprising database query answers or non-answers, because lineage alone can overwhelm them.The IMDB example’s two surprising genres have a combined lineage of 137 base tuples.
- Illustration: Responsibility rankings identify informative causes in the IMDB example, including Sweeney Todd and ambiguous director tuples.The ranking helps users focus on a small set of explanations rather than the full lineage.
- Main results: Causality for any conjunctive query has PTIME data complexity, and all causes can be retrieved by a first-order relational query.The query may require one level of negation; under stated no-self-join and table-partition conditions, Why-So causes can be retrieved conjunctively.
- Main results: For conjunctive queries without self-joins, responsibility has a dichotomy: it is either computable in PTIME or checking a threshold is NP-hard.The PTIME cases use a non-obvious reduction to Ford–Fulkerson max flow, while self-join queries remain harder to classify.
2. QUERY CAUSE AND RESPONSIBILITY
The paper formalizes Why-So and Why-No causality for conjunctive queries using endogenous tuples and contingency sets, then defines responsibility from minimal contingency size. It studies the resulting causality and responsibility problems under data complexity.
- Setting: A database is partitioned into endogenous tuples, which may be causes, and exogenous tuples, which provide the fixed context.For each relation, the schema distinguishes endogenous and exogenous tuple subsets.
- Causality definitions: A counterfactual cause changes the query result when removed, while an actual cause becomes counterfactual after removing a suitable endogenous contingency set.Every counterfactual cause is therefore an actual cause with an empty contingency.
- Causality types: Why-So causality explains an actual answer, whereas Why-No causality explains a non-answer through potentially missing endogenous tuples.Why-No treats the real database as exogenous and adds candidate missing tuples when testing causes.
- Example: In the IMDB example, Sweeney Todd has responsibility 1/3, while Manon Lescaut has responsibility 1/5 under their respective minimal contingencies.The examples show how responsibility ranks causes by the number of tuples that must be removed or added.
- Complexity formulation: The paper studies data complexity with the query fixed, reducing non-Boolean answer analysis to Boolean queries by substituting the answer constants.It defines separate causality and responsibility problems over the endogenous tuples.
3. COMPLEXITY OF CAUSALITY
For conjunctive queries, causality is tractable and can be expressed using relational queries with limited negation. The paper characterizes actual causes through n-lineage and gives conditions under which causality simplifies to conjunctive queries.
- Causality for all conjunctive queries has PTIME data complexity, unlike causality for arbitrary Boolean expressions, which is NP-complete.
- The n-lineage is obtained by computing standard lineage and setting variables for all exogenous tuples to true, leaving an expression over endogenous tuples.
- Actual causes are exactly the endogenous tuples appearing in non-redundant conjuncts of the n-lineage.Theorem 3.2 equates actual causality with the existence of a suitable contingency and membership in a non-redundant n-lineage conjunct.
- All causes can be computed by a non-recursive stratified Datalog program with negation using only two strata.This provides a relational-query formulation for causes of answers and non-answers that can run entirely in the database system.
- Negation is generally necessary because causality is non-monotone: adding tuples can cause existing tuples to cease being causes.The examples show non-monotonicity with mixed endogenous/exogenous relations and with self-joins.
- When each relation is wholly endogenous or exogenous and endogenous relations occur at most once, each causal query is a single conjunctive query without negation.
4. COMPLEXITY OF RESPONSIBILITY
The paper establishes a complexity dichotomy for responsibility in conjunctive queries without self-joins: weakly linear queries are tractable, while non-weakly-linear queries are NP-hard. It also gives a max-flow-based PTIME algorithm for linear queries and shows Why-No responsibility is tractable.
- Hard cases: Three canonical conjunctive queries are NP-hard, and rewriting transfers hardness from these queries to more complex queries.If a rewritten query is NP-hard, the original query is NP-hard; final queries reduce to one of the canonical hard queries.
- PTIME cases: For any linear query, an endogenous tuple’s responsibility can be computed in PTIME using a reduction to max-flow.The network’s minimum cut corresponds to a minimum contingency set, and Ford-Fulkerson computes the cut in PTIME.
- PTIME cases: Weakening preserves PTIME responsibility, so queries that can be weakened to linear queries are weakly linear and tractable.The reduction works because weakening affects exogenous or dominated atoms that are not part of minimum contingencies.
- Dichotomy: Responsibility for conjunctive queries without self-joins is either computable in PTIME or NP-hard, determined by whether the query is weakly linear.Weakly linear queries are in PTIME; queries that are not weakly linear are NP-hard.
- Scope and boundaries: The analysis proves LOGSPACE-hardness for a specific Why-So responsibility query and NP-hardness for queries with self-joins.A complete dichotomy for self-join queries remains open, including the query Rn(x, y), Rn(y, z).
- Why-No responsibility: For non-answers, computing Why-No responsibility is in PTIME.This contrasts with the more complex dichotomy established for Why-So responsibility.
5. RELATED WORK
The work connects database causality to provenance and prior formal accounts of causality. It treats Why-So and Why-No explanations symmetrically while allowing endogenous and exogenous tuples to be distinguished.
- Causality: The paper adapts Halpern–Pearl causality and Chockler–Halpern responsibility to conjunctive database queries without requiring a causal network.Its definitions cover both Why-So and Why-No causality and responsibility.
- Provenance: Why-So causality is closely connected to why-provenance when all database tuples are endogenous, while this work additionally supports endogenous–exogenous partitioning.The partition may be application-dependent or chosen by the user at query time.
- Missing query results: The paper relates Why-No causality to prior approaches that explain missing answers through tuple insertions, modifications, or query-plan operators.It presents Why-No causality as a database explanation framework for non-answers.
- Unifying perspective: Why-So and Why-No causality provide symmetric positive and negative provenance, with responsibility applied uniformly to both cases.The paper also gives Datalog constructions for computing tuple causes under an endogenous–exogenous partition.
6. CONCLUSIONS
The paper introduces database causality for explaining answers and non-answers, retrieves causes relationally, and analyzes causality and responsibility for conjunctive queries.
- Causality provides a framework for explaining answers and non-answers in databases.
- All causes for answers or non-answers can be retrieved using a relational query.
- Why-provenance defines sets of tuples, whereas Why-So causality compares their union and is not generally identical to endogenous why-provenance tuples.
- Causality is always computable in PTIME, while responsibility has a dichotomy for queries without self-joins.
- An earlier proof contained a bug identified by Benny Kimelfeld.
A. NOMENCLATURE
The nomenclature distinguishes database instances, endogenous and exogenous tuples, query lineage objects, causes, responsibilities, and canonical hard queries.
- D denotes a database instance, while Dn and Dx denote endogenous and exogenous tuples, respectively.
- Γ denotes a contingency, CRi denotes causes in relation Ri, and ρt denotes tuple t’s responsibility.
- Φ denotes lineage, Φn denotes endogenous lineage, HD denotes the dual hypergraph, and h∗ denotes a weakened query.
- h∗1, h∗2, and h∗3 are the canonical hard queries of Theorem 4.1.
B. PROOFS CAUSALITY
The causality proof characterizes causes through non-redundant endogenous lineage clauses and constructs a stratified Datalog query that returns all causes.
- A tuple is a cause exactly when its Boolean variable appears in a non-redundant clause of the endogenous lineage.
- For Why-So answers, variables absent from the reduced lineage cannot be causes, while variables in a clause become counterfactual under a contingency removing the other clause variables.
- For Why-No non-answers, a variable in a reduced lineage clause becomes counterfactual under a contingency retaining the other variables in that clause.
- A refinement assigns every query atom as endogenous or exogenous, yielding 2m refinements whose lineages are combined.
- Repeated variable identifications and substitutions generate fewer than 2k2 image queries, with k bounded by query size.
- The Datalog program uses embedding predicates and cause predicates CRi to compute all causes in its output predicates.
C. CANONICAL HARD QUERIES
The hardness constructions encode hypergraphs, colored graphs, and 3SAT formulas as database instances and contingency problems for canonical queries.
- For h∗1, a 3-partite 3-uniform hypergraph becomes relations R, S, T for vertices and W for hyperedges, plus four additional tuples.
- The responsibility of r0, s0, t0, or w0 is 1/(1+|S|), where S is a minimum contingency corresponding to a minimum hypergraph vertex cover.
- For h∗2, a 3-colored graph corresponds to relations R, S, and T, and query truth corresponds to the presence of a 3-cycle.
- A minimum contingency in the colored graph is a smallest edge set containing at least one edge from every cycle.
- Each variable receives a local ring whose length mi is odd, a multiple of 3, and at least 9|CXi|.
- An odd local ring has exactly two minimum forward-edge contingencies of size mi, associated with true and false assignments.
- Each clause occupies nine node pairs in its variables’ rings, mapping its literals to three graph edges with prescribed colors.
- Collapsing selected nodes makes each clause a cycle, and the constructed graph has a contingency of size P exactly when the 3SAT formula is satisfiable.
D. RESPONSIBILITY DICHOTOMY
The responsibility dichotomy classifies conjunctive queries through weakenings, rewrites, and structural conditions, separating PTIME cases from hard cases. Weakly linear queries are solvable in PTIME, while final queries are constrained to exactly 3 variables and satisfy non-containment conditions.
- PTIME cases: If q is in PTIME, then queries obtained by variable deletion, variable addition, or permitted atom deletion are also in PTIME.Variable deletion reduces to q by fixing the deleted variable to a constant; the other rewrite cases preserve or map contingencies.
- Structural proof: The classification proof uses connected components and linear orderings to extend weakenings across rewrites while preserving linearity.Components may fragment in an ordering, but dissociation operations can propagate variables to adjacent exogenous subgoals and restore a linearization.
- Final queries: A final query has exactly 3 variables, and no variable's subgoal set is contained in another variable's subgoal set.The containment condition is proved by constructing a third rewrite and showing that an assumed containment would make q weakly linear, contradicting finality.
- Hard cases: Responsibility-preserving reductions show that several rewrites cannot be final when they yield hard queries or preserve responsibility from a hard query.The arguments use variable and atom transformations, including reductions to h∗1 and h∗3, to exclude these forms from the final class.
E. OTHER RESPONSIBILITY PROOFS
The remaining responsibility results establish hardness through reductions from graph accessibility and vertex cover, and show that Why-No responsibility is tractable for fixed query size. The reductions connect graph reachability and max-flow structure to query responsibility.
- Hardness reductions: Responsibility hardness is established by reducing from Undirected Graph Accessibility, a LOGSPACE-complete problem.The construction creates one tuple per graph vertex and edge, with a distinguished tuple whose minimum contingencies correspond to vertex covers.
- Graph reductions: BGAP is hard for LOGSPACE because an undirected path from a to b exists exactly when the constructed bipartite graph contains a path from a to c.The bipartite graph uses vertices, edge-nodes, and a new node c connected to b.
- Max-flow reduction: FPMF distinguishes whether a path exists by changing the maximum flow from |E| to |E| + 1.The construction assigns capacity 2 to original bipartite edges, capacity 1 to incidence edges, and adds source- and target-connected nodes for a and b.
- Query reduction: The reduction from FPMF to query responsibility represents capacities with tuples in relations R, S, and T, together with distinguished tuples.Capacity-1 edges create one tuple, while capacity-2 edges create two tuples in the corresponding relation.
- Why-No responsibility: Why-No responsibility is tractable in data complexity because a counterfactual tuple requires inserting at most m −1 tuples, where m is the query's number of subgoals.The contingency size is bounded by the fixed query size.