REVIEW 1 major objections 3 minor 22 references
Uniform Reliability of Self-Join-Free Conjunctive Queries
T0 review · 1 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read For self-join-free conjunctive queries, counting the subsets that satisfy the query is #P-complete precisely when the query is non-hierarchical.
desk verdict Strong paper that settles the uniform-reliability dichotomy for self-join-free CQs; the only real problem is an overstated abstract claim about the per-relation generalization. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The carrying object is the family $Q_{r,s,t}$ of two-variable queries of the form $R_1(x),\ldots,R_r(x), S_1(x,y),\ldots,S_s(x,y), T_1(y),\ldots,T_t(y)$, the simplest non-hierarchical shape. The reduction constructs instances from a bipartite graph using two gadgets: an $(a,b)$-gadget containing all $R$-facts on $a$, $S$-facts on $(a,b)$, and $T$-facts on $b$, and an $(a,b,c,d)$-gadget that concatenates two such gadgets. The counts of violating subinstances in these gadgets define constants $\gamma$, $\delta_R$, $\delta_T$, and $\delta_\perp$, and the number $N_p$ of violating subinstances of the $p$-th instance is shown to equal a sum of $Y$-variables times powers of a coefficient $\alpha$. This yields a Vandermonde system $\vec{N}=A\vec{Y}$, and the proof that $A$ is invertible uses the parity of the gadget counts (the exponent of $2$ in their prime factorization) plus the inequality $\delta_R \times \delta_T \neq \gamma \times \delta_\perp$. The construction transfers the #P-hard problem of counting independent sets of a bipartite graph to the oracle for uniform reliability.
What would settle it
For the smallest non-hierarchical query $Q_1$ with $r=s=t=1$, build the instance $D_p$ from a small bipartite graph, compute the number of violating subinstances by brute force for several $p$, and check whether the values satisfy the claimed Vandermonde equation; a single match that spans two gadgets would invalidate the equation system.
Extended reading notes
Core claim
The central claim, Theorem 3.1, is that for conjunctive queries without self-joins, uniform reliability is solvable in polynomial time for hierarchical queries and is #P-complete for all non-hierarchical queries. Hierarchical means that for any two variables, the sets of query atoms mentioning them are either disjoint or one contains the other. The tractable side follows from the known reliability dichotomy; the contribution is the hardness side, proved by reducing from counting independent sets in bipartite graphs. The proof works for every non-hierarchical query by first reducing to a representative family $Q_{r,s,t}$ of two-variable queries, then building a system of linear equations whose coefficients form an invertible Vandermonde matrix, so that the number of independent sets can be recovered from a polynomial number of oracle calls.
Load-bearing premise
The proof that every match of the query in the constructed instances is confined to a single gadget plus the endpoint facts is stated without a full formal proof, and this local-match property is the load-bearing premise for the product formula that yields the Vandermonde system.
Editorial extensions
If this is right
- Uniform reliability is #P-complete for every non-hierarchical self-join-free conjunctive query, so the uniform case is no easier than the general reliability problem.
- For every non-hierarchical self-join-free CQ, computing the Shapley value of a tuple is also intractable, because that computation reduces to counting subinstances with a prescribed number of tuples, a generalization covered by the same dichotomy.
- For the query $R(x), S(x,y), T(y)$, reliability with relation-wise probabilities is #P-hard when the probabilities of $R$, $S$, and $T$ are $2^{-r}$, $2^{-s}$, and $2^{-t}$ for positive integers $r,s,t$, and also when $S$ has probability $1$ while $R$ and $T$ have any probabilities strictly between $0$ and $1$.
- For relation-wise probabilities, the only easy cases identified for $Q_1$ are those where one end relation is deterministic; the paper conjectures that these are the only easy cases.
Reading between the lines
- If the paper's conjecture holds, the relation-wise probability problem for $Q_1$ would have a clean boundary: hard whenever both end relations are probabilistic, and easy only when one end is deterministic.
- The Vandermonde-gadget technique may extend beyond self-join-free CQs; a testable first step is whether the same construction yields hardness for uniform reliability of unions of conjunctive queries or of queries with repeated relation symbols.
- Because the hardness proof uses only the uniform distribution, it suggests that deterministic facts are not what makes probabilistic query evaluation hard, and that any future tractability for a non-hierarchical query in the uniform setting would need a structural restriction beyond the query's shape.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies uniform reliability UR(Q) for self-join-free conjunctive queries: counting the subsets of facts of an input database that satisfy Q, equivalently probabilistic query evaluation when every fact has probability 1/2. The main result, Theorem 3.1, states a dichotomy: UR(Q) is polynomial-time computable for hierarchical queries and #P-complete for all non-hierarchical queries. The tractability direction follows from the Dalvi--Suciu dichotomy, and the hardness direction is proved by reducing from counting independent sets in bipartite graphs. The reduction focuses on the family Q_{r,s,t} of two-variable queries (Section 3), builds gadget-based instances D_p (Section 4), derives a linear equation system relating the oracle answers N_p to combinatorial variables Y_{i,j,c,d,d'} (Section 5), and proves that the resulting Vandermonde matrix is invertible by showing all coefficients are distinct via 2-adic valuations and a non-equality of gadget counts (Section 6). Section 7 gives partial results for the more general problem where probabilities are uniform per relation but may differ across relations, including a full solution for Q1 in the case s=1 and a conjecture for the remaining cases.
Significance. If the proof is correct, the paper settles a natural open problem that had resisted solution even for the simplest non-hierarchical query Q1. The result is significant because it shows that the hierarchical/non-hierarchical boundary, known for probabilistic query evaluation with arbitrary or one-sided probabilities, also governs unweighted counting of satisfying subinstances. The proof is self-contained and technically substantial: it constructs explicit gadgets, reduces from #P-hard bipartite independent-set counting, sets up a linear system with an explicit Vandermonde matrix, and proves invertibility using elementary number-theoretic arguments. The paper also honestly discusses the limitations of the generalization in Section 7. These are clear strengths. I did not find circularity; the hardness proof reduces from Provan--Ball and the tractability side from Dalvi--Suciu, neither of which depends on the paper's own results.
major comments (1)
- [Section 4] The paragraph beginning "Observe that the construction of D_p is designed to ensure that any match..." states a structural property that is load-bearing for the entire proof, but no proof of this property is given. Claim 5.1's product formula for the number of violating subinstances in D_p(R',T') depends on the assertion that every satisfying match is contained in the facts of a single gadget plus the endpoint facts on elements of R and T. Without a formal justification, the factorization underpinning the linear system is not fully established. The observation is believable and can likely be proved by arguing that a match of Q_{r,s,t} chooses one element for x and one for y, and that all S-facts in D_p connect either two elements within the same four-element gadget or one element of a gadget to its adjacent interior element, so that any match cannot combine facts from two distinct edge gadgets unless they share an endpoint. I request that this argument be written out, either in Section 4 or in Appendix B immediately before Claim 5.1.
minor comments (3)
- [Abstract] The final sentence of the abstract states that the paper establishes "a generalization of the dichotomy that covers every restricted case of reliability in which the probabilities of tuples are determined by their relation." This overstates the content of Section 7, which explicitly says that the general question is not completely answered and proves only partial results for Q1, leaving Conjecture 7.4 open. The abstract should be weakened to describe the Section 7 results as preliminary or partial.
- [Section 4] The notation for the (a,*,*,w)-gadget and the (u,*)-gadget is understandable from context, but a short formal definition of "using fresh elements for b and c, as denoted by the *'s" would improve precision, especially since the subsequent accounting in Claim 5.1 counts these gadgets by type.
- [Section 6] In the paragraph following Lemma 6.2, the text says "by Lemma 6.3, we have gamma * delta_perp != delta_R * delta_T". This is correct, but Lemma 6.3 is proved in Appendix C with a case distinction and a polynomial identity. For readability, the main text should refer explicitly to the appendix proof and state that the difference is exactly (2s)^3(2r-1)(2t-1), so a reader can verify the non-vanishing without reconstructing Table 1.
Circularity Check
No significant circularity: the main dichotomy proof reduces from external #P-hard problems and Dalvi–Suciu, and the self-citations are motivational only.
full rationale
The paper's central claim, Theorem 3.1, is not circular. The tractability direction is imported from the external Dalvi–Suciu dichotomy [5], not from the authors' own results, and the uniform-to-weighted conversion is a direct identity. The hardness direction is a genuine gadget reduction from counting independent sets in bipartite graphs, which is #P-hard by the external Provan–Ball result [20]. The derived linear system connects oracle values N_p to graph parameters, and invertibility is established by explicit 2-adic valuation arguments and Lemma 6.3, whose proof computes an explicit nonzero difference. Proposition 3.3 reduces UR(Q_{r,s,t}) to UR(Q) via a bijection on models, again independently argued. The self-citations, such as [16] on Shapley values, appear only in motivation and related work and are not load-bearing in the proof. The unproved 'observe' about local matches in Section 4 is a gap in exposition, not circularity: it is a factual property of the constructed gadgets and is directly checkable. Finally, the abstract's final sentence overclaims a full per-relation dichotomy that Section 7 explicitly leaves open, but that is a presentation issue and not a circular derivation. Overall, the derivation is self-contained against external benchmarks and no step reduces to its own inputs.
Assumptions & free parameters
assumptions (4)
- standard math Counting independent sets in a bipartite graph is #P-hard, equivalently counting satisfying assignments of monotone partitioned 2-DNF formulas is #P-hard.
- domain assumption Dalvi and Suciu dichotomy: PQE(Q) is PTIME for hierarchical self-join-free CQs and #P-hard otherwise.
- standard math Standard properties of Vandermonde matrices, including invertibility when nodes are distinct, and the Kronecker product of invertible matrices is invertible.
- standard math The polynomial identity X^3 + 3X(X-1)^2 - 3X^2(X-1) - (X-1)^3 = 1.
Cite this review
Pith. "Pith review of Uniform Reliability of Self-Join-Free Conjunctive Queries." pith.science (2026). https://pith.science/paper/R4TPZFUO
@misc{pith2026190807093,
author = {Pith},
title = {Pith review of: Uniform Reliability of Self-Join-Free Conjunctive Queries},
year = {2026},
howpublished = {\url{https://pith.science/paper/R4TPZFUO}},
note = {Machine review of arXiv:1908.07093}
}
read the original abstract
The reliability of a Boolean Conjunctive Query (CQ) over a tuple-independent probabilistic database is the probability that the CQ is satisfied when the tuples of the database are sampled one by one, independently, with their associated probability. For queries without self-joins (repeated relation symbols), the data complexity of this problem is fully characterized by a known dichotomy: reliability can be computed in polynomial time for hierarchical queries, and is #P-hard for non-hierarchical queries. Inspired by this dichotomy, we investigate a fundamental counting problem for CQs without self-joins: how many sets of facts from the input database satisfy the query? This is equivalent to the uniform case of the query reliability problem, where the probability of every tuple is required to be 1/2. Of course, for hierarchical queries, uniform reliability is solvable in polynomial time, like the reliability problem. We show that being hierarchical is also necessary for this tractability (under conventional complexity assumptions). In fact, we establish a generalization of the dichotomy that covers every restricted case of reliability in which the probabilities of tuples are determined by their relation.
Reference graph
Works this paper leans on
-
[1]
Symmetric Weighted First-Order Model Counting
Paul Beame, Guy Van den Broeck, Eric Gribkoff, and Dan Suciu. Symmetric weighted first-order model counting https://arxiv.org/abs/1412.1505. In PODS , pages 313--328. ACM, 2015
work page Pith review arXiv 2015
-
[2]
Answering Conjunctive Queries under Updates
Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering conjunctive queries under updates https://arxiv.org/abs/1702.06370. In PODS , pages 303--318. ACM , 2017
work page Pith review arXiv 2017
-
[3]
Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem https://www.cs.sfu.ca/ abulatov/papers/counting-acm.pdf. J. ACM , 60(5):34:1--34:41, 2013
work page 2013
-
[4]
From weighted to unweighted model counting https://www.ijcai.org/Proceedings/15/Papers/103.pdf
Supratik Chakraborty, Dror Fried, Kuldeep S Meel, and Moshe Y Vardi. From weighted to unweighted model counting https://www.ijcai.org/Proceedings/15/Papers/103.pdf. In IJCAI , 2015
work page 2015
-
[5]
Nilesh Dalvi and Dan Suciu. Efficient query evaluation on probabilistic databases https://homes.cs.washington.edu/ suciu/vldbj-probdb.pdf. VLDB Journal , 16(4):523--544, 2007
work page 2007
-
[6]
Nilesh Dalvi and Dan Suciu. The dichotomy of probabilistic inference for unions of conjunctive queries https://homes.cs.washington.edu/ suciu/jacm-dichotomy.pdf. J.\ ACM , 59(6), 2012
work page 2012
-
[7]
Dalvi, Christopher R \' e , and Dan Suciu
Nilesh N. Dalvi, Christopher R \' e , and Dan Suciu. https://homes.cs.washington.edu/ suciu/file15_cacm-paper.pdf Probabilistic databases: D iamonds in the dirt . Commun. ACM , 52(7):86--94, 2009
work page 2009
-
[8]
Pradeep Dubey and Lloyd S. Shapley. Mathematical properties of the B anzhaf power index. Mathematics of Operations Research , 4(2):99--131, 1979
work page 1979
Show all 22 references
-
[9]
Erich Gr \" a del, Yuri Gurevich, and Colin Hirsch. The complexity of query reliability https://www.researchgate.net/profile/Yuri_Gurevich2/publication/2900852_The_Complexity_of_Query_Reliability/links/0c96053321102376cd000000/The-Complexity-of-Query-Reliability.pdf. In PODS ,...
1998
-
[10]
http://www.vldb.org/pvldb/vol9/p552-gribkoff.pdf Slim S hot: I n-database probabilistic inference for knowledge bases
Eric Gribkoff and Dan Suciu. http://www.vldb.org/pvldb/vol9/p552-gribkoff.pdf Slim S hot: I n-database probabilistic inference for knowledge bases . PVLDB , 9(7):552--563, 2016
2016
-
[11]
Grofman and H
B. Grofman and H. Scarrow. Iannucci and Its Aftermath: The Application of the Banzhaf Index to Weighted Voting in the State of New York , pages 168--183. Physica-Verlag HD, Heidelberg, 1979
1979
-
[12]
On the history of the K ronecker product
Harold V Henderson, Friedrich Pukelsheim, and Shayle R Searle. On the history of the K ronecker product. Linear and Multilinear Algebra , 14(2):113--120, 1983
1983
-
[13]
http://vldb.org/pvldb/vol5/p1160_abhayjha_vldb2012.pdf Probabilistic databases with MarkoViews
Abhay Kumar Jha and Dan Suciu. http://vldb.org/pvldb/vol5/p1160_abhayjha_vldb2012.pdf Probabilistic databases with MarkoViews . PVLDB , 5(11):1160--1171, 2012
2012
-
[14]
Bertossi, Benny Kimelfeld, and Moshe Sebag
Ester Livshits, Leopoldo E. Bertossi, Benny Kimelfeld, and Moshe Sebag. The S hapley value of tuples in query answering. CoRR , abs/1904.08679, 2019. URL: http://arxiv.org/abs/1904.08679, http://arxiv.org/abs/1904.08679 arXiv:1904.08679
1904 arXiv
-
[15]
A dichotomy in the complexity of counting database repairs https://www.sciencedirect.com/science/article/pii/S0022000013000214
Dany Maslowski and Jef Wijsen. A dichotomy in the complexity of counting database repairs https://www.sciencedirect.com/science/article/pii/S0022000013000214. J. Comput. Syst. Sci. , 79(6):958--983, 2013
2013
-
[16]
Counting database repairs that satisfy conjunctive queries with self-joins http://www.openproceedings.org/ICDT/2014/paper_17.pdf
Dany Maslowski and Jef Wijsen. Counting database repairs that satisfy conjunctive queries with self-joins http://www.openproceedings.org/ICDT/2014/paper_17.pdf. In ICDT , pages 155--164. OpenProceedings.org, 2014
2014
-
[17]
https://www.cs.ox.ac.uk/people/dan.olteanu/papers/oh-sum08.pdf Using OBDD s for efficient query evaluation on probabilistic databases
Dan Olteanu and Jiewen Huang. https://www.cs.ox.ac.uk/people/dan.olteanu/papers/oh-sum08.pdf Using OBDD s for efficient query evaluation on probabilistic databases . In SUM , volume 5291 of Lecture Notes in Computer Science , pages 326--340. Springer, 2008
2008
-
[18]
Scott Provan and Michael O
J. Scott Provan and Michael O. Ball. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM Journal on Computing , 12(4), 1983
1983
-
[19]
The Shapley value: E ssays in honor of Lloyd S
Alvin E Roth. The Shapley value: E ssays in honor of Lloyd S. Shapley . Cambridge University Press, 1988
1988
-
[20]
Bertossi, Dan Suciu, and Guy Van den Broeck
Babak Salimi, Leopoldo E. Bertossi, Dan Suciu, and Guy Van den Broeck. Quantifying causal effects on query answering in databases https://arxiv.org/abs/1603.02705. In TAPP , 2016
2016 arXiv
-
[21]
L.S. Shapley. Stochastic games https://www.pnas.org/content/39/10/1095. Proceedings of the National Academy of Sciences of the United States of America , 39:1095--1100, 1953
1953
-
[22]
Probabilistic Databases
Dan Suciu, Dan Olteanu, Christopher R \' e , and Christoph Koch. Probabilistic Databases . Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011
2011
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.