Tractable Conjunctive Queries over Static and Dynamic Relations
Ahmet Kara Zheng Luo Milos Nikolic Dan Olteanu Haozhe Zhang

[
    Anupam Das Abhishek De
    April 29, 2024
==========================





We investigate the evaluation of conjunctive queries over static and dynamic relations. While static relations are given as input and do not change, dynamic relations are subject to inserts and deletes.

We characterise syntactically three classes of queries 
that admit constant update time and constant enumeration delay. 
We call such queries tractable. Depending on the class, the preprocessing time is linear, polynomial, or exponential (under data complexity, so the query size is constant).

To decide whether a query is tractable, it does not suffice to analyse separately the sub-query over the static relations and the sub-query over the dynamic relations. Instead, we need to take the interaction between the static and the dynamic relations into account. Even when the sub-query over the dynamic relations is not tractable, the overall query can become tractable if the dynamic relations are sufficiently constrained by the static ones.   





  
Acknowledgements.
The authors would like to acknowledge the UZH Global Strategy and Partnerships Funding Scheme and EPSRC grant EP/T022124/1.



§ INTRODUCTION


Incremental view maintenance, also known as fully dynamic query evaluation, is a fundamental task in data management, e.g., <cit.>.
A natural question is to understand which queries are tractable, i.e., which queries admit constant time per single-tuple update (insert or delete) and also constant delay for the enumeration of the result tuples. The problem setting also allows for some one-off preprocessing phase to construct a data structure that supports the updates and the enumeration.
Prior work <cit.> showed that the q-hierarchical queries are the conjunctive queries that are tractable; this already holds even if we only allow for linear time preprocessing. All other queries cannot admit both constant update time and constant enumeration delay, even when we allow arbitrary time for preprocessing. If we only allow inserts (and no deletes), then every free-connex α-acyclic conjunctive query becomes tractable <cit.>.
The tractable queries with free access patterns, where the free variables are partitioned into input and output, naturally extend the  q-hierarchical queries, which are queries without input variables <cit.>. Further works investigated classes of intractable queries for which the update time and enumeration delay are shown to be not constant yet worst-case optimal, e.g., triangle queries <cit.> and hierarchical queries with arbitrary free variables <cit.>.
Further works consider restrictions to the data or to the update sequence: Intractable queries become tractable when the update sequence has a small enclosureness parameter <cit.> or when the database satisfies functional dependencies <cit.>, bounded degrees <cit.>, or more general integrity constraints <cit.>.

All aforementioned works consider the all-dynamic setting, where all relations are updateable. In this work, we extend the tractability frontier by considering a mixed setting, where the input database can have both dynamic relations, which are subject to change, and static relations, which do not change. The mixed setting appears naturally in real-world applications at RelationalAI (personal communication). For instance, in the retailer domain, the Inventory and Sales relations are updated very frequently, whereas the Stores and Demographics relations are updated very infrequently and can be considered static for a large time period. We show that by differentiating between static and dynamic relations, we can design efficient query maintenance strategies tailored to the mixed setting.





 §.§ Main Contributions


We characterise syntactically three classes of tractable conjunctive queries depending on their preprocessing time, cf. Figure <ref>: ⊂⊂. These classes are defined in Section <ref>.

The class  defines the tractable queries with linear time preprocessing: 



    Let a CQ Q and a database of size N. 


  * If Q is in , then it can be evaluated with N preprocessing time,
1 update time, and 1 enumeration delay. 


  * If Q is not in  and has no self-joins, then 
it cannot be evaluated with  N preprocessing time, 1
update time, and 1 enumeration delay, 
unless the Online Matrix-Vector Multiplication or the Boolean Matrix-Matrix Multiplication conjecture fail.  



  * If Q is not in  and has no self-joins, then there is no γ > 0 such that Q can be evaluated with N^3/2-γ preprocessing time, N^1/2-γ
update time, and N^1/2-γ enumeration delay, 
unless the Online Matrix-Vector Multiplication or the Boolean Matrix-Matrix Multiplication conjecture fail.  




The upper bound in Theorem <ref> relies on a rewriting of a given query using multiple strata of views, where the views are defined by projecting or joining input relations or other views (Section <ref>). We call such rewritings safe if the views can be maintained in constant time under single-tuple updates to the input relations and support constant-delay enumeration of the query result. We show that every  query has a safe rewriting and the views can be computed in linear time (Section <ref>).
The lower bound in Theorem <ref> relies on two widely used conjectures: the Online Matrix-Vector Multiplication <cit.> and the Boolean Matrix-Matrix Multiplication <cit.>. The proof of the lower bound is outlined in Section <ref>. 





Let the query Q_1(A,B,C) = R^d(A,D), S^d(A,B), T^s(B,C) 
in Figure <ref>. The dynamic relations R and S are adorned with the superscript d, while the static relation T is adorned with s. The query is not tractable in the all-dynamic setting (as it is not q-hierarchical, cf. Section <ref>), yet it is in  , so it is tractable and uses linear time preprocessing. 


In the all-static setting,  becomes the class of free-connex α-acyclic queries, which are those conjunctive queries that admit constant enumeration delay after linear time preprocessing <cit.>. In the all-dynamic setting,  becomes the class of q-hierarchical queries, which are those conjunctive queries that admit constant enumeration delay and constant update time after linear time preprocessing. Every query  in  is free-connex α-acyclic and its dynamic sub-query, which is obtained by removing the static relations, is q-hierarchical. Yet the queries in   need to satisfy further syntactic constraints on the connections between their static and dynamic relations: For instance, Q_3 and Q_4 from Figure <ref> are not in  even though they are free-connex α-acyclic and their dynamic sub-queries are q-hierarchical.

Queries in ∖ are tractable but require super-linear time preprocessing that depends on a new width measure , which we call the preprocessing width of the query:



    Every query in   can be evaluated with N^ preprocessing time, 1 update time,
    and 1 enumeration delay, where N is the database size and
     is the preprocessing width of the query. 


Like the queries in , every query in  also admits a safe rewriting (Section <ref>). 


The query Q_2(A,C,D) = R^d(A,D), S^s(A,B), T^s(B,C), U^d(D) from Figure <ref> is contained in ∖: It is tractable but requires quadratic time preprocessing. The quadratic blowup is due to the creation of a view that joins the static relations S and T  on the bound variable B.


The preprocessing width is not captured by previous width notions, such as the fractional hypertree width (fhtw) of the static sub-query or of the entire query <cit.>. Let us take the free-connex α-acyclic query Q_7(A,B,C) = R^s(A,B), S^s(B,C), T^s(A,C), U^d(A,B,C), whose fhtw is 1. For its static sub-query, which is the triangle join, fhtw is 3/2. The preprocessing width is 1, so Q_7 is in . The triangle join Q_8(A,C) = R^s(A,B), S^s(B,C), T^d(A,C) has fhtw =3/2 and its static sub-query has fhtw =2. The preprocessing width is 2: We need to materialize the view V^s(A,C) = R^s(A,B), S^s(B,C), which is the static sub-query. We may reduce the preprocessing width to 3/2 for the static sub-query by also joining with the dynamic relation T^d(A,C), yet the modified view becomes dynamic and needs to be maintained under updates to T. However, this maintenance cannot be achieved with constant update time, while allowing for constant enumeration delay <cit.>.


The class  characterises tractable queries that can use exponential time preprocessing:



 Every query in   can be evaluated with 2^p· p^2 time preprocessing, 1 update time, and 1 enumeration delay, where N is the database size, p = N^ρ^*((Q)), (Q) is the static sub-query of Q, and ρ^* is the fractional edge cover number.



    Let a CQ Q and a database of size N. 

  * If Q is in , then it can be evaluated with 2^p time preprocessing, 
1 update time, and 1 enumeration delay, where p = N^ρ^*((Q)) and ρ^*((Q)) is the fractional edge cover number of the static sub-query (Q).


  * If Q is not in  and has no self-joins,  then there is no γ > 0 such that Q can be evaluated with arbitrary preprocessing time, N^1/2-γ update time, and N^1/2-γ enumeration delay, unless the Online Matrix-Vector Multiplication conjecture fails. 



The class  is merely of theoretical interest since it comes with  preprocessing time that is exponential in the size of the input database. The reason for this high preprocessing time is to ensure constant enumeration delay; if we would allow the enumeration delay to become linear, then the preprocessing time would collapse to linear for the acyclic queries in . 
We use the fractional edge cover number as it characterises the worst-case optimal size of the static sub-query result as a function of the size N of the input relations <cit.>.


The query Q_3(A,B) = R^d(A), S^s(A,B), T^d(B)  from Figure <ref> is in ∖.
The possible results of Q_3 are completely predetermined by its static sub-query: They are the subsets of the materialized static sub-query, while the updates to the dynamic relations only act as selectors in this powerset. Such queries require exponential time preprocessing as there are 2^N many possible subsets of the relation S^s of size N. 
Its dynamic sub-query, i.e., the sub-query over the dynamic relations, is q-hierarchical. Its static sub-query, i.e., the sub-query over the static relation, is trivially free-connex α-acyclic. This means that, when taken in isolation, the dynamic sub-query can be evaluated with constant update time and enumeration delay after linear time preprocessing, while the static sub-query can be evaluated with constant enumeration delay after linear time preprocessing. Yet Q_3 is not in : It does not admit constant update time and enumeration delay after linear time preprocessing.
The queries Q_4, Q_5, and Q_6 from Figure <ref> are not in : Their dynamic sub-queries are not covered by the static sub-queries. They are discussed in Section <ref>.



Queries in ∖ may not admit safe rewritings that rely solely on joins and projections. Take again Q_3(A,B) = R^d(A), S^s(A,B), T^d(B) from Figure <ref>. There is no safe rewriting of this query that solely relies on projections and joins. Any rewriting that supports constant-delay enumeration of the query result must contain a view that either joins: 
(i) R^d and  S^s; 
(ii) S^s and T^d; or
(iii) R^d and  T^d.
None of these views can be maintained with constant update time. Consider the view V(A,B)= R^d(A), S^s(A,B). An insert of a value a to R requires to iterate over all B-values paired with a in S^s in order to propagate the change to the view V. The number of such B-values can be linear, which implies that the update time is linear.
Section <ref> gives our evaluation strategy for queries in .








The class ∖ contains queries where the sub-query over the dynamic 
relations is q-hierarchical and the one over the static relations is 
free-connex acyclic[Free-connex acyclic queries characterise the class of queries that 
admit constant-delay enumeration after linear preprocessing time in the setting where 
all relations are static <cit.>.].  This shows that in order to  obtain tractability, 
we need to take the interaction between the static and the dynamic relations into account. 
The class also  also contains queries where the sub-query over the dynamic relations
not q-hierarchical, hence, not tractable in the all-dynamic setting. 
Even if the sub-query over the dynamic relations is not q-hierarchical, we can still obtain
tractability in the mixed setting in case the variables that make the dynamic sub-query 
not q-hierarchical are covered by static relations. The coverage by static relations constrains the set of possible tuples in dynamic relations that can contribute to the query result and takes the hardness out of the evaluation problem. 







§ PRELIMINARIES


We use ℕ to denote the set of natural numbers including 0.
For n∈ℕ, we define [n] = {1,2,…,n}. In case n=0, we have [n]=∅.




  
*Databases with Static and Dynamic Relations
A schema is a tuple of variables. 
We treat schemas and sets of variables
interchangeably, assuming a fixed ordering of variables.
The domain of a variable X is denoted by  (X). 
A value tuple t over schema X = (X_1, … , X_n)
is an element from ( X) = (X_1) ×⋯×(X_n).

A relation over schema X is a finite set of value tuples over the same schema.  
The size |R| of a relation R  is the number of its tuples. 
The relation R is called dynamic if it is subject to changes;
otherwise, it is called static. 
To emphasize that R is static or dynamic, we write R^s or respectively R^d.  
A database is a finite set of relations. The size of a database is the sum of the sizes of its relations. 





  
*Single-Tuple Updates
We denote an  insert of a tuple t into a dynamic relation R by +R( t) and a delete of t from R by 
-R( t). 
The insert +R( t) inserts t into R if t is not contained in R, and 
the delete -R( t) deletes t from R if it is 
contained in R.
A single-tuple update is either an insert or a delete of a tuple.





  
*Conjunctive Queries
A conjunctive query (CQ) is of the form  

    Q( X) = R_1^d( X_1), … ,R^d_k( X_k),
        S_1^s( Y_1) … , S^s_ℓ( Y_ℓ)

where 
each R_i^d( X_i) is a dynamic atom;
each S_j^s( Y_j) is a static atom;
(Q) = ⋃_i ∈ [k] X_i ∪⋃_j ∈ [ℓ] Y_j is the set of variables of Q;
(Q) =  X ⊆(Q) is the set of free variables, while all others  are bound variables; 
(Q) is the set of all atoms of Q;
(X) is the set of the atoms containing the variable X in their schema.









The static (dynamic) sub-query (Q) ((Q)) is obtained from Q
by omitting all dynamic (static) atoms and their variables.
We say that Q is without self-joins if every relation symbol appears in at most one atom. 
We visualise queries as hypergraphs where nodes are query variables (free variables are underlined), solid red hyperedges
represent dynamic atoms, and dotted blue hyperedges represent static atoms. 





Analogously, the static sub-query (Q)  is obtained from (Q) by skipping all variables that appear in some dynamic atom of Q. 
Analogously, we obtain the dynamic sub-query by skipping all static atoms and 
restricting the head of the query to those variables
that appear in dynamic  atoms.
We obtain the  reduced dynamic sub-query by further skipping the variables that appear in static atoms in Q.



Consider the query 
Q_2(A,C,D) = R^d(A,D), S^s(A,B), T^s(B,C), U^d(D)
and its hypergraph
from Figure <ref>.
Its static and dynamic sub-queries are 
Q^s(A,C) = S^s(A,B), T^s(B,C)
and respectively 
Q^d(A,D) = R^d(A,D), U^d(D).








A CQ is (α)-acyclic if we can construct a tree, called 
join tree, such that: 
(1) the nodes of the tree are the atoms of the query, and 
(2) for each variable, it holds: if the variable appears in two atoms, then it appears in all atoms on the unique path between the two atoms in the tree <cit.>.
A CQ is called free-connex acyclic if it is acyclic and stays acyclic after adding a new atom whose schema 
consists of the free variables <cit.>.




A CQ is hierarchical if for any two variables X and Y, it holds (X) ⊆(Y),
(Y) ⊆(X), or (X) ∩(Y) = ∅ <cit.>. 

A hierarchical query is q-hierarchical if for any two variables X and Y with 
(X) ⊃(Y), it holds: if Y is free, 
then X is free <cit.>. 





A path in a query Q is a sequence X_1, …, X_n of non-repeating variables from Q such that each two adjacent variables X_i and X_i+1 are contained in an atom from Q, ∀ i∈[n-1]. 
We sometimes see a path as the set of its variables.
Two variables X_1 and X_n are connected if there is a path X_1, …, X_n. An atom R( Y) and a variable X_n are connected if there is a path X_1, …, X_n for some variable X_1∈ Y. Two atoms, R( Y) and S( Z), are connected if there are X_1 ∈ Y and X_n ∈ Z such that X_1 and X_n are connected.
A set  of atoms in Q is called a connected component of Q if any two atoms in  are connected and this does not hold for any superset of .















The query Q_1(A,B,C) = R^d(A,D), S^d(A,B), T^s(B,C) has the path D, A, B, C that connects (i) the variables D and C and (ii) the atoms R^d(A,D) and T^s(B,C).








  
*Dynamic Query Evaluation

The problem of dynamic query evaluation is as follows: In a database containing both static and dynamic relations, when presented with a query, our goal is to maintain the query result under updates to the dynamic relations and to allow for the enumeration of tuples in the query result following an update.

A single-tuple update to a relation R is an insert or a delete of a tuple 
to R. We denote an insert of t by + t and its delete by - t. In this paper, we consider set semantics: A tuple is either in or not in the database; the results of this paper can be generalised to bag semantics, or ℤ-sets, where tuples are associated with (positive or negative) multiplicities.

Following prior work, e.g., <cit.>, we decompose the time complexity of dynamic query evaluation into preprocessing time, update time, and enumeration delay. The preprocessing time is the time to compute a data structure that represents the query result before receiving any update. The update time is the time to update the data structure under an insert or delete of a single tuple to the database. The enumeration delay is the maximum of three times: the time between the start of the enumeration process and outputting the first tuple, the time between outputting any two consecutive tuples, and the time between outputting the last tuple and the end of the enumeration process <cit.>.




  
*Computation Model and Data Complexity
We use the RAM model of computation where database schemas and data values are of constant size. To address the elements in a set of 
N values, where N is the input size, we need an index of constant size. Looking up the value in the set at a given index takes constant time. We further assume that each relation  R  over schema X is implemented by a data structure 
of size O(|R|) that can: 
(1) look up, insert, and delete entries in constant time, and
(2) enumerate all stored entries in R with constant delay.
For a schema S ⊂ X, 
we use an index data structure that for any 
t∈( S) can: 
(3) enumerate all tuples in σ_ S=tR with constant delay, and 
(4) insert and delete index entries in constant time. 
All aforementioned lookup times, update times, and enumeration delays are amortised.

We  report time complexities as functions of the database size N at the update time and using data complexity (the query is fixed and has constant size).
Constant update time and constant delay therefore mean that they do not depend on the database size.  A query is tractable if it can be maintained with constant update time and enumeration delay.

Due to space constraints, Appendix <ref> introduces the fractional edge cover number ρ^*_Q( S) of a variable set  S, the  
Online Matrix-Vector Multiplication (OMv), Online Vector-Matrix-Vector Multiplication (OuMv), and the Boolean Matrix-Multiplication (BMM) conjectures. 




 


§ SAFE QUERY REWRITING



A rewriting of a query is a project-join plan for the query. In the context of dynamic query evaluation, query rewritings have been previously used under the term view trees due to their natural tree-shaped graphical depiction <cit.>.
In this paper, we introduce a special type of query rewritings called safe, which ensures tractable evaluation.

A rewriting of a CQ Q using views (rewriting of Q in short) 
is a forest 
= {T_i}_i ∈ [n] of trees T_i 
where the leaves are the atoms of Q and each inner node is a view V such that:



  * If V has a single child, then V results from its 
child by projecting away some variables; we 
call V a  projection view. 

  * If V has several children, then V is the join of its children; we call V a join view. 

A view V is  dynamic if the subtree rooted at V contains a dynamic atom. For convenience, we also refer to the atoms in a rewriting as views. 



 Figure <ref> gives three (out of many possible) rewritings of the query 
 Q_2(A,C,D) = R^d(A,D), S^s(A,B), T^s(B,C),U^d(D)
 from Figure <ref>.
 Each rewriting is depicted as a tree. 
 In all rewritings, the view V_ST is static, while the view V_RST is dynamic since it contains the dynamic relation R^d in its subtree. 




Next, we define safe query rewritings, which have 
four properties. The two correctness properties ensure that the views correctly encode the query result as a factorised representation <cit.>.
The update property guarantees that the dynamic views can be maintained in constant time under single-tuple updates to any dynamic relation. 
The enumeration property ensures that the tuples in the query result can be listed from the views with constant delay.

 
 
A rewriting = {T_i}_i ∈ [n] 
is safe for a CQ Q if: 


  Correctness
    (1) For each connected component  of Q, there is a tree  T_i that contains all atoms in . 
    (2) For any projection view V'( Y) with  child view V( X), it holds that
    each atom of Q containing a variable from X ∖ Y is contained only in the subtree rooted at V.


  Update The schema of each dynamic view covers the 
schema of each of its sibling views. 


  Enumeration
Each tree T_i has a subtree T_i' containing the root of T_i such that: 
    ⋃_i∈ [n](T_i') = (Q),

where (T_i') is the set of variables of the views in the subtree T_i'. 

 

 The computation time for a query rewriting is the time 
 to materialise all its views.
 

 
 
Let a CQ Q and a database of size N.
If Q has a safe rewriting with f(N) computation time for some function f, then 
Q can be evaluated with f(N) preprocessing time, 
1 update time, and 1 enumeration delay. 
  


The first rewriting in Figure <ref> is not safe: 
It violates the enumeration property because the root view V_RSTU contains the bound variable B, thus there is no guarantee of reporting distinct (A,C,D)-values with constant delay, as per our computational model.
One possibility is to project away B before starting the enumeration but this requires time linear in the size of V_RSTU. 
The rewriting also violates the update property: for instance, the schema of the dynamic view R^d(A,D) does not cover the schema of its sibling V_ST(A,B,C), thus 
computing the change in V_RST for an update to R^d
requires iterating over linearly many (B,C)-values from V_ST that are paired with the A-value from the update.

The second rewriting is also not safe: 
It satisfies the enumeration property as the root view encodes the query result 
but fails on the update property for both dynamic atoms. 








The third rewriting is safe and admits 1 update time and 1 enumeration delay, per Proposition <ref>. We next show how to handle updates and enumerate from this rewriting.

We can propagate an update to R^d or U^d to their ancestor views in constant time. 
Consider an insert of a new tuple (a,d) to relation R^d.
To compute the change in V_RST,
we check if a exists in V_ST” via a constant-time lookup.
If not, we stop as no further propagation is needed; 
otherwise, we insert (a,d) into V_RST in constant time.
We maintain V_RST' by inserting d into that view.
We compute the change in the root V_RSTU by checking if d exists in U^d via a constant-time lookup, and if so, we insert d into the root. 
Propagating an insert to U^d requires a lookup in V_RST' and a insert into V_RSTU, both in constant time.
Deletes to R^d and U^d are handled analogously. 
Thus, updates in this rewriting take constant time.

We can enumerate the distinct 
tuples in the query result using three nested for-loops. 
The first loop iterates over the D-values in V_RSTU; 
the second loop iterates over the A-values in V_RST paired with a D-value from the first loop;
and the third loop iterates over the C-values in V'_ST paired with an A-value from the second loop. 
Hence, each distinct output tuple can be constructed in constant time. 

The time to compute the view V_ST is quadratic because in the worst case each
A-value in S^s is paired with each C-value in T^s.
All other views in the rewriting are either projection views or
semi-joins of one child view with another child view. 
Thus, the overall computation time for the rewriting is N^2,
where N is the database size.   



§ NEW QUERY CLASSES


In this section we introduce the query classes , , and 
. We first define two syntactic properties that underlie the classes  and  and ensure that any query in these two classes has a safe rewriting using views. The class  contains queries that do not satisfy these properties. 



A query has safe atom-to-atom paths if any path P connecting two dynamic atoms goes through a variable that is common to the two atoms:


A query has safe atom-to-atom paths if for 
every path P connecting two dynamic atoms R( X)
and S( Y), it holds 
X ∩ Y ∩ P ≠∅.



The queries
Q_3(A,B, C) = R^d(A), S^s(A,B), T^d(B)
and 
Q_4(A,B, C) = R^d(A, B), S^d(A, C), T^s(B, C) 
from Figure <ref> do not have safe 
atom-to-atom paths. 
The path A,B connects
the two dynamic atoms R^d(A) and T^d(B) in Q_3,
which do not share any variable. 
The path B,C connects
the two dynamic atoms R^d(A,B) and S^d(A,C)
in Q_4 but does not go through their only common 
variable A.


A query has safe atom-to-variable paths if
any path P connecting a dynamic atom with a free variable 
goes through a free variable of the atom:


A query Q has safe atom-to-variable paths if 
for every path P connecting a dynamic atom R( X)
with a free variable, it holds X ∩ free(Q) ∩ P ≠∅.



The query Q_5(B, C) = R^d(A, B), S^d(A, C), T^s(B, C)
from Figure <ref> does not have safe 
atom-to-variable paths since the path A,B connects
the dynamic atom S^d(A, C) with the free variable 
B but does not go through C, which is the free variable of S^d(A, C).


A query has safe paths if it has safe atom-to-atom paths and safe atom-to-variable paths.  We can check efficiently whether a query has safe paths:



For any CQ Q with n variables and m atoms, it can be decided in O(n^2 · m^2) time whether Q has safe paths.


Safe paths ensure that the dynamic sub-query is q-hierarchical:





  * Any CQ without static relations is q-hierarchical if and only if it
has safe paths. 

  * The dynamic sub-query of any CQ with safe  paths is q-hierarchical. 



In Section <ref>, we show that every 
query with safe paths admits a safe rewriting, that is, it can be rewritten into a forest of views that support constant update time and constant enumeration delay. To obtain linear preprocessing time, we further require that the query is free-connex α-acyclic.



A CQ is in  if it is free-connex α-acyclic and has safe paths.  


For the class , we skip the condition that the query is 
free-connex acyclic. 



A CQ is in  if it has safe paths.  



    Consider the queries from Figure <ref>.    
    The query Q_1 is in  since it is free-connex α-acyclic and has safe paths.
    The query Q_2 has safe paths but is not free-connex since adding its head atom Q_2(A,C,D) to its body yields a cyclic query. Hence, Q_2 is in .
    The queries Q_3-Q_6 are not in  since they have no safe paths. 






The class  requires   
that dynamic atoms are covered by static atoms in case the safe path 
property is violated:







A CQ is in  if it has safe paths or every variable contained in a dynamic atom is 
also contained in a static atom.



The query Q_3 does not have safe atom-to-atom paths 
but is in  since the two dynamic atoms 
are covered by a static atom. The queries 
Q_4-Q_6 are not contained in  because they have variables 
in dynamic atoms that are not covered by static atoms. 





The queries Q_1 and Q_2 in Figure <ref> are simple 
-queries. The query Q_2 is q-hierarchical; the query Q_1 is not q-hierarchical 
but free-connex. 


This  class  characterises the tractable queries over static and dynamic relations. 



    Consider a CQ Q and a database of size N. 


  * If Q is in , it can be evaluated with N preprocessing time and 1 update time and enumeration delay. 


  * If Q is not in  and has no self-joins,  there is no γ > 0 such that Q can be evaluated with N^3/2-γ preprocessing time and N^1/2-γ
update time and enumeration delay, 
unless the OMv or the BMM conjecture fails.  





The query Q_3 in Figure <ref> is contained in .
Since it is not free-connex acyclic, it is not included in .


For -queries, the preprocessing time can be super-linear but is 
characterised by the fractional hypertree width:




    Given a -query and a database of size N, the query can be evaluated with N^ preprocessing time and 1 update time and enumeration delay, where 
     is the fractional hypertree width of the query. 






The Queries Q_4-Q_7 in Figure <ref> are contained in 
but not in the other two subsumed classes. 
All queries besides Q_6 have an atom-to-atom path that is not safe. 
The query Q_6 has an atom-to-variable path that is not safe.
All queries except Q_7 are free-connex acyclic. 


The class  characterises all CQs over static and dynamic relations that admit 
constant update time and enumeration delay: 




    Consider a CQ Q. 


  * If Q is in , it can be evaluated with 2^2^P
preprocessing time and 1 update time and enumeration delay, where P = ρ^*((Q)) is the fractional edge cover of the static subquery.


  * If Q is not in  and has no self-joins,  there is no γ > 0 such that Q can be evaluated with arbitrary preprocessing time and N^1/2-γ
update time and enumeration delay, 
unless the OMv fails.  



 


§ EVALUATION OF QUERIES IN  AND 


We describe our evaluation strategy for queries in 
the class , which includes the class .
In Section <ref>, we introduce variable orders, which guide the construction of safe rewritings for such queries. 
We also define the preprocessing width of a query 
based on its variable orders.
We show that for queries in , the preprocessing width 
is 1.
In Section <ref>, we show how we can construct a
safe rewriting for queries in  following variable orders
in time that is given by their preprocessing width.  
This proves the complexity upper bounds in 
Theorems <ref> and <ref>.



 §.§ Variable Orders


We say that two variables in a query are dependent if 
they appear in the same atom. 
A variable order (VO) for a query Q in  is a 
forest ω = {ω_i}_i ∈ [n] of trees 
ω_i such that: (1) The nodes of ω are the variables in Q;
(2) the variables of each atom in Q lie on a root-to-leaf path in 
ω <cit.>. 
We denote by (ω) the set of variables in ω and by
ω_X the subtree of ω rooted at X.
We associate each VO ω with a dependency 
function _ω that maps each variable X in ω 
to the subset of its ancestors on which the variables in ω_X 
depend on: 
_ω(X) = {Y | Y  is an ancestor of  X  and ∃ Z ∈ω_X  s.t. Y depends on Z}. 


An extended VO results from a VO ω by adding the atoms in Q as new leaves: Each atom becomes the child of the lowest variable in ω that is contained in the schema of the atom.
A VO is canonical if the variables of each atom are the inner nodes of a root-to-leaf path in the extended VO. 
It is called free-top if no bound variable is on top of a free variable. 
Every q-hierarchical query admits a free-top canonical 
VO <cit.>. 
We say that the dynamic part of a VO 
ω = {ω_i}_i ∈ [n]
is canonical if each tree ω_i
has a connected subtree ω_i' including the root such that
{ω_i'}_i ∈ [n] is a canonical VO for (Q).













    
      Consider the query Q from Figure <ref>. 
      The query has safe paths but is not free-connex α-acyclic, thus Q ∈. 
      The dynamic subquery (Q) is q-hierarchical, per Proposition <ref>.
      
      
      The figure shows an extended free-top VO for the query where the dynamic part consisting of 
      the variables A, B, and C is canonical. 
    

We can generalise the above example to all queries in : 



    Any query in  has a free-top VO whose dynamic part is
    canonical.



In the following, we use VO to refer to an extended free-top VO 
whose dynamic part is q-hierarchical. 








Next, we define the preprocessing width  of VOs and queries in . For a variable X in a VO,  
Q_X denotes the query that joins all atoms in the subtree 
of the VO rooted at X: 


    (ω)     = max_X ∈(ω)ρ_Q_X^*({X}∪_ω(X)) 
    (Q)     = min_ω∈(Q) (ω)


The preprocessing width of any query in  is 1: 



For any query Q in , it holds (Q)= 1.



Figure <ref> shows the dependency set for each variable in the VO ω.
We have dep_ω(D) = {A,C} and 
ρ_Q_D^*({A,C,D}) = 2 since we need two atoms to cover these variables.
For all other sets, the fractional edge cover number is 1. 
Hence, the preprocessing width of the overall query is 2.

Figure <ref> shows for each 
variable in the VO ω its dependency set. We have
dep_ω(H) = {B,D,I} and 
ρ_Q_H^*({B,D,H, I}) = 2, since we need two atoms to cover these variables.
Similarly, we have dep_ω(G) = {C,F} and 
ρ_Q_G^*({C,F}) = 2. For all other sets, the 
fractional edge cover number is 1. Hence, the preprocessing width of the overall query is 2.





 §.§ Safe Rewriting of Queries in 


We show that every query in  has a safe rewriting 
using views. The time to compute the views is N^,
where N is the database size and  is the
preprocessing width of the query. 











Prior work uses view trees following variable orders to evaluate 
queries in the all-dynamic setting <cit.>. We adapt the view tree construction to the 
setting over static and dynamic relations and show that for
queries in , 
the resulting view trees are safe rewritings.



Given a VO ω for a query Q in , the procedure  in Figure <ref>
rewrites Q into a forest of views following ω.
It proceeds recursively on the structure of ω.
If ω consists of a set of trees, it creates a view tree for each tree in ω (Line 1). 
If ω is a single tree with root X, it proceeds as follows.
If X is an atom or its only child is an atom, 
it returns the atom (Lines 2-3).
Otherwise,
it creates a join view V_X that joins the created child views
and puts on top a projection view V_X' that projects away X, unless X has no ancestor (Lines 5-7). 




    Figure <ref> shows the view tree constructed by the procedure  following the VO ω depicted in the figure. Observe that we obtain 
    the view tree from the VO by replacing each variable X either 
    by a single projection view V_X'(dep_ω(X)) or by
    a join view  V_X({X}∪ dep_ω(X)) and a projection 
    view V_X'(dep_ω(X)) on top. 
    
    We can verify that the view tree satisfies all four properties of safe rewritings as specified in 
    Definition <ref>. 
    
    The schema of each dynamic view in the view tree covers the schema of each of its siblings; for instance, the schema of the view V'_B(A) covers the schema of the sibling view V'_C(A).
    The views V_A(A) and R^d(A,B) encode the query result. 

    The time to compute the view V_D(A,C,D) is quadratic in the database size.
    All other views compute semi-joins or project away a variable in linear time.
    Thus, the computation time for this rewriting is quadratic.
  
From Proposition <ref> follows that this query admits constant update time and constant enumeration delay after quadratic preprocessing time.  

    It contains all atoms 
    of Q  and if a view is obtained by projecting away a variable 
    X, then all atoms containing X are in the subtree of the view 
    (correctness properties). For instance, the view V_G', which 
    projects away G, has both atoms Y^s(C,G) and Z^s(F,G)
    that contain G in their schema in its subtree. 
    The schema of each dynamic view covers the schema of each of its siblings (update property). For instance, the schema of the view V'_F(AC) covers the schema if the sibling view V'_E(A,C).   
Finally, the view tree contains a sub-tree including the root where the union of the schemas of all views are exactly the free variables.   



The procedure  outputs a safe rewriting. The computation time of the rewriting is given by the preprocessing width of Q.

    
    For any query Q in , VO ω for Q, and database of size N, 
    (ω) is a safe rewriting for Q
    with N^ computation time, where N is the database size and  is the preprocessing width of Q. 




Given a query Q in  and a VO ω for Q
let = (ω).
The correctness property in the definition of safe rewriting is satisfied by the view trees constructed by the procedure  because of the fact that each atom is placed under its variables in the VO. The update property guaranteed by the property that the dynamic part of the VO is hierarchical.   
The enumeration property follows simply from the fact that the VO is free-top. The complexity analysis closely follows the analysis of view tree constructions in prior work <cit.>. Details are deferred to Appendix <ref>.













§ EVALUATION OF QUERIES IN 



In this section, we first exemplify our evaluation strategy for one simple query in  and then describe it for arbitrary queries in .

Consider the query Q_3(A,B) = R^d(A), S^s(A,B), T^d(B) from Figure <ref>. It does not admit a safe rewriting, thus the evaluation strategy described in Section <ref> cannot achieve constant update and constant enumeration delay.
At a first glance, Q_3 does not seem tractable as a single-tuple update can lead to linearly many changes to the query result. 
For example, an insert +a to R^d may be paired with linearly many B-values in S^s.
Yet if we allow for more preprocessing time, we can resolve this difficulty by precomputing the effect of each possible update and store it in a transition system that allows us to efficiently fetch the updated query result after each single-tuple update. 

A transition system is a tuple (, s_init, , δ), 
where  is a set of states, s_init∈ is the initial state,  is a set of single-tuple updates, and δ: ×→ is a function that maps a state and a single-tuple update to another state.
In our context, each state corresponds to a database instance and the materialised query result over that database; since the static relations do not change and are the same across all states, we only record in the states the content of the dynamic relations and the query result.
Each transition corresponds to a single-tuple update to a dynamic relation.
In the preprocessing step, we build such a transition system.
For each update, we use the transition system to move from the current state to another state. 
To enumerate the query result, we enumerate the tuples in the current state.
We next show our evaluation strategy for query Q_3.



We create one state for each possible snapshot of the dynamic relations R^d and T^d, that is, for every combination of the possible A-values in R^d and B-values in T^d. We then build the transitions between these states that correspond to the insertions and deletions of A- and B-values. Even though the domain of R^d and T^d can be unbounded, the result of Q_3 is nevertheless guarded by the static relation S^s. This means that only the A- and B-values from S^s can appear in the query result.
Therefore, we can restrict the domain of the variables in the dynamic relations R^d and T^d to the A-values and B-values from S^s.

Let = π_A S^s and = π_B S^s.
For each pair α⊆ and β⊆, we create a state (α, β) and the corresponding query result for  R^d=α and T^d=β. That is, the state (α, β) has the result Q_3(A,B) = α(A), S^s(A,B), β(B).
The transition system has the states = {(α, β) |α⊆, β⊆}.
The initial state s_init=(α_0,β_0) is the state corresponding to the input database with α_0 = R^d∩ and β_0=T^d∩.
Each transition corresponds to an insertion +a (deletion -a) of an A-value a ∈ to (from) R^d or the insertion +b (deletion -b) of a B-value b ∈ to (from) T^d.
Consider a state (α, β) ∈. For each a ∈∖α, we create the transition δ((α, β), +a) = (α∪{a}, β). For each a ∈α, we create the transition δ((α, β), -a) = (α∖{a}, β). We ignore transitions from a state to itself without loss of generality. We create similar transitions for inserting and deleting B-values.
Once the transition system is built, we move to the initial state.
We start from the state (∅, ∅), and simulate the insertion of each value in the input dynamic relations to move to the initial state.





Figure <ref> shows an input database (left) and the transition system built for query Q_3 on the input database (right).
The A- and B-values in S^s are = {a_1} and = {b_1, b_2}, respectively.
The transition system contains eight states (boxes), one for each combination of the subsets α⊆ and β⊆.
Each state (α, β) defines the result of Q_3 for R^d=α and T^d=β.
Since the input dynamic relations are R^d={a_1} and T^d={b_3},
the initial state has α={a_1} and β=∅, since b_3∉ and does not match any transition.

The input database contains N A-value and B-values, so the transition system contains 2^N states.
The query result at any state is a subset of S^s and can be computed in N time. The number of transitions from any state is bounded by twice the number of distinct A-values and B-values, which is N. For each transition, we take O(N) time to find the landing state (α,β) of size O(N) among exponentially many such pairs. Overall, it takes N^2 time to build the index to allow  transitions from each state. Once built, we can move between states in constant time. Overall, we can create each state and its transitions in N^2 time. The general case is detailed in Appendix <ref>.

The preprocessing time is given by the number of states times the creation time per state, so 2^N· N^2.
The update time is constant since for each single-tuple update to the dynamic relation, we find in constant time the corresponding transition and move to the target state or ignore the update if it does not match any transition.
We enumerate the tuples in the current state trivially with constant delay, as the query result is already materialised.


We generalize the evaluation strategy from Example <ref> to arbitrary queries in . 
The transition system can be built in time 2^p · p^2, where p = N^ρ^*((Q)), as stated in Theorem <ref>.
Finding the initial state takes time N.

Consider a query Q in . Let k be the number of dynamic relations in Q.
We create one state for each possible snapshot of the dynamic relations. 
Since Q is in , every variable in a dynamic atom R^d() also occurs in a static atom.
Similar to Example <ref>, we restrict the possible values for  in R^d to the projection of the result of the static sub-query (Q) of Q onto . Let us denote this projection by _R^d. Similarly, we create the sets _R^d_1, …, _R^d_k for all dynamic relations R^d_1, …, R^d_k. The size of each such set is upper bounded by the size of the result of the static sub-query, which is N^ρ^*((Q)).

The transition system has the states = {(α_1,…,α_k) |α_1 ⊆_R_1^d, …, α_k ⊆_R_k^d}, i.e., we create a state for each combination of the subsets of _R^d_1, …, _R^d_k.
The overall number of states is (2^N^ρ^*((Q)))^k = 2^k · N^ρ^*((Q)).

Consider an arbitrary state (α_1,…,α_k) ∈.
We materialise the corresponding query result, that is, the result of Q where R^d_i = α_i, for i∈[k].
The size of the result is bounded by N^ρ^*((Q)), and thus can be computed in N^ρ^*((Q)) time.

We next build the transitions for each state.
Consider a dynamic relation R^d_i.
For each a ∈_R^d_i∖α_i, we create a transition δ((α_1,…,α_k), +a) = (α_1,…,α_i ∪{a},…,α_k) that moves to the state where a is included, 
and conversely, for each a ∈α_i, we create a transition δ((α_1,…,α_k), -a) = (α_1,…,α_i ∖{a},…,α_k) that moves to the state where a is removed.
The state has N^ρ^*((Q)) transitions per dynamic relation. 
Appendix <ref> explains how to build an index for these transitions in N^2ρ^*((Q)) time, which allows us to move from the current state to another state for an update in constant time.
We build the transitions and compute the index for all k dynamic relations.
Overall, we can create the state in k · N^2ρ^*((Q)) time.


Building the transition system takes time proportional to the number of states times the time to build one state: 2^k · N^ρ^*((Q))· k · N^2ρ^*((Q)) in total.
We simplify it to 2^p · p^2, where p = N^ρ^*((Q)).
This matches the complexity in Theorem <ref>.



§ LOWER BOUND FOR QUERIES OUTSIDE 


In this section, we outline the proof of the lower bound result in 
Theorem <ref>.
It consists of two parts.
In the first part, we give lower bounds 
on the evaluation complexity
of the simple queries  
Q_RST() = R^d(A),S^s(A,B), T^d(B) 
and
Q_ST(A) = S^s(A,B),T^d(B).
None of these queries is contained in :
the first one does not have safe atom-to-atom paths
and the second one does not have safe atom-to-variable paths. 
In the second part, the argument is as follows. 
Consider a query Q ∉ that has no self-joins. 
By definition of , this means that 
(1) Q is not free-connex acyclic, or (2) it does not have safe atom-to-atom paths, or 
(3) it does not have safe atom-to-variable paths. 
In case Q is not free-connex acyclic, we cannot achieve
constant-delay enumeration of the result after linear preprocessing time
(even without processing any update), unless the BMM conjecture fails <cit.>. 

If Q does not have atom-to-atom or atom-to-variable paths, we 
reduce the evaluation of Q_RST or respectively 
Q_ST to the evaluation of Q, which transfers the lower bound 
for these queries to Q. 
The latter reduction is standard 
(see, e.g., <cit.>).

In the following, we outline the lower bound proofs for Q_RST and 
Q_ST and defer the details to Appendix <ref>.

The lower bound for Q_RST is conditioned on the OuMv conjecture, which is implied by the OMv conjecture <cit.>:



The CQ 
Q_RST() = R^d(A), S^s(A,B), T^d(B) cannot be evaluated with 
N^3/2-γ preprocessing time, 
N^1/2-γ update time, and 
N^1/2-γ enumeration delay
for any γ >0, where N is the database size, unless the OuMv conjecture fails.



Prior work reduces the OuMv problem to the evaluation of the variant 
of Q_RST where
all relations are dynamic <cit.>.
The reduction starts with an empty database 
and encodes the matrix 

of the OuMv problem into the relation S using updates. 
In our case, it is not possible to do this encoding using updates, since the relation is static. Instead, we do the encoding
before the preprocessing stage of
the evaluation algorithm for Q_RST.

We explain the reduction in more detail. 
Assume that there is an algorithm A that 
evaluates Q_RST with 
N^1/2-γ update time and 
enumeration delay after N^3/2-γ preprocessing time,  
for some γ >0. 
Consider an n× n matrix M and n pairs (u_r,v_r) of 
n-dimensional vectors that serve as input to the OuMv problem.
We first encode M into the relation S in time n^2,
which leads to a database of size n^2.
Then, in each round r ∈ [n], we  encode the vectors u_r
and v_r into R and respectively  T using n updates and trigger the enumeration procedure of 
A to obtain from Q_RST the result of u_rMv_r. 
This takes n(n^2)^1/2-γ
= n^2-2γ time. After 
n rounds, we use overall 
n^3-2γ time. This means
that we solve the OuMv problem in sub-cubic time,
which contradicts the conjecture. 



The reduction of the OMv problem to the evaluation of the query 
Q_ST(A) = S^s(A, B), T^d(B) 
is similar to the above reduction. 
We encode the matrix M into the relation S before the preprocessing stage  and encode each incoming vector v_r into T using updates. 



§ OUTLOOK: TRACTABILITY BEYOND 



This work explores the tractability of conjunctive queries  over static and dynamic relations. 
The largest class of tractable queries put forward is . Yet a characterisation of all tractable queries remains open.
In the following, we discuss the evaluation of some queries outside the class . 

Let a query Q. The reduced dynamic sub-query of Q is Q without its static atoms and the variables in these static atoms. An immediate observation is that queries whose reduced dynamic sub-query is not q-hierarchical are not tractable. This is implied by the intractability of non-q-hierarchical queries in the all-dynamic setting <cit.>. 
One example query whose reduced sub-query is not q-hierarchical is the query Q_6(A,B) = R^d(A), S^d(A,B), T^d(B,C), U^s(C) from Figure <ref>.
A question is whether the queries, whose reduced dynamic sub-queries are q-hierarchical, are tractable. We discuss next two such queries that are not in : 
Q_4(A,B,C) = R^d(A,B), S^d(A,C), T^s(B,C) and 
Q_5(B,C) = R^d(A,B), S^d(A,C), T^s(B,C)
from Figure <ref>.


The evaluation strategy illustrated in Example <ref> can be easily extended to Q_4. We create the same transition system as in  Example <ref> and assign each A-value a that is common to R^d and S^d to the state that stores the (B,C)-values paired with a in the result.
Any update to R^d or S^d changes the assignment of at most one A-value. 
At any time, we can enumerate the query result by iterating over the A-values and enumerating for each of them the tuples in their corresponding state. 

The query Q_5(B,C) differs from Q_4 in that the variable A is bound. The above approach for Q_4 does not allow for constant-delay enumeration of the result of Q_5 since distinct A-values might be assigned to distinct states that share (B,C)-tuples. Filtering out duplicates can however incur a non-constant enumeration delay. 


 It is open whether it is possible to achieve constant-delay enumeration of distinct (B,C)-tuples in the union of all states. 

would bring us one step further towards 
a complete characterisation of all tractable queries over static and dynamic relations.


Q_4(A,B,C) = R^d(A,B), S^d(A,C), T^s(B,C)
Q_5(B,C) = R^d(A,B), S^d(A,C), T^s(B,C)
Q_6(A,B) = R^d(A), S^d(A,B), T^d(B,C), U^s(C)



abbrv





§ FURTHER PRELIMINARIES


We recall some notions that were omitted in Section <ref>. 
We start with well-known width measure for queries.



Given a CQ Q and ⊆(Q),    
a fractional edge cover
of  is a solution 
λ = (λ_R())_R() ∈(Q) to the following 
linear program: 

    minimize   ∑_R() ∈ (Q)λ_R()      
    subject to   ∑_R()∈ (Q)  s.t.  X ∈λ_R()≥ 1        for all  X ∈ and 
       λ_R()∈ [0,1]        for all  R() ∈(Q)

The optimal objective value of the above program 
is called the fractional edge cover number of the variable set  
and is denoted as ρ_Q^∗().  
If Q is clear from the context, we omit 
the index Q and write ρ^∗(). When all Q's variables are considered, namely = (Q), we write ρ^*(Q).
For a database of size N, the result of a query Q without bound variables can be computed in time 
N^ρ^*(Q) <cit.>.




A tree decomposition of a CQ Q is a pair (, χ), where  is a tree with vertices V() and χ: V() → 2^(Q) maps each node t of the tree  to a subset χ(t) of variables of Q such that the following properties hold:

    
  * for every atom R(X) ∈(Q), the schema X is a subset of χ(t) for some t ∈ V(),
    
  * for every variable X ∈(Q), the set {t | X ∈χ(t)} is a non-empty connected subtree of . The sets χ(t) are called the bags of the tree decomposition.

A tree decomposition is free-connex if it has a connected sub-tree
such that the union of the bags of this sub-tree are the free variables.
We use TD(Q) to denote the set of free-connex tree decompositions of Q.




Given a CQ Q and a free-connex tree decomposition (, χ) of Q, the fractional hypertree width of (, χ) and of Q are defined 
as follows:

    w(, χ)     = max_t ∈ V()ρ^*_Q(χ(t))
    
        w(Q)     = min_(, χ) ∈ TD(Q) w(, χ)




Next, we overview the widely believed complexity-theoretic conjectures.



Given two n × n Boolean matrices A and B, represented as lists of their non-zero entries, the task is to output the product AB.




The BMM problem cannot be solved in time m^1 + o(1), where m is the number of non-zero entries in A, B and AB.




We are given an n × n Boolean matrix M and receive n Boolean column vectors v_1,…, v_n of size n, one by one. After seeing each vector v_i, the task is to output the product Mv_i before seeing the next vector.




For any constant γ > 0, there is no algorithm that solves the 
OMv problem in time n^3-γ.




We are given an n × n Boolean matrix M and receive n pairs of Boolean column vectors (u_1, v_1),…, (u_n, v_n) of size n, one by one. 

After seeing each pair of vectors (u_i, v_i), the task is to output the product u_iMv_i before seeing the next pair.


The following OuMv conjecture is implied by the OMv conjecture.



For any constant γ > 0, there is no algorithm that solves OuMv 
problem in time n^3-γ.



§ MISSING DETAILS IN SECTION <REF>



 §.§ Proof of Proposition <ref>

Proposition <ref>
Let a CQ Q and a database of size N.
If Q has a safe rewriting with f(N) computation time
for some function f, then 
Q can be evaluated with f(N) preprocessing time, 
1 update time, and 1 enumeration delay. 




Let  be a safe rewriting for Q. 
The preprocessing time is the computation time of .

To enumerate the result of Q, we nest the enumeration procedures for the connected components of Q, concatenating their output tuples.
For each connected component C, the enumeration procedure traverses the tree T ∈ containing all atoms from C in a top-down manner.
The enumeration property of  guarantees that there exists a subtree T' of T having the same root as T that covers exactly the free variables of C.

We enumerate the result of C by traversing the subtree T' in preorder. 
At each view V( X), we fix the values of variables in X ∖ Y, where Y is the set of variables of the ancestor views of V. 
We retrieve in constant time a tuple of values over X ∖ Y from V for the given Y-value. 
After visiting all views once, we construct the first complete output tuple for C and report it. 
We continue iterating over the remaining distinct values over X ∖ Y in the last visited view V, reporting new tuples with constant delay.
After exhausting all values from V, we backtrack and repeat the enumeration procedure for the next Y-value. The enumeration stops once all views from the subtree T' are exhausted.
Given that all views are calibrated bottom-up but the enumeration proceeds top-down, the procedure only visits those tuples that appear in the output, thus ensuring constant enumeration delay.



We propagate a constant-sized update through a tree in a bottom-up manner, maintaining each view on the path from the affected relation to the root.
From the update property of the safe rewriting , computing the delta of any join view involves only constant-time lookups in the sibling views of the child carrying the update. The size of the delta also remains constant.
Computing the delta of a projection view also requires a constant-time projection of its incoming update.
Since an update to one relation affects one tree of , propagating an update through  takes constant time. 



§ MISSING DETAILS IN SECTION <REF>





 §.§ Proof of Proposition <ref>

Proposition <ref>.
For any CQ with n variables and m atoms, it can be decided
in n^2 · m^2 
time whether Q has safe paths.



A CQ Q has safe atom-to-atom paths if every path between any two dynamic atoms includes at least one of their common variables. 
For each pair (R( X), S( Y)) of dynamic atoms of Q,
we first construct the Gaifman graph of the hypergraph of Q without the common variables C =  X ∩ Y. The graph contains n nodes and n^2 edges. 
We next choose any x ∈ X ∖ C and y ∈ Y ∖ C and check if x is reachable from y using the Breadth-First Search algorithm in n^2 time; if so, Q has unsafe atom-to-atom paths. 
We repeat this procedure for every pair of dynamic atoms, which gives the total cost of n^2 · m^2.

A CQ Q has safe atom-to-variable paths if every path between a dynamic atom and a free variable includes at least one free variable from that atom.
For each dynamic atom R( X), 
we construct the Gaifman graph Q without the free variables from R( X).
For each atom containing a free variable y, 
we choose any x ∈ X ∖(Q) and check if x is reachable from y in the graph; if so, Q has unsafe atom-to-variable paths.  
The total time is n^2· m^2.



 §.§ Proof of Proposition <ref>

Proposition <ref>.



  * Any CQ without static relations is q-hierarchical if and only if it
has safe paths. 

  * The dynamic sub-query of any CQ with safe  paths is q-hierarchical. 



We start with the proof of the second statement in Proposition <ref>. 
Consider a CQ Q with safe paths. 
We denote by (X)
the set of dynamic atoms that contain a variable X.
Assume for the sake of contradiction 
that (Q) is not hierarchical. This means that Q contains 
two variables X and Y such that 
(X) ⊈(Y), 
(Y) ⊈(X), and 
(X) ∩(Y) ≠∅.
This implies that Q has three dynamic atoms 
R^d( X), S^d( Y), and T^d( Z)
such that 
X ∈ X, X ∈ Y, X ∉ Z,
Y ∈ Z, Y ∈ Y, and Y ∉ X.
The path P = (X,Y) connects the two dynamic
atoms R^d( X) and T^d( Z) such that 
P ∩ X ∩ Z = ∅.
This means that Q does not have safe atom-to-atom paths, which is 
a contradiction. 

Assume now that (Q) is hierarchical, but not q-hierarchical. 
This implies that Q contains 
two dynamic atom R^d( X) and S^d( Y), a bound variable X
with X ∈ X and X ∈ Y, and a free variable 
Y with Y ∈ Y and Y ∉ X.
The path P = (X,Y) connects the the dynamic
atoms R^d( X) with the free variable Y such that 
P ∩(Q) ∩ X = ∅.
This means that Q does not have safe atom-to-variable paths, which is 
again a contradiction. 



Next, we prove the first statement in Proposition <ref>. The "⇐"-direction follows directly from the second statement. It remains to show the 
"⇒"-direction. Consider a q-hierarchical CQ Q without static atoms. 

We first show that Q has safe atom-to-atom paths. Consider a path P
that connects two atoms R^d( X) and S^d( Y). It follows from the structural properties of q-hierarchical queries that P must contain a variable X that is contained in X and in Y. Hence, P ∩ X ∩ Y ≠∅.
This mean that Q has safe atom-to-atom paths. 

Now, we show that Q has safe atom-to-variable paths. Let P be a path
that connects an atom R^d( X) with a free variable Y. Without loss of generality, 
assume that Y is not included in X. Otherwise,  
P ∩(Q) ∩ X ≠∅ and the property holds. 
Let X ∈ X be the starting point of P in R^d( X).
The structural properties of hierarchical queries imply that (X) ⊃(Y).
Since Y is free, X must be free. This implies however that 
P ∩(Q) ∩ X ≠∅.
This means that Q has safe atom-to-variable paths.


If Q does not contain any pair of dynamic atoms that are connected, it is trivial that both Safe Path properties hold. Now we consider the following two cases.


Case 1: If a path P connects two atoms R( X) and S( Y) that share a set of variables Z =  X∩ Y. Suppose X∩ Y∩ P = ∅, then R( X), S( Y) and the atoms involved in the path P forms a cycle, thus contradicting the fact that Q is q-hierarchical. Therefore, the Safe Atom-to-Atom Path property holds.


Case 2: If a path P connects two atoms R( X) and S( Y) that do not share any variable X∩ Y = ∅, then
the path must contain at least three variables, because a 2-hop path P' = (X_1, X_2)  where  X_1 ∈ X and  X_2 ∈ Y implies that 

    (X_1) ∩(X_2) ≠∅∧(X_1) ⊈(X_2) ∧(X_1) ⊉(X_2),

thus violating the q-hierarchical property.

So we now consider the path

    P = (X_1, …, X_n)  where  n ≥ 3, X_1 ∈ X and  X_n ∈ Y.

By the definition of a path that two adjacent variables are contained in an atom, the first two variables X_1 and X_2 on the path share at least one atom 

    (X_1) ∩(X_2) ≠∅.
 

Given that Q is q-hierarchical, the atoms of X_1 are subsumed in those of X_2 or the other way around

    (X_1) ⊊(X_2) ∨(X_1) ⊋(X_2).
 

This observation allows us to shrink the path between R( X) and S( Y) by one variable.

If the atoms of X_1 are subsumed in those of X_2, then X_1 and X_2 are both contained in R( X). Therefore, we obtain a shorter path P_1 between R( X) and S( Y) by removing X_1

    P_1 = (X_2, …, X_n)  where  n ≥ 3, X_2 ∈ X and  X_n ∈ Y.


Otherwise, the atoms of X_2 are subsumed in those of X_1, we obtain an alternative shorter path P'_1 between R( X) and S( Y) by removing X_2

    P'_1 = (X_1, X_3 …, X_n)  where  n ≥ 3, X_1 ∈ X and  X_n ∈ Y.



By repeating the process for n-1 times, we can obtain a path with only one variable 

    P_n-1 = (X_k)  where  1 ≤ k ≤ n, X_k ∈ X and  X_k ∈ Y.



The fact that X_k is in both R( X), S( Y) contradicts the assumption of Case 3, X∩ Y = ∅. So Case 3 does not occur. Therefore, the Safe Atom-to-Atom Path property holds.





We now prove that the Safe Atom-to-Variable Path property also holds.  
We consider a path P connecting a dynamic atom R( X) with a free variable A.

It it trivial when the path contains only one variable P = (A), the Safe Atom-to-Variable Path property holds.

Case 1: Assuming that P = (B, A) where the variable B is in X, equivalently R( X) ∈(B), the Safe Atom-to-Variable Path property holds when B is free. Otherwise, by the q-hierarchical property, we now have that

    (B) ⊊ atoms(A) ⇒ R( X) ∈(A).

We conclude that

    X∩ free(Q) ∩ P≠∅.



Case 2: Assuming that P = (X_1, …, X_n, A), where n ≥ 2 and X_1 ∈ X, the Safe Atom-to-Variable Path property also holds when X_1 is free. Now we consider the situation when X_1 is bound. Similarly to the process above, the q-hierarchical property allows us to shrink the path to P = (X_k, A) where 1 ≤ k ≤ n and X_k ∈ X. By the same argument of Case 1, we can also conclude that X∩ free(Q) ∩ P≠∅.



§ MISSING DETAILS IN SECTION <REF>


We introduce two notions that will be useful for the proofs in 
the following sections: static parts of queries and VOs with neck. 

A static part of a query Q is constructed as follows. 

Without loss of generality, assume that Q does not have repeating relation symbols. In case a relation symbol R
appears k >1 times in the query, we can  create k copies of R in the database and refer to each copy by a distinct relation name.  
We call an atom R( X') the reduced version of a static atom 
R( X) in Q if X' results from X by skipping 
variables that appear in dynamic atoms of Q.
Let Q' result from (Q) by replacing
all atoms with their reduced versions. 
Consider a connected component  of Q'. 
Let  be the set of all static atoms in Q whose reduced versions are 
in . 
Let Y be the set of variables that appear 
in the atoms in  and in (Q) and F 
the free variables of Q that appear in 
the atoms in .
We call Q_p( F) = (R( Z))_R( Z) ∈
a static part of Q with intersection set Y.



Figure <ref> (top) shows 
a -query Q, its dynamic sub-query (Q), and the static parts of Q with their intersection sets below.
For instance, the third static part Q_p(C) = R(G,C), S(G,F) in the figure has the intersection set {C,F}.













An important observation, which will be used in the following proofs, is that the intersection set of each  static part is covered by a single dynamic atom:



For any query Q in  and any static part Q_p of 
Q with intersection set Y, there is a single dynamic atom R^d( X) in Q such that Y ⊆ X.   



For the sake of contradiction, assume that we need least two distinct dynamic atoms R_1^d( X_1) and R_2^d( X_2) 
from Q to cover the variables in 
Y. This means that there are variables X_1 ∈ X_1 and X_2 ∈ X_2 such that X_1 ∉ X_1 ∩ X_2 and X_2 ∉ X_1 ∩ X_2. By construction of Q_p and its intersection set, there must be a path P in Q of the form (X_1=Y_1, … , Y_n = X_2), where all variables Y_i with i ∈{2, …, n-1} appear only in static atoms. Hence, none of the variables Y_i with i ∈{2, …, n-1} can be included in the intersection 
X_1 ∩ X_2. Since X_1 and X_2 are not included in X_1 ∩ X_2 either, it holds 
P ∩ X_1 ∩ X_2 = ∅. This means that Q 
does not have safe atom-to-atom paths. Thus, Q is not in ,
which is a contradiction. 


Given a VO ω and a subset   of its variables,  
we say that ω  has neck  if its 
upper part is a path consisting of the variables in .
More formally, there
is an ordering X_1, …, X_n of the variables in  such that X_1 is 
the root of ω and for each i ∈ [n-1], X_i + 1 is the only child of X_i. 



Figure <ref> (bottom right) shows for each static part with intersection set Y, a VO with neck Y. For simplicity, we omit the atoms in the VOs.
In each VO, the intersection variables form a path and are on top of all the other variables.
For instance, the VO for the third static part 
Q_p(C) = R(G,C), S(G,F) has the intersection variables C and F above G.




 §.§ Proof of Proposition <ref>

Proposition <ref>.
Any query in  has a free-top VO whose dynamic part is
    canonical.




Given a query Q in , we show how to construct a 
free-top VO for Q whose dynamic part is q-hierarchical. 
The high-level idea of the construction is as follows. 
By Proposition <ref>, the 
dynamic sub-query (Q) of Q is q-hierarchical, hence, it admits a canonical VO. 
First, we construct a canonical VO ω^d for (Q). 
Then, we split the static sub-query (Q) into several parts 
for which we create free-top VOs. 
Finally, we combine ω^d with the VOs for the static parts and show that the resulting structure is a free-top VO for Q.


We first show that for any static part Q_p of Q with intersection 
set Y, we can construct a free-top VO with neck Y.


Figure <ref> shows under each static part of the query Q with intersection set Y,
a free-top VO  with neck Y for the static part.  
Observe that in the VO for the third static part Q_p(C) = R(G,C), S(G,F), the free variable C is on top of F and G, and the intersection variables C and F are on top of G.


First, we show:


Let Q be a CQ in  and Q_p a static part of Q with intersection set Y. If (Q_p) ∖ Y ≠∅,
then all variables in Y are free.



For the sake of contradiction, assume that Y contains a bound variable Y and Q_p
has a free variable X that is not contained in Y.
By Proposition <ref>, Y is included in a
dynamic atom R( X) of Q. 
Since Y is the intersection set of Q_p,
the variable X cannot be covered by any dynamic atom of Q.
This means that Q contains a path P of the form 
Y=X_1, … , X_n = X that connects R( X) with the free variable 
X such that (Q) ∩ X ∩ P =∅.
This implies that Q does not have safe atom-to-variable paths. Hence, 
Q cannot be in , which is a contradiction. 


Using Proposition <ref>, we show:



Let Q be a CQ in  and Q_p a static part of Q with intersection set Y. There is a free-top VO for Q_p with neck Y.



It follows from Proposition <ref> that all free variables in Q_p are in Y.
Hence, we can construct the following free-top VO ω for Q
with neck Y. We construct a path N out of the variables in 
Y such that the free variables in Y are on top of all other variables in Y. This path becomes the neck of ω. In the rest of ω, we again make sure that the free variables are on top of the other variables. Observe that this is always possible, since in the worst case,
ω is path, in which case the variables can be ordered arbitrarily. 


We describe now how to construct from the free-top VOs for the static parts of Q, a free-top VO ω for the overall query such that the dynamic part of ω is canonical.    
The construction is described by the procedure createVO in Figure <ref>. 



The procedure first constructs a canonical VO 
ω^d for (Q).
The existence of such a canonical VO is guaranteed by the fact that 
(Q) is q-hierarchical (Proposition <ref>).
Then, for each static part Q_i with intersection set Y_i, it 
constructs a free-top VO ω_i with neck Y_i.
The existence of such a VO is guaranteed by 
Proposition <ref>. We obtain the final VO by attaching the VOs for the static parts to ω^d. We explain next how a VO ω_i 
for a static part is attached to ω^d.  


By Proposition <ref>, the neck of ω_i 
is included in a single atom of (Q).
Hence, all neck variables are on a root-to-leaf path of 
ω^d. If Y_i is empty, we add ω_i as a separate tree to ω.
Otherwise, let X be the lowest variable in ω_i that is contained 
in Y_i and let Y be the lowest variable in ω^d 
that is contained in Y_i.
We make the child trees of X to child trees of Y. 


Figure <ref>
shows under the query Q the free-top VO obtained by putting together  the canonical VO for (Q) and the free-top VOs 
for the static parts.


It remains to show:



For any query Q in  , createVO(Q) is a free-top VO for Q whose dynamic part is canonical.



Consider a query Q in  with static parts 
Q_1, …, Q_n and corresponding intersection 
sets Y_1, …,  Y_n and let ω = createVO(Q). 
Let ω^d be the canonical variable order of (Q) and
ω_1, …, ω_n the free-top VOs of the static parts
Q_1, …, Q_n with necks Y_1, …,  Y_n, as guaranteed by Proposition <ref>.  

We show that the variables of any atom R( X) of Q is on a root-to-leaf 
path of ω.     
The atom R( X) must be  in dyn(Q) or in a static part Q_i. 
In the former case, the variables in X lie on a root-to-leaf path in ω^d.

In the latter case, they lie on a root-to-leaf-path
of ω_i. In both cases, they must lie on a root-to-leaf path in ω, since ω^d and ω_i are subtrees in ω. 

For the sake of contradiction, assume that ω contains a bound variable Y above a free variable X. Since ω^d and ω_1, …  ,ω_n are free-top, it must hold Y ∈(ω^d), 
X ∉(ω^d) and X ∈(ω_i), for some i ∈ [n].

Let R( X) be a dynamic atom
with Y ∈ X. It follows from the construction of ω that 
there is a path P from Y to X such that X ∩(Q) ∩ P = ∅. This implies that Q does not have have safe atom-to-variable paths. Hence, Q is not a query from the class , which is a contradiction.

Finally, by construction, the dynamic part ω^d of ω is canonical. 






 §.§ Proof of Proposition <ref>

Proposition <ref>.
For any query Q in , it holds (Q)= 1.



Consider a query Q in .  We will show that we can construct 
for Q a free-top VO ω with preprocessing width 1 such that
the dynamic part of ω is canonical.  

First, we will construct for every static part Q_p of Q with intersection set Y, a free-top VO  with neck Y
and preprocessing width 1. 
Then, we use the procedure createVO from 
Figure <ref> to build a free-top VO for Q
with preprocessing width 1, whose dynamic part is canonical. 



  
*Constructing VOs for Static Parts
Consider a static part Q_p of Q with intersection set Y.
We explain how to construct for Q_p a free-top VO with neck Y and preprocessing width 1.  
By definition, Q is free-connex acyclic. 
It follows from prior work that a query is free-connex 
acyclic if and only if it
has a free-top VO ω that has preprocessing width 1 but 
whose dynamic part is not necessarily canonical <cit.>.
Let Q' and Q_p' be the queries obtained from Q and respectively Q_p by adding a fresh atom 
R( Y). The query Q' must be free-connex acyclic either.
Hence, it has a free-top VO ω with preprocessing width 1. 
We start with such a VO ω for Q'
and eliminate one-by-one all variables that do not appear in Q_p'. When removing a variable X with parent variable Y, the children of X become the children of Y.
If a removed variable X does not have a parent, the child trees of X become independent trees. Observe that after all variables that are not contained in Q_p' are removed, we are left with a valid free-top VO for Q_p' whose preprocessing width is 1. Hence, it is free-connex acyclic. 
This means that it has a free-connex tree decomposition where each bag is 
covered by single atom <cit.>. We root the tree decomposition at the bag that contains 
R( Y). This decomposition can be transformed into a free-top VO of width 1 following a construction in prior work <cit.>.  
The construction proceeds top-down and an leaves the variables of each bag on a root-to-leaf path. hence, the resulting VO has neck Y.



  
*Constructing a VO for Q
Let Q_1, … , Q_n be the static parts of Q with intersection 
sets Y_1, … Y_n. For each i ∈ [n], let 
Q_i' be the extension of Q_i by a fresh atom R_i( Y_i).
The purpose of using R_i( Y_i) in the query Q_i is to guarantee 
that in any VO for Q_i, the variables in Y_i are on a root-to-leaf path.
Let ω^d be the canonical VO of (Q) and ω_1, …ω_n the free-top VOs for Q_1', … , Q_n' constructed as described above. We use the procedure createVO in 
Figure <ref> to combine the VO ω^d with the 
VOs ω_1, … , ω_n. The same arguments as in the proof
of Proposition <ref> imply 
that we obtain a valid free-top VO ω for Q whose dynamic part is canonical.


It remains to explain that the preprocessing width of ω
is 1. 
Consider a variable X that is contained in a dynamic atom.
Since the dynamic part of ω is canonical, all ancestor variables of X are contained  in each dynamic atom below X. This implies 
ρ^*_Q_X({X}∪_ω(X)) =1.
Consider now a variable X that does not appear in (Q) in some static part 
Q_i. Since ω_i has preprocessing width 1, it holds
ρ^*_Q_X({X}∪_ω_i(X)) =1 within ω_i.
Since all variables that depend on X must be included in Q_i, 
we obtain ρ^*_Q_X({X}∪_ω(X)) =1 within ω.
Overall, we derive that the preprocessing width of ω and, hence, of Q is 1.




 §.§ Proof of Proposition <ref>

Proposition <ref>.
For any query Q in , VO ω for Q, and database of size N, (ω) is a safe rewriting for Q
    with N^ computation time, where  is the preprocessing width of Q. 




Given a query Q in , a VO ω for Q, and database of size N, let = (ω).
We show that  satisfies all properties for safe 
rewritings, as specified in Definition <ref>. 

We first show that the correctness properties for safe rewritings hold. 
By the definition of VOs, the variables of each atom must be on 
a root-to-leaf path and each atom is placed under its lowest variable in the VO. This implies that for each connected component  of Q, 
all atoms in  must be in a single tree of  (first correctness property). Since all atoms containing a variable X must be below X in the VO, all atoms that contain X must be in the subtree rooted at a projection view V_X (second correctness property). 


Now we show that the update property holds for .
By definition, the dynamic part of ω is canonical.
Hence, the schema of each dynamic atom covers all ancestor variables. 
This implies that also each dynamic view V contains in its schema 
all its ancestor variables. Consider a dynamic view V_X and its sibling view V_Y. By construction,
we need to consider two cases. In the first case, V_Y is an atom.
In this case, the schema of V_Y is included in its ancestor variables. 
Hence, V_X covers the schema of V_Y.
In the second case, V_Y is a projection view at some variable Y that does not include Y. In this case,  the view V_Y can only contain variables that are ancestors of V_X. Hence also in this case, V_X covers all variables of V_Y.

The enumeration property follows simply from the fact that the  follows a free-top VO. 

It remains to show that all views can be computed in N^ time.
The proof follows closely prior work using view trees <cit.>. Let T be a tree in . 
We show by induction on the structure of T   that every view in T
can be computed in N^ time.




Base Case:
The base case states that each leaf atom can be computed in 
N^, which is obviously true. 

Induction Step:
Consider a projection view a V_X'((X))
in T.   
Such a view results from its single child view by projecting away 
X.
By induction hypothesis,  the view V_X can be computed in N^ time. Hence, it is of size N^. 
The view V_X' can be constructed from V_X by a single scan, which takes  
N^ time. 


Consider now a join view  V_X({X}∪(X)) in T.   
Let V_1(_1), …,  V_k(_k) be the child 
views of V_X.
By induction hypothesis, each child view can be computed 
in N^ time.
By construction of T, any variable that appears in at least 
two of the child views must be contained in the schema of V_X.
This mean that variables that do not appear in {X}∪(X)
cannot be join variables among the child views of V_X.
In each child view we project away 
all non-join variables that do not appear in {X}∪(X), 
using N^ time.  
Let V_1'(_1'), … ,V_k'(_k') be the resulting 
child views. 



Using a worst-case optimal join algorithm <cit.>, we 
then compute the view V_X from its child views 
in |V_X| time.


The size of V_X is upper-bounded by N^p where 
p = ρ^*_Q_X({X}∪(X))
and Q_X is the query that joins 
all atoms in the subtree rooted at V_X.
Since p ≤, the view V_X can be computed in N^ time.



§ MISSING DETAILS IN SECTION <REF>



In Section <ref>, we described how to evaluate a -query using a transition system.
We explain here how to build in N^2ρ^*((Q)) time
an index that allows us to move from the current state in the transition system to another state for a single-tuple update in constant time.

We first describe how to build an index that allows fast lookups of a state in the transition system for a given snapshot of the dynamic relations. 
Consider a dynamic relation R^d in Q.
As we discussed in Section <ref>, we restrict the domain of R^d to those values appearing in the static relations in Q, which is denoted by _R^d.
The size of _R^d is N^ρ^*((Q)).
We index the values in _R^d from 0 to |_R^d|-1. 
Each instance of R^d is a subset of the set {0, …, |_R^d|-1}.
We could represent this using a bitset that needs log |_R^d| bits, where each bit represents whether the corresponding tuple is in the instance of R^d.
In other words, we encode each instance of R^d as a bitset, i.e., an integer in {0, …, 2^|_R^d|-1}.
For a state (α_1, …, α_k), where α_i is an instance of the dynamic relation R^d_i, we encode (α_1, …, α_k) as a tuple (i_1, …, i_k), where i_j is the bitset that represents α_j.
It takes N^ρ^*((Q)) time to encode a state.

We create an index T that is a k-dimensional tensor, where each dimension corresponds to the bitsets representing the instances of a dynamic relation.
The entry T(i_1, …, i_k) with the indices (i_1, …, i_k) is a pointer pointing to the state that corresponds to the instances of the dynamic relations represented by the bitsets (i_1, …, i_k).
Each dimension has 2^N^ρ^*((Q)) entries.
For a given bitset, we can look it up in the corresponding dimension in log 2^N^ρ^*((Q)) time, which is N^ρ^*((Q)).
Therefore, for a tuple (i_1, …, i_k) of bitsets, we can look up the corresponding pointer in T in N^ρ^*((Q)) time.
In the preprocessing step, we create all states without transitions as described in Section <ref>, and then we fill in the entries of T.

We now create the transitions between the states.
Consider a state (α_1, …, α_k) and an insertion of a tuple a ∈_R^d_i∖α_i to a dynamic relation R^d_i.
We want to move to the state that contains additionally a, i.e., (α_1, …, α_i ∪{a}, …, α_k).
We encode (α_1, …, α_k) as a tuple (i_1, …, i_k) of bitsets in N^ρ^*((Q)) time and look up the pointer p = T(i_1, …, i_k) to this state from the tensor in N^ρ^*((Q)) time. 
We then create the transition: δ((α_1, …, α_k), +a) = p.
We do the same for the deletion of a tuple a ∈α_i, i.e., δ((α_1, …, α_k), -a) = p', where p' = T(i_1, …, i_k), 
and then the similar process for the other dynamic relations.  Overall, within one state, there can be N^ρ^*((Q)) transitions, so we spend N^ρ^*((Q))·N^ρ^*((Q)) = N^2ρ^*((Q)) time to find all pointers for the transitions in the state.

To allow for moving from one state to another state for a single-tuple update in constant time, we build a hash table that maps each value a ∈_R^d_i to the corresponding pointer to the next state.
The size of the hash table is N^ρ^*((Q)), and we can build it in N^ρ^*((Q)) time.

Overall, we can build the index for the transitions in N^2ρ^*((Q)) time.





§ MISSING DETAILS IN SECTION <REF>


We prove the lower bound in Theorem <ref>, which states:



Any Q ∉ without self-joins
cannot be evaluated 
with N preprocessing time, 1
update time, and 1 enumeration delay,
where N is the database size,
unless the OMv or the BMM conjecture fails. 


We first show a lower bound for the simple queries
Q_RST() = R^d(A), S^s(A,B), T^d(B)
and 
Q_ST(A) = S^s(A,B), T^d(B), which are both 
not included in .


Proposition <ref>.
For any Q ∉ without self-joins,  
there is no γ > 0 such that Q can be evaluated with N^3/2-γ preprocessing time, N^1/2-γ
update time, and N^1/2-γ enumeration delay, 
unless the Online Matrix-Vector Multiplication or the Boolean Matrix-Matrix Multiplication conjecture fails.





 §.§ Lower Bound for Q_RST

The lower bound for the query Q_RST() = R^d(A), S^s(A,B), T^d(B) relies on the OuMv conjecture, which is implied by the OMv conjecture <cit.>:

Proposition <ref>.
The CQ
Q_RST() = R^d(A), S^s(A,B), T^d(B) cannot be evaluated with 
N^3/2-γ preprocessing time, 
N^1/2-γ update time, and 
N^1/2-γ enumeration delay
for any γ >0, where N is the database size, unless the OuMv conjecture fails.


Assume that we have an Algorithm  that maintains the  
query Q_RST with N^3/2 - γ preprocessing time, 
N^1/2 - γ update time, and N^1/2 - γ enumeration delay
for some γ >0. 
We show that we can use the Algorithm  to solve the OuMv problem given by Definition <ref> in subcubic time, which contradicts Conjecture <ref>. 

Considering an n-by-n matrix M and n pairs of vectors (u_1, v_1), … , (u_n, v_n) that serve as the input to the OuMv problem, we construct an Algorithm  that uses
the static relation S^s(A, B) to encode M and the two dynamic relations R^d(A) and T^d(B) to encode the vector pairs (u_r, v_r)_r∈[n]. Next, we explain the encoding in detail. 

Algorithm  starts with the empty relations R^d(A), S^s(A, B) and T^d(B). First, it populates relation S^s(A, B) such that (i,j) ∈ S^s(A,B) if and only if M(i,j) = 1. After the initial population, the static relation S^s(A, B) does not accept any update. The two dynamic relations, R^d(A) and T^d(B), are empty before the first vector pair is given.
Then, it executes the preprocessing mechanism of Algorithm . 
In round 1, Algorithm  receives the vector pair (u_1, v_1) and updates R^d(A) and T^d(B) so that i ∈ R(A) if and only if u_1[i]= 1 and i ∈ T(B) if and only if v_1[i]= 1. We observe that u^T_1Mv_1 = 1 if and only if the (Boolean) result of Q_RST is true.
Algorithm  triggers the enumeration mechanism of  and outputs 1 if the result of Q_RST is true. Otherwise, it outputs 0. In each round, this procedure is repeated.

We analyse the overall time used by Algorithm . 
Given that M is an n× n matrix  M, the size and construction time of relation S^s are both n^2. It results in a database D of size |D| = n^2.
The preprocessing time is

    (n^2)^3/2 - γ = n^3 - 2γ

In each round r ∈ [n], Algorithm  executes at most 
4n updates to R^d(A) and T^d(B) and enumerates the first result of Q_RST. 
Since the database size remains n^2, the time to update the relations is

    2n · (n^2)^0.5 - γ = n^2 - 2γ

It is sufficient to enumerate the first result tuple to check if Q_RST is empty. 
The time to check emptiness is,

    (n^2)^0.5 - γ = n^1 - 2γ

Hence, for n rounds, the overall time is n^3-2γ. 
We conclude that the overall time Algorithm  takes to 
solve the OuMv problem is  n^3-2γ, thus contradicting Conjecture <ref> which rules out sub-cubic solutions for the OuMv problem.




 §.§ Lower Bound for the Query Q_ST



The CQ 
Q_ST(A) = S^s(A, B), T^d(B) cannot be evaluated with 
N^3/2-γ preprocessing time, 
N^1/2-γ update time, and 
N^1/2-γ enumeration delay
for any γ >0, where N is the database size, unless the OMv conjecture fails.


The proof is similar to that of Proposition <ref>. The main difference is the direct reduction from the OMv problem given by Definition <ref>. 

Assume there is an Algorithm  that maintains the  
query Q_ST with 
N^3/2-γ preprocessing time, 
N^1/2-γ update time, and 
N^1/2-γ enumeration delay
for some γ >0,
We show that the existence of Algorithm  contradicts Conjecture <ref>. 

We construct an Algorithm  that uses the static relation S^s(A, B) to encode the n-by-n matrix M and a dynamic relation T^d(B) to encode each vector v_r ∈ [n], where M and v_r ∈ [n] are the input to the OMv problem.

Algorithm  first populates relation S^s to reflect the non-empty entries in M.

Similar to the proof of Proposition <ref>, Algorithm  executes the preprocessing mechanism of Algorithm  in the beginning and n updates to T^d(B) when a vector v_r∈[n] arrives. To obtain the result of Mv_r∈[n], Algorithm  enumerates the result of Q_ST.

 
The static relation S^s dominates the size of the database |D| = n^2.
The preprocessing time of Algorithm  is,

    (n^2)^1.5 - γ = n^3 - 2γ

The total update and enumeration time over n rounds is,

    n · n · (n^2)^0.5 - γ = n^3 - 2γ

The subcubic processing time contradicts Conjecture <ref>.



 §.§ Proof of Proposition <ref>

Consider a CQ Q ∉. By definition of the 
class , one of the following cases holds: (1) Q is not 
free-connex acyclic, or (2) Q does not have safe atom-to-atom paths, or (3) Q does not have safe atom-to-variable paths. 
If Case (1) holds, then Q does not admit constant-delay enumeration after liner time preprocessing even without executing any updates <cit.>.  

In the sequel we show how we can reduce the the evaluation of 
one of the queries Q_RST and Q_ST if Case (2) or Case (3) holds for Q.
This reduction transfers the lower bound for Q_RST and Q_ST to Q.



  
*Violation of the Atom-to-Atom Path Property
Consider a CQ Q that does not have safe atom-to-atom paths. 
This means that the query  contains at least one path P of the form 
X_1, … , X_n that connects two dynamic atoms 
R̂^d( A) and T̂^d( B)  such that 
P ∩ A ∩ B = ∅.
This implies n ≥ 2. The path connecting  
the two dynamic atoms is illustrated in Figure <ref>. 





The idea of the reduction of the evaluation of the query 
Q_RST to the evaluation of the query Q is as follows. 
We use the relations on the path P to encode the static relation S^s and use the dynamic relations R̂^d
and T̂^d to encode the dynamic relations R^d
and T^d in Q. In particular, we use the 
variables 
X_1, …, X_n-1 to simulate the variable A and the variable X_n to simulate the 
variable B in Q_RST. This means, the variables X_1, … , X_n are assigned the same values. All other variables in Q are assigned a fixed dummy value. 

In the preprocessing stage, we construct the relations 
constituting the path P such that the above encoding is satisfied. Each update to R^d or T^d is translated into an update 
to R̂^d or respectively T̂^d. Observe that
the property 
P ∩ A ∩ B = ∅ ensures that 
the simulations of the variables A and B do not interfere with each other. 
Each enumeration request to Q_RST is translated into an enumeration request to Q. The answer of  Q_RST is true
if and only if the result of Q is non-empty. 

Before preprocessing, we first populate all the atoms on the path other than R^*() and T^*() such that they contain the following tuples (_k∈[n-1] = i, a), (X_n-1 = i, X_n = j, a) and (_n = j, a) if and only if (i, j) ∈ S^s(A, B).

All atoms not on the path are filled with (a). After the initial population, we suspend any updates to all the atoms other than R^*() and T^*().

Whenever R^d(X) or T^d(Y) is updated, we update the two dynamic relations R^*() and T^*() such that
    
    (i) ∈ R^d(A)  (X_1 = i, a) ∈ R^*()

    
    (j) ∈ T^d(B)  (X_n = j, a) ∈ T^*().





  
*Violation of the Atom-to-Variable Property

Assume that the query Q does not have safe atom-to-variable paths. This means that
the query  contains a path P of the form 
X_1, … , X_n that connects a dynamic atom 
T̂^d( B) with the free variable X_1 such that 
P ∩ B ∩(Q) = ∅.
The path in Q is illustrated in  Figure <ref>. 



of the evaluation of the query 
Q_RST to the evaluation of the query Q is as follows. 
We use the variables X_1, …, X_n-1 to simulate the variable A and the variable X_n to simulate the 
variable B in Q_RST. In particular, the variables X_1, … , X_n are assigned the same values. All other variables in Q are assigned a fixed dummy value. 

that with a path P that connects a free variables X_1 with a dynamic atom R^*(), as shown in Figure <ref>, such that it violates Safe Atom-to-Variable Path property by ∩ free(Q) ∩ P = ∅.
We use the dynamic relation T^*() to encode T^d(B) and all the rest atoms on the path P to encode the static relation S^s(A, B).





The idea of the reduction is similar to the previous case. 
We use the relations constituting the path to encode the static  relation S and use the dynamic relation  
T̂^d to simulate the dynamic relation T^d
In particular, we use the variables X_2, … , X_n
to simulate the variable B in Q_ST and use the free 
variable X_1 to simulate the free variable A in Q_ST. 



In the preprocessing stage 
We further assume that there is only one bound variable B ∈ on the path P. If the intersection contains variables other than B, such as ∩ P = {B, C}, we can shrink the path P to exclude them. Alternatively, we can copy the value of B to all other variables in . 

Before preprocessing, we first populate all the atoms on the path other than T^*() such that the following tuples are in the atoms on the path (X_i∈[n] = i, a), (X_n = i, B = j, a) and (B = j, a) if and only if (i, j) ∈ S^s(A, B).
All atoms not on the path are filled with (a).

Whenever T^d(B) is updated, we update T^*() such that

    (j) ∈ T^d(B)  (B = j, a) ∈ T^*().


We have now encoded Q_RST in Q^* that violates Safe Atom-to-Atom Path property and Q_ST in Q' that violates Safe Atom-to-Variable Path property. If the algorithm mentioned in Proposition <ref> exists, we can solve both Q_RST and Q_ST in subcubic time, thus violating Conjecture <ref> and <ref>.

