The Role of Semirings in Incremental View Maintenance
arXiv:2606.07795v1 [cs.DB] 5 Jun 2026
EDEN CHMIELEWSKI, University of Zurich, Switzerland ANDREI DRAGHICI, University of Zurich, Switzerland DAN OLTEANU, University of Zurich, Switzerland HAOZHE ZHANG, University of Zurich, Switzerland We study the problem of incremental view maintenance (IVM) under inserts to 𝐾-databases, where 𝐾 is a commutative semiring without additive inverse. The key observation put forward in this paper is that the complexity of the IVM problem depends fundamentally on the underlying semiring. We introduce a class of conjunctive queries called 𝑝-hierarchical and show that for any 𝑝-hierarchical query with fractional hypertree width fhtw and any insert-only update sequence of length 𝑁 to an initially empty 𝐾-database over an arbitrary semiring 𝐾 without additive inverse, we can construct a data structure that can be updated in amortized O (𝑁 fhtw−1 ) time and can support constant delay enumeration of the query result. In particular, the amortized update time for any 𝛼-acyclic 𝑝-hierarchical query is constant. We also give conditional lower bounds showing that any conjunctive query without self-joins that is not 𝑝-hierarchical cannot be maintained with amortized constant update time and constant enumeration delay under inserts to 𝐾-databases. Here, 𝐾 can be the natural semiring and its generalizations to the provenance and covariance semirings or any idempotent and strictly ordered semiring such as the tropical semiring. When put together, our upper and lower bounds imply a dichotomy for the insert-only maintenance of conjunctive queries without self-joins and the aforementioned semirings: A query can be maintained with amortized constant update time and constant enumeration delay if and only if it is 𝛼-acyclic 𝑝-hierarchical. Our dichotomy is sandwiched between two known maintenance dichotomies, both for the Boolean semiring. On the one hand, tractable maintenance under inserts-only can only be achieved for the free-connex 𝛼-acyclic queries, which form a strict superset of the 𝛼-acyclic 𝑝-hierarchical queries. On the other hand, tractable maintenance under both inserts and deletes can only be achieved for the 𝑞-hierarchical queries, which form a strict subset of the 𝛼-acyclic 𝑝-hierarchical queries.
1
Introduction
The Incremental View Maintenance (IVM) problem for conjunctive queries is fundamental to databases [25]: Given a query and a database subject to a sequence of single-tuple updates, the IVM problem is to maintain the result of the query under the updates and to allow for the enumeration of the tuples in the query result after each update. A key observation that motivates the study of this problem is that maintaining the result of a query under updates can be more efficient than re-evaluating the query from scratch. Several modern IVM systems, including DBToaster [21], DynYannakakis [14], F-IVM [16, 25], CROWN [30], RAIVM [27], and DBSP [8], have been recently developed in academia and industry and implement state-of-the-art insights on how to efficiently maintain queries under updates [25]. The deployment of such systems is rarely restricted to maintaining plain conjunctive queries over standard relational databases. Instead, IVM systems often maintain the provenance, multiplicities, or covariance information associated with the query result. Such more sophisticated tasks can be modeled as query maintenance over 𝐾-databases [12], where tuples are mapped to payloads from a commutative semiring 𝐾. This calls for a systematic study of IVM over 𝐾-databases, such as over the provenance semiring. The main question addressed in this paper is whether the choice of the semiring 𝐾 can influence the tractability of query maintenance: Are there conjunctive queries that can be maintained optimally for some semirings and not for others? Authors’ Contact Information: Eden Chmielewski, [email protected], University of Zurich, Department of Informatics, Zurich, Switzerland; Andrei Draghici, [email protected], University of Zurich, Department of Informatics, Zurich, Switzerland; Dan Olteanu, [email protected], University of Zurich, Department of Informatics, Zurich, Switzerland; Haozhe Zhang, [email protected], University of Zurich, Department of Informatics, Zurich, Switzerland.
2
Eden Chmielewski, Andrei Draghici, Dan Olteanu, and Haozhe Zhang
This paper answers positively this question. It proceeds in two steps. First, it gives a syntactic characterization of all conjunctive queries that admit tractable, indeed optimal, maintenance under inserts to 𝐾-databases for a class of semirings that do not admit additive inverse. This class, denoted by K in this paper, consists of: the natural semiring and generalizations thereof (e.g., the provenance semiring [12] and the covariance semiring [16]) and any idempotent and strictly ordered semiring such as the tropical semiring. By tractable maintenance we mean maintenance with amortized constant update time and constant enumeration delay. The queries in this class are called 𝛼-acyclic p-hierarchical, a new notion introduced in this paper. Furthermore, we show that any non-p-hierarchical query without self-joins cannot admit tractable maintenance for the aforementioned semirings, unless widely held conjectures fail. When put together, our upper and lower bounds imply a dichotomy for the insert-only maintenance of conjunctive queries without self-joins and the aforementioned semirings: A query can be maintained with amortized constant update time and constant enumeration delay if and only if it is 𝛼-acyclic 𝑝-hierarchical. Second, we observe that our dichotomy does not apply to the Boolean semiring. On one hand, all free-connex 𝛼-acyclic queries admit tractable maintenance under inserts to B-databases, while all non-free-connex 𝛼-acyclic queries without self-joins cannot admit tractable maintenance [2, 5, 30]1 . All 𝛼-acyclic p-hierarchical queries are free-connex, yet there are free-connex 𝛼-acyclic queries that are not p-hierarchical. On the other hand, all q-hierarchical queries admit tractable maintenance under inserts and deletes to B-databases, while all non-q-hierarchical queries without self-joins cannot admit tractable maintenance [6]. Furthermore, all q-hierarchical queries are 𝛼-acyclic and p-hierarchical, while there are acyclic p-hierarchical queries that are not q-hierarchical. Our dichotomy for 𝛼-acyclic p-hierarchical queries is thus strictly sandwiched between the dichotomies for free-connex 𝛼-acyclic queries and q-hierarchical queries, as illustrated in Fig. 1. The semirings considered in this paper enable practical IVM applications not available to IVM engines that only work with databases over the Boolean semiring. For instance, the tropical semiring can be used to express the computation of single-source and all-pairs shortest paths in graphs [23]. The provenance semiring is used to: quantify the contributions of input facts to the query result and explain the query result [3, 4, 7, 18]; capture the lineage over random events in probabilistic databases [28]; and recover bag semantics via tuple multiplicities. The covariance semiring (defined over natural numbers) captures the maintenance of the covariance matrix of features defined by the data columns in the result of queries over databases [16, 24]. Further works on semiring-annotated databases. The theoretical foundations of 𝐾-databases [12] have been extensively explored across various classical database problems. Early works established the decidability and complexity bounds for the containment and equivalence of conjunctive queries under provenance semiring semantics [10], and generalized the problem of exact query reformulation using views to semiring-annotated relations [11]. As applications demand richer metadata, research also formalized the algebraic evaluation of multiple, potentially dependent annotations drawn from different semirings [22]. Closely related to IVM under inserts is the semi-naïve evaluation of recursive Datalog queries, such as reachability: Both avoid redundant computation by using the delta of the query, i.e., only focus on the changes to the output as direct consequence of the change in the input. Yet whereas IVM performs incremental computation under inserts to the 1 All conjunctive queries that are not free-connex 𝛼-acyclic cannot admit constant delay enumeration after O (𝑁 ) prepro-
cessing time over a database of size 𝑁 , unless the Boolean Matrix Multiplication conjecture fails [5]. This also implies that such queries cannot be maintained with amortized constant update time and constant enumeration delay, since we can simulate the query evaluation over a static database of size 𝑁 as a sequence of 𝑁 single-tuple inserts to an initially empty database. Then, if each insert would take amortized constant time, then we would need an overall O (𝑁 ) computation time of the query result, from which we would enumerate its tuples with constant delay.
The Role of Semirings in Incremental View Maintenance
3
𝛼-acyclic
free-connex 𝛼-acyclic
Insert-only [2, 30] Boolean Semiring
𝑝-hierarchical 𝛼-acyclic
Insert-only [This paper] K Semirings
𝑞-hierarchical
Insert-delete [6] Boolean Semiring
Fig. 1. The strict containment hierarchy of tractable classes of conjunctive queries. Each continuous line is a separation result: Any query in the class inside the line can be maintained with constant delay enumeration and (amortized) constant update time over 𝐾-databases, while any query without self-joins outside the class cannot enjoy such tractable maintenance. Such dichotomies are known for: 𝑞-hierarchical queries and the Boolean semiring [6]; free-connex 𝛼-acyclic queries and the Boolean semiring [2, 30]; and the 𝛼-acyclic 𝑝-hierarchical queries and the class K of semirings (this paper).
input database, semi-naïve evaluation generates inserts to the query result which is used as input at the next iteration of a recursive fixed-point loop. Recent work [19] introduced an extension of recursive Datalog queries to 𝐾-databases and studied under which conditions on the semiring 𝐾 the semi-naïve evaluation of recursive queries over 𝐾-databases terminates. It does not consider the time complexity to process each insert and does not provide a characterization of queries with tractable maintenance under inserts. We note that by unfolding the linear recursion for reachability a fixed number of steps we obtain path queries over binary 𝐾-relations. These queries are 𝛼-acyclic, yet they are not p-hierarchical and not even free-connex. Therefore, they are not tractable for the semirings considered in this paper, not even for the Boolean semiring. Contributions. To summarize, the contributions of this paper are as follows. 1. We introduce the notion of p-hierarchical queries (Sec. 3). The p-hierarchical queries are exactly those conjunctive queries expressible as full conjunctive queries with body atoms defined by q-hierarchical queries, whose free variables occur in all atoms. We also show that the fractional hypertree width of a p-hierarchical query is the same as for its Boolean version. When restricted to 𝛼-acyclicity, p-hierarchical queries sit between q-hierarchical and free-connex queries: The class of 𝛼-acyclic p-hierarchical strictly includes the class of q-hierarchical queries [6] and is strictly included in the class of free-connex 𝛼-acyclic queries [5]. 2. We establish an upper bound for maintaining p-hierarchical queries (Sec. 4): Theorem 1. Let any conjunctive query 𝑄 and a sequence of 𝑁 inserts to an initially empty 𝐾database over a semiring 𝐾 without additive inverse. If 𝑄 is p-hierarchical, then it can be maintained with O (𝑁 fhtw ) preprocessing time, O (1) enumeration delay, and amortized O (𝑁 fhtw−1 ) update time per single-tuple insert, where fhtw is the fractional hypertree width of the Boolean version of 𝑄. Since fhtw = 1 for any 𝛼-acyclic p-hierarchical query, Thm. 1 guarantees that such queries admit tractable maintenance.
4
Eden Chmielewski, Andrei Draghici, Dan Olteanu, and Haozhe Zhang
3. We further prove conditional lower bounds on the amortized update time for non-p-hierarchical queries (Sec. 5): Such queries cannot be maintained in amortized constant time under inserts. We give lower bounds for the aforementioned class K of semirings. These lower bounds are conditional on the Online Matrix-vector (OMv) conjecture [13], a widely held conjecture for streaming problems. Theorem 2. Given any conjunctive query 𝑄 without self-joins that is not p-hierarchical, there is 3 1 no algorithm that maintains 𝑄 with O (𝑁 2 −𝛾 ) preprocessing time, O (𝑁 2 −𝛾 ) enumeration delay, and 1 O (𝑁 2 −𝛾 ) update time amortized over a sequence of 𝑁 inserts to an initially empty 𝐾-database, for any 𝐾 ∈ K and 𝛾 > 0, unless the OMv conjecture fails. 4. The second and third contributions imply a new dichotomy that characterizes the tractability of the IVM problem for conjunctive queries over 𝐾-databases: Corollary 3 (Theorems 1 and 2). Let any conjunctive query 𝑄 and a sequence of 𝑁 inserts to an initially empty 𝐾-database, where 𝐾 ∈ K. • If 𝑄 is p-hierarchical, then it can be maintained with O (𝑁 ) preprocessing time, O (1) enumeration delay, and amortized O (1) update time per single-tuple insert. • If 𝑄 is not p-hierarchical and has no self-joins, then there is no algorithm that maintains 𝑄 3 1 3 with O (𝑁 2 −𝛾 ) preprocessing time, O (𝑁 2 −𝛾 ) enumeration delay, and O (𝑁 2 −𝛾 ) amortized update time per single-tuple insert, for any 𝛾 > 0, unless the OMv conjecture fails. 2
Preliminaries
In this section we introduce concepts and notation used in the rest of the paper, following closely prior work [1, 16]. Data and Queries. A schema X is a tuple of attributes or variables (𝑋 1, . . . , 𝑋𝑛 ), which we also conveniently see as a set to allow set operations on tuples. For each variable 𝑋𝑖 ∈ X, let Dom(𝑋𝑖 ) denote its domain. A tuple x of values over the schema X is an element of the set Dom(X) = Dom(𝑋 1 ) × · · · × Dom(𝑋𝑛 ). A commutative ring (𝐾, +, ·, 0, 1) consists of a set 𝐾 equipped with two binary operations (+) and (·), such that (𝐾, +, 0) is an abelian group, (𝐾, ·, 1) is a commutative monoid, and multiplication distributes over addition. A semiring satisfies the same axioms except that (𝐾, +, 0) is required only to be a commutative monoid (i.e., additive inverses need not exist). In this paper, we only consider commutative semirings that are not rings. Examples of such semirings are the natural sum-product semiring (N, +, ·, 0, 1) and the Boolean semiring ({true, false}, ∨, ∧, false, true). We assume without loss of generality that the semirings have elements of constant size and their operations (+) and (·) that take constant time. Let (𝐾, +, ·, 0, 1) be a semiring. A 𝐾-relation 𝑅 over a schema X and the semiring 𝐾 is a function 𝑅 : Dom(X) → 𝐾 that maps tuples of values over X to elements of 𝐾 [12]. A tuple x ∈ Dom(X) is called a key, and 𝑅(x) its payload in 𝑅. When applying set operations to 𝑅, we treat it as the set of tuples x with 𝑅(x) ≠ 0. For instance, the size of 𝑅, denoted by |𝑅|, is the size of the set {x | 𝑅(x) ≠ 0}. A 𝐾-database D is a collection of relations over the same semiring 𝐾. Its size |D | is the sum of the sizes of its 𝐾-relations. We express conjunctive queries as functional aggregate queries over a semiring 𝐾 [20]: ∑︁ 𝑄 (F) = 𝑅1 (X1 ) · . . . · 𝑅𝑘 (Xk ), (1) B
Í
where and (·) are the summation and multiplication operations from the semiring 𝐾, respectively. 𝑅1, . . . , 𝑅𝑘 are relation symbols, each Xi is a schema, and each 𝑅𝑖 (Xi ) is an atom of 𝑄. We assume distinct relation symbols in a query. If several relation symbols correspond to the same physical
The Role of Semirings in Incremental View Maintenance
5
database relation, which happens in case 𝑄 has self-joins, then we assume without loss of generality (i.e., without changes in the data complexities stated in the paper) that each such atom gets its own def Ð copy of the database relation. The set of variables of 𝑄 is vars(𝑄) = 𝑖 ∈ [𝑘 ] Xi . The free variables of 𝑄 are F = Free(𝑄) ⊆ vars(𝑄), while B = Bound(𝑄) = vars(𝑄) \ F are the bound variables. If F = vars(𝑄), then 𝑄 is a full (or join) query. By at(𝑄) and at(𝑌 ) we denote the set of all atoms of 𝑄 and the set of all atoms 𝑅𝑖 (Xi ) with 𝑌 ∈ Xi , respectively. For compactness, we write a set of variables as the concatenation of their names, e.g., {𝑋, 𝑌 Í , 𝑍 } becomes 𝑋𝑌 𝑍 while {𝑋 } becomes 𝑋 . The Boolean version of 𝑄 is defined as the query 𝑄 () = vars(𝑄 ) 𝑅1 (X1 ) · . . . · 𝑅𝑘 (Xk ) that has no free variables. The marginalization of variables Y ⊆ X from a relation 𝑅 with schema X, denoted by 𝑆 (Z) = Í def Í {𝑅(x) | x ∈ Dom(X) ∧ z = x.Z}, Y 𝑅(X) for Z = X \ Y, is defined by: ∀z ∈ Dom(Z) : 𝑆 (z) = where x.Z is the restriction of the tuple x to the values of the variables in schema Z. The union of two relations 𝑅 and 𝑆 with the same schema X, denoted by 𝑇 = 𝑅 ∪ 𝑆, is defined as: ∀x ∈ Dom(X) : 𝑇 (x) = 𝑅(x) + 𝑆 (x). Thus, the semantics of 𝑄 in Eq. (1) are defined as the relation: Í ∀f ∈ Dom(F) : 𝑄 (f) = x∈Dom(vars(𝑄 ) ):x.F=f 𝑅1 (x.X1 ) · . . . · 𝑅𝑘 (x.X𝑘 ). Data Updates. We model database updates as a sequence of single-tuple inserts. When a tuple x is inserted into a relation 𝑅 having schema X, we represent this operation via a delta relation 𝛿𝑅 : Dom(X) → 𝐾. The state of the relation post-update is simply its union with the delta: def
𝑅 = 𝑅 ∪ 𝛿𝑅. To propagate updates through joins, we apply standard delta rules. For a join of two views 𝑉1 (Z1 ) and 𝑉2 (Z2 ), the change is evaluated as 𝛿 (𝑉1 · 𝑉2 ) = (𝛿𝑉1 · 𝑉2 ) ∪ (𝑉1 · 𝛿𝑉2 ) ∪ (𝛿𝑉1 · 𝛿𝑉2 ). For multi-way joins, this rule is applied recursively. In our insert-only framework, where a single physical relation is modified at any given step (say, 𝑉1 ), 𝛿𝑉2 is strictly empty. This simplifies the propagation to 𝛿 (𝑉1 · 𝑉2 ) = 𝛿𝑉1 · 𝑉2 . Updates are defined for joins of relations using the classical delta rule: 𝛿 (𝑉1 (Z1 ) · 𝑉2 (Z2 )) = (𝛿𝑉1 (Z1 ) · 𝑉2 (Z2 )) ∪ (𝑉1 (Z1 ) · 𝛿𝑉2 (Z2 )) ∪ (𝛿𝑉1 (Z1 ) · 𝛿𝑉2 (Z2 )). This generalizes to a join of arbitrary relations by taking 𝑉2 to be the join of relations and applying recursively the delta rule to 𝛿𝑉2 . If only 𝑉1 is changed, then 𝛿𝑉2 = ∅ and 𝛿 (𝑉1 (Z1 ) · 𝑉2 (Z2 )) = 𝛿𝑉1 (Z1 ) · 𝑉2 (Z2 ). Furthermore, delta Í Í operations distribute seamlessly over variable marginalization, meaning 𝛿 ( Y 𝑉 ) = Y 𝛿𝑉 . Finally, recall our assumption regarding distinct relation symbols for self-joins; an insert into a physical database relation triggers independent delta updates for each of its logical copies in the query. Delta View Trees. Our maintenance approach relies on a hierarchical structure of materialized views. We adopt the exact formalism of view trees introduced in [1]. Definition 4 ((Delta) View Tree). [1, Def. 1] A view tree 𝑇 for a query 𝑄 is a rooted tree with the properties: • There is a one-to-one mapping between the leaves of 𝑇 and the atoms of 𝑄. • Each inner node is a view over some variables of 𝑄. • If a node 𝑉 ′ (Y) has a single child node 𝑉 (X), then it is a projection view defined by marginalizÍ ing variables of 𝑉 (X), i.e., 𝑉 ′ (Y) = X\Y 𝑉 (X). Furthermore, every atom of 𝑄 with a variable from X \ Y occurs in the subtree rooted at 𝑉 (X). • If a node 𝑉 (X) has several children 𝑉1 (X1 ), . . . , 𝑉𝑛 (Xn ), for 𝑛 ≥ 2, then it is a join view defined by the natural join of the child views, i.e., 𝑉 (X) = 𝑉1 (X1 ) · . . . · 𝑉𝑛 (Xn ). When a base relation 𝑅 undergoes an update, we denote the updated structure as a delta view tree, 𝛿𝑇𝑅 . In this structure, the leaf 𝑅 is substituted with 𝛿𝑅, and consequently, every view 𝑉 on the path from 𝛿𝑅 up to the root is substituted with its corresponding delta view, 𝛿𝑉 .
6
Eden Chmielewski, Andrei Draghici, Dan Olteanu, and Haozhe Zhang
Following standard conventions [5], we say that a procedure enumerates the output of a query with constant delay if the time elapsed during the following three intervals is strictly bounded by a constant: (i) from the initiation of the enumeration algorithm until the first tuple is produced; (ii) the interval between producing any two successive tuples; and (iii) the time from the final tuple being produced until the algorithm fully terminates. Hypergraphs, Tree Decompositions, and Widths. A hypergraph H is a pair H = (V, E), where V is a set of vertices, and E ⊆ 2 V is a set of hyperedges; each hyperedge 𝑍 ∈ E is a subset of V. Given a CQ as in Eq. 1, the hypergraph of 𝑄 (F) is a query hypergraph H = (V, E, F), where V := vars(𝑄) and E := {𝑍 | 𝑅(𝑍 ) ∈ at(𝑄)}. We identify the query 𝑄 (F) with its query hypergraph H . For a subset 𝑆 ⊆ V, we use 𝑄 [𝑆] = (𝑆, E [𝑆]) to denote the subquery induced by 𝑆, where E [𝑆] = {𝑒 ∩ 𝑆 | 𝑒 ∈ E}. Given the query hypergraph H of 𝑄 (F), a tree decomposition (TD) for H is a pair (𝑇 , 𝜒), where 𝑇 is a tree, and 𝜒 : nodes(𝑇 ) → 2 V such that: • for every hyperedge 𝑍 ∈ E, there exists 𝑡 ∈ nodes(𝑇 ) with 𝑍 ⊆ 𝜒 (𝑡); • for every vertex 𝑋 ∈ V, the set {𝑡 ∈ nodes(𝑇 ) | 𝑋 ∈ 𝜒 (𝑇 )} form a connected subtree of 𝑇 . Each set 𝜒 (𝑡) is called a bag of the TD. A TD (𝑇 , 𝜒) is free-connex if there is a connected subtree 𝑆 Ð of 𝑇 such that 𝑡 ∈nodes(𝑆 ) 𝜒 (𝑡) = F, i.e., the union of the variables appearing in 𝑆 is exactly the set of free variables. Let FTD(H ) denote the set of free-connex TDs of H . Note that for any conjunctive query 𝑄, all the TDs of the Boolean version of 𝑄 are trivially free-connex. A fractional edge cover is a function 𝜌 : E → [0, 1] such that for every vertex 𝑣 ∈ V, the following condition holds (every vertex is covered): ∑︁ 𝜌 (𝑒) ≥ 1 𝑒 ∈ E:𝑣 ∈𝑒
The fractional edge cover number of 𝑄, denoted 𝜌 ∗ (𝑄), is the minimum total weight over all valid fractional edge covers: ∑︁ 𝜌 ∗ (𝑄) = min 𝜌 (𝑒) 𝜌 𝑒∈E
The width of (𝑇 , 𝜒) is defined as width(𝑇 , 𝜒) =
max
𝜌 ∗ (𝑄 [𝜒 (𝑡)])
𝑡 ∈nodes(𝑇 )
Definition 5 (Fractional Hypertree Width (fhtw)). For any query 𝑄 (F) = (V, E), its fractional hypertree width fhtw is defined as: fhtw(𝑄 (F)) =
min (𝑇 ,𝜒 ) ∈FTD(𝑄 (F) )
width(𝑇 , 𝜒)
We call a query 𝑄 acyclic iff there exists a tree decomposition for the hypergraph of 𝑄 in which every bag is covered by an input atom. Notice that the fractional hypertree width of an acyclic query is one. Finally, we present the definition of free-connex acyclic queries. Definition 6 (Free-Connex Acyclic). 𝑄 is free-connex acyclic if the modified query 𝑄 + , constructed by adding a single new atom containing exactly the free variables of 𝑄, remains acyclic. 3
P-Hierarchical Queries
We start by introducing the prior, related class of q-hierarchical queries, which can be maintained with O (1) update time and constant delay enumeration under insert-delete sequences over the Boolean semiring.
The Role of Semirings in Incremental View Maintenance
7
Definition 7 (q-hierarchical). ([6, Def. 3.1]) A conjunctive query 𝑄 is q-hierarchical if for any two variables 𝑋, 𝑌 ∈ vars(𝑄) the following is satisfied: (1) [hierarchical property] at(𝑋 ) ∩ at(𝑌 ) = ∅ or at(𝑋 ) ⊆ at(𝑌 ) or at(𝑌 ) ⊆ at(𝑋 ), and (2) [q property] if at(𝑋 ) ⊊ at(𝑌 ) and 𝑋 ∈ Free(𝑄), then 𝑌 ∈ Free(𝑄). Our main contribution is the syntactic characterization of all tractable conjunctive queries that can be maintained in amortized constant time and allow constant delay enumeration under updates over a variety of semirings. This is the class of p-hierarchical (short for piecewise-hierarchical) queries. In subsequent sections we prove that acyclic p-hierarchical queries are exactly the conjunctive queries that can be maintained under inserts in amortized constant time and allow constant delay enumeration for commonly used semirings such as the natural and the tropical semiring. The key insight behind this class is that under insert-only sequences, the free variables no longer need to satisfy the strict non-overlapping hierarchies required by q-hierarchical queries under insert-delete sequences. Instead, the hierarchical constraints apply exclusively to how bound variables interact with each other and with the free variables. Definition 8 (p-hierarchical Query). A conjunctive query 𝑄 is p-hierarchical if the following is satisfied: (1) [bound-bound interaction] ∀𝑋, 𝑌 ∈ Bound(𝑄): at(𝑋 ) ⊆ at(𝑌 ) or at(𝑌 ) ⊆ at(𝑋 ) or at(𝑋 ) ∩ at(𝑌 ) = ∅; and (2) [bound-free interaction] ∀𝑋 ∈ Bound(𝑄), 𝑌 ∈ Free(𝑄): at(𝑋 ) ⊆ at(𝑌 ) or at(𝑋 ) ∩ at(𝑌 ) = ∅. The class of 𝛼-acyclic p-hierarchical queries is strictly sandwiched between the classes of qhierarchical queries [6] and of free-connex 𝛼-acyclic queries [5], as it strictly includes the former and is included in the latter. Example 9. Any full conjunctive (or join) query is trivially p-hierarchical, since it has no bound variables. Two simple examples of free-connex Í Í 𝛼-acyclic query that are not p-hierarchical are: 𝑄 1 () = 𝑋 ,𝑌 𝑅(𝑋 ) ·𝑆 (𝑋, 𝑌 ) ·𝑇 (𝑌 ) and 𝑄 2 (𝑋 ) = 𝑌 𝑆 (𝑋, 𝑌 ) ·𝑇 (𝑌 ). 𝑄 1 violates condition (1), while 𝑄 2 violates condition (2). A simple 𝛼-acyclic p-hierarchical query that is not q-hierarchical is the full variant of 𝑄 1 : 𝑄 1′ (𝑋, 𝑌 ) = 𝑅(𝑋 ) · 𝑆 (𝑋, 𝑌 ) ·𝑇 (𝑌 ). This is because at(𝑋 ) and at(𝑌 ) overlap but one is not included in the other. Note that 𝑄 1 and 𝑄 2 are also not q-hierarchical: 𝑄 1 is not even hierarchical, while 𝑄 2 is hierarchical but does not have the 𝑞 property. For variables 𝑋, 𝑌 , we say that 𝑋 dominates 𝑌 iff at(𝑋 ) ⊇ at(𝑌 ). Example 10. Throughout this paper, we use as a running example the acyclic query ∑︁ 𝑄 (𝐴, 𝐶) = 𝑅1 (𝐴, 𝐵, 𝐷, 𝐸) · 𝑅2 (𝐴, 𝐵, 𝐷, 𝐹 ) · 𝑅3 (𝐴, 𝐵, 𝐺) · 𝑅4 (𝐶) · 𝑅5 (𝐴, 𝐶, 𝐻 ). 𝐵,𝐷,𝐸,𝐹,𝐺,𝐻
Notice that 𝐵 dominates 𝐷 and 𝐺, 𝐷 dominates 𝐸 and 𝐹 , and 𝐻 has an atom set that is disjoint from the atom sets of all other bound variables. This satisfies condition (1). Variable 𝐴 dominates all bound variables, and 𝐶 has an atom set which is disjoint from all bound variables except 𝐻 , which it dominates. So 𝑄 satisfies conditions (1) and (2), and is thus p-hierarchical. Notice, however, that the sets at(𝐴) and at(𝐶) are neither disjoint, nor is one subsumed by the other one, so 𝑄 is not q-hierarchical. We next present an alternative characterization of p-hierarchical queries in terms of their decomposition into q-hierarchical subqueries. A query is free-dominated if its free variables occur in all of its atoms. Proposition 11. A query 𝑄 is p-hierarchical if and only if it can be expressed as a full conjunctive query with body atoms defined by free-dominated q-hierarchical subqueries.
8
Eden Chmielewski, Andrei Draghici, Dan Olteanu, and Haozhe Zhang
Proof. The proof relies on Algorithm 1 and lemmas, which are introduced later in the paper. [⇒] By Lemma 22, given a p-hierarchical query 𝑄, Algorithm 1 produces a forest of extended bound variable orders. By Lemma 23, each extended bound variable order corresponds to a freedominated query, and if we project out the bound variables of each subquery, then these queries are q-hierarchical. Joining these free-dominated q-hierarchical queries with the atoms of 𝑄 that consist only of free variables precisely equals 𝑄, and gives us the rewriting of 𝑄 as desired. [⇐] Consider a query 𝑄 (F) that is not p-hierarchical. Assume that 𝑄 violates condition (1), that is, there are two bound variables 𝑋, 𝑌 ∈ Bound(𝑄) such that at(𝑋 ) ∩at(𝑌 ) ≠ ∅, at(𝑋 ) \at(𝑌 ) ≠ ∅, and at(𝑌 ) \ at(𝑋 ) ≠ ∅. Consider a decomposition 𝑄 (F) = 𝑄 1 (F1 ) · . . . · 𝑄𝑘 (F𝑘 ), where 𝑄 1, . . . , 𝑄𝑘 are all q-hierarchical and free-dominated. Since, 𝑋, 𝑌 are bound variables of 𝑄, there must be one subquery 𝑄𝑖 (F𝑖 ) that contains both at(𝑋 ) and at(𝑌 ). However, this subquery cannot be q-hierarchical. Now, assume that 𝑄 violates condition (2). Thus, there are variables 𝑋 ∈ Bound(𝑄) and 𝑌 ∈ Free(𝑄) such that at(𝑋 ) ∩ at(𝑌 ) ≠ ∅ and at(𝑋 ) \ at(𝑌 ) ≠ ∅. Again, consider a decomposition 𝑄 (F) = 𝑄 1 (F1 ) · . . . · 𝑄𝑘 (F𝑘 ), where 𝑄 1, . . . , 𝑄𝑘 are all q-hierarchical and free-dominated. There must be a subquery 𝑄𝑖 (F𝑖 ) that contains all the atoms in at(𝑋 ). Since, at(𝑋 ) ∩ at(𝑌 ) ≠ ∅ we have that 𝑌 ∈ F𝑖 . However, because at(𝑋 ) \ at(𝑌 ) ≠ ∅, 𝑄𝑖 cannot be free-dominated. □ Example 12. Consider again the query from Ex. 10. 𝑄 can be equivalently expressed as 𝑄 (𝐴, 𝐶) = 𝑄 1 (𝐴) · 𝑄 2 (𝐴, 𝐶) · 𝑄 3 (𝐶), where the free-dominated q-hierarchical subqueries are defined as: Í 𝑄 1 (𝐴) = Í𝐵,𝐷,𝐸,𝐹,𝐺 𝑅1 (𝐴, 𝐵, 𝐷, 𝐸) · 𝑅2 (𝐴, 𝐵, 𝐷, 𝐹 ) · 𝑅3 (𝐴, 𝐵, 𝐺) 𝑄 2 (𝐴, 𝐶) = 𝐻 𝑅5 (𝐴, 𝐶, 𝐻 ) 𝑄 3 (𝐶) = 𝑅4 (𝐶). Finally, an important property is that the fractional hypertree width of a p-hierarchical query is equal to the fractional hypertree width of the Boolean version of that query. This allows us to relate the complexity of maintaining a p-hierarchical query in terms of the fractional hypertree width of its Boolean version (Theorem 1). Proposition 13. For any p-hierarchical query, its fractional hypertree width equals the fractional hypertree width of its Boolean version. 4
Maintaining P-Hierarchical Queries
In this section, we present our maintenance approach for p-hierarchical queries. We begin with a high-level intuition, which is to maintain different parts of the query over different semirings. We then introduce the notion of variable orders [16], which are used to decompose the query into q-hierarchical subqueries that can be maintained efficiently over the original semiring, and then derive maintenance plans for these q-hierarchical subqueries. We demonstrate this technique using the query from Ex. 10 as a running example. Then we show how the join of these subqueries can be maintained over the Boolean semiring while still recovering the payloads over the original semiring. Finally, we establish the correctness and complexity of our approach. 4.1
Intuition behind our Approach
The intuition behind our maintenance approach for p-hierarchical queries relies on the decomposition of p-hierarchical queries into a full conjunctive query over q-hierarchical sub-queries, as established in Prop. 11. Our algorithm uses two ingredients: an approach to maintain efficiently q-hierarchical queries over any semiring and another approach to maintain full conjunctive queries
The Role of Semirings in Incremental View Maintenance
9
restricted to the Boolean semiring. It relies on prior work that already introduced the two ingredients. Prior work [6, 14, 24, 30] introduced approaches that can maintain tractably q-hierarchical queries under both inserts and deletes using a factorized representation of the query result or a conceptually similar hierarchy of materialized views. We use a similar construction for the first ingredient. Further prior work [2] introduced an approach to maintain full conjunctive queries under inserts to B-databases using again a hierarchy of materialized views. We use this latter approach as our second ingredient. Our algorithm composes the maintenance strategies for the two ingredients to obtain one maintenance strategy for any p-hierarchical query as one hierarchy of materialized views. Remarkably, this suffices to guarantee the correctness of both the update and the enumeration steps. Inserts are propagated bottom-up and update each view from the leaf representing the updated relation through the hierarchy to the root view. Yet at the border between the two maintenance strategies, the payloads from the original semiring are cast as payloads in the Boolean semiring. This ensures that different payloads for the same tuple become indistinguishable under the Boolean semiring. Only the addition of a new tuple is propagated further beyond this border. This reduces the amount of insert propagations and brings an asymptotic complexity gain when compared to the approach that keeps the same semiring throughout the entire hierarchy of materialized views. This reduction in update propagations comes with a loss: The payload in the original semiring is not propagated beyond the border for existing tuples. This means that at enumeration time, the tuples in the views above the border, whose join make up the tuples in the query result, do not carry the correct payload. To retrieve the correct payload for a tuple in the query result, we need to construct it on the fly using lookups in the views right below the border, so in the root views for each of the q-hierarchical query. Since their number is only linear in the number of q-hierarchical subqueries (and independent of the size of the input data), this takes constant time. Furthermore, the prefix hierarchy made up of the views above the border supports the enumeration of all tuples in the query result with constant delay, following prior work [2]. 4.2
Variable Orders
A variable order determines the order in which we solve each join variable. Definition 14 (Variable Order). (Adapted from [16, Def. 3.1]) A variable order 𝜔 for a join query 𝑄 is a rooted forest 𝐹 with one node per variable in 𝑄 such that for each relation in 𝑄, its variables lie along the same root-to-leaf path in 𝐹 . Note that this definition corresponds to an f-tree in the terminology of prior work [26]. This definition applies to join queries, as it does not inherently distinguish between bound and free variables. We call a variable order free-top if no bound variable is an ancestor of a free variable. Every q-hierarchical query admits a free-top variable order where each root-to-leaf path is a schema of an atom of the query [16]. If the query is q-hierarchical, free-dominated, and non-Boolean, then it admits a free-top variable order 𝜔 that is a tree, and each atom of 𝑄 has a schema that forms a path beginning at the root. Crucially, the free variables themselves form a path at the top of this tree. By removing these free variables from 𝜔, we obtain a bound variable order. Furthermore, an extended bound variable order is constructed from a bound variable order 𝜔 for a conjunctive query 𝑄 by appending each atom 𝑅(Y) ∈ at(𝑄) as a child of the lowest bound variable in Y. This structure allows us to reason effectively about queries with bound variables. Example 15. Recall the p-hierarchical query from Ex. 10, which was shown in Ex. 12 to be the join of the free-dominated q-hierarchical subqueries 𝑄 1 , 𝑄 2 , and 𝑄 3 . Fig. 2 gives a free-top variable order for each of the queries 𝑄 1 , 𝑄 2 , and 𝑄 3 .
10
Eden Chmielewski, Andrei Draghici, Dan Olteanu, and Haozhe Zhang
𝐴 𝐵 BVO
𝐷
𝐴 𝐺
𝐶 𝑅3
𝐸
𝐹
𝑅1
𝑅2
BVO
𝐻
𝐶
𝑅5
𝑅4
Fig. 2. (left) A variable order of 𝑄 1 ; (middle) A variable order of 𝑄 2 ; (right) A variable order of 𝑄 3 . BVO denotes the bound variable order. Free variables are dark red.
Algorithm 1: CreateVarOrders(𝑄) Input: A p-hierarchical query 𝑄 Output: A forest of extended bound variable orders Initialize a directed graph 𝐺 := (V, E) with V := Bound(𝑄) and E := ∅ 2 foreach 𝑋 ∈ V do 3 if ∃𝑌 ∈ V s.t. 𝑋 < 𝑌 ∧ 𝑍 ∈ V s.t. 𝑋 < 𝑍 < 𝑌 then 4 E := E ∪ {(𝑌 → 𝑋 )} 1
foreach tree 𝑇 ∈ 𝐺 with vertices V (𝑇 ) do foreach 𝑅(Y) ∈ at(V (𝑇 )) do 7 V := V ∪ {𝑅(Y)} 8 let 𝑋 be the lowest vertex in 𝑇 s.t. 𝑋 ∈ V (𝑇 ) ∩ Y 9 E := E ∪ {(𝑋 → 𝑅(Y))}
5
6
10
return 𝐺 with undirected edges
These variable orders are trees, and each root-to-leaf path is a schema of an atom of the respective query (highlighted and labeled accordingly). Additionally, the free variables of each query form a path at the top of its respective tree. For example, 𝑄 1 has only the free variable 𝐴, so in the given variable order, 𝐴 is the root of the tree. 𝑄 2 has free variables 𝐴 and 𝐶, which form a path at the top of the tree. Removing the free variables gives a bound variable order for each query. Because 𝑄 3 consists only of free variables, its bound variable order is trivially empty. Finally, we construct the extended bound variables orders by attaching the atoms 𝑅1 (𝐴, 𝐵, 𝐷, 𝐸), 𝑅2 (𝐴, 𝐵, 𝐷, 𝐹 ), 𝑅3 (𝐴, 𝐵, 𝐺), 𝑅5 (𝐴, 𝐶, 𝐻 ), 𝑅4 (𝐶) as children of the nodes coresponding to variables 𝐸, 𝐹, 𝐺, 𝐻, 𝐶, respectively. 4.3 Running Example In this section, we demonstrate our query optimization process for p-hierarchical queries, which proceeds in two phases. First, we decompose the query into a forest of extended bound variable orders, each corresponding to a free-dominated q-hierarchical query (Algorithm 1). Next, we transform each variable order into a view tree (Algorithm 2). In the end, each view tree can be maintained in constant time. To highlight these phases, we use as a running example the p-hierarchical query from Ex. 10. 4.3.1 Phase 1: Variable Order Construction. We present Algorithm 1, which takes a p-hierarchical query 𝑄 as input and uses the dominance relationships between bound variables to construct a
The Role of Semirings in Incremental View Maintenance
𝐵 𝑇1
𝐷 𝐸
𝐻
𝑇2
𝐻
𝑉7 (𝐴)
𝑉8 (𝐴, 𝐶 )
𝑅5 (𝐴, 𝐶, 𝐻 )
𝑉6 (𝐴, 𝐵)
𝑅5 (𝐴, 𝐶, 𝐻 )
𝐵
𝐺 𝐹
11
𝐷
𝐺
𝑅3 (𝐴, 𝐵, 𝐺 )
𝑉4 (𝐴, 𝐵)
𝑉5 (𝐴, 𝐵)
𝑅1 (𝐴, 𝐵, 𝐷, 𝐸 ) 𝑅2 (𝐴, 𝐵, 𝐷, 𝐹 )
𝑉3 (𝐴, 𝐵, 𝐷 )
𝑅3 (𝐴, 𝐵, 𝐺 )
𝑉1 (𝐴, 𝐵, 𝐷 )
𝑉2 (𝐴, 𝐵, 𝐷 )
𝐸
𝐹
𝑅1 (𝐴, 𝐵, 𝐷, 𝐸 ) 𝑅2 (𝐴, 𝐵, 𝐷, 𝐹 )
Fig. 3. (left) A forest of bound variable orders intermediately produced by Algorithm 1 for the input query 𝑄 from Ex. 10; (middle) A forest of extended bound variable orders produced by Algorithm 1 for the same query; (right) The forest of view trees produced by Algorithm 2 for forest of the extended bound variable orders (redundant views have been omitted).
forest of extended bound variable orders. In our setting, a forest is a directed graph where all nodes have in-degree one apart from the root nodes, which have in-degree zero. We impose a partial order on the bound variables, defined as follows: For two bound variables 𝑋 and 𝑌 , if at(𝑋 ) ⊂ at(𝑌 ), then 𝑋 < 𝑌 . If at(𝑋 ) = at(𝑌 ), then 𝑋 < 𝑌 only if 𝑋 is lexicographically smaller. If 𝑌 is the smallest variable that dominates 𝑋 (according to the partial order), then 𝑌 minimally dominates 𝑋 , and we construct an edge from 𝑌 to 𝑋 (lines 1-4). By the end of this construction, we have produced a forest where each tree 𝑇 with vertex set V (𝑇 ) is a bound variable order. Additionally, the corresponding free-dominated q-hierarchical query can be derived by joining the set of atoms that the variables of V (𝑇 ) appear in, and projecting out V (𝑇 ). In particular, each atom of this query has a schema with bound variables that form a path starting at the root of 𝑇 . Example 16. We illustrate lines 1-4 of Algorithm 1 using 𝑄 from Ex. 10 as input. The algorithm begins by constructing a graph 𝐺 with the vertex set V = Bound(𝑄) = {𝐵, 𝐷, 𝐸, 𝐹, 𝐺 } (line 1). Then, for each bound variable 𝑋 ∈ V, we search for a bound variable that minimally dominates 𝑋 (lines 2-4). We start with the bound variable 𝐸. We have at(𝐸) = {𝑅1 (𝐴, 𝐵, 𝐷, 𝐸)}, and the bound variables that appear in atoms with 𝐸 are 𝐵 and 𝐷, which have atom sets at(𝐵) = {𝑅1 (𝐴, 𝐵, 𝐷, 𝐸), 𝑅2 (𝐴, 𝐵, 𝐷, 𝐹 ), 𝑅3 (𝐴, 𝐵, 𝐺)} and at(𝐷) = {𝑅1 (𝐴, 𝐵, 𝐷, 𝐸), 𝑅2 (𝐴, 𝐵, 𝐷, 𝐹 )}, respectively. Because at(𝐸) ⊂ at(𝐵), 𝐸 < 𝐵. However, we cannot add an edge from 𝐵 to 𝐸, because at(𝐸) ⊂ at(𝐷) ⊂ at(𝐵), and so 𝐸 < 𝐷 < 𝐵, and thus 𝐵 does not minimally dominate 𝐸. Instead, 𝐷 minimally dominates 𝐸, and so we add an edge from 𝐷 to 𝐸 in the graph. Similarly, at(𝐹 ) = {𝑅2 (𝐴, 𝐵, 𝐷, 𝐹 )}, and the bound variables which appear in atoms with 𝐹 are 𝐵 and 𝐷. 𝐹 < 𝐷 < 𝐵, so 𝐷 minimally dominates 𝐵, and we add an edge from 𝐷 to 𝐹 . For variable 𝐺, at(𝐺) = {𝑅3 (𝐴, 𝐵, 𝐺)} and 𝐺 appears only with bound variable 𝐵. 𝐺 < 𝐵, so 𝐵 minimally dominates 𝐺, and we add an edge from 𝐵 to 𝐺. Variable 𝐷 appears with bound variables 𝐵, 𝐸, 𝐹 , and 𝐺. Only 𝐵 is larger, so 𝐵 minimally dominates 𝐷, and we add an edge from 𝐵 to 𝐷. Variables 𝐵 and 𝐶 are dominated by no bound variables. The resulting graph is a forest with two trees 𝑇1 and 𝑇2 shown in Fig. 3 on the left. Each tree is a bound variable order and they correspond to queries 𝑄 1 (𝑇1 ) and 𝑄 2 (𝑇2 ) from Ex. 12. After constructing the forest, each tree (bound variable order) is extended with the atoms of its corresponding query (lines 5-9) to form extended bound variable orders. Thus, Algorithm 1 produces a forest of extended bound variable orders.
12
Eden Chmielewski, Andrei Draghici, Dan Olteanu, and Haozhe Zhang
Example 17. Continuing Ex. 16, Algorithm 1 now extends each bound variable order with the corresponding atoms. We begin by iterating over the two trees (bound variable orders) 𝑇1 and 𝑇2 in the forest shown on the left in Fig. 3. The tree 𝑇1 has (bound) variables V (𝑇1 ) = {𝐵, 𝐷, 𝐸, 𝐹, 𝐺 }. This implies the corresponding query has atoms at(V (𝑇 )) = {𝑅1 (𝐴, 𝐵, 𝐷, 𝐸), 𝑅2 (𝐴, 𝐵, 𝐷, 𝐹 ), 𝑅3 (𝐴, 𝐵, 𝐺)}. To extend the variable order, we must add each of these three atoms as leaves of 𝑇1 . Each atom is added as a leaf of the lowest bound variable in 𝑇1 which occurs in its schema. For instance, 𝑅1 has bound variables 𝐵, 𝐷, and 𝐸. 𝐵 occurs in the first level of 𝑇1 , 𝐷 occurs in the second level, and 𝐸 occurs in the third level, so we add 𝑅1 (𝐴, 𝐵, 𝐷, 𝐸) as a leaf of 𝐸. Similarly, 𝑅2 has bound variables 𝐵, 𝐷, and 𝐹 . 𝐹 occurs in the third level of 𝑇1 , so we add 𝑅2 (𝐴, 𝐵, 𝐷, 𝐹 ) as a leaf of 𝐹 . We repeat this process for 𝑅3 (𝐴, 𝐵, 𝐺), which is added as a leaf of 𝐺. 𝑇2 has only the variables V (𝑇2 ) = {𝐻 }, and at(V (𝑇2 )) = {𝑅5 (𝐴, 𝐶, 𝐻 )}. Because 𝐻 is the only bound variable in 𝑅5 , we trivially add 𝑅5 (𝐴, 𝐶, 𝐻 ) as a leaf of 𝐻 . The result is a forest of extended bound variable orders shown in the middle in Fig. 3. In constructing the bound variable orders, Algorithm 1 simultaneously derives a q-hierarchical decomposition of the original query 𝑄. Once the algorithm terminates, each extended bound variable order corresponds to a free-dominated q-hierarchical subquery. The original query 𝑄 can then be expressed as the join of these subqueries and the atoms of 𝑄 whose schemas consist entirely of free variables. Example 18. Continuing Ex. 17, consider the forest of extended bound variable orders produced by Algorithm 1, which are shown in the middle of Fig. 3. Consider the leftmost extended bound variable order. This corresponds to the subquery which is the join of the atoms 𝑅1 (𝐴, 𝐵, 𝐷, 𝐸), 𝑅2 (𝐴, 𝐵, 𝐷, 𝐹 ), and 𝑅3 (𝐴, 𝐵, 𝐺), with all bound variables marginalized out. Because this is an extended bound variable order, the bound variables {𝐵, 𝐷, 𝐺, 𝐸, 𝐹 } are precisely the inner nodes of the tree. Thus, the tree corresponds to the free-dominated q-hierarchical subquery 𝑄 1 (𝐴) = 𝑅1 (𝐴, 𝐵, 𝐷, 𝐸) · 𝑅2 (𝐴, 𝐵, 𝐷, 𝐹 ) · 𝑅3 (𝐴, 𝐵, 𝐺), which was derived from the extended bound variable order. Similarly, the extended bound variable order on the right with the bound variable {𝐻 } corresponds to the free-dominated q-hierarchical subquery 𝑄 2 (𝐴, 𝐶) = 𝑅5 (𝐴, 𝐶, 𝐻 ). 𝑄 has only one atom, 𝑅4 (𝐶), whose schema consists entirely of bound variables. This atom corresponds to a third free-dominated q-hierarchical subquery, 𝑄 3 (𝐶) = 𝑅4 (𝐶). As shown in Ex. 12, 𝑄 can be expressed as the join of 𝑄 1 , 𝑄 2 , and 𝑄 3 . 4.3.2 Phase 2: View Tree Transformation. After constructing the forest of extended bound variable orders (via Algorithm 1), Algorithm 2 recursively transforms each extended bound variable order into a view tree (Def. 4). The algorithm operates over a forest 𝜈 whose vertices are either bound variables, atoms, or views defined over their children. By processing the vertices in a post-order traversal, the algorithm applies the following logic: vertices corresponding to atoms are left unchanged (lines 4–5), while each bound variable vertex is replaced by a path consisting of a join view over its children topped by a projection view (lines 6–9) in which the bound variable is marginalized out. Ultimately, this bottom-up transformation gives a forest of view trees. Example 19. Continuing Ex. 17, Algorithm 2 transforms the forest of extended bound variable orders shown in the middle of Fig. 3 into the forest of view trees shown on the right. Note that when a bound variable node has only one child, the algorithm still creates both a join view and a projection view, even though no join is necessary. These redundant join views can be omitted, as shown in the figure. 4.3.3 Final Maintenance Plan. After constructing the forest of view trees, we add as nodes the atoms of 𝑄 which have only free variables in their schemas. Each of these nodes is a trivial view tree. Example 20. Continuing Ex. 19, we add to the forest the node 𝑅4 (𝐶). This is the only atom of 𝑄 with a schema that is over exclusively free variables.
The Role of Semirings in Incremental View Maintenance
13
Algorithm 2: Rewrite(𝜈) Input: A forest 𝜈 Output: A forest of view trees switch 𝜈 do case {𝜈𝑖 }𝑖 ∈ [𝑛] do 3 return {Rewrite(𝜈𝑖 )}𝑖 ∈ [𝑛]
1
2
5
case 𝑅(Y) do return 𝑅(Y)
6
case
4
𝑋 do 𝜈 1 . . . 𝜈𝑘 7 8
9
let 𝑇𝑖 = Rewrite(𝜈𝑖 ) and let the root view be 𝑉𝑖 (S𝑖 ), ∀𝑖 ∈ [𝑘] Ð let S = 𝑖 ∈ [𝑘 ] S𝑖 𝑉𝑋′ (S \ {𝑋 }) return 𝑉𝑋 (S) 𝑉 (S ) . . . 𝑉𝑘 (S𝑘 ) 1 1
Joining the subqueries corresponding to these view trees is a valid rewriting of 𝑄 that decomposes 𝑄 into free-dominated q-hierarchical subqueries. In particular, 𝑄 is the join of the root views of these view trees. Example 21. Continuing Ex. 20, the forest of view trees has root views 𝑉7 (𝐴) and 𝑉8 (𝐴, 𝐶) (shown in Fig. 3 on the right), and 𝑅4 (𝐶). 𝑄 is precisely the join of these views. 4.4
Correctness
In this section, we present the proofs of correctness for our maintenance plan. Lemma 22. Given a p-hierarchical query 𝑄, Algorithm 1 creates a forest of extended bound variable orders 𝜔 1, ..., 𝜔𝑛 over disjoint variables and atoms. Each 𝜔𝑖 corresponds to the join of at(vars(𝜔𝑖 )). Proof. First we show that by line 5 of Algorithm 1, the graph 𝐺 (V, E) is a forest. Suppose for sake of contradiction that 𝐺 is not a forest. Then either (1) there exists a vertex with in-degree greater than one, or (2) there exists a directed cycle. Suppose case (1). Then ∃𝑌 , 𝑍 ∈ V = Bound(𝑄) that both have an edge to a vertex 𝑋 ∈ V, and without loss of generality, 𝑌 precedes 𝑍 lexicographically. This implies at(𝑋 ) ⊆ at(𝑌 ) and at(𝑋 ) ⊆ at(𝑍 ). If at(𝑋 ) = at(𝑌 ) ⊆ at(𝑍 ), then 𝑋 < 𝑌 < 𝑍 , so an edge would not exist from 𝑍 to 𝑋 . If at(𝑋 ) = at(𝑍 ) ⊂ at(𝑌 ), then 𝑋 < 𝑍 < 𝑌 , so an edge would not exist from 𝑌 to 𝑋 . Now consider the case that at(𝑌 ) and at(𝑍 ) are incomparable. Because 𝑄 is p-hierarchical and at(𝑌 ) ∩ at(𝑍 ) ≠ ∅, at least one of the bound variables 𝑌 or 𝑍 must dominate the other, a contradiction. Now suppose case (2). Then ∃𝑋 1, ..., 𝑋𝑘 ∈ V that form a directed cycle 𝑋 1, ..., 𝑋𝑘 , 𝑋 1 . If we have an edge from 𝑋𝑖 to 𝑋 𝑗 , then 𝑋 𝑗 < 𝑋𝑖 , so at(𝑋 𝑗 ) ⊆ at(𝑋𝑖 ). So it must be the case that all variables in this cycle have identical atom sets, and if we have an edge from 𝑋𝑖 to 𝑋 𝑗
14
Eden Chmielewski, Andrei Draghici, Dan Olteanu, and Haozhe Zhang
in this cycle, then 𝑋𝑖 is lexicographically larger than 𝑋 𝑗 . Because 𝑋 1 < 𝑋𝑘 < 𝑋𝑘 −1 ... < 𝑋 1 , 𝑋 1 is lexicographically larger than itself, a contradiction. Now we show that by line 5, for each tree 𝑇 in 𝐺, each atom in at(V (𝑇 )) has bound variables that lie along the same root-to-leaf path in 𝑇 . Consider an atom 𝑅(Y) ∈ at(V (𝑇 )) with bound variable 𝑌 ∈ Y s.t. 𝑌 ∈ V (𝑇 ). Suppose for sake of contradiction that there exists another bound variable 𝑍 ∈ Y which does not fall along the root to leaf path in 𝑇 which contains 𝑌 . Either (1) 𝑍 ∉ V (𝑇 ) or (2) 𝑍 ∈ V (𝑇 ). Suppose the first case and let 𝑊 be the root of the tree 𝑍 appears in. at(𝑌 ) ⊆ at(𝑋 ) and at(𝑍 ) ⊂ at(𝑌 ), so at(𝑋 ) ∩ at(𝑍 ) ≠ ∅ and because 𝑄 is p-hierarchical, 𝑋 or 𝑊 must dominate the other. If at(𝑋 ) ⊂ at(𝑊 ) or at(𝑋 ) = at(𝑊 ) and 𝑋 precedes 𝑊 lexicographically, then 𝑋 < 𝑊 , and there should be an edge from 𝑊 (or the minimally dominating bound variable) to 𝑋 , a contradiction, as 𝑋 is a root. The other case is symmetric. Thus, 𝑍 ∈ V (𝑇 ). Now suppose case (2) and let 𝑊 be the first common ancestor of 𝑌 and 𝑍 in 𝑇 . Then there is a path from 𝑊 to 𝑌 and from 𝑊 to 𝑍 , so 𝑌 < 𝑊 and 𝑍 < 𝑊 . Because 𝑄 is p-hierarchical and at(𝑌 ) ∩ at(𝑍 ) ≠ ∅, 𝑌 or 𝑍 must dominate the other. If at(𝑌 ) ⊂ at(𝑍 ) or at(𝑌 ) = at(𝑍 ) and 𝑌 precedes 𝑍 lexicographically, then 𝑌 < 𝑍 < 𝑊 . Let 𝑌1 be the first variable in the path from 𝑊 to 𝑌 s.t. 𝑌1 < 𝑍 , and suppose 𝑌2 has an edge in this path to 𝑌1 . Because 𝑌 ≤ 𝑌1 < 𝑌2 and 𝑌1 < 𝑍 , at(𝑌1 ) ⊆ at(𝑍 ) and at(𝑌1 ) ⊆ at(𝑌2 ), so at(𝑍 ) ∩ at(𝑌2 ) ≠ ∅. Thus, 𝑌1 < 𝑍 < 𝑌2 , and there does not exist an edge from 𝑌2 to 𝑌1 , a contradiction. Next we show that the bound variables of Y form a subpath of a root-to-leaf path in 𝑇 . Suppose for sake of contradiction that they fall along the subpath 𝑋 1, ..., 𝑋𝑖 , 𝑋𝑖+1, ..., 𝑋𝑘 of a root-to-leaf path, where 𝑋 1, 𝑋𝑘 ∈ Y and 𝑋𝑖 ∉ Y. Then 𝑋𝑘 < 𝑋𝑖 , so at(𝑋𝑘 ) ⊆ at(𝑋𝑖 ). And yet 𝑅(Y) ∈ at(𝑋𝑘 ) and 𝑅(Y) ∉ at(𝑋𝑖 ), a contradiction. Next we show that this subpath must start at the root of 𝑇 . Suppose for sake of contradiction the bound variables of Y fall along a subpath of the root-to-leaf path 𝑋 1, ..., 𝑋𝑖 , 𝑋𝑖+1, ..., 𝑋𝑘 , where 𝑋 1, ..., 𝑋𝑖 ∉ Y and 𝑋𝑖+1 ∈ Y. Then 𝑋𝑖+1 < 𝑋𝑖 , so at(𝑋𝑖+1 ) ⊆ at(𝑋𝑖 ), and yet 𝑅(Y) ∈ at(𝑋𝑖+1 ) and 𝑅(Y) ∉ at(𝑋𝑖 ), a contradiction. Thus, for each atom in at(V (𝑇 )), the bound variables form a path starting at the root of 𝑇 . Consider a leaf 𝑌 . Because at(𝑌 ) ⊆ at(V (𝑇 )), all atoms 𝑌 occurs in must have bound variables that form a subpath of a root-to-leaf path in 𝑇 starting at the root. Because 𝑌 occurs in the schema of at least one atom 𝑅(Y) and 𝑌 is a leaf, the bound variables of Y must form the path from the root to 𝑌 . Thus, each root-to-leaf path in 𝑇 is an atom of 𝑄. Furthermore, the root 𝑋 dominates all bound variables V (𝑇 ) in 𝑇 , and because 𝑄 is p-hierarchical, a free variable that appears in a schema with a bound variable must dominate the bound variable. Thus, the variables in vars(at(𝑋 )) ∩ Free(𝑄) appear in all atoms in at(V (𝑇 )), and the query corresponding to the join of at(V (𝑇 ) is free-dominated. By adding a path of free variables to the top of the tree, we would have one node in 𝑇 per variable in at(V (𝑇 )), and each atom in at(V (𝑇 )) would have a schema that forms a path beginning at the root of 𝑇 . Thus, 𝑇 is a bound variable order, and lines 5-9 of Algorithm 1 extend 𝑇 with all atoms in at(V (𝑇 )), turning 𝑇 into an extended bound variable order where the leaves are precisely at(V (𝑇 )). □ Lemma 23. Given a 𝑝-hierarchical query 𝑄, each extended bound variable order produced by Algorithm 1 corresponds to a free-dominated q-hierarchical query. Additionally, 𝑄 is the join of these q-hierarchical queries and the atoms of 𝑄 whose schemas contain only free variables. Proof. By Lemma 22, Algorithm 1 produces a forest of extended bound variable 𝜔 1, ..., 𝜔𝑛 , where Î each 𝜔𝑖 corresponds to the free-dominated join query 𝑄𝑖 (F𝑖 ) = 𝑅 (Y) ∈at(vars(𝜔𝑖 ) ) 𝑅(Y). Now we will show that if we marginalize out the bound variables vars(𝜔𝑖 ), the resulting query 𝑄𝑖′ which has bound variables vars(𝜔𝑖 ), atoms at(vars(𝜔𝑖 )), and free variables F = vars(at(vars(𝜔𝑖 ))) ∩ Free(𝑄) is q-hierarchical. Consider any two bound variables 𝑋 1, 𝑋 2 ∈ vars(𝜔𝑖 ). Because 𝑄 is p-hierarchical,
The Role of Semirings in Incremental View Maintenance
15
at(𝑋 1 ) ⊆ at(𝑋 2 ), at(𝑋 2 ) ⊆ at(𝑋 1 ), or at(𝑋 1 ) ∩ at(𝑋 2 ) = ∅. Because at(𝑋 1 ) ⊆ at(vars(𝜔𝑖 )) and at(𝑋 2 ) ⊆ at(vars(𝜔𝑖 )), the property still holds for 𝑄𝑖′ . Consider a free variable 𝑋 1 ∈ F and a bound variable 𝑋 2 ∈ vars(𝜔𝑖 )). Because 𝑄𝑖 is free dominated (and 𝑄𝑖′ as well, because it has the same atom set), 𝑋 1 appears in all atoms. Thus, at(𝑋 2 ) ⊆ at(vars(𝜔𝑖 )) = at(𝑋 1 ), so all free variables dominate all bound variables in 𝑄𝑖′ , and all free variables dominate each other in 𝑄𝑖′ . Thus, 𝑄𝑖′ is free-dominated q-hierarchical. Now we will show that 𝑄 is the join of these q-hierarchical queries and the atoms of 𝑄 which consist only of free variables. Because each atom of 𝑄𝑖 has bound variables that form a path beginning at the root of 𝜔𝑖 , and the extended bound variable orders have disjoint variables, the extended bound variable orders have disjoint atoms. Further, as each bound variable of 𝑄 appears in an extended bound variable order, and each 𝜔𝑖 corresponds to the join of at(vars(𝜔𝑖 )) = leaves(𝑄𝑖 ), each atom with a bound variable in its schema appears as a leaf of an extended bound variable order. Additionally, each 𝑄𝑖 is over distinct bound variables. Thus, each query 𝑄𝑖 represents the join of disjoint atoms whose union is precisely the atoms of 𝑄 that contain a bound variable, and each 𝑄𝑖 has disjoint bound variables in its schema. Thus, for each 𝑄𝑖 , we can marginalize out the bound variables to obtain the query 𝑄𝑖′ . 𝑄 is precisely the join of these queries and the atoms of 𝑄 with schemas that contain only free variables. □ Lemma 24. Given a forest of extended bound variable orders, Algorithm 2 produces a view tree for each variable order. Additionally, the root of each view tree has a schema that consists precisely of the free variables of the respective query, and each join view corresponds to an intersection. Proof. Let the original input to Algorithm 2 be the forest of extended bound variable orders 𝜔 = {𝜔 1, ..., 𝜔𝑛 }, where each extended bound variable order 𝜔𝑖 corresponds to the join query 𝑄𝑖 . In lines 2-3, we recursively invoke Algorithm 2 for each 𝜔𝑖 ∈ 𝜔, and we visit each variable of 𝜔𝑖 in a postorder traversal (lines 6-7). By construction of each 𝜔𝑖 , the leaves are precisely at(𝑄𝑖 ), which are untouched by Algorithm 2 (lines 4-5). Each inner node of 𝜔𝑖 becomes a view with a schema defined over its children (lines 8-9). Inductively, each view is over variables of 𝑄𝑖 . When Algorithm 2 visits the variable 𝑋 , we replace it with two connected views: a view 𝑉 (S) that is the join of the children views, and a marginalization view 𝑉 (S \ 𝑋 ) that is the parent of 𝑉 (S) (line 9). As all atoms of 𝑄𝑖 that contain the bound variable 𝑋 occur in the subtree rooted at 𝑉 (S) (by construction of 𝜔𝑖 ), Algorithm 2 produces a view tree 𝑇𝑖 for each 𝜔𝑖 . Furthermore, as all atoms of 𝑄𝑖 are leaves of 𝑇𝑖 , and 𝑇𝑖 only consists of join and projection views (that project out only bound variables), the root view of 𝑇𝑖 is over the free variables of 𝑄𝑖 . Now we inductively show that when Algorithm 2 visits the inner node 𝑋 in a postorder traversal of the extended bound variable order 𝜔𝑖 , all of the children of 𝑋 are views with the same schema path(𝑋 ), and so 𝑋 is replaced by an intersection view with schema path(𝑋 ), which has a parent view with the schema path(𝑋 ) \ 𝑋 (line 9). As the base case, consider visiting the node 𝑋 1 in the extended bound variable order 𝜔𝑖 , where the children of 𝑋 1 are all leaves (atoms of 𝑄𝑖 ). By construction of 𝜔𝑖 , all leaves of 𝑋 1 are atoms with the same schema, path(𝑋 1 ). So Algorithm 2 replaces 𝑋 with the intersection view with schema path(𝑋 1 ), and with a parent view with schema path(𝑋 1 ) \ 𝑋 1 . As the induction step, consider visiting an inner node 𝑋𝑘 , and assume the claim holds for all inner nodes that have already been visited in the postorder traversal. Because 𝑋𝑘 is visited only after all of its children have been visited, the inductive hypothesis applies to all of its children. Thus, each of its children 𝑋 𝑗 in 𝜔𝑖 has been replaced with an intersection view that has schema path(𝑋 𝑗 ), with a parent that has schema path(𝑋 𝑗 ) \ 𝑋 𝑗 = path(𝑋𝑘 ). Thus, all children of 𝑋𝑘 are projection views with the same schema path(𝑋𝑘 ), and 𝑋𝑘 is replaced with an intersection view with schema path(𝑋𝑘 ), with a parent that is the projection view with schema path(𝑋𝑘 ) \ 𝑋𝑘 .
16
Eden Chmielewski, Andrei Draghici, Dan Olteanu, and Haozhe Zhang
As the claim holds for 𝑋𝑘 , we have inductively shown all inner nodes are replaced by intersection and projection views, and so all join views correspond to intersections. □ Proposition 25. Given a p-hierarchical query 𝑄 (X), its maintenance plan (Subsec. 4.3.3) constructs Î a forest of view trees T such that 𝑄 (X) = 𝑉 (Y) ∈roots( T ) 𝑉 (Y) and each tree admits constant update time for a single-tuple insert. Proof. By Lemma 22, given a p-hierarchical query 𝑄, Algorithm 1 constructs a forest of extended bound variable orders, and by Lemma 23, 𝑄 is the join of the corresponding queries (if we project out the bound variables of 𝑄), and the atoms of 𝑄 with schemas that consist only of free variables. By Lemma 24, Algorithm 2 takes a forest of extended bound variable orders as input, and produces a view tree for each variable order. Additionally, the root of each view tree has a schema that consists precisely of the free variables of the respective query, and each join view corresponds to an intersection. Thus, executing Algorithm 1 with 𝑄 as input, and using the resulting forest of extended bound variable orders as input to Algorithm 2, and adding to T all atoms of 𝑄 with schemas that consist only of free variables, yields a forest of view trees T s.t. 𝑄 is the join of the root view of each view tree. Further, because each view tree consists only of projection and intersection views (or stand-alone relations), and intersections and projections and relations each take constant time to update (given a single-tuple insert), each view tree in T admits constant update time given a single-tuple update, and 𝑄 is precisely is the join of of the root views of each view tree in the forest T produced by our maintenance approach. □ 4.5
Augmenting View Trees
In the previous section, we showed how to decompose a p-hierarchical query 𝑄 into q-hierarchical subqueries, and how to construct a forest of view trees T such that 𝑄 is the join of the root views of these view trees. Now consider the query that results from this decomposition, 𝑄 (X) = Î 𝑉 (Y) ∈roots( T ) 𝑉 (Y). We can augment each view tree by adding an indicator projection 1𝑉 (Y) (Y) atop each root view 𝑉 (Y). Joining these indicator projections yields the join query 𝑄 ′ that can be maintained over the Boolean semiring using prior work [2], as long as we restrict ourselves to the insert-only setting. In particular, all tuples in 𝑄 ′ have non-zero payload if and only if they have non-zero payload in 𝑄. Thus, when we enumerate a tuple 𝑡 from 𝑄 ′ with a non-zero payload, we can recover its payload in 𝑄 by simply projecting each 𝑡 onto the schema of each indicator projection, and looking up its payload in the view below it in the forest of augmented view trees. Multiplying these payloads and replacing each payload of a tuple in 𝑄 ′ with the respective product recovers the correct payloads of the tuples in 𝑄, as if the entire query was maintained over the same semiring. We are now ready to present the proof of the main theorem. Proof of Theorem 1. Consider the forest of view trees T Î produced by our maintenance approach for the p-hierarchical query 𝑄. By Prop. 25, 𝑄 (F) = 𝑉 (Y) ∈roots( T ) 𝑉 (Y). Consider the forest of view trees T ′ obtained by adding an indicator projection 1𝑉 (Y) atop each root view 𝑉 (Y) in Î T . Then all views in the set roots(T ′ ) are over the Boolean semiring, and the query ′ 𝑄 (F) = 𝑉 (Y) ∈roots( T ′ ) 𝑉 (Y) maps all tuples in 𝑄 with non-zero payload to the payload one, and zero otherwise. Consider a single-tuple insert to D. Because T has disjoint atoms (Lemma 22), only one view tree 𝑇 in the forest T will be updated. By Prop. 25, 𝑇 admits constant update time. This implies the root view 𝑉 (Y) of 𝑇 admits constant update time, and so the indicator projection 1𝑉 (Y) admits constant update time as well. As the view trees in T ′ are precisely those in T with an indicator projection on top, the augmented view tree 𝑇 ′ in T ′ that corresponds to 𝑇 in T also admits constant update time. Thus, given a single-tuple insert to D, T ′ admits constant update time.
The Role of Semirings in Incremental View Maintenance
17
Let D be an initially empty database (so all views in T ′ are initially empty), and consider 𝑁 single-tuple inserts to D. Because T ′ admits constant update time for each single-tuple insert and only one tree in T ′ is updated, its root admits constant update time and thus the number of tuples inserted into the root is O (1). Summing up over 𝑁 single-tuple inserts implies O (𝑁 ) total inserts into the roots of T ′ . As these root views are precisely the input relations of 𝑄 ′ , and 𝑄 ′ is a ′ full-join query over the Boolean semiring, 𝑄 ′ admits amortized O (𝑁 fhtw(𝑄 ) −1 ) update time and non-amortized constant enumeration delay [2, Theorem 4.1]. Now we will show how to use the result of 𝑄 ′ to obtain the result of 𝑄. Suppose we perform a single-tuple insert to D, update T ′ , and perform all inserts to input relations of 𝑄 ′ as defined by roots(T ′ ). It is immediate that 𝑄 ′ maps all tuples in 𝑄 with non-zero payload to the payload one, and zero otherwise. Consider a tuple x ∈ Dom(X) s.t. 𝑄 (x) ≠ 0. Then its payload is 𝑄 (x) = Î ′ 𝑉 (Y) ∈roots( T ) 𝑉 (𝜋 Y x). Thus, for each tuple x ∈ Dom(X) s.t. 𝑄 (x) ≠ 0, we can project x onto the ′ schema of each indicator projection in T (the forest of augmented view trees), look up the payload of this projected tuple in the child view, and take the product of these payloads. This product is precisely the payload 𝑄 (x). Further, each projection and look-up takes constant time, and the number of times we perform each operation is bounded by |at(𝑄)|, which is constant w.r.t. data complexity. Thus, when we begin with an initially empty database D and receive a stream of 𝑁 singletuple inserts, after each insert, we update the forest of augmented view trees T ′ (which takes ′ constant time) and we update the query 𝑄 ′ (which admits O (𝑁 fhtw(𝑄 ) −1 ) amortized update time and constant enumeration delay). When enumerating the output of 𝑄 ′ , all tuples with payload zero in 𝑄 ′ are skipped as they obtain payload zero in 𝑄, and each tuple in 𝑄 ′ with non-zero payload is enumerated with constant enumeration delay, and while enumerating the tuple, we recover the payload in 𝑄 in constant time by multiplying payloads of views in T ′ , as described above. Thus, ′ each insert into D takes amortized update time O (𝑁 fhtw(𝑄 ) ) and admits non-amortized constant delay enumeration of the output. Now we will show that fhtw(𝑄 ′ ) ≤ fhtw(𝑄). Let H = (V, E, F) denote the hypergraph of 𝑄, and let H ′ = (V ′, E ′, F) denote the hypergraph of 𝑄 ′ . Let (𝑇 , 𝜒) be such a minimal width tree decomposition of the Boolean version of 𝑄. Consider the tree decomposition (𝑇 ′, 𝜒 ′ ) obtained by removing the bound variables of 𝑄 from each bag of the tree decomposition (𝑇 , 𝜒). We will show (𝑇 ′, 𝜒 ′ ) is a valid tree decomposition for 𝑄 ′ . By Lemmas 23 and 24, T is a forest of view trees corresponding to free-dominated subqueries such that each root view is over the free variables of the respective subquery. Consider an edge 𝑒 ′ ∈ E ′ . The edges of 𝐸 ′ are precisely the set of schemas of roots(T ), so 𝑒 ′ is the schema of the root view of a view tree corresponding to a subquery 𝑄𝑖 that is free-dominated. Thus, there exists an atom of 𝑄𝑖 with schema 𝑒 ∈ E s.t. 𝑒 ′ ⊆ 𝑒. Because (𝑇 , 𝜒) is a tree decomposition of the Boolean version of 𝑄, there exists a vertex 𝑡 ∈ nodes(𝑇 ) s.t. 𝑒 ⊆ 𝜒 (𝑡). Thus, 𝑒 ′ ⊆ 𝜒 (𝑡). Additionally, because 𝑒 ′ ⊆ F, and we only remove bound variables, 𝑒 ′ ⊆ 𝜒 ′ (𝑡). Thus, for every edge 𝑒 ′ ∈ E ′ , 𝑒 ′ is a subset of 𝜒 ′ (𝑡) for some 𝑡 ∈ nodes(𝑇 ′ ), and so every variable of 𝑄 ′ appears in a bag of (𝑇 ′, 𝜒 ′ ). Now we will show that for every variable 𝑋 ∈ V ′ = F, the set {𝑡 |𝑋 ∈ 𝜒 ′ (𝑡)} is a connected subtree in 𝑇 ′ (we have already shown the set is non-empty). Because 𝑋 ∈ V, the set {𝑡 |𝑋 ∈ 𝜒 (𝑡)} is a non-empty connected subset in 𝑇 . Now suppose for sake of contradiction that the set is disconnected in 𝑇 ′ . Then there exists a connected component 𝐶 1 with vertex 𝑡 1 ∈ nodes(𝑇 ′ ) and a connected component 𝐶 2 with vertex 𝑡 2 ∈ nodes(𝑇 ) ′ s.t. 𝑋 ∈ 𝜒 ′ (𝑡 1 ) and 𝑋 ∈ 𝜒 ′ (𝑡 2 ). Additionally, 𝑡 1, 𝑡 2 ∈ nodes(𝑇 ), and 𝑡 1 and 𝑡 2 are connected in 𝑇 . Consider the path from 𝑡 1 to 𝑡 2 in 𝑇 . Then there exists a vertex 𝑡 𝑗 along this path s.t. 𝑋 ∈ 𝜒 (𝑡 𝑗 ) and 𝑋 ∉ 𝜒 ′ (𝑡 𝑗 ). This is a contradiction, because we
18
Eden Chmielewski, Andrei Draghici, Dan Olteanu, and Haozhe Zhang
only remove bound variables, and 𝑋 is free. Thus, for all 𝑋 ∈ V ′ , {𝑡 |𝑋 ∈ 𝜒 ′ (𝑡)} forms a non-empty connected subtree in 𝑇 ′ , and so (𝑇 ′, 𝜒 ′ ) is a valid tree decomposition of 𝑄 ′ . Now we will show the width of (𝑇 ′, 𝜒 ′ ) is less than or equal to the width of (𝑇 , 𝜒). Consider a vertex 𝑡 ∈ nodes(𝑇 ) = nodes(𝑇 ′ ). Then 𝜒 ′ (𝑡) ⊆ 𝜒 (𝑡). Consider an optimal fractional edge cover 𝜌𝑡 of 𝜒 (𝑡). Let 𝜌𝑡′ map each 𝑒 ′ ∈ E ′ to zero. Let 𝑒 ∈ E be an edge of H that contains a free variable. Because T is a forest of view trees s.t. each query is free-dominated and 𝑄 is the join of the root views (whose schemas are the edges E ′ ) there exists an edge 𝑒 ′ ∈ E ′ s.t. 𝑒 ′ = 𝑒 ∩ F. Increment 𝜌𝑡′ (𝑒 ′ ) by 𝜌𝑡 (𝑒), and repeat this for all edges of E that contain a free variable. In the end, 𝜌𝑡′ is a fractional edge cover for 𝜒 ′ (𝑡) (because 𝜒 ′ (𝑡) contains only free variables), and Í Í 𝜌 ∗ (𝑄 ′ [𝜒 ′ (𝑡)]) ≤ 𝑒 ∈ E ′ [ 𝜒 (𝑡 ) ] 𝜌𝑡′ (𝑒) ≤ 𝑒 ∈ E [ 𝜒 (𝑡 ) ] 𝜌𝑡 (𝑒) = 𝜌 ∗ (𝑄 [𝜒 (𝑡)]). Further, because this holds true for all vertices 𝑡 ∈ nodes(𝑇 ), we have fhtw(𝑄 ′ ) =
min (𝑇1 ,𝜒 ) ∈TD(𝑄 (F) ) ′
width(𝑇1, 𝜒)
≤ width(𝑇 , 𝜒) = ≤
𝜌 ∗ (𝑄 [𝜒 (𝑡)]) ∑︁ max ′ 𝜌𝑡′ (𝑒)
max
𝑡 ∈nodes(𝑇 ′ )
𝑡 ∈nodes(𝑇 )
≤
∑︁
max ′
𝑡 ∈nodes(𝑇 )
=
𝑒 ∈ E ′ [ 𝜒 ′ (𝑡 ) ]
max
𝜌𝑡 (𝑒)
𝑒 ∈ E [ 𝜒 (𝑡 ) ]
𝜌 ∗ (𝑄 [𝜒 (𝑡)])
𝑡 ∈nodes(𝑇 )
= width(𝑇 , 𝜒) = fhtw(𝑄 ′′ ) where 𝑄 ′′ is the Boolean version of 𝑄. 5
□
Lower Bounds for Non-P-Hierarchical Queries
In this section, we prove Theorem 2 that establishes lower bounds for the maintenance of queries without self-joins under inserts over different semirings. In particular, we show that non-𝑝hierarchical queries over 𝐾-databases, where 𝐾 is the natural or tropical semiring, cannot be maintained with constant update time and constant enumeration delay under widely held conjectures. We then sketch the extension of the proof for further semirings in K. Our lower bounds rely on the hardness of the Online Matrix-Vector Multiplication (OMv) problem. We start by introducing the OMv problem. Definition 26 (Online Matrix-Vector Multiplication (OMv) [13]). We are given an 𝑛 × 𝑛 Boolean matrix M and receive 𝑛 Boolean column vectors v1, . . . , v𝑛 of size 𝑛, one by one; after seeing each vector v𝑖 , we output the product Mv𝑖 before we see the next vector. It is strongly believed that the OMv problem cannot be solved in subcubic time. Conjecture 27 (OMv conjecture, Theorem 2.2 [13]). For any 𝛾 > 0, there is no algorithm that solves this problem in time O (𝑛 3−𝛾 ) Although, we base our results on the hardness of the OMv conjecture, we introduce the following additional conjecture which is a consequence of the OMv conjecture [13] since it is a more suitable starting point for some of our reductions. Definition 28 (Online Vector-Matrix-Vector Multiplication (OuMv) [13]). We are given an 𝑛 × 𝑛 Boolean matrix M and receive 𝑛 pairs of Boolean column vectors (u1, v1 ), . . . , (u𝑛 , v𝑛 ) of size
The Role of Semirings in Incremental View Maintenance
19
𝑛, one by one; after seeing each pair of vectors (u𝑖 , v𝑖 ), we output the product u𝑖 Mv𝑖 before we see the next pair. Conjecture 29 (OuMv conjecture, Theorem 2.4 [13]). For any 𝛾 > 0, there is no algorithm that solves this problem in time O (𝑛 3−𝛾 ) 5.1
Intuition behind our Lower Bound Proofs
The OMv and OuMv conjectures are widely used to prove conditional lower bounds [6, 13, 15, 17]. In all subsequent lower bound proofs, we reduce the OMv or OuMv problem to the IVM problem of a query 𝑄 over a 𝐾-database of size 𝑁 = Θ(𝑛 2 ). That is, if there were an algorithm maintaining a 1 1 non-p-hierarchical query with O (𝑁 2 −𝛾 ) enumeration delay and O (𝑁 2 −𝛾 ) amortized update time, for any 𝛾 > 0, one could use this algorithm to solve the OMv problem in subcubic time. Preprocessing time. To expose the matrix M and the sequence of vectors v1, . . . , v𝑛 from the OMv problem to our IVM oracle for 𝑄, we need to (1) populate an N-database on which 𝑄 is maintained and (2) extract from the result of 𝑄 the sequence of result vectors Mv1, . . . , Mv𝑛 . The first task requires inserts to the database, while the second task requires enumeration of the query result. As we show in the following proofs, the cost of these two tasks, if they were to use 𝑂 (𝑛 1−2𝛾 ) amortized update time and enumeration delay, for some 𝛾 > 0, already contradict the OMv conjecture as they would yield an O (𝑛 3−2𝛾 ) algorithm for the OMv problem. Therefore, an O (𝑛 3−2𝛾 ) = O (𝑁 3/2−𝛾 ) preprocessing time still contradicts the OMv conjecture. For our next reductions, however, we have no preprocessing time as we start with the empty database. Simulating Deletes using Inserts. Prior lower bound proofs based on reductions from OMv/OuMv were for the insert-delete setting, e.g., [6, 15, 17], whereas our proofs are for the more restricted insert-only setting. For the insert-delete setting, the OMv problem is encoded dynamically into the database: at each step, as a new vector v𝑘 arrives, the reduction deletes the contents of the relation representing the previous vector and inserts the new one. Because our framework strictly prohibits deletions, we must encode the OMv steps differently. We bypass the need for deletions by continually inserting the exact same tuples into the database, but with carefully engineered payloads. However, because older tuples are not deleted, the relation’s overall state becomes corrupted by prior insertions. To extract the correct answer for the current step, we must logically filter out this prior data using different algebraic mechanisms depending on the underlying semiring. The Natural Semiring: Accumulation and Differencing. In the natural semiring, payloads accumulate additively. At each step 𝑘, we insert tuples corresponding to the indices 𝑖 such that v𝑘 [𝑖] = 1 with a payload of 1. Because previous insertions cannot be deleted, the target relation represents Í the cumulative sum of all vectors seen so far, t𝑘 = 𝑘𝑖=1 v𝑖 . Consequently, enumerating the query computes the matrix-vector product over this cumulative state, yielding Mt𝑘 . We bypass the lack of deletions by taking the algebraic difference between successive steps: subtracting the evaluated vector of step 𝑘 − 1 from step 𝑘 perfectly isolates the result for the current step, Mv𝑘 . The Tropical Semiring: Dominance via Minimization. In the tropical semiring, where the operators are minimum and addition, we cannot use subtraction to isolate the current step. Instead, we simulate state replacement by encoding “freshness” directly into the payloads. At each step 𝑘, we insert the indices 𝑖 such that v𝑘 [𝑖] = 1 with a strictly decreasing, negative payload Δ𝑘 (where Δ𝑘 < Δ𝑘 −1 ). Because the semiring’s summation acts as a minimum operator, the lowest-cost path through the joins will always be dominated by the most recently inserted tuples. Stale tuples from earlier steps retain larger payloads and are naturally filtered out by the minimization. By simply checking if the query’s output exactly matches the expected combined payload of fresh tuples (for
20
Eden Chmielewski, Andrei Draghici, Dan Olteanu, and Haozhe Zhang
instance, 2Δ𝑘 ), we can determine if a valid OMv intersection exists at the current step, rendering the older data effectively invisible. 5.2
The Natural Semiring
We first show the lower bound for the natural semiring (N, +, ×). Let 𝑄 be any conjunctive query without self-joins that is not p-hierarchical. We reduce the OMv problem to the incremental maintenance of 𝑄. The query 𝑄 must violate one of the two conditions from Def. 8. We next analyze each of these two cases in isolation. Í Case 1. Assume 𝑄 violates the bound-bound interaction, that is, 𝑄 is of the form 𝑄 (F) = B 𝑅(𝑋, Z𝑅 ) · 𝑆 (𝑋, 𝑌 , Z𝑠 ) · 𝑇 (𝑌 , Z𝑇 ) · 𝑈 1 (Z1 ) · . . . · 𝑈𝑚 (Z𝑚 ), subject to the constraints 𝑋, 𝑌 ∉ F, 𝑋 ∉ Z𝑇 , and 𝑌 ∉ Z𝑅 . Í Database construction. We simplify the query 𝑄 to its hard sub-query 𝑄 ′ () = 𝑋 ,𝑌 𝑅(𝑋 ) ·𝑆 (𝑋, 𝑌 ) · 𝑇 (𝑌 ) by fixing the variables in vars(𝑄) \ {𝑋, 𝑌 } to a special constant ★ that is not in the domains of 𝑋 and 𝑌 . For conciseness, we overload ★ to also represent a tuple consisting entirely of this constant, with arity determined by a relation’s schema. To neutralize the effect of the relations 𝑈 1, . . . , 𝑈𝑚 on the joins on 𝑋 and 𝑌 , we initialize each 𝑈𝑖 (Z𝑖 ) as follows: • If 𝑍𝑖 ∩ {𝑋, 𝑌 } = ∅, we insert 𝑈𝑖 (★) ↦→ 1. • If 𝑍𝑖 ∩ {𝑋, 𝑌 } = {𝑋 } or 𝑍𝑖 ∩ {𝑋, 𝑌 } = {𝑌 }, we insert 𝑈𝑖 ( 𝑗, ★) ↦→ 1 for all 𝑗 ∈ [𝑛], where 𝑗 is the value for 𝑋 or 𝑌 . • If 𝑍𝑖 ∩ {𝑋, 𝑌 } = {𝑋, 𝑌 }, we insert 𝑈𝑖 ( 𝑗, 𝑘, ★) ↦→ 1 for all ( 𝑗, 𝑘) ∈ [𝑛] 2 , where 𝑗, 𝑘 are the values for 𝑋, 𝑌 . Note that 1 is the multiplicative identity of the natural semiring. By construction, 𝑄 (★) and 𝑄 ′ () are equivalent for the above-constructed database with arbitrary N-relations 𝑅, 𝑆, and 𝑇 . Let M be the 𝑛 × 𝑛 Boolean matrix in the OMv problem. We initialize the database by encoding M into the N-relation 𝑆: for every M𝑖 𝑗 = 1, we insert 𝑆 (𝑖, 𝑗, ★) ↦→ 1. The OMv problem also gives a sequence of vectors v1, . . . , v𝑛 . At step 𝑘 ∈ [𝑛], we must compute the vector Mv𝑘 . Upon receiving v𝑘 , we make the following inserts into relation 𝑇 . For every index 𝑗 such that v𝑘 [ 𝑗] = 1, we insert 𝑇 ( 𝑗, ★) ↦→ 1. For all other indices 𝑗, i.e., indices 𝑗 for which v𝑘 [ 𝑗] = 0, we make no inserts. A key constraint of our reduction is that we cannot delete from the database relations. Yet we can achieve the effect of deletes followed by inserts by inspecting the difference in the query answer before and after inserts. This is explained next. Since we cannot delete the previous entries in 𝑇 and because the natural semiring accumulates payloads, the vector represented by 𝑇 at step 𝑘 Í𝑘 is the cumulative vector t𝑘 = 𝑚=1 v𝑚 . This sum is over the natural semiring, not the Boolean semiring. Even though, v1, . . . , v𝑛 are Boolean vectors, we treat them as integer vectors and recover the Boolean result out of the query answer. The database implicitly holds the state u𝑘 = Mt𝑘 . Recovering the result for the OMv problem from the query result. To extract the 𝑛-dimensional vector u𝑘 from the scalar result of 𝑄 (★), we execute a sequence of 2𝑛 query enumerations and inserts. For each index 𝑖 ∈ [1, 𝑛]: (𝑖 ) (1) We enumerate the current scalar output 𝑄 before = 𝑄 (★). (2) We insert 𝑅(𝑖) ↦→ 1. (𝑖 ) (3) We enumerate the new scalar output 𝑄 after = 𝑄 (★).
Let 𝑅 ′ (𝑖) be the value of 𝑅(𝑖) before we inserted 𝑅(𝑖) ↦→ 1. Inserting 𝑅(𝑖) ↦→ 1 increases the scalar query answer by exactly the value given by the dot product between the 𝑖-th row of M and the
The Role of Semirings in Incremental View Maintenance
21
vector t𝑘 : ∑︁ ª © ∑︁ (𝑖 ) (𝑖 ) 𝑄 after − 𝑄 before 𝑅(𝑥) · 𝑆 (𝑥, 𝑦) · 𝑇 (𝑦) + 𝑅(𝑖) · 𝑆 (𝑖, 𝑦) · 𝑇 (𝑦) ® = 𝑦 ¬ «𝑥 ∈ [𝑛]\{𝑖 },𝑦 ∑︁ ∑︁ ª © 𝑅 ′ (𝑖) · 𝑆 (𝑖, 𝑦) · 𝑇 (𝑦) ® 𝑅(𝑥) · 𝑆 (𝑥, 𝑦) · 𝑇 (𝑦) + − 𝑦 𝑥 ∈ [𝑛]\{𝑖 },𝑦 ¬ «∑︁ ∑︁ ′ = (𝑅(𝑖) − 𝑅 (𝑖)) ·𝑆 (𝑖, 𝑦) · 𝑇 (𝑦) = 𝑆 (𝑖, 𝑦) · 𝑇 (𝑦) = M𝑖 t𝑘 = u𝑘 [𝑖] {z } 𝑦 | 𝑦 1
We record this difference as the 𝑖-th element of u𝑘 . Í After 2𝑛 enumeration steps, we can reconstruct the cumulative vector u𝑘 = M 𝑚∈ [𝑘 ] v𝑚 . To isolate the answer at the current step, we subtract the vector u𝑘 −1 from the previous step 𝑘 − 1: u𝑘 − u𝑘 −1 = Mv𝑘 . To recover the Boolean vector Mv𝑘 , we check if u𝑘 [𝑖] − u𝑘 −1 [𝑖] > 0, for each 𝑖 ∈ [𝑛]. Time analysis. There is no preprocessing as we start with the empty database. At each step 𝑘 ∈ [𝑛], the database size is 𝑁 = Θ(𝑛 2 ), as we keep the distinct tuples in each relation; on inserting a tuple 𝑡 with payload 𝑝 2 , if 𝑡 is already in the database with payload 𝑝 1 , then we keep one copy of 𝑡 in the database with payload 𝑝 1 + 𝑝 2 . In each of the 𝑛 steps, we insert at most 𝑛 tuples into 𝑇 , and exactly 𝑛 probing tuples into 𝑅. The total number of insertions per step is bounded by 2𝑛. At each step we enumerate the scalar result of the query 𝑄 (★) exactly 2𝑛 times. So, over 𝑛 steps we perform at most 2𝑛 2 inserts and 2𝑛 2 enumeration requests. 3 Assume there exists an algorithm that maintains 𝑄 with O (𝑁 2 −𝛾 ) = O (𝑛 3−2𝛾 ) preprocessing 1 1 time, O (𝑁 2 −𝛾 ) = O (𝑛 1−2𝛾 ) amortized insert time and O (𝑁 2 −𝛾 ) = O (𝑛 1−2𝛾 ) enumeration delay over a sequence of O (𝑁 ) inserts, for some 𝛾 > 0. Then, the time needed by our algorithm is O (𝑛 3−2𝛾 + 2𝑛 2 ) · O (𝑛 1−2𝛾 ) + O (2𝑛 2 ) · O (𝑛 1−2𝛾 ) = O (𝑛 3−2𝛾 ). This is subcubic for every 𝛾 > 0 and contradicts the OMv conjecture. Case 2. Now, assume that the query 𝑄 violates the bound-free interaction of Def. 8. This means Í 𝑄 is of the form 𝑄 (𝑋, F) = B 𝑆 (𝑋, 𝑌 , Z𝑠 ) ·𝑇 (𝑌 , Z𝑇 ) ·𝑈 1 (Z1 ) · . . . ·𝑈𝑚 (Z𝑚 ), where 𝑌 ∉ F and 𝑋 ∉ Z𝑇 . Again, we reduce the OMv problem to the incremental maintenance of 𝑄 and proceed with an identical preprocessing step. Database construction. Let M be the 𝑛 × 𝑛 Boolean matrix in the OMv problem. We initialize the database by encoding M into the N-relation 𝑆: for every M𝑖 𝑗 = 1, we insert 𝑆 (𝑖, 𝑗, ★) ↦→ 1. For relations 𝑈 1 (Z1 ), . . . , 𝑈𝑚 (Z𝑚 ), we apply the general auxiliary setup Í from Case 1. Thus, for any 𝑖 ∈ [𝑛] we have that 𝑄 (𝑖, ★) is equivalent to its sub-query 𝑄 ′′ (𝑖) = 𝑗 ∈ [𝑛] 𝑆 (𝑖, 𝑗, ★) · 𝑇 ( 𝑗, ★) on the above-constructed database. At each step 𝑘 ∈ [𝑛], vector v𝑘 arrives. For every 𝑖 ∈ [𝑛] such that v𝑘 [𝑖] = 1, we insert 𝑇 (𝑖, ★) ↦→ 1. As before, the payload of a tuple (𝑖, ★) in 𝑇 at step 𝑘 is exactly the sum of its insertions Í across all steps 1 to 𝑘. Let this cumulative vector be t𝑘 = 𝑗 ∈ [𝑘 ] v 𝑗 . Thus, 𝑇 (𝑖, ★) = t𝑘 [𝑖]. Again, we treat vectors v1, . . . .v𝑛 as integer vectors.
22
Eden Chmielewski, Andrei Draghici, Dan Olteanu, and Haozhe Zhang
Recovering the result for the OMv problem from the query result. We enumerate the result of the query 𝑄 (𝑋, ★). For a specific output binding 𝑋 = 𝑖, the query evaluates to: ∑︁ ∑︁ 𝑄 (𝑖, ★) = 𝑆 (𝑖, 𝑗, ★) · 𝑇 ( 𝑗, ★) = M𝑖 𝑗 t𝑘 [ 𝑗] 𝑗 ∈ [𝑛]
𝑗 ∈ [𝑛]
Thus, enumerating all 𝑛 results of the query yields the complete integer vector Mt𝑘 . To extract the required Boolean OMv answer Mv𝑘 , the algorithm maintains the integer vector from the previous step, Mt𝑘 −1 , and computes the element-wise difference: Mv𝑘 = Mt𝑘 − Mt𝑘 −1 and check for each 𝑖 ∈ {1, . . . , 𝑛} if (Mv𝑘 ) [𝑖] is greater than zero or not. Time analysis. We start with the empty database and there is no preprocessing. At each step 𝑘 ∈ [𝑛], the database size is 𝑁 = Θ(𝑛 2 ), as we keep the distinct tuples in each relation; on inserting a tuple 𝑡 with payload 𝑝 2 , if 𝑡 is already in the database with payload 𝑝 1 , then we keep one copy of 𝑡 in the database with payload 𝑝 1 + 𝑝 2 . In each of the 𝑛 steps, we insert at most 𝑛 tuples into 𝑇 . The total number of insertions per step is bounded by 𝑛. At each step we enumerate exactly 𝑛 tuples from the query 𝑄 (X, ★). So, over 𝑛 steps we perform exactly 𝑛 2 inserts and enumerate exactly 𝑛 2 tuples. 1 Assume there exists an algorithm that maintains 𝑄 with O (𝑁 2 −𝛾 ) = O (𝑛 1−2𝛾 ) amortized insert 1 time and O (𝑁 2 −𝛾 ) = O (𝑛 1−2𝛾 ) enumeration delay over a sequence of O (𝑁 ) inserts, for some 𝛾 > 0. Then, the time needed by our algorithm is O (𝑛 2 ) · O (𝑛 1−2𝛾 ) + O (𝑛 2 ) · O (𝑛 1−2𝛾 ) = O (𝑛 3−2𝛾 ). This is subcubic for every 𝛾 > 0 and contradicts the OMv conjecture. This concludes the proof for the natural semiring. We next show how the reduction works by means of a concrete example. Example 30. Consider the following Boolean matrix M and sequence of input vectors v1 and v2 : 1 1 0 1 0 © ª © ª © ª M = 0 1 1® , v1 = 0® , v2 = 1® «1 0 0¬ «0¬ «0¬ Our goal isÍto compute Mv1 and then compute Mv2 , relying only on the scalar output of the hard query 𝑄 () = 𝑋 ,𝑌 𝑅(𝑋 ) · 𝑆 (𝑋, 𝑌 ) · 𝑇 (𝑌 ). In the preprocessing phase, we initialize relation 𝑆 to represent the matrix M: 𝑋 𝑌 ↦→ S[𝑋, 𝑌 ] 1 1 ↦→ 1 1 2 ↦→ 1 2 2 ↦→ 1 2 3 ↦→ 1 3 1 ↦→ 1 Initially, the relations 𝑅 and 𝑇 are empty (i.e., mapping all tuples to 0). Step 1: We start with the insert 𝑇 (1) ↦→ 1. Thus, we have the cumulative vector t1 = v1 = (1, 0, 0) ⊤ . The relation 𝑇 now contains a single tuple: 𝑌 1
↦→ T[𝑌 ] ↦→ 1
(1) Next, we use updates to 𝑅 and query evaluations to find u1 . Initially, 𝑄 before = 0.
The Role of Semirings in Incremental View Maintenance
23
(1) (1) (1) (1) • For 𝑖 = 1: We insert 𝑅(1) ↦→ 1. 𝑄 before = 0, 𝑄 after = 1 =⇒ 𝑄 after − 𝑄 before =1−0=1 (2) (2) (2) (2) • For 𝑖 = 2: We insert 𝑅(2) ↦→ 1. 𝑄 before = 1, 𝑄 after = 1 =⇒ 𝑄 after − 𝑄 before =1−1=0 (3) (3) (3) (3) • For 𝑖 = 3: We insert 𝑅(3) ↦→ 1. 𝑄 before = 1, 𝑄 after = 2 =⇒ 𝑄 after − 𝑄 before =2−1=1
At the end of Step 1, we have that u1 = (1, 0, 1) ⊤ : 1 0 1 © ª © ª © ª u1 − u0 = 0® − 0® = 0® = Mv1 «1¬ «0¬ «1¬ Step 2: We process the insert 𝑇 (2) ↦→ 1. This gives us t2 = v1 + v2 = (1, 1, 0) ⊤ . The relation 𝑇 now maps two tuples to 1: 𝑌 ↦→ T[𝑌 ] 1 ↦→ 1 2 ↦→ 1 Before any new updates to 𝑅, the query enumerates the current database state based on the accumu(1) lated payloads from Step 1. We find 𝑄 before = 4. We again probe by updating 𝑅: (1) (1) 1 1 • For 𝑖 = 1: We insert 𝑅(1 ↦→ 1). 𝑄 before = 4, 𝑄 after = 6 =⇒ 𝑄 after − 𝑄 before =6−4=2 (2) (2) 2 2 • For 𝑖 = 2: We insert 𝑅(2 ↦→ 1). 𝑄 before = 6, 𝑄 after = 7 =⇒ 𝑄 after − 𝑄 before =7−6=1 (3) (3) 3 3 • For 𝑖 = 3: We insert 𝑅(3 ↦→ 1). 𝑄 before = 7, 𝑄 after = 8 =⇒ 𝑄 after − 𝑄 before =8−7=1
At the end of Step 2, we have that u2 = (2, 1, 1) ⊤ : 1 2 1 © ª © ª © ª u2 − u1 = 1® − 0® = 1® = Mv2 «1¬ «1¬ «0¬ Because we operate over the natural semiring (N, +, ×), payloads accumulate monotonically. By the end of Step 2, the state of relation 𝑅 reflects a payload of 2 for every probed tuple: 𝑋 1 2 3
↦→ R[𝑋 ] ↦→ 2 ↦→ 2 ↦→ 2
Generalizations of the natural semiring. The previous proof can be immediately extended to databases over semirings with domains that subsume the set of natural numbers or domains of tuples where one its component ranges over the natural numbers. Prominent examples include the universal provenance semiring (N[𝑋 ], +, ·) whose domain consists of multivariate polynomials with natural number coefficients [12], and the covariance semiring ((N, N𝑚 , N𝑚×𝑚 ), +, ·) [16, Def. 9]. For the universal provenance we can restrict the domain to polynomials of degree zero (natural numbers) and for the covariance semiring we restrict the domain to triples from (N, 0𝑚×1, 0𝑚×𝑚 ). 5.3
The Tropical Semiring
We show the lower bound for the min tropical semiring T = (R ∪ {+∞}, min, +), a similar proof works for the max tropical (or arctic) semiring (R ∪ {−∞}, max, +). The proof is different from the one for the natural semiring in Section 5.2. Let 𝑄 be any conjunctive query without self-joins that is not p-hierarchical. There are two ways in which 𝑄 can violate the p-hierarchical property.
24
Eden Chmielewski, Andrei Draghici, Dan Olteanu, and Haozhe Zhang
Case 1. We assume that 𝑄 violates the bound-bound interaction, so it is of the form 𝑄 (F) = minB 𝑅(𝑋, Z𝑅 ) + 𝑆 (𝑋, 𝑌 , Z𝑠 ) +𝑇 (𝑌 , Z𝑇 ) +𝑈 1 (Z1 ) + . . . +𝑈𝑚 (Z𝑚 ), subject to the constraints 𝑋, 𝑌 ∉ F, 𝑋 ∉ Z𝑇 , and 𝑌 ∉ Z𝑅 . We reduce the OuMv problem to the incremental maintenance problem for 𝑄. Database construction. Similar to the previous reductions, we simplify the query 𝑄 to its hard sub-query 𝑄 ′ () = min𝑋 ,𝑌 𝑅(𝑋 ) + 𝑆 (𝑋, 𝑌 ) + 𝑇 (𝑌 ) by fixing the variables in vars(𝑄) \ {𝑋, 𝑌 } to a special constant ★ that is not in the domains of 𝑋 and 𝑌 . For conciseness, we overload ★ to also represent a tuple consisting entirely of this constant, with arity determined by the relation’s schema. To neutralize the effect of the relations 𝑈 1, . . . , 𝑈𝑚 on the joins on 𝑋 and 𝑌 , we initialize each 𝑈𝑖 (Z𝑖 ) as follows: • If 𝑍𝑖 ∩ {𝑋, 𝑌 } = ∅, we insert 𝑈𝑖 (★) ↦→ ∞. • If 𝑍𝑖 ∩ {𝑋, 𝑌 } = {𝑋 } or 𝑍𝑖 ∩ {𝑋, 𝑌 } = {𝑌 }, we insert 𝑈𝑖 ( 𝑗, ★) ↦→ ∞ for all 𝑗 ∈ [𝑛], where 𝑗 is the value for 𝑋 or 𝑌 . • If 𝑍𝑖 ∩ {𝑋, 𝑌 } = {𝑋, 𝑌 }, we insert 𝑈𝑖 ( 𝑗, 𝑘, ★) ↦→ ∞ for all ( 𝑗, 𝑘) ∈ [𝑛] 2 , where 𝑗, 𝑘 are the values for 𝑋, 𝑌 . Note that ∞ is the multiplicative identity of the tropical semiring. By construction, 𝑄 (★) =
min
𝑅( 𝑗, ★) + 𝑆 (𝑖, 𝑗, ★) + 𝑇 (𝑘, ★).
𝑖 ∈ [𝑛],𝑗 ∈ [𝑛]
Let M be the 𝑛 × 𝑛 Boolean matrix, and let (u𝑖 , v𝑖 ) be the sequence of vector pairs at step 𝑖 ∈ [𝑛]. We map the matrix dimension to the database size such that 𝑁 = Θ(𝑛 2 ). We encode the matrix M into the T-relation 𝑆. For all pairs ( 𝑗, 𝑘) ∈ [𝑛] 2 : • If M 𝑗𝑘 = 1, we insert 𝑆 ( 𝑗, 𝑘, ★) ↦→ 0. • If M 𝑗𝑘 = 0, we insert 𝑆 ( 𝑗, 𝑘, ★) ↦→ ∞. Additionally, we initialize 𝑅 and 𝑇 by inserting ( 𝑗, ★) with payload 0 for all 𝑗 ∈ {1, . . . , 𝑛}. At each step 𝑖, we receive vectors u𝑖 and v𝑖 . Since we operate in an insert-only setting, we cannot empty the relations 𝑅 and 𝑇 using deletes. Instead, we insert new versions of tuples with strictly smaller payloads, ensuring that the fresh data dominates the minimization. Let 𝐶 ≥ 2 be a constant. We define the payload for step 𝑖 as Δ𝑖 = −𝑖 · 𝐶. Observe that Δ𝑖 < Δ𝑖 −1 . We perform the following updates: • For every 𝑗 such that u𝑖 [ 𝑗] = 1, insert 𝑅( 𝑗, ★) ↦→ Δ𝑖 . • For every 𝑘 such that v𝑖 [𝑘] = 1, insert 𝑇 (𝑘, ★) ↦→ Δ𝑖 . For indices where the Boolean vector is 0 we perform no inserts; they retain payloads from previous steps 𝑡 < 𝑖 (where Δ𝑡 > Δ𝑖 ). Recovering the result for the OMv problem from the query result. Let 𝑃 ( 𝑗, 𝑘) = 𝑅( 𝑗, ★) + 𝑆 ( 𝑗, 𝑘, ★) + 𝑇 (𝑘, ★). By construction, we have 𝑄 (★) = min 𝑗,𝑘 𝑃 ( 𝑗, 𝑘). Consider the minimum path cost at step 𝑖. We distinguish two cases: • Case 1: u𝑖⊤ Mv𝑖 = 1. Thus, there exist indices 𝑗, 𝑘 such that u𝑖 [ 𝑗] = 1, v𝑖 [𝑘] = 1, and M 𝑗𝑘 = 1. For this specific pair, the current payloads in 𝑅 and 𝑇 are Δ𝑖 , and 𝑆 ( 𝑗, 𝑘, ★) = 0. Thus: 𝑃 ( 𝑗, 𝑘) = Δ𝑖 + 0 + Δ𝑖 = 2Δ𝑖 • Case 2: u𝑖⊤ Mv𝑖 = 0. For any pair ( 𝑗, 𝑘), if M 𝑗𝑘 = 0, then 𝑆 ( 𝑗, 𝑘, ★) = ∞ and 𝑃 ( 𝑗, 𝑘) = ∞. Consider a pair where M 𝑗𝑘 = 1 (so 𝑆 ( 𝑗, 𝑘, ★) = 0), but the vectors do not match (i.e., u𝑖 [ 𝑗] = 0 or v𝑖 [𝑘] = 0). This implies that at least one of the tuples in 𝑅 or 𝑇 was not updated in step 𝑖. The most recent update to that tuple occurred at some step 𝑡 ≤ 𝑖 − 1. Since payloads are decreasing, the "stale" payload is at least Δ𝑖 −1 . Therefore, the path cost is bounded by: 𝑃 ( 𝑗, 𝑘) ≥ Δ𝑖 −1 + 0 + Δ𝑖 + = −(𝑖 − 1)𝐶 − 𝑖𝐶 = 2Δ𝑖 + 𝐶
The Role of Semirings in Incremental View Maintenance
25
Since 𝐶 ≥ 2, 2Δ𝑖 + 𝐶 > 2Δ𝑖 . Thus, u𝑖⊤ Mv𝑖 = 1 ⇐⇒ 𝑄 (★) = 2Δ𝑖 . Time analysis. The database size is 𝑁 = Θ(𝑛 2 ). In each of the 𝑛 steps, we insert 𝑛 tuples into 𝑅, and 𝑛 tuples into 𝑇 . The total number of insertions per step is bounded by 2𝑛. At each step we enumerate the scalar result of the query 𝑄 (★) once. So, over 𝑛 steps we perform at most 2𝑛 2 inserts and 𝑛 enumeration requests. 1 Assume there exists an algorithm that maintains 𝑄 with O (𝑁 2 −𝛾 ) = O (𝑛 1−2𝛾 ) amortized insert 1 time and O (𝑁 2 −𝛾 ) = O (𝑛 1−2𝛾 ) enumeration delay over a sequence of O (𝑁 ) inserts, for some 𝛾 > 0. Then, the time needed by our algorithm is O (2𝑛 2 ) · O (𝑛 1−2𝛾 ) + O (𝑛) · O (𝑛 1−2𝛾 ) = O (𝑛 3−2𝛾 ). This is subcubic for every 𝛾 > 0 and contradicts the OMv conjecture. Case 2. Now, assume that 𝑄 violates the bound-free interaction, so it is of the form 𝑄 (𝑋, F) = minB 𝑆 (𝑋, 𝑌 , Z𝑠 ) + 𝑇 (𝑌 , Z𝑇 ) + 𝑈 1 (Z1 ) + . . . + 𝑈𝑚 (Z𝑚 ), where 𝑌 ∉ F and 𝑋 ∉ Z𝑇 . We reduce the OMv problem to the IVM problem for 𝑄. Database construction. As before, we map the matrix dimension to the database size such that 𝑁 = Θ(𝑛 2 ) and use the specialized constant value ★. We encode the matrix M into the T-relation 𝑆. For all pairs ( 𝑗, 𝑘) ∈ [𝑛] 2 : • If M 𝑗𝑘 = 1, we insert 𝑆 ( 𝑗, 𝑘, ★) ↦→ 0. • If M 𝑗𝑘 = 0, we insert 𝑆 ( 𝑗, 𝑘, ★) ↦→ ∞. Additionally, we initialize 𝑇 by inserting ( 𝑗, ★) with payload 0 for all 𝑗 ∈ {1, . . . , 𝑛}. For relations 𝑈 1 (Z1 ), . . . , 𝑈𝑚 (Z𝑚 ), we apply the general auxiliary setup with 1Z = 0 from the previous proof. Thus, 𝑄 (𝑋, ★) = min 𝑆 (𝑋, 𝑌 , ★) + 𝑇 (𝑌 , ★). 𝑌
At each step 𝑖 ∈ [𝑛], we receive vector v𝑖 . We define the payload Δ𝑖 = −𝑖 · 𝐶 for a constant 𝐶 ≥ 2, ensuring Δ𝑖 < Δ𝑖 −1 . For every index 𝑘, for which v𝑖 [𝑘] = 1, we insert 𝑇 (𝑘, ★) ↦→ Δ𝑖 . For every index 𝑘, for which v𝑖 [𝑘] = 0, we keep the previous payload, which is greater than or equal to Δ𝑖 −1 . Recovering the result for the OMv problem from the query result. Consider the value of the join for a specific 𝑗: 𝑃 ( 𝑗) = min (𝑆 ( 𝑗, 𝑘) + 𝑇 (𝑘)) . 𝑘
• Case 1: (Mv𝑖 ) 𝑗 = 1. There exists some 𝑘 such that M 𝑗𝑘 = 1 and v𝑖 [𝑘] = 1. For this 𝑘, 𝑆 ( 𝑗, 𝑘) = 0 and 𝑇 (𝑘) has the fresh payload Δ𝑖 . 𝑃 ( 𝑗) ≤ 0 + Δ𝑖 = Δ𝑖 . • Case 2: (Mv𝑖 ) 𝑗 = 0. For all 𝑘, either M 𝑗𝑘 = 0 (so 𝑆 ( 𝑗, 𝑘) = ∞) or v𝑖 [𝑘] = 0 (so 𝑇 (𝑘) has stale payload ≥ Δ𝑖 −1 ). 𝑃 ( 𝑗) ≥ 0 + Δ𝑖 −1 > Δ𝑖 . By filtering for tuples where the payload is exactly Δ𝑖 , we correctly recover exactly the indices 𝑗 where the result vector is 1. Time Analysis. We start with the empty database and there is no preprocessing. At each step 𝑘 ∈ [𝑛], the database size is 𝑁 = Θ(𝑛 2 ), as we keep the distinct tuples in each relation; on inserting a tuple 𝑡 with payload 𝑝 2 , if 𝑡 is already in the database with payload 𝑝 1 , then we keep one copy of 𝑡 in the database with payload min(𝑝 1, 𝑝 2 ). In each of the 𝑛 steps, we insert 𝑛 tuples into 𝑇 . At each step we enumerate exactly 𝑛 tuples from the query 𝑄 (X, ★). So, over 𝑛 steps we perform exactly 𝑛 2 inserts and enumerate exactly 𝑛 2 tuples.
26
Eden Chmielewski, Andrei Draghici, Dan Olteanu, and Haozhe Zhang 1
Assume there exists an algorithm that maintains 𝑄 with O (𝑁 2 −𝛾 ) = O (𝑛 1−2𝛾 ) amortized insert 1 time and O (𝑁 2 −𝛾 ) = O (𝑛 1−2𝛾 ) enumeration delay over a sequence of O (𝑁 ) inserts, for some 𝛾 > 0. Then, the time needed by our algorithm is O (𝑛 2 ) · O (𝑛 1−2𝛾 ) + O (𝑛 2 ) · O (𝑛 1−2𝛾 ) = O (𝑛 3−2𝛾 ). This is subcubic for every 𝛾 > 0 and contradicts the OMv conjecture. Generalization to Idempotent Strictly Ordered Semirings. We can generalize our previous lower bound beyond the specific tropical semiring, by relying on the algebraic properties of idempotency and strictly ordered semirings. To simulate an insert-only sequence, we must be able to inject new payloads that “dominate” old payloads. That is, the sum (in the semiring) of the new payload with the existing payload yields the new payload, so we can effectively forget the existing payload. This is the same effect as deleting a tuple 𝑡 with the existing payload and inserting 𝑡 with the new payload. This can be achieved if the semiring is idempotent. Next, since we may want to use new payloads for each insert, we require that the domain of the semiring contains an infinite strictly increasing chain of elements. Finally, we need to be able to observe if a multiplication contains exclusively new payloads, so the multiplication needs to be strictly monotonic over this chain. As established [9, 12], any idempotent semiring (𝐾, +, ·) induces a natural order ⪯𝐾 defined by: 𝑎 ⪯𝐾 𝑏 ⇐⇒ 𝑎 + 𝑏 = 𝑏. For the tropical semiring, the natural order 𝑎 ⪯𝐾 𝑏 is the reverse order 𝑎 ≥ 𝑏 on Z ∪ {∞}, since 𝑎 min 𝑏 = 𝑏 whenever 𝑎 ≥ 𝑏. For the Boolean semiring, the natural order on the domain {false, true} is false ⪯𝐾 true, since false ∨ true = true. The + semiring operator computes the least upper bound of its operands, effectively allowing the query evaluation to ignore old payloads and only retain the dominant new payloads. To formalize the infinite chain of strictly increasing elements that is preserved by multiplication, we define a specific class of semirings. Definition 31 (Idempotent Strictly Ordered (ISO) Semirings). A semiring (𝐾, +, ·) is idempotent strictly ordered if it is idempotent with a natural order ⪯𝐾 (𝑎 ⪯𝐾 𝑏 ⇐⇒ 𝑎 + 𝑏 = 𝑏) and it satisfies conditions: (1) There exists a countably infinite sequence of elements (𝑐𝑖 )𝑖 ∈ N in 𝐾 such that for all 𝑖 ≥ 1, 𝑐𝑖 ⪯𝐾 𝑐𝑖+1 and 𝑐𝑖 ≠ 𝑐𝑖+1. (2) The multiplication operator (·) is strictly monotonic over this chain. For any elements in the chain where 𝑎 ≺𝐾 𝑏, it holds that 𝑎 · 𝑐 ≺𝐾 𝑏 · 𝑐 for any 𝑐 ≠ 0𝐾 , where 0𝐾 denotes the addition identity of the semiring. The combination of these properties guarantees that the multiplication of exclusively fresh payloads (𝑐𝑖 · 𝑐𝑖 ) strictly dominates multiplications, where one of the payloads precedes the fresh ones (e.g., 𝑐𝑖 −1 · 𝑐𝑖 ). The tropical semiring (Z ∪ {∞}, min, +) belongs to this class by utilizing the chain 𝑐𝑖 = −𝑖 · 𝐶 (for 𝐶 ≥ 2). In this semiring, decreasing payloads map to strictly greater elements in the min-induced natural partial order, and scalar addition strictly preserves these differences. We are now ready to prove the lower bound for idempotent strictly ordered semirings. The lower bounds hold for any idempotent strictly ordered semiring by applying the exact reduction presented for the tropical semiring, under the following homomorphic mapping of the payload assignments and operators: • Identities: The absorbing payload ∞ maps to the addition identity 0𝐾 (the minimum element under ⪯𝐾 ). The neutral payload 0 maps to the multiplicative identity 1𝐾 . • Payloads: The decreasing integers Δ𝑖 map directly to the strictly increasing chain elements 𝑐𝑖 . • Operators: The (min) aggregation maps to the semiring addition (+), which computes the supremum. The scalar addition evaluation maps to the semiring multiplication (·).
The Role of Semirings in Incremental View Maintenance
27
Under this mapping, the fresh product evaluating to Δ𝑖 + Δ𝑖 = 2Δ𝑖 in the tropical reduction maps to 𝑐𝑖 · 𝑐𝑖 in the idempotent strictly ordered semiring. A stale product evaluates to an element bounded by 𝑐𝑖 −1 · 𝑐𝑖 . By Def. 31, strict monotonicity guarantees 𝑐𝑖 −1 · 𝑐𝑖 ≺𝐾 𝑐𝑖 · 𝑐𝑖 . Consequently, the semiring addition operator (+) filters out all stale products by acting as a supremum, yielding exactly 𝑐𝑖 · 𝑐𝑖 if and only if the corresponding Boolean matrix-vector product is 1. The contradiction of the complexity bounds remains identical. 6
Conclusion
In this paper, we study the role of semirings on the incremental view maintenance problem for conjunctive queries. We show that a query can be maintained under single-tuple inserts with amortized constant update time and constant enumeration delay over 𝐾-databases if and only if the query is 𝛼-acyclic p-hierarchical. Here, 𝐾 is the natural or tropical semiring, or generalizations of them. The "only if" result is conditional on the OMv conjecture. We also give a maintenance procedure for arbitrary (so not only 𝛼-acyclic) p-hierarchical queries and show that the amortized time is O (𝑁 fhtw−1 ), where 𝑁 is the length of the sequence of inserts and fhtw is the fractional hypertree width of the Boolean version of the query. There are several immediate lines of future work worth exploring: • Our understanding of optimality for IVM remains severely limited, as it has to be built on lower bounds. Recent work [29] introduced new conditional lower bounds for IVM beyond those conditioned on the OMv problem. A natural further step is to define classes of queries whose maintenance complexity matches the new lower bounds for various semirings. • One challenge brought by our maintenance algorithm for p-hierarchical queries concerns the enumeration of the query result: Whereas the entire query result can be enumerated with constant delay after each insert, it remains open whether such a constant-delay enumeration is possible for the delta of the query result after each insert. • The seminal result on q-hierarchical queries [6] supports both inserts and deletes to the standard database under set semantics, but does not consider the generalization to 𝐾databases. A question is whether such a generalization is immediate. Prior work [16, 24] showed this to be the case for the Z-ring and the covariance ring, but the case of arbitrary rings (semirings with additive inverse) remains open. Acknowledgements This work was partially supported by Swiss NSF 200021-231956. References [1] Mahmoud Abo Khamis, Eden Chmielewski, Andrei Draghici, Ahmet Kara, and Dan Olteanu. 2026. Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations. Proc. ACM Manag. Data 4, 2, Article 109 (2026), 22 pages. doi:10.1145/3801905 [2] Mahmoud Abo Khamis, Ahmet Kara, Dan Olteanu, and Dan Suciu. 2024. Insert-Only versus Insert-Delete in Dynamic Query Evaluation. Proc. ACM Manag. Data 2, 5, Article 219 (Nov. 2024). doi:10.1145/3695837 [3] Omer Abramovich, Daniel Deutch, Nave Frost, Ahmet Kara, and Dan Olteanu. 2024. Banzhaf Values for Facts in Query Answering. Proc. ACM Manag. Data 2, 3 (2024), 123. doi:10.1145/3654926 [4] Omer Abramovich, Daniel Deutch, Nave Frost, Ahmet Kara, and Dan Olteanu. 2025. Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms. Proc. VLDB Endow. 18, 11 (2025), 3996–4008. doi:10.14778/3749646.3749670 [5] Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. 2007. On Acyclic Conjunctive Queries and Constant Delay Enumeration. In CSL. 208–222. doi:10.1007/978-3-540-74915-8_18 [6] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. 2017. Answering Conjunctive Queries Under Updates. In PODS. 303–318. doi:10.1145/3034786.3034789
28
Eden Chmielewski, Andrei Draghici, Dan Olteanu, and Haozhe Zhang
[7] Leopoldo E. Bertossi, Benny Kimelfeld, Ester Livshits, and Mikaël Monet. 2023. The Shapley Value in Database Management. SIGMOD Rec. 52, 2 (2023), 6–17. doi:10.1145/3615952.3615954 [8] Mihai Budiu, Tej Chajed, Frank McSherry, Leonid Ryzhyk, and Val Tannen. 2023. DBSP: Automatic Incremental View Maintenance for Rich Query Languages. Proc. VLDB Endow. 16, 7 (2023), 1601–1614. doi:10.14778/3587136.3587137 [9] Michel Gondran and Michel Minoux. 2008. Graphs, Dioids and Semirings: New Models and Algorithms (Operations Research/Computer Science Interfaces Series) (1 ed.). [10] Todd J. Green. 2009. Containment of conjunctive queries on annotated relations. In ICDT. 296–309. doi:10.1145/ 1514894.1514930 [11] Todd J. Green, Zachary G. Ives, and Val Tannen. 2011. Reconcilable Differences. Theory of Computing Systems (2011), 460–488. doi:10.1007/s00224-011-9323-x [12] Todd J. Green, Grigoris Karvounarakis, and Val Tannen. 2007. Provenance semirings. In PODS. 31–40. doi:10.1145/ 1265530.1265535 [13] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. 2015. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. In STOC. 21–30. doi:10.1145/2746539.2746609 [14] Muhammad Idris, Martín Ugarte, and Stijn Vansummeren. 2017. The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates. In SIGMOD. 1259–1274. doi:10.1145/3035918.3064027 [15] Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2019. Counting Triangles under Updates in Worst-Case Optimal Time. In ICDT. 4:1–4:18. doi:10.4230/LIPICS.ICDT.2019.4 [16] Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2024. F-IVM: Analytics over Relational Databases under Updates. VLDB J. 33, 4 (2024), 903–929. doi:10.1007/S00778-023-00817-W [17] Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2025. Conjunctive Queries with Free Access Patterns under Updates. LMCS Volume 21, Issue 2, Article 23 (2025). doi:10.46298/lmcs-21(2:23)2025 [18] Ahmet Kara, Dan Olteanu, and Dan Suciu. 2024. From Shapley Value to Model Counting and Back. Proc. ACM Manag. Data 2, 2 (2024), 79. doi:10.1145/3651142 [19] Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler, Dan Suciu, and Yisu Remy Wang. 2024. Convergence of datalog over (Pre-) Semirings. J. ACM 71, 2 (2024), 8:1–8:55. doi:10.1145/3643027 [20] Mahmoud Abo Khamis, Hung Q. Ngo, and Atri Rudra. 2016. FAQ: Questions Asked Frequently. In PODS. 13–28. doi:10.1145/2902251.2902280 [21] Christoph Koch, Yanif Ahmad, Oliver Kennedy, Milos Nikolic, Andres Nötzli, Daniel Lupei, and Amir Shaikhha. 2014. DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views. VLDB J. 23, 2 (2014), 253–278. doi:10.14778/2336664.2336670 [22] Egor V. Kostylev and Peter Buneman. 2012. Combining Dependent Annotations for Relational Algebra. In ICDT. 196–207. doi:10.1145/2274576.2274597 [23] Mehryar Mohri. 2002. Semiring Frameworks and Algorithms for Shortest-Distance Problems. J. Autom. Lang. Comb. 7, 3 (2002), 321–350. doi:10.25596/JALC-2002-321 [24] Milos Nikolic and Dan Olteanu. 2018. Incremental View Maintenance with Triple Lock Factorization Benefits. In SIGMOD. 365–380. doi:10.1145/3183713.3183758 [25] Dan Olteanu. 2024. Recent Increments in Incremental View Maintenance. In PODS. 8–17. doi:10.1145/3635138.3654763 [26] Dan Olteanu and Jakub Závodný. 2015. Size Bounds for Factorised Representations of Query Results. ACM Trans. Database Syst. 40, 1 (2015), 2:1–2:44. doi:10.1145/2656335 [27] RelationalAI, Inc 2026. RAIVM Engine. https://www.relational.ai. [28] Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch. 2011. Probabilistic Databases. Morgan & Claypool Publishers. doi:10.2200/S00362ED1V01Y201105DTM016 [29] Qichen Wang. 2026. Towards Parameterized Hardness on Maintaining Conjunctive Queries. CoRR abs/2603.14754 (2026). arXiv:2603.14754 doi:10.48550/ARXIV.2603.14754 [30] Qichen Wang, Xiao Hu, Binyang Dai, and Ke Yi. 2023. Change Propagation without Joins. Proc. VLDB Endow. 16, 5 (2023), 1046–1058. doi:10.14778/3579075.3579080
A
Appendix
Proposition 13[restated] For any p-hierarchical query, its fractional hypertree width equals the fractional hypertree width of its Boolean version. Proof. Let 𝑄 (F) be a p-hierarchical query. Any free-connex TD of 𝑄 if also a free-connex TD of the Boolean version of 𝑄. We argue that any optimal TD of the Boolean version of 𝑄 can be transformed into a free-connex TD of 𝑄 without increasing the fractional edge cover of any bag.
The Role of Semirings in Incremental View Maintenance
29
We start by decomposing 𝑄 into free dominated q-hierarchical queries 𝑄 (F) = 𝑄 1 (F1 ) ·. . .·𝑄𝑘 (F𝑘 ) using Prop. 11. Now, let (𝑇 , 𝜒) be an optimal TD of 𝑄 such that its width is exactly 𝑤 = fhtw(𝑄). Consider the TD (𝑇 ′, 𝜒 ′ ), where𝑇 ′ = 𝑇 and 𝜒 ′ (𝑡) = 𝜒 (𝑡)∩Free(𝑄). It follows that width(𝑇 ′, 𝜒 ′ ) ≤ 𝑤 and (𝑇 ′, 𝜒 ′ ) still respects the connectedness property of TDs, but it might not cover all the atoms of 𝑄. This tree will act as the required connected subtree that contains only free variables. Now, for each subquery 𝑄𝑖 (F𝑖 ), we argue that fhtw(𝑄𝑖 ) ≤ fhtw(𝑄). Let (𝑇𝑖 , 𝜒𝑖 ) be a TD, where 𝑇𝑖 = 𝑇 and 𝜒𝑖 (𝑡) = 𝜒 (𝑡) ∩ vars(𝑄𝑖 ). We show that the fractional edge cover Í of any bag 𝜒𝑖 (𝑡) is at most 𝑤. Let 𝜌 be an optimal edge cover of bag 𝜒 (𝑡), 𝑡 ∈ nodes(𝑇 ) with 𝜌 (𝑒) ≤ 𝑤. We aim to construct an edge cover 𝜌𝑖′ for the bag 𝜒𝑖 (𝑡) that does not use edges 𝑒 ∉ at(𝑄𝑖 ). By the definition of a p-hierarchical decomposition, any external atom 𝑒 ∉ at(𝑄𝑖 ) contains no bound variables of 𝑄𝑖 . Therefore, its contribution to the bag 𝜒𝑖 (𝑡) is restricted entirely to the free variables 𝑒 ∩ vars(𝑄𝑖 ) ⊆ Free(𝑄𝑖 ). Because 𝑄𝑖 is a free-dominated subquery, every atom in 𝑄𝑖 contains all of Free(𝑄𝑖 ). So, we can move that weight to any other edge that contains all the free variables. Pick an arbitrary edge 𝑒 ∗ ∈ at(𝑄𝑖 ) such that 𝑒 ∗ covers F𝑖 . We define 𝜌 ′ exclusively over at(𝑄𝑖 ): ( Í 𝜌 (𝑒) + 𝑒 ′ ∉at(𝑄𝑖 ) 𝜌 (𝑒 ′ ) if 𝑒 = 𝑒 ∗ ′ 𝜌 (𝑒) = 𝜌 (𝑒) otherwise For any bound variable 𝑋 ∈ Bound(𝑄𝑖 ), its coverage is preserved because it was only ever covered by atoms in at(𝑄𝑖 ). For any free variable 𝑌 ∈ Free(𝑄𝑖 ), the exact weight lost by discarding Í external atoms is transferred to 𝑒 ∗ , which contains 𝑌 . Thus, 𝜌 ′ is a valid edge cover for 𝜒𝑖′ (𝑡) with 𝜌𝑖′ (𝑒) ≤ 𝑤, so we conclude that fhtw(𝑄𝑖 ) ≤ fhtw(𝑄). Furthermore, the TD (𝑇𝑖 , 𝜒𝑖 ) must contain a bag with 𝜒𝑖 (𝑡) ⊇ F𝑖 . Using this node, we can attach the subtree 𝑇𝑖 to 𝑇 ′ by adding an edge between this node 𝑡 ∈ nodes(𝑇𝑖 ) to a node 𝑡 ′ ∈ nodes(𝑇 ′ ) with 𝜒 ′ (𝑡 ′ ) ⊇ 𝐹𝑖 while preserving the connectedness property of TDs for the free variables. The connectedness for the bound variables is guaranteed by each individual TD 𝑇𝑖 . We do the same for all TDs to obtain a new TD (𝑇 ∗, 𝜒 ∗ ) for 𝑄. The subtree 𝑇 ′ ensures the free-connex property and since every atom of 𝑄 belongs to some subquery 𝑄𝑖 , it must be covered by some bag in 𝑇𝑖 , so it is also covered by some bag in 𝑇 ∗ . Finally, since every bag in 𝑇 ′ and 𝑇𝑖 has a fractional edge cover of at most 𝑤, the width of (𝑇 ∗, 𝜒 ∗ ) is at most 𝑤. Therefore, (𝑇 ∗, 𝜒 ∗ ) is a free-connex TD for 𝑄 with width(𝑇 ∗, 𝜒 ∗ ) = 𝑤. □