[Submitted on 26 Jul 2026]

View PDF HTML (experimental)

Abstract:Dynamic query processing keeps query answers up to date during insertions and deletions. For conjunctive queries (CQs) under set semantics, the maintainable classes are known exactly: the $q$-hierarchical CQs under arbitrary updates, widening to the free-connex CQs under insertion-only updates. But modern analytics aggregates, including bag counting, SUM/COUNT, provenance, access control, and shortest paths---all captured by evaluating a CQ over a positive commutative semiring. We ask whether aggregation changes what can be maintained efficiently, and if so, when.
Under arbitrary updates, it does not: maintenance is at least as hard as over the Boolean semiring. Under insertion-only updates, it does: the boundary retreats from free-connex to a new class we call strong-connex, with $q$-hierarchical $\subsetneq$ strong-connex $\subsetneq$ free-connex $\subsetneq$ acyclic. For every ordered semiring carrying a suitable monotone sequence (e.g., sum-product and tropical), no free-connex but non-strong-connex CQ is maintainable in $O(|D|^{1/2-\epsilon})$ time under the OuMv and OMv conjectures. We further strengthen this lower bound into a family parameterized by the height and dimension of the query, under the combinatorial $k$-clique and generalized OuMv conjectures; these quantify how far the annotated hardness grows as the queries scale.
On the algorithmic side, a single framework matches these boundaries by adapting CROWN to annotated relations. It maintains every strong-connex CQ in $O(1)$ amortized time under insertion-only updates, regardless of the underlying semiring. Moreover, under arbitrary updates, it maintains every $q$-hierarchical CQ in $O(1)$ amortized time if the semiring has $O(1)$-deletable aggregations. Together, the upper and lower bounds give query- and semiring-parameterized dichotomies that recover the Boolean picture and pinpoint the hardness aggregation adds.

Submission history

From: Qichen Wang [view email]
[v1] Sun, 26 Jul 2026 22:58:57 UTC (223 KB)