Pith. sign in

REVIEW 2 minor 30 references

The Role of Semirings in Incremental View Maintenance

T0 review · 0 major / 2 minor · reviewed 2026-06-27 · grok-4.3

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

Pith's one-line read A conjunctive query without self-joins can be maintained with amortized constant update time and constant enumeration delay under inserts to K-databases if and only if it is α-acyclic p-hierarchical.

desk verdict The paper pins down a semiring-dependent dichotomy for constant-time insert-only IVM on conjunctive queries without self-joins via the new p-hierarchical class. read the letter →

arxiv 2606.07795 v1 pith:GCAC6UOE submitted 2026-06-05 cs.DB

Eden Chmielewski , Andrei Draghici , Dan Olteanu , Haozhe Zhang This is my paper · ORCID
classification cs.DB
keywords incrementalviewmaintenanceconjunctivequeriessemiringsp-hierarchicalalpha-acyclicitydichotomyinsert-onlyupdates
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

The paper studies incremental view maintenance for conjunctive queries when databases receive only insertions and the values come from a commutative semiring without additive inverses. It introduces the class of p-hierarchical queries and proves that any such query with fractional hypertree width fhtw admits a data structure supporting amortized O(N^{fhtw-1}) update time and constant-delay enumeration of the result over any qualifying semiring. When the query is additionally α-acyclic the update time becomes constant. Conditional lower bounds show that queries without self-joins that fall outside the p-hierarchical class cannot achieve constant amortized update time and constant delay for the natural semiring, the provenance semiring, the covariance semiring, or any idempotent strictly ordered semiring such as the tropical semiring. The upper and lower bounds together establish a clean dichotomy for insert-only maintenance of conjunctive queries without self-joins.

What carries the argument

p-hierarchical queries, a structural class of conjunctive queries that permits hierarchical decomposition for incremental maintenance, together with α-acyclicity and the absence of additive inverses in the semiring.

What would settle it

A conjunctive query without self-joins that is not α-acyclic p-hierarchical yet admits a data structure with amortized constant update time and constant enumeration delay for inserts over the natural semiring would falsify the claimed dichotomy.

Watch

Extended reading notes

Core claim

For K-databases over semirings without additive inverses, a conjunctive query without self-joins admits amortized constant update time and constant enumeration delay under inserts if and only if the query is α-acyclic p-hierarchical.

Load-bearing premise

The lower-bound direction holds only for conjunctive queries without self-joins.

Editorial extensions

If this is right

  • Any α-acyclic p-hierarchical query admits constant amortized update time and constant delay enumeration for any semiring without additive inverses.
  • A p-hierarchical query that is not α-acyclic requires amortized update time O(N^{fhtw-1}) where fhtw is its fractional hypertree width.
  • Any conjunctive query without self-joins that is not p-hierarchical cannot be maintained with amortized constant update time and constant delay under the listed semirings.
  • The dichotomy applies uniformly to the natural numbers semiring, provenance semiring, covariance semiring, and idempotent strictly ordered semirings such as the tropical semiring.

Reading between the lines

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

  • The restriction to insert-only sequences and semirings without additive inverses is what allows the algorithms to avoid cancellations that would otherwise require more expensive recomputation.
  • Similar structural characterizations might exist for maintenance under deletions or mixed updates, though the paper does not address them.
  • Query optimizers could use the p-hierarchical property as a syntactic check to decide whether constant-time view maintenance is feasible for a given workload.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 2 minor

Summary. The manuscript claims to establish a dichotomy for the incremental maintenance of conjunctive queries without self-joins over commutative semirings without additive inverses. Specifically, such a query admits amortized constant update time and constant delay enumeration under insert-only updates to K-databases if and only if it is α-acyclic and p-hierarchical. The upper bound construction applies to any p-hierarchical query and depends on its fractional hypertree width, while conditional lower bounds are provided for non-p-hierarchical queries over the natural semiring and generalizations including provenance, covariance, and idempotent strictly ordered semirings like the tropical semiring.

Significance. If the results hold, this work provides a fundamental structural characterization of when IVM is tractable, showing that semiring choice (via axioms like absence of additive inverses or idempotence) directly governs complexity. The upper bounds rely on query hypergraph properties and semiring axioms for a data structure supporting updates and enumeration; the conditional lower bounds are scoped precisely to queries without self-joins. This offers a clean, falsifiable dichotomy that credits the use of structural query properties rather than fitted parameters.

minor comments (2)
  1. [Abstract] Abstract: the p-hierarchical class is introduced without even a one-sentence characterization or example, which reduces immediate readability of the central dichotomy claim.
  2. The manuscript would benefit from an explicit statement (perhaps in the introduction or a dedicated section) of the exact conditional hypotheses used in the lower-bound proofs, as the abstract only alludes to them.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our results, the accurate characterization of the dichotomy, and the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified

full rationale

The derivation relies on the newly introduced structural definition of p-hierarchical queries together with standard semiring axioms and known notions such as fractional hypertree width and α-acyclicity. Upper bounds are obtained by explicit data-structure constructions whose update and enumeration costs are bounded directly from the query structure; lower bounds are conditional hardness results scoped explicitly to conjunctive queries without self-joins. No step reduces a claimed bound to a quantity defined inside the paper by construction, no fitted parameter is relabeled as a prediction, and no load-bearing premise rests solely on a self-citation whose content is itself unverified. The result is therefore self-contained against external benchmarks.

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

The central claim rests on standard semiring axioms (commutativity, no additive inverse) and the newly introduced p-hierarchical structural restriction; no numerical free parameters are fitted.

assumptions (1)
  • domain assumption K is a commutative semiring without additive inverse
    Explicitly stated as the algebraic setting for the K-databases throughout the abstract.
invented entities (1)
  • p-hierarchical query
    purpose: Structural class of conjunctive queries for which the efficient IVM data structure exists
    Newly defined in the paper to separate tractable from intractable cases under the semiring model.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Role of Semirings in Incremental View Maintenance." pith.science (2026). https://pith.science/paper/GCAC6UOE

@misc{pith2026260607795,
  author       = {Pith},
  title        = {Pith review of: The Role of Semirings in Incremental View Maintenance},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GCAC6UOE}},
  note         = {Machine review of arXiv:2606.07795}
}
abstract

We study the problem of incremental view maintenance (IVM) under inserts to $K$-databases, where $K$ is a commutative semiring without additive inverse. The key observation put forward in this paper is that the complexity of the IVM problem depends fundamentally on the underlying semiring. We introduce a class of conjunctive queries called $p$-hierarchical and show that for any $p$-hierarchical query with fractional hypertree width $\fhtw$ and any insert-only update sequence of length $N$ to an initially empty $K$-database over an arbitrary semiring $K$ without additive inverse, we can construct a data structure that can be updated in amortized $\bigO(N^{\fhtw-1})$ time and can support constant delay enumeration of the query result. In particular, the amortized update time for any $\alpha$-acyclic $p$-hierarchical query is constant. We also give conditional lower bounds showing that any conjunctive query without self-joins that is not $p$-hierarchical cannot be maintained with amortized constant update time and constant enumeration delay under inserts to $K$-databases. Here, $K$ can be the natural semiring and its generalizations to the provenance and covariance semirings or any idempotent and strictly ordered semiring such as the tropical semiring. When put together, our upper and lower bounds imply a dichotomy for the insert-only maintenance of conjunctive queries without self-joins and the aforementioned semirings: A query can be maintained with amortized constant update time and constant enumeration delay if and only if it is $\alpha$-acyclic $p$-hierarchical.

Figures

Figures reproduced from arXiv: 2606.07795 by the authors.

Figure 1
Figure 1. The strict containment hierarchy of tractable classes of conjunctive queries. Each continuous line is a [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. (left) A variable order of 𝑄1; (middle) A variable order of 𝑄2; (right) A variable order of 𝑄3. BVO denotes the bound variable order. Free variables are dark red. Algorithm 1: CreateVarOrders(𝑄) Input: A p-hierarchical query 𝑄 Output: A forest of extended bound variable orders 1 Initialize a directed graph 𝐺 := (V, E) with V := Bound(𝑄) and E := ∅ 2 foreach 𝑋 ∈ V do 3 if ∃𝑌 ∈ V s.t. 𝑋 < 𝑌 ∧ š𝑍 ∈ V s.t. 𝑋 < 𝑍 < 𝑌 the… view at source ↗
Figure 3
Figure 3. (left) A forest of bound variable orders intermediately produced by Algorithm [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 28 canonical work pages

  1. [1]

    Mahmoud Abo Khamis, Eden Chmielewski, Andrei Draghici, Ahmet Kara, and Dan Olteanu. 2026. Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations.Proc. ACM Manag. Data4, 2, Article 109 (2026), 22 pages. doi:10.1145/3801905

    work page doi:10.1145/3801905 2026

  2. [2]

    Mahmoud Abo Khamis, Ahmet Kara, Dan Olteanu, and Dan Suciu. 2024. Insert-Only versus Insert-Delete in Dynamic Query Evaluation.Proc. ACM Manag. Data2, 5, Article 219 (Nov. 2024). doi:10.1145/3695837

    work page doi:10.1145/3695837 2024

  3. [3]

    Omer Abramovich, Daniel Deutch, Nave Frost, Ahmet Kara, and Dan Olteanu. 2024. Banzhaf Values for Facts in Query Answering.Proc. ACM Manag. Data2, 3 (2024), 123. doi:10.1145/3654926

    work page doi:10.1145/3654926 2024

  4. [4]

    Omer Abramovich, Daniel Deutch, Nave Frost, Ahmet Kara, and Dan Olteanu. 2025. Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms.Proc. VLDB Endow.18, 11 (2025), 3996–4008. doi:10.14778/3749646.3749670

    work page doi:10.14778/3749646.3749670 2025

  5. [5]

    Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. 2007. On Acyclic Conjunctive Queries and Constant Delay Enumeration. InCSL. 208–222. doi:10.1007/978-3-540-74915-8_18

    work page doi:10.1007/978-3-540-74915-8_18 2007

  6. [6]

    Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. 2017. Answering Conjunctive Queries Under Updates. In PODS. 303–318. doi:10.1145/3034786.3034789 28 Eden Chmielewski, Andrei Draghici, Dan Olteanu, and Haozhe Zhang

    work page doi:10.1145/3034786.3034789 2017

  7. [7]

    Knowledge graphs querying,

    Leopoldo E. Bertossi, Benny Kimelfeld, Ester Livshits, and Mikaël Monet. 2023. The Shapley Value in Database Management.SIGMOD Rec.52, 2 (2023), 6–17. doi:10.1145/3615952.3615954

    work page doi:10.1145/3615952.3615954 2023

  8. [8]

    Mihai Budiu, Tej Chajed, Frank McSherry, Leonid Ryzhyk, and Val Tannen. 2023. DBSP: Automatic Incremental View Maintenance for Rich Query Languages.Proc. VLDB Endow.16, 7 (2023), 1601–1614. doi:10.14778/3587136.3587137

    work page doi:10.14778/3587136.3587137 2023

Show all 30 references
  1. [9]

    2008.Graphs, Dioids and Semirings: New Models and Algorithms (Operations Research/Computer Science Interfaces Series)(1 ed.)

    Michel Gondran and Michel Minoux. 2008.Graphs, Dioids and Semirings: New Models and Algorithms (Operations Research/Computer Science Interfaces Series)(1 ed.)

    2008

  2. [10]

    Todd J. Green. 2009. Containment of conjunctive queries on annotated relations. InICDT. 296–309. doi:10.1145/ 1514894.1514930

    2009

  3. [11]

    Green, Zachary G

    Todd J. Green, Zachary G. Ives, and Val Tannen. 2011. Reconcilable Differences.Theory of Computing Systems(2011), 460–488. doi:10.1007/s00224-011-9323-x

    2011 doi

  4. [12]

    Green, Grigoris Karvounarakis, and Val Tannen

    Todd J. Green, Grigoris Karvounarakis, and Val Tannen. 2007. Provenance semirings. InPODS. 31–40. doi:10.1145/ 1265530.1265535

    2007

  5. [13]

    Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. 2015. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. InSTOC. 21–30. doi:10.1145/2746539.2746609

    2015 doi

  6. [14]

    Muhammad Idris, Martín Ugarte, and Stijn Vansummeren. 2017. The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates. InSIGMOD. 1259–1274. doi:10.1145/3035918.3064027

    2017 doi

  7. [15]

    Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang

    Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2019. Counting Triangles under Updates in Worst-Case Optimal Time. InICDT. 4:1–4:18. doi:10.4230/LIPICS.ICDT.2019.4

    2019 doi

  8. [16]

    Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2024. F-IVM: Analytics over Relational Databases under Updates.VLDB J.33, 4 (2024), 903–929. doi:10.1007/S00778-023-00817-W

    2024 doi

  9. [17]

    Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2025. Conjunctive Queries with Free Access Patterns under Updates.LMCSVolume 21, Issue 2, Article 23 (2025). doi:10.46298/lmcs-21(2:23)2025

    2025 doi

  10. [18]

    Ahmet Kara, Dan Olteanu, and Dan Suciu. 2024. From Shapley Value to Model Counting and Back.Proc. ACM Manag. Data2, 2 (2024), 79. doi:10.1145/3651142

    2024 doi

  11. [19]

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

    Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler, Dan Suciu, and Yisu Remy Wang. 2024. Convergence of datalog over (Pre-) Semirings.J. ACM71, 2 (2024), 8:1–8:55. doi:10.1145/3643027

    2024 doi

  12. [20]

    Ngo, and Atri Rudra

    Mahmoud Abo Khamis, Hung Q. Ngo, and Atri Rudra. 2016. FAQ: Questions Asked Frequently. InPODS. 13–28. doi:10.1145/2902251.2902280

    2016 doi

  13. [21]

    Christoph Koch, Yanif Ahmad, Oliver Kennedy, Milos Nikolic, Andres Nötzli, Daniel Lupei, and Amir Shaikhha. 2014. DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views.VLDB J.23, 2 (2014), 253–278. doi:10.14778/2336664.2336670

    2014 doi

  14. [22]

    Kostylev and Peter Buneman

    Egor V. Kostylev and Peter Buneman. 2012. Combining Dependent Annotations for Relational Algebra. InICDT. 196–207. doi:10.1145/2274576.2274597

    2012 doi

  15. [23]

    Mehryar Mohri. 2002. Semiring Frameworks and Algorithms for Shortest-Distance Problems.J. Autom. Lang. Comb.7, 3 (2002), 321–350. doi:10.25596/JALC-2002-321

    2002 doi

  16. [24]

    Milos Nikolic and Dan Olteanu. 2018. Incremental View Maintenance with Triple Lock Factorization Benefits. In SIGMOD. 365–380. doi:10.1145/3183713.3183758

    2018 doi

  17. [25]

    Dan Olteanu. 2024. Recent Increments in Incremental View Maintenance. InPODS. 8–17. doi:10.1145/3635138.3654763

    2024 doi

  18. [26]

    Dan Olteanu and Jakub Závodný. 2015. Size Bounds for Factorised Representations of Query Results.ACM Trans. Database Syst.40, 1 (2015), 2:1–2:44. doi:10.1145/2656335

    2015 doi

  19. [27]

    RAIVM Engine

    RelationalAI, Inc 2026. RAIVM Engine. https://www.relational.ai

    2026

  20. [28]

    2011.Probabilistic Databases

    Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch. 2011.Probabilistic Databases. Morgan & Claypool Publishers. doi:10.2200/S00362ED1V01Y201105DTM016

    2011 doi

  21. [29]

    Qichen Wang. 2026. Towards Parameterized Hardness on Maintaining Conjunctive Queries.CoRRabs/2603.14754 (2026). arXiv:2603.14754 doi:10.48550/ARXIV.2603.14754

    2026 doi

  22. [30]

    Qichen Wang, Xiao Hu, Binyang Dai, and Ke Yi. 2023. Change Propagation without Joins.Proc. VLDB Endow.16, 5 (2023), 1046–1058. doi:10.14778/3579075.3579080 A Appendix Proposition13[restated]For any p-hierarchical query, its fractional hypertree width equals the fractional hype...

    2023 doi

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.