arXiv CSopen access

Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

databases, sql, data management, storage

Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations Mahmoud Abo-Khamis2 , Eden Chmielewski1 , Andrei Draghici1 , Ahmet Kara3 , Dan Olteanu1

arXiv:2605.08397v1 [cs.DB] 8 May 2026

University of Zurich , 2 Relational AI, 3 OTH Regensburg

Abstract We study the classical incremental view maintenance problem: Given a query and a database, maintain the query output under single-tuple updates (inserts or deletes) to the database such that the tuples in the query output can be enumerated with constant delay after any update. We introduce a maintenance approach whose update time matches or improves the best update time reported in prior work. Whereas prior approaches are manually tailored to each of a handful of queries, our approach generalizes to arbitrary join queries. It combines three techniques: delta queries, trees of materialized views, and heavy-light data partitioning. The overall update time incurred by our approach for a given join query is characterized by the maintenance width, a new measure that is parameterized by the heavy-light threshold for data partitioning. We show how to find the threshold that minimizes the maintenance width.

Acknowledgements

This work is partially supported by SNSF 200021-231956.

Introduction

In this paper, we study the classical incremental view maintenance (IVM) problem for join (or full conjunctive) queries: Given a query and a database, we want to maintain the query output under single-tuple updates (inserts or deletes) to the database such that the tuples in the query output can be enumerated with constant delay after each update. This problem is central to databases and received attention from both database systems and theory communities over the past decades. As highlighted in a recent overview [28], there has been renewed interest in charting the complexity of the IVM problem [14, 16] and in developing IVM systems in academia [23, 12, 17, 32] and industry [6, 26, 30]. The classical IVM approach is based on delta queries [7]. More recently, two further techniques made their way into the IVM theory and systems: using a hierarchy, or tree, of materialized views [23, 17], and heavylight data partitioning [14, 16]. View trees (and variants thereof) have been previously used for maintenance by several IVM systems. DBToaster [23] compiles the given query into a set of view trees, one for each updatable relation. Dynamic Yannakakis [12], F-IVM [17, 13], and Crown [32] compile the given query into one view tree, which is then maintained under updates. MVIVM translates the given query into a so-called multivariate extension query, which is maintained using view trees [1]. With the exception of q-hierarchical queries, which can be maintained using (a variant of) view trees with constant update time and constant enumeration delay as shown in a seminal work [5] and readily adopted by all subsequent approaches, the update time achieved by these approaches for arbitrary queries can be suboptimal. Motivated by the suboptimality of the aforementioned IVM approaches, a distinct line of theoretical work [14, 15, 16, 10, 1] proposed adaptive maintenance approaches that partition the data and use different view trees for different data parts. This can lead to asymptotically lower and even optimal update times. These adaptive approaches were employed for a handful of queries, for which a careful crafting of view trees and the accompanying complexity analysis were made on a case-by-case basis, with no general approach in sight. One notable exception is the adaptive maintenance of hierarchical queries with arbitrary free 1

Join Queries

hierarchical

Update Time Upper Bounds

Update Time Lower Bounds

F-IVM [17]

IVMϵ [15, 16]

HHH [10]

MVIVM [1]

This Paper

O(1)

N/A

O(1)

1/2−γ

1/2 ∗

3-path (

)

Ω(N

) [5, 1]

O(N )

O(N

)

O(N

4-path (

)

Ω(N 1/2−γ ) [5, 1]

O(N )

O(N 1/2 )∗

N/A

1/2−γ

1/2

O(N 1/2 )

N/A

O(N 2/3 )∗

O(N )

O(N 2/3 )

N/A

O(N 2/3 )∗

O(N )

O(N 2/3 )

2/3 ∗

O(N

)

O(N

LW-k

Ω(N 1/2−γ ) [5, 1]

O(N )

O(N 1/2 )

4-cycle (□)

Ω(N 2/3−γ ) [1]

O(N )

Ω(N 2/3−γ ) [1]

O(N )

)

big paw ( bow tie (▷◁)

)

O(N

1/2

)

O(N 2/3 )

N/A

O(N 2/3 )

N/A

O(N )

) [1]

O(N )

N/A

O(N

Ω(N 2/3−γ ) [1]

O(N )

N/A

Ω(N 3/4−γ ) [1]

O(N )

N/A

Ω(N

O(N 1/2 )

O(N ) 1/2 ∗

O(N 1/2 )

O(N )

paw (

)

N/A

) [5, 1]

2/3−γ

O(N

O(N 1/2 )

Ω(N

)

1/2

)

triangle (△)

diamond (

1/2 ∗

)

O(N

2/3

Table 1: Comparison between the update times of our maintenance approach versus the best known combinatorial results for different join queries studied in the literature. Update times of all approaches are amortized, except for F-IVM which is worst-case. N is the size of the database at the time of the update. All results assume that after each update, constant delay enumeration of the query output is supported. (∗ ) entries indicate update times shown only for the counting version of the problem; (N/A) entries indicate that Q the approach is not applicable; LW-k is the Loomis-Whitney query on k variables: Q(X1 , . . . , Xk ) = i∈[k] Ri ({X1 , . . . , Xk } − {Xi }). All lower bounds assume the query has no self-joins and they hold for any γ > 0. variables [16]. IVMϵ is the first approach to achieve optimal (amortized) update time O(N 1/2 ) for the triangle count query [14] and for the full triangle query [15], where N is the database size at the time of update. A further optimality result is known for a subclass of hierarchical (but not q-hierarchical) queries [16], where the update time and enumeration delay are O(N 1/2 ). Yet tight bounds on the update time are not known beyond these notable cases. This is primarily due to the scarcity of the available lower bounds, which are conditional on the Online Matrix-Vector-Multiplication (OMv) conjecture [11, 5]1 or on the conjectured optimality of the submodular width for static query evaluation [1].2 Further approaches fall short of achieving the best known update times. For instance, the MVIVM approach [1], which reduces the IVM problem of a query to that of its multivariate extension, was shown to require O(N ) update time for the 4-cycle query [1, Fig. 4], whereas the best known update time is O(N 2/3 ). MVIVM also needs O(N ) update time for the 4-path query, whereas the best update time is O(N 1/2 ). Table 1 overviews the update times (lower and upper bounds) achieved by representative combinatorial3 approaches for queries studied in the literature. In this paper, we put forward an adaptive maintenance approach that works for arbitrary join queries and whose update time matches or improves the best update time reported in prior work. Our approach uses all three aforementioned techniques: delta queries, view trees, and data partitioning. The key challenge addressed by our approach is to algorithmically find the view trees and the heavy-light threshold parameter for data partitioning that minimize the update time for any given join query. This challenge was not addressed in prior works [14, 15, 10, 16], as the choices of view trees and threshold 1 In the OMv problem, we are given an n×n Boolean matrix M and receive n column vectors of size n denoted by v , . . . , v , n 1 one by one; after seeing each vi , we output the product Mvi , before we see the next vector. The OMv conjecture states that 3−γ for any γ > 0, there is no combinatorial algorithm that solves OMv in time O(n ) [11]. Unless the OMv conjecture fails, there is no dynamic algorithm that can enumerate the output of a non-q-hierarchical self-join-free conjunctive query on any database of size N with arbitrary pre-processing time and O(N 1/2−γ ) delay and update time for any γ > 0 [5]. 2 This conjecture states that for every γ > 0 and every (full or Boolean) conjunctive query Q, there does not exist a combinatorial algorithm that for any database of size N can answer Q in time O(N subw(Q)−γ + OUT), where subw(Q) is the submodular width of Q and OUT is the query output size [1]. This conjecture in the static query evaluation setting implies b that there is no fully dynamic algorithm that can maintain Q with amortized update time O(N subw(Q)−1−γ ) and constant b is the multivariate extension of Q [1]. enumeration delay for any γ > 0, where Q 3 Using fast-matrix multiplication, a recently proposed non-combinatorial IVM algorithm [3] can achieve O(N 2/3−γ ) for the 4-cycle query, where γ = 0.009811.

parameter were made manually for each of the considered queries. As shown in Table 1, our approach matches the best known upper bounds on the update time for the queries considered in the literature, while also providing a general approach for arbitrary join queries. It also achieves new non-trivial sub-linear update times for other queries, e.g., the optimal O(N 1/2 ) update time for the 4-path query. This paper is organized as follows. Sec. 2 introduces preliminary notions used throughout the paper. Sec. 3 overviews our approach, exemplifies it on the 4-cycle query, and states our main theorem. Sec. 4 introduces the maintenance width, our new measure for the complexity of the maintenance cost. Sec. 5 compares the maintenance width and our evaluation strategy with width measures and strategies used in prior approaches. Sec. 6 discusses how to amortize the cost of occasional expensive updates over a sequence of updates. Sec. 7 reviews the constant-delay enumeration of tuples from the query output represented by the view trees. Sec. 8 concludes with thoughts on future work. Some proof details are deferred to the appendix. Further details on the amortization and enumeration procedures, as well as the application of our approach to the queries listed in Table 1, are provided in the appendix.

Preliminaries

2.1

Data and Queries

A schema X is a tuple of attributes or variables (X1 , . . . , Xn ), which we also conveniently see as a set to allow set operations on tuples. Each variable Xi draws its values from a set Dom(Xi ). A tuple x of values over the schema X is an element of the set Dom(X) = Dom(X1 ) × . . . × Dom(Xn ). Following prior work on IVM, e.g., [17], a relation R over schema X is a function that maps tuples of values over X to multiplicities, which are integers. When applying set operations to R, we treat it as the set of tuples x with R(x) > 0. For instance, the size of R, denoted by |R|, is the number of tuples x for which R(x) > 0. We specify queries using a syntax similar to that of functional aggregate queries over the (Z, +, ·, 0, 1) ring [21]: X Q(F ) = R1 (X1 ) · . . . · Rk (Xk ), (1) B

where and (·) are the summation and respectively multiplication operation from the ring, R1 , . . . , Rk are relation symbols, each Xi is a schema, and each Ri (Xi ) is an atom of Q. We assume distinct relation symbols in a query. If several relation symbols correspond to the same physical database relation, which happens in case Q 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 copy of the database relation. The set of def S variables of Q is vars(Q) = i∈[k] Xi . The free variables of Q are F ⊆ vars(Q), while B = vars(Q) \ F are the bound variables. If vars(Q) = F , then Q is a full (or join) query. By at(Q) and at(Y ) we denote the set of all atoms of Q and the set of all atoms Ri (Xi ) with Y ∈ Xi , respectively. For compactness, we write a set of variables as the concatenation of their names, e.g., {X, Y, Z} becomes XY Z while {X} becomes X. Each variable A ∈ X i ∩ X j expresses an equi-join between Ri and Rj , for i ̸= j, and is called a join variable. Let JQ be the tuple of all join variables in Q, ordered using a fixed total order on vars(Q). def S For any variable Y ∈ vars(Q), Dom(Y ) is defined as: Dom(Y ) = Ri (X i )∈at(Y ) πY Ri , where π is the standard projection operator in relational algebra. The marginalization of variables Y ⊆ X from a relation P def R P over variables X, denoted by S(Z) = Y R(X) for Z = X \ Y , is defined by: ∀z ∈ Dom(Z) : S(z) = {R(x) | x ∈ Dom(X) ∧ z = x.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 R and S over the same variable set X, denoted by T = R ∪ S, is defined as:P∀x ∈ Dom(X) : T (x) = R(x) + S(x). The query Q in Eq. (1) defines the relation: ∀f ∈ Dom(F ) : Q(f ) = x∈Dom(vars(Q)):f =x.F R1 (x.X 1 ) · . . . · Rk (x.X k ).

2.2

Data Updates

Following prior work [17], we model database updates as a sequence of single-tuple inserts and deletes. The insert (delete) of a tuple x into (from) a relation R is expressed as a delta relation δR that maps x to 1 (and −1, respectively). The updated relation is the union of the old relation and the delta relation: R := R ∪ δR. A delete, whose effect is a tuple with negative multiplicity in the updated relation, is 3

rejected. Updates are defined for joins of relations using the classical delta rule: δ(V1 (Z 1 ) · V2 (Z 2 )) = (δV1 (Z 1 ) · V2 (Z 2 )) ∪ (V1 (Z 1 ) · δV2 (Z 2 )) ∪ (δV1 (Z 1 ) · δV2 (Z 2 )). This generalizes to a join of arbitrary relations by taking V2 to be the join of relations and applying recursively the delta rule to δV2 . If only V1 is changed, then and δ(V1 (Z 1 ) · V2 (Z 2 )) = δV1 (Z 1 ) · V2 (Z 2 ). Updates commute with variable marginalization: P δV2 = ∅P δ( Y V ) = Y δV . If a database relation has several copies due to our assumption on distinct relation symbols, then each of these copies needs to be updated and triggers a delta query.

2.3

Delta View Trees

Our maintenance approach is supported by a tree of materialized views. Definition 1 ((Delta) View Tree). A view tree T for a query Q is a rooted tree with the properties: • There is a one-to-one mapping between the leaves of T and the atoms of Q. • Each inner node is a view over some variables of Q. • If a node V ′ (Y ) has a single childP node V (X), then it is a projection view defined by marginalizing variables of V (X), i.e., V ′ (Y ) = X\Y V (X). Furthermore, every atom of Q with a variable from X \ Y occurs in the subtree rooted at V (X). • If a node V (X) has several children V1 (X1 ), . . . , V1 (Xn ), for n ≥ 2, then it is a join view defined by the natural join of the child views, i.e., V (X) = V1 (X1 ) · . . . · Vk (Xn ). Under an update to a relation R, the view tree T becomes a delta view tree, denoted by δTR , where R is replaced by δR, and each view V along the path from δR to the root view is replaced by δV . For a view tree T , an update to a relation R, and a view V (X) ∈ T , let leaves(δV (X), δTR ) denote the set of all leaves of the subtree of δTR rooted at δV (X). When δTR is clear from context, it is omitted. We use T (Q) to denote the set of all view trees of Q. Fig. 1 depicts view trees for the 4-cycle query. A procedure enumerates the query output with constant delay if the time is constant between: (i) the start of the enumeration process and the output of the first tuple; (ii) outputting any two consecutive tuples; and (iii) outputting the last tuple and the end of the enumeration process [8]. Any view tree for a join query allows for the constant-delay enumeration of the query output [17].

2.4

Heavy-Light Data Partitioning

For a join variable Y , we partition the Y -values in the database in light and heavy according to a threshold parameter ϵ ∈ [0, 1] and database size N : X Light(Y ) := {y ∈ Dom(Y ) | |σY =y Ri | ≤ N ϵ } Heavy(Y ) := Dom(Y ) \ Light(Y ). Ri (Xi )∈at(Y )

That is, a light Y -value y occurs in at most N ϵ tuples across all relations, while there are at most N 1−ϵ heavy Y -values. For an atom R(Y, Z), the relation R is the disjoint union of its fragment where Y is light and its fragment where Y is heavy. Definition 2 (Degree Configuration). Given a query Q with the tuple of join variables (Y1 , . . . , Yn ), a degree configuration is a tuple (d1 , . . . , dn ), where di = L in case Yi is light and di = H in case Yi is heavy (i ∈ [n]). There are 2n degree configurations for a query Q with n join variables. We denote by D(Q) the set of all such degree configurations. Definition 3 (Relation Restriction). Given a query Q with the tuple of join variables (Y1 , . . . , Yn ), degree configuration d = (d1 , ..., dn ), and atom R(X) in Q, the d-restriction of relation R is: {r | r ∈ R ∧ ∀i ∈ [n] : Yi ∈ X → (di = L ∧ r.Yi ∈ Light(Yi ) ∨ di = H ∧ r.Yi ∈ Heavy(Yi ))}.

2.5

Degree Constraints

Using the degree configurations and the updates, we derive constraints on the degrees for the database values. Definition 4 (Degree Constraint). [27, Def. 1] A degree constraint on a database of size N is a tuple (Z|Y , N pZ|Y ), where Y ⊊ Z and pZ|Y ∈ Q≥0 . Let Q be a query and Ri (X i ) an atom of Q. Then Ri (X i ) guards the degree constraint (Z|Y , N pZ|Y ) if Z ⊆ X i and maxt |πZ (σY =t.Y Ri )| ≤ N pZ|Y . def

S For a set of degree constraints C, we denote the set of all variables appearing in C by vars(C) = p (Z|Y ,N Z|Y )∈C Z. A projection of a set C of degree constraints onto a set V of variables, denoted by C[V ], is defined as the set {(Z ∩ V |Y , N pZ|Y ) | (Z|Y , N pZ|Y ) ∈ C ∧ Y ⊊ Z ∩ V }. Projections may not only shrink the set of variables covered by a degree constraint (Z ∩ V ), but also remove a constraint from C altogether. This happens when Y ⊊ Z ∩ V is violated. For instance, the projection (Y |Y , N pZ|Y ) of the constraint (Z|Y , N pZ|Y ) onto Y is uninformative and therefore discarded. For a database of size N , delta view δV (X) in a delta view tree TRj for an update δRj , and degree configuration d, we define the set of degree constraints that are guarded by the database relations at the leaves L = leaves(δV (X)) of δV (X) in TRj as: def

DC(L, d) = {(X i |∅, N ) | Ri (X i ) ∈ L ∧ i ̸= j}∪

(size constr.)

(light constr.)

{(X i |Y, N ) | Ri (X i ) ∈ L ∧ Y ∈ X i ∧ Y is light in d ∧ i ̸= j}∪ {(Y |∅, N

1−ϵ

) | Ri (X i ) ∈ L ∧ Y ∈ X i ∧ Y is heavy in d ∧ i ̸= j}∪

{(A|∅, 1) | A ∈ X j }

(heavy constr.) (update constr.)

Note that this set does not contain constraints that are guarded by the relation Rj itself, since this relation is not in δTRj . If a set C of degree constraints is guarded by a relation, then this also holds for its projection C[X] onto any set of variables X ⊆ vars(C). Definition 5 (Acyclic Sets of Degree Constraints). For any set C of degree constraints, associate a directed graph GC with a node for every variable in vars(C) and with a directed edge (y, z) ∈ Y × (Z − Y ) for every degree constraint (Z | Y , N pZ|Y ) ∈ C. If GC is acyclic, then C is called acyclic. We denote by A(C) the set of all maximal acyclic subsets of C. All maximal acyclic subsets of a set C of degree constraints contain all size, heavy, and update constraints from C, as these constraints have the form (Z|∅, N pZ|∅ ) and do not create edges in the constraint graph. It is only the light constraints that create edges and therefore cycles in this graph.

2.6

RAM Model of Computation

We assume that each relation Ri is implemented by a data structure of size O(|Ri |) that can: (i) look up, insert, and delete tuples in Ri in amortized constant time, and (ii) enumerate all tuples in Ri with constant delay. For a set S ⊊ Xi , we use an index data structure that, for any tuple xS over the variables in S, (iii) can enumerate all tuples in σS=xS Ri with constant delay, and (iv) insert and delete index entries in amortized constant time. We also need indices to (v) enumerate with constant delay the distinct tuples in each relation constructed by marginalizing any subset of variables of Ri . We report the time complexity as a function of the database size N only, where the query is considered fixed and of constant size (data complexity). Therefore, the enumeration delay is constant when it does not depend on the database size.

Overview of Our Adaptive IVM approach

In this section, we overview our maintenance approach. Given a join query Q, a database of size N , and a single-tuple update (tuple insert or delete), our approach updates the query output and allows for constantdelay enumeration of the tuples in the query output. Our approach is adaptive: For different heavy-light partitioning of the database on the columns corresponding to the join variables in Q (as described in Sec. 2), it may use a different maintenance strategy.

V5 (A, C)

V5 (B, D)

V3 (A, C)

V4 (C, A)

V3 (B, D)

V4 (B, D)

V1 (A, B, C)

V2 (C, D, A)

V1 (A, B, D)

V2 (B, C, D)

R(A, B) S(B, C) T (C, D) U (D, A)

R(A, B) U (D, A) S(B, C) T (C, D)

View Tree 1

View Tree 2

V5 (A, D)

V5 (C, D)

V5 (B, C)

V5 (A, B)

V4 (A, D) U (D, A)

V4 (C, D) T (C, D)

V4 (B, C) S(B, C)

V4 (A, B) R(A, B)

V3 (A, C, D)

V2 (A, C) T (C, D)

V2 (A, C) U (D, A)

V3 (B, C, D)

V3 (A, B, D)

V2 (B, D) T (C, D)

V2 (B, D) U (D, A)

V1 (A, B, C)

V1 (A, B, D)

V1 (B, C, D)

R(A, B) S(B, C)

R(A, B) U (D, A)

S(B, C) T (C, D)

View Tree 3

View Tree 4

View Tree 5

View Tree 6

Figure 1: The six view trees used to maintain the 4-cycle query. Example 6. We use as running example throughout this section the 4-cycle query: Q(A, B, C, D) = R(A, B) · S(B, C) · T (C, D) · U (D, A). The query has 4 join variables, 24 = 16 degree configurations. For instance, the degree configuration d = (L, L, H, H) for the tuple of join variables (A, B, C, D) corresponds to the relation restrictions where A and B are light while C and D are heavy. Under an update δR, the delta query is: δQ(A, B, C, D) = δR(A, B) · S(B, C) · T (C, D) · U (D, A). For the degree configuration d, threshold parameter ϵ, and database size N , we have the following degree constraints: DC(at(δQ), d) = {(BC|∅, N ), (CD|∅, N ), (AD|∅, N ), (AD|A, N ϵ ), (BC|B, N ϵ ), (C|∅, N 1−ϵ ), (D|∅, N 1−ϵ ), (A|∅, 1), (B|∅, 1)}. The first three constraints are size constraints (relations S, T , and U have sizes at most N ). The next two constraints are light constraints, e.g., there are at most N ϵ D-values for a given A-value. The first two constraints in the second line are heavy constraints, e.g., there are at most N 1−ϵ C-values, while the last two constraints express that each of A and B is set to one value (due to the update δR). We maintain the output of a join query using trees of materialized views (Def. 1). Example 7. Fig. 1 depicts six possible view trees for the 4-cycle query. The leaves are atoms that correspond to the four relations, while the intermediate nodes are join or projection views. Each view tree admits a simple maintenance mechanism [17, 13]. Given an update to a relation, all views along the path from the leaf corresponding to the updated relation to the root may be affected by the update and we compute deltas for them. We refer to the modified tree, where the updated relation and the views along the path to the root are replaced by their deltas, as the delta view tree. The enumeration of the tuples in the query output proceeds top-down in the view tree and needs constant delay per tuple. Example 8. An update δR : {(a, b) 7→ m} to relation R, where m = +1 for an insert and m = −1 for a delete, in the first view tree in Fig. 1 triggers the computation of updates for the views along the path from 6

the leaf R to the root of the view tree: δV1 (A, B, C) = δR(A, B) · S(B, C) X δV3 (A, C) = δV1 (A, B, C)

V1 := V1 ∪ δV1 V3 := V3 ∪ δV3

δV5 (A, C) = δV3 (A, C) · V4 (C, A)

V5 := V5 ∪ δV5

This bottom-up propagation of the updates ensures that the views are calibrated top-down. For instance, all pairs (a, c) in V5 are also in all views and relations below V5 ; furthermore, the B-values (D-values) paired with (a, c) in V1 (V2 ) are also in R and S (respectively T and U ). Consequently, the tuples in the query output can be enumerated with constant delay. We enumerate with constant delay: the pairs (a, c) in V5 , the B-values paired with (a, c) in V1 and the D-values paired with (a, c) in V2 . View trees (and variants thereof) have been previously used by several IVM systems [5, 23, 12, 17, 13, 32]. For instance, F-IVM [17] compiles a given query into one view tree, which is then maintained under updates as shown in Ex. 8. As discussed in the introduction, the update time achieved by these approaches for arbitrary queries can be suboptimal. Our approach can use several view trees. It considers a heavy-light partitioning of the data and can use different view trees for different degree configurations. This adaptivity can lead to lower update times than when using a single view tree. The challenge brought by adaptivity is to algorithmically find (1) an asymptotically best view tree for each degree configuration and (2) the heavy-light threshold parameter ϵ that minimizes the update time for any given query. We address this challenge as follows. In our approach, the update time is a function of the threshold parameter ϵ. In particular, given a delta view tree and a degree configuration, each delta view is computed under the degree constraints parameterized by ϵ. By parameterization, we mean that for a degree constraint (Z|Y , N pZ|Y ), the exponent pZ|Y is a linear function of ϵ, which evaluates to a positive rational number for a given value for ϵ. The compute time for a delta view is given by O(N s ), where N is the database size and s is the optimal solution of a linear program that computes the polymatroid bound under degree constraints [22, 27]. This polymatroid bound is a generalization of the well-known AGM bound [4] from size constraints to more general degree constraints that also include the light constraints. The linear program of such bounds assigns a positive weight to each constraint such that for each query variable, the sum of the weights of the constraints that cover the variable is at least one. The objective is to minimize the sum of all weights, where each weight is multiplied by the exponent pZ|Y in the corresponding constraint. A key observation is that the inequalities of the linear program do not depend on ϵ. Therefore, the vertices of the polyhedron given by the feasible region of the linear program are independent of ϵ. This also means that the optimal solution, which is given by one of these vertices, can be expressed as the minimum over all vertices of the objective instantiated for each vertex. Example 9. Let us consider View Tree 4 (Fig. 1), the degree configuration d = (L, L, H, H) for join variables (A, B, C, D), and an update δR. This update triggers updates to the views along the path from R to the root of the view tree. We first consider δV1 (A, B, C) = δR(A, B) · S(B, C). The degree constraints that hold at the leaves of δV1 (A, B, C) in the delta view tree are: C1 = DC(leaves(δV1 (A, B, C)), d) = {(BC|∅, N ), (BC|B, N ϵ ), (C|∅, N 1−ϵ ), (A|∅, 1), (B|∅, 1)}. We obtain the exponent s of an upper bound O(N s ) on the time to compute δV1 (A, B, C) using the following linear program that assigns a weight (positive number) to each constraint. We have the following vector of weights: w = w1 , w2 , w3 , w4 , w5 . We assume that the order of the weights follows the order of the above constraints. The linear program is as follows: minimize

w1 · 1 + w2 · ϵ + w3 · (1 − ϵ) + w4 · 0 + w5 · 0

subject to

w4 ≥ 1

// covers A

w1 + w5 ≥ 1

// covers B

w1 + w2 + w3 ≥ 1

// covers C

w1 , . . . , w5 ≥ 0 7

The objective is the sum of all weights, each multiplied by the base-N logarithm of the bound in the corresponding constraint; note the coefficient of w4 and w5 is logN 1 = 0, so these weights do not contribute to the objective. The program has one inequality per variable: the sum of the weights of those constraints that cover the variable must be at least 1. For the optimal solution, it is enough to consider the weight vectors that are the vertices of the convex polyhedron given by the feasible region of the above linear program: (1, 0, 0, 1, 0), (0, 1, 0, 1, 1), (0, 0, 1, 1, 1). None of these vertices depend on ϵ, yet the program solutions may be parameterized by ϵ. For instance, the solution given by the 3rd vertex, which sets w3 = w4 = w5 = 1 and all other weights to 0, is 1 − ϵ, whereas the solution given by the 2nd vertex, which sets w2 = w4 = w5 = 1 and all other weights to 0, is ϵ. The minimal solution is therefore at most min(ϵ, 1 − ϵ). The delta view δV1 is a join query that can be computed using an adaptation of aP worst-case optimal join algorithm [27] in time O(N min(ϵ,1−ϵ) ). We next consider δV2 (A, C) = B δV1 (A, B, C). The time to compute δV2 is asymptotically the same as for δV1 , since the former can be computed in one pass over the latter. In the paper, we introduce a systematic approach to upper bound the time to compute conjunctive queries with bound variables, such as δV2 . For this, we consider the set of constraints that hold at the leaves of δV2 , which is C1 , projected onto different supersets of the set of its free variables {A, C}, i.e., C2 = C1 [AC] = {(C|∅, N ), (C|∅, N 1−ϵ ), (A|∅, 1)} and C1 = C1 [ABC]. We next discuss each of these two cases. Using C2 , we can define the join query QC2 that over-approximates δV2 in the sense that all tuples in δV2 are also in QC2 (multiplicities are ignored): QC2 (A, C) = δR′ (A) · S ′ (C), where δR′ is the projection of δR onto A and S ′ is the projection of S onto C (Def. 13). The query QC2 can be computed in time O(N 1−ϵ ): C2 states that we have one A-value and at most N 1−ϵ C-values. The output of δV2 can be recovered by semi-join reducing QC2 with δV1 . The time to compute δV2 is therefore asymptotically the same as for QC2 . In case we use C1 , we retain B and with it the light constraint and the update constraint on B. The join query defined by C1 is precisely δV1 , which is an over-approximation of δV2 in the sense that we can recover the tuples of δV2 from δV1 in the same O(N min(ϵ,1−ϵ) ) time as for computing δV1 . We next consider δV3 (A, C, D) = δV2 (A, C) · U (D, A). We take the set C3 = DC(leaves(δV3 ), d) of constraints that hold at the leaves of δV3 and project it onto the two possible supersets of the set of its free variables: C3′ = C3 [ACD] = {(C|∅, N ), (C|∅, N 1−ϵ ), (A|∅, 1), (D|∅, N 1−ϵ ), (AD|∅, N ), (AD|A, N ϵ )} and C3′′ = C3 [ABCD] = C1 ∪ {(D|∅, N 1−ϵ ), (AD|∅, N ), (AD|A, N ϵ )}. In case of C3′ , we use the join query QC3′ that over-approximates δV3 : QC3′ (A, C, D) = δR′ (A) · S ′ (C) · U (D, A). We use that: There is one A-value that is also light, D is heavy, and C is heavy. This yields a N min(ϵ,1−ϵ) bound on the number of D-values. The time is then O(N min(ϵ,1−ϵ)+1−ϵ ) = O(N min(1,2−2ϵ) ). In case of C3′′ , we use the join query QC3′′ (A, B, C, D) = δR(A, B) · S(B, C) · U (D, A). This query overapproximates δV3 in the sense that for every tuple t in δV3 there is a tuple t′ in QC3′ such that t′ .(ACD) = t. To compute this query, we observe that the number of C-values or of D-values is upper bounded by N min(ϵ,1−ϵ) , since both C and D are heavy and there is one A-value and one B-value and both values 2 min(ϵ,1−ϵ) are ). The analysis follows similarly for δV4 (C, D) = P light. This yields the compute time O(N A δV3 (A, C, D) and δV5 (C, D) = δV4 (C, D) · T (C, D). Our approach needs to account for all such evaluation strategies for each delta view, as their time may depend on ϵ and it is only clear which ones support the lowest overall update time once we find the value of ϵ that minimizes the update time across all degree configurations and relation updates. The update time for a view tree and degree configuration is given by the maximum time to compute any delta view in the view tree. For a degree configuration, the update time is the minimum update time over all possible view trees. The overall update time is the maximum update time over all degree configurations. We call the base-N logarithm of the overall update time for a query Q the maintenance width of Q and denote it by mw(Q) (Def. 20). This width is given by a nesting of minimizations and maximizations of linear functions in the threshold parameter ϵ. Its minimal value, and ϵ that gives its minimal value, can be computed using a set of linear programs (Sec. 4.4). Example 10. Table 2 gives the base-N logarithm of the update time for each degree configuration, when using the best view tree for that configuration. Each of the six view trees from Fig. 1 is used by at least one configuration. No further view trees are needed to achieve the overall lowest update time. The maintenance width mw(Q) of the 4-cycle query Q is then the minimum over all expressions in the table column for the base-N logarithm of the update time (we ignore wlog the expressions for all remaining view trees as they 8

Configuration (A, B, C, D) ∗, L, ∗, L L, L, L, H L, L, H, H L, H, L, ∗ L, H, H, L L, H, H, H

View Tree 1 2 4 2 5 2

Configuration (A, B, C, D) H, L, L, H H, L, H, H H, H, L, L H, H, L, H H, H, H, ∗

logN UpdateTime ϵ ϵ f (ϵ) f (ϵ) f (ϵ) 1−ϵ

View Tree 3 1 6 2 1

logN UpdateTime f (ϵ) 1−ϵ f (ϵ) 1−ϵ 1−ϵ

Table 2: The base-N logarithm of the update time for each degree configuration and a specific view tree def from Fig. 1. Here, f (ϵ) = max(min(2ϵ, 2 − 2ϵ)), min(2ϵ, 1)); (∗) in the degree configuration indicates that the join variable can be either heavy or light. do not yield a smaller maintenance width). This width can be computed as the minimization of optimal solutions of linear programs: mw(Q) = min max(ϵ, 1 − ϵ, max(min(2ϵ, 2 − 2ϵ), min(2ϵ, 1))) ϵ

= min max(ϵ, 1 − ϵ, min(2ϵ, 2 − 2ϵ), min(2ϵ, 1)) ϵ

∗

= min min(max(ϵ, 1 − ϵ, 2ϵ, 2ϵ), max(ϵ, 1 − ϵ, 2ϵ, 1), ϵ

max(ϵ, 1 − ϵ, 2 − 2ϵ, 2ϵ), max(ϵ, 1 − ϵ, 2 − 2ϵ, 1)) +

= min(min max(ϵ, 1 − ϵ, 2ϵ, 2ϵ) s.t. 0 ≤ ϵ ≤ 1 ϵ

min max(ϵ, 1 − ϵ, 2 − 2ϵ, 1) s.t. 0 ≤ ϵ ≤ 1 ϵ

min max(ϵ, 1 − ϵ, 2 − 2ϵ, 2ϵ) s.t. 0 ≤ ϵ ≤ 1 ϵ

min max(ϵ, 1 − ϵ, 2 − 2ϵ, 1) s.t. 0 ≤ ϵ ≤ 1) ϵ

s.t.

q≥ϵ

q ≥1−ϵ

q ≥ 2ϵ

0 ≤ ϵ ≤ 1.

The optimal solution is 2/3 and obtained for ϵ = 1/3. Once we know the value of ϵ, we can decide which evaluation strategy is best for each delta view in each view tree and for each degree configuration. We are now ready to state the main technical result of this paper. Our incremental view maintenance approach follows the setting of prior work [14, 15, 16]. It has a preprocessing phase, in which the heavy-light partitioning happens and the views of the used view trees are materialized. Then, it receives a sequence of single-tuple updates (inserts and deletes) and processes one update at a time. After each update, it can resolve requests to enumerate the tuples in the query output with constant delay. After some updates, the heavy/light degree assignment of some values may become invalid as: (1) light (heavy) values become heavy (light) according to the current threshold N ϵ ; or (2) the threshold itself changes significantly as N changes [14]. In the first case, we need to move values between the light and heavy parts of relations; this is called minor rebalancing. In the second case, we need to recompute the partitioning and then the views from scratch; this is called major rebalancing. Major and minor rebalancing only need to be performed after a sufficiently large number of updates so that the partitioning still guarantees the desired asymptotic complexity for the update time. By amortizing the cost of rebalancing over many updates, the update time remains the same, albeit amortized. 9

Theorem 11. Any join query Q can be maintained with O(N 1+mw(Q) ) preprocessing time, amortized O(N mw(Q) ) single-tuple update time, and O(1) enumeration delay, where N is the size of the database at the time of update and mw(Q) is the maintenance width of Q.

The Maintenance Width

In this section, we introduce the maintenance width and show how to compute it. This measure is central to our approach as it is the exponent of the update time incurred by our approach for maintaining the query output under database updates. Consider a view V (X) defined over a database that satisfies a set of degree constraints. Given an update δRi , we bound the time needed to compute the delta view δV using a formulation [22, 27] as a linear optimization problem that generalizes the well-known AGM bound [4] to incorporate the degree constraints. Adapting this framework to our setting presents two challenges. First, the original algorithm [22, 27] is designed for join queries (all variables are free); we must extend it to support views, where some variables are marginalized out. Second, our degree constraints depend on the threshold parameter ϵ, which is not fixed in advance. Consequently, we cannot solve the bounding linear program numerically. Instead, we solve it symbolically to obtain an objective value expressed as an explicit function of ϵ. We then select the optimal ϵ that minimizes the worst-case maintenance cost across all degree configurations.

4.1

The Polymatroid Bound under Degree Constraints

In this section, we first revisit prior work on the polymatroid bound [27]. This bound is essential to our analysis of the maintenance time under different degree configurations and updates. Definition 12 (Polymatroid Bound under Degree Constraints). [27, Eq. 48] Given a set C = {c1 , . . . , cm } of degree constraints, we define the Polymatroid Bound under Degree Constraints, denoted by PBD(C), as the optimal value of the following linear program: minimize

wi · p i

(2)

ci =(Z|Y ,N pi )∈C

subject to

wi ≥ 1

∀A ∈ vars(C)

(3)

∀ci = (Z|Y , N pi ) ∈ C

(4)

ci =(Z|Y ,N pi )∈C A∈Z\Y

wi ≥ 0

Prior work [27] showed that join queries can be computed worst-case optimally in the presence of acyclic degree constraints. In particular, given a join query Q and an acyclic set C of constraints, where each constraint is guarded by database relations used in Q, then Q can be evaluated in time O |vars(Q)| · |C| · [N + N PBD(C) ] · log N [27]. The log N factor in the runtime is due to the use of B-tree indices and can be dropped by using hash maps to represent the relations. The additive N log N factor is due to pre-computation. Notice that Inequalities 3, 4 are trivially satisfied by setting all variables wi to 1, so PBD(C) is always defined.

4.2

Upper Bounding the Time to Compute a Delta View

In our work we need to compute delta views that are not necessarily join queries. For this, we extend the prior work [27] to compute queries with arbitrary bound variables under degree constraints. We do this in several steps. First, we show how to derive possible join queries that over-approximate a given delta view. We tailor the set of constraints that are satisfied by the database to those relations and variables that are relevant to the over-approximation join queries. We then use the algorithm from prior work [27] to compute the over-approximation join queries under specific constraints and take the over-approximation with the lowest time complexity. Below, we make this plan concrete. 10

Definition 13 (Guarding Query). Let d be a degree configuration, δTR be a delta view tree for an update δRj , δV (X) be a delta view in δTRj , and C = DC(leaves(δV (X)), d). For any set Y of variables such that X ⊆ Y ⊆ vars(C) and any acyclic set C ′ ∈ A(C[Y ]) of degree constraints, we define the C ′ -guarding query of δV as the join query: QC ′ (Y ) = R1′ (X ′1 ) · . . . · Rk′ (X ′k ) where {R1 (X 1 ), . . . , Rk (X k )} is the set of atoms P at the leaves of δV (X) in δTRj that guard the constraints in C ′ and includes δRj (X j ), and Ri′ (X ′i ) = X i \Y Ri (X i ) and X ′i = X i ∩ Y for i ∈ [k]. Ex. 9 gives guarding queries for several delta views. Remark 14. In Def. 13, C ′ is a maximal acyclic subset of C[Y ]. It contains all size, heavy, and update constraints from C[Y ], since these constraints are of the form (Z|∅, N pZ|∅ ) and cannot be part of a cycle in the constraint graph. Therefore, C ′ may only miss some of the light constraints from C[Y ]. Yet the variables in these light constraints are also covered by a size constraint. The implication is twofold. First, the atoms that guard the constraints in C ′ are also those that guard the constraints in C[Y ]. Second, vars(C ′ ) = vars(C[Y ]). Example 15. We discuss the computation of the delta view δV5 (A, C) in the delta view tree based on View Tree 1 (Fig. 1) under the update δR and the degree configuration d = (L, L, ·, ·), so where the join variables A and B are light and where – for simplicity here – we do not partition on the remaining join variables C and D. The following degree constraints are guarded by the leaves of δV5 (A, C): C = DC(leaves(δV5 ), d) = {(A|∅, 1), (B|∅, 1), (BC|B, N ϵ ), (BC|∅, N ), (CD|∅, N ), (AD|A, N ϵ ), (AD|∅, N )}. The C-guarding query is QC (A, B, C, D) = δR(A, B) · S(B, C) · T (C, D) · U (A, D) and its output can be computed in worst-case optimal time O(N PBD(C) ) [27]. Since the two queries QC and δV5 have the same body, it follows that if we project the output of QC (A, B, C, D) onto the variables {A, C} we obtain the output of δV5 . However, PBD(C) evaluates to 1 or 2ϵ (by using the first, second, and fifth constraints or by using the first, second, third, and sixth constraints to cover all variables) which gives the upper bounds O(N ) and O(N 2ϵ ). Depending on the value of ϵ, both of these bounds can be tight upper bounds on the time needed to compute the output of QC , but they are loose on the time needed to compute the output of δV5 . As we show in later examples in this section, the output of δV5 can be computed in time O(N ϵ ). The reason is that the linear program for PBD(C) needs to cover all variables, including the bound variables B and D, and this increases the cost of its optimal solution. Any guarding query of a delta view over-approximates the delta view in the sense that we can recover the output of a delta view from the output of any of its guarding queries. Lemma 16. For any delta view δV (X) and any of its C[Y ]-guarding queries QC[Y ] (Y ), where C is the set of constraints that are guarded by the leaves of δV (X) and X ⊆ Y , it holds: For any tuple x in the output of δV over any database, there is a tuple y in the output of QC[Y ] over the same database such that x = y.X. Proof. Let {R1 (X 1 ), . . . , Rk (X k )} = leaves(δV (X)). The delta view is thus defined by X δV (X) = R1 (X 1 ) · . . . · Rk (X k ). (

i∈[k] X i )\X

Let C be the set of constraints that are guarded by the databaseSrelations R1 , . . . , Rk . Since C always contains the size constraints of these relations, it holds that vars(C) = i∈[k] X i . By definition of the C[Y ]-guarding query QC[Y ] (Y ) (Def. 13), we have that X ⊆ Y ⊆ vars(C) and: X QC[Y ] (Y ) = R1′ (X ′1 ) · . . . · Rk′ (X ′k ), where Ri′ (X ′i ) = Ri (X i ) and X ′i = X i ∩ Y for i ∈ [k]. X i \Y

The set of tuples in the output of δV is:   X t.X | 

R1 (t.X 1 ) · . . . · Rk (t.X k ) > 0

  

t∈Dom(vars(C))

(5)

whereas the set of tuples in the output of QC[Y ] is: y ∈ Dom(Y ) | R1′ (y.X ′1 ) · . . . · Rk′ (y.X ′k ) > 0 .

(6)

If the output of δV is empty, then the statement of the lemma follows trivially. Otherwise, consider a tuple x in the output of δV given in Eq. (5). Since the sum in Eq. (5) is positive, it must contain at least one positive term. Thus, there exists a tuple t ∈ Dom(vars(C)) with t.X = x such that R1 (t.X 1 ), . . . , Rk (t.X k ) are all positive. It then also follows that R1′ (t.X ′1 ) · . . . · Rk′ (t.X ′k ) > 0, since X ′i ⊆ X i and Ri′ is defined by marginalizing X i \ Y from Ri , for i ∈ [k]. We conclude that for any tuple x such that δV (x) > 0 there exists at least one tuple y ∈ Dom(Y ) with y.X = x such that QC[Y ] (y) > 0. Guarding queries for a delta view are join queries, so we can compute them efficiently under an acyclic set of degree constraints [27]. Furthermore, we can compute the delta view in time proportional to the time need to compute any of its guarding queries. Lemma 17. Given a database of size N , a delta view tree δTR , a delta view δV (X) in δTR , and any of the C-guarding queries of δV (X), where C is an acyclic set of constraints, then δV can be computed in time O(N PBD(C) ) given that the child views of δV (X) in δTR are already computed. Proof. We compute δV in two steps. In the first step, we compute the join query QC in time O(N PBD(C) ) using the algorithm from prior work [27]. Its output is, however, an over-approximation of the output of δV as stated in Lemma 16. In the second step, we first create a relation V ′ that is the projection of QC ’s output onto the set of variables of the child views of δV in T . We next semi-join reduce V ′ with each of the child views of δV . The multiplicity of each tuple t in V ′ becomes the product of the multiplicities of the tuples in the child views whose join make t in V ′ . By performing the computation of the delta views bottom-up in the delta view tree, we ensure that the correct multiplicities of the child views are computed before those of the parent views. Finally, we marginalize out all variables of V ′ except X to obtain the output of δV . The second step also takes time proportional to the size of QC ’s output, so in O(N PBD(C) ) time. There are two immediate implications of Lemma 17. First, it gives a maintenance strategy for a delta view tree and an update δRj : We proceed bottom-up from δRj , first compute its parent delta view, then the parent of the parent, and so on until the delta view at the root. Second, it gives an upper bound on the update time for a delta view: This is the minimum of the computation time over all its guarding queries. A question remains: Why should we consider all guarding queries of a delta view in order to upper bound the compute time for the delta view? Recall there is a guarding query for each set of variables that is a superset of the set of free variables of the delta view and a subset of the set of variables at the leaves of the delta view in the delta view tree. The key observation is that a guarding query with more variables does not necessarily have a higher computation time than another guarding query with less variables. P Example 18. Returning to Ex. 15, let us consider an over-approximation of δV5 (A, C) = B,D δR(A, B) · S(B, C) · T (C, D) · U (D, A). Projecting the set C of degree constraints onto {A, C} gives C[AC] = {(A|∅, 1), (C|∅, N ), (A|∅, N )} with the C[AC]-guarding query QC[AC] (A, C) = δR′ (A) · S ′ (C) · T ′ (C) · U ′ (A). By Lemma 16, we know that this join query is an over-approximation of the conjunctive query δV5 (A, C). We can bound the time needed to compute QC[AC] (A, C) by O(N PBD(C[AC]) ) using Lemma 17. This bound is O(N ) and obtained by covering the variable A with the first constraint and the variable C with the second constraint. While correct, this bound is loose since it does not exploit the lightness information on B. The previous example highlights a trade-off: projecting the set C of constraints onto a subset of its variables guarantees the correctness of the bound, but it may discard useful constraints (like those conditioned on B). Although this requires covering more variables in the linear program, it allows us to retain more constraints in the projection. Thus, we need to look at all the subsets X ′ with X ⊆ X ′ ⊆ vars(C).

Example 19. We continue Ex. 18 and now consider an over-approximation of δV5 (A, C) by projecting the set C of degree constraints onto the superset {A, B, C}. This new projection preserves a light constraint conditioned on B and gives C[ABC] = {(A|∅, 1), (B|∅, 1), (BC|∅, N ), (C|∅, N ), (A|∅, N ), (BC|B, N ϵ )} By Lemma 16, we conclude that QC[ABC] = δR(A, B) · S(B, C) · T ′ (C) · U ′ (A) is an over-approximation of δV5 (A, C). The time needed to compute QC[ABC] is bounded by O(N PBD(C[ABC]) ), which is O(N ϵ ) (by covering A, B, C using the first two and the last constraints). This is tighter than O(N ) for all ϵ < 1. Yet, if we would project C onto the full set {A, B, C, D} of variables, then we would regain the constraints on D at the price of having to cover D in the linear program. As shown in Ex. 15, this gives the upper bound of O(N min(1,2ϵ) ), which is also worse than O(N ϵ ) for all ϵ ∈ (0, 1).

4.3

Symbolic Optimization

As illustrated in Ex. 18, the degree constraints can depend on ϵ (e.g., N ϵ ), while the value of ϵ is not fixed in advance. Consequently, in the linear program of Def. 12, we treat the coefficients pi as functions of ϵ in order to obtain an explicit closed form expression for the optimal value as a function of ϵ. All the degree constraints obtained by the function DC(·, ·) have the form ci = (Z | Y , N pi = N fi (ϵ) ), where fi is either affine in ϵ (it is ϵ or 1 − ϵ) or constant (it is 0 or 1). For each constraint ci , we view the coefficient pi as the function fi (ϵ). Crucially, while the objective function in Eq. (2) varies with ϵ, the feasible region P(C) defined by Eq. (3) and (4) depends only on the sets C and X, and is independent of ϵ. It is a standard result in linear programming that, if an optimum exists, then it is attained at a vertex of the feasible polyhedron P(C) [29]. Since P(C) is defined by a fixed set of constraints, it has a finite set of vertices (and independent on the database size), which we denote by SC . The vertices w = (wi )ci ∈C ∈ SC are constant vectors independent of ϵ. We can compute these weight vectors w once and reuse them to evaluate the cost for any ϵ. For a specific vertex w ∈ SC and parameter ϵ, the symbolic cost is given by: X def obj(w, C)(ϵ) = wi · fi (ϵ). ci ∈C

We are now ready to introduce the notion of maintenance width, which captures the maintenance cost for a given query. In order to find the lowest maintenance cost for a query, we look at the degree configuration that induces the most expensive set of degree constraints, for which we pick the cheapest view tree. For this view tree, we pick the most expensive view to maintain under the most expensive update.4 Definition 20 (Maintenance Width). For a join query Q, the maintenance width of Q is def

mw(Q) = min

max

min

ϵ∈[0,1] d∈D(Q) T ∈T (Q)

max

min

V (X)∈T R(Y )∈leaves(V (X),T )

C⊆DC(leaves(δV (X),δTR ),d) X⊆X ′ ⊆vars(C) C ′ ∈A(C[X ′ ]) w∈SC′

obj(w, C ′ )(ϵ).

(7)

Remark 21. Def. 20 states that for every degree configuration d and view tree T , we take the maximum compute time over all views V of all its delta views δV subject to updates at each of its leaves δR. This computes the maximum update time per view over updates at any of its leaves in δTR and then takes the maximum over all views in the view tree. In contrast, our maintenance approach propagates each update δR from a leaf along the path to the root of the delta view tree δTR for δR and takes the maximum time to compute the delta views that are the ancestors of δR in δTR . Yet both ways to account for the maintenance time for a given view tree yield the same maximum time to update all the views of T under all updates at the leaves. This justifies the equivalent formulation in the definition. 4 Alternatively, the maintenance width can be seen as the outcome of a game where we choose ϵ and the view tree T to minimize cost, while an adversary chooses the data statistics d, the update δRi , and the specific view in T to maximize cost.

We explain how Lemma 17 implies that any join query Q can be maintained with update time O(N mw(Q) ) as stated in Theorem 11. Fix an ϵ ∈ [0, 1]. Given a degree configuration d and a view tree T for Q, let PBD∗ (d, T )(ϵ) =

max

V (X)∈T R(Y )∈leaves(V (X),T )

PBD∗ (d, δV (X), δTR )(ϵ) =

min

PBD∗ (d, δV (X), δTR )(ϵ) and min

min

min obj(w, C ′ )(ϵ).

C⊆DC(leaves(δV (X),δTR ),d) X⊆X ′ ⊆vars(C) C ′ ∈A(C[X ′ ]) w∈SC′

Consider an atom R(Y ) in a view tree T for Q and an update δR to a relation R in Q. To maintain T under δR, we derive the delta view tree δTR , and compute bottom-up all delta views δV (X) along the path from R(Y ) to the root of δTR . By Lemma 17, each such delta view δV (X) can be computed in time ∗ ∗ O(N PBD (d,δV (X),δTR )(ϵ) ). The view tree T can then be maintained in time O(N PBD (d,T )(ϵ) ) by taking the maximum over all views in T and for each such view V the maximum over all atoms R at the leaves of this view of the time to compute the δV under the update δR. By Def. 20, we conclude that Q can be maintained in time O(N mw(Q) ) under any update to its input relations.

4.4

Computing the Maintenance Width

The computability of the maintenance width relies on the observation that all domains in Def. 20, excluding the interval [0, 1], are finite. Let H denote the set of affine functions f (ϵ) = obj(w, C)(ϵ) generated by the inner minimization over C and w. The maintenance width can be viewed as the value of a logical expression involving finite min and max operations over functions in H. We rewrite the nested minimization and maximization steps into a canonical min-of-max form by iteratively using the distributivity of max over min: max(a, min(b, c)) = min(max(a, b), max(a, c)). Thus, there exists a finite index set M and, for each i ∈ M, a finite set of affine functions Fi ⊆ H such that: mw(Q) = min min max f (ϵ) . (8) i∈M

ϵ∈[0,1]

f ∈Fi

Since the min operator is commutative, we can swap the continuous minimization over ϵ with the discrete minimization over i. This yields: mw(Q) = min min max f (ϵ) . (9) i∈M

ϵ∈[0,1]

f ∈Fi

Eq. (9) reduces the optimization problem to finding the minimum of |M| independent sub-problems. Each sub-problem aims to minimize the pointwise maximum of a finite set of affine functions over the unit interval. Consequently, the objective is a piecewise linear convex function of ϵ, which can be efficiently minimized by the following linear program:

minimize

subject to

v ≥ f (ϵ)

∀f ∈ Fi

0≤ϵ≤1 By solving these linear programs, we obtain both the exact value of mw(Q) and the optimal parameter ϵ∗ for which this value is obtained. Fixing ϵ∗ determines the threshold for data partitioning. We then proceed to select the optimal view tree for each degree configuration d by choosing the view tree T that minimizes the maintenance width for this fixed ϵ∗ . In case of ties, we deterministically select a canonical tree (e.g., in lexicographical order). We denote this selected tree by T (d). The set of these selected trees constitutes the set of active view trees that we use in our maintenance algorithm. In practice, this set can be significantly smaller than the set of all possible view trees. For instance, we only need six view trees for the optimal maintenance of the 4-cycle query. Furthermore, for every update δRj and view V (X) we determine the optimal set X ′ of variable to use for computing a guarding query that is an over-approximation of δV under the update δRj . 14

Comparison with Prior Width Measures

In this section, we compare the maintenance width with other common width measures and discuss our choice of view trees as the maintenance strategy of our approach.

5.1

Dynamic Width

The maintenance width generalizes the previously introduced notion of dynamic width, which defines the update time for maintaining queries under simple size constraints [18]. Any query Q can be maintained with O(N dw(Q) ) update time, where dw(Q) denotes the dynamic with of Q. To the best of our knowledge, the dynamic width defines the best update time achieved by approaches that do not rely on heavy-light partitioning. The F-IVM column in Table 1 lists the update times for several queries, these times follow the dynamic width5 . For any hierarchical query Q, we have mw(Q) = dw(Q) = 0. Hence, both our approach and F-IVM achieve O(1) update time. For the bow tie query Q, we have mw(Q) = dw(Q) = 1, implying that both our approach and F-IVM achieve O(N ) update time. For all other queries in Table 1, we have mw(Q) < dw(Q), which means that our approach outperforms F-IVM. Computing the dynamic width requires iterating over all view trees, then over the views in each view tree, and finally over the leaves under each view. For the maintenance width, we must further iterate over all degree configurations, which accounts for the increased complexity of the definition, yet which may yield a smaller width value. In the following, we introduce the dynamic width dw and show that mw(Q) is upper-bounded by dw(Q) for any join query Q. We start by recalling the fractional edge cover number of a set of variables with regard to a query [4]. Given a query Q and a set Y ⊆ vars(Q) of variables, the fractional edge cover number ρ∗Q (Y ) of Y with regard to Q is the cost of the optimal solution of the following linear program: X minimize wR(X) R(X)∈at(Q)

subject to

wR(X) ≥ 1

for all B ∈ Y

R(X):B∈X

wR(X) ≥ 0

for all R(X) ∈ at(Q)

Given a set L of atoms of a query Q, we denote by QL the join query whose body is the conjunction of the atoms in L. We can now define the dynamic width of a join query6 : Definition 22 (Dynamic Width). For any join query Q, the dynamic width of Q is def

dw(Q) =

min

T ∈T (Q)

max V (X)∈T R(Y )∈leaves(V (X),T )

ρ∗Qleaves(V (X),T ) (X \ Y ).

(10)

Proposition 23. For any join query Q, it holds mw(Q) ≤ dw(Q). Proof. The proof is implied by the following chain of (in)equalities. We explain each step below. def

mw(Q) = min

max

min

ϵ∈[0,1] d∈D(Q) T ∈T (Q)

max

min

V (X)∈T R(Y )∈leaves(V (X),T )

C⊆DC(leaves(δV (X),δTR ),d) X⊆X ′ ⊆vars(C) C ′ ∈A(C[X ′ ]) w∈SC′

(1)

≤ max

min

d∈D(Q) T ∈T (Q)

max

min

V (X)∈T R(Y )∈leaves(V (X),T )

C⊆DC(leaves(δV (X),δTR ),d) X⊆X ′ ⊆vars(C) C ′ ∈A(C[X ′ ]) w∈SC′

obj(w, C ′ )(ϵ)

obj(w, C ′ )(1)

5 Although the work on F-IVM [17] did not formally introduce the notion of dynamic width, the update time achieved by F-IVM for any query Q is of the form O(N dw(Q) ), where dw(Q) denotes the dynamic width of Q. The notion of dynamic width was formally introduced in subsequent work [18]. 6 We introduce here a simplified version of the dynamic width restricted to join queries, whereas the original definition [18] is for the more general conjunctive queries. This is because our maintenance width is defined here for join queries only.

(2)

min

max

T ∈T (Q)

min

V (X)∈T R(Y )∈leaves(V (X),T )

(3)

≤

min

V (X)∈T R(Y )∈leaves(V (X),T )

(4)

≤

min

max

T ∈T (Q)

obj(w, C ′ )(1)

ˆ min obj(w, C)(1)

max

T ∈T (Q)

C⊆DC(leaves(δV (X),δTR ),L) X⊆X ′ ⊆vars(C) C ′ ∈A(C[X ′ ]) w∈SC′

V (X)∈T R(Y )∈leaves(V (X),T )

w∈SĈ

ρ∗Qleaves(V (X),T ) (X \ Y )

def

= dw(Q),

where L = (L)|JQ | is the degree constraint where all join variables are light and Cˆ = C[X] with C = {(Z|∅, N )|S(Z) ∈ leaves(δV (X), δTR ) ∧ S ̸= R} ∪ {(B|∅, 1)|B ∈ Y )}. Inequality (1) is obtained by fixing ϵ to 1. Equality (2) is implied by the following observation. Consider a degree configuration d ∈ D(Q) and a vector w ∈ SC ′ in the definition of mw(Q). Assuming that ϵ = 1, any degree constraint resulting from a variable A that is heavy in d is of the form (A | ∅, N 1−ϵ = N 0 ). This implies that for any vector w ∈ SC ′ , the additive factor added to obj(w, C ′ )(1) by such a constraint is of the form wi · (1 − ϵ) = 0. Hence, instead of maximizing obj(w, C ′ )(1) over all possible degree configurations, it suffices to restrict to the configuration L = (L)|JQ | , where all variables are light. Inequality (3) holds because C ⊆ DC(leaves(δV (X), δTR ), L) and both C and Cˆ = C[X] are acyclic, since the graph associated with C does not have any edge. For Inequality (4), consider a view δV (X) in a delta view tree for an update δR(Y ). Assume that Ĉ = {c1 , . . . , cm } ∪ {cB }B∈X∩Y , where each ci is of the form (Z|∅, N ) and each cB is of the form (B|∅, 1). ˆ The linear program determining minw∈SĈ obj(w, C)(1) is as follows: X

minimize

wi · 1 +

subject to

wB · 0

B∈X∩Y

ci =(Z|∅,N )

wi ≥ 1

∀A ∈ X \ Y

wi + w B ≥ 1

∀B ∈ X ∩ Y

ci =(Z|∅,N ) A∈Z

(11)

ci =(Z|∅,N ) B∈Z

wi ≥ 0

∀i ∈ [m]

w ≥0

∀B ∈ X ∩ Y

The above program simplifies to the linear program determining ρ∗Qleaves(V (X),T ) (X \Y ) due to the following two observations. Firstly, each constraint in Cˆ is of the form (Z|∅, N ) or of the form (B|∅, 1) with B ∈ X ∩Y . Secondly, the weights wB associated with constraints of the form cB = (B|∅, 1) do not have any effect on the objective function of the above linear program, since they are multiplied with 0 in the definition of the objective function. Hence, the constraints in Line (11) can be easily satisfied by setting such a weight wB to 1. This implies that constraints in Line (11) can be omitted.

5.2

Fractional Hypertree Width and Submodular Width

The maintenance width does not come with a simple syntactic check. Indeed, to find this width for a given query Q, one needs to iterate over all view trees and degree configurations for Q and solve a linear program to cost the update of each view in a view tree triggered by an update to any input relation. Yet this is conceptually not different from well-established width measures, such as the fractional hypertree width [25] or the submodular width [2]. These widths are defined by iterating over all hypertree decompositions [9] of Q and by solving a linear program to cost each bag of a hypertree decomposition. Furthermore, the 16

submodular width also requires adaptive computation by data partitioning. There are two differences here: (i) The data partitioning for the submodular width is fine-grained as it yields (poly-logarithmically many in N ) database parts of uniform degrees, whereas for the maintenance width it is coarse-grained as it yields (constantly many in N ) database parts with either heavy or light degrees. (ii) The data partitioning for the maintenance width is on the input relations only, whereas for the submodular width it can also be on the intermediate results (so also on the materialized views in our setting). There are two aspects of our maintenance width which are distinct from the aforementioned widths. (i) Due to our dynamic setting, we need to consider the cost of view updates in addition to the cost of computing the view only. (ii) We do not know the concrete cost of each view update until we fix the threshold ϵ, which can only be done after constructing the function in ϵ that defines the width. This is novel to our setting.

5.3

View Trees vs. Hypertree Decompositions

Each view tree of a query Q can be mapped to a hypertree decomposition of Q (possibly with redundant bags), where each view (relation) becomes a bag consisting of the view variables. Also, from each hypertree decomposition we can construct a view tree, with one view for each bag of the decomposition, possibly additional projection views, and one leaf per relation in Q. So both view trees and hypertree decompositions allow us to explore the same space of structural decompositions of Q, albeit the view trees are more refined in that they use redundant information in the form of materialized projection views to allow for a faster propagation of updates in the view trees.

Major and Minor Rebalancing of Data Partitioning

In the previous sections we showed that for any join query Q, the view trees constructed by our approach can be maintained in O(N mw(Q) ) time under one single-tuple update, where mw(Q) denotes the maintenance width of Q. In this section, we extend this analysis to sequences of single-tuple updates. We show that, given a sequence of single-tuple updates, the amortized single-tuple update time remains O(N mw(Q) ). Our proof is based on an adaptation of the amortization technique previously developed for the triangle query [15]. For clarity, we outline the differences from that prior work and state the central ideas of the argument. Each update may affect both the size of the database and the degrees of data values. Whenever the database size exceeds specified bounds, we recompute the view trees for all degree configurations by taking the new database size into account. We refer to this operation as major rebalancing. Similarly, if a light value becomes heavy, or vice-versa, as a result of an update, we move the affected tuples between the corresponding relation fragments and update the view trees evaluated over these fragments. We call this operation minor rebalancing. The cost of both types of rebalancing can be amortized over the number of updates between two consecutive rebalancing steps, yielding an amortized rebalancing cost of O(N mw(Q) ) per single-tuple update. One difference between the maintenance strategy for the triangle query in prior work [15] and the approach proposed here is the definition of light and heavy values. In the prior work, lightness and heaviness were defined with respect to each individual relation; that is, an X-value x is considered light in a relation R if |σX=x R| ≤ N ϵ , and heavy otherwise. In contrast, in this work we define lightness and heaviness globally, with respect to all relations in the database (see Sec. 2). This distinction does not change the analysis of the amortized rebalancing time. The detailed analysis of the major and minor rebalancing steps is given in the extended version of this article.

Constant-Delay Enumeration of the Query Output

For any join query, our approach constructs a set of view trees and maintains them under single-tuple updates to the input relations. As discussed in this section, we can also enumerate the query output from these view trees with constant delay. Consider a join query Q(X) = R1 (X 1 ) · . . . · Rk (X k ) with degree configurations D(Q). Let OUT denote the set of output tuples of Q, and OUTd the set of output tuples of Q under the degree configuration d ∈ D(Q). The set OUT is the disjoint union of the sets OUTd . Given a constant-delay enumeration procedure for each tuple set OUTd , we can therefore enumerate the tuples in OUT with constant delay by 17

P invoking the procedures one after the other. For each tuple t ∈ OUT, its multiplicity is i∈[k] Ri (t.X i ), which can be computed in constant time. We next discuss such a constant-delay enumeration procedure for a single set OUTd , for any d ∈ D(Q). Recall that for each degree configuration d ∈ D(Q), our approach maintains a view tree T d . It then suffices to enumerate OUTd from T d with constant delay. Prior work shows how from any view tree, the tuples in the join of the views in the tree can be enumerated with constant delay [13, Prop. 11]. The extended version of this article gives further details, illustrates the enumeration procedure for the 4-cycle query, and explains how to slightly change the approach to maintain the count version of the query with the same update time and constant-delay enumeration.

Conclusion

In this paper we introduced an approach to adaptive maintenance of join queries under database updates (inserts and deletes) that exploits the constraints that come with partitioning the database using the heavy and light degrees of the values of the join variables. Our approach matches the best known update times stated in the literature, while also generalizing to arbitrary join queries. There are several promising directions of future work, we list below a few: • Our complexity results hold for join queries only, but they can be generalized in a standard way to arbitrary conjunctive queries by taking view trees that correspond to free-connex hypertree decompositions of such queries. This free-connex restriction is necessary to ensure constant delay enumeration of the query output. The machinery developed in this paper to upper bound the sizes and compute times for delta views already works for arbitrary conjunctive queries. • We can extend our approach to richer constraints beyond degree constraints: Using ℓp -norms on the degree sequences of join columns, we can obtain tighter upper bounds on the size of the query output and on the runtime to compute it [19, 20]. Adopting such statistics to the dynamic setting requires to maintain them efficiently under updates. • We currently partition the data on each join variable. It remains open whether partitioning on tuples of variables and subsets of such tuples can improve the update time. For instance, for a query with body R(A, B, C) · S(A, B, D) · T (A, E) · U (B, F ) we currently only partition on A and B separately, although we could also partition on the tuple A, B. Our framework extends immediately to this more general setting. • We can lower the update time by using fast matrix multiplication: The O(N 2/3 ) barrier for the update time of the 4-cycle query can be broken using a non-combinatorial IVM approach [3]. It is unclear however how to generalize this non-combinatorial approach to arbitrary queries. • When using a maintenance approach based on single view tree, inserts-only updates can require a lower update time than the general case with both inserts and deletes [1]. It is open whether this restriction can also lower the update time in our approach.

References [1] Mahmoud Abo Khamis, Ahmet Kara, Dan Olteanu, and Dan Suciu. Insert-only versus insert-delete in dynamic query evaluation. Proc. ACM Manag. Data, 2(5), November 2024. doi:10.1145/3695837. [2] Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. Panda: Query evaluation in submodular width. TheoretiCS, Volume 4, Apr 2025. URL: https://theoretics.episciences.org/13722, doi:10.46298/theoretics.25.12. [3] Sepehr Assadi and Vihan Shah. An improved fully dynamic algorithm for counting 4-cycles in general graphs using fast matrix multiplication. Proc. ACM Manag. Data, 3(2):91:1–91:24, 2025. doi:10.1145/ 3725228.

[4] Albert Atserias, Martin Grohe, and Dániel Marx. Size bounds and query plans for relational joins. In FOCS, pages 739–748, 2008. doi:10.1109/FOCS.2008.43. [5] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering Conjunctive Queries Under Updates. In PODS, pages 303–318, 2017. doi:10.1145/3034786.3034789. [6] Mihai Budiu, Leonid Ryzhyk, Gerd Zellweger, Ben Pfaff, Lalith Suresh, Simon Kassing, Abhinav Gyawali, Matei Budiu, Tej Chajed, Frank McSherry, and Val Tannen. DBSP: automatic incremental view maintenance for rich query languages. VLDB J., 34(4), 2025. doi:10.1007/S00778-025-00922-Y. [7] Rada Chirkova and Jun Yang. Materialized views. Found. Trends Databases, 4(4):295–405, 2012. doi:10.1561/1900000020. [8] Arnaud Durand and Etienne Grandjean. First-order queries on structures of bounded degree are computable with constant delay. ACM Trans. Comput. Logic, 8(4), August 2007. doi:10.1145/1276920. 1276923. [9] Georg Gottlob, Zoltán Miklós, and Thomas Schwentick. Generalized hypertree decompositions: Nphardness and tractable variants. J. ACM, 56(6):30:1–30:32, 2009. doi:10.1145/1568318.1568320. [10] Kathrin Hanauer, Monika Henzinger, and Qi Cheng Hua. Fully dynamic four-vertex subgraph counting. In SAND, pages 18:1–18:17, 2022. doi:10.4230/LIPICS.SAND.2022.18. [11] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In STOC, pages 21–30, 2015. doi:10.1145/2746539.2746609. [12] Muhammad Idris, Martı́n Ugarte, and Stijn Vansummeren. The dynamic yannakakis algorithm: Compact and efficient query processing under updates. In SIGMOD, pages 1259–1274, 2017. doi: 10.1145/3035918.3064027. [13] Ahmet Kara, Zheng Luo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Tractable Conjunctive Queries over Static and Dynamic Relations. In ICDT, pages 12:1–12:21, 2025. doi:10.4230/LIPIcs. ICDT.2025.12. [14] Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Counting triangles under updates in worst-case optimal time. In ICDT, pages 4:1–4:18, 2019. doi:10.4230/LIPICS.ICDT.2019. 4. [15] Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Maintaining triangle queries under updates. ACM Trans. Database Syst., 45(3):11:1–11:46, 2020. doi:10.1145/3396375. [16] Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Trade-offs in static and dynamic evaluation of hierarchical queries. In PODS, pages 375–392, 2020. doi:10.1145/3375395.3387646. [17] Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. F-IVM: analytics over relational databases under updates. VLDB J., 33(4):903–929, 2024. doi:10.1007/S00778-023-00817-W. [18] Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Conjunctive queries with free access patterns under updates. LMCS, Volume 21, Issue 2, Jun 2025. URL: https://lmcs.episciences. org/13059, doi:10.46298/lmcs-21(2:23)2025. [19] Mahmoud Abo Khamis, Vasileios Nakos, Dan Olteanu, and Dan Suciu. Join size bounds using lp -norms on degree sequences. Proc. ACM Manag. Data, 2(2):96, 2024. doi:10.1145/3651597. [20] Mahmoud Abo Khamis, Vasileios Nakos, Dan Olteanu, and Dan Suciu. Information theory strikes back: New development in the theory of cardinality estimation. SIGMOD Rec., 54(1):7–15, 2025. doi:10.1145/3733620.3733623.

[21] Mahmoud Abo Khamis, Hung Q. Ngo, and Atri Rudra. FAQ: questions asked frequently. In PODS, pages 13–28, 2016. doi:10.1145/2902251.2902280. [22] Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. Computing join queries with functional dependencies. In PODS, pages 327–342, 2016. doi:10.1145/2902251.2902289. [23] Christoph Koch, Yanif Ahmad, Oliver Kennedy, Milos Nikolic, Andres Nötzli, Daniel Lupei, and Amir Shaikhha. DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views. VLDB J., 23(2):253–278, 2014. doi:10.14778/2336664.2336670. [24] Lynn Harold Loomis and Hassler Whitney. An inequality related to the isoperimetric inequality. Bulletin of the American Mathematical Society, 55:961–962, 1949. URL: https://api.semanticscholar.org/ CorpusID:123450423. [25] Dániel Marx. Approximating fractional hypertree width. ACM Trans. Algorithms, 6(2):29:1–29:17, 2010. doi:10.1145/1721837.1721845. [26] Derek Gordon Murray, Frank McSherry, Michael Isard, Rebecca Isaacs, Paul Barham, and Martı́n Abadi. Incremental, iterative data processing with timely dataflow. Commun. ACM, 59(10):75–83, 2016. doi:10.1145/2983551. [27] Hung Q. Ngo. Worst-case optimal join algorithms: Techniques, results, and open problems. In PODS, page 111–124, 2018. doi:10.1145/3196959.3196990. [28] Dan Olteanu. Recent increments in incremental view maintenance. In PODS, pages 8–17, 2024. doi: 10.1145/3635138.3654763. [29] Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons, Inc., USA, 1986. [30] Daniel Sotolongo, Daniel Mills, Tyler Akidau, Anirudh Santhiar, Attila-Péter Tóth, Botong Huang, Boyuan Zhang, Igor Belianski, Ling Geng, Matt Uhlar, Nikhil Shah, Olivia Zhou, Saras Nowak, Sasha Lionheart, Vlad Lifliand, Wendy Grus, Yiwen Zhu, Ankur Sharma, Dzmitry Pauliukevich, Enrico Sartorello, Ilaria Battiston, Ivan Kalev, Lawrence Benson, Leon Papke, Niklas Semmler, Till Merker, and Yi Huang. Streaming democratized: Ease across the latency spectrum with delayed view semantics and snowflake dynamic tables. In SIGMOD, pages 622–634, 2025. doi:10.1145/3722212.3724455. [31] Dan Suciu, Dan Olteanu, R. Christopher, and Christoph Koch. Probabilistic Databases. Morgan & Claypool Publishers, 1st edition, 2011. [32] Qichen Wang, Xiao Hu, Binyang Dai, and Ke Yi. Change propagation without joins. Proc. VLDB Endow., 16(5):1046–1058, 2023. doi:10.14778/3579075.3579080.

Additional Examples

In this section, we provide additional (and extended) examples of our maintenance approach and show how it can recover all results of existing IVM approaches (where the update time is amortized, and the enumeration delay is constant). Conditional on the OMv conjecture [11, 5] or on the conjectured optimality of the submodular width for static query evaluation [1], the update times shown here cannot be improved for any query by a polynomial factor, except for the update time of the bow tie query, which exhibits a gap of O(N 1/4 ). We also highlight the adaptability of our approach, which can be used to maintain any join query. To this end, we demonstrate our approach on query patterns that have not been specifically considered in prior IVM works and provide results on their update times.

A.1

Extended Example: 4-Cycle Query

In Sec. 3, we claimed that our approach maintains the 4-cycle query Q□ (A, B, C, D) = R(A, B) · S(B, C) · T (C, D) · U (D, A) with amortized update time O(N 2/3 ). The update time cannot be improved by a polynomial factor, conditional on the conjectured optimality of the submodular width for static query evaluation [1]. In this section, we explain how we obtain the update times given in Table 2. As Q□ has four join variables, there are 16 degree configurations. For each degree configuration, we pick an optimal view tree to use for maintenance. Fig. 1 shows the six view trees we use and Table 2 shows the view tree chosen for each degree configuration and the update time as a function of ϵ. The update time is the maximum compute time of any delta view in the delta view tree for an update to any relation. We illustrate in detail how to find the update times of the three degree configurations below: {(L, L, L, L), (L, L, H, H), (L, H, H, H)} Other degree configurations witness identical update times that are derived similarly. Note: In our analysis we do not explicitly state the compute time of views corresponding to marginalizations and intersections (except the first time), as their compute times are inherited from a child view whose compute time has already been shown. A.1.1

(L, L, L, L)

For the degree configuration d = (L, L, L, L) and View Tree 1 in Fig. 1, we simulate an update to each of the four relations R, S, T , and U , find the compute time of each delta view, and take the maximum. We begin with δR. The first delta view to be evaluated is δV1 (A, B, C) = δR(A, B) · S(B, C). The constraints that holds at the leaves of δV1 in the delta view tree are: C1 = DC(leaves(δV1 ), d) = {(BC|∅, N ), (BC|B, N ϵ ), (BC|C, N ϵ ), (A|∅, 1), (B|∅, 1)}. As the free variables of δV1 are precisely vars(C1 ), C1 is the only constraint set to consider when bounding the compute time of δV1 , and the C1 -guarding query is QC1 = δR(A, B) · S(B, C) = δV1 . PBD(C1 ) = ϵ ϵ using the second, fourth, and fifth constraints, P which yields the compute time O(N ) for δV1 . The next delta view to be evaluated is δV3 (A, C) = B δV1 (A, B, C). The constraint set that holds at the leaves of δV2 is C1 . We consider C1 projected onto different supersets of the free variables of δV3 , namely C1 [AC] = {(C|∅, N ), (A|∅, 1)} and C1 [ABC] = C1 . The join query QC1 that over-approximates δV3 gives the best upper bound of O(N ϵ ) on the compute time of δV3 . Next, we have δV5 (A, C) = δV3 (A, C) · V4 (C, A). The constraints that holds at the leaves of δV5 are: C5 = DC(leaves(δV5 ), d) = {(BC|∅, N ), (CD|∅, N ), (DA|∅, N ), (BC|B, N ϵ ), (BC|C, N ϵ ), (CD|C, N ϵ ), (CD|D, N ϵ ), (DA|A, N ϵ )(DA|D, N ϵ ), (A|∅, 1), (B|∅, 1)} We consider the constraint sets C5 [AC], C5 [ABC], C5 [ACD], and C5 [ABCD] = C5 . The constraint set C5 [ABC] = {(BC|∅, N ), (C|∅, N ), (A|∅, N ), (BC|B, N ϵ ), (BC|C, N ϵ ), (A, ∅, 1), (B|∅, 1)} has the guarding query QC5 [ABC] = δR(A, B) · S(B, C) · T ′ (C) · U ′ (A), where T ′ is the projection of T onto C and U ′ is the projection of U onto A. QC5 [ABC] over-approximates δV5 and gives the best upper bound of O(N ϵ ) on the compute time by using the fourth, sixth, and seventh constraints. Thus, the update time for δR is O(N ϵ ). Because all join variables are light, updates to the remaining relations are symmetric in the respective delta view trees and obtain the same update time. Thus, the update time for the degree configuration (L, L, L, L) and View Tree 1 is O(N ϵ ).

A.1.2

(L, L, H, H)

Next, we show the update time for (L, L, H, H) using View Tree 4 in Fig. 1. Consider an update δR. The first delta view to be evaluated is δV1 (A, B, C) = δR(A, B) · S(B, C). The constraints that holds at the leaves of δV1 are: C1 = DC(leaves(δV1 ), d) = {(BC|∅, N ), (BC|B, N ϵ ), (C|∅, N 1−ϵ ), (A|∅, 1), (B|∅, 1)} We can use the second, fourth, and fifth constraints to yield the compute time O(N ϵ ), or we can use the third, fourth, and fifth constraints to yield the compute time O(N 1−ϵ ). Thus, the compute time for δV1 is O(N min(ϵ,1−ϵ) ). Next, we have δV3 (A, C, D) = δV2 (A, C) · U (D, A). The constraints that hold at the leaves of δV3 are: C3 = DC(leaves(δV3 ), d) = {(BC|∅, N ), (DA|∅, N ), (BC|B, N ϵ ), (DA|A, N ϵ ), (C|∅, N 1−ϵ ), (D|∅, N 1−ϵ ), (A|∅, 1), (B|∅, 1)}. We consider the constraint sets C3 [ACD] and C3 [ABCD] = C3 . The C3 -guarding query that over-approximates δV3 has compute time O(N 2ϵ ) (selecting the third, fourth, seventh, and eighth constraints) or O(N 2−2ϵ ) (selecting the fifth, sixth, seventh, and eighth constraints). The projection C3 [ACD] does not give a better compute time. Thus, the compute time of δV3 is O(N min(2ϵ,2−2ϵ) ). Now we consider an update δS. The first delta view to be evaluated is δV1 (A, B, C) = R(A, B)·δS(B, C), and the constraints that hold at the leaves of δV1 are: C1 = DC(leaves(δV1 ), d) = (AB|∅, N ), (AB|A, N ϵ ), (AB|B, N ϵ ), (B|∅, 1), (C|∅, 1). Selecting the second, fourth, and fifth constraints gives the compute time O(N ϵ ) for δV1 . δV3 (A, C, D) = δV2 (A, C) · U (D, A) and the constraints that hold at the leaves of δV3 are: C3 = DC(leaves(δV3 ), d) = {(AB|∅, N ), (DA|∅, N ), (AB|A, N ϵ ), (AB|B, N ϵ ), (DA|A, N ϵ ), (D|∅, N 1−ϵ ), (B|∅, 1), (C|∅, 1)}. We consider the constraint sets C3 [ACD] and C3 [ABCD] = C3 . The C3 -guarding query that over-approximates δV3 presents two ways to bound the compute time: O(N ) (selecting the second, seventh, and eighth constraints), or O(N 2ϵ ) (selecting the fourth, fifth, sixth, and eighth constraints). C3 [ACD] does not give a better compute time. Thus, the compute time of δV3 is O(N min(2ϵ,1) ), which is also update time for δS. Now we consider an update δU . The first delta view to be evaluated is δV3 , and we have δV3 (A, C, D) = V2 (A, C) · δU (D, A). The constraints that hold at the leaves of δV3 are: C3 = DC(leaves(δV3 ), d) = {(AB|∅, N ), (BC|∅, N ), (AB|A, N ϵ ), (AB|B, N ϵ ), (BC|B, N ϵ ), (C|∅, N 1−ϵ ), (D|∅, 1), (A|∅, 1)}. We consider the constraint sets C3 [ACD] = {(A|∅, N ), (C|∅, N ), (C|∅, N 1−ϵ ), (D|∅, 1), (A|∅, 1)} and C3 [ABCD] = C3 . The C3 [ACD]-guarding query that over-approximates δV3 has compute time O(N 1−ϵ ) (selecting the third, fourth, and fifth constraints). The C3 -guarding query has compute time O(N 2ϵ ) (selecting the third, fifth, seventh, and eighth constraints). Thus, the compute time of δV3 is O(N min(1−ϵ,2ϵ) ), which is also the overall update time for δU . Finally, and update δT has constant update time because C5 [CD] = DC(leaves(δV5 ), d)[CD] = {(C|∅, N ), (D|∅, N ), (C|∅, N 1−ϵ ), (D|∅, N 1−ϵ ), (C|∅, 1), (D|∅, 1)} and the C5 [CD]-guarding query that over-approximates δV5 has compute time O(1) (selecting the fifth and sixth constraints). Overall, the update time for degree configuration (L, L, H, H) and view tree four is given by O(N f (ϵ) ), where f (ϵ) = max(min(2ϵ, 2 − 2ϵ), min(2ϵ, 1)), as shown in Table 2. 22

A.1.3

(L, H, H, H)

Finally, we show the update time for the degree configuration (L, H, H, H) using View Tree 2 in Fig. 1. Consider an update δR. We evaluate δV1 (A, B, D) = δR(A, B) · U (D, A). The constraints that hold at the leaves of δV1 in the delta view tree are: C1 = DC(leaves(δV1 ), d) = {(DA|∅, N ), (DA|A, N ϵ ), (D|∅, N 1−ϵ ), (A|∅, 1), (B|∅, 1)}. The C1 -guarding query is precisely δV1 , and the compute time is O(N ϵ ) (selecting the second, fourth, and fifth constraints) or O(N 1−ϵ ) (selecting the third, fourth, and fifth constraints). Thus, the compute time of δV1 is O(N min(ϵ,1−ϵ) ), which is also the overall update time for δR. An update δU is symmetric to δR and yields the same update time. For an update δS, we evaluate δV2 (B, C, D) = δS(B, C) · T (C, D). The constraints that hold at the leaves of δV2 in the delta view tree are: C2 = DC(leaves(δV2 ), d) = {(CD|∅, N ), (C|∅, N 1−ϵ ), (D|∅, N 1−ϵ ), (B|∅, 1), (C|∅, 1)}. The C2 -guarding query is precisely δV2 , and the compute time is O(N 1−ϵ ) (selecting the third, fourth, and fifth constraints), which is also the overall update time for δS. An update δT is symmetric to δS and achieves the same update time. After simplifying, we have that the update time for degree configuration (L, H, H, H) using View Tree 2 is O(N 1−ϵ ). A.1.4

Maintenance Width

We have shown how to derive all three unique update times shown in Table 2. The update times of the remaining degree configurations can be obtained through similar analysis. The maintenance width mw(Q□ ) of the 4-cycle query is then the minimum over all expressions in the table for the base N logarithm of the update time. This width can be computed as the minimization over ϵ of the maximum optimal solution of linear programs. mw(Q□ ) = min max(ϵ, 1 − ϵ, max(min(2ϵ, 2 − 2ϵ), min(2ϵ, 1))) ϵ

= min max(ϵ, 1 − ϵ, min(2ϵ, 2 − 2ϵ), min(2ϵ, 1)) ϵ

∗

= min min(max(ϵ, 1 − ϵ, 2ϵ, 2ϵ), max(ϵ, 1 − ϵ, 2ϵ, 1), ϵ

max(ϵ, 1 − ϵ, 2 − 2ϵ, 2ϵ), max(ϵ, 1 − ϵ, 2 − 2ϵ, 1)) +

= min(min max(ϵ, 1 − ϵ, 2ϵ, 2ϵ) s.t. 0 ≤ ϵ ≤ 1 ϵ

min max(ϵ, 1 − ϵ, 2 − 2ϵ, 1) s.t. 0 ≤ ϵ ≤ 1 ϵ

min max(ϵ, 1 − ϵ, 2 − 2ϵ, 2ϵ) s.t. 0 ≤ ϵ ≤ 1 ϵ

min max(ϵ, 1 − ϵ, 2 − 2ϵ, 1) s.t. 0 ≤ ϵ ≤ 1) ϵ

s.t.

q≥ϵ

q ≥1−ϵ

q ≥ 2ϵ

0 ≤ ϵ ≤ 1.

We can observe that the optimal solution is 2/3 and obtained for ϵ = 1/3. The other optimization problems give larger solutions. The update time of Q□ is then O(N 2/3 ).

V4 (B, C, D)

V4 (A, C, D)

V4 (A, B, D)

V4 (A, B, C)

V3 (B, C, D) R(B, C, D)

V3 (A, C, D) S(A, C, D)

V3 (A, B, D) T (A, B, D)

V3 (A, B, C) U (A, B, C)

V2 (A, B, C, D)

V1 (A, B, C, D) U (A, B, C)

V1 (A, B, C, D) T (A, B, D)

S(A, C, D) T (A, B, D)

R(B, C, D) T (A, B, D)

R(B, C, D) S(A, C, D)

View Tree 1

View Tree 2

View Tree 3

View Tree 4

Figure 2: The four view trees used to maintain the LW-4 query.

A.2

Loomis-Whitney Queries

Loomis-Whitney queries generalize the triangle query from a clique of k = 3 to higher degrees [24]. The Loomis-Whitney k query of degree k ≥ 3 (denoted LW-k) is defined as Y Q(X1 , ..., Xk ) = Ri ({X1 , ..., Xk } \ {Xi }) i∈[k]

We show that our approach achieves update time O(N 1/2 ) for the LW-4 query and then extend the argument to LW-k. These update times cannot be improved by a polynomial factor, conditional on the OMv conjecture [11, 5] and on the conjectured optimality of the submodular width for static query evaluation [1]. A.2.1

Loomis-Whitney 4

LW-4 is given by QLW-4 (A, B, C, D) = R(B, C, D) · S(A, C, D) · T (A, B, D) · U (A, B, C) The four view trees used to maintain QLW-4 are shown in Fig. 2. Table 3 shows each degree configuration, the view tree used to maintain it, and the update time. The maintenance width mw(QLW-4 ) is then the minimum over all expressions in the table for the base N logarithm of the update time. This width can be computed as the minimization of optimal solutions of linear programs.

mw(QLW-4 ) = min max(ϵ, 1 − ϵ, min(ϵ, 1 − ϵ)) ϵ

= min max(ϵ, 1 − ϵ) ϵ

We can observe that the optimal solution is 1/2 and obtained for ϵ = 1/2. By Theorem 11, the update time of QLW-4 is O(N 1/2 ). A.2.2

Loomis-Whitney k

In this section, we prove our approach cannot be improved by a polynomial factor for LW-k queries conditional on the aforementioned conjectures. Proposition 24. If Q is a Loomis-Whitney k query where k ≥ 3, then Q admits O(N 1/2 ) (amortized) update time and (non-amortized) O(1) enumeration delay using our approach. Proof. Consider the Loomis-Whitney k query Q, where k ≥ 3, and set the partitioning threshold to ϵ = 1/2. Then there are 2k unique degree configurations which fall into two cases: Either the degree configuration indicates at least one light variable, or all variables are heavy.

Configuration (A, B, C, D) L, L, ∗, ∗ L, H, L, ∗ L, H, H, L L, H, H, H H, L, L, ∗

View Tree 1 1 1 1 2

Configuration (A, B, C, D) H, L, H, L H, L, H, H H, H, L, L H, H, L, H H, H, H, L H, H, H, H

logN UpdateTime ϵ ϵ ϵ f (ϵ) ϵ

View Tree 2 2 3 3 4 4

logN UpdateTime ϵ f (ϵ) ϵ f (ϵ) f (ϵ) 1−ϵ

Table 3: The (base N ) logarithm of the update time for each degree configuration and a specific view tree from Fig. 2. Note that f (ϵ) = min(ϵ, 1 − ϵ); (∗) in the degree configuration indicates that the join variable can be either heavy or light. Consider the first case and wlog, let the light variable be Xk , which appears in the schema of all relations except Rk . We construct the view tree for this degree configuration by joining R1 (X2 , ..., Xk ) and R2 (X1 , X3 , ..., Xk ) to create the view V3 (X1 , ..., Xk ). The view Vi+1 (X1 , ..., Xk ) is created by joining Vi (X1 , ..., Xk ) and Ri (X1 , ..., Xi−1 , Xi+1 , ..., Xk ) for all i ∈ [3, k − 1]. We create Vk+1 by projecting Vk onto vars(Rk ), and we create Vk+2 by intersecting Vk+1 and Rk . This view tree is shown in Fig. 3. We now show the update time is O(N 1/2 ). Consider an update δR1 . The first delta view to be computed is δV3 (X1 , ..., Xk ) = δR1 (X2 , ..., Xk ) · R2 (X1 , X3 , ..., Xk ). The number of X1 -values for a given Xk -value is at most N 1/2 , so the compute time is O(N 1/2 ). Each V4 , ..., Vk is simply the semi-join reduction of Vi−1 with Ri−1 and can be inductively shown to have the same compute time. Vk+1 is a projection and Vk+2 is an intersection and achieve the same compute time. An update to R2 is symmetric and achieves the same update time. Now consider an update δR3 . δV4 (X1 , ..., Xk ) = V3 (X1 , ..., Xk ) · δR3 (X1 , X2 , X4 , ..., Xk ) and the number of X3 -values for a given Xk -value is at most N 1/2 , and so δV4 has compute time O(N 1/2 ). As before, the semi-joins V5 , ..., Vk , the projection Vk+1 , and the intersection Vk+2 have the same compute time. Updates to R4 , ..., Rk−1 are symmetric and have the same update time. Now consider an update δRk . Because Vk+2 is simply an intersection of Vk+1 and a single tuple, the compute time is O(1). Thus, the update time is O(N 1/2 ) for such degree configurations. Now consider the case where all variables are heavy. Construct the same view tree as in the first case, and choose Xk arbitrarily. Consider an update δR1 . There are at most N 1/2 different X1 -values, so the compute time is O(N 1/2 ). As before, the semi-joins V4 , ..., Vk , the projection Vk+1 , and the intersection Vk+2 have the same compute time. Thus, the update time of δR1 is O(N 1/2 ). An update to R2 is symmetric and achieves the same update time. Now consider an update δR3 . There are at most N 1/2 different X1 -values, and so δV4 and has compute time O(N 1/2 ). The remaining delta views have the same compute time. Updates to R4 , ..., Rk−1 are symmetric and have the same update time. Now consider an update δRk . As before, Vk+2 is simply an intersection of Vk+1 and a single tuple, so the compute time is O(1). Thus, the update time is O(N 1/2 ) for this degree configuration. Our approach recovers this result, and Q admits update time O(N 1/2 ). It’s clear that the view trees used to maintain LW-4 (shown in Fig. 2) follow the same view tree construction given in the proof of Proposition 24 (shown in Fig. 3). That is, we use left-deep view trees in which we permute the input relations, and after each join, project out the variables which do not appear in subsequent joins.

A.3

Hierarchical Queries

Hierarchical queries are a sub-class of acyclic queries. A query is called hierarchical if for any two variables X and Y , it holds that at(X) ⊆ at(Y ), at(Y ) ⊆ at(X), or at(X) ∩ at(Y ) = ∅ [31]. We show that our approach 25

Vk+2 ({X1 , ..., Xk } \ {Xk }) Vk+1 ({X1 , ..., Xk } \ {Xk })

Rk ({X1 , ..., Xk } \ {Xk })

Vk (X1 , ..., Xk ) Rk−1 ({X1 , ..., Xk } \ {Xk−1 })

Vk−1 (X1 , ..., Xk ) . . . V4 (X1 , ..., Xk ) V3 (X1 , ..., Xk )

R3 ({X1 , ..., Xk } \ {X3 })

R1 ({X1 , ..., Xk } \ {X1 })

R2 ({X1 , ..., Xk } \ {X2 })

Figure 3: The view tree constructed in the proof of Proposition 24. LW-k achieves optimal update time using only left-deep view trees of this structure, where we permute the input relations, and after each join, project on the variables which appear in subsequent joins. obtains the optimal amortized update time for the class of hierarchical join queries (so all variables are free). Proposition 25. If Q is a hierarchical query, then Q admits O(1) (amortized) update time and (nonamortized) O(1) enumeration delay using our approach. Proof of Proposition 25. For any hierarchical query, there is a view tree that contains for each atom R(X) with X = {X1 , . . . , Xn } a root-to-leaf path of the form V1′ (X ′1 ) ← V1 (X 1 ) ← . . . ← Vn′ (X ′n ) ← Vn (X n ) ← R(X) such that for each i ∈ [n], it holds: (1) Vi (X i ) is a join view such that all views and atoms containing Xi are in the subtree rooted at Vi (X i ); (2) Vi′ (X ′i ) is a projection view that projects away Xi from Vi (X i ). Given the structural properties of hierarchical queries, this implies that any two sibling views in the view tree must be over the same set of variables. For any single-tuple update to relation R, each of the views Vi and Vi′ on the path from the atom R(X) to the root of the view tree can be updated as follows: if Vi is a join view, we do constant-time look-ups in the child views of Vi (corresponding to an intersection); if Vi′ is a projection view, we project the update tuple onto the variables of Vi′ , which takes only constant time. The constant-delay enumeration is a general property of the view trees considered in this paper. Our approach will explore the space of view trees and for each degree configuration will pick the above view tree as it has the smallest update time.

A.4

Path Queries

The k-path query is defined as Y

Q(X1 , ..., Xk+1 ) =

Ri (Xi , Xi+1 )

i∈[k]

and so there are k − 1 join variables. In this section, we illustrate our approach on the 3- and 4-path queries. The update time our approach achieves cannot be improved by a polynomial factor for either query, conditional on the OMv conjecture [11, 5] and on the conjectured optimality of the submodular width for static query evaluation [1]. A.4.1

3-Path Query

Consider the 3-path query Q (X1 , X2 , X3 , X4 ) = R1 (X1 , X2 ) · R2 (X2 , X3 ) · R3 (X3 , X4 ) 26

V6 (X3 ) V4 (X3 )

V6 (X2 ) V5 (X3 )

V4 (X2 )

V3 (X2 , X3 ) R3 (X3 , X4 )

V5 (X2 )

V3 (X2 , X3 ) R1 (X1 , X2 )

V1 (X2 )R2 (X2 , X3 )

V1 (X3 )R2 (X2 , X3 )

R1 (X1 , X2 )

R3 (X3 , X4 )

View Tree 1

View Tree 2

Figure 4: The two view trees used to maintain the 3-path query. Configuration (X2 , X3 ) L, L L, H

View Tree 1 1

Configuration (X2 , X3 ) H, L H, H

logN UpdateTime ϵ min(ϵ, 1 − ϵ)

View Tree 2 1

logN UpdateTime min(ϵ, 1 − ϵ) 1−ϵ

Table 4: The (base N ) logarithm of the update time for each degree configuration and a specific view tree from Fig. 4. (∗) in the degree configuration indicates that the join variable can be either heavy or light. Our approach uses two different view trees, shown in Fig. 4. Table 4 shows each degree configuration, the view tree used for maintenance, and the corresponding update time. The maintenance width mw(Q ) is then the minimum over all expressions in the table for the base N logarithm of the update time. This width can be computed as the minimization of optimal solutions of linear programs. mw(Q ) = min max(ϵ, 1 − ϵ, min(ϵ, 1 − ϵ)) ϵ

= min max(ϵ, 1 − ϵ) ϵ

We can observe that the optimal solution is 1/2 and obtained for ϵ = 1/2. By Theorem 11, the update time of Q is O(N 1/2 ). A.4.2

4-Path Query

Consider the 4-path query Q (X1 , X2 , X3 , X4 , X5 ) = R1 (X1 , X2 ) · R2 (X2 , X3 ) · R3 (X3 , X4 ) · R4 (X4 , X5 ) Our approach uses three different view trees, shown in Fig. 5. Table 5 shows each degree configuration, the view tree used for maintenance, and the corresponding update time. The maintenance width mw(Q ) is then the minimum over all expressions in the table for the base N logarithm of the update time. This width can be computed as the minimization of optimal solutions of linear programs. mw(Q ) = min max(ϵ, 1 − ϵ, min(ϵ, 1 − ϵ), max(ϵ, min(2ϵ, 1 − ϵ))) ϵ

= min max(ϵ, 1 − ϵ, min(2ϵ, 1 − ϵ)) ϵ

∗

= min min(max(ϵ, 1 − ϵ, 2ϵ), max(ϵ, 1 − ϵ, 1 − ϵ)) ϵ

= min(min max(ϵ, 1 − ϵ, 2ϵ) s.t. 0 ≤ ϵ ≤ 1 ϵ

min max(ϵ, 1 − ϵ, 1 − ϵ) s.t. 0 ≤ ϵ ≤ 1) ϵ

V7 (X4 ) V7 (X3 )

V7 (X2 )

V5 (X4 )

V6 (X4 )

V5 (X2 )

V6 (X2 )

V5 (X3 )

V6 (X3 )

V4 (X2 , X4 )

R4 (X4 , X5 )

V4 (X2 , X4 )

R1 (X1 , X2 )

V3 (X2 , X3 )

V4 (X3 , X4 )

V2 (X2 , X4 )

V3 (X2 )

V2 (X2 , X4 )

V3 (X4 )

V1 (X2 , X3 , X4 )

R1 (X1 , X2 )

V1 (X2 , X3 , X4 )

R4 (X4 , X5 )

V1 (X2 ) R2 (X2 , X3 ) V2 (X4 ) R3 (X3 , X4 ) R1 (X1 , X2 )

R4 (X4 , X5 )

R2 (X2 , X3 ) R3 (X3 , X4 )

View Tree 2

View Tree 3

View Tree 1

Figure 5: The three view trees used to maintain the 4-path query. Configuration (X2 , X3 , X4 ) L, L, L L, L, H L, H, L L, H, H

View Tree 1 2 1 1

Configuration (X2 , X3 , X4 ) H, L, L H, L, H H, H, ∗

logN UpdateTime ϵ max(ϵ, min(2ϵ, 1 − ϵ)) min(ϵ, 1 − ϵ) 1−ϵ

View Tree 3 2 1

logN UpdateTime max(ϵ, min(2ϵ, 1 − ϵ)) 1−ϵ 1−ϵ

Table 5: The (base N ) logarithm of the update time for each degree configuration and a specific view tree from Fig. 5. (∗) in the degree configuration indicates that the join variable can be either heavy or light. The equality (*) holds due to the distributivity of max over min, while the equality (+) is due to the commutativity of the two min functions. We then have to take the minimum of the optimal solutions of two optimization problems, which can be encoded as linear programs. We can observe that the optimal solution is 1/2 and obtained for ϵ = 1/2. By Theorem 11, the update time of Q is O(N 1/2 ).

A.5

Bow Tie Query

Prior works in IVM often focus on join queries with relatively few join variables. Our approach not only recovers these results, but can be used to maintain any join query with arbitrarily many join variables. In this section, we demonstrate our approach on the bow tie query, which admits update time O(N ) and has five join variables. Q▷◁ = R1 (X1 , X2 ) · R2 (X2 , X3 ) · R3 (X3 , X1 ) · R4 (X3 , X4 ) · R5 (X4 , X5 ) · R6 (X5 , X3 ) The bow tie can be visualized as two triangle queries that share a join variable, shown in Fig. 6. Consider a degree configuration (d1 , d2 , d3 , d4 , d5 ) of Q▷◁ . To construct the corresponding view tree T , we construct view trees T1 and T2 for the two triangle queries defined by vertices X1 , X2 , X3 and X3 , X4 , X5 , which have degree configurations (d1 , d2 , d3 ) and (d3 , d4 , d5 ), respectively. When the root views of T1 and T2 have only X3 in their schema, then given any update, we can intersect these two views to form T and incur no extra cost. Their intersection is the root view of T . Then the update time of Q▷◁ for this degree X2

X3 X1 Bow Tie

X2 X4

Paw

X3 X1

Diamond

Big Paw

Figure 6: The structures of some of the less common queries described in the examples. 28

Vroot (X3 )

V4 (X3 )

V7 (X3 )

V3 (X1 , X3 )

V6 (X3 , X4 , X5 )

V2 (X1 , X3 ) R3 (X3 , X1 )

V5 (X3 , X5 , X6 ) R5 (X4 , X5 )

V1 (X1 , X2 , X3 ) R1 (X1 , X2 )

R4 (X3 , X4 )

R6 (X5 , X3 )

R2 (X2 , X3 )

Figure 7: The view tree T for the bow tie query with degree configuration (H, L, L, H, H). The boxes indicates subtrees T1 and T2 , which correspond to view trees 1 and 6, respectively, in fig. 8. T1 and T2 are view trees for the triangle query under degree configurations (H, L, L) and (L, H, H), respectively. This can be verified in Table 6. Configuration (X1 , X2 , X3 ) L, L, ∗ L, H, L L, H, H H, L, L H, L, H H, H, L H, H, H

View Tree T1 1 2 2 1 1 3 1

Configuration (X3 , X4 , X5 ) L, L, ∗ L, H, L L, H, H H, L, L H, L, H H, H, L H, H, H

logN UpdateTime ϵ ϵ f (ϵ) ϵ f (ϵ) 1 1−ϵ

View Tree T2 4 5 6 4 4 5 4

logN UpdateTime ϵ ϵ 1 ϵ f (ϵ) f (ϵ) 1−ϵ

Table 6: The (base N ) logarithm of the update time for each degree configuration and a specific view tree from Fig. 8. Note that f (ϵ) = min(ϵ, 1 − ϵ); (∗) in the degree configuration indicates that the join variable can be either heavy or light. The bow tie query update time under each degree configuration can be found by looking up the update time of each of its triangles and taking the maximum. configuration becomes the maximum of the update time of T1 (given an update to R1 , R2 , or R3 ) and T2 (given an update to R4 , R5 , or R6 ). The construction of T for one degree configuration is shown in Fig. 7. The triangle query admits O(N ) update time when the root view must contain only X3 in its schema. All eight degree configurations of this triangle query can be maintained using three view trees. In Fig. 8, we show these three view trees for both triangles of Q▷◁ . T is formed by intersecting the root view of T1 (view tree 1, 2, or 3), with the root view of T2 (view tree 4, 5, or 6). The choice of T1 and T2 for a given degree configuration is shown in Table 6. The maintenance width mw(Q▷◁ ) is then the minimum over all expressions in the table for the base N logarithm of the update time. This width can be computed as the minimization of optimal solutions of linear programs. mw(Q▷◁ ) = min max(ϵ, 1 − ϵ, min(ϵ, 1 − ϵ), 1) ϵ

= min max(ϵ, 1 − ϵ, 1) ϵ

We can observe that any choice of ϵ results in the optimal solution 1, so we pick ϵ = 0. By Theorem 11, the update time of Q▷◁ is O(N ).

V4 (X3 )

V3 (X1 , X3 )

V3 (X2 , X3 )

V4 (X3 )

V2 (X2 , X3 ) R2 (X2 , X3 )

V3 (X1 , X2 , X3 )

V2 (X1 , X3 )

R3 (X3 , X1 )

V1 (X1 , X2 , X3 )

R1 (X1 , X2 ) R2 (X2 , X3 )

R1 (X1 , X2 )

R3 (X3 , X1 )

V1 (X1 , X2 , X3 ) R2 (X2 , X3 )

R2 (X2 , X3 )

R3 (X3 , X1 )

View Tree 1

View Tree 2

V8 (X3 )

V7 (X3 , X5 )

V7 (X3 , X4 )

V7 (X3 )

V6 (X3 , X5 ) R6 (X5 , X3 )

V6 (X3 , X4 ) R4 (X3 , X4 )

V6 (X3 , X4 , X5 )

V5 (X3 , X4 , X5 ) R4 (X3 , X4 )

View Tree 3

V5 (X4 , X5 , X6 )

R5 (X4 , X5 )

View Tree 4

R6 (X5 , X3 )

V5 (X3 , X5 , X6 ) R4 (X3 , X4 )

View Tree 5

R5 (X4 , X5 )

R6 (X5 , X3 ) View Tree 6

Figure 8: Each view tree used to maintain the bow tie query can be constructed by creating a view Vroot (X3 ) and attaching from this root two view trees: one from the set {1, 2, 3} and one from the set {4, 5, 6}.

A.6

Diamond Query

Now we consider the diamond query Q = R1 (X1 , X2 ) · R2 (X2 , X3 ) · R3 (X3 , X4 ) · R4 (X4 , X1 ) · R5 (X1 , X3 ) which can be visualized as the 4-cycle with a single chord, shown in Fig. 6. Q uses seven view trees shown in Fig. 9. Table 7 shows for each degree configuration, the view tree used for maintenance, and the corresponding update time. The maintenance width mw(Q ) is then the minimum over all expressions in the table for the base N logarithm of the update time. This width can be computed as the minimization of optimal solutions of linear programs. mw(Q ) = min max(ϵ, 2ϵ, 1 − ϵ, min(ϵ, 1 − ϵ), max(min(2ϵ, 2 − 2ϵ), min(2ϵ, 1)), ϵ

max(1 − ϵ, min(2ϵ, 2 − 2ϵ))) = min max(2ϵ, 1 − ϵ, min(2ϵ, 2 − 2ϵ), min(2ϵ, 1)) ϵ

∗

= min min(max(2ϵ, 1 − ϵ, 2ϵ, 2ϵ), max(2ϵ, 1 − ϵ, 2ϵ, 1), ϵ

max(2ϵ, 1 − ϵ, 2 − 2ϵ, 2ϵ), max(2ϵ, 1 − ϵ, 2 − 2ϵ, 1)) +

= min(min max(2ϵ, 1 − ϵ, 2ϵ, 2ϵ) s.t. 0 ≤ ϵ ≤ 1 ϵ

min max(2ϵ, 1 − ϵ, 2 − 2ϵ, 1) s.t. 0 ≤ ϵ ≤ 1 ϵ

min max(2ϵ, 1 − ϵ, 2 − 2ϵ, 2ϵ) s.t. 0 ≤ ϵ ≤ 1 ϵ

min max(2ϵ, 1 − ϵ, 2 − 2ϵ, 1) s.t. 0 ≤ ϵ ≤ 1) ϵ

V4 (X1 , X2 , X4 )

V4 (X2 , X3 , X4 )

V5 (X3 , X1 )

V3 (X1 , X2 , X4 ) V4 (X1 , X2 , X4 )

V3 (X2 , X3 , X4 ) V4 (X2 , X3 , X4 )

V3 (X3 , X4 , X1 )

V2 (X1 , X2 , X3 , X4 ) R1 (X1 , X2 ) R4 (X4 , X1 )

V2 (X1 , X2 , X3 , X4 ) R2 (X2 , X3 ) R3 (X3 , X4 )

V6 (X1 , X3 ) V4 (X1 , X3 ) R5 (X1 , X3 ) V2 (X1 , X3 )

V1 (X2 , X3 , X4 ) R5 (X1 , X3 )

V1 (X1 , X2 , X3 ) R3 (X3 , X4 ) R4 (X4 , X1 )

R2 (X2 , X3 ) R3 (X3 , X4 )

R1 (X1 , X2 ) R2 (X2 , X3 )

V1 (X1 , X2 , X4 ) R5 (X1 , X3 ) R1 (X1 , X2 ) R4 (X4 , X1 )

View Tree 2

View Tree 1

View Tree 3

V6 (X1 , X4 )

V6 (X3 , X4 )

V6 (X2 , X3 )

V6 (X1 , X2 )

V5 (X1 , X4 ) R4 (X4 , X1 )

V5 (X3 , X4 ) R3 (X3 , X4 )

V5 (X2 , X3 ) R2 (X2 , X3 )

V5 (X1 , X2 ) R1 (X1 , X2 )

V4 (X1 , X2 , X4 ) V3 (X1 , X2 , X4 )

V4 (X1 , X3 , X4 ) R1 (X1 , X2 )

V2 (X1 , X2 , X3 , X4 )

V4 (X1 , X2 , X3 )

V3 (X1 , X3 ) R4 (X4 , X1 )

V3 (X1 , X3 ) R1 (X1 , X2 )

V3 (X1 , X3 ) R2 (X2 , X3 )

V2 (X1 , X3 ) R5 (X1 , X3 )

V2 (X3 , X1 ) R5 (X1 , X3 )

V1 (X2 , X3 , X4 )

R5 (X1 , X3 )

V1 (X1 , X2 , X3 )

R2 (X2 , X3 )

R3 (X3 , X4 )

R1 (X1 , X2 )

View Tree 4

V1 (X3 , X4 , X1 )

R2 (X2 , X3 )

View Tree 5

V1 (X3 , X4 , X1 )

R3 (X3 , X4 ) R4 (X4 , X1 )

View Tree 6

View Tree 7

Figure 9: The seven view trees used to maintain the diamond query. for ϵ = 1/3. By Theorem 11, the update time of Q is O(N 2/3 ). The update time cannot be improved by a polynomial factor, conditional on the conjectured optimality of the submodular width for static query evaluation [1].

A.7

Paw Query

Consider the paw query Q (X1 , X2 , X3 , X4 ) = R1 (X1 , X2 ) · R2 (X2 , X3 ) · R3 (X3 , X1 ) · R4 (X3 , X4 ) which is the triangle query with an additional edge to a new vertex, shown in Fig. 6. Q can be maintained using the three view trees shown in Fig. 10. Table 8 shows for each degree configuration, the view tree used for maintenance and the corresponding update time. The maintenance width mw(Q ) is then the minimum over all expressions in the table for the base N logarithm of the update time. This width can be computed as the minimization of optimal solutions of linear programs. mw(Q ) = min max(ϵ, 1 − ϵ, min(ϵ, 1 − ϵ), min(2ϵ, 2 − 2ϵ)), ϵ

= min max(ϵ, 1 − ϵ, min(2ϵ, 2 − 2ϵ)) ϵ

∗

= min min(max(ϵ, 1 − ϵ, 2ϵ), max(ϵ, 1 − ϵ, 2 − 2ϵ)) ϵ

= min(min max(ϵ, 1 − ϵ, 2ϵ) s.t. 0 ≤ ϵ ≤ 1, ϵ

min max(ϵ, 1 − ϵ, 2 − 2ϵ) s.t. 0 ≤ ϵ ≤ 1) ϵ

Configuration (X1 , X2 , X3 , X4 ) L, L, ∗, L L, L, L, H L, L, H, H L, H, L, L L, H, L, H L, H, H, L L, H, H, H

View Tree 1 4 5 6 3 6 3

Configuration (X1 , X2 , X3 , X4 ) H, L, L, L H, L, L, H H, L, H, L H, L, H, H H, H, L, L H, H, L, H H, H, H, ∗

logN UpdateTime ϵ 2ϵ f (ϵ) 2ϵ f (ϵ) f (ϵ) g(ϵ)

View Tree 1 4 1 1 7 2 1

logN UpdateTime ϵ f (ϵ) min(ϵ, 1 − ϵ) 1−ϵ f (ϵ) g(ϵ) 1−ϵ

Table 7: The (base N ) logarithm of the update time for each degree configuration and a specific view tree from Fig. 9. Note that f (ϵ) = max(min(2ϵ, 2 − 2ϵ), min(2ϵ, 1)); g(ϵ) = max(1 − ϵ, min(2ϵ, 2 − 2ϵ)); (∗) in the degree configuration indicates that the join variable can be either heavy or light. V6 (X3 ) V4 (X3 )

V6 (X3 ) V5 (X3 )

V4 (X3 )

V5 (X3 )

V3 (X1 , X3 ) R4 (X3 , X4 )

V3 (X2 , X3 ) R4 (X3 , X4 )

V2 (X1 , X3 ) R3 (X3 , X1 )

V2 (X2 , X3 ) R2 (X2 , X3 )

V1 (X1 , X2 , X3 )

V5 (X1 , X3 ) V4 (X1 , X2 ) R1 (X1 , X2 ) V3 (X1 , X2 , X3 )

V1 (X1 , X2 , X3 )

R1 (X1 , X2 ) R2 (X2 , X3 )

R1 (X1 , X2 )

View Tree 1

R3 (X3 , X1 )

V1 (X1 , X2 , X3 ) V2 (X3 ) R2 (X2 , X3 ) R3 (X3 , X1 ) R4 (X3 , X4 )

View Tree 2

View Tree 3

Figure 10: The three view trees used to maintain the paw query. optimization problems, which can be encoded as linear programs. The optimal solution is 2/3 and obtained for ϵ = 1/3. By Theorem 11, the update time of Q is O(N 2/3 ). The update time cannot be improved by a polynomial factor, conditioned on the conjectured optimality of the submodular width for static query evaluation [1].

A.8

Big Paw Query

Consider the big paw query Q (X1 , X2 , X3 , X4 , X5 ) = R1 (X1 , X2 ) · R2 (X2 , X3 ) · R3 (X3 , X1 ) · R4 (X1 , X4 ) · R5 (X2 , X5 ) which is the triangle query with two additional edges, each to a new vertex, shown in Fig. 6. Q can be maintained using the three view trees shown in Fig. 11. Table 9 shows for each degree configuration, the view tree used for maintenance and the corresponding update time. The maintenance width mw(Q ) is then the minimum over all expressions in the table for the base N logarithm of the update time. This width can be computed as the minimization of optimal solutions of linear programs. mw(Q ) = min max(2ϵ, 1 − ϵ, min(2ϵ, 1), min(2ϵ, 2 − 2ϵ)), ϵ

∗

= min min(max(2ϵ, 1 − ϵ, 2ϵ, 2ϵ), max(2ϵ, 1 − ϵ, 2ϵ, 2 − 2ϵ) ϵ

max(2ϵ, 1 − ϵ, 1, 2ϵ), max(2ϵ, 1 − ϵ, 1, 2 − 2ϵ)) +

= min(min max(2ϵ, 1 − ϵ) s.t. 0 ≤ ϵ ≤ 1, ϵ

min max(2ϵ, 1 − ϵ, 2 − 2ϵ) s.t. 0 ≤ ϵ ≤ 1, ϵ

Configuration (X1 , X2 , X3 ) L, L, ∗ L, H, L L, H, H

View Tree 1 2 2

Configuration (X1 , X2 , X3 ) H, L, L H, L, H H, H, L H, H, H

logN UpdateTime ϵ ϵ min(ϵ, 1 − ϵ)

View Tree 1 1 3 1

logN UpdateTime ϵ min(ϵ, 1 − ϵ) min(2ϵ, 2 − 2ϵ) 1−ϵ

Table 8: The (base N ) logarithm of the update time for each degree configuration and a specific view tree from Fig. 10. (∗) in the degree configuration indicates that the join variable can be either heavy or light. V8 (X2 )

V8 (X1 )

V6 (X2 )

V7 (X2 )

V6 (X1 )

V7 (X1 )

V5 (X2 , X3 ) R5 (X2 , X5 )

V5 (X1 , X3 ) R4 (X1 , X5 )

V4 (X2 , X3 ) R2 (X2 , X3 )

V4 (X1 , X3 ) R3 (X3 , X1 )

V3 (X1 , X2 , X3 )

V2 (X1 , X2 ) R3 (X3 , X1 ) R1 (X1 , X2 )

V1 (X1 ) R4 (X1 , X4 )

View Tree 1

V8 (X2 )

V9 (X2 )

V7 (X1 , X2 ) R5 (X2 , X5 ) V5 (X1 )

V2 (X2 , X3 ) R1 (X1 , X2 ) R2 (X2 , X3 )

V10 (X2 )

V6 (X1 , X2 )

R4 (X1 , X4 ) V4 (X1 , X2 ) R1 (X1 , X2 )

V1 (X2 )

V1 (X1 , X2 , X3 )

R5 (X2 , X5 )

R2 (X2 , X3 ) R3 (X3 , X1 )

View Tree 2

View Tree 3

Figure 11: The three view trees used to maintain the big paw query. min max(2ϵ, 1 − ϵ, 1, 2ϵ) s.t. 0 ≤ ϵ ≤ 1, ϵ

min max(2ϵ, 1 − ϵ, 1, 2 − 2ϵ) s.t. 0 ≤ ϵ ≤ 1) ϵ

The equality (*) holds due to the distributivity of max over min, while the equality (+) is due to the commutativity of the two min functions. We then have to take the minimum of the optimal solutions of four optimization problems, which can be encoded as linear programs. The optimal solution is 2/3 and obtained for ϵ = 1/3. By Theorem 11, the update time of Q is O(N 2/3 ). The update time cannot be improved by a polynomial factor, conditioned on the conjectured optimality of the submodular width for static query evaluation [1].

Proof of Theorem 11

In this section we prove: Theorem 11. Any join query Q can be maintained with O(N 1+mw(Q) ) preprocessing time, amortized O(N mw(Q) ) single-tuple update time, and O(1) enumeration delay, where N is the size of the database at the time of update and mw(Q) is the maintenance width of Q. Given a join query Q, we analyze the time complexity of each of the three stages of our algorithm: preprocessing, maintenance, and enumeration. Preprocessing. We compute the maintenance width mw(Q) and the optimal parameter ϵ∗ as detailed in Sec. 4.4. Next, we partition the active domain into heavy and light values based on the thresholds defined by

Configuration (X1 , X2 , X3 ) L, L, L L, L, H L, H, L L, H, H

View Tree 1 1 1 1

Configuration (X1 , X2 , X3 ) H, L, L H, L, H H, H, ∗

logN UpdateTime 2ϵ min(2ϵ, 1) min(2ϵ, 1) min(2ϵ, 2 − 2ϵ)

View Tree 2 2 3

logN UpdateTime min(2ϵ, 1) min(2ϵ, 2 − 2ϵ) 1−ϵ

Table 9: The (base N ) logarithm of the update time for each degree configuration and a specific view tree from Fig. 10. (∗) in the degree configuration indicates that the join variable can be either heavy or light. ϵ∗ . We then compute the set of active view trees and assign the optimal tree T d to each degree configuration d. To compute the views of our active view trees, we start with an empty database and then insert one by one each tuple from the initial database of size N . Since the time to process a single update is O(N mw(Q) ), the overall time to compute the views is O(N 1+mw(Q) )). The number of views is only dependent on the query, so independent of the database size. Maintenance. steps:

Consider a single tuple update δR = {t 7→ ±1}. The maintenance procedure follows two

1. Selecting the configuration and delta view tree: We inspect the values in the tuple t. If a value a in t is encountered for the first (i.e., it is not in the active domain), we initialize it as a light value. Otherwise, we use its degree in the data to decide whether it is heavy or light. We then determine the degree configuration d corresponding to the degrees of values in t based on the current heavy-light threshold and select the corresponding view tree T d . 2. View Updates: We compute δTRd for the update δR. By Lemma 17 and the definition of the maintenance width, the cost of this operation is bounded by O(N mw(Q) ) time in data complexity. We the use the computed δTRd to update the view tree T d . This bound on update time holds strictly when the degree constraints for d remain satisfied. However, a sequence of updates may alter value frequencies, violating the constraints. In such cases, a minor or major rebalancing step is triggered. As detailed in Sec. 6, the cost of these rebalancing steps can be amortized over the update sequence, yielding the same (now amortized) update time. Enumeration. Upon each enumeration request, we enumerate the distinct tuples in the query output, along with their multiplicities, from the active view trees with constant delay, as described in Sec. 7.

Missing Details in Section 6

In this section, we give a detailed analysis of the major and minor rebalancing steps explained in Section 6. In the following, we fix a join query Q. Relaxing the Partition Threshold We relax the partition threshold that determines whether a value is classified as light or heavy. The purpose of this relaxation is to prevent sequences of alternating inserts and deletes from causing a value to change between the heavy and light categories after every single update, thereby triggering a rebalancing step after each update. Consider a fixed ϵ ∈ [0, 1]. Given a database of size N , let M ∈ N be chosen such that 41 M ≤ N < M . For any join variable Y , we partition the Y -values in sets Light(Y ) and Heavy(Y ) such that P (1) for all y ∈ Light(Y ), it holds P the database into disjoint 3 1 ϵ ϵ |σ R | ≤ M and (2) for all y ∈ Heavy(Y ), it holds Y =y i Ri (Xi )∈at(Y ) Ri (Xi )∈at(Y ) |σY =y Ri | > 2 M . It 2P follows that a Y -value with Ri (Xi )∈at(Y ) |σY =y Ri | = M ϵ can be either in Light(Y ) or in Heavy(Y ), but it cannot be in both. Since N = Θ(M ), all degree constraints stated after Definition 4 in Section 2 are 34

satisfied in asymptotic terms: each atom Ri (X i ) with join variable A ∈ X i guards the degree constraints (X i | ∅, N ); (X i | A, O(N ϵ )) in case A is light; and (A | ∅, O(N 1−ϵ )) in case A is heavy. A single-tuple update δRi implies the degree constraints (Y | ∅, 1) for all Y ∈ X i . Database States A database state is a triple S = (M, P, F , T ), where: M is the threshold base with 1 4 M ≤ N < M with N being the current database size; P consists of the value sets Heavy(Y ) and Light(Y ) for each join variable Y ; F consists of the database fragments, i.e., it contains for each degree configuration, a corresponding database; and and T consists of set of view trees maintained by our approach. In the initial database state, i.e, before processing any update, the threshold base M is set to 2N + 1. Major Rebalancing If an update causes the database size to drop below ⌊ 14 M ⌋, we set M := ⌊ 12 M ⌋ − 1. If, on the other hand, the update causes the database size to reach M , we set M := 2M . In either case, we recompute the value partitions in P, the database fragments in F , and the view trees in T , using the partition threshold M ε . We refer to this step as major rebalancing. The time required to compute P and F is O(N ). The time needed to compute the view trees in T is given by the preprocessing time O(N 1+mw(Q) ), as stated in Theorem 11. After a major rebalancing step, the database size satisfies N = 12 M (after doubling), or N = 12 M − 12 or |N | = 12 M − 1 (after halving). To violate the size invariant ⌊ 41 M ⌋ ≤ N < M and trigger another major rebalancing step, at least 14 M = Ω(M ) updates are needed. By amortizing the O(N 1+mw(Q) N ) cost of a major rebalancing step over these preceding Ω(M ) updates and observing that N = Θ(M ), we obtain that the amortized cost of major rebalancing per single-tuple update is O(N mw(Q) ). Minor Rebalancing After each single-tuple update δR = {x 7→ m}, we check for each X-value x in x whether it needs to be moved from P Light(X) to Heavy(X) or vice-versa. Assume that before the update, we have x ∈ Light(X) and Ri (Xi )∈at(X) |σX=x Ri | = ⌊ 23 M ε ⌋. Assume that after update, we obtain P 3 ε Ri (Xi )∈at(X) |σX=x Ri | = ⌊ 2 M ⌋ + 1. In this case, we move x from Light(X) to Heavy(X) and move all tuples that contain the value x and are in a database fragment corresponding to a degree configuration where X is light to the fragment where X is heavy. Additionally, we update the view trees in T evaluated over the two database fragments that have been changed. If the X-value moves from Heavy(X) to Light(X), the computation is analogous. We refer to this step as minor rebalancing. If the value x moves from Heavy(X) to Light(X), at most 21 M ε tuples need to be moved between the fragments. If the x moves from Light(X) to Heavy(X), at most 32 M ε + 1 need to be moved between the fragments. Using the update mechanism of our approach to insert and delete tuples from database fragments, we observe that moving a tuple from one fragment to another takes O(N mw(Q) ) time, as stated in Theorem 11. Hence the overall time to do minor rebalancing is O(N mw(Q) M ε ). We amortize this minor rebalancing time over over Ω(M ε ) updates required between two minor rebalancing steps. This implies that the amortized minor rebalancing time per single-tuple update is O(N mw(Q) ).

Missing Details in Section 7

In this section, we prove: Proposition 26. For any join query Q and view tree set T constructed by our approach for Q, it holds that the output of Q can be enumerated from T with constant delay. Before giving the proof of Proposition 26, we illustrate our enumeration strategy for the 4-cycle query: Example 27. Consider the view trees in Fig. 1 used to maintain the 4-cycle query. We illustrate how the tuples in the join of the views in View Trees 1 and 3 can be enumerated from these view trees with constant delay. Our enumeration strategy works for any degree configuration. The enumeration strategy for the other view trees is analogous. In View Tree 1, we use the view V5 to retrieve distinct (A, C)-values and the views V1 and V2 to retrieve distinct B- and respectively D-values. To construct the first output tuple, we retrieve one (A, C)-value (a, c) from V5 , one B-value b from V1 (a, B, c), and one D-value d from V2 (c, D, a). Afterwards, we report the tuple (a, b, c, d). Then, we iterate over the remaining D-values in V2 (c, D, a) and report for each such value d′ , the 35

Enumerate (view tree T ) 1 2 3 4 5 6 7 8 9 10 11 12

let V be the set of views in T that own at least one variable in T let V1 (X 1 ), . . . , Vn (X n ) be an ordering of the views in V that is consistent with T let O i be the variables owned by Vi and let N i = X i \ O i , for i ∈ [n] foreach t1 ∈ V1 (O 1 ) let t′1 = πN 2 t1 foreach t2 ∈ V2 (t′1 , O 2 ) let t′2 = πN 3 (t1 · t2 ) foreach t3 ∈ V2 (t′2 , O 3 ) ··· let t′n−1 = πN n (t1 · · · tn−1 ) foreach tn ∈ Vn (t′n−1 , O n ) report t1 ···tn

Figure 12: Constant-delay enumeration of the tuples in the join of the relations at the leaves of a view tree. tuple (a, b, c, d′ ). After all values in V2 (c, D, a) are exhausted, we retrieve the next B-value b′ in V1 (a, B, c) and then iterate again over all D-values in V2 (c, D, a). For each such value d, we report the tuple (a, c, b′ , d). After the view V1 is exhausted, we retrieve the next (A, C)-value (a′ , c′ ) in V5 and repeat the enumeration process in the context of (a′ , c′ ). We are done, when the enumeration is completed in the context of the last (A, C)-value in V5 . In View Tree 3, we use the view V5 to retrieve distinct (A, D)-values, and the views V3 and V1 to retrieve distinct C- and respectively B-values. The enumeration is analogous to the case of View Tree 1. We denote by vars(T ) the set of variables in a view tree T . Given a view tree T and a view V (X) in T , we say that the view V owns a variable X ∈ vars(T ) if X ∈ X and each view or atom V ′ (X ′ ) with X ∈ X ′ appears in the subtree rooted at V . It follows from the construction of view trees that each variable is owned by a unique view: Proposition 28. For any view tree T and variable X ∈ vars(T ), it holds that T contains a unique view that owns X. Proof. We say that two views in a view tree are independent if they do not appear on a root-to-leaf path in the view tree. Consider a view tree T and a variable X ∈ vars(T ). For the sake of contradiction, assume that T does not contain a unique view owning X. This means that T has two independent views V1 (X1 ) and V2 (X2 ) such that (i) X ∈ X 1 , (ii) X ∈ X 2 , (iii) for any view V1′ (X ′1 ) above V1 (X 1 ), it holds X ∈ / X ′1 , and (iv) for ′ ′ ′ any view V2 (X 2 ) above V2 (X 2 ), it holds X ∈ / X 2 . This implies that the parent view V̂1 (X̂1 ) of V1 (X 1 ) is a projection view that projects away X, which means X ∈ / X̂ 1 . The definition of view trees requires that V2 must be in the subtree rooted at V1 (Definition 1). This means that V1 and V2 cannot be independent, which is a contradiction. Equipped with Proposition 28, we are ready to prove Proposition 26. Proof of Proposition 26. As explained at the beginning of Section 7, it suffices to show that for any view tree T , the set of tuples in the join of the views of T can be enumerated with constant delay. The procedure Enumerate in Fig. 12 describes our enumeration strategy for any given view tree. First, we explain the details of the procedure. Then, we show its correctness, i.e., we explain why it enumerates all distinct tuples represented by the view tree. Finally, we show that it enumerates with constant delay.

Enumeration Procedure Let V be the set of views in the input view tree T that own at least one variable in T . For each i ∈ [n], let O i be the variables owned by Vi and let N i = X i \ O i . The procedure Enumerate creates a strict ordering V1 (X1 ), . . . , Vn (Xn ) of the views in V that is consistent with the partial ordering given by T (Line 2), i.e., for any i, j ∈ [n] it holds: if Vj is on the path from Vi to the root of T , then i < j. The procedure constructs the first value tuple over vars(T ) by traversing the views in the strict order as follows (Lines 4–11). All variables in X1 must be owned by V1 , hence, X 1 = O 1 . The procedure retrieves a tuple t1 over O 1 from V1 . For any i ∈ {2, . . . , n} it proceeds as follows. Let ti−1 be the tuple constructed before visiting the view Vi and let t′i−1 = πN i ti−1 . The procedure retrieves a tuple ti from Vi (t′i−1 , O i ). After all views in V are visited, we have a complete tuple t = t1 · · · tn , which is reported by the procedure. Then, the procedure iterates over the remaining tuples in Vn (t′n−1 , O n ) and outputs for each such tuple t̂n , the tuple t = t1 · · · tn−1 · t̂n . After all tuples in Vn are exhausted, the procedure backtracks, i.e., it retrieves the next tuple in Vn1 and iterates again over the tuples in Vn . The procedure stops after each view in V is exhausted. Correctness The correctness of the enumeration procedure follows from two observations. Firstly, the values of any variable X are retrieved from the view that owns X, which by Proposition 28 is unique. This means that the values are retrieved from a view that joins all views containing X. Secondly, it follows from Proposition 28 that for each view Vi (X i ), it holds: all variables in N i have their owning views above Vi in the view tree. This means that at the time, the procedure visits the view Vi , all variables in N i are already fixed to some constant, which guarantees that all tuples in Vi (t′i−1 , O i ) are distinct. Time analysis The view tree contains constantly many views (in data complexity). For any view Vi and any tuple t over O i , our computation model allows for the constant-delay enumeration of the distinct tuples in Vi (t′i−1 , O i ). This implies that the procedure Enumerate constructs each output tuple in constant time. We conclude this section by showing how our approach can be easily adapted to maintain the query count, i.e., the number of tuples in the query output, with the same update time and constant-delay enumeration as for full queries. Maintaining the Query Count Given a join query Q, consider the view tree Td with root view Vd (X d ) constructed for each degree configuration d ∈ D(Q). We extend each such a view tree with a projection view V̂d () that marginalizes our all variables of Vd . For any single-tuple update, the maintenance time for V̂d is upper-bounded by the maintenance time for Vd . Note that V̂d is a constant function that returns P the number of tuples in the join of the views in Td . Hence, the number of output tuples of the query is d∈D(Q) V̂d (), which can be computed in constant time.

Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations

Related documents