Pith. Sign in

REVIEW

Causal Resolution of Undefined Answers in Datalog with Negation

PaperPDF from arXiv

data files

ReviewThe objections and verdict, as JSON Paper breakdownThe authors' claims, conditions and measurements, as JSON Signed receiptProof this review has not been altered
X Bluesky LinkedIn Reddit Hacker News
Ratan Bahadur Thapa

Databases · Submitted 9 Nov 2026 · 44 references

Pith's verdict: Thorough extension of database causality to undefined answers under WFS, with clean characterizations and complexity bounds; the tractable algorithm is a nice bonus but limited by a strong structural condition.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on November 10, 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.

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

How Pith checks papers →

· 7 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv ID2611.11756 (version 1)
Pith ID2UM2LHXL, Pith's permanent record of this paper and its review
CitationRatan Bahadur Thapa. "Causal Resolution of Undefined Answers in Datalog with Negation." arXiv:2611.11756 (2026). https://pith.science/paper/2UM2LHXL
Cite this reviewBibTeX for Pith's review of this paper
Claim paper

Why Pith says this

Highlight any text to comment on it.

Referee report

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

The paper

The paper claims

Pairing win-loss certificates characterizes all minimum contingencies for Datalog queries with negation under the well-founded semantics.

The reading

This paper extends database causality to Boolean Datalog queries that may evaluate to undefined under the well-founded semantics due to unstratified negation. The authors ask which insertions or deletions of a designated fact can change the query answer to a prescribed new value, and what additional changes to other facts (a contingency) are needed to make the designated fact pivotal. For each of the six possible transitions among true, false, and undefined, they characterize all minimum contingencies by pairing a certificate for the observed answer with a certificate for the target answer. The characterization yields a concrete combinatorial formula for the minimum size. The authors also prove that deciding whether a contingency of bounded size exists is NP-complete for each transition, and that computing the minimum size is complete for a higher complexity class. For a restricted but nontrivial case where the supports of the prime implicants of undefinedness form a subtree hypergraph, they provide a polynomial-time algorithm.

What carries the argument

The key machinery is a game normal form that maps every intervention instance to a win–move game, preserving query values and Hamming distances between states. Central to the characterization are certificates: a triple (W+, W−, ρ) that certifies a win or loss at a position, and a pair (Z, R) that certifies a draw. Pairing a certificate for the observed state with a flipped certificate for the target state gives a term (a conjunction of literals on mutable moves) whose cost equals the minimum contingency size. The propagation theorem (Theorem 19) shows that when one update resolves a draw, the newly winning and losing vertices form a spanning in-arborescence rooted at the source of the update, with alternating membership.

Extended reading notes

Core claim

The paper establishes a complete characterization of minimum contingency sets for each of the six ordered transitions between truth values (true to false, true to undefined, false to true, false to undefined, undefined to true, undefined to false) in the context of Boolean Datalog queries with recursion through negation under the well-founded semantics. The characterization pairs a certificate for the observed answer with a certificate for the target answer, imposing consistent conditions on all other mutable facts. This yields a formula for the minimum size and a description of all minimizers. The paper also proves that whenever a single insertion or deletion resolves a draw at the query, the newly winning and losing positions are connected by a directed alternating tree rooted at the source of the changed move.

Load-bearing premise

The polynomial‑time algorithm (Theorem 24) requires that the support hypergraph of prime implicants for undefinedness is a subtree hypergraph—a strong structural condition whose verification is coNP‑complete (Proposition 51).

Editorial extensions

If this is right

  • Database causality for well-founded semantics now has a complete characterization for all six transitions among true, false, and undefined.
  • The complexity results (NP-complete decision, FPNP[log]-complete optimization, #P-hard counting) set fundamental limits for causal reasoning in recursive Datalog.
  • The polynomial-time algorithm for the subtree hypergraph case gives a tractable fragment for practical intervention design when the conditions hold.
  • The propagation theorem provides a structural explanation for how a single update resolves a draw, which may aid in debugging unexpected query answers.

Reading between the lines

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

  • The subtree hypergraph condition—only one determinate value reachable, prime implicants covering all undefined states, and supports forming connected subgraphs of a common tree—is quite restrictive; future work could identify syntactic database constraints (e.g., acyclic foreign keys) that guarantee this condition.
  • The game representation may extend to other non‑monotonic semantics beyond the well‑founded semantics, such as stable model semantics, though the draw region would differ.
  • The hardness already for the one‑rule win–move program suggests that practical causal tools for recursive Datalog will require heuristics or further domain restrictions, as even minimal recursive rules make these problems NP‑complete.
Original abstract

Unstratified negation may leave the answer to a Boolean Datalog query undefined under the well-founded semantics. We study database causality in this setting by asking which fact insertions and deletions realize a prescribed transition and which other changes preserve the observed query answer while making a designated fact pivotal. Such a set of changes to other facts is a contingency for the designated fact and the prescribed transition. Our game representation assigns one shared move to each mutable fact and preserves query values and intervention distances. Pairing source and target certificates characterizes all minimum contingencies for the six transitions among true, false, and undefined. When inserting or deleting a move resolves a draw, a directed tree traces the newly winning and losing positions along alternating paths to the source of that move. For the fixed one-rule win--move program, deciding whether a contingency of size at most $k$ exists is $\mathrm{NP}$-complete for each transition, even on bounded-degree graphs. Computing the minimum size is $\mathrm{FP}^{\mathrm{NP}[\log]}$-complete, and counting minimum contingencies is $\#\mathrm{P}$-hard under polynomial-time Turing reductions. When only one of true and false is reachable, the prime implicants of undefinedness satisfied at the observation cover every undefined state, and their supports induce nonempty subtrees of a common tree, we compute a minimum resolving intervention in polynomial time from the game instance. From the explicit tree and these implicants, we construct an equally large family of disjoint supports, certifying optimality.

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-11-10: 1 request, 7,673 input tokens.

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

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; .

Unstratified negation may leave the answer to a Boolean Datalog query undefined under the well-founded semantics. We study database causality in this setting by asking which fact insertions and deletions realize a prescribed transition and which other changes preserve the observed query answer while making a designated fact pivotal. Such a set of changes to other facts is a contingency for the designated fact and the prescribed transition. Our game representation assigns one shared move to each mutable fact and preserves query values and intervention distances. Pairing source and target certificates characterizes all minimum contingencies for the six transitions among true, false, and undefined. When inserting or deleting a move resolves a draw, a directed tree traces the newly winning and losing positions along alternating paths to the source of that move. For the fixed one-rule win--move program, deciding whether a contingency of size at most $k$ exists is $\mathrm{NP}$-complete for each transition, even on bounded-degree graphs. Computing the minimum size is $\mathrm{FP}^{\mathrm{NP}[\log]}$-complete, and counting minimum contingencies is $\#\mathrm{P}$-hard under polynomial-time Turing reductions. When only one of true and false is reachable, the prime implicants of undefinedness satisfied at the observation cover every undefined state, and their supports induce nonempty subtrees of a common tree, we compute a minimum resolving intervention in polynomial time from the game instance. From the explicit tree and these implicants, we construct an equally large family of disjoint supports, certifying optimality.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#sentencerolethe authors' own workstates the main conclusionstrength
s0 Unstratified negation may leave the answer to a Boolean Datalog query undefined under the well-founded semantics. background 1.00 0.05 0.03 hedged possibility 1.00
s1 We study database causality in this setting by asking which fact insertions and deletions realize a prescribed transition and which other changes preserve the observed query answer while making a designated fact pivotal. contribution 0.99 0.79 0.07 asserted 0.84
s2 Such a set of changes to other facts is a contingency for the designated fact and the prescribed transition. contribution 0.52 0.30 0.05 asserted 0.99
s3 Our game representation assigns one shared move to each mutable fact and preserves query values and intervention distances. method 0.97 0.92 0.07 asserted 1.00
s4 Pairing source and target certificates characterizes all minimum contingencies for the six transitions among true, false, and undefined. result 0.83 0.93 0.24 asserted 1.00
s5 When inserting or deleting a move resolves a draw, a directed tree traces the newly winning and losing positions along alternating paths to the source of that move. method 0.82 0.87 0.09 asserted 1.00
s6 For the fixed one-rule win--move program, deciding whether a contingency of size at most $k$ exists is $\mathrm{NP}$-complete for each transition, even on bounded-degree graphs. result 1.00 0.88 0.18 asserted 1.00
s7 Computing the minimum size is $\mathrm{FP}^{\mathrm{NP}[\log]}$-complete, and counting minimum contingencies is $\#\mathrm{P}$-hard under polynomial-time Turing reductions. result 1.00 0.86 0.17 asserted 1.00
s8 When only one of true and false is reachable, the prime implicants of undefinedness satisfied at the observation cover every undefined state, and their supports induce nonempty subtrees of a common tree, we compute a minimum resolving intervention in polynomial time from the game instance. result 0.81 0.92 0.21 asserted 1.00
s9 From the explicit tree and these implicants, we construct an equally large family of disjoint supports, certifying optimality. method 0.48 0.94 0.12 asserted 1.00

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

What was examined, and what was not

sources read
  • arXiv listing abstract v1
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

Figures
Figure 1. Let q = approve(a), τ = clearance(a), and E ′ = E ∪ {τ}. Approval is true in both cases before clearance is withdrawn. The diagrams show the values after withdrawal. An arrow P → Q denotes the rule Q ← ¬P after fixing the extensional facts in Example 6. Deleting the audit removes the rule cleared(a) ← ¬blocked(a). If ans(E) = u, then δ(E) = 1 + minτ∈U, c∈{⊤,⊥} κ u→c E (τ). A minimum contingency followed by the designated toggle reaches a determinate state. Conversely, removing any toggle from a smallest intervention yielding a determinate answer leaves the query undefined, giving a…
Figure 2. Two moves with the same condition τ. Both gates read pτ. If the dashed move to terminal z is present, Val(gi ) = Val(vi ) for i ∈ {1, 2}. If it is absent, both gates are winning. Compilation algorithm. Given I = (Π, Dx , U, E, q), we construct NF(I) = (ΠWin, Dg , U g , E g , Win(s)) as follows. 1. Construct the two total games for q on the auxiliary domain and take their disjoint union, with distinguished positions t and f . 2. Ground the move-defining rules over Ab I . For each ground head, take the disjunction of the conjunctions of body literals in the defining ground rule
Figure 3. In Example 2, inserting the dashed move s → ℓ resolves the drawn cycle. The bold edge a → s is the parent tree on S, rooted at s. The labels give the new outcomes and ranks. 5 Complexity We establish data complexity for a fixed program Π. The lower bounds hold for the one-rule program ΠWin of Example 2. In each construction, the query at a designated vertex v is Win(v). 5.1 Decision problems Let b, c ∈ B3 be distinct. Both decision problems take an instance I = (Π, Dx , U, E, q) of Definition 3 and a threshold k ∈ N. The program is fixed, the relations are listed explicitly, and k is
Figure 4. gives the construction for a graph with one edge x and endpoints 1, 2, so X = S1 = S2 = {x}. Deleting α1 makes s1 terminal and ex winning. While τ is present, e∗ is drawn, so q is drawn. Deleting τ now makes sj∗ terminal and e∗ winning. Both successors of q win, so q loses. If τ alone is deleted, ex remains drawn and q remains drawn. By symmetry, {α1} and {α2} are exactly the minimum contingencies for τ at q. p q ex e∗ s1 s2 sj∗ d1 d2 dj∗ α1 α2 τ Edge x = {1, 2} Added singleton {∗} C ex e∗ q p ∅ u → u u → ⊤ u → u u → u {1}, {2}, {1, 2} ⊤ → ⊤ u → ⊤ u → ⊥ u → ⊤
Figure 5. A minimum intervention on a path. Squares mark the deleted facts. The brackets mark two disjoint supports that certify optimality. Size of the explicit family. Take the arena with a conditional move from Section 5 on n ≥ 1 disjoint edges {ui , vi}, 1 ≤ i ≤ n. Let βw denote the mutable move indexed by endpoint w, and let E contain τ and all 2n such moves. The move from the root to the draw vertex is enabled precisely when τ ∈ F ∧
Figure 6. applies Lemma 49 to five supports B1, . . . , B5. Root the tree at r and let tj be the vertex of Bj nearest r. Let P record the chosen indices and X the chosen vertices. Initially t1 = c is the unique deepest such vertex. Removing the three supports containing c leaves B4 and B5, with t4 = b deeper than t5 = r. Thus X = {c, b} meets all five supports. The disjoint supports B1 and B4 require two distinct vertices in every transversal, so both witnesses are optimal. Choosing B3 first and deleting the supports containing t3 = r would leave B1 and B4 active even though B3 meets both. r…

Figures reproduced from arXiv:2611.11756 by the authors.

References

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.