{"id":"22012b25-3503-4f75-b8fa-b21aeee426d3","arxiv_id":"1908.07093","paper_version":9,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Uniform reliability (counting satisfying subsets) for self-join-free conjunctive queries is #P-complete for every non-hierarchical query and polynomial-time for every hierarchical query.","lead":"This paper proves that counting the number of database subsets satisfying a self-join-free conjunctive query is easy exactly when the query is hierarchical, and hard otherwise. It resolves an open question in probabilistic database theory where all facts were previously allowed deterministic probabilities, and it completes a long-sought dichotomy.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: Theorem 3.1 proof is sound; abstract overclaims a per-relation dichotomy that Section 7 leaves open.","rationale":"I read the full proof carefully. The reduction from independent-set counting to UR(Q_{r,s,t}) is a Cook reduction that constructs M instances D_p and solves an M-by-M Vandermonde system. The key factorization (Claim 5.1) depends on the local-match observation, which I verified by a case analysis of element types: original u (R only), original w (T only), fresh a in (*,w)-gadgets (R only), fresh b in gadgets (T only), and fresh c in 4-gadgets (R only). All S-facts go from an R-element to a T-element within the same gadget or to w, so no match can span two gadgets. The distinctness of Vandermonde nodes is established by a 2-adic valuation argument; the inequalities defining M1, M2, and M3 are chosen so that the four equations separate cleanly, and Lemma 6.3's polynomial identity (verified) ensures the final step. Proposition 3.3 is also sound: the rewritten instance forces the 'removed' facts to be present in every satisfying subinstance, giving a bijection of models. Corollary 7.2's probability renormalization is consistent. Thus I find no flaw in Theorem 3.1. The abstract overclaim about covering every relation-determined probability case is unsupported: Section 7 only proves hardness for Q1 in restricted regimes and conjectures the rest. This justifies the reader's CONDITIONAL verdict, but it is not a load-bearing concern for the main dichotomy.","tokens_in":25186,"tokens_out":34875,"duration_ms":300497,"concrete_test":"Brute-force check of Claim 5.1 for r=s=t=1 on a small bipartite graph: build D_p for p=0,1,2, enumerate all subinstances, and compare the number of violating worlds per (R',T') with the product formula; this verifies both the local-match observation and the gadget accounting. If the counts match, the load-bearing assumption of the equation system is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I find no load-bearing flaw in the proof of Theorem 3.1. The reader's flagged 'observe' in Section 4 (local-match property) is unproven but correct: in D_p, every element carrying all R_i-facts has S-facts only to T-elements in the same gadget or to original w, so any match uses facts of one gadget plus endpoint facts; hence Claim 5.1's product formula factorizes. The 2-adic valuation argument in Claim 6.1 correctly extracts i, j, d'+e, c+d, and c+d', and Lemma 6.3 (verified numerically for r=s=t=1) supplies the final distinctness. Proposition 3.3's many-one reduction is also sound: the 'fourth bullet' facts are mandatory in any satisfying world, giving a model bijection. The only concrete problem is the abstract's final sentence, which claims a full dichotomy for all relation-determined probabilities while Section 7 explicitly leaves this open and only gives partial results for Q1. This is a presentation overclaim, not a threat to the main theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":25406,"tokens_out":7682,"duration_ms":90323,"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":[{"comment":"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.","section":"Section 4"}],"minor_comments":[{"comment":"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":"Abstract"},{"comment":"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":"Section 4"},{"comment":"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.","section":"Section 6"}],"recommendation":"major_revision","confidential_remarks":"The main theorem appears sound, and the proof is detailed and careful. The one load-bearing gap is the unproved local-match observation in Section 4; I believe it is correct, but it should be proved in the revision. The abstract overclaims the Section 7 generalization; this should be corrected. I do not see any novelty or citation concerns: the related work, especially the Dalvi--Suciu dichotomy and the recent work of Kenig--Suciu, is properly discussed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main result is exactly what the title promises: for self-join-free conjunctive queries, uniform reliability (every tuple probability 1/2) is in PTIME exactly for hierarchical queries and #P-complete otherwise. This was genuinely open even for the simplest non-hierarchical query Q1, so the paper fills a real gap. The proof is substantial and, as far as I can tell, sound. The reduction from counting independent sets in bipartite graphs is worked out in detail, the Vandermonde system is handled carefully, and the 2-adic valuation argument plus Lemma 6.3 do give the needed distinctness. The appendices contain the full case analysis, including the somewhat tedious Lemma 6.3, which I checked in a small case and believe. The reduction from arbitrary non-hierarchical queries to the Q_{r,s,t} family (Proposition 3.3) is clean and correctly uses self-join-freeness. This is a real contribution, not an incremental one.\n\nSoft spots are minor but worth noting. The abstract's final sentence claims a generalization of the dichotomy to every restricted case where tuple probabilities are determined by the relation. Section 7 does not deliver that: it gives Corollary 7.2 for probabilities that are powers of 1/2, Theorem 7.5 for the case where S-facts are deterministic, and a conjecture for the rest. That is a presentation overclaim, not a technical flaw, but it should be fixed before publication. Also, the 'observe' in Section 4 that every match stays within a single gadget plus endpoint facts is load-bearing for Claim 5.1; it is true and easy to verify from the query shape, but it is stated without proof and a formal argument would make the paper easier to trust.\n\nThe citation pattern is healthy: the hardness relies on Provan and Ball, the tractability on Dalvi and Suciu, and the authors' own prior work is contextual rather than load-bearing. No circularity.\n\nWho is this for: anyone working on probabilistic databases, counting problems for conjunctive queries, or dichotomies for query evaluation. The paper deserves a serious referee and, modulo the abstract fix, acceptance. I would take it to a reading group and would likely cite it when discussing uniform reliability or counting subinstances of CQs.","headline":"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.","tokens_in":25906,"tokens_out":1570,"would_cite":true,"duration_ms":17812,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P15","68Q25","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"For self-join-free conjunctive queries, counting the subsets that satisfy the query is #P-complete precisely when the query is non-hierarchical.","keywords":["uniform reliability","conjunctive queries","hierarchical queries","self-join-free","probabilistic databases","#P-hardness","query reliability","counting problems"],"falsifier":"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.","tokens_in":25011,"feed_emoji":"🧮","tokens_out":11063,"duration_ms":88589,"temperature":0.7,"pith_summary":"The paper settles the complexity of uniform reliability for self-join-free conjunctive queries: the problem of counting how many subsets of the facts in a database make a fixed query true, equivalent to query reliability when every tuple has probability $1/2$. The main result is a dichotomy: this count is computable in polynomial time exactly when the query is hierarchical, and it is #P-complete for every non-hierarchical self-join-free conjunctive query. This was open even for the simplest non-hierarchical query $R(x), S(x,y), T(y)$. The paper also begins the study of the intermediate case where tuples of the same relation share a common probability, proving hardness for several regimes and conjecturing the full boundary.","feed_headline":"For non-hierarchical queries, counting matches is #P-complete","feed_subtitle":"The paper closes an open question and proves uniform reliability is tractable exactly for hierarchical queries.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the known reliability dichotomy that gives the tractable side for hierarchical queries and the characterization of unsafe queries used in the reduction to $Q_{r,s,t}$.","marker":"[5]"},{"why":"Supplies the #P-hard source problem of counting independent sets of a bipartite graph (equivalently, falsifying assignments of a monotone partitioned 2-DNF) that the reduction transforms into uniform reliability.","marker":"[20]"},{"why":"Establishes the reduction from tuple Shapley values to counting subinstances with a fixed number of tuples, letting the hardness result carry over to Shapley-value computation.","marker":"[16]"}],"fun_headline_variants":["Counting matches in CQs: #P-complete unless hierarchical","Hierarchical queries keep uniform reliability easy","No hierarchy? Counting matches is #P-complete","Uniform reliability tractability tied to hierarchy"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Counting matches in CQs: #P-complete unless hierarchical","Hierarchical queries keep uniform reliability easy","No hierarchy? Counting matches is #P-complete","Uniform reliability tractability tied to hierarchy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000547,"raw_usage":{"total_tokens":2593,"prompt_tokens":901,"completion_tokens":1692,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":517,"completion_tokens_details":{"reasoning_tokens":1633}},"tokens_in":517,"tokens_out":1692,"duration_ms":13513,"temperature":1.0,"reasoning_tokens":1633,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:26:30.884388+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Efficient query evaluation on probabilistic databases https://homes.cs.washington.edu/ suciu/vldbj-probdb.pdf","cited_arxiv_id":null,"evidence_quote":"Supplies the known reliability dichotomy that gives the tractable side for hierarchical queries and the characterization of unsafe queries used in the reduction to $Q_{r,s,t}$."},{"cited_title":"Quantifying Causal Effects on Query Answering in Databases","cited_arxiv_id":"1603.02705","evidence_quote":"Supplies the #P-hard source problem of counting independent sets of a bipartite graph (equivalently, falsifying assignments of a monotone partitioned 2-DNF) that the reduction transforms into uniform reliability."},{"cited_title":"Counting database repairs that satisfy conjunctive queries with self-joins http://www.openproceedings.org/ICDT/2014/paper_17.pdf","cited_arxiv_id":null,"evidence_quote":"Establishes the reduction from tuple Shapley values to counting subinstances with a fixed number of tuples, letting the hardness result carry over to Shapley-value computation."}],"review_version":1}