Answering Conjunctive Queries with Aggregations under Updates
arXiv:2607.23881v1 [cs.DB] 26 Jul 2026
QICHEN WANG, Nanyang Technological University, Singapore XIAO HU, University of Waterloo, Canada 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 𝑞-hierarchical CQs under arbitrary updates, widening to the free-connex CQs under insertion-only updates. 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 𝑞-hierarchical ⊊ strong-connex ⊊ free-connex ⊊ 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 𝑂p|𝐷|1{2´𝜖 q 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 𝑘-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 𝑂p1q amortized time under insertion-only updates, regardless of the underlying semiring. Moreover, under arbitrary updates, it maintains every 𝑞-hierarchical CQ in 𝑂p1q amortized time if the semiring has 𝑂p1q-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.
1
Introduction
Dynamic query processing studies how to keep query answers up to date as the underlying database evolves through insertions and deletions of tuples. This setting is the norm rather than the exception: the data behind modern applications is in constant flux, such as transactional writes, event and sensor streams, application logs, and continuously arriving records, while the queries over that data must return fresh answers with low latency for dashboards, monitoring, alerting, fraud detection, and recommendation. Re-evaluating a query from scratch after every change is wasteful and, at scale, infeasible. Instead, one maintains a data structure refreshed incrementally on each update that, on demand, enumerates the current results with a bounded delay between consecutive tuples. The goal is to keep two costs small at once: the amortized update time spent per tuple, and the enumeration delay at query time. This incremental paradigm is also applied in view maintenance in relational engines, continuous query evaluation, and streaming query systems, and it has been studied intensively over the past decade as a source of both practical systems and theoretical dichotomies [5, 12, 13, 15, 22, 27, 28, 31–33, 36, 37, 44, 45]. For conjunctive queries (CQs) under set semantics, the complexity landscape of dynamic evaluation is well-studied. Under arbitrary update sequences, the class of 𝑞-hierarchical CQs admits highly efficient indexing, and Wang [42] shows the hardness increases with chain or star shape queries. On the other hand, in practice, the update sequence may not be arbitrary. For example, the insertion-only sequences capture query evaluation over a static database built one tuple at a time, and the boundary shifts outward with such sequences, widening the maintainable class exactly to Authors’ Contact Information: Qichen Wang, [email protected], Nanyang Technological University, Singapore; Xiao Hu, [email protected], University of Waterloo, Waterloo, Ontario, Canada.
2
Qichen Wang and Xiao Hu acyclic free-connex nullary qhierarchical full strong-connex
Fig. 1. Classification of CQs.
the free-connex CQs. Bridging these extremes, recent work has also characterized maintainability under first-in-first-out (FIFO) update sequences [27]. However, these results exclusively concern the Boolean semiring (i.e., set semantics), where a tuple either belongs to the result or does not. In practice, query answers are frequently annotated: bag semantics count multiplicities, COUNT/SUM aggregations accumulate numeric weights, provenance semirings track derivations, and access-control semirings carry min/max weights. Aggregating over such annotations is not a niche generalization but the primary workhorse of modern data analytics. Indeed, GROUP BY paired with SUM, COUNT, MIN, or MAX drives the vast majority of OLAP and reporting workloads. Because this annotated evaluation framework simultaneously captures bag semantics, probabilistic inference, access control, and shortest-path computations over the tropical semiring, a single result stated over an abstract semiring transfers seamlessly to all of these domains at once. Crucially, these workloads are inherently dynamic. Dashboards constantly recompute aggregates over live tables, feature pipelines re-derive SUM/COUNT statistics as events arrive, and graph analytics continuously update reachability weights. Therefore, applications overwhelmingly demand join-aggregate maintenance, not merely Boolean maintenance. This leaves open a practically central question: Does aggregation fundamentally change what can be maintained efficiently, and if so, when? In this paper, we answer this question by charting the maintainability landscape of join-aggregate queries along two axes: the query structure and the algebraic structure of the aggregation. On the query axis, we identify a new class of strong-connex CQs, which sits strictly between the qhierarchical and free-connex classes. On the semiring axis, we isolate the ordered semirings, whose additive and multiplicative structure admits an infinite strictly increasing sequence. Together, these two axes yield a dichotomy. We further extend both upper and lower bounds to arbitrary updates and to semirings that fall outside this classification. Ultimately, these results mark a significant step toward understanding how aggregation fundamentally impacts the complexity of dynamic query maintenance. 1.1
Problem Definition
Conjunctive Queries. Let R be a database schema with 𝑚 relations 𝑅1, 𝑅2, ¨ ¨ ¨ , 𝑅𝑚 over a set of 𝑛 attributes V “ t𝑥 1, 𝑥 2, ¨ ¨ ¨ , 𝑥𝑛 u. Each relation 𝑅𝑖 is defined ś on a subset of attributes 𝑒𝑖 Ď V. Let domp𝑥q be the domain of attribute 𝑥, and let domp𝑋 q “ 𝑥 P𝑋 domp𝑥q be the domain of a subset of attributes 𝑋 Ď V. Let 𝐷 be a given instance of R, and let the corresponding instances of 𝑅1, ¨ ¨ ¨ , 𝑅𝑚 𝐷 , where 𝑅 𝐷 is a collection of tuples from domp𝑒 q. Whenever the context is clear, we be 𝑅1𝐷 , ¨ ¨ ¨ , 𝑅𝑚 𝑖 𝑖 drop the superscript 𝐷 and use 𝑅𝑖 for both the relation and its instance. In this paper, we consider the class of conjunctive queries without self-joins,1 formally defined as Qp𝐷q :“ 𝜋 y p𝑅1 p𝑒 1 q 1 𝑅2 p𝑒 2 q 1 ¨ ¨ ¨ 1 𝑅𝑚 p𝑒𝑚 qq ,
where y Ď V denotes the set of output attributes, and ȳ “ V ´ y denotes the set of non-output attributes. Each 𝑅𝑖 in Q is distinct, i.e., the CQ has no self-join. We also represent Q as a triple 1 As we only consider CQs without self-joins, we write “CQ” for “CQ without self-joins” in the remainder of this paper.
Answering Conjunctive Queries with Aggregations under Updates
3
Table 1. Main notations used throughout the paper. Symbol
Meaning
Q “ pV, E, yq ȳ “ V ´ y E𝑥 T ; keyp𝑒q 𝐷; |𝐷| 𝑆 K “ pK, ‘, b, 0, 1q 𝑤p𝑡q; suppp𝑅q ď, ă 𝐴p𝑐 1 ,𝑐 2 q 𝑛 ‘,𝑐 2 p𝑣q; 𝑚 b,𝑐 1 p𝑣q 𝑎 a𝑏
CQ with attributes V, relation schemas E, and output attributes y Non-output attributes of Q Set of relation schemas containing attribute 𝑥 (Generalized) join tree; join key of node 𝑒 with its parent Dynamic database; its maximum snapshot size Update sequence Commutative semiring with domain K Annotation of tuple 𝑡; support of K-relation 𝑅 Fixed compatible preorder on K; its strict version Maximum p𝑐 1, 𝑐 2 q-bounded fragment generated by 𝐴 Minimum number of summands (resp. factors) in bounded representations of 𝑣 Monus
pV, E, yq, where E “ t𝑒 1, 𝑒 2, ¨ ¨ ¨ , 𝑒𝑚 u. A CQ is full if y “ V; a full CQ is the natural join of its relations, and we omit 𝜋y in this case. A CQ is nullary if y “ H; under set semantics, a nullary CQ is exactly a Boolean CQ, which indicates whether the underlying join has any result. Several classes of CQs, as illustrated in Figure 1, play a central role in this paper. Their formal definitions are given in Section 2. Table 1 summarizes the notation used throughout the paper. Commutative Semirings and Annotated Relations. A commutative semiring is a tuple K “ pK, ‘, b, 0, 1q, where ‘ and b are commutative binary operators over the domain K, such that pK, ‘, 0q and pK, b, 1q are commutative monoids, b distributes over ‘, and 𝑣 b 0 “ 0 for every 𝑣 P K. As all semirings in this paper are commutative, we omit “commutative” from now on. A semiring is zero-sum-free if 𝑎 ‘ 𝑏 “ 0 implies 𝑎 “ 𝑏 “ 0, and zero-divisor-free if 𝑎 b 𝑏 “ 0 implies 𝑎 “ 0 or 𝑏 “ 0; a semiring with both properties is called positive [20]. All semirings in this paper are further assumed to be positive, and we likewise omit “positive”. Positivity is what keeps insertions apart from deletions: without it, two non-0 annotations can cancel, so an insertion can erase an earlier one. For example, over the integer ring pZ, `, ˆ, 0, 1q, inserting the annotation ´𝑤 on a tuple currently annotated 𝑤 zeroes it out and thereby simulates a deletion, so maintenance over insertion-only sequences (defined below) would degenerate to maintenance under arbitrary updates. In a K-relation, every tuple 𝑡 carries an annotation 𝑤p𝑡q P K; a join combines annotations with b, and a projection aggregates the annotations of tuples that collapse to the same output tuple with ‘. A K-relation 𝑅 over an attribute set 𝑋 is a function 𝑤 : domp𝑋 q Ñ K, whose support is defined as suppp𝑅q “ t𝑡 P domp𝑋 q : 𝑤p𝑡q ‰ 0u. Equivalently, each tuple 𝑡 carries an annotation 𝑤p𝑡q P K, and tuples with annotation 0 are absent. For a CQ Q “ pV, E, yq, let Qfull “ pV, Eq denote the corresponding full CQ. Given an Kinstance 𝐷, the annotation of a join result 𝑡 P Qfull p𝐷q is â 𝑤p𝑡q “ 𝑤p𝜋𝑒 𝑡q, 𝑒PE
and the annotation of a result tuple 𝑡 y P Qp𝐷q is à 𝑤p𝑡 y q “
â 𝑤p𝜋𝑒 𝑡q.
𝑡 P Qfull p𝐷 q: 𝜋 y 𝑡 “𝑡 y 𝑒 P E
Therefore, join multiple annotations and projection sums annotations, exactly as in the positive relational algebra on K-relations [19, 21]. The Boolean semiring pt0, 1u, _, ^, FALSE, TRUEq recovers set semantics; the bag semiring with all input annotations equal to 1 recovers bag
4
Qichen Wang and Xiao Hu
counting and COUNT(*) GROUP BY; and the sum-product semiring pRě0, `, ˆ, 0, 1q captures matrix products and aggregate joins. The optimization setting often relates to the tropical semiring pR Y t´8u, max, `, ´8, 0q. We also specifically explore the max-max semiring K “ pL Y tK, ´8u, ‘, b, K, ´8q over an ordered domain L, where K is a fresh element serving as the additive identity and the multiplicative annihilator, ´8 is a fresh element smaller than every element of L serving as the multiplicative identity, and both operators are commutative: # # maxp𝑎, 𝑏q if 𝑎, 𝑏 P L Y t´8u, maxp𝑎, 𝑏q if 𝑎, 𝑏 P L Y t´8u, 𝑎 ‘𝑏 “ 𝑎 b𝑏 “ 𝑎 if 𝑏 “ K, K if 𝑏 “ K. K-updates and K-sequences. We model each update as a quadruple 𝑢 “ p𝑡, 𝑠, 𝛿, 𝑅𝑖 q for 𝑠 P Z and 𝛿 P Kzt0u: an insertion p𝑡, 𝑠, 𝛿, 𝑅𝑖 q updates the annotation of tuple 𝑡 in relation 𝑅𝑖 to 𝑤p𝑡q ‘ 𝛿 at timestamp 𝑠 (a tuple that is not present is treated as having annotation 0); a deletion retracts one earlier insertion p𝑡, 𝑠 1, 𝛿, 𝑅𝑖 q with 𝑠 1 ă 𝑠, i.e., it removes the contribution 𝛿 from the annotation of 𝑡. Over the Boolean semiring, this reduces to the standard set semantics, where an update either inserts a tuple into 𝑅𝑖 or deletes one from it. Let 𝑆 be a sequence of updates ordered by their timestamps. We only consider a single update at any timestamp, and an enumeration procedure can be invoked after any timestamp. We assume that the initial database is empty; every tuple of a non-empty initial database can be modeled by an insertion at timestamp ´8. Given an update sequence 𝑆, the lifespan of an inserted contribution is an interval r𝑡 `, 𝑡 ´ s, where ` 𝑡 denotes the timestamp of the insertion and 𝑡 ´ denotes the timestamp of the deletion that retracts it (𝑡 ´ “ `8 if it is never retracted). The same tuple can be repeatedly inserted and deleted; we treat these copies as logically different, each with its own lifespan. The database 𝐷 is dynamically defined by 𝑆: for every timestamp 𝑠 P Z, the copies that are alive at 𝑠 (i.e., 𝑠 P r𝑡 `, 𝑡 ´ s) form a snapshot of 𝐷, in which the annotation of a tuple 𝑡 is the ‘-aggregate of its alive contributions. We define the size of a dynamic database, denoted |𝐷|, as the maximum number of copies that co-exist at any timestamp. A special class of update sequences that has been well studied is that of insertion-only sequences, which are closely connected to query evaluation over static databases. An update sequence 𝑆 is insertion-only if it contains no deletion; it is not insertion-only otherwise. Delay-bounded enumeration. We focus on 𝑂p1q-delay enumeration: the time from the start of the enumeration to the first result, the time between any consecutive pair of results, and the time from the last result to the termination of the enumeration process are all 𝑂p1q. The enumeration returns every result tuple together with its annotation; for a nullary query, it returns the single annotation 𝑤pxyq of the empty tuple (or reports that it is 0). In this paper, we aim to understand the maintenance complexity of a CQ for 𝑂p1q-delay enumeration. Throughout, “Q can be maintained in 𝛼 time over a set S of update sequences” is a shorthand for “ there exists an index (resp. there does not exist an index) that can be updated in 𝛼 amortized time over an arbitrary update sequence 𝑆 P S, while supporting 𝑂p1q-delay enumeration for Q whenever needed”. Model of Computation. We work in the unit-cost word-RAM model with word size 𝑂plog 𝑁 q, where 𝑁 is the size of the input data. Domain values, tuple identifiers, pointers, and relation indices fit in 𝑂p1q words. Dictionary operations are assumed to take the expected 𝑂p1q time, or worst-case 𝑂p1q time under a perfect-hashing assumption. For an arbitrary semiring K, each element in the domain of K can be represented by 𝑂p1q words, and the primitive operations including ‘, b, comparison operations, and any difference/deletion operation explicitly assumed below, take 𝑂p1q time. Thus, our bounds are data-structure bounds relative to this semiring representation; they do not include the bit-complexity of evaluating
Answering Conjunctive Queries with Aggregations under Updates
5
arbitrary semiring operations. This assumption is necessary: if the semiring operations are part of the input or are allowed to encode arbitrary computation, the query problem can inherit the computational complexity of those operations [16]. 1.2
Previous Results
Maintaining CQs under arbitrary updates. In 2017, two papers [12, 28] simultaneously studied the worst-case complexity of maintaining CQs under arbitrary updates. Any q-hierarchical CQ can be maintained in 𝑂p1q time under arbitrary updates, even in the presence of COUNT aggregation. Conversely, no non-q-hierarchical CQ can be maintained in 𝑂p|𝐷|1{2´𝜖 q time for any constant 𝜖 ą 0, assuming the OMv conjecture [12]. This lower bound has been matched for some specific non-q-hierarchical CQs, such as the triangle query [31] and the length-4 cycle query [23]. Moreover, any a free-connex CQ can be maintained in 𝑂p|𝐷|q time under arbitrary updates [28, 44], leaving a |𝐷|-gap between the lower and upper bounds for general non-q-hierarchical CQs. Recently, Wang [42] narrowed this gap via two structural parameters of a free-connex CQ, its height ℎ and dimension 𝑑: unless widely believed conjectures fail, no algorithm can maintain such a CQ in 𝑂p|𝐷|1´1{ maxpℎ,𝑑 q´𝜖 q amortized time for any constant 𝜖 ą 0, and a matching instance-dependent algorithm exists for star queries. In addition, the update-delay tradeoff has been investigated for some specific queries, such as the triangle query [31] and hierarchical CQs [32]. Beyond the worst case, Wang and Yi [45] studied the instance-dependent complexity of this problem for foreign-key acyclic joins, based on the enclosureness of update sequences; intuitively, enclosureness measures the interdependence among the lifespan intervals of tuples from different relations. Wang et al. [44] generalized this notion to free-connex CQs, and showed that free-connex CQs can be maintained in time proportional to the enclosureness of the update sequence. The formal definition of enclosureness [27, 44] is not needed in this paper; we only use the fact that every insertiononly sequence has enclosureness 𝑂p1q, so any free-connex CQ over the Boolean semiring can be maintained in 𝑂p1q amortized time over insertion-only sequences [44]. Recently, Hu and Wang [27] extended this update-dependent analysis of Boolean CQs beyond insertion-only sequences, to first-in-first-out (FIFO) and mixed update sequences. This paper takes an orthogonal direction: we fix the class of insertion-only sequences and ask how the complexity landscape changes when the query is evaluated over a general semiring. Maintaining CQs under insertion-only updates. Idris et al. [28] showed that for any CQ Q, if Q can be maintained in 𝛼 time over insertion-only sequences, then for an arbitrary database 𝐷, an index can be built in 𝑂p𝛼 ¨ |𝐷|q preprocessing time, from which all query results of Qp𝐷q can be enumerated with 𝑂p1q delay. Following this reduction, any lower bound for enumerating CQs over static databases implies a lower bound for maintaining CQs over insertion-only sequences. Bagan et al. [9] and Brault-Baron [14] showed that after 𝑂p|𝐷|q preprocessing time, the query results of a CQ Q over any static database 𝐷 can be enumerated with 𝑂p1q delay, if and only if Q is free-connex. Hence, for any non-free-connex CQ, no index can be updated in 𝑂p1q amortized time over insertion-only sequences while supporting 𝑂p1q-delay enumeration, assuming the Boolean Matrix Multiplication2 , Triangle Detection3 , and HyperClique4 conjectures. Together with the 2 The Boolean Matrix Multiplication (BMM) conjecture [9, 11] states: Given two Boolean matrices of size 𝑛 ˆ 𝑛, no algorithm
can compute their product in 𝑂p𝑛 2 q time. 3 The Triangle Detection conjecture [2] states: Given a graph with 𝑚 edges, no algorithm can decide whether a triangle exists or not in 𝑂p𝑚q time. 4 The HyperClique (HC) conjecture [35] states: Given a 𝑘-uniform hypergraph with 𝑚 hyperedges (for 𝑘 ě 3), no algorithm can decide in 𝑂p𝑚q time whether a hyperclique of size 𝑘 ` 1 exists, i.e., a set of 𝑘 ` 1 vertices in which every subset of size 𝑘 forms a hyperedge.
6
Qichen Wang and Xiao Hu
Arbitrary Updates
Insertion-Only Updates
Semiring q-hierarchical Boolean Sum-product Tropical Max-max
𝑂p1q 𝑂p1q 𝑂plog |𝐷|q 𝑂plog |𝐷|q
Any semiring
𝑂p1q:
non-q-hierarchical strong-connex Ωp|𝐷|1{2 q
non-strong-connex
Dichotomy
Ωp|𝐷|1{2 q Ωp|𝐷|1{2 q Ωp|𝐷|1{2 q
𝑂p1q 𝑂p1q 𝑂p1q 𝑂p1q
𝑂p1q Ωp|𝐷|1{2 q Ωp|𝐷|1{2 q 𝑂p1q˚ ; Ωp|𝐷|1{2 q
– ✓ ✓ –
Ωp|𝐷|1{2 q
𝑂p1q
𝑂p1q§ ; Ωp|𝐷|1{2 q;
Theorem 1.1
Table 2. The maintainability landscape for join-aggregate queries with 𝑂p1q-delay enumeration. Cells show the amortized update cost; lower bounds are conditional on the conjectures of Sections 3 and 4.4. (˚) for nullary queries and Ωp|𝐷|1{2 q otherwise. (:) for semirings with 𝑂p1q-deletable aggregates. (;) for ordered semirings that contain a monotone sequence of length |𝐷|𝜂 whose fragments satisfy the strictly-ordered conditions of Section 4.1. (§) for naturally ordered semirings in which every monotone sequence has length 𝑂p1q.
𝑂p1q upper bound for free-connex CQs stated above, the free-connex CQs are exactly the class of Boolean CQs that can be maintained in 𝑂p1q amortized time over insertion-only sequences [27, 44]. Due to the inherent hardness of maintaining non-free-connex CQs even over insertion-only sequences, we focus exclusively on free-connex CQs throughout the remaining of this paper. 1.3
Our Results
We have made significant progress towards a complete answer for the main question and, more generally, characterize the phenomenon through structural conditions on the semiring. Our contributions are fourfold. Our main results are also summarized in Table 2. Characterization of strong-connex CQs. We first characterize a class of CQs called strong-connex CQs that sits between q-hierarchical CQs and free-connex CQs. In symbols, 𝑞-hierarchical ⊊ strong-connex ⊊ free-connex ⊊ acyclic, Note that the Boolean semiring can be efficiently maintained for free-connex queries, but over a large class of semirings (including sum-product semiring), retreats to strong-connex. We further identify two simplest queries that are free-connex but not strong-connex: ` ˘ ` ˘ Qhier “ 𝜋H 𝑅1 p𝑥 1, 𝑥 2 q ’ 𝑅2 p𝑥 1 q ’ 𝑅3 p𝑥 2 q and Qqcore “ 𝜋𝑥 1 𝑅1 p𝑥 1, 𝑥 2 q ’ 𝑅2 p𝑥 2 q and show that every free-connex but non-strong-connex CQ must contain either Qhier or Qqcore as a subquery. These structural properties are the key to extending our lower bounds to general free-connex but non-strong-connex queries. Lower Bounds. We establish our lower bounds via two dimensions: (1) the two queries Qhier and Qqcore are hard to maintain not only over the sum-product and tropical semirings, but over any ordered semiring that contains a monotone sequence of polynomial length, even |𝐷|𝜂 for an arbitrarily small constant 𝜂 ą 0, whose bounded fragments are strictly ordered under ‘ and b, assuming the OuMv and OMv conjectures. These order conditions isolate exactly the algebraic feature a reduction exploits, and cleanly separate hard semirings from easy ones. For example, the Boolean semiring does not admit such monotone sequences, hence maintaining both queries over the Boolean semiring is easy; the sum-product semiring admits such monotone sequences, hence maintaining both queries over the sum-product semiring is hard. (2) We lift the hardness to every free-connex but non-strong-connex CQ: a structural lemma shows that every such CQ contains one of two hard patterns, an D-hierarchy-core mirroring Qhier or a q-core mirroring Qqcore , and a query-level reduction translates the update sequences of the corresponding hard query into update
Answering Conjunctive Queries with Aggregations under Updates
7
sequences of the given CQ, relation by relation, with the annotations preserved. The lower bounds then transfer with the same semiring conditions: both order conditions for an D-hierarchy-core, and only the ‘-condition for a q-core. Additionally, scaling the two hard queries Qhier and Qqcore into path and star families yields a sharper lower bounds parameterized by the height and dimension of the query, under the Combinatorial 𝑘-Clique and OuMv𝑘 conjectures. These quantify how far the annotated hardness grows as the query chain adds more relations or widens a single relation. Upper bounds via annotated CROWN. We adapt the query maintenance framework CROWN [44] from the Boolean setting to annotated relations. The key idea is piggybacking: annotations are propagated only along the tree edges that fold a non-output attribute into a parent, while subtrees whose join keys contain only output attributes keep their annotations local and combine them lazily at enumeration. On the join tree guaranteed by strong-connexity, every propagating edge touches exactly one tuple per update, so every strong-connex CQ can be maintained in 𝑂p1q amortized time over insertion-only update sequences. Beyond strong-connex CQs, the same 𝑂p1q bound holds for every free-connex CQ whenever the semiring is naturally ordered and all of its monotone sequences have length 𝑂p1q. The reason is different from piggybacking: under the natural order, an insertion never decreases the annotation of a tuple, so the successive distinct values of every maintained annotation form a monotone sequence, and each annotation changes at most 𝑂p1q times throughout the entire update sequence. The Boolean semiring is the special case where every monotone sequence has length one. Moreover, we identify that for the max-max semiring (which admits monotone sequences of polynomial length, hence fails the second result above), any nullary CQ (that can even be nonstrong-connex, hence fails the first result above) can also be maintained in 𝑂p1q amortized time over insertion-only update sequences. We further show the same framework applies to q-hierarchical CQs over arbitrary sequences. If the semiring admits 𝑂p1q-deletable aggregates, such as the Boolean and bag semirings, the extension incurs no asymptotic overhead, and every q-hierarchical CQ is maintained in 𝑂p1q amortized time; for semirings without 𝑂p1q-deletable aggregates, such as the tropical and max-max semirings, the maintenance cost increases to 𝑂plog |𝐷|q. This gap is inherent rather than an artifact of our data structure: a sorting reduction proves that the tropical semiring admits no 𝑂p1q-deletable aggregates. New dichotomy results. By combining our upper and lower bounds, we achieve the following dichotomy results for a large class of semirings (including sum-product semiring and tropical semiring as examples): Theorem 1.1. Let K be an ordered semiring that contains a monotone sequence 𝐴 of length |𝐷| 2 such that 𝐴p2|𝐷 |2,2q is both ‘-strictly-ordered and b-strictly-ordered. For any free-connex CQ Q, if Q is strong-connex, there exists an index that can be maintained in 𝑂p1q amortized time over insertion-only sequences while supporting 𝑂p1q-delay enumeration; otherwise, for any constant 𝜖 ą 0, no index for Q can be updated in 𝑂p|𝐷|1{2´𝜖 q amortized time while supporting 𝑂p|𝐷|1{2´𝜖 q-delay enumeration over every insertion-only K-sequence that define a dynamic database of size |𝐷|, assuming the OuMv and OMv conjectures. 1
There are a few interesting observations on general semirings that might contrast with our belief built on top of Boolean semirings. Aggregation is at least as hard as the Boolean case. First, maintaining CQs over any semiring is at least as hard as maintaining the corresponding Boolean CQs: annotating every tuple with 1, and truncating all non-0 annotations to 1 for the final annotation, reduces the latter to the former.
8
Qichen Wang and Xiao Hu
Positivity is exactly what makes this reduction sound: annotations only accumulate, so the support of an annotated relation behaves like a set-semantics relation. Nullary is not necessarily easier than its projection version. We highlight a key contrast with the nullary versus projection queries. For a CQ Q with its nullary version QH . If Q can be maintained in 𝑂p𝛼q time over the Boolean semiring, then so can QH : whenever any result of Q is enumerated, we simply output true for QH . Hence, over the Boolean semiring, the nullary version of a CQ is never harder than its projection counterparts. This implication fails over general semirings: the annotation of a nullary result aggregates the annotations of all join results, carrying strictly more information than the mere existence of matching tuples. Indeed, over the sum-product semiring, it is hard to maintain Qhier for insertion-only update sequences, but it is easy to maintain its full version 𝑅1 p𝑥 1, 𝑥 2 q 1 𝑅2 p𝑥 1 q 1 𝑅3 p𝑥 2 q. As another example, over the max-max semiring, both Qhier and its full version are easy to maintain, yet any other projection version, such as 𝜋𝑥 1 p𝑅1 p𝑥 1, 𝑥 2 q 1 𝑅2 p𝑥 1 q 1 𝑅3 p𝑥 2 qq or 𝜋𝑥 2 p𝑅1 p𝑥 1, 𝑥 2 q 1 𝑅2 p𝑥 1 q 1 𝑅3 p𝑥 2 qq, is hard to maintain. 1.4
Organization
Section 2 introduces the target CQ classes and their structural characterizations. Section 3 proves lower bounds for Qhier and Qqcore over the sum-product and tropical semirings. Section 4 generalizes these lower bounds to general ordered semirings, lifts them to all free-connex non-strong-connex CQs, and strengthens them for path and star families. Section 5 presents matching upper bounds via annotated CROWN, nullary queries over max-max semirings, and arbitrary update extensions. 2
Classification of CQs
This section formally introduces the classes of CQs studied in this paper. We start with basic terminology and several important classes of CQs. In a CQ Q “ pV, E, yq, let E𝑥 “ t𝑒 P E : 𝑥 P 𝑒u be the set of relation schemas containing attribute 𝑥 P V. An attribute 𝑥 P V is unique if it appears in exactly one relation, i.e., |E𝑥 | “ 1. A generalized relation 𝑅𝑒 is defined on a subset 𝑒 Ď V of attributes such that 𝑒 Ď 𝑒 1 X𝑒 2 for some input relations 𝑒 1, 𝑒 2 P E with 𝑒 1 ‰ 𝑒 2 , and is distinguished from the input relations in E. Acyclic CQ [10, 17]. A CQ Q “ pV, E, yq is acyclic if there exists a tree T in which each node corresponds to a distinct input relation in E or a generalized relation, satisfying the following properties: (cover property) each input relation corresponds to a node in T , and each leaf node of T corresponds to an input relation; (connect property) for each attribute 𝑥 P V, all nodes of T containing 𝑥 form a connected subtree of T . We call T a generalized join tree of Q. Given a join tree T , for a non-root node 𝑒 with parent node 𝑒𝑝 , the join key of 𝑒 is keyp𝑒q “ 𝑒 X 𝑒𝑝 ; for the root node 𝑟 of T , we set keyp𝑟 q “ H. Free-connex CQ [9, 27, 44]. A CQ Q “ pV, E, yq is free-connex if it has a generalized join tree T satisfying the following property: (connex property) there exists a connected subtree Tcon of T Ťsuch that (i) Tcon contains the root of T ; (ii) keyp𝑒q Ď y for every node 𝑒 P Tcon ; and (iii) y Ď 𝑒 P Tcon 𝑒. We call T a free-connex join tree of Q, and Tcon the connex subtree of T . 𝑞-hierarchical CQ [12]. A CQ Q “ pV, E, yq is 𝑞-hierarchical if it has a free-connex join tree T satisfying the following property: for every non-root node 𝑒 of T with its parent node 𝑒𝑝 , 𝑒𝑝 Ď 𝑒. An equivalent structural characterization is provided in Lemma 2.1 via two key properties. Lemma 2.1 ([12]). A q-hierarchical CQ Q “ pV, E, yq satisfies: (hierarchy-property) for every pair of attributes 𝑥 1, 𝑥 2 P V, either E𝑥 1 Ď E𝑥 2 or E𝑥 2 Ď E𝑥 1 or E𝑥 1 X E𝑥 2 “ H; and (q-property) if 𝑥 1 P y and E𝑥 1 ⊊ E𝑥 2 , then 𝑥 2 P y.
Answering Conjunctive Queries with Aggregations under Updates
9
A non-q-hierarchical CQ Q “ pV, E, yq must have one of the following structures: (hierarchycore) three distinct relations 𝑒 1, 𝑒 2, 𝑒 3 P E and two distinct attributes 𝑥 1, 𝑥 2 P V with 𝑥 1 P 𝑒 1 X 𝑒 2 ´ 𝑒 3 and 𝑥 2 P 𝑒 2 X 𝑒 3 ´ 𝑒 1 ; and (q-core) if 𝑥 1 P y and E𝑥 1 ⊊ E𝑥 2 , then 𝑥 2 P y. In this paper, we identify the class of strong-connex CQs, which sits between free-connex CQs and 𝑞-hierarchical CQs. We first provide a formal definition with respect to a free-connex join tree. Definition 2.2 (Strong-Connex CQ). A free-connex CQ Q “ pV, E, yq is strong-connex if it has a free-connex join tree satisfying the following property: for each non-root node 𝑒 with parent 𝑒𝑝 , either (i) keyp𝑒q Ď y or (ii) 𝑒𝑝 Ď 𝑒. The free-connex join tree characterized for strong-connex CQs is a strict relaxation of that for q-hierarchical CQs, hence a q-hierarchical CQ must be strong-connex. On the other hand, every strong-connex CQ has a free-connex join tree, hence it must be free-connex. Similarly, we follow up with an equivalent structural characterization. Lemma 2.3. A strong-connex CQ Q “ pV, E, yq must satisfy: (D-hierarchy-property) for any pair of non-output attributes 𝑥 1, 𝑥 2 P ȳ, either E𝑥 1 Ď E𝑥 2 or E𝑥 2 Ď E𝑥 1 or E𝑥 1 X E𝑥 2 “ H; and (head-cluster-property) for every pair of relations 𝑒, 𝑒 1 P E, if 𝑒 X 𝑒 1 X ȳ ‰ H, then 𝑒 X y “ 𝑒 1 X y. Lemma 2.4. A free-connex but non-strong-connex CQ Q “ pV, E, yq must have one of the following structures: (D-hierarchy-core) three distinct relations 𝑒 1, 𝑒 2, 𝑒 3 P E and two distinct attributes 𝑥 1, 𝑥 2 P ȳ with 𝑥 1 P 𝑒 1 X 𝑒 2 ´ 𝑒 3 and 𝑥 2 P 𝑒 2 X 𝑒 3 ´ 𝑒 1 ; or (q-core) two distinct relations 𝑒 1, 𝑒 2 P E and two distinct attributes 𝑥 1 P y, 𝑥 2 P ȳ with 𝑥 1 P 𝑒 1 ´ 𝑒 2 and 𝑥 2 P 𝑒 1 X 𝑒 2 . In Lemma 2.3, both conditions constrain only the non-output attributes. The D-hierarchy-property enforces the hierarchical property solely on non-output attributes, contrasting with 𝑞-hierarchical CQs, where it is required for all attributes. The head-cluster-property demands that any pair of relations sharing a non-output attribute must share the exact same set of output attributes. This property inherently implies the 𝑞-property. To see why, suppose for contradiction that there exist attributes 𝑥 1 P y and 𝑥 2 R y such that E𝑥 1 ⊊ E𝑥 2 . Consider relations 𝑒 P E𝑥 1 and 𝑒 1 P E𝑥 2 zE𝑥 1 . Because 𝑥 2 P 𝑒 X 𝑒 1 X ȳ, the head-cluster-property implies 𝑒 X y “ 𝑒 1 X y, which contradicts the fact that 𝑥 1 P 𝑒z𝑒 1 . Hence, any q-hierarchical CQ must be strong-connex. Every 𝑞-hierarchical CQ is strong-connex, and every strong-connex CQ is free-connex. Both containments are strict. For example, Q “ 𝑅1 p𝑥 1 q 1 𝑅2 p𝑥 1, 𝑥 2 q 1 𝑅3 p𝑥 2, 𝑥 3 q 1 𝑅4 p𝑥 3, 𝑥 4 q 1 𝑅5 p𝑥 4 q is strong-connex but not 𝑞-hierarchical. In constrast, Q “ 𝜋𝑥 3,𝑥 4 p𝑅1 p𝑥 1, 𝑥 2 q 1 𝑅2 p𝑥 2, 𝑥 3 q 1 𝑅3 p𝑥 3, 𝑥 4 qq is free-connex but not strong-connex, because 𝑅1 and 𝑅2 share the non-output attribute 𝑥 2 yet have different output attributes. Furthermore, these structural properties exhibit interesting behaviors at the extremes: all full queries are strong-connex, and all nullary queries are free-connex. 3
Lower Bounds: Example Queries and Semi-rings
In this section, we establish the lower bounds for some example CQs over some example semirings under insertion-only K-sequences to illustrate the high-level idea of how aggregation increases the hardness. Our focus will be on these two simplest free-connex but non-strong-connex CQs, Qhier “ 𝜋H p𝑅1 p𝑥 1, 𝑥 2 q 1 𝑅2 p𝑥 1 q 1 𝑅3 p𝑥 2 qq ,
Qqcore “ 𝜋𝑥 1 p𝑅1 p𝑥 1, 𝑥 2 q 1 𝑅2 p𝑥 2 qq ,
and prove that neither can be maintained efficiently over the sum-product semiring or the tropical semiring. Note that both CQs are free-connex, and hence maintainable in 𝑂p1q amortized time over the Boolean semiring [44]. This result shows a significant separation between the Boolean semiring and the sum-product/tropical semiring.
10
3.1
Qichen Wang and Xiao Hu
Maintaining Qhier
We start with the ř sum-product semiring pRě0, `, ˆ, 0, 1q, where the annotation of the nullary result of Qhier is p𝑖,𝑗 q 𝑤 2 p𝑖q ¨ 𝑤 1 p𝑖, 𝑗q ¨ 𝑤 3 p𝑗q, i.e., a vector-matrix-vector product. This immediately suggests a reduction from the OuMv problem, as illustrated in Figure 2. Conjecture 3.1 (OuMv Conjecture [24]). The following problem cannot be solved in 𝑂p𝑛 3´𝜖 q time for any constant 𝜖 ą 0: Given an 𝑛 ˆ𝑛 Boolean matrix 𝑀 and a sequence of pairs of 𝑛-dimensional Boolean vectors p𝑢 1, 𝑣 1 q, p𝑢 2, 𝑣 2 q, ¨ ¨ ¨ , p𝑢𝑛 , 𝑣𝑛 q, it is required to output 𝑢𝑇𝑖 𝑀𝑣𝑖 before seeing p𝑢𝑖 `1, 𝑣𝑖 `1 q, for every 𝑖 P r𝑛s. Lemma 3.2. For Qhier over the sum-product semiring pRě0, `, ˆ, 0, 1q and any constant 𝜖 ą 0, no index can be updated in 𝑂p|𝐷|1{2´𝜖 q amortized time while supporting 𝑂p|𝐷|1´𝜖 q-delay enumeration over insertion-only K-sequences, assuming the OuMv conjecture. Proof. Given an OuMv instance of dimension 𝑛, let 𝑎ℎ “ ℎ for every ℎ P r𝑛s. We encode the matrix 𝑀 by relation 𝑅1 , the vectors x𝑢ℎ : ℎ P r𝑛sy by 𝑅2 , and the vectors x𝑣ℎ : ℎ P r𝑛sy by 𝑅3 . We build two databases and update them separately with two insertion-only K-sequences 𝑆 1 and 𝑆 2 : first, for both 𝑆 1 and 𝑆 2 , we insert a tuple p𝑖, 𝑗q into 𝑅1 with annotation 1, for each p𝑖, 𝑗q P r𝑛s ˆ r𝑛s with 𝑀𝑖 𝑗 ‰ 0; we also initialize 𝑤 0 “ 0. Then, for each pair of vectors p𝑢ℎ , 𝑣ℎ q, we perform the following procedure: ‚ in 𝑆 1 , we insert a tuple p𝑗q into 𝑅2 for each 𝑗 P r𝑛s with 𝑢ℎ 𝑗 ‰ 0; in 𝑆 2 , we insert a tuple p𝑗q into 𝑅3 for each 𝑗 P r𝑛s with 𝑣ℎ 𝑗 ‰ 0; all with annotation 𝑎ℎ ; ‚ we issue the enumeration query for Qhier over both databases, and let 𝑤ℎ1 , 𝑤ℎ2 be the annotations returned; ‚ in 𝑆 1 , we insert a tuple p𝑗q into 𝑅3 for each 𝑗 P r𝑛s with 𝑣ℎ 𝑗 ‰ 0; in 𝑆 2 , we insert a tuple p𝑗q into 𝑅2 for each 𝑗 P r𝑛s with 𝑢ℎ 𝑗 ‰ 0; again, all with annotation 𝑎ℎ ; ‚ we issue the enumeration query for Qhier over the first database, and let 𝑤ℎ be the annotation returned. We return true for p𝑢ℎ , 𝑣ℎ q if 𝑤ℎ´1 ` 𝑤ℎ ą 𝑤ℎ1 ` 𝑤ℎ2 , and false otherwise. For correctness, observe that for every ℎ P r𝑛s, ˜ ¸ ˜ ¸ ˜ ¸ ˜ ¸ ˜ ¸ ˜ ¸ ℎ ℎ ℎ ℎÿ ´1 ℎÿ ´1 ℎ ÿ ÿ ÿ ÿ 𝑤ℎ “ 𝑎𝑖 𝑢𝑇𝑖 𝑀 𝑎𝑖 𝑣𝑖 , 𝑤ℎ1 “ 𝑎𝑖 𝑢𝑇𝑖 𝑀 𝑎𝑖 𝑣𝑖 , 𝑤ℎ2 “ 𝑎𝑖 𝑢𝑇𝑖 𝑀 𝑎𝑖 𝑣 𝑖 , 𝑖 “1
𝑖 “1
𝑖 “1
𝑖 “1
𝑖 “1
𝑖 “1
so 𝑤ℎ´1 `𝑤ℎ ´𝑤ℎ1 ´𝑤ℎ2 “ p𝑎ℎ𝑢𝑇ℎ q𝑀p𝑎ℎ 𝑣ℎ q “ 𝑎ℎ2 ¨𝑢𝑇ℎ 𝑀𝑣ℎ , which is positive if and only if 𝑢𝑇ℎ 𝑀𝑣ℎ ‰ 0. Each database receives at most 3𝑛 2 insertions in total, so |𝐷| “ 𝑂p𝑛 2 q. If an index for Qhier can be updated in 𝑂p𝑛 1´𝜖 q amortized time over insertion-only K-sequences while supporting 𝑂p𝑛 2´𝜖 q-delay enumeration, the OuMv instance can be solved in 𝑂p𝑛 2 ¨ 𝑛 1´𝜖 ` 𝑛 ¨ 𝑛 2´𝜖 q “ 𝑂p𝑛 3´𝜖 q time, contradicting the OuMv conjecture. □ The same query is also hard over the tropical semiring, where the annotations cannot be canceled out as in a ring; instead, the reduction exploits the strict growth of the inserted annotations. Lemma 3.3. For Qhier over the tropical semiring pR Y t´8u, max, `, ´8, 0q and any constant 𝜖 ą 0, no index can be updated in 𝑂p|𝐷|1{2´𝜖 q amortized time while supporting 𝑂p|𝐷|1´𝜖 q-delay enumeration over insertion-only K-sequences, assuming the OuMv conjecture. Proof. Given an OuMv instance of dimension 𝑛, let 𝑎ℎ “ ℎ for every ℎ P r𝑛s, and encode 𝑀, x𝑢ℎ y, and x𝑣ℎ y by 𝑅1 , 𝑅2 , and 𝑅3 as before. For the tropical semiring, a single database suffices. We insert a tuple p𝑖, 𝑗q into 𝑅1 with annotation 0, for each p𝑖, 𝑗q P r𝑛s ˆ r𝑛s with 𝑀𝑖 𝑗 ‰ 0. Then, for each pair of vectors p𝑢ℎ , 𝑣ℎ q, we insert a tuple p𝑗q into 𝑅2 for each 𝑗 P r𝑛s with 𝑢ℎ 𝑗 ‰ 0, and a tuple
Answering Conjunctive Queries with Aggregations under Updates Ui M Vi−1
R1
Ui M Vi Ui+1 M Vi
11 Time
Ui+1 M Vi+1
M S1
ui
R2
ui+1 vi vi+1
R3
R1
M
R2
ui ui+1
S2
vi
R3
vi+1 Time Ui−1 M Vi Ui M Vi Ui M Vi+1 Ui+1 M Vi+1
Fig. 2. Reduction from OuMv to Qhier , where 𝑈𝑖 “ R2
ř𝑖
𝑇 𝑗 “1 𝑢 𝑗 and 𝑉𝑖 “
ř𝑖
𝑗 “1 𝑣 𝑗 .
v1 v2
R1
M
M v1
M v2
Time
Fig. 3. An illustration of the reduction from OMv to Qcore under sum-product semi-ring.
p𝑗q into 𝑅3 for each 𝑗 P r𝑛s with 𝑣ℎ 𝑗 ‰ 0, all with annotation 𝑎ℎ ; we then issue the enumeration query for Qhier , let 𝑤ℎ be the annotation returned, and return true for p𝑢ℎ , 𝑣ℎ q if 𝑤ℎ “ 𝑎ℎ ` 𝑎ℎ , and false otherwise. Recall that re-inserting a tuple p𝑗q at round ℎ updates its annotation to be the maximum between its previous annotation and 𝑎ℎ , which turns out to be 𝑎ℎ . For correctness, observe that ␣ ( 𝑤ℎ “ max 𝑎𝑘 ` 𝑎𝑙 : 𝑘, 𝑙 P rℎs, Dp𝑖, 𝑗q such that 𝑀𝑖 𝑗 ‰ 0, 𝑢𝑘𝑖 ‰ 0, 𝑣𝑙 𝑗 ‰ 0 . Since 𝑎 1 ă 𝑎 2 ă ¨ ¨ ¨ ă 𝑎𝑛 , we have 𝑤ℎ “ 𝑎ℎ ` 𝑎ℎ if and only if the maximum is attained with 𝑘 “ 𝑙 “ ℎ, i.e., if and only if 𝑢𝑇ℎ 𝑀𝑣ℎ ‰ 0. The cost analysis is the same as in Lemma 3.2. □ 3.2
Maintaining Qqcore
Conjecture 3.4 (OMv Conjecture [24]). The following problem cannot be solved in 𝑂p𝑛 3´𝜖 q time for any constant 𝜖 ą 0: Given an 𝑛 ˆ 𝑛 Boolean matrix 𝑀 and a sequence of 𝑛-dimensional Boolean vectors 𝑣 1, 𝑣 2, ¨ ¨ ¨ , 𝑣𝑛 , it is required to output 𝑀𝑣𝑖 before seeing 𝑣𝑖 `1 , for every 𝑖 P r𝑛s. Lemma 3.5. For Qqcore over the sum-product semiring pRě0, `, ˆ, 0, 1q and any constant 𝜖 ą 0, no index can be updated in 𝑂p|𝐷|1{2´𝜖 q amortized time over insertion-only K-sequences while supporting 𝑂p|𝐷|1{2´𝜖 q-delay enumeration, assuming the OMv conjecture. Proof of Lemma 3.5. See Figure 3. Given an instance of OMv, we encode matrix 𝑀 by 𝑅1 and vectors x𝑣ℎ : ℎ P r𝑛sy by 𝑅2 . We construct an insertion-only sequence 𝑆 for Qqcore as follows: (1)
12
Qichen Wang and Xiao Hu
we add a tuple 𝑡 “ p𝑖, 𝑗q into 𝑅1 , for each p𝑖, 𝑗q P r𝑛s ˆ r𝑛s with 𝑀𝑖 𝑗 ‰ 0; (2) for each 𝑖 P r𝑛s, we set 𝑤 0 p𝑖q “ 0; (3) for vector 𝑣ℎ , we add a tuple 𝑡 “ p𝑗q into 𝑅2 for each 𝑗 P r𝑛s if 𝑣ℎ 𝑗 ‰ 0; (4) we issue the enumeration query for Qqcore , and for each result 𝑖 enumerated for Qqcore with annotation 𝑤ℎ p𝑖q, if 𝑤ℎ p𝑖q ą 𝑤ℎ´1 p𝑖q, we set p𝑀𝑣ℎ q𝑖 “ 1; (5) repeat (3)-(4) for vector 𝑣ℎ`1 . If an index can be updated in 𝑂p𝑛 1´𝜖 q amortized time over insertion-only K-sequences while supporting 2 ¨ 𝑛 1´𝜖 q “ 𝑂p𝑛 3´𝜖 q 𝑂p𝑛 1´𝜖 q-delay enumeration, the OMv problem can be solved in 𝑂p𝑛 2 ¨ 𝑛 1´𝜖 ` 𝑛a 2 time. The construction above requires a database of size at most 𝑛 , thus 𝑛 ě |𝐷|. □ Over the tropical semiring, the same reduction simplifies further: instead of comparing the annotation of an output value against its previous one, the reduction tests it against the newest annotation, as max retains only the latest round. Lemma 3.6. For Qqcore over the tropical semiring pR Y t´8u, max, `, ´8, 0q and any constant 𝜖 ą 0, no index can be updated in 𝑂p|𝐷|1{2´𝜖 q amortized time over insertion-only K-sequences while supporting 𝑂p|𝐷|1{2´𝜖 q-delay enumeration, assuming the OMv conjecture. Proof. Given an OMv instance of dimension 𝑛, let 𝑎ℎ “ ℎ for every ℎ P r𝑛s. We encode the matrix 𝑀 by 𝑅1 , inserting a tuple p𝑖, 𝑗q with annotation 0 for each p𝑖, 𝑗q P r𝑛s ˆ r𝑛s with 𝑀𝑖 𝑗 ‰ 0, and the vectors by 𝑅2 : for vector 𝑣ℎ , we insert a tuple p𝑗q with annotation 𝑎ℎ for each 𝑗 P r𝑛s with 𝑣ℎ 𝑗 ‰ 0; re-inserting p𝑗q at round ℎ updates its annotation to the maximum of its previous annotation and 𝑎ℎ , which is 𝑎ℎ . We then issue the enumeration query and report the 𝑖-th entry of 𝑀𝑣ℎ as 1 if the output value 𝑖 is enumerated with annotation exactly 𝑎ℎ , and as 0 otherwise. For correctness, the annotation of the output value 𝑖 after round ℎ is ␣ ( max 𝑎𝑘 : 𝑘 P rℎs, D𝑗 such that 𝑀𝑖 𝑗 ‰ 0, 𝑣𝑘 𝑗 ‰ 0 ; since 𝑎 1 ă 𝑎 2 ă ¨ ¨ ¨ ă 𝑎𝑛 , it equals 𝑎ℎ if and only if the maximum is attained with 𝑘 “ ℎ, i.e., if and only if p𝑀𝑣ℎ q𝑖 “ 1. The cost analysis is the same as in Lemma 3.5. □ 4
Lower Bounds: General Results
Now, we move to lower bounds for general CQs and semirings, distilling the properties that make the constructions of Section 3 work over an arbitrary ordered semiring. Section 4.1 introduces the two concepts that these properties rest on, the bounded fragments and the order conditions of a semiring, and identifies the general conditions on an ordered semiring K under which the two hardness results hold. Finally, we lift the hardness of the two queries to every free-connex but non-strong-connex CQ, which completes the lower bound side of Theorem 1.1. 4.1
K-relations
We recall the algebraic model of annotated relations, following the semiring-provenance framework of Green et al. [21] and its extensions to aggregate queries [4, 30]. Recall from Section 1 the definitions of a commutative semiring K “ pK, ‘, b, 0, 1q and of the K-relations defined on top of it. Subsemirings and bounded fragments. A fragment of K “ pK, ‘, b, 0, 1q is a tuple pL, ‘, b, 0, 1q, where L Ď K with 0, 1 P L. A fragment is a subsemiring if L is closed under ‘ and b, i.e., for all 𝑣 1, 𝑣 2 P L, we must have 𝑣 1 ‘ 𝑣 2 P L and 𝑣 1 b 𝑣 2 P L. For 𝑛, 𝑚 P Zě1 , a value 𝑣 P K has an p𝑛, 𝑚q-representation over 𝐴 Ď K if 𝑣“
𝑛 â 𝑚 à 𝑖 “1 𝑗 “1
𝑠𝑖 𝑗 , where 𝑠𝑖 𝑗 P 𝐴 Y t0, 1u for all 𝑖 P r𝑛s, 𝑗 P r𝑚s.
(1)
Answering Conjunctive Queries with Aggregations under Updates
13
If 𝑛 “ 1, 𝑣 is essentially the b-aggregation over 𝑚 elements from 𝐴. We call such a value an 𝐴-product, and each participating element 𝑠 𝑗 is called a factor. Equivalently, such a value 𝑣 admits a representation as follows: 𝑣“
𝑛 à
𝑝𝑖 , where 𝑝𝑖 is an 𝐴-product with rank at most 𝑚 for all 𝑖 P r𝑛s.
(2)
𝑖 “1
Let 𝑐 1, 𝑐 2 P Zě1 Y t8u. A fragment pL, ‘, b, 0, 1q is p𝑐 1, 𝑐 2 q-bounded over 𝐴 if every 𝑣 P L has an p𝑛, 𝑚q-representation over 𝐴 for some 𝑛 ď 𝑐 1 and 𝑚 ď 𝑐 2 . We denote by 𝐴p𝑐 1,𝑐 2 q the maximum p𝑐 1, 𝑐 2 q-bounded fragment over 𝐴, whose domain is exactly the set of all values in K that have an p𝑛, 𝑚q-representation over 𝐴 with 𝑛 ď 𝑐 1 and 𝑚 ď 𝑐 2 . For 𝑣 P K, define 𝑛 ‘,𝑐 2 p𝑣q :“ min t𝑛 : 𝑣 has an p𝑛, 𝑚q-representation over 𝐴 for some 𝑚 ď 𝑐 2 u , and 𝑚 b,𝑐 1 p𝑣q :“ min t𝑚 : 𝑣 has an p𝑛, 𝑚q-representation over 𝐴 for some 𝑛 ď 𝑐 1 u . In particular, for every 𝑎 P 𝐴 Y t0, 1u, padding with 1-factors and 0-summands gives 𝑛 ‘,𝑐 2 p𝑎q “ 1
@𝑐 2 ě 1,
𝑚 b,𝑐 1 p𝑎q “ 1
@𝑐 1 ě 1.
Moreover, if 𝑣 is an 𝐴-product, then 𝑚 b,𝑐 1 p𝑣q is denoted as the rank of 𝑣; in other words, the smallest number of factors (either an identity element t0, 1u, or an element from 𝐴) required to form 𝑣. Example 4.1. Consider the bag semiring K “ pN, `, ˆ, 0, 1q and the subset 𝐴 “ t1, 2, 3, 4u Ď N. The maximum p2, 1q-bounded fragment over 𝐴 is 𝐴p2,1q “ pL, `, ˆ, 0, 1q with L “ t0, 1, 2, 3, 4, 5, 6, 7, 8u: its domain consists of the sums of any two elements of t0, 1, 2, 3, 4u. Now, consider the element 6 P L. We have 𝑛 `,2 p6q “ 1 since 6 has the p1, 2q-representation 6 “ 2 ˆ 3, and 𝑚 ˆ,2 p6q “ 1 since 6 has the p2, 1q-representation 6 “ 3 ` 3. The maximum p1, 2q-bounded fragment over 𝐴 is 𝐴p1,2q “ pM, `, ˆ, 0, 1q with M “ t0, 1, 2, 3, 4, 6, 8, 9, 12, 16u: its domain consists of the products of any two elements of t0, 1, 2, 3, 4u. Now, consider the element 7 P K. We have 𝑛 `,2 p7q “ 2 since 7 has the p2, 2q-representation 7 “ 3 ` 4, but no p1, 2q-representation. ř Finally, the domain of 𝐴p8,8q is exactly K, as every 𝑣 P N has the p𝑣, 1qrepresentation 𝑣 “ 𝑖 Pr𝑣 s 1. Example 4.2. Consider the tropical semiring K “ pN Y t´8u, max, `, ´8, 0q, where ‘ “ max and b “ `, and the set 𝐴 “ t1, 2, 3, 4u. It can be checked that 𝐴p𝑖,1q “ pL, max, `, ´8, 0q with L “ t´8, 0, 1, 2, 3, 4u for any 𝑖 P Zě1 , since the ‘-operator (max) never leaves the set of its operands. Similarly, 𝐴p𝑖,2q “ pM, max, `, ´8, 0q with M “ t´8, 0, 1, 2, 3, 4, 5, 6, 7, 8u for any 𝑖 P Zě1 . The domain of 𝐴p8,8q is exactly K, as every 𝑣 P N has the p1, 𝑣q-representation 𝑣 “ 1 b 1 b ¨ ¨ ¨ b 1 (𝑣 times, recalling that b is `). Orders. In this work, an ordered semiring K “ pK, ‘, b, 0, 1, ďq is a semiring equipped with a preorder ď on K. For a pair of elements 𝑎, 𝑏 P K, we write 𝑎 ă 𝑏 if 𝑎 ď 𝑏 and 𝑏 ď 𝑎. The order ď can be chosen as the natural preorder of the additive monoid, namely 𝑎 ďnat 𝑏
if and only if
D𝑐 P K such that 𝑎 ‘ 𝑐 “ 𝑏,
and a semiring is a naturally ordered semiring [19] if ďnat is antisymmetric, i.e, if 𝑎 ďnat 𝑏 and 𝑏 ďnat 𝑎 for 𝑎, 𝑏 P K, then 𝑎 “ 𝑏. All ordering assumptions below are stated with respect to the fixed preorder ď, which may or may not be ďnat . We require ď to be compatible with ‘ and b, namely 𝑎 ď 𝑏 implies 𝑎 ‘ 𝑐 ď 𝑏 ‘ 𝑐 for every 𝑎, 𝑏, 𝑐 P K, and 𝑎 ď 𝑏 implies 𝑎 b 𝑐 ď 𝑏 b 𝑐 for every 𝑎, 𝑏, 𝑐 P K with 𝑐 ą 0. This requirement is automatic when ď is the natural preorder.
14
Qichen Wang and Xiao Hu
A sequence 𝐴 “ p𝑎 1, . . . , 𝑎𝑘 q is called monotone if 0 ă 𝑎 1 ă 𝑎 2 ă ¨ ¨ ¨ ă 𝑎𝑘 . The semiring K is called 𝑘-monotone if it contains a monotone sequence of length 𝑘. We now define the bounded order conditions. Let 𝐴 “ p𝑎 1, . . . , 𝑎𝑘 q be a monotone sequence, and let 𝐴p𝑐 1,𝑐 2 q “ pL, ‘, b, 0, 1q be the maximum p𝑐 1, 𝑐 2 q-bounded fragment generated by the elements of 𝐴. Now, we can define ‘-strictly-ordered and b-strictly-ordered for 𝐴p𝑐 1,𝑐 2 q . ‚ The fragment 𝐴p𝑐 1,𝑐 2 q is b-strictly-ordered if replacing the strictly smallest factor of an 𝐴-product by an element of Â𝐴 that dominates all factors causes a strict increase. Consider a non-zero 𝐴-product 𝑝 “ 𝑚 𝑗 “1 𝑠 𝑗 with 2 ď 𝑚 ď 𝑐 2 . Let 𝑠𝑚 ă 𝑠 𝑗 for all 𝑗 ‰ 𝑚 wlog. Let 𝑎 P 𝐴 be an arbitrary value. If 𝑎 ě max 𝑗 Pr𝑚s 𝑠 𝑗 and 𝑎 ą 𝑠𝑚 , then ˜ ¸ 𝑚 ´1 â 𝑝ă 𝑠 𝑗 b 𝑎. 𝑗 “1
‚ The fragment 𝐴p𝑐 1,𝑐 2 q is ‘-strictly-ordered if a new 𝐴-product that strictly dominates all previous 𝐴-products causes a strict increase. Consider an arbitrary value 𝑣 P L. By definition, it admits the following representation for 𝑛 ď 𝑐 1 and 𝑚 ď 𝑐 2 : 𝑣“
𝑛 à
𝑝𝑖 , where 𝑝𝑖 is an 𝐴-product with rank at most 𝑚 for all 𝑖 P r𝑛s.
𝑖 “1
Let 𝑞 be an arbitrary 𝐴-product with rank at most 𝑐 2 . If 𝑛 ă 𝑐 1 , and 𝑞 ą t0, 𝑝 1, 𝑝 2, ¨ ¨ ¨ , 𝑝𝑛 u, then 𝑣 ă 𝑣 ‘ 𝑞. The condition 𝑛 ă 𝑐 1 ensures that 𝑣 ‘ 𝑞 P L. Throughout this paper, whenever the fragment 𝐴p𝑐 1,𝑐 2 q is assumed to be strictly-ordered, we additionally assume that every 𝐴-product is positive, i.e., strictly greater than 0 under the fixed preorder ď. Example 4.3. Consider the capped semiring K “ pt0, 1, . . . , 10u, ‘, b, 0, 1q, where 𝑎 ‘ 𝑏 “ minp10, 𝑎 ` 𝑏q
and
𝑎 b 𝑏 “ minp10, 𝑎 ˆ 𝑏q,
with the usual order on integers. Let 𝐴 “ p2, 3q. The 𝐴-products of rank at most 2 are t1, 2, 3, 4, 6, 9u, while 𝐴-products of rank at most 3 are t1, 2, 3, 4, 6, 8, 9, 10u, as, e.g., 2 b 2 b 3 “ minp12, 10q “ 10. Therefore, the domain of 𝐴p1,2q is t0, 1, 2, 3, 4, 6, 9u, the domain of 𝐴p2,1q is t0, 1, 2, 3, 4, 5, 6u, while the domain of 𝐴p2,2q , 𝐴p2,3q and 𝐴p3,2q all coincide with the domain of K. 𝐴p1,2q is b-strictly-ordered: for example, 2 b 2 “ 4 ă 6 “ 2 b 3 and 2 b 3 “ 6 ă 9 “ 3 b 3. On the other hand, 𝐴p1,3q is not b-strictly-ordered: 3 b 3 b 2 “ 10 “ 3 b 3 b 3. 𝐴p2,2q is ‘-strictly-ordered: for an arbitrary pair of 𝐴-products 𝑝, 𝑞 each with rank at most 2, if 𝑝 ă 𝑞, then 𝑝 ă minp10, 𝑝 ` 𝑞q “ 𝑝 ‘ 𝑞. On the other hand, 𝐴p3,2q is not ‘-strictly-ordered: for example, 6 ‘ 6 “ 10 “ 6 ‘ 6 ‘ 9. The following monotonicity property is immediate from the definitions, as every representation admissible for p𝑐 11 , 𝑐 21 q is also admissible for p𝑐 1, 𝑐 2 q: Proposition 4.4. Let 𝐴 “ p𝑎 1, . . . , 𝑎𝑘 q. If 𝐴p𝑐 1,𝑐 2 q is ‘-strictly-ordered, then for any 𝑐 11 ď 𝑐 1 and 1 𝑐 2 ď 𝑐 2 , the fragment 𝐴p𝑐 11 ,𝑐 21 q is ‘-strictly-ordered. 4.2
Maintaining Qhier and Qqcore over Ordered Semirings
The next theorem shows that the hardness of Qhier requires only a short monotone sequence, of length |𝐷|𝜂 for an arbitrarily small constant 𝜂 ą 0, at the price of a blocked reduction.
Answering Conjunctive Queries with Aggregations under Updates
15
Theorem 4.5. Let K “ pK, ‘, b, 0, 1, ďq be an ordered semiring that contains, for some constant 𝜂 ą 0, a monotone sequence 𝐴 of length |𝐷|𝜂 such that 𝐴p2|𝐷 |1`2𝜂 ,2q is both ‘-strictly-ordered and b-strictly-ordered. For any constant 𝜖 ą 0, no index for Qhier using 𝑂p|𝐷|1`𝜂 ´𝜖 q space can be updated in 𝑂p|𝐷|1{2´𝜖 q amortized time while supporting 𝑂p|𝐷|1´𝜖 q-delay enumeration over insertion-only K-sequences, assuming the OuMv conjecture. Remark. In Theorem 4.5, we add an additional requirement on the length of the monotone sequence with a space hypothesis. The idea is that one can simulate a hard instance by decomposing the inputs into different blocks, and for each block, one can refresh the entire maintained index via reloading the persistent initial database, which can be either the matrix/tensor (for the OMv/OuMv and generalized OuMv𝑘 problem) or graph (for the 𝑘-cycle detection problem). The space hypothesis is what makes this step affordable: for example, given an OMv/OuMv instance, the stored image has the size of the index itself, so each restore costs 𝑂p|𝐷|1`𝜂 ´𝜖 q, and the 𝑂p|𝐷|1{2´𝜂 q restores cost 𝑂p|𝐷|3{2´𝜖 q in total. If the index is required to use linear space, every restore takes linear time, and the space hypothesis holds automatically for 𝜖 ď 𝜂. If the space is unbounded, restoring by copying is no longer affordable, and the reduction would either rebuild each block by re-inserting the matrix part, at total cost 𝑂p|𝐷|2´𝜂 ´𝜖 q, which respects the budget only when 𝜂 ` 𝜖 ě 1{2, or avoid the blocks altogether, which requires a monotone sequence of length |𝐷|1{2 ; the latter is how Lemmas 3.2 and 3.3 proceed over the sum-product and the tropical semiring, with no space hypothesis. The same discussion applies to the blocked reduction of Lemma 4.15; Lemmas 4.13 and 4.14 need no blocks and no space hypothesis: their update sequences make a single pass over the vertices of the constructed graph, at most 𝑂p|𝐷|q of them, which a monotone sequence of length |𝐷| covers. Proof of Theorem 4.5. Let |𝐷| be a fixed parameter, such that we will define a dynamic database whose size is 𝑂p|𝐷|q. Given an OuMv instance of dimension 𝑛, let 𝐴 “ p𝑎 1, . . . , 𝑎𝑚 q be the monotone sequence, where 𝑚 “ |𝐷|𝜂 . We encode 𝑀, x𝑢ℎ y, and x𝑣ℎ y by 𝑅1 , 𝑅2 , and 𝑅3 , and maintain two databases with insertion-only K-sequences 𝑆 1 and 𝑆 2 , as in Lemma 3.2. We process the vector pairs in consecutive blocks, each of length at most 𝑚. At the beginning of each block, we reset the two databases: for both 𝑆 1 and 𝑆 2 , we insert the tuple p𝑖, 𝑗q into 𝑅1 with annotation 1 for every p𝑖, 𝑗q P r𝑛s ˆ r𝑛s with 𝑀𝑖 𝑗 ‰ 0. After the first initialization, we store an image of the resulting index, and reinitialize later blocks by restoring this image rather than recomputing the matrix part from scratch. Consider a block beginning with vector index 𝑔. We initialize 𝑤 0 “ 0. For the ℓ-th vector pair in this block, let ℎ “ 𝑔 ` ℓ ´ 1, where 1 ď ℓ ď 𝑚, and perform the same four steps as in Lemma 3.2, with all round-ℓ tuples inserted with annotation 𝑎 ℓ : obtain 𝑤ℎ1 (from 𝑆 1 , with only 𝑢ℎ inserted) and 𝑤ℎ2 (from 𝑆 2 , with only 𝑣ℎ inserted), complete the pair in both databases, and obtain 𝑤 ℓ from 𝑆 1 . We return true for the pair p𝑢ℎ , 𝑣ℎ q if 𝑤ℎ1 ‘ 𝑤ℎ2 ă 𝑤 ℓ ´1 ‘ 𝑤 ℓ , and false otherwise. If ℓ “ 𝑚 and there are still vector pairs to process, we reset both databases and start the next block. For correctness, call a quadruple p𝑖, 𝑗, ℓ 1, ℓ 2 q with ℓ 1, ℓ 2 P rℓs a witness if 𝑀𝑖 𝑗 ‰ 0, the 𝑢-vector of round ℓ 1 sets position 𝑖, and the 𝑣-vector of round ℓ 2 sets position 𝑗; its contribution is the product term 𝑎 ℓ 1 b 𝑎 ℓ 2 of rank 2. Each of the four compared values is the ‘-aggregate of the contributions of its visible witnesses: a witness with ℓ 1, ℓ 2 ď ℓ ´ 1 is visible to all four values; a witness with ℓ 1 “ ℓ and ℓ 2 ă ℓ is visible to 𝑤 ℓ and 𝑤ℎ1 ; a witness with ℓ 2 “ ℓ and ℓ 1 ă ℓ is visible to 𝑤 ℓ and 𝑤ℎ2 ; and a current witness, with ℓ 1 “ ℓ 2 “ ℓ, is visible only to 𝑤 ℓ . Writing r𝑃s for the indicator that
16
Qichen Wang and Xiao Hu
equals 1 if the condition 𝑃 holds and 0 otherwise, and ℎ ℓ 1 “ 𝑔 ` ℓ 1 ´ 1 for the global index of the ℓ 1 -th pair of the block, then ˜˜ ¸ ˜ ¸¸ 𝑠 𝑡 à à à “ ‰ “ ‰ 𝑊 p𝑠, 𝑡q “ 𝑎 ℓ 1 b 𝑢ℎℓ 1 ,𝑖 ‰ 0 b r𝑀𝑖 𝑗 ‰ 0s b 𝑎 ℓ 2 b 𝑣ℎℓ 2 ,𝑗 ‰ 0 𝑖,𝑗 Pr𝑛 s
ℓ 1 “1
ℓ 2 “1
for the value whose 𝑢-side has been inserted up to the 𝑠-th pair and whose 𝑣-side up to the 𝑡-th, the four compared values are 𝑤 ℓ “ 𝑊 pℓ, ℓq, 𝑤 ℓ ´1 “ 𝑊 pℓ ´ 1, ℓ ´ 1q, 𝑤ℎ1 “ 𝑊 pℓ, ℓ ´ 1q, and 𝑤ℎ2 “ 𝑊 pℓ ´ 1, ℓq. Hence, ` ˘ 𝑤 ℓ ´1 ‘ 𝑤 ℓ “ 𝑤ℎ1 ‘ 𝑤ℎ2 ‘ 𝑊 , where 𝑊 is the ‘-aggregate of the contributions of the current witnesses, each equal to 𝑎 ℓ b 𝑎 ℓ . A current witness exists if and only if 𝑢ℎT 𝑀𝑣ℎ ‰ 0. If no current witness exists, the two compared values are equal, and the test correctly returns false. Otherwise, let 𝑣 “ 𝑤ℎ1 ‘ 𝑤ℎ2 . Each of 𝑤ℎ1 and 𝑤ℎ2 is the ‘-aggregate of at most 𝑛 2𝑚p𝑚 ´ 1q product terms of rank 2 over 𝐴, and each of 𝑤 ℓ ´1 and 𝑤 ℓ of at most 𝑛 2𝑚 2 such terms; hence, both compared values, as well as 𝑣 ‘ p𝑎 ℓ b 𝑎 ℓ q, are ‘-aggregates of at most 2𝑛 2𝑚 2 “ 2|𝐷|1`2𝜂 product terms, and lie in the domain of 𝐴p2|𝐷 |1`2𝜂 ,2q . Consider any pℓ 1, ℓ 2 q ‰ pℓ, ℓq with ℓ 1, ℓ 2 ď ℓ and, without loss of generality, ℓ 1 ď ℓ 2 , so that ℓ 1 ă ℓ: the order compatibility gives 𝑎 ℓ 1 b𝑎 ℓ 2 ď 𝑎 ℓ 1 b𝑎 ℓ , and one application of the b-strict order, replacing the strictly smallest factor 𝑎 ℓ 1 , gives 𝑎 ℓ 1 b 𝑎 ℓ ă 𝑎 ℓ b 𝑎 ℓ . Hence the term 𝑎 ℓ b 𝑎 ℓ strictly dominates every term of 𝑣, and the ‘-strict order gives 𝑣 ă 𝑣 ‘ p𝑎 ℓ b 𝑎 ℓ q. Finally, the remaining current witnesses are positive, so 𝑣 ‘ p𝑎 ℓ b 𝑎 ℓ q ď 𝑣 ‘ 𝑊 , and the test correctly returns true. It remains to analyze the running time. Since |𝐷| “ 𝑂p𝑛 2 q and 𝑚 “ |𝐷|𝜂 , the number of blocks is r𝑛{𝑚s “ 𝑂p|𝐷|1{2´𝜂 q, and restoring the stored image of the index, whose size is 𝑂p|𝐷|1`𝜂 ´𝜖 q by the space hypothesis, costs 𝑂p|𝐷|1`𝜂 ´𝜖 q per block, for a total of 𝑂p|𝐷|1{2´𝜂 ¨ |𝐷|1`𝜂 ´𝜖 q “ 𝑂p|𝐷|3{2´𝜖 q. Across all blocks, the vector relations receive 𝑂p𝑛 2 q “ 𝑂p|𝐷|q insertions in total, which cost 𝑂p|𝐷| ¨ |𝐷|1{2´𝜖 q “ 𝑂p|𝐷|3{2´𝜖 q. The 𝑂p𝑛q “ 𝑂p|𝐷|1{2 q enumeration calls cost 𝑂p|𝐷|1´𝜖 q each, for a total of 𝑂p|𝐷|3{2´𝜖 q. Altogether, the OuMv instance is solved in 𝑂p|𝐷|3{2´𝜖 q “ 𝑂p𝑛 3´2𝜖 q time, contradicting the OuMv conjecture, as 𝜖 ą 0. □ Remark. Theorem 4.5 generalizes both reductions of tropical semirings and sum-product semirings, and its two order conditions reflect the structure of the witnesses. A witness of Qhier combines one contribution from each of the two per-round relations, so its term is a product of rank 2, and the reduction must tell the current witness, whose two factors are both maximal, apart from a witness that reuses an older round in one factor. The b-strict order provides exactly this separation: it asks the product to be sensitive to its smallest factor, so that 𝑎 ℓ b 𝑎 ℓ strictly exceeds every mixed term, and the ‘-strict order then lifts the separation from single terms to the compared aggregates. The result can further extend to semirings whose product is min, such as the fuzzy semiring pr0, 1s, max, min, 0, 1q. However, we have identified a max-max semiring (Section 1) sits on the other side of this line: a product maxp𝑎, 𝑏q is insensitive to its smaller factor, so the b-strictly ordered condition failed. Detailed analysis and matching optimal upper bound can be found in Section 5.3. We next turn to Qqcore , whose hardness is established by a similar construction from the OMv conjecture. As the query has an output attribute, no second database is needed: the reduction reads off the changes of the annotations of individual output values. Theorem 4.6. Let K “ pK, ‘, b, 0, 1, ďq be an ordered semiring that contains, for some constant 𝜂 ą 0, a monotone sequence 𝐴 of length |𝐷|𝜂 such that 𝐴p|𝐷 |1{2`𝜂 ,1q is ‘-strictly-ordered. For any constant 𝜖 ą 0, no index for Qqcore using 𝑂p|𝐷|1`𝜂 ´𝜖 q space can be updated in 𝑂p|𝐷|1{2´𝜖 q amortized
Answering Conjunctive Queries with Aggregations under Updates
17
time while supporting 𝑂p|𝐷|1{2´𝜖 q-delay enumeration over insertion-only K-sequences, assuming the OMv conjecture. Proof. Let |𝐷| be a fixed parameter, such that we will define a dynamic database whose size is 𝑂p|𝐷|q. Let 𝐴 “ p𝑎 1, ¨ ¨ ¨ , 𝑎𝑚 q be the monotone sequence, where 𝑚 “ |𝐷|𝜂 . Given an OMv instance of dimension 𝑛, we encode the matrix 𝑀 by relation 𝑅1 and the vectors x𝑣ℎ : ℎ P r𝑛sy by relation 𝑅2 . We process the vectors in consecutive blocks, each of length at most 𝑚. At the beginning of each block, we reset the database: we insert the tuple p𝑖, 𝑗q into 𝑅1 with annotation 1 for every p𝑖, 𝑗q P r𝑛s ˆ r𝑛s with 𝑀𝑖 𝑗 ‰ 0, reusing the snapshot of the index as in the proof of Theorem 4.5. Consider a block beginning with vector index 𝑔, and initialize 𝑤 0 r𝑖s “ 0 for every 𝑖 P r𝑛s. For the ℓ-th vector in this block, let ℎ “ 𝑔 ` ℓ ´ 1, where 1 ď ℓ ď 𝑚, and perform the following: ‚ insert the tuple p𝑗q into 𝑅2 with annotation 𝑎 ℓ for every 𝑗 P r𝑛s with 𝑣ℎ 𝑗 ‰ 0; ‚ issue the enumeration query for Qqcore , and let 𝑤 ℓ r𝑖s be the annotation of the output value 𝑖, where 𝑤 ℓ r𝑖s “ 0 if 𝑖 is not enumerated. We report the 𝑖-th entry of 𝑀𝑣ℎ as 1 if 𝑤 ℓ ´1 r𝑖s ă 𝑤 ℓ r𝑖s, and as 0 otherwise. If ℓ “ 𝑚 and there are still vectors to process, we reset the database and start the next block. For correctness, fix an output value 𝑖. The annotation 𝑤 ℓ r𝑖s is the ‘-aggregate of the contributions of the witnesses p𝑗, ℓ 1 q with ℓ 1 P rℓs, 𝑀𝑖 𝑗 ‰ 0, and the vector of round ℓ 1 setting position 𝑗; each contribution is the rank-1 product term 𝑎 ℓ 1 , and there are at most 𝑛𝑚 “ |𝐷|1{2`𝜂 of them, and at most 𝑛p𝑚 ´ 1q for 𝑤 ℓ ´1 r𝑖s; hence, all values involved, including 𝑤 ℓ ´1 r𝑖s ‘ 𝑎 ℓ , lie in the domain of 𝐴p|𝐷 |1{2`𝜂 ,1q . As before, 𝑤 ℓ r𝑖s “ 𝑤 ℓ ´1 r𝑖s ‘ 𝑊ℓ r𝑖s, where 𝑊ℓ r𝑖s aggregates the contributions of the current witnesses, each equal to 𝑎 ℓ . A current witness exists if and only if the 𝑖-th entry of 𝑀𝑣ℎ is 1. If no current witness exists, then 𝑤 ℓ r𝑖s “ 𝑤 ℓ ´1 r𝑖s, and we correctly report 0. Otherwise, 𝑎 ℓ strictly dominates every term 𝑎 ℓ 1 with ℓ 1 ă ℓ of 𝑤 ℓ ´1 r𝑖s, so the ‘-strict order gives 𝑤 ℓ ´1 r𝑖s ă 𝑤 ℓ ´1 r𝑖s ‘ 𝑎 ℓ , and 𝑤 ℓ ´1 r𝑖s ‘ 𝑎 ℓ ď 𝑤 ℓ r𝑖s by compatibility, as the remaining current witnesses are positive; we correctly report 1. For the running time, the number of blocks is 𝑂p|𝐷|1{2´𝜂 q, and restoring the stored image of the index costs 𝑂p|𝐷|1`𝜂 ´𝜖 q per block by the space hypothesis; the vector relations receive 𝑂p𝑛 2 q “ 𝑂p|𝐷|q insertions in total; and each of the 𝑂p𝑛q enumeration calls returns at most 𝑛 results with 𝑂p|𝐷|1{2´𝜖 q delay. As in the proof of Theorem 4.5, the total cost is 𝑂p|𝐷|3{2´𝜖 q “ 𝑂p𝑛 3´2𝜖 q, contradicting the OMv conjecture, as 𝜖 ą 0. □ Remark. The precondition of Theorem 4.6 is weaker than that of Theorem 4.5: the condition on b disappears. By Proposition 4.4, every semiring satisfying the conditions of Theorem 4.5 also satisfies those of Theorem 4.6; but not vice versa. For example, the max-max semiring is only ‘-strictly-ordered but not b-strictly-ordered. Hence, it fails to satisfy the condition in Theorem 4.5, maintaining Qhier over the insertion-only sequences defined by max-max semiring is not necessarily hard. Later in Section 5, we actually show that Qhier can be maintained in 𝑂p1q amortized time on the insertion-only sequences defined by the max-max semiring. But, in general, it is unknown whether Qhier can be maintained over insertion-only sequences only characterized by the precondition of Theorem 4.6 instead of Theorem 4.5. 4.3
Extensions to Non-Strong-Connex CQs
We now lift the hardness of Qhier and Qqcore to every free-connex but non-strong-connex CQ. The generalization has two ingredients. First, a structural lemma shows that every such CQ embeds one of two hard structures, each mirroring one of the two hard queries. Second, a reduction shows that any CQ containing an D-hierarchy-core (resp. a q-core) can simulate the maintenance of Qhier (resp. Qqcore ): the update sequences of the hard query are translated, relation by relation, into update
18
Qichen Wang and Xiao Hu
Table 3. Hardness landscape for free-connex but non-strong-connex CQs under varying semiring orderings.
with a monotone sequence 𝐴 of length |𝐷|𝜂 such that 𝐴p2|𝐷 |1`2𝜂 ,2q is ‘-strictly-ordered 𝐴p|𝐷 |1{2`𝜂 ,1q is ‘-strictly-ordered and b-strictly-ordered with D-hierarchy-core with q-core
hard hard
open, some semirings are easy hard
sequences of Q, with the annotations preserved. Together with Theorems 4.5 and 4.6, we obtain the hardness landscape for general non-free-connex queries. Theorem 4.7. Let K be an ordered semiring that contains, for some constant 𝜂 ą 0, a monotone sequence 𝐴 of length |𝐷|𝜂 such that 𝐴p2|𝐷 |1`2𝜂 ,2q is both ‘-strictly-ordered and b-strictly-ordered. For any CQ Q that contains an D-hierarchy-core, and any constant 𝜖 ą 0, no index for Q using 𝑂p|𝐷|1`𝜂 ´𝜖 q space can be updated in 𝑂p|𝐷|1{2´𝜖 q amortized time while supporting 𝑂p|𝐷|1{2´𝜖 q-delay enumeration over insertion-only K-sequences, assuming the OuMv conjecture. Theorem 4.8. Let K be an ordered semiring that contains, for some constant 𝜂 ą 0, a monotone sequence 𝐴 of length |𝐷|𝜂 such that 𝐴p|𝐷 |1{2`𝜂 ,1q is ‘-strictly-ordered. For any CQ Q that contains a q-core, and any constant 𝜖 ą 0, no index using 𝑂p|𝐷|1`𝜂 ´𝜖 q space can be updated in 𝑂p|𝐷|1{2´𝜖 q amortized time while supporting 𝑂p|𝐷|1{2´𝜖 q-delay enumeration over insertion-only K-sequences, assuming the OMv conjecture. Recall Proposition 4.4: if there exist a monotone sequence 𝐴 of length |𝐷|𝜂 such that 𝐴p2|𝐷 |1`2𝜂 ,2q is ‘-strictly-ordered, then 𝐴p|𝐷 |1{2`𝜂 ,1q is also ‘-strictly-ordered. Hence, these two theorems together establish the following corollary: Corollary 4.9. Let K be an ordered semiring that contains, for some constant 𝜂 ą 0, a monotone sequence 𝐴 of length |𝐷|𝜂 such that 𝐴p2|𝐷 |1`2𝜂 ,2q is both ‘-strictly-ordered and b-strictly-ordered. For any free-connex but non-strong-connex CQ Q, and any constant 𝜖 ą 0, no index for Q using 𝑂p|𝐷|1`𝜂 ´𝜖 q space can be updated in 𝑂p|𝐷|1{2´𝜖 q amortized time while supporting 𝑂p|𝐷|1{2´𝜖 q-delay enumeration over insertion-only K-sequences, assuming the OuMv and OMv conjectures. Remark. Specifically, the sum-product semiring admits a monotone sequence of the required length whose bounded fragments are both ‘-strictly-ordered and b-strictly-ordered. Thus, Theorem 4.9 instantiates the lower bound for every free-connex but non-strong-connex query, completing the lower-bound side of the dichotomy in Theorem 1.1. In contrast, the max-max semiring contains a monotone sequence whose bounded fragments are ‘-strictly-ordered but not b-strictly-ordered; hence, hardness over the max-max semiring only holds for queries containing the q-core. Lastly, because the Boolean semiring has no monotone sequence of length greater than one, neither lower bound applies, meaning free-connex but non-strong-connex queries remain efficiently maintainable under insertion-only sequences. 4.4
Extensions to Larger Heights and Dimensions
The lower bounds of Theorems 4.5 and 4.6 can be strengthened for queries that are structurally larger than the two hard queries. Following the parameterized analysis of the Boolean setting in [42], we measure a free-connex CQ along two axes – height and dimension. We first introduce the height of a generalized free-connex join tree. The height of T is the maximum number of input relations on any leaf-to-root path, not counting generalized relations. The existence of generalized relations aims to remove the strict layering of the tree: if 𝑒 1 and 𝑒 2 share the same join key, then
Answering Conjunctive Queries with Aggregations under Updates
19
𝑒 1 and 𝑒 2 may be placed at the same level as two child nodes of a generalized relation r𝑒 1 X 𝑒 2 s, reducing the height of the join tree. The height of a free-connex CQ is the minimum height over all its free-connex join trees; it captures how far the query scales out by chaining more relations, and the q-hierarchical CQs are exactly the CQs of height 1 [27, 44]. The dimension of a CQ, in contrast, captures how far the query scales up by placing more join attributes and output attributes into a single relation; for instance, the star query 𝑄𝑑 below has dimension 𝑑, while a query has dimension 1 if and only if it is q-hierarchical [42]. We refer to [42] for the formal definitions as they are not required to understand the given results; in this subsection, we exhibit two concrete families of queries whose maintenance over annotated relations admits lower bounds strictly above |𝐷|1{2 , for different heights and dimensions, while we do not claim such bounds for every query of a given height or dimension; a full parameterized classification of annotated CQs, in the spirit of [42], is left as future work. The results of this subsection rest on two additional conjectures. The first one concerns combinatorial algorithms, i.e., algorithms that do not rely on fast matrix multiplication: Conjecture 4.10 (Combinatorial 𝑘-Cliqe Conjecture [1]). For any integer 𝑘 ě 3 and any 𝜖 ą 0, no combinatorial algorithm can detect a 𝑘-clique in a graph with 𝑛 vertices in 𝑂p𝑛𝑘 ´𝜖 q time. The conjecture connects to our path queries through the 𝑘-cycle detection problem: given a directed graph 𝐺 “ p𝑉 , 𝐸q with 𝑛 vertices and 𝑚 edges, decide whether 𝐺 contains a cycle of 𝑘 distinct vertices. Lincoln and Vyas [34] proved conditional lower bounds for this problem on sparse graphs: Theorem 4.11 ([34], Theorem 15 and Corollary 16). Assuming the Combinatorial 𝑘-Clique Conjecture, for any constant 𝜖 ą 0, no combinatorial algorithm can detect a 𝑘-cycle in a directed graph with 𝑚 edges in 𝑂p𝑚 2𝑘 {p𝑘 `1q´𝜖 q time for odd 𝑘 ě 3 with 𝑚 “ 𝑛 1`2{p𝑘 ´1q , nor in 𝑂p𝑚 p2𝑘 ´2q{𝑘 ´𝜖 q time for even 𝑘 ě 4 with 𝑚 “ 𝑛𝑘 {p𝑘 ´2q . The restriction to sparse graphs is essential in our setting, as the maintenance complexity is measured by the input size |𝐷| rather than the domain size. The proof sketch of Lemma 4.13 below decides, for every node of such a graph, whether the node lies on a 𝑘-cycle, and thereby inherits this hardness; we refer to [42] for the full reduction. The fragments in the hypotheses of the two lemmas below are determined by the maximum number of colored paths in a sparse graph: every maintained annotation aggregates one summand over 𝐴 per colored path and round, and the number of colored paths is at most the product of the color class sizes, maximized by classes of equal size at p𝑛{p𝑘 ´ 1qq𝑘 ´1 . The full counting is given in Appendix B. The second conjecture generalizes the OuMv problem from matrices to tensors, as proposed by Jin and Xu [29]: given a Boolean tensor 𝑀 of size 𝑛𝑘 and, in each round, 𝑘 Boolean vectors 𝑢 p1q, ¨ ¨ ¨ , 𝑢 p𝑘 q of dimension 𝑛, the task is to decide whether 𝑢 p1q ˆ ¨ ¨ ¨ ˆ 𝑢 p𝑘 q has a non-empty p𝑗q intersection with 𝑀, i.e., whether 𝑀𝑖 1,¨¨¨ ,𝑖𝑘 “ 1 for some indices with 𝑢𝑖 𝑗 “ 1 for every 𝑗 P r𝑘s, before the next round of vectors arrives. Conjecture 4.12 (OuMv𝑘 Conjecture [29]). For any 𝛾, 𝜖 ą 0, no algorithm can solve the OuMv𝑘 problem with 𝑛𝛾 rounds in 𝑂p𝑛𝛾 `𝑘 ´𝜖 q total time, even after polyp𝑛q-time preprocessing of the tensor. We first scale out Qhier into a path family of 𝑘 relations, whose height is ℎ “ r𝑘{2s; Figure 4 illustrates the two reductions of this subsection. Lemma 4.13. Let K be an ordered semiring that contains a monotone sequence 𝐴 of length |𝐷| such that 𝐴p2|𝐷 |p𝑘 `1qpℎ´1q{ℎ ,2q is both ‘-strictly-ordered and b-strictly-ordered, and let 𝑄𝑘 “ 𝜋H p𝑅1 p𝑥 1 q 1 𝑅2 p𝑥 1, 𝑥 2 q 1 ¨ ¨ ¨ 1 𝑅𝑘 ´1 p𝑥𝑘 ´2, 𝑥𝑘 ´1 q 1 𝑅𝑘 p𝑥𝑘 ´1 qq
20
Qichen Wang and Xiao Hu
(a) 𝑅1 : 𝑎ℓ
𝑅𝑘 ´1
𝑅3
𝑅2
¨¨¨
𝑣 𝐿0 𝐿1
𝐿𝑘 ´1
𝐿2 𝑅𝑘 : 𝑎 ℓ
(b)
𝐿ℎ (output 𝑥 1 )
𝑢 𝐿ℎ`1
.. backward copy . (edges reversed) 𝑅ℎ Ð out-neighbors of 𝑣
forward copy 𝑅ℎ Ð in-neighbors of 𝑣
.. .
𝐿1 𝐿2ℎ´1 𝑎ℓ
𝑣
𝑎ℓ
𝐿0
Fig. 4. The reductions of Lemma 4.13 (a) and Lemma 4.14 (b) on a colored graph. Solid edges are inserted up front with annotation 1; dashed edges are inserted in rounds, carrying the monotone annotation 𝑎 ℓ of the current vertex 𝑣 P 𝐿0 . In (a), the endpoint relations 𝑅1 and 𝑅𝑘 of the nullary 𝑄𝑘 receive the out- and in-neighbors of 𝑣, in two databases with opposite insertion orders. In (b), every layered 2ℎ-cycle through 𝑣 is split at 𝑣 and at the antipodal meeting vertex 𝑢 into two halves of ℎ edges, each maintained by one copy of Qℎ exposing 𝑢 as the output value: 𝑣 lies on a layered 2ℎ-cycle if and only if some output value increases strictly in both copies.
be evaluated over K. For any constant 𝜖 ą 0, no combinatorial algorithm can maintain 𝑄𝑘 in 𝑂p|𝐷|pℎ´1q{ℎ´𝜖 q amortized time while supporting 𝑂p|𝐷|1´𝜖 q-delay enumeration over insertion-only K-sequences, where ℎ “ r𝑘{2s, assuming the Combinatorial 𝑘-Clique Conjecture. Proof sketch. We adapt the construction of [42]. The input graph is colored, partitioned, and inserted into 𝑅2, ¨ ¨ ¨ , 𝑅𝑘 ´1 up front, with every tuple annotated by 1. We sort the nodes and process them one by one. For the ℓ-th node 𝑣, we insert the tuple p𝑢q into 𝑅1 for every edge p𝑣, 𝑢q P 𝐸, and the tuple p𝑢q into 𝑅𝑘 for every edge p𝑢, 𝑣q P 𝐸, all with annotation 𝑎 ℓ ; as in the proof of Theorem 4.5, we maintain two copies of the database that receive the insertions into 𝑅1 and 𝑅𝑘 in opposite orders. Let 𝑤 ℓ ´1 be the annotation before the insertions of 𝑣, let 𝑤 ℓ1 and 𝑤 ℓ2 be the annotations of the two copies after their respective first rounds, and let 𝑤 ℓ be the annotation after all insertions of 𝑣. Then, 𝑣 lies on at least one cycle of length 𝑘 if and only if 𝑤 ℓ1 ‘ 𝑤 ℓ2 ă 𝑤 ℓ ´1 ‘ 𝑤 ℓ , by the same witness-counting argument as before. The vertices of such a cycle are made pairwise distinct by color-coding [6], and balancing the cost of the reduction against the cycle-detection bounds of Theorem 4.11 rules out combinatorial maintenance in 𝑂p|𝐷|pℎ´1q{ℎ´𝜖 q amortized update time. The full reduction is given in Appendix B. □ Similarly, Theorem 4.6 extends to path queries with one output attribute:
Answering Conjunctive Queries with Aggregations under Updates
21
Lemma 4.14. Let K be an ordered semiring that contains a monotone sequence 𝐴 of length |𝐷| such that 𝐴p|𝐷 |ℎ´1,1q is ‘-strictly-ordered, and let Qℎ “ 𝜋𝑥 1 p𝑅1 p𝑥 1, 𝑥 2 q 1 𝑅2 p𝑥 2, 𝑥 3 q 1 ¨ ¨ ¨ 1 𝑅ℎ p𝑥ℎ qq
be evaluated over K. For any constant 𝜖 ą 0, no combinatorial algorithm can maintain Qℎ in 𝑂p|𝐷|pℎ´1q{ℎ´𝜖 q amortized time while supporting 𝑂p|𝐷|1{ℎ´𝜖 q-delay enumeration over insertion-only K-sequences, assuming the Combinatorial 𝑘-Clique Conjecture. Proof sketch. The query Qℎ is the height-ℎ analogue of Qqcore : for ℎ “ 2 it is Qqcore itself. The reduction combines the color-coded cycle encoding of Lemma 4.13 with the per-output-value read-off of Theorem 4.6. To detect 2ℎ-cycles, we split every candidate cycle at the current vertex 𝑣 and at the meeting vertex antipodal to it into two walks of ℎ edges each, and maintain one copy of Qℎ per half, both exposing the meeting vertex as the output attribute 𝑥 1 [42]. The internal relations 𝑅1, ¨ ¨ ¨ , 𝑅ℎ´1 of each copy hold the colored edges of its half with annotation 1; for the ℓ-th vertex 𝑣, 𝑅ℎ of one copy receives the in-neighbors of 𝑣, and the other receives the out-neighbors of 𝑣, all annotated 𝑎 ℓ . An output value whose annotation strictly increases in both copies is exactly a meeting vertex of a colored 2ℎ-cycle through 𝑣, and the ‘-strict order reads these increases off the enumeration, exactly as Theorem 4.6 reads 𝑀𝑣ℎ off the output values of Qqcore . The full reduction is given in Appendix B. □ Next, we scale up Qhier by increasing the arity of the middle relation. Applying the OuMv𝑘 Conjecture, we obtain a parameterized hardness result based on the dimension 𝑑 of the query: Lemma 4.15. Let K be an ordered semiring that contains, for some constant 𝜂 ą 0, a monotone sequence 𝐴 of length |𝐷|𝜂 such that 𝐴p2𝑑 ´1 |𝐷 |1`𝑑𝜂 ,𝑑 q is both ‘-strictly-ordered and b-strictly-ordered, and let 𝑄𝑑 “ 𝜋H p𝑅1 p𝑥 1, 𝑥 2, ¨ ¨ ¨ , 𝑥𝑑 q 1 𝑅2 p𝑥 1 q 1 𝑅3 p𝑥 2 q 1 ¨ ¨ ¨ 1 𝑅𝑑 `1 p𝑥𝑑 qq
be evaluated over K. For any constant 𝜖 ą 0, no index using 𝑂p|𝐷|1`𝜂 ´𝜖 q space can be updated in 𝑂p|𝐷|p𝑑 ´1q{𝑑 ´𝜖 q amortized time while supporting 𝑂p|𝐷|1´𝜖 q-delay enumeration over insertion-only K-sequences, assuming the OuMv𝑘 Conjecture with 𝑘 “ 𝑑.
Proof sketch. We reduce from OuMv𝑑 , encoding the tensor in 𝑅1 and the 𝑗-th vector stream in 𝑅 𝑗 `1 . A witness pairs a nonzero tensor entry with, for each coordinate 𝑗, a round ℓ 𝑗 whose vector sets that coordinate, and contributes the rank-𝑑 term 𝑎 ℓ1 b ¨ ¨ ¨ b 𝑎 ℓ𝑑 to the annotation of 𝑄𝑑 ; a round is a true answer exactly when it creates an all-current witness, one with ℓ1 “ ¨ ¨ ¨ “ ℓ𝑑 “ ℓ. Isolating the all-current witnesses calls for an inclusion–exclusion over which of the 𝑑 current updates have been applied. We keep one database per subset 𝑇 Ď r𝑑s, applying the round-ℓ update of the vectors in 𝑇 before reading its annotation 𝑓 p𝑇 q and the rest afterwards, so a witness with current coordinates 𝑝 “ t𝑗 : ℓ 𝑗 “ ℓu is visible to 𝑓 p𝑇 q iff 𝑝 Ď 𝑇 . In the comparison à à 𝑓 p𝑇 q ‰ 𝑓 p𝑇 q, 𝑇 : |𝑇 | even
𝑇 : |𝑇 | odd
a witness with 𝑝 ‰ r𝑑s cancels, as r𝑑sz𝑝 has equally many even- and odd-sized subsets, while an all-current witness (𝑝 “ r𝑑s) survives on the side of parity 𝑑; the strict inequality then follows from the order argument of Theorem 4.5. For 𝑑 “ 3 (see Figure 5), the even side is 𝑓 pHq ‘ 𝑓 pt1, 2uq ‘ 𝑓 pt1, 3uq ‘ 𝑓 pt2, 3uq and the odd side 𝑓 pt1uq ‘ 𝑓 pt2uq ‘ 𝑓 pt3uq ‘ 𝑓 pt1, 2, 3uq: for example, a witness with 𝑝 “ t1u is visible twice on each side, a witness with 𝑝 “ t1, 2u once on each side, and a witness with 𝑝 “ H, i.e., the query results before conducting any updates in the current round, is visible four times on each side, so all
22
Qichen Wang and Xiao Hu t1, 2, 3u t1, 2u
t1, 3u
t2, 3u
t1u
t2u
t3u
H
Fig. 5. The 2𝑑 databases of Lemma 4.15 for 𝑑 “ 3, one per subset 𝑇 Ď r𝑑s of the vector updates applied before reading 𝑓 p𝑇 q. Shaded subsets form the even side of the comparison, unshaded ones the odd side. A witness with current pattern 𝑝 is visible to 𝑓 p𝑇 q if and only if 𝑝 Ď 𝑇 , so for 𝑝 ‰ r𝑑s it is counted equally often on both sides; only an all-current witness (𝑝 “ r𝑑s), visible to 𝑓 pt1, 2, 3uq alone (thick border), breaks the equality.
cancel; only the all-current witness (𝑝 “ t1, 2, 3u), visible to 𝑓 pt1, 2, 3uq only, survives and breaks the equality. The full proof is in Appendix B. □ 5
Upper Bounds
In this section, we revisit the data structure of CROWN [44] and show how to adapt it to maintain annotations. The resulting upper bound matches the lower bound in Theorem 1.1 for the insertiononly setting. 5.1
CROWN Revisited
For dynamic evaluation, several upper-bound algorithms [28, 44, 45] follow a common design. They maintain a partially reduced representation over a free-connex join tree in a bottom-up manner, and then use this representation to support 𝑂p1q-delay enumeration of the query answers. Dynamic Yannakakis [28] already supports conjunctive queries over K-relations. However, for nonq-hierarchical queries, its update time can be 𝑂p|𝐷|q, even under insertion-only update sequences for strong-connex queries. We therefore adapt the CROWN framework [44] to annotated relations. The advantage of CROWN is that it replaces materialized join views by semi-join, intersection, and projection views. This avoids materializing polynomial-size intermediate joins. For the Boolean semiring, CROWN maintains free-connex queries in amortized 𝑂p1q time over all insertion-only update sequences, while still supporting 𝑂p1q-delay enumeration. This improves over Dynamic Yannakakis in the non-q-hierarchical free-connex case. We first recall the Boolean version of CROWN. Let T be a free-connex join tree. For each node 𝑅p𝑒q of T , CROWN maintains two views: a semi-join view 𝑉𝑠 p𝑅q and a projection view 𝑉𝑝 p𝑅q. For a leaf node, 𝑉𝑠 p𝑅q “ 𝑅. For an internal node, let 𝐶p𝑅q denote the set of children of 𝑅p𝑒q in T . If 𝑅p𝑒q is an input relation, then 𝑉𝑠 p𝑅q “ 𝑅p𝑒q
𝑉𝑝 p𝑅𝑐 q.
⋉ @𝑅𝑐 p𝑒𝑐 qP𝐶 p𝑅 q
If 𝑅p𝑒q is a generalized relation, then č 𝑉𝑠 p𝑅q “
𝑉𝑝 p𝑅𝑐 q, @𝑅𝑐 p𝑒𝑐 qP𝐶 p𝑅 q
which is well-defined whenever all children of 𝑒 have a join key exactly 𝑒, which is required for generalized relations on a generalized join tree. The projection view is the projection of the semi-join view onto the join key with the parent, i.e., 𝑉𝑝 p𝑅q “ 𝜋 keyp𝑒 q𝑉𝑠 p𝑅q.
Answering Conjunctive Queries with Aggregations under Updates
23
In the Boolean setting, updates are propagated only when the support of a view changes. For each projection view 𝑉𝑝 p𝑅q, CROWN maintains a counter 𝑐r𝑡s for every tuple 𝑡 P 𝑉𝑝 p𝑅q, where 𝑐r𝑡s records how many tuples of 𝑉𝑠 p𝑅q are projected to 𝑡. An insertion into 𝑉𝑝 p𝑅q is propagated only when 𝑐r𝑡s changes from 0 to 1, and a deletion is propagated only when 𝑐r𝑡s changes from 1 to 0. Thus, changes to multiplicities that do not change the Boolean support are not propagated. A direct annotated version of this algorithm would replace Boolean relations by K-relations and would maintain all views with their annotations. This is the standard approach in static evaluation. For a free-connex query 𝑄 over K-relations, the annotated query result can be computed in 𝑂p|𝐷| ` |Qp𝐷q|q time by first constructing a partial reducer along a free-connex join tree and then computing annotations during enumeration [30, 43]. More concretely, the reduction phase follows the same intuition as Yannakakis’ algorithm. Subtrees that contain no output attributes are absorbed into their parent: they are projected to the shared key, and their annotations are multiplied into the parent relation by b. The remaining relations are then reduced by semi-joins from the leaves to the root. These semi-joins remove tuples that cannot be included in any full result while preserving the annotations of the remaining tuples. Finally, non-output attributes are projected away, and annotations of tuples that collapse to the same output tuple are aggregated by ‘. After this reduction, the query becomes a full join over the partially reduced relations. Since the query is free-connex, this full join can be evaluated in linear time 𝑂p|𝐷| ` |Qp𝐷q|q, or enumerated with constant delay. The annotation of each output tuple is obtained by the standard K-relation semantics: annotations are multiplied by b along joins, and the necessary ‘-aggregation has already been performed during the reduction phase. However, directly maintaining all annotated views dynamically does not preserve the update cost as in the Boolean case. The semi-join operation used by CROWN is annotation-free: it checks whether matching tuples exist in the child projection view, but it does not propagate their annotations. There is, however, an important class of semirings, including the Boolean semiring, for which this propagation is still harmless: the naturally ordered semirings in which every monotone sequence has length 𝑂p1q. Lemma 5.1. Let K “ pK, ‘, b, 0, 1q be a naturally ordered semiring in which every monotone sequence has length 𝑂p1q, and let Q be a free-connex CQ evaluated over K. Q can be maintained in amortized 𝑂p1q time over insertion-only update sequences, while supporting 𝑂p1q-delay enumeration. Proof. We maintain all CROWN views together with their annotations. Since K is positive, under an insertion-only sequence, the annotation of any fixed tuple in any view evolves only by 𝑤 Ð 𝑤 ‘ 𝛿 for various 𝛿 ą 0, so its successive values are non-decreasing under the natural order, and its successive distinct values form a monotone sequence. By assumption, this occurs 𝑂p1q times throughout the entire sequence. Hence, each update triggers only 𝑂p1q additional annotated propagations beyond the support changes, and the latter are handled by the Boolean CROWN in amortized 𝑂p1q time [44]. □ Remark. Here, we require the semiring to be naturally ordered, as the proof relies on antisymmetry. This hypothesis cannot be dropped, even though all semirings under consideration are positive. Consider the odd-even semiring, the quotient of pN, `, ˆ, 0, 1q that identifies all odd numbers into a single class 𝑜 and all even numbers at least 2 into a single class 𝑒: its domain is t0, 𝑜, 𝑒u with 1 “ 𝑜, and 𝑜 ‘ 𝑜 “ 𝑒, 𝑜 ‘ 𝑒 “ 𝑜, 𝑒 ‘ 𝑒 “ 𝑒, 𝑜 b 𝑜 “ 𝑜, 𝑜 b 𝑒 “ 𝑒 b 𝑒 “ 𝑒. It is positive, since classes of numbers at least 1 never sum or multiply to 0, and every monotone sequence has length 𝑂p1q: any compatible order placing 0 strictly below 𝑜 forces 𝑜 ď 𝑒 ď 𝑜, so t𝑜, 𝑒u contains no strict pair. Yet it is not naturally ordered – the same cycle 𝑜 ďnat 𝑒 ďnat 𝑜 violates
24
Qichen Wang and Xiao Hu
anti-symmetry – and the counting argument above collapses: re-inserting a tuple flips its annotation between 𝑜 and 𝑒, so a single view tuple can change its annotation on every update, and the number of annotated propagation is no longer bounded by the length of monotone sequences. This failure is not an artifact of our proof. Annotations over this semiring carry the parity of the number of insertions, and the cancellation of a ring reappears one level up: re-inserting a tuple retires it, since any witness with an 𝑒-annotated factor contributes 𝑒, and such contributions never affect whether the ‘-aggregate is 𝑜 or 𝑒. Maintaining Qhier under insertion-only sequences then reports, in every round, whether the number of live witnesses is odd – an online vector-matrix-vector product over F2 – so amortized 𝑂p1q update time with 𝑂p1q-delay enumeration is ruled out, assuming the analogue of the OuMv conjecture over F2 . Example 5.2. Let K “ ptpublic, internal, confidential, secret, Ku, ‘, b, K, publicq be the accesscontrol (security) semiring [18], whose levels are ordered by restrictiveness as public ă internal ă confidential ă secret ă K, with K (“inaccessible”) the most restrictive level. Alternative derivations combine by the less restrictive clearance, 𝑎 ‘ 𝑏 “ minp𝑎, 𝑏q, while join requires the more restrictive one, 𝑎 b 𝑏 “ maxp𝑎, 𝑏q; consequently, K is the additive identity and absorbing for b, and public is the multiplicative identity, as required by the semiring axioms. The semiring is naturally ordered, with 𝑎 ďnat 𝑏 exactly when 𝑏 is at most as restrictive as 𝑎, and every monotone sequence has length at most 4: as further derivations are inserted, the annotation of a fixed tuple can only become less restrictive, and after it reaches public, no insertion can change it. Therefore, the annotated propagation has only constant overhead over the Boolean semiring, and by Lemma 5.1, any freeconnex CQ over this semiring can be maintained in amortized 𝑂p1q update time with 𝑂p1q-delay enumeration. 5.2
Modified CROWN for Annotated Relations
For a general semiring K, the annotation of a parent tuple may depend on the aggregate annotation of a child subtree. Hence, every change to an annotation in such a child subtree may need to be propagated upward. For q-hierarchical queries, such propagation can still be bounded by 𝑂p1q: on a height-1 free-connex join tree, every parent is a generalized relation contained in its children, so a single-tuple update affects a single tuple in each ancestor view. For non-q-hierarchical queries, in contrast, such propagation can affect 𝑂p|𝐷|q tuples after one update in the worst case. To avoid this additional propagation cost, we use the same piggybacking approach as in the static evaluation. For every relation/view, we use superscript B to indicate an annotation-free relation/view, i.e., 𝑅 B {𝑉𝑠B p𝑅q{𝑉𝑝B p𝑅q contains the same tuple as 𝑅{𝑉𝑠 p𝑅q{𝑉𝑝 p𝑅q, but the annotations of these relations/views are all set to be 1. We maintain annotations only where they are needed for the final output computation but cannot be obtained during enumeration, and we use annotationfree views elsewhere. Let Q be a free-connex CQ and let T be an arbitrary free-connex join tree of Q. For each node 𝑅p𝑒q, we maintain the following modified semi-join view based on the different join keys: ¸ ˜ ¸ ˜ 𝑉𝑠 p𝑅q “ 𝑅p𝑒q 1
1
𝑅𝑐 p𝑒𝑐 qP𝐶 p𝑅 q: keyp𝑒𝑐 q⊈y
𝑉𝑝 p𝑅𝑐 q
⋉
1
𝑅𝑐 p𝑒𝑐 qP𝐶 p𝑅 q: keyp𝑒𝑐 qĎy
𝑉𝑝B p𝑅𝑐 q .
A child whose join key contains a non-output attribute contributes its annotation to 𝑅p𝑒q through an annotated join: the non-output attributes below it are projected away before the enumeration ever visits them, so their ‘-aggregates must be folded into the parent. This folding is always safe on a free-connex join tree, due to the following observation: every output attribute that appears in the subtree rooted at 𝑒𝑐 also appears in keyp𝑒𝑐 q, since it appears in some node of the connex subtree as well, and hence, by the connect property, in every node on the path between the two, including 𝑒𝑐
Answering Conjunctive Queries with Aggregations under Updates
25
and its parent. Therefore, the ‘-projection in 𝑉𝑝 p𝑅𝑐 q “ 𝜋keyp𝑒𝑐 q𝑉𝑠 p𝑅𝑐 q aggregates over non-output attributes only. In contrast, a child whose join key contains only output attributes is used to filter 𝑅p𝑒q by its Boolean support; its annotations are not propagated upward, but kept locally and used during output enumeration. To this end, for every node 𝑒 with keyp𝑒q Ď y, including the root, we maintain an output view 𝑉𝑜 p𝑅q “ 𝜋𝑒 Xy𝑉𝑠 p𝑅q, where the projection aggregates by ‘ the annotations of all 𝑉𝑠 p𝑅q-tuples that agree on 𝑒 X y. Enumeration is then performed over the join of the output views: 1
𝑅 p𝑒 q: keyp𝑒 qĎy
𝑉𝑜 p𝑅q.
This join is over output attributes only; it contains the connex subtree of T , hence covers y, and remains partially reduced, so it can be enumerated with constant delay as in Boolean CROWN. Its correctness follows from the distributivity of b over ‘: the nodes whose join keys contain a non-output attribute are partitioned by their lowest ancestors with output-only join keys, the annotation of every input relation is folded along annotated joins into the output view of exactly one such ancestor 𝑣, and the observation above guarantees that the output attributes involved in this folding are all retained by 𝑉𝑜 p𝑅𝑣 q. Hence, the annotation of an output tuple is obtained by multiplying the annotations of the participating output-view tuples using b. This construction is correct for every free-connex CQ over every semiring; the update cost, however, is not bounded in general: a single-tuple update below an annotated join may change the ‘-aggregate of a projection view that joins with many parent tuples, so the propagation can touch 𝑂p|𝐷|q tuples in the worst case, as in the running example of Figure 6. For strong-connex CQs, this propagation cost collapses. Run the construction on the free-connex join tree T given by Definition 2.2: every child 𝑒𝑐 whose join key contains a non-output attribute falls under condition (ii), so 𝑒 Ď 𝑒𝑐 and keyp𝑒𝑐 q “ 𝑒. Its projection view 𝑉𝑝 p𝑅𝑐 q is then keyed on the full parent schema, the annotated “join” degenerates to a per-tuple b-multiplication, and an annotation change in 𝑉𝑝 p𝑅𝑐 q affects exactly one tuple of 𝑉𝑠 p𝑅q. All remaining propagation is support-based, exactly as in the Boolean CROWN data structure. We obtain the following upper bound. Lemma 5.3. Let K “ pK, ‘, b, 0, 1q be any semiring, and let Q be any strong-connex CQ. Q can be maintained in amortized 𝑂p1q time over any insertion-only K-sequence, while supporting 𝑂p1q-delay enumeration. Proof sketch. We maintain the views above over the tree T of Definition 2.2, whose correctness has been argued for arbitrary strong-connex CQs. For the complexity analysis, consider a single insertion into the relation 𝑅p𝑒q with keyp𝑒q Ď y. The support changes are exactly those of the Boolean CROWN, which cost amortized 𝑂p1q over any insertion-only sequence [44]. Positive is essential for this claim: non-0 annotations can neither sum nor multiply to 0, so every view tuple carries a non-0 annotation exactly when its Boolean counterpart is present, and the support of every view evolves as in the Boolean run. The additional work is the annotated propagation along the path from those 𝑒 with keyp𝑒q ⊈ y, towards its lowest ancestor whose join key contains only output attributes: every edge on this path satisfies condition (ii) of Definition 2.2, so the update changes the annotation of exactly one tuple of 𝑉𝑠 and one tuple of 𝑉𝑝 (or 𝑉𝑜 ) for every relation along the path, each maintainable in 𝑂p1q time as 𝑤 Ð 𝑤 ‘𝛿 1 or 𝑤 Ð 𝑤 b𝛿 1 for an appropriate 𝛿 1 . The 𝑂p1q-delay enumeration follows from the Boolean CROWN over the connex subtree with output-only join keys, where the annotation of each result is computed by 𝑂p1q many b-multiplications. □
26
Qichen Wang and Xiao Hu
r 𝑥3 s Answers from enumeration
𝑉𝑠 pr 𝑥 3 sq “ 𝑉𝑜 pr 𝑥 3 sq “ 𝑉𝑝B p𝑅2 q 1 𝑉𝑝B p𝑅3 q “ t 𝑐 1 : 1, 𝑐 2 : 1 u after inserting 𝑡 1 : 𝑉𝑜 pr 𝑥 3 sq “ t 𝑐 1 : 1, 𝑐 2 : 1 u after inserting 𝑡 2 : 𝑉𝑜 pr 𝑥 3 sq “ t 𝑐 1 : 1, 𝑐 2 : 1 u
Qp𝐷 old q “ t p𝑐 1, 𝑑 1 q : 546, Qp𝐷 new q “ t p𝑐 1, 𝑑 1 q : 15876,
p𝑐 2, 𝑑 2 q : 1870 u p𝑐 2, 𝑑 2 q : 19635 u
Enumeration: 𝑉𝑜 pr 𝑥 3 sq ’ 𝑉𝑜 p𝑅2 q ’ 𝑉𝑜 p𝑅3 q ’ 𝑉𝑜 p𝑅4 q
annotation-free 𝑉𝑝B p𝑅3 q
annotation-free 𝑉𝑝B p𝑅2 q 𝑅2 p𝑥 2, 𝑥 3 q
𝑅3 p𝑥 3, 𝑥 4 q
𝑉𝑠 p𝑅2 q “ 𝑅2 ’ 𝑉𝑝 p𝑅1 q “ t p𝑏 1, 𝑐 1 q : 6, p𝑏 1, 𝑐 2 q : 10 u
𝑉𝑠 p𝑅3 q “ 𝑅3 ⋉ 𝑉𝑝B p𝑅4 q “ t p𝑐 1, 𝑑 1 q : 7, p𝑐 2, 𝑑 2 q : 11 u
𝑉𝑝B p𝑅2 q “ t 𝑐 1 : 1, 𝑐 2 : 1 u 𝑉𝑜 p𝑅2 q “ t 𝑐 1 : 6, 𝑐 2 : 10 u
𝑉𝑝B p𝑅3 q “ tp𝑐 1 q : 1, p𝑐 2 q : 1u 𝑉𝑜 p𝑅3 q “ t p𝑐 1, 𝑑 1 q : 7, p𝑐 2, 𝑑 2 q : 11 u annotation-free 𝑉𝑝B p𝑅4 q
annotated 𝑉𝑝 p𝑅1 q Insert 𝑡 1 “ p𝑎 2, 𝑏 1 q : 19
𝑅4 p𝑥 4, 𝑥 5 q
𝑅1 p𝑥 1, 𝑥 2 q
𝑉𝑝 p𝑅1 q : 2 Ñ 21 𝑉𝑠 p𝑅2 q : p𝑏 1, 𝑐 1 q : 6 Ñ 63 p𝑏 1, 𝑐 2 q : 10 Ñ 105 𝑉𝑜 p𝑅2 q : t 𝑐 1 : 63, 𝑐 2 : 105 u
𝑉𝑠 p𝑅1 q “ t p𝑎 1, 𝑏 1 q : 2 u 𝑉𝑝 p𝑅1 q “ t 𝑏 1 : 2 u
Insert 𝑡 2 “ p𝑑 1, 𝑒 2 q : 23 𝑉𝑝B p𝑅4 q unchanged
𝑉𝑠 p𝑅4 q “ t p𝑑 1, 𝑒 1 q : 13, p𝑑 2, 𝑒 2 q : 17 u 𝑉𝑝B p𝑅4 q “ t 𝑑 1 : 1, 𝑑 2 : 1 u 𝑉𝑜 p𝑅4 q “ t 𝑑 1 : 13, 𝑑 2 : 17 u
𝑉𝑠 p𝑅3 q, 𝑉𝑜 p𝑅3 q unchanged 𝑉𝑜 p𝑅4 q t 𝑑 1 : 13, 𝑑 2 : 17 u Ñt 𝑑 1 : 36, 𝑑 2 : 17 u
Fig. 6. Maintained views and update propagation in CROWN for the running example.
Example 5.4. Consider ` ˘ Qp𝑥 3, 𝑥 4 q “ 𝜋𝑥 3,𝑥 4 𝑅1 p𝑥 1, 𝑥 2 q 1 𝑅2 p𝑥 2, 𝑥 3 q 1 𝑅3 p𝑥 3, 𝑥 4 q 1 𝑅4 p𝑥 4, 𝑥 5 q
over the bag semiring pN, `, ˆ, 0, 1q. We use the generalized free-connex join tree shown in Figure 6. Initially, 𝑅1 “ tp𝑎 1, 𝑏 1 q : 2u, 𝑅2 “ tp𝑏 1, 𝑐 1 q : 3, p𝑏 1, 𝑐 2 q : 5u, 𝑅3 “ tp𝑐 1, 𝑑 1 q : 7, p𝑐 2, 𝑑 2 q : 11u, 𝑅4 “ tp𝑑 1, 𝑒 1 q : 13, p𝑑 2, 𝑒 2 q : 17u. The views maintained before any update are shown in the figure. Joining the output views gives Qp𝐷 old q “ tp𝑐 1, 𝑑 1 q : 546, p𝑐 2, 𝑑 2 q : 1870u. Now insert 𝑡 1 “ p𝑎 2, 𝑏 1 q : 19 into 𝑅1 . Since 𝑅1 contains no output attributes, 𝑅1 won’t be visited during the enumeration, this change of annotation needs to be propagated from 𝑅1 to 𝑅2 , yielding 𝑉𝑠 p𝑅2 q “ tp𝑏 1, 𝑐 1 q : 63, p𝑏 2, 𝑐 2 q : 105u,
𝑉𝑜 p𝑅2 q “ t𝑐 1 : 63, 𝑐 2 : 105u
Next insert 𝑡 2 “ p𝑑 1, 𝑒 2 q : 23 into 𝑅4 . Since 𝑅4 contains output attributes, we only need to maintain the annotation-free 𝑉𝑝B p𝑅4 q, which remains unchanged after the update. Therefore, no update is propagated, making 𝑉𝑠 p𝑅3 q and 𝑉𝑜 p𝑅3 q also unchanged, while 𝑉𝑜 p𝑅4 q “ t𝑑 1 : 36, 𝑑 2 : 17u. Thus, the enumeration after both insertions gives Qp𝐷 new q “ tp𝑐 1, 𝑑 1 q : 15876, p𝑐 2, 𝑑 2 q : 19635u. 5.3
Nullary Queries
Theorem 4.5 requires that the semiring contains a monotone sequence 𝐴 of length |𝐷|𝜂 , for some constant 𝜂 ą 0, whose fragment 𝐴p2|𝐷 |1`2𝜂 ,2q is strictly-ordered with respect to both ‘ and b. On the other hand, Theorem 4.6 requires the fragment 𝐴p|𝐷 |1{2`𝜂 ,1q to be strictly-ordered only with respect to ‘ for Qqcore : its product terms have rank 1, so no condition on b is imposed. Thus, there is a gap between the two requirements. We show that this gap is real for certain semirings, using the max-max semiring defined in Section 1. Over this semiring, the annotation of a join result is the maximum annotation among
Answering Conjunctive Queries with Aggregations under Updates
27
the tuples that participate in the join, so, for a nullary query, the final annotation is the maximum annotation of any input tuple that participates in at least one full join result. Lemma 5.5. Let K be the max-max semiring over an ordered domain L, and let Q be an acyclic nullary CQ. Q can be maintained in amortized 𝑂p1q time over any insertion-only K-sequence while supporting 𝑂p1q-delay enumeration. Proof. Every update of a K-sequence carries an annotation 𝛿 P Kzt0u, and neither operation produces 0 “ K from non-K arguments, so the annotation of every tuple that is ever present lies in L Y t´8u. On this subdomain, ´8 is the smallest element, and both ‘ and b coincide with plain max; we therefore reason about maxima throughout. Let Qfull “ pV, E, Vq be the corresponding full query of Q. The annotation of the nullary answer satisfies ˆ ˙ ˆ ˙ 𝑤pHq “ max 𝑤p𝑡q “ max max 𝑤p𝑡𝑖 q “ max max 𝑤p𝑡𝑖 q . 𝑡 P Qfull
𝑡 “𝑡 1 ’𝑡 2 ¨¨¨’𝑡 |E | P Qfull
𝑅𝑖 P E
𝑅𝑖 P E
𝑡 “𝑡 1 ’𝑡 2 ¨¨¨’𝑡 |E | P Qfull
Therefore, it suffices to maintain ˆ Q𝑖 “ 𝜋H 𝑅𝑖 p𝑒𝑖 q 1
1
𝑅 p𝑒 qP E z𝑅𝑖
˙ 𝑅 B p𝑒q ,
i.e., for each relation 𝑅𝑖 p𝑒𝑖 q P E, the maximum annotation of an 𝑅𝑖 -tuple that can be extended to a full join result. Let 𝑤𝑖 pHq be the annotation of the nullary answer of Q𝑖 . Then 𝑤𝑖 pHq “
max 𝑡 “𝑡 1 ’𝑡 2 ¨¨¨’𝑡 |E | P Qfull
𝑤p𝑡𝑖 q,
and hence 𝑤pHq “ max 𝑤𝑖 pHq, 𝑅𝑖 P E
which can be obtained by first enumerating the query results for Q𝑖 , then computing the maximum over them. It remains to show that each Q𝑖 can be maintained efficiently. Fix 𝑅𝑖 . We maintain Q𝑖 by running CROWN on a generalized join tree rooted at 𝑅𝑖 . All relations other than 𝑅𝑖 are replaced by their Boolean supports. Thus, all child views below the root are propagated through the semi-join operator, and no annotation needs to be propagated. The only annotations that matter are the annotations of 𝑅𝑖 -tuples that survive, and their maximum can be maintained under an insertion-only update sequence in amortized 𝑂p1q time. Since |E| is fixed, maintaining all queries Q𝑖 adds only a constant factor to the update time. The final nullary annotation is the maximum over the constantly many values 𝑤𝑖 pHq, and can therefore also be updated in amortized 𝑂p1q time. □ 5.4
Arbitrary Update Sequences
The insertion-only upper bounds above rely on monotonicity: once a tuple appears in a projection view, later insertions cannot invalidate its existence. Under arbitrary updates, deletions may remove the last witness for a projected tuple. In the Boolean setting, CROWN handles this by maintaining support counters. For annotated relations, however, a deletion must also remove the deleted contribution from the ‘-aggregates stored in the views. We first introduce the notion of deletable aggregates for semirings.
28
Qichen Wang and Xiao Hu
Inverses, rings, and monus. The semiring K is a ring if pK, ‘, 0q is an abelian group, i.e., for every 𝑎 P K there is an additive inverse ´𝑎 such that 𝑎 ‘ p´𝑎q “ 0. Rings therefore support subtraction 𝑎 ´ 𝑏 :“ 𝑎 ‘ p´𝑏q, for example, the integer ring pZ, `, ˆ, 0, 1q. In contrast, many semirings used for annotations, such as the Boolean and bag semirings, have no additive inverses. For naturally ordered semirings, one can sometimes use a weaker subtraction-like operation called monus. Following the standard definition for K-relations with difference [7, 19], a semiring with monus, or m-semiring, is a naturally ordered semiring such that for every pair of elements 𝑎, 𝑏 P K, the set t𝑐 P K : 𝑎 ďnat 𝑏 ‘ 𝑐u has a least element, denoted by 𝑎 a 𝑏. For pN, `, ˆ, 0, 1q, the monus is exactly truncated subtraction: 𝑎 a𝑏 “ maxt𝑎 ´𝑏, 0u. For the Boolean semiring, the monus coincides with 𝑎 ^ ␣𝑏. The monus is the algebraic operation used to interpret relational difference over semiring-annotated relations [19, 39]. For maintenance under deletions, what matters is not the monus operator itself, but whether an ‘-aggregate can be maintained when its contributing elements are deleted. We capture this requirement by the following notion. Definition 5.6 (Deletable aggregates). A semiring K admits 𝑂p1q-deletable aggregates if there is a representation scheme that stores, for any multiset 𝐴 of elements from K, a state 𝜎p𝐴q of 𝑂p1q words, supporting each of the following operations in 𝑂p1q time: (i) return ‘𝑣 P𝐴 𝑣 from 𝜎p𝐴q; (ii) given 𝛿 P K, update 𝜎p𝐴q to 𝜎p𝐴 Z t𝛿uq; and (iii) given an element 𝛿 P 𝐴, update 𝜎p𝐴q to 𝜎p𝐴zt𝛿uq. Although rings fall outside the positive semirings considered in this paper, deletability is a purely algebraic notion, and every ring admits 𝑂p1q-deletable aggregates: store ‘𝑣 P𝐴 𝑣 itself, and implement deletion by adding the additive inverse, 𝜎p𝐴zt𝛿uq “ 𝜎p𝐴q ‘ p´𝛿q. The bag semiring pN, `, ˆ, 0, 1q also does, by storing the sum and using truncated subtraction. The Boolean semiring admits 𝑂p1qdeletable aggregates as well, but not through its monus: a does not satisfy p‘𝑣 P𝐴 𝑣qa𝛿 “ ‘𝑣 P𝐴zt𝛿 u 𝑣 in general, since ptrue _ trueq a true must remain true, while true ^ ␣true “ false. Instead, the state stores the number of true elements in 𝐴, and the aggregate is true if and only if this counter is positive; this technique is known as derivation counting [15]. In contrast, the tropical semiring does not admit 𝑂p1q-deletable aggregates, at least when the annotations are abstract values that can only be accessed through semiring operations and comparisons: Lemma 5.7. Tropical semiring pRYt´8u, max, `, ´8, 0q does not admit 𝑂p1q-deletable aggregates, assuming that annotations are accessed only through 𝑂p1q-time semiring operations and comparisons, and that sorting 𝑛 values in this model requires Ωp𝑛 log 𝑛q operations in the worst case. Proof. Assume, for contradiction, that such a representation scheme exists. Given an arbitrary set 𝐴 Ď R of 𝑛 values, we can sort 𝐴 as follows: (1) insert all elements of 𝐴 into the state 𝜎 by operation (ii), in 𝑂p𝑛q total time; (2) query cur “ ‘𝑣 P𝐴 𝑣 “ max𝑣 P𝐴 𝑣 by operation (i), and output cur; (3) delete cur from 𝜎 by operation (iii), and update 𝐴 with 𝐴ztcuru; (4) repeat (2)-(3) until 𝐴 becomes empty. The output sequence is 𝐴 sorted in decreasing order. Each of the 𝑛 rounds of (2)–(3) takes 𝑂p1q time, so the total runtime is 𝑂p𝑛q operations, contradicting the Ωp𝑛 log 𝑛q sorting lower bound. □ If K admits 𝑂p1q-deletable aggregates (Definition 5.6) – as do all rings, the Boolean semiring via derivation counting, and the bag semiring via truncated subtraction – then every aggregate stored in a view can be maintained in 𝑂p1q time per insertion and deletion, and the data structure extends to arbitrary update sequences with no asymptotic overhead over its Boolean counterpart. For the tropical semiring, which does not admit 𝑂p1q-deletable aggregates (Lemma 5.7), we show that this is not an artifact of our data structure but an inherent barrier, by adapting the sorting reduction to the maintenance problem:
Answering Conjunctive Queries with Aggregations under Updates
29
Lemma 5.8. Let Q be any non-full CQ, and K be the tropical semiring pR Y t´8u, max, `, ´8, 0q. Q cannot be maintained in 𝑂p1q amortized time while supporting 𝑂p1q-delay enumeration over arbitrary K-sequences, under the same assumption as in Lemma 5.7. Proof. Assume, for contradiction, that such an index exists. Let 𝑥 1 P ȳ be a non-output attribute of Q, contained in relation 𝑅𝑖 . We instantiate Q so that it simulates Q 1 “ 𝜋H 𝑅p𝑥 1 q: for every relation 𝑅 𝑗 with 𝑗 ‰ 𝑖, insert a single tuple that takes a fixed dummy value on every attribute, with annotation 1 “ 0; tuples of 𝑅𝑖 take the dummy value on all attributes except 𝑥 1 . Then every result of Q has annotation max𝑡 P𝑅𝑖 𝑤p𝑡q. Given a set 𝐴 Ď R of 𝑛 distinct values, we sort 𝐴 as follows. For the 𝑗-th element 𝑎 P 𝐴, insert a tuple 𝑡 𝑗 into 𝑅𝑖 with a fresh 𝑥 1 -value and annotation 𝑎, and store the entry 𝑎 Ñ 𝑡 𝑗 in a dictionary; this takes 𝑂p𝑛q total time. Then repeat 𝑛 times: enumerate Q to obtain the current maximum value 𝑤, output 𝑤, retrieve the tuple 𝑡 Ð 𝑤 from the dictionary, and delete (the insertion of) 𝑡 from the index. Each round takes 𝑂p1q time, so the values of 𝐴 are output in decreasing order within 𝑂p𝑛q operations in total, contradicting the assumed Ωp𝑛 log 𝑛q lower bound for sorting. □ 6
Conclusion
We settled how aggregation affects the dynamic maintenance of conjunctive queries, giving a dichotomy parameterized by both the query and the semiring. Under arbitrary updates, aggregation is as hard as the Boolean case: the frontier stays at the 𝑞-hierarchical CQs, maintainable in 𝑂p1q amortized time for 𝑂p1q-deletable aggregations and 𝑂plog |𝐷|q otherwise. Under insertion-only updates, it retreats from free-connex to the strong-connex class we introduce; a single CROWN-based algorithm maintains every strong-connex CQ in 𝑂p1q amortized time with 𝑂p1q-delay enumeration, while no free-connex but non-strong-connex CQ is maintainable in 𝑂p|𝐷|1{2´𝜖 q time under the OuMv and OMv conjectures, with sharper height- and dimension-parameterized bounds under the Combinatorial 𝑘-Clique and OuMv𝑘 conjectures. Several directions remain open. First, our lower bounds under the Combinatorial 𝑘-Clique Conjecture apply exclusively to combinatorial algorithms, leaving room for algebraic methods. Fast matrix multiplication (FMM) already powers the best algorithms for evaluating large classes of CQs [3, 26] and was also used to accelerate dynamic subgraph maintenance [8, 38, 40, 41]. Whether FMM can speed up annotated CQ maintenance remains an open question. The obstacle is algebraic rather than technical: FMM relies on subtraction, which a general semiring does not provide, and no truly subcubic algorithm is known for the min-plus product that the tropical semiring needs [46]. A semiring is therefore likely to admit such speedups exactly when its additive structure supports cancellation, which suggests a second classification of semirings orthogonal to the order conditions studied here. In the same spirit, recent work shows that OMv hypotheses for several non-Boolean products are equivalent to the Boolean one [25]; identifying the semirings for which the analogous equivalence holds would place our conditional lower bounds on a broader foundation. Second, the trade-off between maintenance cost and enumeration delay. We have insisted on 𝑂p1q delay throughout, which makes the dichotomy sharp but hides a spectrum: for triangle and hierarchical queries over the Boolean semiring, allowing a larger delay provably buys a smaller update time, and the resulting trade-offs are Pareto optimal under the OMv Conjecture [31, 32]. Whether annotations admit the same trade-off is unclear, since our reductions read the maintained annotation through a single enumeration call and therefore degrade gracefully as the delay grows, whereas the upper bound relies on propagating each annotation eagerly. Mapping the update-delay curve for free-connex but non-strong-connex CQs, and determining how the shape of that curve depends on the semiring, would complete the picture that the present dichotomy only outlines.
30
Qichen Wang and Xiao Hu
References [1] Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. 2015. If the Current Clique Algorithms Are Optimal, so Is Valiant’s Parser. In IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). 98–117. doi:10.1109/FOCS.2015.16 [2] Amir Abboud and Virginia Vassilevska Williams. 2014. Popular conjectures imply strong lower bounds for dynamic problems. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. IEEE, 434–443. [3] Mahmoud Abo Khamis, Xiao Hu, and Dan Suciu. 2025. Fast Matrix Multiplication meets the Submodular Width. Proc. ACM Manag. Data 3, 2, Article 98 (June 2025), 26 pages. doi:10.1145/3725235 [4] Mahmoud Abo Khamis, Hung Q Ngo, and Atri Rudra. 2016. FAQ: questions asked frequently. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 13–28. [5] Yanif Ahmad, Oliver Kennedy, Christoph Koch, and Milos Nikolic. 2012. DBToaster: Higher-order delta processing for dynamic, frequently fresh views. Proceedings of the VLDB Endowment 5, 10 (2012), 968–979. [6] Noga Alon, Raphael Yuster, and Uri Zwick. 1995. Color-Coding. J. ACM 42, 4 (1995), 844–856. doi:10.1145/210332.210337 [7] K. Amer. 1984. Equationally complete classes of commutative monoids with monus. Algebra Universalis 18, 1 (1984), 129–131. doi:10.1007/BF01182254 [8] Sepehr Assadi and Vihan Shah. 2025. An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs using Fast Matrix Multiplication. In Proceedings of the 44th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. [9] Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. 2007. On Acyclic Conjunctive Queries and Constant Delay Enumeration. In Computer Science Logic. Springer Berlin Heidelberg, Berlin, Heidelberg, 208–222. [10] C. Beeri, R. Fagin, D. Maier, and M. Yannakakis. 1983. On the desirability of acyclic database schemes. JACM 30, 3 (1983), 479–513. [11] Christoph Berkholz, Fabian Gerhardt, and Nicole Schweikardt. 2020. Constant Delay Enumeration for Conjunctive Queries: A Tutorial. ACM SIGLOG News 7, 1 (feb 2020), 4–33. doi:10.1145/3385634.3385636 [12] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. 2017. Answering Conjunctive Queries under Updates. In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (Chicago, Illinois, USA) (PODS ’17). Association for Computing Machinery, New York, NY, USA, 303–318. doi:10.1145/3034786.3034789 [13] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. 2018. Answering UCQs under Updates and in the Presence of Integrity Constraints. In 21st International Conference on Database Theory (ICDT 2018). Schloss Dagstuhl-LeibnizZentrum fuer Informatik. [14] Johann Brault-Baron. 2013. De la pertinence de l’énumération: complexité en logiques propositionnelle et du premier ordre. Ph. D. Dissertation. University of Caen. [15] Rada Chirkova and Jun Yang. 2012. Materialized views. Foundations and Trends® in Databases 4, 4 (2012), 295–405. [16] Thomas Eiter and Rafael Kiesel. 2021. On the Complexity of Sum-of-Products Problems over Semirings. Proceedings of the AAAI Conference on Artificial Intelligence 35, 7 (May 2021), 6304–6311. doi:10.1609/aaai.v35i7.16783 [17] Ronald Fagin. 1983. Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. J. ACM 30, 3 (1983), 514–550. doi:10.1145/2402.322390 [18] J. Nathan Foster, Todd J. Green, and Val Tannen. 2008. Annotated XML: Queries and Provenance. In Proceedings of the 27th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). ACM. doi:10.1145/1376916. 1376954 [19] Floris Geerts and Antonella Poggi. 2010. On database query languages for K-relations. Journal of Applied Logic 8, 2 (2010), 173–185. doi:10.1016/j.jal.2009.09.001 [20] Jonathan S. Golan. 1999. Semirings and their Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands. doi:10.1007/978-94-015-9333-5 [21] Todd J. Green, Grigoris Karvounarakis, and Val Tannen. 2007. Provenance semirings. In Proceedings of the Twenty-Sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM, New York, NY, USA, 31–40. doi:10.1145/1265530.1265535 [22] Ashish Gupta, Inderpal Singh Mumick, and Venkatramanan Siva Subrahmanian. 1993. Maintaining views incrementally. ACM SIGMOD Record 22, 2 (1993), 157–166. doi:10.1145/170036.170066 [23] Kathrin Hanauer, Monika Henzinger, and Qi Cheng Hua. 2022. Fully Dynamic Four-Vertex Subgraph Counting. In 1st Symposium on Algorithmic Foundations of Dynamic Networks. [24] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. 2015. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (Portland, Oregon, USA) (STOC ’15). Association for Computing Machinery, New York, NY, USA, 21–30. doi:10.1145/2746539.2746609 [25] Bingbing Hu and Adam Polak. 2025. Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems. In 33rd Annual European Symposium on Algorithms (ESA 2025) (Leibniz International Proceedings in Informatics
Answering Conjunctive Queries with Aggregations under Updates
31
(LIPIcs), Vol. 351). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 54:1–54:16. doi:10.4230/LIPIcs.ESA.2025.54 [26] Xiao Hu. 2024. Fast Matrix Multiplication for Query Processing. Proc. ACM Manag. Data 2, 2 (2024). doi:10.1145/3651599 [27] Xiao Hu and Qichen Wang. 2025. Towards Update-Dependent Analysis of Query Maintenance. Proc. ACM Manag. Data 3, 2 (PODS), Article 117 (2025), 25 pages. doi:10.1145/3725254 [28] Muhammad Idris, Martin Ugarte, and Stijn Vansummeren. 2017. The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates. In Proceedings of the 2017 ACM International Conference on Management of Data (Chicago, Illinois, USA) (SIGMOD ’17). Association for Computing Machinery, New York, NY, USA, 1259–1274. doi:10.1145/3035918.3064027 [29] Ce Jin and Yinzhan Xu. 2022. Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC). ACM, 1515–1528. doi:10.1145/3519935. 3520036 [30] Manas R. Joglekar, Rohan Puttagunta, and Christopher Ré. 2016. AJAR: Aggregations and Joins over Annotated Relations. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (San Francisco, California, USA) (PODS ’16). Association for Computing Machinery, New York, NY, USA, 91–106. doi:10.1145/2902251.2902293 [31] Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2020. Maintaining Triangle Queries under Updates. ACM Trans. Database Syst. 45, 3, Article 11 (aug 2020), 46 pages. doi:10.1145/3396375 [32] Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2020. Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 375–392. doi:10.1145/3375395.3387646 [33] Christoph Koch. 2010. Incremental query evaluation in a ring of databases. In Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). 87–98. doi:10.1145/1807085.1807100 [34] Andrea Lincoln and Nikhil Vyas. 2020. Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 151). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 11:1–11:17. doi:10.4230/LIPIcs.ITCS. 2020.11 [35] Andrea Lincoln, Virginia Vassilevska Williams, and Ryan Williams. 2018. Tight hardness for shortest cycles and paths in sparse graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1236–1252. [36] Milos Nikolic, Mohammad Dashti, and Christoph Koch. 2016. How to win a hot dog eating contest: Distributed incremental view maintenance with batch updates. In Proc. ACM SIGMOD International Conference on Management of Data. ACM, 511–526. [37] Milos Nikolic and Dan Olteanu. 2018. Incremental view maintenance with triple lock factorization benefits. In Proc. ACM SIGMOD International Conference on Management of Data. ACM, 365–380. [38] Piotr Sankowski. 2004. Dynamic Transitive Closure via Dynamic Matrix Inverse. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. 509–517. [39] Dan Suciu. 2024. Different Differences in Semirings. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen (Open Access Series in Informatics (OASIcs), Vol. 119), Antoine Amarilli and Alin Deutsch (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 10:1–10:20. doi:10.4230/OASIcs.Tannen.10 [40] Jan van den Brand, Sebastian Forster, Yasamin Nazari, and Adam Polak. 2024. On Dynamic Graph Algorithms with Predictions. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms. 3534–3557. doi:10.1137/1. 9781611977912.126 [41] Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak. 2019. Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds. In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science. 456–480. [42] Qichen Wang. 2026. Towards Parameterized Hardness on Maintaining Conjunctive Queries. Proc. ACM Manag. Data 4, 2, Article 121 (May 2026), 26 pages. doi:10.1145/3801917 [43] Qichen Wang, Bingnan Chen, Binyang Dai, Ke Yi, Feifei Li, and Liang Lin. 2025. Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees. Proc. ACM Manag. Data 3, 3, Article 235 (June 2025), 28 pages. doi:10.1145/3725423 [44] Qichen Wang, Xiao Hu, Binyang Dai, and Ke Yi. 2023. Change Propagation Without Joins. Proceedings of the VLDB Endowment 16, 5 (2023), 1046–1058. doi:10.14778/3579075.3579080 [45] Qichen Wang and Ke Yi. 2020. Maintaining Acyclic Foreign-Key Joins under Updates. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 1225–1239. [46] Ryan Williams. 2014. Faster all-pairs shortest paths via circuit complexity. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (STOC). 664–673. doi:10.1145/2591796.2591811
32
A
Qichen Wang and Xiao Hu
Missing Proofs in Section 2
Proof of Lemma 2.3. Let T be a free-connex join tree witnessing Definition 2.2, i.e., every nonroot node 𝑒 with parent 𝑒𝑝 satisfies (i) keyp𝑒q Ď y or (ii) 𝑒𝑝 Ď 𝑒. By the connect property, the nodes containing any fixed attribute 𝑥 form a connected subtree T𝑥 of T . In particular, if both endpoints of an edge contain a non-output attribute 𝑥, then the child 𝑒 of this edge has 𝑥 P keyp𝑒q ⊈ y, so condition (ii) must hold at 𝑒, i.e., 𝑒𝑝 Ď 𝑒. For the D-hierarchy-property, suppose that some pair 𝑥 1, 𝑥 2 P ȳ satisfies E𝑥 1 ⊈ E𝑥 2 , E𝑥 2 ⊈ E𝑥 1 , and E𝑥 1 X E𝑥 2 ‰ H. Pick 𝑒 1 P E𝑥 1 zE𝑥 2 , 𝑒 3 P E𝑥 2 zE𝑥 1 , and 𝑒 2 P E𝑥 1 X E𝑥 2 . The path from 𝑒 1 to 𝑒 2 lies in T𝑥 1 , the path from 𝑒 2 to 𝑒 3 lies in T𝑥 2 , and the path from 𝑒 1 to 𝑒 3 is contained in their union, so every edge of the latter path has both endpoints in T𝑥 1 or both in T𝑥 2 , and is therefore of type (ii). Let 𝑎 be the node of this path closest to the root: following the path from 𝑎 down to 𝑒 1 and down to 𝑒 3 , type (ii) yields 𝑎 Ď 𝑒 1 and 𝑎 Ď 𝑒 3 . But 𝑎 lies on the path, so 𝑥 1 P 𝑎 or 𝑥 2 P 𝑎, giving 𝑥 1 P 𝑒 3 or 𝑥 2 P 𝑒 1 , a contradiction. For the head-cluster-property, consider 𝑒, 𝑒 1 P E with 𝑥 P 𝑒 X 𝑒 1 X ȳ, and suppose that some 𝑦0 P p𝑒 X yqz𝑒 1 exists; the case of p𝑒 1 X yqz𝑒 is symmetric. The path from 𝑒 to 𝑒 1 lies in T𝑥 , so all its edges are of type (ii), and its node 𝑎 closest to the root satisfies 𝑎 Ď 𝑒 1 ; in particular, 𝑦0 R 𝑎. By the connex property, 𝑦0 appears in some node 𝑔 of the connex subtree Tcon , and since Tcon is connected and contains the root, it contains every ancestor of 𝑔. Let 𝑏 be the lowest common ancestor of 𝑒 and 𝑔. The path from 𝑒 to 𝑔 lies in T𝑦0 and passes through 𝑏, so 𝑦0 P 𝑏. Both 𝑎 and 𝑏 are ancestors of 𝑒, hence comparable. If 𝑏 is 𝑎 or an ancestor of 𝑎, then 𝑎 lies on the path from 𝑒 to 𝑏, so 𝑦0 P 𝑎, a contradiction. Otherwise, 𝑏 lies strictly below 𝑎 on the path from 𝑒 to 𝑎, which is contained in T𝑥 ; then 𝑥 belongs to 𝑏 and to its parent, so 𝑥 P keyp𝑏q, while 𝑏 P Tcon as an ancestor of 𝑔, so keyp𝑏q Ď y by the connex property, contradicting 𝑥 R y. Hence, a strong-connex CQ must satisfy both D-hierarchy-property and head-cluster-property, which completes the proof. □ The converse of Lemma 2.3 also holds: the two properties are not only necessary but also sufficient for a free-connex CQ, so strong-connexity could equivalently be defined through them. Lemma A.1. Every free-connex CQ satisfying the D-hierarchy-property and the head-cluster-property is strong-connex. Proof of Lemma A.1. We first dispose of two extreme cases. If y “ V, then every join key of any free-connex join tree of Q is trivially a subset of y, so condition (i) holds at every non-root node. If y “ H, the D-hierarchy property degenerates to the hierarchy property, so Q is q-hierarchical, and Q admits a height-1 free-connex join tree in which every internal node is a generalized relation contained in each of its children [44]; hence, condition (ii) holds at every non-root node. In the remainder, we consider H ⊊ y ⊊ V. Without loss of generality, we also assume that Q contains no unique attributes: a unique attribute appears in a single node of any join tree, so it affects no join key, none of the tree properties, and neither of the two conditions. A non-output attribute 𝑥 P ȳ is maximal if there is no 𝑧 P ȳ with E𝑥 ⊊ E𝑧 . For a CQ satisfying the two properties, the sets E𝑥 of maximal attributes partition the relations containing non-output attributes. First, every relation 𝑒 with 𝑒 X ȳ ‰ H belongs to E𝑥 for some maximal 𝑥: pick 𝑥 P 𝑒 X ȳ with E𝑥 maximal among tE𝑧 : 𝑧 P 𝑒 X ȳu; if some 𝑧 P ȳ had E𝑥 ⊊ E𝑧 , then 𝑒 P E𝑥 Ď E𝑧 would give 𝑧 P 𝑒, contradicting the choice of 𝑥. Second, the sets of two maximal attributes 𝑥, 𝑥 1 are either equal or disjoint: if 𝑒 P E𝑥 X E𝑥 1 , the D-hierarchy property forces E𝑥 Ď E𝑥 1 or E𝑥 1 Ď E𝑥 , and maximality of both forces E𝑥 “ E𝑥 1 . Now fix a maximal attribute 𝑥 (one per distinct set E𝑥 ). All relations in E𝑥 agree on their output attributes: any 𝑒, 𝑒 1 P E𝑥 satisfy 𝑥 P 𝑒 X 𝑒 1 X ȳ, so 𝑒 X y “ 𝑒 1 X y by the head-cluster property;
Answering Conjunctive Queries with Aggregations under Updates
33
we denote this common set by y𝑥 . Moreover, every non-output attribute 𝑧 of a relation 𝑒 P E𝑥 satisfies E𝑧 Ď E𝑥 (the two sets share 𝑒, so they are comparable by the D-hierarchy property, and E𝑥 is maximal); hence 𝑧 appears in no relation outside E𝑥 . Consider the nullary CQ ˜ ¸ ď Q̄𝑥 :“ p𝑒zyq, t𝑒zy : 𝑒 P E𝑥 u, H 𝑒 P E𝑥
obtained by removing the output attributes from the relations of E𝑥 . By the above, the D-hierarchy property makes Q̄𝑥 q-hierarchical, and as in the case y “ H, Q̄𝑥 admits a height-1 free-connex join tree T̄𝑥 in which every internal node is a generalized relation contained in each of its children [44]. Let T𝑥 be obtained from T̄𝑥 by adding y𝑥 to every node: every leaf p𝑒zyq Y y𝑥 “ 𝑒 becomes the input relation 𝑒 itself, and every internal node remains a valid generalized relation (if 𝑔 Ď 𝑒zy for some 𝑒 P E𝑥 , then 𝑔 Y y𝑥 Ď 𝑒, as y𝑥 “ 𝑒 X y), still contained in each of its children. In particular, every non-root node of T𝑥 satisfies condition (ii). Next, we pull out a connex subtree. Let T 1 be an arbitrary free-connex join tree of Q, and let Tcon be a connex subtree of T 1 . We make Tcon maximal, i.e., every leaf node of Tcon is also a leaf node of T 1 , or contains non-output attributes. By the definition of the connex subtree, only the leaf nodes of Tcon can contain non-output attributes, so all join keys within Tcon contain only output attributes. For every maximal attribute 𝑥, there exists a node 𝑒 P Tcon such that 𝑥 P 𝑒; otherwise, the maximality of 𝑥 or the connect property of T 1 would be violated. We now replace 𝑒 with the height-1 join tree T𝑥 . The resulting tree is still a valid join tree, in which we allow generalized relations in the middle of the tree: since 𝑒 X 𝑒𝑝 Ď y, every node of T𝑥 contains the join key 𝑒 X 𝑒𝑝 , so replacing 𝑒 with T𝑥 preserves all the requirements of a join tree. After replacing every such 𝑒 with T𝑥 , we conclude that the resulting tree T is a valid free-connex join tree satisfying the two conditions. First, all relations appear in T : a relation 𝑒 with 𝑒 X ȳ ‰ H appears in the subtree T𝑥 for the maximal attribute 𝑥 of its class, and 𝑒 P Tcon otherwise. Every subtree T𝑥 satisfies condition (ii), as shown above, while the remaining subtree Tcon has all its join keys contained in y, and thus satisfies condition (i). □ Proof of Lemma 2.4. Consider an arbitrary free-connex but non-strong-connex CQ Q “ pV, E, yq. We claim that either D-hierarchy-property or head-cluster-property fails on Q. Suppose not, assume Q satisfies both D-hierarchy-property and head-cluster-property. From Lemma A.1, Q must be strong-connex in this case, contradicting the assumption. Then, we distinguish the following two cases on Q: If the D-hierarchy-property fails on Q, there exist 𝑥 1, 𝑥 2 P ȳ with E𝑥 1 ⊈ E𝑥 2 , E𝑥 2 ⊈ E𝑥 1 , and E𝑥 1 X E𝑥 2 ‰ H; then any 𝑒 2 P E𝑥 1 X E𝑥 2 , 𝑒 1 P E𝑥 1 zE𝑥 2 , and 𝑒 3 P E𝑥 2 zE𝑥 1 form an D-hierarchy-core. If the head-cluster-property fails on Q, there exists a pair of relations 𝑒 1, 𝑒 2 P E with some attribute 𝑥 2 P 𝑒 1 X 𝑒 2 X ȳ and 𝑒 1 X y ‰ 𝑒 2 X y; without loss of generality, some 𝑥 1 P p𝑒 1 X yqz𝑒 2 exists, and p𝑒 1, 𝑒 2, 𝑥 1, 𝑥 2 q is a q-core. Hence, Q contains an D-hierarchy-core or a q-core. □ B
Missing Proofs in Section 4.4
Note that the proofs of both Lemma 4.13 and Lemma 4.14 reduce the maintenance problem to 𝑘-cycle detection on sparse graphs and invoke Theorem 4.11, following [42]; Lemma 4.13 uses the cycle length 𝑘, the number of relations of 𝑄𝑘 , and Lemma 4.14 the even cycle length 2ℎ. Let 𝐺 “ p𝑉𝐺 , 𝐸𝐺 q be a directed graph with 𝑛 vertices and 𝑚 edges at the density of Theorem 4.11, so that 𝑛 “ 𝑚 pℎ´1q{ℎ for both parities. We first color 𝐺: the vertices receive colors from t0, 1, ¨ ¨ ¨ , 𝑘 ´ 1u, and only the edges from a color class 𝐿 𝑗 to the next class 𝐿 𝑗 `1 mod 𝑘 are kept. Coloring reduces
34
Qichen Wang and Xiao Hu
closed walks to cycles: a closed walk that advances once through the 𝑘 classes, called a layered cycle, visits 𝑘 pairwise distinct vertices. By color-coding [6], every 𝑘-cycle of 𝐺 survives the pruning under at least one of 𝑂plog 𝑛q colorings, which we try one by one; a colored graph contains a layered 𝑘-cycle if and only if some vertex 𝑣 P 𝐿0 lies on one, which is what both reductions decide, vertex by vertex (see Figure 4). Bounding the size of the fragments is the step that our annotated setting adds on top of the Boolean reduction of [42]: over the Boolean semiring the aggregates are idempotent and no bound is needed, while our strict-order argument applies only to values inside a bounded fragment. The fragments assumed in the two lemmas are determined by the maximum number of layered paths in the colored graph: every annotation maintained below is an ‘-aggregate with one summand over 𝐴 per layered path together with the vertices of 𝐿0 whose insertions produced its endpoint tuples. The counting uses only the number of vertices. The coloring partitions the vertices into the classes 𝐿0, 𝐿1, ¨ ¨ ¨ , 𝐿𝑘 ´1 , and a layered path on 𝑘 ´ 1 vertices picks one vertex from each of 𝐿1, ¨ ¨ ¨ , 𝐿𝑘 ´1 ; ś ř hence there are at most 𝑘𝑖 “´11 |𝐿𝑖 | such paths, and under the constraint 𝑘𝑖 “´11 |𝐿𝑖 | ď 𝑛 this product is maximized by classes of equal size, at p𝑛{p𝑘 ´ 1qq𝑘 ´1 ď 𝑛𝑘 ´1 . Likewise, the ℎ ´ 1 later vertices of a layered walk leaving a fixed vertex come from ℎ ´ 1 distinct classes, so at most 𝑛ℎ´1 such walks leave any vertex. Counting the 𝐿0 -vertices as part of the witness, a witness of Lemma 4.13 becomes a tuple of 𝑘 ` 1 vertices, and a witness of Lemma 4.14, for a fixed output value, a tuple of ℎ vertices; the same product bound gives at most 𝑛𝑘 `1 ď |𝐷|p𝑘 `1qpℎ´1q{ℎ and 𝑛ℎ ď |𝐷|ℎ´1 witnesses, and hence the fragments 𝐴p2|𝐷 |p𝑘 `1qpℎ´1q{ℎ ,2q and 𝐴p|𝐷 |ℎ´1,1q , using 𝑛 “ 𝑚 pℎ´1q{ℎ ď |𝐷|pℎ´1q{ℎ . B.1
Proof of Lemma 4.13
Proof of Lemma 4.13. We run the reduction on the colored graphs described above, with cycle length 𝑘; fix one coloring. Encoding. For 1 ď 𝑗 ď 𝑘 ´ 2, we insert into 𝑅 𝑗 `1 p𝑥 𝑗 , 𝑥 𝑗 `1 q every edge p𝑢, 𝑢 1 q P 𝐸𝐺 with 𝑢 P 𝐿 𝑗 and 𝑢 1 P 𝐿 𝑗 `1 , with annotation 1. We process the vertices of 𝐿0 in a single pass, and maintain two databases that receive the endpoint insertions in opposite orders; no blocks or resets are needed, as the monotone sequence of length |𝐷| covers all |𝐿0 | ď 𝑛 vertices. For the ℓ-th vertex 𝑣: in the first database, we insert the tuple p𝑢q into 𝑅1 for every edge p𝑣, 𝑢q P 𝐸𝐺 with 𝑢 P 𝐿1 , and query the annotation 𝑤 ℓ1 ; in the second database, we insert the tuple p𝑢q into 𝑅𝑘 for every edge p𝑢, 𝑣q P 𝐸𝐺 with 𝑢 P 𝐿𝑘 ´1 , and query the annotation 𝑤 ℓ2 ; we then complete the insertions in both databases, and query the first one for 𝑤 ℓ ; all endpoint tuples of the ℓ-th vertex carry annotation 𝑎 ℓ . We report that 𝑣 lies on a layered 𝑘-cycle if and only if 𝑤 ℓ1 ‘ 𝑤 ℓ2 ă 𝑤 ℓ ´1 ‘ 𝑤 ℓ . Correctness. A witness is a tuple p𝑢 1, ¨ ¨ ¨ , 𝑢𝑘 ´1, ℓ 1, ℓ 2 q such that p𝑢 𝑗 , 𝑢 𝑗 `1 q P 𝑅 𝑗 `1 for every 1 ď 𝑗 ď 𝑘 ´ 2, the ℓ 1 -th vertex has an edge to 𝑢 1 , and 𝑢𝑘 ´1 has an edge to the ℓ 2 -th vertex; its contribution is the rank-2 product term 𝑎 ℓ 1 b 𝑎 ℓ 2 . Exactly as in the proof of Theorem 4.5, the two compared values aggregate the same witnesses, except the current witnesses (ℓ 1 “ ℓ 2 “ ℓ), each contributing 𝑎 ℓ b𝑎 ℓ to 𝑤 ℓ ´1 ‘𝑤 ℓ only. A current witness is a closed walk 𝑣 Ñ 𝑢 1 Ñ ¨ ¨ ¨ Ñ 𝑢𝑘 ´1 Ñ 𝑣; as the walk advances once through the layers 𝐿0, 𝐿1, ¨ ¨ ¨ , 𝐿𝑘 ´1 , its 𝑘 vertices lie in pairwise distinct layers and are therefore distinct, so the current witnesses are exactly the layered 𝑘-cycles through 𝑣. For the order argument, we count the product terms that the compared values aggregate. A witness is identified with a tuple of 𝑘 ` 1 vertices: the vertex 𝑣 ℓ 1 P 𝐿0 whose insertions put p𝑢 1 q into 𝑅1 , the path vertices 𝑢 1, ¨ ¨ ¨ , 𝑢𝑘 ´1 , and the vertex 𝑣 ℓ 2 P 𝐿0 whose insertions put p𝑢𝑘 ´1 q into 𝑅𝑘 . By the product bound above, there are at most 𝑛 2 ¨ 𝑛𝑘 ´1 “ 𝑛𝑘 `1 ď |𝐷|p𝑘 `1qpℎ´1q{ℎ such tuples. Hence each of 𝑤 ℓ ´1 , 𝑤 ℓ , 𝑤 ℓ1 , and 𝑤 ℓ2 aggregates at most |𝐷|p𝑘 `1qpℎ´1q{ℎ product terms of rank 2, and each compared value, the ‘-sum of two of them, at most 2|𝐷|p𝑘 `1qpℎ´1q{ℎ ; all values involved thus lie
Answering Conjunctive Queries with Aggregations under Updates
35
in the domain of 𝐴p2|𝐷 |p𝑘 `1qpℎ´1q{ℎ ,2q , and the argument of Theorem 4.5 applies verbatim: the test succeeds if and only if a current witness exists. Running time. The databaseřsize is |𝐷| “ Θp𝑚q: the middle relations receive 𝑂p𝑚q tuples, and the endpoint relations receive 𝑣 𝑂pdegp𝑣qq “ 𝑂p𝑚q tuples in total. Recall that 𝑛 “ 𝑚 pℎ´1q{ℎ . The reduction has two cost components. First, the insertions: the 𝑂p𝑚q tuples cost 𝑂p𝑚 ¨ 𝑚 pℎ´1q{ℎ´𝜖 q “ 𝑂p𝑚 p2ℎ´1q{ℎ´𝜖 q at the assumed amortized update time. Second, the enumeration: the 𝑂p𝑛q queries each return the single nullary annotation at delay 𝑂p|𝐷|1´𝜖 q, for a total of 𝑂p𝑛¨𝑚 1´𝜖 q “ 𝑂p𝑚 pℎ´1q{ℎ`1´𝜖 q “ 𝑂p𝑚 p2ℎ´1q{ℎ´𝜖 q. The two components sum to 𝑂p𝑚 p2ℎ´1q{ℎ´𝜖 q, and summing over the 𝑂plog 𝑛q colorings adds a logarithmic factor, absorbed into the polynomial slack. Finally, p2ℎ´1q{ℎ “ 2𝑘{p𝑘 `1q for odd 𝑘 “ 2ℎ ´ 1, and p2ℎ ´ 1q{ℎ “ p2𝑘 ´ 2q{𝑘 for even 𝑘 “ 2ℎ, so 𝑘-cycle detection is solved in 1 1 𝑂p𝑚 2𝑘 {p𝑘 `1q´𝜖 q time for odd 𝑘 and in 𝑂p𝑚 p2𝑘 ´2q{𝑘 ´𝜖 q time for even 𝑘, for some constant 𝜖 1 ą 0, contradicting Theorem 4.11 and thus the Combinatorial 𝑘-Clique Conjecture. □ B.2
Proof of Lemma 4.14
Proof of Lemma 4.14. The reduction combines the encoding of Lemma 4.13 with the per-outputvalue read-off of Theorem 4.6. We run it on the colored graphs described above, with the even cycle length 2ℎ, so that the color classes are 𝐿0, 𝐿1, ¨ ¨ ¨ , 𝐿2ℎ´1 and 𝑛 “ 𝑚 pℎ´1q{ℎ ; fix one coloring. Every candidate cycle 𝑣 Ñ 𝑐 1 Ñ ¨ ¨ ¨ Ñ 𝑐 2ℎ´1 Ñ 𝑣 with 𝑐 𝑗 P 𝐿 𝑗 advances once through the classes; we call its vertex 𝑣 P 𝐿0 the apex and the antipodal vertex 𝑐ℎ P 𝐿ℎ its meeting vertex. Encoding. Following [42], we split every candidate cycle at its apex and its meeting vertex into a backward half 𝑣 Ñ 𝑐 1 Ñ ¨ ¨ ¨ Ñ 𝑐ℎ and a forward half 𝑐ℎ Ñ 𝑐ℎ`1 Ñ ¨ ¨ ¨ Ñ 𝑐 2ℎ´1 Ñ 𝑣, of ℎ edges each, and maintain one copy of Qℎ per half, both exposing the meeting vertex as the output attribute 𝑥 1 . In the forward copy, the relation 𝑅 𝑗 , for 1 ď 𝑗 ď ℎ ´ 1, receives every edge p𝑎, 𝑏q P 𝐸𝐺 with 𝑎 P 𝐿ℎ´1` 𝑗 and 𝑏 P 𝐿ℎ` 𝑗 ; in the backward copy, 𝑅 𝑗 receives the reversed tuple p𝑎, 𝑏q for every edge p𝑏, 𝑎q P 𝐸𝐺 with 𝑎 P 𝐿ℎ`1´ 𝑗 and 𝑏 P 𝐿ℎ´ 𝑗 . These tuples carry annotation 1 and are inserted up front. We process the vertices of 𝐿0 in a single pass; as in Lemma 4.13, no blocks or resets are needed, since the monotone sequence of length |𝐷| covers all |𝐿0 | ď 𝑛 vertices. For the ℓ-th apex 𝑣, we insert into 𝑅ℎ of the forward copy the tuple p𝑤q for every in-edge p𝑤, 𝑣q P 𝐸𝐺 with 𝑤 P 𝐿2ℎ´1 , and into 𝑅ℎ of the backward copy the tuple p𝑤q for every out-edge p𝑣, 𝑤q P 𝐸𝐺 with 𝑤 P 𝐿1 , all with annotation 𝑎 ℓ ; we then enumerate both copies. Let 𝑤 ℓ r𝑢s and 𝑤 ℓ1 r𝑢s be the annotations of the output value 𝑢 in the forward and backward copies after the ℓ-th apex is processed, with value 0 if 𝑢 is not enumerated. We report that 𝑣 lies on a layered 2ℎ-cycle if and only if some output value 𝑢 satisfies both 𝑤 ℓ ´1 r𝑢s ă 𝑤 ℓ r𝑢s and 𝑤 ℓ1 ´1 r𝑢s ă 𝑤 ℓ1 r𝑢s. Correctness. As the internal edges carry annotation 1, every layered path of ℎ ´ 1 edges from 𝑢 to an endpoint tuple contributes exactly that endpoint’s annotation. Hence 𝑤 ℓ r𝑢s is the ‘-aggregate of the rank-1 terms 𝑎 ℓ 1 with ℓ 1 ď ℓ, one for each forward walk of ℎ edges from 𝑢 to the ℓ 1 -th apex, and 𝑤 ℓ1 r𝑢s likewise for the backward walks of ℎ edges from the ℓ 1 -th apex to 𝑢. Since 𝑎 ℓ strictly dominates every earlier term, the ‘-strict order gives, exactly as in Theorem 4.6, that 𝑤 ℓ ´1 r𝑢s ă 𝑤 ℓ r𝑢s if and only if 𝑢 reaches the current apex 𝑣 by a forward walk, and 𝑤 ℓ1 ´1 r𝑢s ă 𝑤 ℓ1 r𝑢s if and only if 𝑣 reaches 𝑢 by a backward one; the two walks together close a layered 2ℎ-cycle through 𝑣 with meeting vertex 𝑢, and conversely, every layered 2ℎ-cycle through 𝑣 produces both strict increases at its meeting vertex. For the order argument, we count the rank-1 terms as in Lemma 4.13: a term of 𝑤 ℓ r𝑢s or 𝑤 ℓ1 r𝑢s is identified with a tuple of ℎ vertices, the ℎ ´ 1 later vertices of a layered walk leaving 𝑢 together with the vertex of 𝐿0 whose insertions produced the matching endpoint tuple. By the product bound above, there are at most 𝑛ℎ ď |𝐷|ℎ´1 such tuples, so every value involved aggregates at most |𝐷|ℎ´1 rank-1 terms and lies in the domain of 𝐴p|𝐷 |ℎ´1,1q , and the ‘-strict order assumed in the lemma covers the order argument.
36
Qichen Wang and Xiao Hu
Running time. The database size is |𝐷| “ Θp𝑚q, and 𝑛 “ 𝑚 pℎ´1q{ℎ as before. The reduction has two cost components. First, the insertions: ř the internal relations of the two copies hold 𝑂p𝑚q tuples, and the endpoint relations receive 𝑣 𝑂pdegp𝑣qq “ 𝑂p𝑚q tuples in total, so at 𝑂p|𝐷|pℎ´1q{ℎ´𝜖 q amortized update time they cost 𝑂p𝑚 ¨ 𝑚 pℎ´1q{ℎ´𝜖 q “ 𝑂p𝑚 p2ℎ´1q{ℎ´𝜖 q. Second, the enumeration: each of the 𝑂p𝑛q apexes triggers an enumeration of both copies, and a copy returns at most 𝑛 output values at delay 𝑂p|𝐷|1{ℎ´𝜖 q, for 𝑂p𝑛 ¨ 𝑛 ¨ 𝑚 1{ℎ´𝜖 q “ 𝑂p𝑚 p2ℎ´2q{ℎ`1{ℎ´𝜖 q “ 𝑂p𝑚 p2ℎ´1q{ℎ´𝜖 q in total. The two components sum to 𝑂p𝑚 p2ℎ´1q{ℎ´𝜖 q “ 𝑂p𝑚 p2𝑘 ´2q{𝑘 ´𝜖 q for the even cycle length 𝑘 “ 2ℎ, and summing over the 𝑂plog 𝑛q colorings adds a logarithmic factor, absorbed into the polynomial 1 slack. Hence, even 2ℎ-cycle detection is solved in 𝑂p𝑚 p2𝑘 ´2q{𝑘 ´𝜖 q time for some constant 𝜖 1 ą 0, contradicting Theorem 4.11 and thus the Combinatorial 𝑘-Clique Conjecture. □ B.3
Proof of Lemma 4.15
Proof of Lemma 4.15. We reduce from the OuMv𝑑 problem with 𝛾 “ 𝑑 ´ 1, i.e., the OuMv𝑘 Conjecture with 𝑘 “ 𝑑 and 𝑛𝑑 ´1 rounds. Encoding. We encode the tensor 𝑀 by the 𝑑-ary relation 𝑅1 and the 𝑗-th vector stream by the unary relation 𝑅 𝑗 `1 , for every 𝑗 P r𝑑s. Re-inserting a tupleÀ accumulates its annotation, so after the vectors of rounds 1, ¨ ¨ ¨ , ℓ have been inserted, 𝑅 𝑗 `1 r𝑖s “ ℓ 1 : 𝑢 p 𝑗 q of round ℓ 1 sets 𝑖 𝑎 ℓ 1 , and the annotation of the nullary query 𝑄𝑑 equals â à 𝑅1 r𝑖 1, ¨ ¨ ¨ , 𝑖𝑑 s b 𝑅 𝑗 `1 r𝑖 𝑗 s. 𝑗 Pr𝑑 s
p𝑖 1 ,¨¨¨ ,𝑖𝑑 q: 𝑀𝑖 1 ¨¨¨𝑖𝑑 “1
Expanding the products by distributivity, this annotation is the ‘-aggregate of the contributions of all witnesses, where a witness is a tuple p𝑖 1, ¨ ¨ ¨ , 𝑖𝑑 , ℓ1, ¨ ¨ ¨ , ℓ𝑑 q such that 𝑀𝑖 1 ¨¨¨𝑖𝑑 “ 1 and, for every 𝑗 P r𝑑s, the 𝑗-th vector of round ℓ 𝑗 sets position 𝑖 𝑗 ; its contribution is the rank-𝑑 product term 𝑎 ℓ1 b ¨ ¨ ¨ b 𝑎 ℓ𝑑 . The 2𝑑 databases. Generalizing the two-database construction of Theorem 4.5, we maintain one database for every subset 𝑇 Ď r𝑑s of the vector positions, 2𝑑 in total, which is a constant under data complexity. Into every database we insert the tuple p𝑖 1, ¨ ¨ ¨ , 𝑖𝑑 q into 𝑅1 with annotation 1 for every entry with 𝑀𝑖 1 ¨¨¨𝑖𝑑 “ 1. We process the rounds in consecutive blocks of length 𝑚 “ |𝐷|𝜂 , and reset all databases between blocks from a stored snapshot of the tensor part, exactly as in Theorem 4.5. Consider the ℓ-th round of a block, with vectors 𝑢 p1q, ¨ ¨ ¨ , 𝑢 p𝑑 q carrying the round annotation 𝑎 ℓ . In the database of 𝑇 we perform three steps: (i) for every 𝑖 P 𝑇 , insert the tuple p𝑗q into 𝑅𝑖 `1 with p𝑖 q annotation 𝑎 ℓ for every 𝑗 P r𝑛s with 𝑢 𝑗 “ 1; (ii) issue the enumeration query and let 𝑓 p𝑇 q be the returned annotation; (iii) insert the remaining vectors, those of positions 𝑖 R 𝑇 , in the same way, so that every database has received all 𝑑 current vectors before the next round begins. We answer the round true if and only if à à 𝑓 p𝑇 q ‰ 𝑓 p𝑇 q. 𝑇 : |𝑇 | even
𝑇 : |𝑇 | odd
Correctness. At the query time of round ℓ, the database of 𝑇 has received exactly the round-ℓ vectors of the positions in 𝑇 (step (i)), on top of all vectors of the previous rounds (step (iii) of earlier rounds). Call 𝑝 “ t𝑗 P r𝑑s : ℓ 𝑗 “ ℓu the current pattern of a witness, i.e., the set of coordinates that use the current round; its remaining coordinates satisfy ℓ 𝑗 ă ℓ and are present in every database. Hence a witness is visible to the database of 𝑇 , and its contribution is one of the terms ‘-aggregated in 𝑓 p𝑇 q, if and only if 𝑝 Ď 𝑇 . Fix a witness with current pattern 𝑝 and contribution 𝑐 “ 𝑎 ℓ1 b¨ ¨ ¨b𝑎 ℓ𝑑 , and count the multiplicity of 𝑐 on each side. Writing every superset 𝑇 Ě 𝑝 as 𝑇 “ 𝑝 Y 𝑆 with 𝑆 Ď r𝑑sz𝑝, its cardinality is |𝑝| ` |𝑆|, so the parity of |𝑇 | is determined by that of |𝑆|.
Answering Conjunctive Queries with Aggregations under Updates
37
‚ If 𝑝 ‰ r𝑑s, the complement r𝑑sz𝑝 is non-empty, and a non-empty set has equally many even- and odd-sized subsets, namely 2𝑑 ´|𝑝 |´1 each. Thus 𝑐 is visible to 2𝑑 ´|𝑝 |´1 even-sized 𝑇 and 2𝑑 ´|𝑝 |´1 odd-sized 𝑇 , and contributes to both sides with the same multiplicity. ‚ If 𝑝 “ r𝑑s (an all-current witness), the only superset is 𝑇 “ r𝑑s itself, so 𝑐 appears once, on the side matching the parity of 𝑑, and never on the other side. Let 𝐶 be the ‘-aggregate of the contributions of all witnesses whose pattern is a proper subset of r𝑑s, taken with the multiplicity 2𝑑 ´|𝑝 |´1 above; by the count, 𝐶 occurs identically on both sides. Let 𝑊 be the ‘-aggregate of the all-current contributions, each equal to 𝑎 ℓb𝑑 “ 𝑎 ℓ b ¨ ¨ ¨ b 𝑎 ℓ . Then the two sides are 𝐶 and 𝐶 ‘ 𝑊 , with 𝑊 falling on the side of parity 𝑑. An all-current witness exists if and only if the current vectors 𝑢 p1q ˆ ¨ ¨ ¨ ˆ 𝑢 p𝑑 q intersect 𝑀, so it remains to test 𝐶 ă 𝐶 ‘ 𝑊 . If no all-current witness exists, 𝑊 is empty, the two sides are equal, and we correctly answer false. Otherwise, every term of 𝐶 is a witness contribution with a proper current pattern, hence has at least one factor 𝑎 ℓ𝑗 with ℓ 𝑗 ă ℓ. Fix such a term and such a factor: raising every other factor bp𝑑 ´1q
to 𝑎 ℓ by the order compatibility gives 𝑎 ℓ1 b ¨ ¨ ¨ b 𝑎 ℓ𝑑 ď 𝑎 ℓ𝑗 b 𝑎 ℓ
, in which 𝑎 ℓ𝑗 is the strictly bp𝑑 ´1q
smallest factor, and one application of the b-strict order gives 𝑎 ℓ𝑗 b 𝑎 ℓ ă 𝑎 ℓb𝑑 . Hence 𝑎 ℓb𝑑 strictly dominates every term of 𝐶. Each side ‘-aggregates at most 2𝑑 ´1 ¨ |𝐷| ¨ 𝑚𝑑 “ 2𝑑 ´1 |𝐷|1`𝑑𝜂 product terms of rank 𝑑: there are at most |𝐷| nonzero tensor entries, at most 𝑚 “ |𝐷|𝜂 round choices for each of the 𝑑 coordinates within a block, and 2𝑑 ´1 databases in each parity class. Hence 𝐶, 𝑊 , and 𝐶 ‘ 𝑎 ℓb𝑑 all lie in the domain of 𝐴p2𝑑 ´1 |𝐷 |1`𝑑𝜂 ,𝑑 q , and the ‘-strict order gives 𝐶 ă 𝐶 ‘ 𝑎 ℓb𝑑 . Since the remaining all-current contributions are positive, 𝐶 ‘ 𝑎 ℓb𝑑 ď 𝐶 ‘ 𝑊 , so 𝐶 ă 𝐶 ‘ 𝑊 and we correctly answer true. Running time. The database size is |𝐷| “ Θp𝑛𝑑 q: the tensor relation contributes at most 𝑛𝑑 tuples, and each block inserts at most 𝑑𝑛𝑚 “ 𝑂p𝑛𝑑 q vector tuples before being reset. There are r𝑛𝑑 ´1 {𝑚s “ 𝑂p𝑛𝑑 ´1 |𝐷|´𝜂 q blocks, and each reset restores the stored images of the 2𝑑 indexes, whose sizes are 𝑂p|𝐷|1`𝜂 ´𝜖 q by the space hypothesis, for a total of 𝑂p2𝑑 𝑛𝑑 ´1 |𝐷|´𝜂 ¨|𝐷|1`𝜂 ´𝜖 q “ 𝑂p𝑛 p𝑑 ´1q`𝑑 ´𝑑𝜖 q “ 𝑂p𝑛 2𝑑 ´1´𝑑𝜖 q. Across all rounds, the 2𝑑 databases receive 𝑂p2𝑑 ¨ 𝑛𝑑 ´1 ¨ 𝑑𝑛q “ 𝑂p𝑛𝑑 q vector insertions, which cost 𝑂p𝑛𝑑 ¨ |𝐷|p𝑑 ´1q{𝑑 ´𝜖 q “ 𝑂p𝑛 2𝑑 ´1´𝑑𝜖 q under the assumed amortized update time. The 𝑂p2𝑑 𝑛𝑑 ´1 q enumeration calls cost 𝑂p|𝐷|1´𝜖 q “ 𝑂p𝑛𝑑 ´𝑑𝜖 q each, for a total of 𝑂p𝑛 2𝑑 ´1´𝑑𝜖 q. Altogether, the OuMv𝑑 instance with 𝑛𝑑 ´1 rounds is solved in 𝑂p𝑛 2𝑑 ´1´𝑑𝜖 q “ 𝑂p𝑛 p𝑑 ´1q`𝑑 ´𝑑𝜖 q time after linear preprocessing, which contradicts the OuMv𝑘 Conjecture with 𝛾 “ 𝑑 ´ 1 and 𝑘 “ 𝑑, as 𝜖 ą 0. □ C
Missing Proofs in Section 4.3
Proof of Theorem 4.7. Let 𝑒 1, 𝑒 2, 𝑒 3 P E and 𝑥 1, 𝑥 2 form the D-hierarchy-core of Q. Given an insertion-only K-sequence 𝑆 1 of Qhier , we construct an insertion-only K-sequence 𝑆 for Q as follows. For every relation 𝑒 P E with 𝑒 X t𝑥 1, 𝑥 2 u “ H, we add the update p˚, ´8, 1, 𝑅𝑒 q as above. For the remaining relations: ‚ if 𝑥 1, 𝑥 2 P 𝑒, for every update p𝑡, 𝑠, 𝛿, 𝑅1 q in 𝑆 1 , we add p𝑡 1, 𝑠, 1, 𝑅𝑒 q if 𝑒 ‰ 𝑒 2 or p𝑡 1, 𝑠, 𝛿, 𝑅𝑒 q if 𝑒 “ 𝑒 2 to 𝑆, where 𝜋𝑥 1,𝑥 2 𝑡 1 “ 𝑡 and 𝜋𝑥 𝑡 1 “ ˚ for every attribute 𝑥 P 𝑒zt𝑥 1, 𝑥 2 u; ‚ if 𝑥 1 P 𝑒 but 𝑥 2 R 𝑒, for every update p𝑡, 𝑠, 𝛿, 𝑅2 q in 𝑆 1 , we add p𝑡 1, 𝑠, 1, 𝑅𝑒 q to 𝑆 if 𝑒 ‰ 𝑒 1 or p𝑡 1, 𝑠, 𝛿, 𝑅𝑒 q to 𝑆 if 𝑒 “ 𝑒 1 , where 𝜋𝑥 1 𝑡 1 “ 𝑡 and 𝜋𝑥 𝑡 1 “ ˚ for every attribute 𝑥 P 𝑒zt𝑥 1 u; ‚ if 𝑥 2 P 𝑒 but 𝑥 1 R 𝑒, for every update p𝑡, 𝑠, 𝛿, 𝑅3 q in 𝑆 1 , we add p𝑡 1, 𝑠, 1, 𝑅𝑒 q to 𝑆 if 𝑒 ‰ 𝑒 3 or p𝑡 1, 𝑠, 𝛿, 𝑅𝑒 q to 𝑆 if 𝑒 “ 𝑒 3 , where 𝜋𝑥 2 𝑡 1 “ 𝑡 and 𝜋𝑥 𝑡 1 “ ˚ for every attribute 𝑥 P 𝑒zt𝑥 2 u. Here 𝑅1 p𝑥 1, 𝑥 2 q, 𝑅2 p𝑥 1 q, and 𝑅3 p𝑥 2 q are the three relations of Qhier . By the definition of the Dhierarchy-core, 𝑥 1, 𝑥 2 P ȳ are non-output attributes of Q, and every attribute outside t𝑥 1, 𝑥 2 u takes
38
Qichen Wang and Xiao Hu
the single value ˚, so Q has at most one result tuple, whose annotation equals the nullary annotation of Qhier multiplied by 1s; the reduction reads it with a single enumeration call per round. Each update of 𝑆 1 is mapped to at most |E| “ 𝑂p1q updates, so |𝐷| changes by at most a constant factor, and the bounds transfer from Theorem 4.5. □ Proof of Theorem 4.8. Let 𝑒 1, 𝑒 2 P E and 𝑥 1, 𝑥 2 form the q-core of Q. Given an insertion-only K-sequence 𝑆 1 of Qqcore , we construct an insertion-only K-sequence 𝑆 for Q as follows. For every relation 𝑒 P E with 𝑒 X t𝑥 1, 𝑥 2 u “ H, we add the update p˚, ´8, 1, 𝑅𝑒 q, i.e., a single dummy tuple with all attributes set to the fixed value ˚, inserted with annotation 1 in the initial database. For the remaining relations, we distinguish three cases: ‚ if 𝑥 1, 𝑥 2 P 𝑒, for every update p𝑡, 𝑠, 𝛿, 𝑅1 q in 𝑆 1 , we add p𝑡 1, 𝑠, 𝛿, 𝑅𝑒 q to 𝑆, where 𝜋𝑥 1,𝑥 2 𝑡 1 “ 𝑡 and 𝜋𝑥 𝑡 1 “ ˚ for every attribute 𝑥 P 𝑒zt𝑥 1, 𝑥 2 u; ‚ if 𝑥 2 P 𝑒 but 𝑥 1 R 𝑒, for every update p𝑡, 𝑠, 𝛿, 𝑅2 q in 𝑆 1 , we add p𝑡 1, 𝑠, 𝛿, 𝑅𝑒 q to 𝑆, where 𝜋𝑥 2 𝑡 1 “ 𝑡 and 𝜋𝑥 𝑡 1 “ ˚ for every attribute 𝑥 P 𝑒zt𝑥 2 u; ‚ if 𝑥 1 P 𝑒 but 𝑥 2 R 𝑒, for every update p𝑡, 𝑠, 𝛿, 𝑅1 q in 𝑆 1 , we add p𝑡 1, ´8, 1, 𝑅𝑒 q to 𝑆, where 𝜋𝑥 1 𝑡 1 “ 𝑡 and 𝜋𝑥 𝑡 1 “ ˚ for every attribute 𝑥 P 𝑒zt𝑥 1 u. Whenever an enumeration query is issued to Qqcore , we issue an enumeration query to Q. At any timestamp, the results of Q and Qqcore are in one-to-one correspondence, with equal annotations up to a fixed b-multiplication by 1: every relation avoiding 𝑥 1, 𝑥 2 contributes the dummy tuple with annotation 1, every relation containing 𝑥 1 alone contributes the 1-annotated copy of the corresponding 𝑅1 -tuple, and the annotations of the tuples carrying p𝑥 1, 𝑥 2 q and 𝑥 2 replicate those of 𝑅1 and 𝑅2 . Each update of 𝑆 1 is mapped to at most |E| “ 𝑂p1q updates, so |𝐷| changes by at most a constant factor, and the time, delay, and space bounds transfer verbatim from Theorem 4.6. □