Causality and Minimal Supports in Recursive Datalog

Ratan Bahadur Thapa; Steffen Staab

REVIEW

Causality and Minimal Supports in Recursive Datalog

Ratan Bahadur Thapa, Steffen Staab

Databases · Submitted 17 Jul 2026

Pith's verdict: A clean, correct theory paper: the support-hypergraph framing is the right object for deletion-based explanation in positive Datalog, and the reachability/min-cut result is the genuinely nice part; the novelty is modest but the proofs are honest and the scope is well disclosed.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 1, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2607.16443 (version 2)

Pith IDMO5YZPQL, Pith's permanent record of this paper and its review

CitationRatan Bahadur Thapa, Steffen Staab. "Causality and Minimal Supports in Recursive Datalog." arXiv:2607.16443 (2026). https://pith.science/paper/MO5YZPQL

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Quick take: this is a solid, honest theory paper. The central claim—that the support hypergraph determines actual causes, counterfactual causes, responsibility, and deletion robustness for positive Datalog—is proven cleanly, and the reachability result (minimal supports = simple s-t paths, robustness = minimum directed edge cut) is the genuinely nice part. The reader's ACCEPT verdict is right; I'd support sending this to a serious referee.

What is actually new: the support-hypergraph framing for recursive Datalog, the separation between fixed UCQs (bounded supports, polynomially many) and transitive closure (linear-size supports, exponentially many), and the fixed-goal invariance theorem. The invariance theorem is almost definitional—two programs equivalent for the goal have identical support families by definition of equivalence—but the consequence, that proof-tree shape doesn't matter for deletion-based explanation, is worth stating explicitly. The path/cut identity (Theorem 4) is a clean formalization of something people probably suspected, and it is the real contribution.

Soft spots, in proportion. First, the novelty is modest if you view the framework through monotone Boolean functions. Proposition 1 is essentially the standard fact that in a monotone Boolean function a set satisfies the function iff it contains a minimal true set. The paper doesn't cite the minimal-diagnosis/abduction literature; that's a gap, but not a damaging one. Second, the NP-hardness result is a standard vertex-cover reduction, and the paper honestly calls it a calibration. Fine. Third, the abstract slightly overstates the reachability result: it says deletion robustness is the minimum directed edge cut without noting the all-endogenous, distinct-endpoints condition. The body states it correctly; this is a minor abstract-level omission. Fourth, scope is explicitly limited to positive programs and Meliou-style deletion semantics, with negation deferred. That is honest disclosure, not a flaw.

Do I have any substantive objection? No. The proofs check out. The active-domain finiteness premise is stated and used correctly. The path/cut arguments are exact. The paper does not claim Datalog causality itself as new, and it is careful about what it does and doesn't prove.

Who this is for: people working on Datalog provenance, explanation, or causality in databases. It's a theory paper; there are no experiments to judge. I would cite it if I worked on recursive-query explanation, and I would bring it to a reading group as a clean example of monotone-support reasoning.

Recommendation: engage with it. Send it to peer review. The work is correct, well-scoped, and the reachability result is likely to be useful beyond this paper.

Referee report

Significance

The support hypergraph is a clean semantic abstraction: it is exactly the deletion-relevant object under the Meliou-style causality semantics adopted. The proofs are complete and checkable; Proposition 1 is a sound monotonicity argument, and the contingency/transversal bookkeeping in Theorem 2 and Proposition 2 works out. The paper's strongest contribution is the crisp separation between UCQ and recursive Datalog at the support level, together with the reachability identity (minimal supports = s-t paths, robustness = edge cut), which yields a polynomial-time robustness computation in a setting with exponentially many supports. The scope is stated honestly: all results are for positive Datalog and for deletion-only causality. The counterexample separating proof-tree multiplicity from support structure is instructive, and the invariance theorem (Theorem 3) is a useful semantic sanity check. I found no internal gaps.

Minor objections (3)

[Section 5 / Example 3] The observation that left- and right-recursive transitive closures have identical minimal supports for a fixed goal is a direct instance of Theorem 3. Consider adding a cross-reference there so the example explicitly points to the general invariance result.
[Proof of Corollary 2 / References] The max-flow/min-cut citation in the proof of Corollary 2 is [11,2]; reference [2] is about inverse network flow problems rather than a standard max-flow algorithm. A textbook or the original Ford-Fulkerson reference would be a more precise citation for the polynomial-time claim.
[Proposition 2] The nested minimum in the contingency-size formula is correct, but the well-definedness of the inner minimum (it is nonempty whenever S^+_τ is nonempty) is tacit. A one-sentence remark would make the formula easier to verify on first reading.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

The authors prove that for positive Datalog, the support hypergraph — the family of inclusion-minimal input fact sets that entail an answer — completely determines actual causes, counterfactual causes, responsibility, and deletion robustnes

The reading

The paper sets out to show that for positive Datalog programs, the entire deletion-based explanatory content of a derived answer is carried by one abstract object: the family of inclusion-minimal sets of deletable input facts that still entail the answer, organized as a hypergraph. It proves that this support hypergraph determines exactly which facts are actual causes, which are counterfactual causes, what each fact's responsibility is, and how many deletions are needed to make the answer disappear. It then shows that recursion changes the picture qualitatively: fixed nonrecursive conjunctive queries have bounded, polynomially many minimal supports, while a single recursive transitive-closure program can have supports of unbounded size and exponentially many of them. For all-endogenous reachability, the robustness answer is clean: minimal supports are exactly simple directed paths, and deletion robustness is exactly the minimum directed edge cut. If the results hold, explanation in recursive rule systems reduces to understanding a hypergraph, decoupled from proof trees and derivation multiplicity.

What carries the argument

The central object is the support hypergraph H_{Π,D,A}=(D_n, S_{Π,D,A}): its vertices are the endogenous (deletable) input facts, and each hyperedge is an inclusion-minimal set of such facts that, together with the exogenous background facts, entails the answer atom A under the program Π. Its work is to absorb all deletion-relevant information: Proposition 1 shows entailment after any retention E is equivalent to E containing some hyperedge, and Theorem 2 shows causes and robustness are membership and hitting properties of the hypergraph. For reachability, the hypergraph becomes the family of simple s-t paths, and the transversal problem becomes a directed edge cut.

Extended reading notes

Core claim

For any positive Datalog program and any partitioned database, the paper claims that the support hypergraph—vertices are the deletable input facts, hyperedges are the inclusion-minimal sets of those facts that entail the target atom together with the fixed background facts—is a complete invariant for deletion-based explanation. Theorem 2 proves that a fact is an actual cause iff it appears in at least one minimal support, a counterfactual cause iff it appears in every minimal support, and that the deletion robustness radius equals the minimum number of facts needed to hit every support (the transversal number). Proposition 2 gives the exact contingency-size formula for responsibility from th

Load-bearing premise

The entire chain rests on monotonicity and finiteness of positive Datalog entailment: only because a retained set either contains a minimal support or not (Proposition 1) do the hypergraph characterizations follow; if negation or non-finite active domains are introduced, the support family need not be upward-closed and the correspondences can break.

Editorial extensions

If this is right

For any positive Datalog answer, an explanation system only needs to compute or approximate minimal supports; actual causes, counterfactual causes, responsibility, and deletion robustness then follow without inspecting derivation trees.
Fixed-goal equivalent Datalog programs (e.g., left- vs right-recursive transitive closure) give the same answers and the same explanations, so explanation is a property of the query's semantics, not its rule syntax.
Reachability explanations are tractable despite exponentially many minimal supports: the minimum number of edge deletions that breaks Path(s,t) is computable in polynomial time as a directed edge cut, without enumerating paths.
Fixed union-of-conjunctive-query explanations have bounded size and polynomially many minimal supports, while a single recursive rule can force unbounded support size and exponential support count; this is a sharp separation in explanation complexity.
The deletion-robustness threshold problem is NP-hard even for a fixed positive nonrecursive one-rule program, so no general polynomial algorithm exists for that decision problem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The support-hypergraph reduction likely transfers to any monotone query language with a finite active domain—for example recursive SQL common table expressions—since the proof only needs upward-closed support families and a least fixpoint; the paper states the result for positive Datalog, but the mechanism is more general.
The path/cut equivalence suggests a broader program: for a given recursive query, look for a min-cut/max-flow or separation dual whose polynomial-time computability could make robustness tractable even when the support hypergraph is exponentially large; reachability shows the pattern exists, though not every query will have one.
The divergence between infinite proof trees and a single minimal support implies that provenance systems built on derivation counting may be exponentially more verbose than necessary for deletion-based questions; a testable extension is to compare how often support hypergraphs are drastically smaller than proof-tree and circuit provenance on recursive-rule workloads.
The empty-support convention (an answer entailed by exogenous facts alone has infinite robustness) is natural but makes robustness a two-valued cliff; an extension to weighted deletions or to robustness excluding exogenous entailment might give finer-grained explanations for mixed endogenous/exogenous databases.

Original abstract

Explaining an inferred fact under rule evaluation can require identifying the inclusion-minimal input sets that suffice for the inference and the deletions that make the fact disappear. For a fixed union of conjunctive queries, every minimal support is bounded by the query body. For recursive rules, the same answer may depend on large supports, and the number of minimal supports may be exponential in the input. We study the gap through deletion-based explanation, using inclusion-minimal endogenous input facts that entail the atom together with fixed background facts. We organize these supports as a hypergraph and prove that it determines actual causes, counterfactual causes, responsibility, and deletion robustness. The resulting view separates nonrecursive queries from recursive Datalog at the level of minimal input explanations. For positive-length reachability, minimal supports are exactly simple directed paths, and deletion robustness is the minimum directed edge cut. We also prove invariance under fixed-goal equivalent positive Datalog programs and an NP-hardness calibration for the robustness threshold problem.

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.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 6,185 input tokens.

What the abstract itself states, as probabilities: claims first 0.05 · states limitation 0.61 · human participants 0.01 · controlled comparison 0.03 · randomized assignment 0.01 · states quantitative result 0.83 · compares with prior results 0.50 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v2. Results and the main claim are underlined; show every role.

Explaining an inferred fact under rule evaluation can require identifying the inclusion-minimal input sets that suffice for the inference and the deletions that make the fact disappear. For a fixed union of conjunctive queries, every minimal support is bounded by the query body. For recursive rules, the same answer may depend on large supports, and the number of minimal supports may be exponential in the input. We study the gap through deletion-based explanation, using inclusion-minimal endogenous input facts that entail the atom together with fixed background facts. We organize these supports as a hypergraph and prove that it determines actual causes, counterfactual causes, responsibility, and deletion robustness. The resulting view separates nonrecursive queries from recursive Datalog at the level of minimal input explanations. For positive-length reachability, minimal supports are exactly simple directed paths, and deletion robustness is the minimum directed edge cut. We also prove invariance under fixed-goal equivalent positive Datalog programs and an NP-hardness calibration for the robustness threshold problem.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	Explaining an inferred fact under rule evaluation can require identifying the inclusion-minimal input sets that suffice for the inference and the deletions that make the fact disappear.	background 1.00	0.10	0.06	hedged possibility 0.69
s1	For a fixed union of conjunctive queries, every minimal support is bounded by the query body.	background 0.75	0.44	0.07	asserted 1.00
s2	For recursive rules, the same answer may depend on large supports, and the number of minimal supports may be exponential in the input.	gap 0.52	0.36	0.14	asserted 0.51
s3	We study the gap through deletion-based explanation, using inclusion-minimal endogenous input facts that entail the atom together with fixed background facts.	contribution 0.67	0.89	0.11	asserted 0.95
s4	We organize these supports as a hypergraph and prove that it determines actual causes, counterfactual causes, responsibility, and deletion robustness.	result 0.46	0.94	0.32	asserted 1.00
s5	The resulting view separates nonrecursive queries from recursive Datalog at the level of minimal input explanations.	interpretation 0.61	0.83	0.41	asserted 1.00
s6	For positive-length reachability, minimal supports are exactly simple directed paths, and deletion robustness is the minimum directed edge cut.	result 1.00	0.81	0.12	asserted 1.00
s7	We also prove invariance under fixed-goal equivalent positive Datalog programs and an NP-hardness calibration for the robustness threshold problem.	result 0.86	0.94	0.11	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 0.99 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v2

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Causal Resolution of Undefined Answers in Datalog with Negation
cs.DB 2026-11 accept novelty 7.0 of 10

The paper gives a complete complexity classification for contingency-based causality in Datalog with negation under the well-founded semantics, covering all six transitions among true, false, and undefined.
Minimum-Cost Robust Evidence Certificates for Horn Reasoning under Correlated Source Failures
cs.AI 2026-10 accept novelty 7.0 of 10

A minimum-cost robust evidence certificate for Horn reasoning under correlated source failures can be synthesized using a counterinterpretation-guided hitting-set algorithm.

How the literature uses it

1 arXiv paper cite this in 3 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

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.