Order-Dependent Complexity of Enumeration and Direct Access for Conjunctive Queries on Dynamic Data

Order-Dependent Complexity of Enumeration and Direct Access for Conjunctive Queries on Dynamic Data Antoine Amarilli1,2 , Nofar Carmeli3 , and Clémence Dumoulin3 1

arXiv:2611.04519v1 [cs.DB] 3 Nov 2026

2

LTCI, Télécom Paris, Institut polytechnique de Paris, France Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRIStAL, France 3 Inria, LIRMM, Univ. Montpellier, CNRS, France

Abstract This note studies the fine-grained complexity of ranked enumeration and ranked direct access of conjunctive query answers over a dynamic database. We focus on lexicographically sorted answers, defined by an ordering on the query’s free variables. From the literature, when no particular order is required, we know that when the query is selfjoin-free and q-hierarchical, we can build a data structure for enumeration (resp. direct access) with linear (resp. linearithmic) preprocessing and constant (resp. logarithmic) update time in the size of the database. For enumeration (resp. direct access), this data structure yields an algorithm that enumerates all query answers (resp. that returns the kth query answer) with constant delay (resp. logarithmic access time). Our goal is to extend these results to ranked enumeration and ranked direct access, with the ranking function defined by a lexicographic order. We define a property on the order over the variables of Q, which we call being hierarchyconsistent. Given a user-specified query and hierarchy-consistent order, we first propose, for ranked enumeration under updates, an algorithm with linear preprocessing and logarithmic update time that enumerates all the query answers according to the user-specified order with constant delay. Moreover, for ranked direct access under updates, we propose an algorithm with linear preprocessing and logarithmic update time that returns the kth tuple according to the user-specified order with logarithmic access time. In contrast, given a user-specified query and non-hierarchy-consistent order, we show a lower bound for ranked direct access under updates.

1

Introduction

For a conjunctive query (or CQ) Q, given a database D, materializing the answers Q(D) can be costly: the number of answers |Q(D)| can be up to |D||Q| . Producing or holding the full answer set at once is therefore often impractical. Instead, it is more natural to find approaches that allow us to access partial information about the query result without materializing it. In particular, we may want to access the k th answer to Q on D, or to enumerate the answers one by one without repetitions. These tasks are typically formalized in database theory in two ways. The first one is enumeration: rather than producing all tuples at once, an enumeration algorithm outputs them one by one, with a guarantee of bounded delay between two consecutive tuples. The second one is direct access: this is the task of outputting, on an input k, the k th answer for Q over D. It is well-known from the work of Bagan, Durand, and Grandjean [BDG07] that we can enumerate the answers to self-join-free CQs with linear preprocessing and constant delay in data complexity provided that these queries satisfy the so-called acyclic free-connex condition; this restriction is (conditionally) necessary within the class of self-join-free CQs, and a characterization of tractable CQs with self-joins is still open [CS23, RCCS26]. What is more, Brault-Baron [BB13] has shown that direct access was possible with linearithmic preprocessing and logarithmic access time in data complexity. We also note the line of work on factorized databases [OS16], which represent query results compactly using a structure derived from the query, and enumerate the answers with constant delay when no particular order is required or when the user-defined order is compatible with this structure.

1

The literature has then extended these questions along two independent axes: supporting efficient updates to the underlying database (and updating the structure used for enumeration or direct access without recomputing it from scratch); and providing results in a specific order (e.g., in some lexicographic order specified by the user). The goal of the present work is to bridge these two directions. We present existing results on each of them in turn. First, in the dynamic setting, [BKS17] show that q-hierarchical conjunctive queries can be enumerated with constant delay and constant update time after linear preprocessing, and that for self-joinfree CQs this classification is (conditionally) optimal. An analogous result for direct access is shown in [Kep20]. Further works have investigated which guarantees could be provided for CQs beyond this class; this is not the focus of the present work, but we review these directions nevertheless. Dynamic Yannakakis [IUV17] maintains constant-delay enumeration for all free-connex queries (i.e., more generally than q-hierarchical conjunctive queries) with a more costly update time (namely, it is linear in the input database). This was then refined in [WHDY23] with an update cost that depends on the update sequence, which becomes constant for insertion-only sequences. We now review the different types of data structures that are used to show efficient enumeration and direct access guarantees on dynamic data; we will re-use some of them in the present work. [Kep20] use a circuit-like structure that stores the assignments of each variable of the q-tree in AVL trees. Circuits could also describe such a structure, but they are not so convenient to maintain in the dynamic setting, given that the domain of assignments is not fixed and updates add or remove edges of the circuit. In contrast, [KLN+ 25] use view-trees, whose interface and implementation can be defined separately; we re-use the structure of view-trees in the present paper. In all these works, the answers are produced in an arbitrary order determined by the data structure, and ranked enumeration or ranked direct access under updates is not handled. Second, for ranked enumeration or direct access in the static setting, where answers are output according to a ranking function, an important earlier work is [TGR25]. For acyclic free-connex queries, they build a data structure in linearithmic data complexity, after which the answers to Q on D can be enumerated in any lexicographic order with logarithmic delay between consecutive tuples. Ranked direct access, which returns the k-th answer in the user-defined order, has been studied by [CTG+ 23], who also build a data structure in quasilinear time, with logarithmic access time. Circuits, which are compact representations of the answers, have also been used for direct access, for conjunctive queries with negation [CCIS26], and for enumeration beyond conjunctive queries through knowledge compilation [Hu26]. None of these works considers updates to the database. Hence, our contribution sits at the intersection of these two lines of work: which orders can we support in the dynamic setting? Since we consider the dynamic setting, we build on the dichotomy established by [Kep20] (and [BKS17] for enumeration), which identifies q-hierarchical queries as the class for which linear preprocessing, constant delay or logarithmic access, and constant updates are possible under updates. We therefore restrict our attention to this class of queries, and we maintain the answers with view-trees [KLN+ 25]. Contributions. This note presents the preliminary results that we have obtained for ranked enumeration and ranked direct access to conjunctive queries under updates. We focus on q-hierarchical queries, because otherwise intractability holds (for self-join-free queries, and conditionally) even in the absence of ranking functions. We study lexicographic orders defined by an order on the query’s free variables, and introduce a condition on such orders, called being hierarchy-consistent. We show that, for hierarchy-consistent orders, we can perform ranked enumeration and ranked direct access following a lexicographic ordering, with the same favorable guarantees as in the case without a specific ordering, up to a logarithmic update time instead of constant update time for enumeration. By contrast, we show that, for non-hierarchy-consistent orders, a conditional intractability result rules out efficient ranked direct access. Paper structure. The paper is organized as follows: Section 2 introduces the notations and concepts necessary to understand the paper. In Section 3, we define the data structure used for ranked enumeration and ranked direct access in the dynamic setting, and give an algorithm to build it. In Section 4, we define a property on the user-defined order, called hierarchy-consistency, and give two algorithms for ranked enumeration and ranked direct access in the dynamic setting when the order satisfies this property, with bounds in combined complexity. In Section 5, we show that when the

2

order does not satisfy this property, ranked direct access in the dynamic setting is conditionally not achievable, in data complexity, with polynomial preprocessing, sublinear access time, and sublinear update time.

2

Preliminaries

2.1

Basic Notions

Database. A schema σ is a finite set of relation symbols {R1 , . . . , Rs }, with every R ∈ σ having a fixed arity ar(R). A database instance D is of the form D = {R1D , . . . , RsD } where, for each R ∈ σ, RD ⊆ domar(R) is a finite set of tuples (a1 , . . . , aar(R) ), and dom is a set of constant values called the domain, on which we assume a totalP order. The size |D| of the database instance D is the number of tuples that it stores, i.e. it is |D| := R∈σ |RD |. We fix an infinite set of variables denoted by vars. For a tuple t = (a1 , . . . , al ) indexed by variables (x1 , . . . , xl ) ∈ varsl and a set X ⊆ {x1 , . . . , xl }, we write t[X] for the restriction of t to the variables of X, preserving the order of t. Conversely, for a set of variables Y ⊇ {x1 , . . . , xl } ordered by a total order ≺ that agrees with (x1 , . . . , xl ) on {x1 , . . . , xl }, a tuple t′ indexed by Y is an extension of t if t′ [{x1 , . . . , xl }] = t, preserving the order ≺. Updates. We consider two types of updates: insertions and deletions. An insertion is defined as a command insert R(a1 , . . . , aar(R) ). Applied to a database instance D, this results in a database ′ instance D′ with RD := RD ∪ {(a1 , . . . , aar(R) )}. Similarly, a deletion is defined as a command delete R(a1 , . . . , aar(R) ). Applied to a database instance D, this results in a database instance D′ ′ with RD := RD \ {(a1 , . . . , aar(R) )}. Note that insert does not change D if the inserted tuple already exists in D; likewise, D is unchanged when we delete a tuple that D does not contain. Queries. A conjunctive query (CQ) is defined as Q(x̄) := ∃ȳ(ψ1 ∧ · · · ∧ ψd ) where x̄ := (x1 , . . . , xl ), ȳ := (y1 , . . . , yk ) and each ψi is an atom of the form R(z1 , . . . , zar(R) ). We mainly focus on CQs that are self-join-free, written SJFCQ, if no relation symbol occurs more than once in the query. For an atom ψ or a query Q, we write vars(ψ) ⊆ vars and vars(Q) ⊆ vars for the set of variables occurring in ψ and Q, respectively. For a variable x ∈ vars(Q), we denote by atomsQ (x) the finite set of atoms in Q in which x appears, i.e. atomsQ (x) = {ψ ∈ Q | x ∈ vars(ψ)}. Moreover, the set of variables vars(Q) is partitioned into free variables free(Q) := {x1 , . . . , xl } and quantified variables {y1 , . . . , yk }. In addition, for a CQ Q(x̄) := ∃ȳ(ψ1 ∧ · · · ∧ ψd ) and a set of variables X ⊆ free(Q), the projection of Q over X, denoted by ΠX (Q), is the CQ defined as ΠX (Q) := ∃ȳ∃(x̄ \ X)(ψ1 ∧ · · · ∧ ψd ). Finally, given a query Q(x1 , . . . , xl ) and a database instance D, the set of answers to Q over D, i.e. the set of tuples resulting from applying Q to D, is defined as Q(D) := {(a1 , . . . , al ) ∈ doml | D |= Q(a1 , . . . , al )}. Note that ΠX (Q)(D) = {t[X] | t ∈ Q(D)}, i.e., the answers of the projection of a query over X are the restrictions of its answers to X.

2.2

Problem Definition

The model of computation is the RAM model with uniform cost measure and word size Θ(log n). Under this assumption, additions and multiplications on integers of size O(log n), as well as lookup table and array accesses, take constant time. Given this computation model, we consider two query evaluation problems throughout this paper: ranked enumeration under updates and ranked direct access under updates. To define these problems, we first need to introduce the notion of orders. Order on answers. Let D be a database instance, Q a query, and ≺ a total order over free(Q). Let (x1 , . . . , xl ) be the free variables of Q listed according to this order. We define an order on answers ≺ on Q(D) induced by ≺, called the lexicographic order, as follows. For two answers t1 , t2 ∈ Q(D), we say that t1 ≺ t2 if there exists j ∈ [l] such that we have t1 [xi ] = t2 [xi ] for all i < j and we have t1 [xj ] < t2 [xj ], where < denotes the total order on the domain values.

3

Enumeration. The enumeration problem consists of two phases. Given a database instance D and a query Q, the preprocessing phase builds a data structure D. The enumeration phase outputs all tuples in Q(D) without repetition, and finally emits a special value end-of-enumeration to signal the end of enumeration. We consider several extensions of this problem. First, if a total order ≺ over free(Q) is given before the preprocessing, the task of ranked enumeration asks us to output all tuples in Q(D) in the lexicographic order ≺ on Q(D) induced by ≺. Second, if an update command (insert R(a1 , . . . , aar(R) ) or delete R(a1 , . . . , aar(R) )) is issued after the preprocessing, letting D be the original database instance and D′ be the database instance obtained by applying the update command to D, then the task of enumeration under updates asks us to modify the data structure D to a data structure D’ that represents the updated database instance, i.e., which allows us to enumerate the tuples of Q(D′ ). If the update command occurs during the enumeration phase, we interrupt enumeration and restart it from scratch on the new database D′ . Combining both variants, the ranked enumeration under updates is the version where we are given the database instance D, the query Q, and a total order ≺ over free(Q), and where we must be able to enumerate tuples of Q(D) in the order ≺ and also support updates to D in the sense above. Direct access. The direct access problem consists of two phases. Given a database instance D and a query Q, the preprocessing phase builds a data structure D. Then, in the access phase, we receive user queries consisting of an index k ≥ 0, and we must return the k th tuple of Q(D) in an implementationdefined order, or a special value out-of-bounds if k ≥ |Q(D)|. We again extend this problem to support lexicographic orders and to support updates. First, if a total order ≺ over free(Q) is given with D and Q before the preprocessing, then the task of ranked direct access asks us to support access queries where the implementation-defined order on tuples must coincide with the lexicographic order ≺ on Q(D), induced by ≺. Second, the task of ranked direct access under updates asks us to support update commands (insert R(a1 , . . . , aar(R) ) or delete R(a1 , . . . , aar(R) )) after the preprocessing, and again we must modify the data structure D so that it represents the updated database instance D′ and can be used to access tuples in the new set of answers Q(D′ ). Combining both variants, the ranked direct access under updates problem is the version where we are given the database instance D, the query Q, and a total order ≺ over free(Q), and where we must be able to support queries on the lexicographic order induced by ≺ and also to support updates to D in the sense above. Complexity measures. For the query evaluation problems defined earlier, we measure complexity using combined complexity, i.e., as a function of the database size |D| and of the size |Q| of the query Q, i.e., the length of Q when written as a word over the alphabet σ ∪ vars(Q) ∪ {∃, ∧, (, )}. For each query evaluation problem, we consider the preprocessing time tp , the update time tu when supporting updates, and either the delay time td for enumeration problems or the access time ta for direct access problems. For ranked enumeration (with or without updates), the delay time td is the maximum time between any two consecutive outputs, before the first output, and between the last output and the special value end-of-enumeration. For ranked direct access (with or without updates), the access time ta is the time to return the k th tuple or the special value out-of-bounds. Let fp , fd , fa and fu be numeric functions. For ranked enumeration under updates (resp., ranked direct access under updates), an algorithm is said to be in time ⟨fp , fd , fu ⟩ (resp., ⟨fp , fa , fu ⟩, if for every database instance D and query Q, we have the preprocessing time tp = O(fp (|D|, |Q|)), the delay time td = O(fd (|D|, |Q|)) (resp., the access time ta = O(fa (|D|, |Q|))) and the update time tu = O(fu (|D|, |Q|)). Note that the task of (ranked) direct access (under updates) generalizes the task of (ranked) enumeration (under updates). Indeed, for every numeric function fp , f, fu , if we have an algorithm in time ⟨fp , f, fu ⟩ for (ranked) direct access under updates, then we have an algorithm in time ⟨fp , f, fu ⟩ for (ranked) enumeration under updates, and likewise without updates. We can perform (ranked) enumeration (under updates) with (ranked) direct access (under updates) as follows. Once the data structure D is built, in O(fp (|D|)), from a q-hierarchical SJFCQ Q, a database instance D and whenever it exists, an order ≺ over free(Q), we can return the k th answer for k = 1, 2, 3, . . . in several queries in the access phase, with O(f (|D|)) delay. Finally, whenever an update occurs, we modify D in O(fu (|D|)), and restart queries in the access phase with k = 1.

4

2.3

Initial Observations

The complexity of enumeration and direct access of conjunctive queries on dynamic data was studied in [Kep20], which introduced the class of q-hierarchical CQs. We now recall the definition of this class and the lower bounds and upper bounds that it yields. Definition 2.1. A CQ Q is q-hierarchical if for any two variables x1 , x2 ∈ vars(Q) the following is satisfied: (i) atomsQ (x1 ) ⊆ atomsQ (x2 ) or atomsQ (x1 ) ⊇ atomsQ (x2 ) or atomsQ (x1 ) ∩ atomsQ (x2 ) = ∅, and (ii) if atomsQ (x1 ) ⊊ atomsQ (x2 ) and x1 ∈ free(Q), then x2 ∈ free(Q). It was shown in [Kep20] that, for SJFCQs that are not q-hierarchical, some complexity lower bounds apply to enumeration under updates and direct access under updates, even in the non-ranked versions. These lower bounds are conditional to the OMv-conjecture, which we introduce below. OMv-conjecture The Online Matrix-vector multiplication (OMv) problem is defined as follows. We are given an n × n Boolean matrix M , on which we allow arbitrary polynomial preprocessing. Then, a sequence of n Boolean vectors ⃗v1 , . . . , ⃗vn of dimension n is given online, one vector at a time. For each i ∈ [n], we must output M⃗vi before receiving ⃗vi+1 . The complexity measure is the total running time required to output all vectors M⃗vi . The OMv conjecture states that no algorithm solves the OMv problem in time O(n3−ε ) for any ε > 0. We now recall the lower bounds on enumeration under updates and direct access under updates from [Kep20]. Theorem 2.2 ([Kep20, Theorem 3.13]). Fix a number ε > 0 and a self-join-free conjunctive query Q. If Q is not q-hierarchical, there is no algorithm with polynomial preprocessing time and O(|D|1−ε ) update time that enumerates Q(D) with O(|D|1−ε ) delay in data complexity, unless the OMv-conjecture fails. Theorem 2.3 ([Kep20, Theorem 3.16]). Fix a number ε > 0 and a self-join-free conjunctive query Q. If Q is not q-hierarchical, there is no algorithm with polynomial preprocessing time and O(|D|1−ε ) update time that solves the direct access problem in time O(|D|1−ε ) delay in data complexity, unless the OMv-conjecture fails. In contrast, it was also shown in [Kep20] that, for q-hierarchical SJFCQs, there are algorithms for efficient enumeration under updates and efficient direct access under updates. Theorem 2.4 ([BKS17, Theorem 3.2]). There is an algorithm that receives a q-hierarchical SJFCQ Q and a database instance D, and computes within O(|Q|O(1) |D|) preprocessing time a data structure that can be updated in time O(|Q|O(1)) and allows the following: 1. enumerate Q(D) with delay O(|Q|O(1) ) Theorem 2.5 ([Kep20, Theorem 3.9]). There is an algorithm that receives a q-hierarchical SJFCQ Q and a database instance D and computes within preprocessing time O(|Q|O(1) |D| log |D|) a data structure that can be updated in time O(|Q|O(1) log |D|) and allows the following: 1. output the query result size |Q(D)| in time O(1) and, 2. enumerate the tuples in Q(D) in lexicographic order according to the implementation order with delay O(|Q|O(1) ) and, 3. upon input of an arbitrary k, takes time O(|Q|O(1) log |D|) to immediately output the k th answer that the enumeration procedure of (2) would have output In the next section, we will review proof techniques used to show these results because we will extend them for our own results. In light of the lower bounds of Theorem 2.2 and Theorem 2.3, we will focus on q-hierarchical SJFCQs throughout the paper. Our goal is to investigate how this complexity picture is affected for ranked enumeration under updates and ranked direct access under updates as defined previously. 5

3

Data Structures: Q-Trees, View-Trees, and Grounded-Trees

In this section, we define the data structure built in the preprocessing phase from the q-hierarchical SJFCQ and the database instance given as input. This data structure is from [KLN+ 25], and we call it a grounded-tree. As we study combined complexity, we present an algorithm from [Kep20] to build a so-called q-tree for a given q-hierarchical SJFCQ. We then define from this the notions of view-trees and grounded-trees, and we show how to build grounded-trees from a q-hierarchical SJFCQ and a database instance.

3.1

From Q-trees to Grounded-Trees

In this part, we define the data structure built in the preprocessing by giving the definitions of q-trees, view-trees, and grounded-trees. We recall the definition of q-trees from [Kep20]. Definition 3.1. Let Q be a q-hierarchical CQ. A q-tree for Q is a directed tree TQ = (VQ , EQ ) with VQ = vars(Q) ∪ {vroot } rooted in vroot where 1. for all atoms ψ in Q, the set vars(ψ) ∪ {vroot } forms a directed path starting in TQ at vroot , and 2. free(Q) ∪ {vroot } is a connected subset in TQ . A CQ Q is q-hierarchical if and only if it admits a q-tree [Kep20, Lemma 4.2]. For each v ∈ VQ , we denote by ancTQ (v) the ancestors of v in TQ , including vroot . We can then define the following as in [KLN+ 25]: Definition 3.2. Let Q be a q-hierarchical SJFCQ and TQ = (VQ , EQ ) one of its q-trees. Let TQext = ext (VQext , EQ ) be the extended q-tree of TQ which is defined as follows: we have VQext = VQ ∪ {ψ | ψ ∈ Q} ext and EQ = EQ ∪ {(xi , ψi ) | xi ∈ vars(ψi ) with xi the farthest variable from vroot in TQ }. The viewΠ ext ⋊ } and edge set | (u, v) ∈ EQ | v ∈ VQext } ∪ {V(u,v) tree V (TQ ) is the rooted tree with vertex set {Vv⋉ Π ext ⋊ ⋊ Π Π ⋊ or V(u,v) is associated ) | (u, v) ∈ EQ , v a child of u}, where each node Vv⋉ , Vv⋉ {(Vu⋉ , V(u,v) ), (V(u,v) Π ⋉ ⋊ to a view Wv or W(u,v) which is a relational algebra expression defined as follows: ⋊ (i) for each leaf v ∈ VQext labeled by an atom ψ := R(x1 , . . . , xar(R) ) then the view associated to Vv⋉ ⋉ ⋊ := ψ, is Wv ⋊ is (ii) for each internal vertex v ∈ VQext with children v1 , . . . , vk , then the view associated to Vv⋉ Π Π ⋉ ⋊ := W(v,v1 ) ⋊ ⋉ ··· ⋊ ⋉ W(v,vk ) , Wv Π Π ⋊ ext := Π(ancTQ (u)∪{u})\{vroot } Wv⋉ , then the view associated to V(u,v) is W(u,v) . (iii) for each edge (u, v) ∈ EQ

Given a database instance D, we now enrich the view-tree V (TQ ) with the data of D, which gives ⋊ Π a grounded-tree VD (TQ ). Each vertex Vv⋉ (resp. V(u,v) ) in the view-tree V (TQ ) is associated to a table ⋉ ⋊ Π ⋉ ⋊ Π ⋊ Π (resp. W(u,v) ). In particular, for Zv (resp. Z(u,v) ) such that Zv (resp. Z(u,v) ) is the evaluation of Wv⋉ ⋉ ⋊ ⋉ ⋊ D every leaf VR labeled by an atom R(x1 , . . . , xar(R) ), then ZR := R . The other views of VD (TQ ) are then computed bottom-up from the leaf views, following their definitions. Note that some projection Π views are defined on the same set of variables as their child. For instance, in Figure 1, the view W(x 2 ,R) ⋊ ⋉ ⋊ Π is identical to WR⋉ , therefore Z(x = Z . We do not try to remove these redundant views, because R 2 ,R) doing so would complicate the definitions and would not improve the asymptotic complexities of our algorithms. In addition, whenever you have a vertex V with associated view W and a child Vi , then letting Z and Zi be the tables respectively associated to them, for each tuple t ∈ Z, we denote by buckett (Zi ) ⋊ the set of tuples t′ ∈ Zi such that t′ [free(W )] = t. Note that for a variable xi , the vertex Vx⋉ has i Π ⋉ ⋊ Π several children V(xi ,xj ) in V (TQ ). For each tuple t ∈ Zxi and each V(xi ,xj ) of Vxi , we have that Π Π ⋊ . For buckett (Z(x ) has exactly one tuple. A projection view V(x has exactly one child view Vx⋉ j i ,xj ) i ,xj ) Π ⋉ ⋊ ′ each tuple t ∈ Z(xi ,xj ) , there exists buckett (Vxj ) with several tuples t which are extensions of t over ancTQ (xj ) ∪ {xj } \ {vroot }.

6

⋊ Vv⋉ () root () Π V(v

root ,x1 )

()

() ⋊ (x ) Vx⋉ 1 1 b1 b3

Π V(x (x1 ) 1 ,x2 ) b1 b3

vroot

Π V(x (x1 ) 1 ,T ) b1 b3 b4

x1 ⋊ (x , x ) Vx⋉ 1 2 2

x2 R(x1 , x2 )

T (x1 )

b1 b3 b3

c1 c1 c3

b3 b4

x1

x2

b1 b3 b3

c1 c1 c3

(c) Q1 (D)

S(x1 , x2 )

ext (a) Extended q-tree TQ 1

⋊ VT⋉ (x1 ) b1

Π V(x (x1 , x2 ) 2 ,R) b1 c1 b2 c2 b3 c1 b3 c3

Π V(x (x1 , x2 ) 2 ,S) b1 c1 b2 c1 b3 c1 b3 c3

⋉ ⋊ VR (x1 , x2 ) b1 c1 b2 c2 b3 c1 b3 c3

⋊ VS⋉ (x1 , x2 ) b1 c1 b2 c1 b3 c1 b3 c3

(b) Grounded-tree for V (TQ1 )

Figure 1: Representation of an extended q-tree, grounded-tree, and query result for Q1 (D) (see Example 3.3) Example 3.3. Figure 1 represents an extended q-tree and its grounded-tree for the query Q1 (x1 , x2 ) = ⋉ ⋊ ⋊ R(x1 , x2 ) ∧ S(x1 , x2 ) ∧ T (x1 ), where by definition of a grounded-tree ZR (x1 , x2 ) := R, ZS⋉ (x1 , x2 ) := S ⋉ ⋊ and ZT (x1 ) := T , and for the database instance D given by the relations R, S and T . Note that the q-tree TQ is the subtree of Figure 1 in black. In addition, for the tuple t = (b3 ) shown ⋊ in gray, the tuples t′ ∈ bucket(b3 ) (Vx⋉ ) are in a lighter gray. 2

3.2

Data Structure Implementation

In this section, we first describe the implementation of the data structure defined previously, inspired by [Kep20], using lookup tables and B + -trees. We then present the algorithms that we use when performing the preprocessing on this data structure. B + -trees. Given a set of tuples S and a ranking function f that maps each tuple of S to a value of an ordered domain, a B+ -tree for (S, f ) is a balanced search tree that stores S in sorted order according to f . More precisely, all leaves are at the same depth, and each leaf stores a bounded number of consecutive tuples in the order f , whereas the internal nodes only store keys and pointers that guide the search for a specific tuple. Moreover, the leaves are chained in a linked list following f . It is well known that B + -trees admit algorithms allowing us to insert a tuple, delete a tuple, retrieve a tuple, and retrieve the minimum tuple for f each in time O(log |S|), since the height of the tree is logarithmic in the number of stored tuples. What is more, given a pointer to a tuple stored in the tree, accessing the tuple that follows it in the order induced by f takes time O(1), by moving to the next tuple of the same leaf or, at the end of a leaf, by following the pointer to the next leaf.

7

Grounded-tree implementation. Let V be a vertex of the view-tree V (TQ ), let W be the view associated to V , let Z be the table associated to V , and let V ′ be the parent of V . To navigate each table Z efficiently, we group all tuples t ∈ Z by their restriction t′ to free(W ′ ). We implement each table Z as a lookup table whose keys are all tuples t′ ∈ Z ′ and whose value for each t′ is buckett′ (Z). For each buckett′ (Z), given a ranking function fbuckett′ (Z) that maps each t ∈ buckett′ (Z) to a value of an ordered domain, we store buckett′ (Z) in a B + -tree sorted according to fbuckett′ (Z) . Therefore, given a table Z and a key t′ ∈ Z ′ , accessing the B + -tree buckett′ (Z) takes constant time since Z is a lookup table. Besides, given buckett′ (Z) and a ranking function fbuckett′ (Z) , since each bucket is a B + -tree for (buckett′ (Z), fbuckett′ (Z) ), inserting or deleting a tuple t in buckett′ (Z) while keeping it sorted according to fbuckett′ (Z) takes time O(log |D|). Further, given a pointer to a tuple in buckett′ (Z), retrieving its successor takes constant time.

3.3

Preprocessing

We next show how to build the grounded-tree from a SJFCQ Q. To do so, we first build a q-tree TQ , extend it to a view-tree V (TQ ), and, given a database instance D, we enrich V (TQ ) into a groundedtree with all the database facts from D. We now recall the combined complexity of building a q-tree, given a q-hierarchical CQ. Lemma 3.4 ([Kep20, Lemma 4.2]). A CQ Q is q-hierarchical if and only if Q has a q-tree. Moreover, there is an O(|Q|O(1) ) algorithm that decides whether an input CQ Q is q-hierarchical, and if so, outputs a q-tree. Given a database instance D, a q-hierarchical SJFCQ Q, and a q-tree TQ for Q, we now show how to build the grounded-tree for TQ in the preprocessing phase. We can show a preprocessing upper bound in O(|D| · |Q|) using the fact that we can sort in linear time in the RAM model [Gra96]. Proposition 3.5. There exists an algorithm that, given a q-hierarchical SJFCQ Q, one of its q-trees TQ , and a database instance D, builds the grounded-tree VD (TQ ), in which each bucket b is sorted by a given ranking function fb , in time O(|D||Q|). Note that if one wants to avoid linear-time sorting algorithms, the preprocessing can instead be performed in time O(|D| · |Q| log |D|), using any linearithmic sorting algorithm. We can now prove Proposition 3.5: Proof of Proposition 3.5. For a given q-hierarchical SJFCQ Q and one of its q-trees TQ , we first compute the extended q-tree TQext in time O(|Q|) by adding, for each atom ψ ∈ Q, a leaf ψ as a child of the farthest variable xi from vroot in TQ such that xi ∈ vars(ψ). Afterwards, we compute the ⋊ Π view-tree V (TQ ) by traversing TQext while adding Vv⋉ for each vertex v ∈ TQext , and V(u,v) for each ext edge (u, v) ∈ TQ , in time O(|Q|). We then initialize all tables to the empty table by creating an empty table Z for each vertex V of the view-tree, giving us the empty grounded tree VD (TQ ). Given a ⋉ ⋊ := RD for every relation R of D. We then propagate the tuples database instance D, we then set ZR bottom-up as follows. Let V be a vertex, let Vi be a child of V , let Z and Zi be the tables associated to V and Vi , and let W be the view associated to V . For each table Zi , we evaluate the view Wi and group the tuples of Zi into buckets according to their restriction to free(W ): each tuple t′ ∈ Zi is placed in the bucket buckett (Zi ) with key t = t′ [free(W )]. If W is a projection view, then Z contains the keys t of the buckets of its only child Zi . If W is a join view, we fix one child Vi and scan the keys t of the buckets of Zi ; for each of them, we check in constant time per other child Vj that buckett (Zj ) exists, and t is added to Z only if all these buckets exist. Every table has at most |D| tuples: the leaves are relations of D, a projection view has at most as many tuples as its child, and a join view has at most as many tuples as any of its children. Hence, a projection vertex is processed in time O(|D|), and a join vertex in time O(|D|) per child. Since the sum of the number of children over all vertices is the number of edges of the view-tree, which is O(|Q|), all views are evaluated in time O(|Q| · |D|). Using the fact that we can sort in linear time in the RAM model [Gra96], we then sort each buckett (Zi ) according to its ranking function fbuckett (Zi ) and build, for each bucket, a B + -tree from the sorted list in linear time. Each table Z contains at most |D| tuples in total, separated into several buckets, so this takes O(|D|) per table, and O(|Q| · |D|) overall. Hence, there exists an algorithm that builds a grounded tree VD (TQ ), in which each bucket buckett′ (Z) is sorted according to fbuckett′ (Z) , in time O(|Q| · |D|). 8

For the query evaluation problems we tackle throughout this paper, we can therefore build a grounded-tree for a q-hierarchical SJFCQ Q in time O(|Q|O(1) + |Q| · |D|), i.e., linear preprocessing in data complexity, by building one of its q-trees with Lemma 3.4 and applying Proposition 3.5.

4

Hierarchy-Consistent Orders

We now define a notion of order on the free variables of a q-hierarchical CQ. Definition 4.1. Let Q be a q-hierarchical CQ. Then, Q induces a partial order on free(Q) where xi <Q xj if atomsQ (xj ) ⊊ atomsQ (xi ). A total order ≺ on free(Q) is hierarchy-consistent for Q if it is a linear extension of this partial order. Given a q-hierarchical CQ Q, and a hierarchy-consistent order ≺ over free(Q), we now want to perform ranked enumeration and ranked direct access. To do so, we need to build a data structure adapted to ≺. We therefore want a q-tree, used to build the data structure, in which ≺ can be obtained easily, for instance by a topological sort. It follows from the proof of [Kep20, Lemma 4.2] that several q-trees may represent a q-hierarchical CQ Q. However, every hierarchy-consistent order ≺ cannot be obtained by a topological sort of any q-tree. Indeed, for each pair x1 , x2 ∈ vars(Q), whenever atomsQ (x1 ) = atomsQ (x2 ) and x1 ∈ free(Q) ⇐⇒ x2 ∈ free(Q), the ancestor-descendant relation between these variables may vary: in one q-tree x2 is an ancestor of x1 , while in another x1 is an ancestor of x2 , as shown in Figure 2. Thus, a hierarchy-consistent order where x1 < x2 cannot be obtained by a topological sort of the first q-tree. We make this clearer with an example: Example 4.2. Let Q(x1 , x2 , x3 , x4 ) := R(x1 , x2 , x4 ) ∧ S(x3 , x4 ) be a q-hierarchical CQ. The linear extension ≺ such that vroot ≺ x4 ≺ x3 ≺ x2 ≺ x1 is a topological sort of T1 but cannot be obtained by a topological sort of T2 in Figure 2. vroot

vroot

x4

x4

x3

x2

x3

x1

x1

x2

(a) T1

(b) T2

Figure 2: Q-trees for Q(x1 , x2 , x3 , x4 ) := R(x1 , x2 , x4 ) ∧ S(x3 , x4 ) Hence, in the preprocessing phase, we build a compatible q-tree for the order ≺, defined as follows. Definition 4.3. Let Q be a q-hierarchical CQ, TQ one of its q-trees, and ≺ a hierarchy-consistent order on free(Q). We say TQ is compatible with ≺ if ≺ is the restriction to free(Q) of a topological order of TQ . We now show that such a q-tree exists, strengthening [Kep20, Lemma 4.2] (which we had restated previously as Lemma 3.4). Claim 4.4. Given a q-hierarchical CQ Q and a hierarchy-consistent order ≺ on its free variables, we can build a q-tree TQ compatible with ≺ in O(|Q|O(1) ). Proof. To build such a q-tree compatible with a hierarchy-consistent order ≺, we adapt the algorithm from [Kep20, Lemma 4.2] using ≺ to break ties when, for x1 , x2 ∈ free(Q), we have atomsQ (x1 ) = atomsQ (x2 ). This algorithm builds a q-tree TQ of Q such that each path of TQ is a path of the form vroot , x1 , . . . , xs where atomsQ (xs ) ⊆ · · · ⊆ atomsQ (x1 ). In this algorithm, when for two variables x1 , x2 ∈ free(Q), we have atomsQ (x1 ) = atomsQ (x2 ), we choose arbitrarily which variable will be the ancestor of the other. To get a q-tree in which ≺ is a topological sort, we break this tie following the order ≺, i.e., when for two variables x1 , x2 ∈ free(Q), we have atomsQ (x1 ) = atomsQ (x2 ), if x1 ≺ x2 then x1 is an ancestor of x2 , otherwise x2 is an ancestor of x1 . 9

Before showing how to achieve ranked enumeration (resp. direct access) under updates for a hierarchy-consistent given order, we first show that, when the database changes due to the insertion or deletion of a tuple, we can update the grounded-tree in time O(log |D|). Recall that in a grounded-tree, each bucket b is sorted by a ranking function fb . When the order ≺ used to build the grounded-tree is hierarchy-consistent, we define these ranking functions as the lexicographic ranking functions induced by ≺. Let V be a non-root vertex of the grounded tree VD (TQ ), let W be the view associated to V , let Z be the table associated to V , and let V ′ be the parent of V with associated view W ′ . Let Q be a q-hierarchical CQ, let ≺ be the hierarchy-consistent order over free(Q), let TQ be a q-tree for Q compatible with ≺, and let D be a database instance. We extend ≺ arbitrarily to a topological order of TQ over all of vars(Q). For each bucket buckett′ (Z) of the grounded tree VD (TQ ), the lexicographic ranking function fbuckett′ (Z) , induced by ≺ over vars(Q), is simply the identity: fbuckett′ (Z) (t) := t for every t ∈ buckett′ (Z), where the domain is the set of tuples over free(W ) ordered lexicographically according to ≺. In other words, for all t1 , t2 ∈ buckett′ (Z), we have fbuckett′ (Z) (t1 ) ≺ fbuckett′ (Z) (t2 ) if and only if t1 ≺ t2 , where ≺ is the lexicographic order induced by ≺. Lemma 4.5. Let Q be a q-hierarchical SJFCQ, ≺ a hierarchy-consistent order over free(Q), TQ a q-tree for Q compatible with ≺, and D a database instance. Let VD (TQ ) be the grounded-tree for TQ and D whose buckets b are sorted using the lexicographic ranking functions fb defined by ≺. Given an update command update R(a1 , . . . , aar(R) ), let D′ be the database instance obtained by applying update R(a1 , . . . , aar(R) ) to D. There exists an algorithm that, given VD (TQ ) and given an update R(a1 , . . . , aar(R) ), computes in time O(|Q| log |D|) the grounded tree VD′ (TQ ), whose buckets b are sorted using the lexicographic ranking functions fb . Proof. Let VD (TQ ) be a grounded-tree and for each bucket of VD (TQ ), let its tuples be sorted lexicographically. Let update R(a1 , . . . , aar(R) ) be an update of a tuple t := R(a1 , . . . , aar(R) ), and let D′ be the database instance obtained by applying update R(a1 , . . . , aar(R) ) to D. We build VD′ (TQ ) by inserting or removing database facts from VD (TQ ) as follows. We distinguish two cases depending on the kind of update. ⋉ ⋊ (X ∪Y ) with X the set of free variables of the view When the update is an insertion, for the table ZR ⋉ ⋊ ⋉ ⋊ Π W(xi ,R) , we insert t in the bucket buckett[X] (ZR ). Accessing buckett[X] (ZR ) takes constant time, and ⋉ ⋊ ⋉ ⋊ inserting t in buckett[X] (ZR ) while keeping buckett[X] (ZR ) sorted lexicographically takes logarithmic ⋊ ⋊ time. Then, we propagate the insertion upwards in VD (TQ ) on the path from VR⋉ to Vv⋉ as follows. root ⋉ ⋊ ′ Π ′ Π When we insert a tuple t in a buckett′ (Zxj ), with t = t[W(xi ,xj ) ], we insert t in buckett′′ (Z(x ) i ,xj ) ′′ ′ Π ′ Π where t = t [free(W(xi ,xj ) )]. If t already exists in buckett′′ (Z(xi ,xj ) ), the propagation stops. OthΠ ⋊ ⋊ erwise, when we insert a tuple t in buckett′ (Z(x ) with t′ = t[Wx⋉ ], we insert t′ in buckett′′ (Zx⋉ ) i i i ,xj ) ′′ ′ ⋉ ⋊ Π where t = t [Wxi ], if and only if t exists in all Z(xi ,xk ) for each child xk of xi in the extended q-tree. Π It is equivalent to checking if buckett (Z(x ) exists, which takes constant time. In the worst case, i ,xk ) ⋉ ⋊ we propagate an update until Vvroot , which takes O(|Q| log |D|). ⋉ ⋊ When the update is a deletion, for the table ZR (X ∪ Y ) with X the set of free variables of the ⋉ ⋊ ⋉ ⋊ Π ) takes constant time, and view W(xi ,R) , we remove t from buckett[X] (ZR ). Accessing buckett[X] (ZR ⋉ ⋊ ⋉ ⋊ removing t from buckett[X] (ZR ) while keeping buckett[X] (ZR ) sorted lexicographically takes logarithmic time. Let t := (a1 , . . . , aar(R) ) be the deleted tuple. Then, we propagate the deletion upwards in ⋊ ⋊ ⋊ VD (TQ ) on the path from VR⋉ to Vv⋉ as follows. When we delete a tuple t from a buckett′ (Zx⋉ ), with root j ′ Π ⋉ ⋊ ′ Π t = t[free(W(xi ,xj ) )], if buckett′ (Zxj ) becomes empty, we remove t from buckett′′ (Z(xi ,xj ) ), which ⋊ takes time O(log |D|). If there still exists a tuple in buckett′ (Vx⋉ ) the propagation stops. When we j Π ′ ⋉ ⋊ ⋊ delete a tuple t in buckett′ (Z(xi ,xj ) ), with t = t[free(Zxi )], we remove t′ from buckett′′ (Zx⋉ ), where i ′′ ′ t = t [ancTQ (xi )] if it exists; otherwise, the propagation stops. In the worst case, we propagate a ⋊ deletion until Vv⋉ , which takes O(|Q| log |D|). Hence, an update takes O(|Q| log |D|). root We can now show how to achieve ranked enumeration under updates when the order in the input is hierarchy-consistent.

10

4.1

Ranked Enumeration Under Updates

In this part, given a q-hierarchical SJFCQ Q and a database instance D, we propose an enumeration algorithm in ⟨|D||Q|, |Q|, |Q| log |D|⟩ delay in combined complexity, i.e., linear preprocessing, logarithmic update, and constant delay times in data complexity, when the order on the free variables of Q is hierarchy-consistent. Theorem 4.6. There exists an algorithm that, given a q-hierarchical SJFCQ Q, a hierarchy-consistent total order ≺ on its free variables, a q-tree TQ for Q compatible with ≺ and a database instance D, enumerates Q(D) in the lexicographic order defined by ≺ with O(|D||Q|) preprocessing, O(|Q| log |D|) update time, and O(|Q|) delay. Proof. Given a q-hierarchical SJFCQ Q, a database instance D, and a hierarchy-consistent order ≺ over free(Q), we apply the preprocessing procedure to build the grounded-tree VD (TQ ) using Proposition 3.5. Then, when updates arrive, we handle them using Lemma 4.5. Hence, all that remains is to explain how to perform ranked enumeration, which we now present. Let x1 , . . . , xl be the free variables of Q listed according to ≺. Algorithm 1 is written as nested loops over x1 , . . . , xl for readability. In this algorithm, we traverse the grounded-tree VD (TQ ) from top to bottom to build each answer tQ(D) of the enumeration. For a non-root variable xj , the ⋊ Π ) to traverse is determined by a tuple t′ chosen in table Z(x . Recall that bucket buckett′ (Zx⋉ j i ,xj ) ′ Π ⋉ ⋊ there is only one tuple t per bucket buckett (Z(xi ,xj ) ) such that t ∈ Zxi and t = t′ , therefore ⋊ ⋊ ). In the following, we traverse the grounded-tree by only visiting the join ) = buckett (Zx⋉ buckett′ (Zx⋉ j j ⋉ ⋊ ⋊ vertices Vxi . Moreover, since ≺ is hierarchy-consistent, t is chosen before the tuple in buckett′ (Zx⋉ ), j ⋊ ) is always known when we need it. so buckett′ (Zx⋉ j ⋊ To enumerate the first answer of Q(D), we start from the root table Zv⋉ . Let t0 := () be the root ⋉ ⋊ tuple of Zvroot , if it exists. Otherwise, we return end-of-enumeration. Then, for every child c of vroot ⋊ in TQ , we save the bucket buckett0 (Zc⋉ ) in a variable bucket[c]. Afterward, for j = 1, . . . , l in this order, we take the first tuple tj of the bucket saved in variable bucket[xj ], determined by the tuple chosen for its parent. At last, we output the answer built from the first tuple tl of the corresponding bucket, and pause the algorithm with the command yield. To enumerate the next answer of Q(D), we look for the rightmost variable xi whose current tuple is not the last of its bucket. If there is none, the enumeration ends. Otherwise, we replace the tuple of xi with the following tuple of its bucket, and for each xj with j > i, in the order ≺, we take the first tuple of the bucket determined by the tuple chosen for its parent. Only the variables after xi−1 change between two consecutive answers. ⋊ ⋊ Getting buckett (Zx⋉ ) for a tuple t and a variable xj takes constant time, since each vertex Vx⋉ is a j j ⋉ ⋊ look-up table where keys are all assignments of the free variables of Wxi where xi is the parent of xj in the extended q-tree TQext . Therefore, the delay to output a new tuple is at most the traversal of every join vertex of the grounded-tree until the last free variable of the order ≺, i.e., the delay of Algorithm 1 is O(|Q|). Combining the delay bound with the bounds from Proposition 3.5 and Lemma 4.5, there exists an algorithm that enumerates Q(D) with O(|D| · |Q|) preprocessing, O(|Q| log |D|) update time and O(|Q|) delay.

4.2

Ranked Direct Access Under Updates

In this part, we first explain how to enrich the grounded-tree representing a database instance for a given hierarchy-consistent order on the free variables of a q-hierarchical SJFCQ Q. Then, we adapt an algorithm from [CTG+ 23] into an algorithm in ⟨|D||Q|, |Q| log |D|, |Q| log |D|⟩ that, given Q, a hierarchy-consistent order ≺, a q-tree for TQ compatible with ≺, and a database instance, answers ranked direct access under updates in O(|Q| log(|D|)) access time. Enriched grounded-tree for ranked direct access under updates Let VD (TQ ) be a groundedtree as described in Section 3 for a given q-hierarchical SJFCQ Q, a given database instance D, and a hierarchy-consistent order ≺. Recall that each bucket b is sorted according to a lexicographic ranking function fb . This ranking function is the identity: fb (t) := t for every t ∈ b, meaning b is sorted ⋊ Π lexicographically. We call VDfree (TQ ) the subtree of VD (TQ ) containing all vertices {Vx⋉ ∪ V(x | i i ,xj ) 11

Algorithm 1: Ranked enumeration according to a hierarchy-consistent order ≺ Input: VD (TQ ): a grounded-tree for Q(D) Output: answers of Q(D) in the lexicographic order induced by ≺ begin Let x1 < . . . < xl be the variables of free(Q) in the desired hierarchy-consistent order ≺ ⋊ for t0 ∈ Zv⋉ do root tQ(D) ← () for c child of vroot in free(Q) do ⋊ ⋊ bucket[Zc⋉ ] ← buckett0 (Zc⋉ ) ⋉ ⋊ for t1 ∈ bucket[Zx1 ] do tQ(D) [x1 ] ← t1 [x1 ] for c child of x1 in free(Q) do ⋊ ⋊ bucket[Zc⋉ ] ← buckett1 (Zc⋉ ) .. . ⋊ for tl ∈ bucket[Zx⋉ ] do l tQ(D) [xl ] ← tl [xl ] yield tQ(D)

yield end-of-enumeration

xi , xj ∈ free(Q) ∪ {vroot }}. As Q is q-hierarchical, VDfree (TQ ) is a connected subtree. Let V be a vertex, let Vi be the parent of V , let Z and Zi be the tables associated to V and Vi , and let W be the view associated to V . For each tuple t in a bucketti (Z) with ti ∈ Zi , we add weights wbucketti (Z) (t). Note that these weights are different from the ranking function fb , as they are not used to sort the tuples in a bucket. The weight wbucketti (Z) (t) represents the number of different answers in Q(D) that extend t over the variables in the views of the subtree rooted in V in VDfree (TQ ). We compute these weights bottom-up while building the grounded-tree VD (TQ ), and when an update occurs. For leaves in the subtree VDfree (TQ ), we initiate all weights to 1. When we propagate the tuple upward in VD (TQ ), as explained in Proposition 3.5 and Lemma 4.5, we compute the weight for each tuple propagated as ⋊ follows. Note that in this case, the propagation of an update never stops before achieving Vv⋉ , since root we need to update weights for the parent of each vertex. This still takes O(|Q| log |D|). Let xi , xj ∈ free(Q) ∪ {vroot } such that xj is a child of xi in TQ , and ti the tuple restricted over the variable of the view Wi associated to the parent Vi of vertex V .   1 if Z is associated to a leaf in VDfree (TQ )  P  ′ Π ⋉ ⋊ (t ) if Z = Z(x , w i ,xj ) wbucketti (Z) (t) := t′ buckett (Zxj )  Q  w ′ ⋉ ⋊   buckett (Z Π ) (t ) if Z = Zxi . xj

(xi ,xj )

Π Therefore, if t ∈ Z(x , its weight wb (t) is the sum of all the weights of the tuples t′ that are i ,xj ) ⋊ Π extensions of t in the table Zx⋉ . Otherwise, recall that buckett (Z(x ) contains exactly one tuple. j i ,xj ) ⋉ ⋊ Then, if t ∈ Zxi , its weight wb (t) is the product, over all children xj of xi , of the weight of the unique Π tuple txj ∈ buckett (Z(x ). i ,xj ) In addition to wb (t), we compute a prefix sum startb (t) for each bucket b and each tuple t ∈ b. This P sum is′ the cumulative sum of the weights of the tuples that strictly precede t, i.e., startb (t) := w(t ). t′ ∈b,t′ <t

Example 4.7. We now consider the query Q2 (x1 , x3 ) := R(x1 , x2 ) ∧ T (x3 ), where by definition of a ⋉ ⋊ ⋊ := RD and ZT⋉ := T D . view-tree we have ZR We enrich the view-tree V (TQ2 ) with the weights w(t) and the prefix sum start(t). The result is represented in Figure 3. ⋊ Note that, for t ∈ Zv⋉ , the value w(t) is the total number of tuples in Q2 (D). root 12

⋊ Vv⋉ () root ()

vroot Π V(v

root ,x1 )

x1

x3

x2

T (x3 )

R(x1 , x2 ) (a) Extended q-tree TQ2

x1

x3

b1 b1 b1 b3 b3 b3

d1 d2 d3 d1 d2 d3

(b) Q2 (D)

() ⋊ (x ) Vx⋉ 1 1 b1 b3

()

w(t) 2 w(t) 1 1

start(t) 0 start(t) 0 1

w(t) 6

start(t) 0 Π V(v

root ,x3 )

() ⋊ (x ) Vx⋉ 3 3 d1 d2 d3

Π V(x (x1 ) 1 ,x2 ) b1 b3

()

w(t) 3 w(t) 1 1 1

start(t) 0 start(t) 0 1 2

Π V(x (x3 ) 3 ,T ) d1 d2 d3

⋊ (x , x ) Vx⋉ 1 2 2 b1 c1 b1 c2 b3 c1

⋊ VT⋉ (x3 ) d1 d2 d3

Π V(x (x1 , x2 ) 2 ,R) b1 c1 b1 c2 b3 c1 ⋉ ⋊ VR (x1 , x2 ) b1 c1 b1 c2 b3 c1

(c) View-tree for V (TQ2 )

Figure 3: Representation of q-tree, view-tree and query result for Q2 (D) (see Example 4.7) To understand how weights and prefix sums are maintained after updates, we describe the implementation of a bucket b. We use the B + -tree described in Section 3, where the tuples of b are sorted lexicographically by their values. Each leaf stores a bounded number of consecutive tuples t of b, together with their weights w(t). Each internal node n stores the sum of the values stored in its children, that is, the total weight of the tuples stored in the leaves below n. Inserting or removing a tuple in b, or changing its weight, takes time O(log |D|), including the update of the sums stored in the internal nodes along the path from the leaf to the root. Propagating an update of the database to the O(|Q|) views of the grounded-tree thus takes time O(|Q| log |D|). The prefix sums are not stored: the value startb (t) of a tuple t is computed when needed. To compute it, we traverse the B + -tree from the root to the leaf of t. At each internal node, we add the values stored in the children located to the left of the child we visit, and, in the leaf, we add the weights of the tuples preceding t. Since the height is O(log |D|) and each node has a bounded number of children, computing the prefix sum of a tuple takes time O(log |D|). Then, in a bucket b, given a value k, we can find in time O(log |D|) the last tuple t sorted according to fb such that startb (t) < k. Theorem 4.8. There exists an algorithm that, given a q-hierarchical SJFCQ Q, a hierarchy-consistent total order ≺ on its free variables, a q-tree TQ for Q compatible with ≺ and a database instance D, answers ranked direct access for Q(D) in the lexicographic order defined by ≺ with O(|D| · |Q|) preprocessing, O(|Q| log |D|) update time and O(|Q| log |D|) access time. Proof. This access algorithm is Algorithm 1: Lexicographic Direct-Access from [CTG+ 23], whose data complexity is O(log(|D|)). This algorithm consists of getting the right bucket for each view of the view-tree, which is done in constant time as views are implemented as look-up tables, and then picking the correct tuple in those buckets, which takes O(log(|D|)), as proven in [CTG+ 23, Lemma 3.8]. In combined complexity, as we look for this tuple for each variable of the order ≺, and we traverse each view of the view-tree, the complexity of the access algorithm is O(|Q| log(|D|)). Hence, combining this complexity with Proposition 3.5 and Lemma 4.5, there exists an algorithm that answers ranked direct access for Q(D) and ≺ with O(|D| · |Q|) preprocessing, O(|Q| log |D|) update time and O(|Q| log |D|) access time.

13

5

Non-Hierarchy-Consistent Orders

In this section, given a q-hierarchical SJFCQ Q, an order ≺ over free(Q) and a database instance D, our goal is to develop an algorithm with O(|D| · |Q|) preprocessing and O(|Q| log |D|) update time for ranked direct access under updates (resp. ranked enumeration under updates) according to ≺ with O(|Q| log |D|) access time (resp. delay), i.e., linear preprocessing, logarithmic update, and logarithmic access (resp. delay) times in data complexity. We will show that for ranked direct access under updates, such an algorithm conditionally does not exist.

5.1

Ranked Direct Access Under Updates

Our contribution on ranked direct access under updates relies on Theorem 2.2. The following lower bound states that efficient ranked direct access under updates cannot be achieved for a q-hierarchical SJFCQ when the given order on its free variables is allowed to be non-hierarchy-consistent. Our lower bound holds in data complexity and applies to any q-hierarchical SJFCQ and non-hierarchy-consistent order on its free variables. Theorem 5.1. Fix a number ε > 0, ε′ > 0, a q-hierarchical SJFCQ Q and an order ≺ over free(Q). If ≺ is not hierarchy-consistent for Q, then there is no algorithm with polynomial preprocessing time and O(|D|1−ε ) update time that, given a database instance D, answers ranked direct access for Q(D) ′ and ≺ with O(|D|1−ε ) access time, assuming the OMv-conjecture in data complexity. To prove this lower bound for ranked direct access, we first show that an efficient ranked direct access algorithm for any non-hierarchy-consistent order on any q-hierarchical SJFCQ Q would imply efficient enumeration under updates, for some non-q-hierarchical SJFCQ Q′ , which according to Theorem 2.2 is not possible (even without an order) when assuming the OMv-conjecture. Lemma 5.2. Suppose there is a q-hierarchical SJFCQ Q and a non-hierarchy-consistent order ≺ over free(Q), such that there exists an algorithm in ⟨fp , fa , fu ⟩ where fp is polynomial, fa and fu are O(|D|1−ε ) for some ε, and that, given a database instance D, answers ranked direct access for Q(D) and ≺. Then there exists a non-q-hierarchical SJFCQ Q′ , such that there is an algorithm in ⟨fp , fd , fu ⟩ that, given a database instance D, enumerates Q′ (D) with fd = O(fa log |D|). To show this lower bound, we reduce the enumeration of a projection Q′ of Q to ranked direct access under updates on Q, where Q is a q-hierarchical SJFCQ with a non-hierarchy-consistent order over its variables. We choose the free variables of Q′ so that Q′ is not q-hierarchical. Given a database instance D, we enumerate the tuples of Q′ (D) as follows: we use ranked direct access on Q(D) to retrieve the k th answer, and then find by binary search the smallest k ′ > k such that the k ′ answer has a different projection on the free variables of Q′ . Each such answer is a new tuple of Q′ (D), which we output. Let us give the formal proof of Lemma 5.2: Proof of Lemma 5.2. Let D be a database instance, Q be a q-hierarchical SJFCQ, and ≺ be a nonhierarchy-consistent order over free(Q). Let (x1 , . . . , xl ) be the free variables of Q listed in the order of ≺. Then there exist two variables xi , xj ∈ free(Q) such that atomsQ (xi ) ⊊ atomsQ (xj ) and xi ≺ xj . Let Q′ := ΠXi (Q) be the projection of Q over Xi := {x1 , . . . , xi }. Thus, free(Q′ ) = free(Q) \ {xi+1 , . . . , xl }, with xj ∈ {xi+1 , . . . , xl }. Therefore, Q′ is not q-hierarchical, since condition (ii) of Definition 2.1 is violated on variables xi and xj . Indeed, atomsQ′ (xi ) ⊊ atomsQ′ (xj ) and xi ∈ free(Q′ ), whereas xj ∈ / free(Q′ ). Suppose there exists an algorithm with update time tu that supports ranked direct access in time ta for Q(D) and the order ≺. Let N := |Q(D)| denote the number of answers of Q on D. Since Q is a q-hierarchical SJFCQ, we can retrieve N in O(1) data complexity, after a O(|D|) preprocessing, and maintain this value in O(log |D|) update time [Kep20, Theorem 3.9]. Let ≺ be the lexicographic order of Q(D) induced by ≺, and let (t1 , . . . , tN ) be the answers of Q(D) listed according to ≺, where each tk ∈ (t1 , . . . , tN ) can be computed in time ta using the algorithm assumed in the lemma statement. We now show how to design an efficient enumeration algorithm for Q′ (D). We start by checking if N = 0 (or if accessing t1 returns out-of-bounds), in which case we output end-of-enumeration and terminate; otherwise we compute t1 and output the tuple s1 := t1 [Xi ]; this step takes time ta . Then, at each step, we compute the next tuple in the enumeration from the last outputted one. To 14

do this, suppose we have already output the pth tuple sp := tk [Xi ] for some k ∈ [N ]. We define the next relevant rank k ′ := min{ℓ ∈ [k, N ] | tk [Xi ] ̸= tℓ [Xi ]} as the next index of an answer of Q whose projection to Xi changes relative to tk . If no such ℓ exists, the enumeration algorithm will output the special value end-of-enumeration and terminate. Otherwise, the (p + 1)th tuple of the enumeration will be set as sp+1 := tk′ [Xi ]. All that remains is to explain how we can efficiently find sp+1 or detect termination. We first access tN and check whether tN [Xi ] = sp ; if so, the enumeration is finished, and the algorithm will output end-of-enumeration. Otherwise, we show how to compute the next relevant rank k ′ . To do this, we compute k ′ by performing a binary search on the interval [l, r] = [k, N ]. At each step, let m = ⌊(l + r)/2⌋ and access the tuple tm . If tk [Xi ] ≺ tm [Xi ], then k ′ ∈ [l, m], and we set r := m. Otherwise, we have k ′ ∈ [m + 1, r], and we set l := m + 1. We repeat this process, updating the interval [l, r] at each step, until we have l = r. At that point, one can easily see that we must have k ′ = l. This binary search requires O(log N ) access calls, and therefore runs in time O(ta log N ). Thus, we obtain an algorithm with update time tu and delay td = O(ta log N ) for enumerating Q′ (D). Moreover, we have N = |Q(D)| ≤ |D||Q| , therefore, we obtain delay td = O(ta log |D|) in data complexity. Having proved our auxiliary result (Lemma 5.2), we are ready to conclude the proof of Theorem 5.1: Proof of Theorem 5.1. Let D be a database instance, Q be a q-hierarchical SJFCQ, and ≺ be a nonhierarchy-consistent order over free(Q) for Q. Suppose there is ε > 0 such that there exists an algorithm with polynomial preprocessing and O(|D|1−ε ) update time that answers ranked direct access in O(|D|1−ε ) access time for Q(D) and ≺. By Lemma 5.2, there exists a non-q-hierarchical SJFCQ Q′ such that there is an algorithm that enumerates Q′ (D) with O(|D|1−ε log |D|) delay and sublinear update time. Let ε′ := ε/2. By Theorem 2.2, ′ ′ as Q′ is not q-hierarchical, no algorithm enumerates Q′ (D) with O(|D|1−ε ) delay and O(|D|1−ε ) up′ date time, unless the OMv-conjecture fails. Since O(|D|1−ε log |D|) = O(|D|1−ε ) this contradicts the OMv-conjecture. Therefore, unless the OMv-conjecture fails, there is no dynamic algorithm with polynomial prepro′ cessing time and O(|D|1−ε ) update time that answers ranked direct access in O(|D|1−ε ) access time for a q-hierarchical SJFCQ and a non-hierarchy-consistent order on its free variables.

5.2

Ranked Enumeration Under Updates

We have shown a dichotomy for ranked direct access under updates: assuming the OMv-conjecture, there exists an algorithm for ranked direct access with complexity ⟨|D| · |Q|, |Q| log |D|, |Q| log |D|⟩ if and only if the order in input is hierarchy-consistent. For ranked enumeration, we do not have a matching lower bound. We believe in fact that the situation with ranked enumeration under updates is different, and that it remains efficient even when the order is not hierarchy-consistent, at the cost of an additional logarithmic factor in the delay in data complexity. Our approach is to adapt the algorithm anyK-part of [TGR25], which relies on the Lawler-Murty procedure, to the grounded tree VD (TQ ). The main difference with the static setting lies in the optimal weights of the tuples. In the static case, they are computed once, before the enumeration, by a dynamic programming pass over the tree. In our setting, we compute them during the preprocessing phase, as part of the construction of the grounded tree, and we maintain them when the database is updated. We leave the details and the analysis of this approach to a future version of the present work.

References [BB13]

Johann Brault-Baron. De la Pertinence de l’Énumération. PhD thesis, Université Paris 7, 2013.

[BDG07]

Guillaume Bagan, Arnaud Durand, and Étienne Grandjean. On Acyclic Conjunctive Queries and Constant Delay Enumeration. In International Workshop on Computer Science Logic, 2007.

[BKS17]

Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Queries under Updates. PODS, 2017. 15

Answering Conjunctive

[CCIS26]

Florent Capelli, Nofar Carmeli, Oliver Irwin, and Sylvain Salvati. Direct Access for Conjunctive Queries with Negations. Logical Methods in Computer Science, Volume 22, Issue 1, March 2026.

[CS23]

Nofar Carmeli and Luc Segoufin. Conjunctive Queries with Self-Joins, Towards a FineGrained Enumeration Complexity Analysis. In PODS, 2023.

[CTG+ 23] Nofar Carmeli, Nikolaos Tziavelis, Wolfgang Gatterbauer, Benny Kimelfeld, and Mirek Riedewald. Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries. ACM Transactions on Database Systems, 48(1), March 2023. [Gra96]

Étienne Grandjean. Sorting, Linear Time and the Satisfiability Problem. Annals of Mathematics and Artificial Intelligence, 16(1), December 1996.

[Hu26]

J. Hu. Ranked Enumeration over Circuits via Implicit Representations. PhD thesis, University of California, Santa Cruz, 2026. ProQuest ID: 32863524.

[IUV17]

Muhammad Idris, Martin Ugarte, and Stijn Vansummeren. The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates. SIGMOD, 2017.

[Kep20]

Jens Keppeler. Answering Conjunctive Queries and FO+MOD Queries under Updates. PhD thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät, 2020.

[KLN+ 25] Ahmet Kara, Zheng Luo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Tractable Conjunctive Queries over Static and Dynamic Relations. In ICDT, Dagstuhl, Germany, 2025. [OS16]

Dan Olteanu and Maximilian Schleich. Factorized Databases. SIGMOD Rec., 45(2), September 2016.

[RCCS26]

Clément Rouvroy, Nofar Carmeli, David Carral, and Luc Segoufin. Constant-Delay Enumeration of Conjunctive Queries with Self-Joins and Projections. In BDA, 2026.

[TGR25]

Nikolaos Tziavelis, Wolfgang Gatterbauer, and Mirek Riedewald. Any-k Algorithms for Enumerating Ranked Answers to Conjunctive Queries. ACM Transactions on Database Systems, 51(1), 2025.

[WHDY23] Qichen Wang, Xiao Hu, Binyang Dai, and Ke Yi. Change Propagation Without Joins. Proc. VLDB Endow., 16(5), January 2023.

16

Related documents

• Bookkeeping, Composition, or Unreachable Gold? Reading MemoryAgentBench's Conflict-Resolution Scores Against a Frozen Last-Write Resolver#1233232
• Binary Path Sort: A Sorting Algorithm to Assess the Ranking Order of a Single Respondent#297829
• Pre-Query Retention with Bounded Bit and Word Retrieval#1390044
• On the Use of the Dempster Shafer Model in Information Indexing and Retrieval Applications#933440
• ON THE USE OF THE DEMPSTER SHAFER MODEL IN INFORMATION INDEXING AND RETRIEVAL APPLICATIONS#933350