pith. sign in

arxiv: 2606.07795 · v1 · pith:GCAC6UOEnew · submitted 2026-06-05 · 💻 cs.DB

The Role of Semirings in Incremental View Maintenance

Eden Chmielewski , Andrei Draghici , Dan Olteanu , Haozhe Zhang This is my paper

Pith reviewed 2026-06-27 20:04 UTC · model grok-4.3

classification 💻 cs.DB
keywords incremental view maintenanceconjunctive queriessemiringsp-hierarchical queriesalpha-acyclicitydichotomyinsert-only updates
0
0 comments X

The pith

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.

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

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.

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.

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.

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.

Where Pith is reading between the lines

These are 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.

Load-bearing premise

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

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.

Figures

Figures reproduced from arXiv: 2606.07795 by Andrei Draghici, Dan Olteanu, Eden Chmielewski, Haozhe Zhang.

Figure 1
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. 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. 𝑋 <… view at source ↗
Figure 3
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 ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 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.

axioms (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 no independent evidence
    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.

pith-pipeline@v0.9.1-grok · 5836 in / 1356 out tokens · 27588 ms · 2026-06-27T20:04:07.710065+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 26 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

  9. [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

  10. [10]

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

    arXiv 2009

  11. [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

    work page doi:10.1007/s00224-011-9323-x 2011

  12. [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

    arXiv 2007

  13. [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

    work page doi:10.1145/2746539.2746609 2015

  14. [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

    work page doi:10.1145/3035918.3064027 2017

  15. [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

    work page doi:10.4230/lipics.icdt.2019.4 2019

  16. [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

    work page doi:10.1007/s00778-023-00817-w 2024

  17. [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

    work page doi:10.46298/lmcs-21(2:23)2025 2025

  18. [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

    work page doi:10.1145/3651142 2024

  19. [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

    work page doi:10.1145/3643027 2024

  20. [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

    work page doi:10.1145/2902251.2902280 2016

  21. [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

    work page doi:10.14778/2336664.2336670 2014

  22. [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

    work page doi:10.1145/2274576.2274597 2012

  23. [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

    work page doi:10.25596/jalc-2002-321 2002

  24. [24]

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

    work page doi:10.1145/3183713.3183758 2018

  25. [25]

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

    work page doi:10.1145/3635138.3654763 2024

  26. [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

    work page doi:10.1145/2656335 2015

  27. [27]

    RAIVM Engine

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

    2026

  28. [28]

    2011.Probabilistic Databases

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

    work page doi:10.2200/s00362ed1v01y201105dtm016 2011

  29. [29]

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

    work page doi:10.48550/arxiv.2603.14754 2026

  30. [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 hypertree width of its Boolean version. Proof. Let 𝑄( F) be a p-hierarchical query. ...

    work page doi:10.14778/3579075.3579080 2023