Pith. sign in

REVIEW 2 major objections 5 minor 39 references

Rewriting Consistent Answers on Annotated Data

T0 review · 2 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Consistent answers on annotated semiring databases are rewritable in a first-order-like logic exactly when the query's attack graph is acyclic.

desk verdict Genuinely new framework for consistent answers over semirings, but the main rewritability theorem rests on a lemma whose proof is only sketched—worth serious review, not yet fully verifiable. read the letter →

arxiv 2412.11661 v2 pith:7NKJX56X submitted 2024-12-16 cs.DB cs.LO

Phokion G. Kolaitis , Nina Pardal , Jonni Virtema , Jef Wijsen This is my paper · ORCID
classification cs.DBcs.LO MSC 68P1503B7068Q19
keywords consistentqueryansweringrepairssemiringsconjunctivequerieskeyconstraintsfirst-orderrewritabilityattackgraphapproximationhardness
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Over databases whose tuples carry values from a naturally ordered positive semiring, this paper defines the consistent answer to a query as the minimum, over all repairs of the inconsistent database, of the semiring value the query returns. The central result is an equivalence: for self-join free conjunctive queries with one key constraint per relation, these semiring-consistent answers can be evaluated by a single formula of a new logic LK — a first-order-like logic with a guarded minimization operator and a flattening negation — if and only if the query's attack graph is acyclic. This generalizes the known Boolean trichotomy of Koutris and Wijsen to every naturally ordered positive semiring, yielding concrete rewritings for the bag, tropical, Viterbi, and fuzzy semirings. For the bag semiring, the paper further shows that when the attack graph contains a strong cycle, computing the consistent answer is NP-hard even to approximate within any constant factor. A reader should care because the paper draws a sharp, syntactically checkable boundary between queries whose consistent answers are cheaply rewritable and queries whose answers are essentially intractable.

What carries the argument

The central objects are the logic LK, which augments first-order logic with a guarded minimization operator ∇_G x.φ that returns the least semiring value of φ over elements where the guard G is non-zero, and a Supp operator that flattens every non-zero value to 0; the attack graph of a conjunctive query, whose vertices are the query atoms and whose directed edges record when one atom's non-key variables can determine a key value of another atom through the key constraints; and the notion of a naturally ordered positive semiring, whose total order makes the minimum over repairs well-defined. The proof carries the argument by showing that, for acyclic attack graphs, the minimum over exponentially many repairs decomposes one unattacked atom at a time into a guarded minimization inside an LK formula, and that any cyclic attack graph yields a Boolean instance where a rewriting would contradict the known trichotomy for ordinary databases.

What would settle it

Exhibit a self-join-free conjunctive query with an acyclic attack graph and a naturally ordered positive semiring, for instance the bag semiring, for which no LK formula equals the minimum of the query over all repairs; equivalently, find an instance where the identity mCA_K(q,D,α) = Σ_c mCA_K(q[x],D,α(c/x)) of Lemma 4.15 fails, since the inductive rewriting is built entirely on that identity.

Watch

Extended reading notes

Core claim

The paper establishes Theorem 4.9: for any naturally ordered positive semiring K, any self-join-free conjunctive query q, and any set Σ of key constraints with one key per relation of q, the consistent-answer problem mCA_K(q,Σ) is LK-rewritable if and only if the attack graph of q is acyclic. The forward direction builds an LK formula by induction on the query, peeling off an unattacked atom and rewriting the consistent answer as a guarded minimization over that atom's non-key values multiplied by the rewriting of the remaining query; the converse shows that any LK rewriting translates, via the embedding of LK into first-order logic on the Boolean semiring, into an FO rewriting, and the prior trichotomy implies that such a rewriting forces acyclicity. Corollary 5.2 adds that over the bag semiring, a strong cycle in the attack graph makes even constant-factor approximation of mCAN(q,Σ) NP-hard under first-order reductions. The contribution is a syntax-to-complexity transfer: the same graph condition separates rewritable from intractable consistently across all naturally ordered positive semirings.

Load-bearing premise

The main construction depends on Lemma 4.15, whose proof is only sketched in an appendix and imports a lemma from a closely related paper with a shared author; if that lemma fails, the inductive rewriting in the central theorem collapses.

Editorial extensions

If this is right

  • For the bag, tropical, Viterbi, and fuzzy semirings, an acyclic attack graph yields an explicit LK rewriting, so consistent answers on those annotated databases are computable by evaluating one formula in the semiring analogue of uniform constant-depth circuits.
  • A query whose attack graph contains a strong cycle is, over bag databases, NP-hard to approximate even up to any constant relative factor, so no polynomial-time approximation scheme can exist unless P equals NP.
  • The Boolean trichotomy for self-join-free conjunctive queries under key constraints is subsumed as the special case K = B, with the same attack graph as the deciding criterion.
  • The data complexity of LK lies in a semiring variant of uniform AC0, meaning rewritable consistent answers retain the parallelizability of ordinary first-order query evaluation.
  • The paper supplies a uniform definition of repairs for annotated databases — maximal sub-databases whose supports satisfy the key constraints — so the same consistent-answer semantics applies across all naturally ordered positive semirings.

Reading between the lines

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

  • If the central equivalence extends as stated, the acyclicity criterion is likely to govern rewritability for other semirings whose natural preorder is total, such as truncated or cap-product semirings, because the proof machinery of guarded minimization and superfrugal repairs is semiring-generic.
  • The strong-cycle inapproximability result for the bag semiring suggests that other infinite naturally ordered semirings, such as the tropical semiring, may admit analogous constant-factor inapproximability; a direct reduction would need to control how the semiring's order interacts with annotated constants.
  • For queries whose attack graph has only weak cycles, the Boolean case is polynomial-time but not first-order rewritable, and the analogous semiring question is left open; a plausible outcome is polynomial-time computability through a semiring Datalog variant rather than an LK rewriting.
  • The min-over-repairs semantics aligns with the greatest-lower-bound semantics used for range aggregation queries, so the LK rewritings here could be reused as building blocks for computing glb answers to SUM-like aggregate queries over bag databases.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies consistent query answering for databases annotated with values from a naturally ordered positive semiring. It defines repairs as maximal sub-databases whose support satisfies a set of key constraints, defines the consistent answers mCA_K(q,Σ,𝔇) as the semiring minimum of the query values over all repairs, and introduces the logic LK, an extension of first-order logic with a guarded minimization operator ∇ and a Supp operator that flattens annotations. The main result (Theorem 4.9) states that, for self-join-free conjunctive queries with one key constraint per relation, the attack graph of the query is acyclic if and only if mCA_K(q,Σ) is LK-rewritable. The paper also proves (Corollary 5.2) that for the bag semiring, a strong cycle in the attack graph makes constant-factor approximation of the consistent answers NP-hard under first-order reductions.

Significance. If correct, Theorem 4.9 yields a uniform generalization of the FO-rewritable case of the Koutris-Wijsen trichotomy to all naturally ordered positive semirings, with new consequences for the bag, tropical, Viterbi, and fuzzy semirings. The non-approximability result in Section 5 is a novel and plausible contribution that connects consistent query answering with approximation algorithms. The right-to-left direction of the main theorem is sound and concise, and the overall proof strategy is convincing. The main caveat is that the left-to-right direction depends on Lemma 4.15, whose proof in Appendix B.3 is a sketch rather than a complete, self-contained argument. Until that lemma is fully proved or replaced by a precise statement and proof of the imported external result, the central theorem is not fully verifiable from this manuscript. The definitions of LK and of the semiring semantics are otherwise carefully developed, and the connection to constant-depth circuit classes is a useful contribution.

major comments (2)
  1. [Appendix B.3, Lemma 4.15] Lemma 4.15 is load-bearing for the left-to-right direction of Theorem 4.9: it is used both in the base case and in the inductive step of the proof. Its proof in Appendix B.3 is not self-contained. The argument cites [2, Lemma 4.5] without stating the lemma, introduces 'superfrugal repairs' and '∀R_i-blocks' through informal definitions, and defers the central induction over decreasing i with the sentence 'The reasoning is similar to that in Claim 2.' Since the lemma is semiring-sensitive—it exchanges a minimum over repairs with a sum over the active domain—the transfer from the Boolean/numerical setting of [2] to arbitrary naturally ordered positive semirings is precisely the point that needs to be proved. As it stands, a reader cannot fully verify Theorem 4.9 from the preprint alone.
  2. [Section 4.2, Eq. (7)] The displayed definition of the guarded minimization shorthand appears inconsistent with the stated semantics and with Proposition 4.3. With Supp(φ) defined as 1 if φ = 0 and 0 otherwise, and χ := Supp(∃z′G(®y,z′)), the formula θ(®y,z) := (Supp(G(®y,z)) ∧ ∃z′φ(®y,z′) ∧ χ) ∨ (φ(®y,z) ∧ χ) evaluates to 0 for every z whenever ∃z′G is supported (since then χ = 0), and it evaluates to the sum of all φ-values plus φ(z) when no G is supported. This contradicts the surrounding explanation and Proposition 4.3. If the authors intend a typographically distinct 'double Supp' operator (the shorthand mentioned on page 9), that distinction must be made explicit in Eq. (7) and the formula corrected accordingly. This is not merely cosmetic, because the guarded minimization operator is used in the path-query example and in the rewritings built in Theorem 4.9.
minor comments (5)
  1. [Section 4.3, Definition 4.7] The sentence defining FnAC0_K(+,×, min, Supp) writes 'max' instead of 'min'; the first class should be the functions computed by AC0_K(+,×, min, Supp) circuits.
  2. [Section 5, qsink example] The statement of the qsink example uses the bound variables ρ and α that are not introduced, and the parameter ε is replaced by ρ; the claim should be stated uniformly for every ε ≥ 1.
  3. [Appendix B.3, proof of Lemma 4.15] The definition of PreCopy(ℜ,i) as 'the smallest subset of Rep(𝔇,Σ) that contains ℜ′ whenever ...' is unclear; it should be replaced by the explicit description 'the set of all repairs ℜ′ that agree with ℜ on R_j-facts for all j ≤ i'.
  4. [Section 4.4, proof of Proposition 4.12] The step 'It is easy to see that ψ is an FO-rewriting of Cons(q,Σ)' would benefit from a sentence noting that for the Boolean semiring mCAB(q,Σ,𝔇) is always in {0,1} and that φ(𝔇) ≠ 0 holds exactly when Cons(q,Σ,𝔇) = 1.
  5. [Section 4.2, grammar of LK] The grammar for LK includes ∇xφ and Supp(φ), but the guarded-minimization shorthand ∇_G z.φ is defined only in prose around Eq. (7); the shorthand should be either integrated into the syntax or explicitly designated as a definable abbreviation with a correctness proof.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular reduction found: the main iff theorem is a substantive definability result, though its left-to-right proof inherits a load-bearing external co-authored lemma with a sketched proof.

full rationale

The paper's central equivalence (Theorem 4.9) relates a syntactic graph condition (acyclic attack graph, Definition 4.11) to the existence of an LK-formula equal to mCA_K(q,Σ) (Definition 4.4). Neither side is defined in terms of the other: LK has an independent semiring semantics, and mCA_K is defined directly as the minimum over repairs (Definition 3.5). The right-to-left direction (Proposition 4.12) reduces to the external Koutris-Wijsen result [26] via Proposition 4.2; this is a genuine import, not a renaming. The left-to-right direction is an induction that repeatedly applies Lemma 4.15. The proof of Lemma 4.15 given in Appendix B.3 is not fully self-contained: it invokes [2, Lemma 4.5] and then sketches a 'superfrugal repair' induction, ending with 'the reasoning is similar to that in Claim 2' and asserting the needed minimization without completing the induction. Because [2] shares an author with the present paper, the main theorem's acyclic-to-rewritable direction currently rests on a co-authored external lemma whose transfer to arbitrary naturally ordered positive semirings is not proven in full. This is a verifiability and correctness-risk concern, not a circularity: [2, Lemma 4.5] is a published result with independent content, it is not the target theorem, and no equation in the paper reconstructs mCA_K from its own definition. The path-query rewriting in Section 4.1 is proved directly in Appendix B.1, and the non-approximability results in Section 5 reduce to the known [26] trichotomy via a first-order reduction (Proposition 5.1), again without circularity. Score 2 reflects the load-bearing external co-authored dependency, not a circular derivation.

Assumptions & free parameters 0 free parameters · 6 assumptions · 1 invented entities

The central claim relies on standard finite-model-theoretic facts, on the external trichotomy of [26], and on a lemma imported from [2] that is used in the proof of the key decomposition lemma. No free parameters are fitted. The genuinely new formal object is the logic LK.

assumptions (6)
  • standard math The active domain of every K-database considered is finite and non-empty, so sums, products, and minima over the domain are finite.
    Assumed in the definitions of semiring semantics (Section 3) and used in the evaluation of LK formulas (Section 4.2).
  • standard math Every finite subset of a naturally ordered positive semiring has a minimum under its total order.
    Used to define mCA_K as a minimum over all repairs (Definition 3.5) and to give semantics to the guarded minimization operator (Equation (7)).
  • domain assumption Proposition 3.1, imported from Grädel and Tannen [17, Prop. 9], links semiring semantics of FO to set-based satisfaction on the support.
    Justifies the flattening definition of repairs in Definition 3.3 and the embedding of FO into LK in Proposition 4.2.
  • domain assumption The Koutris-Wijsen trichotomy theorem [26] for consistent answers of self-join-free conjunctive queries under primary keys is correct.
    Used as a black box in Proposition 4.12 (right-to-left direction of Theorem 4.9) and in Corollary 5.2 to transfer hardness to APPROX.
  • domain assumption Lemma 4.5 of [2] about superfrugal repairs is correct and is imported into the proof of Lemma 4.15.
    The proof of the key decomposition Lemma 4.15 depends on this external lemma; the preprint does not reproduce its proof.
  • standard math Armstrong's axioms for functional dependencies correctly compute the closure used in the definition of the attack graph.
    Used in Definition 4.10 to define the closure (var(𝒚))+Σ(q\R).
invented entities (1)
  • Logic LK with guarded minimization ∇ and suppression operator Supp
    purpose: Serves as the target language for rewritings of consistent answers mCA_K; the guarded minimizer captures the per-block minima appearing in semiring repairs.
    This is a new formal language introduced in Section 4.2. It has a defined semantics and a circuit-complexity upper bound (Proposition 4.8), but no independent falsifiable handle outside the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Rewriting Consistent Answers on Annotated Data." pith.science (2026). https://pith.science/paper/7NKJX56X

@misc{pith2026241211661,
  author       = {Pith},
  title        = {Pith review of: Rewriting Consistent Answers on Annotated Data},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7NKJX56X}},
  note         = {Machine review of arXiv:2412.11661}
}
read the original abstract

We embark on a study of the consistent answers of queries over databases annotated with values from a naturally ordered positive semiring. In this setting, the consistent answers of a query are defined as the minimum of the semiring values that the query takes over all repairs of an inconsistent database. The main focus is on self-join free conjunctive queries and key constraints, which is the most extensively studied case of consistent query answering over standard databases. We introduce a variant of first-order logic with a limited form of negation, define suitable semiring semantics, and then establish the main result of the paper: the consistent query answers of a self-join free conjunctive query under key constraints are rewritable in this logic if and only if the attack graph of the query contains no cycles. This result generalizes an analogous result of Koutris and Wijsen for ordinary databases, but also yields new results for a multitude of semirings, including the bag semiring, the tropical semiring, and the fuzzy semiring. Further, for the bag semiring, we show that computing the consistent answers of any self-join free conjunctive query whose attack graph has a strong cycle is not only NP-hard but also it is NP-hard to even approximate the consistent answers with a constant relative approximation guarantee.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 21 canonical work pages

  1. [2]

    Aziz Amezian El Khalfioui and Jef Wijsen. 2024. Computing Range Consistent Answers to Aggregation Queries via Rewriting. Proc. ACM Manag. Data 2, 5, Article 218 (Nov. 2024), 19 pages. https://doi.org/10.1145/3695836

    work page doi:10.1145/3695836 2024

  2. [1]

    Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley

    work page 1995

  3. [3]

    Bertossi, and Jan Chomicki

    Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. 1999. Consistent Query Answers in Inconsistent Databases. In Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia, Pennsylvania, USA , Victor Vianu and Christos H. Papadimitriou (Eds.). ACM Press, 68–79. https://doi.or...

    arXiv 1999

  4. [4]

    Bertossi, Jan Chomicki, Xin He, Vijay Raghavan, and Jeremy P

    Marcelo Arenas, Leopoldo E. Bertossi, Jan Chomicki, Xin He, Vijay Raghavan, and Jeremy P. Spinrad. 2003. Scalar aggregation in inconsistent databases. Theor. Comput. Sci. 296, 3 (2003), 405–434. https://doi.org/10.1016/S0304- 3975(02)00737-5

    doi:10.1016/s0304- 2003

  5. [5]

    Armstrong

    William W. Armstrong. 1974. Dependency Structures of Data Base Relationships.. In Proc. of IFIP World Computer Congress. 580–583

    work page 1974

  6. [6]

    Kolaitis

    Albert Atserias and Phokion G. Kolaitis. 2024. Consistency of Relations over Monoids. Proc. ACM Manag. Data 2, 2 (2024), 107. https://doi.org/10.1145/3651608

    doi:10.1145/3651608 2024

  7. [7]

    Timon Barlag, Miika Hannula, Juha Kontinen, Nina Pardal, and Jonni Virtema. 2023. Unified Foundations of Team Semantics via Semirings. In KR. 75–85

    work page 2023

  8. [8]

    Timon Barlag and Heribert Vollmer. 2021. A Logical Characterization of Constant-Depth Circuits over the Reals. In Logic, Language, Information, and Computation - 27th International Workshop, WoLLIC 2021, Virtual Event, October 5-8, 2021, Proceedings (Lecture Notes in Computer Science, Vol. 13038) , Alexandra Silva, Renata Wassermann, and Ruy J. G. B. de Q...

    work page doi:10.1007/978-3-030-88853-4_2 2021

Show all 39 references
  1. [9]

    Mix Barrington, Neil Immerman, and Howard Straubing

    David A. Mix Barrington, Neil Immerman, and Howard Straubing. 1990. On Uniformity within NC 1. J. Comput. Syst. Sci. 41, 3 (1990), 274–306. https://doi.org/10.1016/0022-0000(90)90022-D

    1990 doi

  2. [10]

    Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. 1997. Complexity and Real Computation . Springer-Verlag, Berlin, Heidelberg

    1997

  3. [11]

    Dannert, Erich Grädel, Matthias Naaf, and Val Tannen

    Katrin M. Dannert, Erich Grädel, Matthias Naaf, and Val Tannen. 2021. Semiring Provenance for Fixed-Point Logic. In 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, January 25-28, 2021, Ljubljana, Slovenia (Virtual Conference) (LIPIcs, Vol. 183), Christel Baie...

    2021 doi

  4. [12]

    Daniel Deutch, Tova Milo, Sudeepa Roy, and Val Tannen. 2014. Circuits for Datalog Provenance. In Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014 , Nicole Schweikardt, Vassilis Christophides, and Vincent Leroy (Eds.). OpenProceed...

    2014 doi

  5. [13]

    Heinz-Dieter Ebbinghaus, Jörg Flum, and Wolfgang Thomas. 1984. Mathematical logic. Springer

    1984

  6. [14]

    Diego Figueira, Anantha Padmanabha, Luc Segoufin, and Cristina Sirangelo. 2023. A Simple Algorithm for Consistent Query Answering Under Primary Keys. In 26th International Conference on Database Theory, ICDT 2023, March 28-31, 2023, Ioannina, Greece (LIPIcs, Vol. 255), Floris ...

    2023 doi

  7. [15]

    Ariel Fuxman and Renée J. Miller. 2007. First-order query rewriting for inconsistent databases. J. Comput. Syst. Sci. 73, 4 (2007), 610–635. https://doi.org/10.1016/J.JCSS.2006.10.013

    2007 doi

  8. [16]

    M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman

    1979

  9. [17]

    Erich Grädel and Val Tannen. 2017. Semiring Provenance for First-Order Model Checking. CoRR abs/1712.01980 (2017)

    2017 arXiv

  10. [18]

    Todd J. Green. 2011. Containment of Conjunctive Queries on Annotated Relations. Theory Comput. Syst. 49, 2 (2011), 429–459. https://doi.org/10.1007/S00224-011-9327-6

    2011 doi

  11. [19]

    Green, Gregory Karvounarakis, and Val Tannen

    Todd J. Green, Gregory Karvounarakis, and Val Tannen. 2007. Provenance semirings. InProceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 11-13, 2007, Beijing, China , Leonid Libkin (Ed.). ACM, 31–40. https://doi.org/10.1145...

    2007

  12. [20]

    Erich Grädel and Val Tannen. 2024. Provenance analysis and semiring semantics for first-order logic. (2024). To appear in a volume in honor of János Makowsky, published by Birkhäuser

    2024

  13. [21]

    S. Jukna. 2023. Tropical Circuit Complexity: Limits of Pure Dynamic Programming . Springer International Publishing. https://books.google.co.uk/books?id=sLUO0AEACAAJ

    2023

  14. [22]

    Ngo, Reinhard Pichler, Dan Suciu, and Yisu Remy Wang

    Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler, Dan Suciu, and Yisu Remy Wang. 2022. Convergence of Datalog over (Pre-) Semirings. In PODS ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022 , Leonid Libkin and Pablo Barceló (Eds.)...

    2022

  15. [23]

    Kostylev, Juan L

    Egor V. Kostylev, Juan L. Reutter, and András Z. Salamon. 2012. Classification of annotation semirings over query containment. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20-24, 2012 , Mic...

    2012

  16. [24]

    Paraschos Koutris, Xiating Ouyang, and Jef Wijsen. 2021. Consistent Query Answering for Primary Keys on Path Queries. In PODS’21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Virtual Event, China, June 20-25, 2021 , Leonid Libkin...

    2021

  17. [25]

    Paraschos Koutris, Xiating Ouyang, and Jef Wijsen. 2024. Consistent Query Answering for Primary Keys on Rooted Tree Queries. Proc. ACM Manag. Data 2, 2 (2024), 76. https://doi.org/10.1145/3651139

    2024 doi

  18. [26]

    Paraschos Koutris and Jef Wijsen. 2017. Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints. ACM Trans. Database Syst. 42, 2 (2017), 9:1–9:45. https://doi.org/10.1145/3068334

    2017 doi

  19. [27]

    Paraschos Koutris and Jef Wijsen. 2018. Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018 , Jan Van den Buss...

    2018

  20. [28]

    Paraschos Koutris and Jef Wijsen. 2020. First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020 , Dan S...

    2020

  21. [29]

    Paraschos Koutris and Jef Wijsen. 2021. Consistent Query Answering for Primary Keys in Datalog. Theory Comput. Syst. 65, 1 (2021), 122–178. https://doi.org/10.1007/S00224-020-09985-6

    2021 doi

  22. [30]

    Leonid Libkin. 2004. Elements of Finite Model Theory . Springer. https://doi.org/10.1007/978-3-662-07003-1 19

    2004 doi

  23. [31]

    Anantha Padmanabha, Luc Segoufin, and Cristina Sirangelo. 2024. A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join.Proc. ACM Manag. Data2, 2 (2024), 74. https://doi.org/10.1145/3651137

    2024 doi

  24. [32]

    Papadimitriou

    Christos H. Papadimitriou. 1994. Computational complexity. Addison-Wesley

    1994

  25. [33]

    Till Tantau. 2007. Logspace Optimization Problems and Their Approximability Properties. Theory Comput. Syst. 41, 2 (2007), 327–350. https://doi.org/10.1007/S00224-007-2011-1

    2007 doi

  26. [34]

    Moshe Y. Vardi. 1982. The complexity of relational query languages (Extended Abstract). In Proc. ACM Symposium on Theory of Computing (STOC 82 . 137–146

    1982

  27. [35]

    Heribert Vollmer. 1999. Introduction to Circuit Complexity - A Uniform Approach. Springer. https://doi.org/10.1007/978- 3-662-03927-4

    1999 doi

  28. [36]

    Jef Wijsen. 2010. On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases. In Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2010, June 6-11, 2010, Indianapolis, ...

    2010

  29. [37]

    Jef Wijsen. 2012. Certain conjunctive query answering in first-order logic. ACM Trans. Database Syst. 37, 2 (2012), 9:1–9:35. https://doi.org/10.1145/2188349.2188351

    2012

  30. [38]

    flattening

    Hangdong Zhao, Shaleen Deep, Paraschos Koutris, Sudeepa Roy, and Val Tannen. 2024. Evaluating Datalog over Semirings: A Grounding-based Approach. Proc. ACM Manag. Data 2, 2 (2024), 90. https://doi.org/10.1145/3651591 20 A Semiring semantics via interpretations In this appendix...

    2024 doi

  31. [39]

    The former𝑅𝑛−1-fact contributes(2× 1)+( 2× 1) = 4, while the latter contributes 1× 8 = 8

    Furthermore, assume that 𝑅𝔇 𝑛−1(𝑎,𝑏) = 2 and𝑅𝔇 𝑛−1(𝑎,𝑐) = 1, two facts belonging to the same ∀𝑅𝑛−1-block. The former𝑅𝑛−1-fact contributes(2× 1)+( 2× 1) = 4, while the latter contributes 1× 8 = 8. So our procedure will select𝑅𝑛−1(𝑎,𝑏), which, notably, is not the fact with the s...

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.