We consider the problem of maintaining the result of the triangle count query Q( ) = ;sum R(A; B) on S(B; C) on T (C; A) under single-tuple updates to the input relations R, S, and T . The relations are given as key-payload maps whose keys are tuples over relation schemas, payloads are tuple multiplicities, and key lookups are (amortized) O(1)-time operations. A single-tuple update R(a; b) = f (a; b) 7! p g to relation R maps a key (a; b) to a nonzero payload p (positive for inserts and negative for deletes); updates to S and T are analogous. The nave maintenance approach recomputes the triangle count from scratch after each update. Computing this query using worst-case optimal join algorithms [5] takes O(N 1:5) time, where N is the current size of the input database. To incrementally maintain the triangle count under single-tuple updates, existing incremental view maintenance (IVM) approaches need linear time. For instance, under the update R to R, the classical IVM [2] computes the delta query ;sum R(a; b) on S(b; C) on T (C; a) in O(N ) time because it needs to intersect two lists of possibly linearly many C-values that are paired with b in S and with a in T . The factorized IVM [6] materializes the view VST (B; A) = B;A;sum S(B; C) on T (C; A) using O(N 2) space. It then computes the delta query ;sum R(a; b) on VST (b; a) in O(1) time; however, updates to S and T still require O(N ) time to maintain the triangle count Q and view VST . This raises the question of whether the triangle count can be maintained in sublinear time. Recent work proves that no algorithm can maintain Q in time O(N 0:5 ) for any > 0, under reasonable complexity-theoretic assumptions [1]. An algorithm with sublinear maintenance time for Q is not yet known. This work introduces IVM , an IVM approach that maintains the triangle count in amortized sublinear time. IVM partitions each input relation into two parts, heavy and light, based on the degrees of data values, the database size, and a parameter . It then adapts the maintenance strategy to di erent heavy-light combinations of parts of the input relations to achieve worst-case sublinear maintenance. As the database evolves under updates, IVM rebalances the partitions to account for a new database size and updated degrees of data values. While this rebalancing may take superlinear time, it remains sublinear per update. Given a database of size N and 2 [0; 1], IVM maintains the triangle count in O(N maxf ;1 g) amortized time while using O(N 1+minf ;1 g) space. It thus de nes a continuum of approaches exhibiting a space-time tradeo based on .
? An extended version of this work is available online [3].
Materialized View De nition
Q( ) = Su;v;w2fh;lg ;sum Ru(A; B) no Sv(B; C) no Tw(C; A)
VRS(A; C) = A;C;sum Rh(A; B) no Sl(B; C)
VST (B; A) = B;A;sum Sh(B; C) no Tl(C; A)
VT R(C; B) = C;B;sum Th(C; A) no Rl(A; B)
O(
Setting = 0:5 gives O(N 0:5) amortized worst-case optimal time and O(N 1:5) space utilization. Existing IVM approaches are extreme points in this continuum of approaches de ned by IVM . For instance, to recover classical IVM, we set 2 f0; 1g to achieve O(N ) update time and O(N ) space utilization; to recover factorized IVM, we set distinct parameters for each relation (cf. [3] for details). IVM can also count all triangles in a static database in worst-case optimal time O(N 1:5) by inserting N tuples, one at a time, into initially empty relations. 2
We split each input relation into two disjoint parts, called heavy and light parts. Given R 2 [0; 1], an A-value a is heavy in R if j A=aRj N R , where N is the database size; otherwise, it is light. We partition R into Rh and Rl such that Rh = f t 2 R j t:A is heavy g and Rl = R n Rh; similarly, we partition S on B, and T on C. In the following, we assume that = R = S = T is xed.
We decompose the query Q into skew-aware views expressed over the relation parts: Quvw( ) = ;sum Ru(A; B) on Sv(B; C) on Tw(C; A), where u; v; w 2 fh; lg. The query Q is thus a union (sum) of partial counts: Q( ) = Su;v;w2fh;lg Quvw( ).
We adapt the maintenance strategy to each skew-aware view to ensure sublinear update time. While most of these views admit sublinear delta computation, few exceptions require linear-time maintenance. For these exceptions, IVM precomputes the update-independent parts of delta queries as materialized views and uses them to speed up the delta evaluation. Such auxiliary views also require maintenance, yet their maintenance cost is sublinear for single-tuple updates.
Figure 1 shows the materialized views used by IVM to maintain the triangle count query. The size of the view VRS (A; C) is upper-bounded by the size of the result of the join of Rh(A; B) and Sl(B; C) in two distinct ways. One can iterate over all (a; b) pairs in Rh and then nd the C-values in Sl for each b. Since Sl contains only tuples with light B-values, there are at most N distinct Cvalues for each B-value. This gives an upper bound of O(jRhj N ) = O(N 1+ ). Alternatively, one can iterate over all (b; c) pairs in Sl and then nd the Avalues in Rh for each b. Since Rh contains only tuples with heavy A-values, there are at most NN = N 1 distinct A-values. This gives an upper bound of O(jSlj N 1 ) = O(N 2 ). The overall space complexity is the minimum of the bounds. The space analysis for VST and VT R is analogous.
We explain our adaptive strategy on a single-tuple update R (a; b) to relation R. This update can a ect either the heavy or light part of R, hence the Delta Evaluation Strategy Q hh( ) = R (a; b) PC Th(C; a) Sh(b; C) Q hl( ) = R (a; b) VST (b; a) Q lh( ) = R (a; b) PC Th(C; a) Sl(b; C) or
= R (a; b) PC Sl(b; C) Th(C; a)
Q ll( ) = R (a; b) PC Sl(b; C) Tl(C; a)
Q( ) = Q hh( ) + Q hl( ) + Q lh( ) + Q ll( )
VRS(a; C) = Rh(a; b) Sl(b; C)
VT R(C; b) = Rl(a; b) Th(C; a)
O(N min f ;1 g)
O(N 1 )
O(
Figure 2 shows the deltas of the views a ected by the update R (a; b) and their time complexity when evaluated from left to right. In all but one case, the complexity is determined by the number of C-values that need to be iterated over. Computing the deltas involves multiplying the payloads of matching tuples and, if C is not in the target view schema, summing them over C-values.
We rst analyze the access patterns of the skew-aware delta views: (
An insert (a; b) into R may promote a from light to heavy in R or may increase the heavy-light threshold such that some A-values change from heavy to light. Without rebalancing the partitions, our assumptions on the number of B-values paired with a or the number of heavy A-values may become invalid.
IVM loosens the partition threshold to amortize the cost of rebalancing over multiple updates. Instead of the actual database size N , the threshold now depends on a variable M for which the invariant b 41 M c N < M always holds. If the database size violates one of the limits, we perform major rebalancing where we double or halve M to satisfy the invariant again, repartition the input relations using the new threshold M , and recompute the auxiliary views. The time complexity of this operation is O(M 1+minf ;1 g), which is amortized over at least d 41 M e updates between two major rebalancing steps.
IVM also enforces the following two invariants: The number of tuples with the same value of the partitioning attribute is less than 32 M in each light part and at least 12 M in each heavy part. If any of the two invariants is violated, we perform minor rebalancing where we move at most d 32 M e tuples from one part to another and update the a ected views. The time complexity of this operation is O(M +maxf ;1 g), which is amortized over at least d 21 M e updates between two minor rebalancing steps for the same value of the partitioning attribute.
In conclusion, both rebalancing steps together take O(M maxf ;1 g) amortized time. Since each single-tuple update can be realized in time O(M maxf ;1 g) and M = O(N ), IVM needs O(N maxf ;1 g) overall amortized time. The extended version of this work presents a detailed complexity analysis of IVM [3]. 3
IVM can be applied to any query but may not always yield asymptotic improvements over existing approaches. It can achieve sublinear maintenance for the counting variants of acyclic queries, e.g., 3-path and 4-path, and cyclic queries, e.g., Loomis-Whitney and 4-cycle. Di erent semirings can be used to speci y operations on the payloads [6]; we used here (Z; +; ; 0; 1) to express counting. An early prototype implementation of IVM on top of DBToaster [4] shows several factors performance improvement over classical and factorized IVM. Acknowledgments. This project has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 682588. The rst author acknowledges funding from Fondation Wiener Anspach.