REVIEW
Causal Explanations for Stratified Datalog
Databases · Submitted 21 Aug 2026 · 20 references
Pith's verdict: A real, well-proved advance in causality for stratified Datalog: Theorem 3 holds up, and the paper deserves a serious referee.
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
The causal content of any safe stratified Datalog program over a finite mutable domain is exactly captured by two families of prime implicants, one for the observed answer and one for the opposite answer.
The reading
What carries the argument
A prime implicant here is an inclusion-minimal term, a pair $(P,N)$ of disjoint mutable facts whose conjunction forces the program answer to a fixed value; the paper calls prime $1$-implicants prime truth conditions and prime $0$-implicants prime falsity conditions. The key mechanism is pairing a prime implicant of the observed outcome that contains the candidate's current literal with a prime implicant of the opposite outcome that contains the complementary literal, requiring the two terms to be compatible after flipping the candidate literal in the opposite term. The compatibility condition enforces the semantic requirement that the non-candidate changes alone preserve the observed outcome before the candidate is toggled, and the number of toggles needed to satisfy the merged term is the minimum contingency size. The paper constructs both prime families compositionally by stratified perfect-model evaluation and, for blocked recursive reachability, identifies them with path terms and mode-labelled edge-cut terms.
Extended reading notes
Core claim
The central result, Theorem 3, is a precise reduction of actual causality to Boolean implicants. Let $b$ be the observed answer at state $E$ and let $\ell_E(\tau)$ be the current truth value of a candidate mutable fact $\tau$. Then $\tau$ is an actual cause of outcome $b$ exactly when some prime $b$-implicant contains the literal $\ell_E(\tau)$. The minimum contingency size $\kappa_E(\tau)$ equals $K_E(\tau)$, the minimum, over all compatible pairs consisting of a prime $b$-implicant and a prime $(1-b)$-implicant that disagree only on $\tau$, of the number of non-candidate literals that the merged term requires changing from the observed state. Robustness is the same kind of minimum distance to any prime $(1-b)$-implicant. As direct consequences, the positive-Datalog minimal-support theory is recovered, blocked recursive reachability yields path–cut formulas and an exact responsibility formula, and for fixed nonrecursive stratified programs cause recognition, robustness, and responsibility are NP-complete while intervention-response equivalence is coNP-complete.
Load-bearing premise
The results depend on treating the answer as a Boolean function over a fixed finite set of mutable facts, with exogenous facts immutable and with actual cause defined by contingencies that first preserve the observed outcome; if that semantics is changed, the prime-pair characterization and the complexity bounds are not guaranteed.
Editorial extensions
If this is right
- For positive Datalog programs, the prime-implicant formula collapses to the minimal-support and transversal characterizations, so the new theory conservatively extends the known deletion-causality results.
- For blocked recursive reachability, a fact is a cause exactly when it lies on a potential path, minimum contingency has a simple formula $a(\pi)+c(K,\alpha)-1$ over path–cut pairs meeting only at the candidate edge, and robustness is a minimum edge cut or a shortest path depending on whether the answer is true or false.
- Two programs have identical intervention responses on every mutable state exactly when their prime truth families (equivalently, their prime falsity families) coincide.
- For fixed nonrecursive stratified programs, deciding whether a given absent fact is a cause, whether robustness is below a threshold, or whether responsibility is above a threshold is NP-complete, and deciding whether two fixed programs are intervention-equivalent is coNP-complete, all in data complexity.
- The prime families themselves can be exponential in the instance size even when the causal quantities—answer, cause status, and robustness—remain computable in polynomial time.
Reading between the lines
- The same compatible-prime-pair construction likely applies to any Boolean response function over a finite domain, not only stratified Datalog; the Datalog program is one way of generating the prime families, but the characterization itself is Boolean.
- The exponential size of the prime families suggests that practical implementations should avoid explicit enumeration and instead compute the minimum pair distance directly, perhaps through symbolic representations or specialized search.
- The path–cut formulas for blocked reachability hint that other recursive programs may admit graph-theoretic causal formulas, replacing prime-implicant enumeration with min-cut and shortest-path algorithms.
- One could test the characterization's boundaries by extending the semantics to multiple models or undefined values; under such changes the Boolean-function reduction must be re-examined.
Original abstract
Rule-based reasoning with exceptions requires causal explanations that account for both present and absent facts. For positive Datalog, monotonicity allows minimal supports to determine deletion causality. Stratified negation removes that property because inserting or deleting a fact may create or destroy an answer. We study actual causes, responsibility, and robustness for safe and stratified Datalog under perfect-model semantics and interventions over a finite set of mutable extensional facts. We prove that minimal supports and inclusion-minimal outcome-changing interventions do not determine causality, while robustness radius one may coexist with unbounded minimum contingencies. Our main result characterizes the minimum contingency size of a candidate fact by compatible prime implicants for the observed and opposite outcomes. The characterization conservatively recovers support-based causality for positive Datalog and yields path--cut characterizations for blocked recursive reachability. For fixed nonrecursive stratified programs, we establish data-complexity NP-completeness for cause recognition, robustness, and responsibility, and coNP-completeness for intervention-response equivalence between two such programs.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
Rule-based reasoning with exceptions requires causal explanations that account for both present and absent facts. For positive Datalog, monotonicity allows minimal supports to determine deletion causality. Stratified negation removes that property because inserting or deleting a fact may create or destroy an answer. We study actual causes, responsibility, and robustness for safe and stratified Datalog under perfect-model semantics and interventions over a finite set of mutable extensional facts. We prove that minimal supports and inclusion-minimal outcome-changing interventions do not determine causality, while robustness radius one may coexist with unbounded minimum contingencies. Our main result characterizes the minimum contingency size of a candidate fact by compatible prime implicants for the observed and opposite outcomes. The characterization conservatively recovers support-based causality for positive Datalog and yields path--cut characterizations for blocked recursive reachability. For fixed nonrecursive stratified programs, we establish data-complexity NP-completeness for cause recognition, robustness, and responsibility, and coNP-completeness for intervention-response equivalence between two such programs.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Rule-based reasoning with exceptions requires causal explanations that account for both present and absent facts. | background 0.99 | 0.06 | 0.02 | asserted 1.00 |
| s1 | For positive Datalog, monotonicity allows minimal supports to determine deletion causality. | background 1.00 | 0.10 | 0.02 | asserted 1.00 |
| s2 | Stratified negation removes that property because inserting or deleting a fact may create or destroy an answer. | background 0.91 | 0.09 | 0.02 | asserted 0.98 |
| s3 | We study actual causes, responsibility, and robustness for safe and stratified Datalog under perfect-model semantics and interventions over a finite set of mutable extensional facts. | contribution 0.99 | 0.84 | 0.06 | asserted 0.87 |
| s4 | We prove that minimal supports and inclusion-minimal outcome-changing interventions do not determine causality, while robustness radius one may coexist with unbounded minimum contingencies. | result 1.00 | 0.92 | 0.17 | asserted 0.98 |
| s5 | Our main result characterizes the minimum contingency size of a candidate fact by compatible prime implicants for the observed and opposite outcomes. | result 0.76 | 0.94 | 0.95 | asserted 1.00 |
| s6 | The characterization conservatively recovers support-based causality for positive Datalog and yields path--cut characterizations for blocked recursive reachability. | interpretation 0.73 | 0.91 | 0.10 | asserted 1.00 |
| s7 | For fixed nonrecursive stratified programs, we establish data-complexity NP-completeness for cause recognition, robustness, and responsibility, and coNP-completeness for intervention-response equivalence between two such programs. | result 0.97 | 0.95 | 0.08 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites · 3 sentences without a confident label
Cites as background 1 paper
-
Provenance games and graphs represent successful and failed rule applications under negation [ref] .
Efficiently Computing Provenance Graphs for Queries with Negation · Related Work · 0.95
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.