Earliest query answering over streamed trees
arXiv:2606.07408v1 [cs.DS] 5 Jun 2026
Mateusz Gienieczko 1, Martín Muñoz 2, Filip Murlak 3, Charles Paperman 4 June 8, 2026 Technical University of Munich, Germany Univ. Artois, CNRS, UMR 8188, Centre de Recherche en Informatique de Lens (CRIL), F-62300, France 3 University of Warsaw, Poland 4 CRIStAL, Université de Lille, INRIA, France 1
2
Abstract Streaming allows executing queries over massive JSON or XML documents whose size makes it infeasible to fully parse them into a tree. Earliest query answering is a radical approach to reducing latency and memory footprint. To minimize latency, a document node must be returned as soon as the node is guaranteed to be an answer regardless of how the document ends. Similarly, to minimize memory footprint, a node must be discarded as soon as it cannot become an answer regardless of how the document ends. For simple queries that select nodes based on the path from the root, the decision for each node can be made on the spot, but practical languages such as XPath or JSONpath support filters, which allow selecting nodes based on information collected from various parts of the document, possibly further down the stream. This makes earliest query answering a challenging task, as candidate nodes must be kept in memory until it becomes clear that they can be safely returned or discarded. We show that this can be done for all unary queries expressible in monadic second order logic (MSO), while ensuring constant update time—provided that nodes are returned by passing a suitable iterator, rather than one by one.
1
Introduction
Tree-shaped data occurs in many settings, from XML and JSON documents to program syntax trees, logs, database dumps, and web data [2]. A large body of work, originating especially from the XML era, has studied how to extract information from such data [16, 5, 1, 15, 23, 7]. Despite this long history, efficient query evaluation over trees remains a relevant problem. In high-throughput settings the cost of parsing the input and materializing a full in-memory representation of the tree can already dominate the cost of query evaluation itself [25]. 1
A standard approach is to first build an in-memory representation of the input tree and then evaluate the query on this representation. This approach is often too expensive—both in time and in memory—especially for massive semistructured files. To obtain high performance, parsing and query evaluation should instead be integrated: the evaluator should inspect the input as it is read, maintain only the information that may still influence future answers, and avoid materializing the whole tree whenever possible. This naturally leads to streaming algorithms for querying trees. Streaming evaluation is relevant for fully streaming query engines, such as rsonpath [14] and JSONSki [20], but also for preprocessing pipelines that filter or partially analyze documents before loading them into a database, as in Sparser [25], or in more elaborate storage mechanisms such as JSONTiles [9]. In this setting, complex navigation and filtering constructs may force the query engine to maintain candidate nodes across long portions of the input stream. This phenomenon already appears for filters in XPath [27], and also in the recently proposed JSONPath standard [19]. In a streaming setting, two efficiency requirements are particularly important. The first is memory: the algorithm should have a parsimonious memory footprint, storing only information that may still affect future answers. The second is delay: answers should be produced as soon as possible. Once the status of a node is determined by the prefix read so far, keeping this node as a pending candidate increases memory consumption and introduces unnecessary latency in returning the result set. Conversely, the decision must be made only once enough information is available. Earliest query answering [13, 12] captures this tension by requiring each node to be accepted or rejected as soon as its status is forced by the current stream prefix. In this paper, we represent trees as nested words [3], or equivalently as streams of opening and closing events. We study Boolean and unary queries expressed in monadic second-order logic (MSO) [8]. A Boolean query asks whether the whole tree satisfies a property. A unary query selects positions, or nodes, of the input tree that satisfy a formula with one free first-order variable, and the output is the set of positions satisfying the formula. One cannot hope, however, for constant memory in general. Even simple unary queries may require the algorithm to remember linearly many candidate positions. For example, consider the query that selects all nodes whose label is equal to the label of the last leaf in document order. Until the last leaf is read, the algorithm does not know which label is relevant; in the worst case, it may therefore need to keep enough information to output all positions with that eventual label. Thus a Ω(n) memory lower bound is unavoidable for some queries, with n the size of the input word. Our goal is therefore not to guarantee small memory for every query. Rather, we aim to maintain the necessary information efficiently, while ensuring that no candidate is kept longer than what is logically necessary.
2
Our contribution We provide a streaming algorithm for unary queries definable in MSO that complies with earliest query answering by maintaining a specialized data structure with constant-time updates in data complexity, in the RAM model. The constant may depend on the query, but not on the size of the input prefix read so far. The algorithm performs each step with constant delay, and it emits each position at the earliest prefix at which its membership in the query result set is determined. More precisely, a position is output (resp. rejected) as soon as all possible completions of the current stream prefix agree that this position belongs (resp. does not belong) to the answer. This notion is independent of syntactic elements such as the closing event of the corresponding node: depending on the query, a position may become determined either before its subtree is closed, exactly when it is closed, or after. The algorithm is therefore optimal regarding the information available in the stream prefix: no correct streaming algorithm can output or reject a position earlier. Structure of the paper After this, in Section 2, we present some preliminary notions in order to state the main result. Then, in Section 3, we show a simplified algorithm that does earliest query answering for boolean formulas; namely, the algorithm only has to decide whether the forest is a model of the formula or not, and do this as early as possible. After this (Section 4), we present the main result of the paper as an extension of the algorithm from the previous section that works for unary formulas. This algorithm uses a certain data structure that we first describe as an interface; we show its inner workings in the following section (Section 5). The last two sections are a discussion about related works in the literature (Section 6), and then conclusions and future work (Section 7).
2
Preliminaries and Problem statement
Forests and trees Our data will be represented by ordered unranked labeled forests (from now on, just forests). They contain nodes which are labeled by a function λ mapping nodes to an alphabet Σ. We use the standard notions of parent, child, sibling, etc., and we assume that the roots in the forest are also siblings. We will also compose forests by concatenation and by application. If F and G are forests, then the forest H = F · G is the disjoint union of the two: if G is not empty, then the rightmost root of F becomes the left sibling of the leftmost root of G, and if G (resp. F ) is empty, then H = F (resp. H = G). If a ∈ Σ and F is a forest, then H = a(F ) is a tree: if F is non empty, then H is a tree with a root that is labeled a, and that has the roots of F as its children, and if F is empty, then H is a single node labeled a. Observe that for every nonempty forest F there are two unique (possibly empty) forests G and H, and a symbol a ∈ Σ such that F = a(G) · H. Important: For presentation purposes, the title of the paper and the introduction talk about data represented in trees. Nonetheless, for the rest of
3
the paper the input will always be forest, and the word “tree” will exclusively refer to a forest with one root. Automata model We work with automata over unranked forests, in the firstchild next-sibling variant. We assume the automata are bottom-up and rightto-left deterministic1 . Formally, an automaton is a tuple A = (Σ, Q, δ, init, Final) where Q is a set of states, δ : Σ × Q × Q → Q is the transition function, init ∈ Q is the sole initial state, and Final ⊆ Q is the set of final states. The semantics are as follows. Fix a forest F : we say that A evaluates a node v in F to a state r if it evaluates its leftmost child to p, its right sibling to q, and δ(λ(v), p, q) = r. If the leftmost child or the right sibling do not exist, they evaluate to init by default. Alternatively, we can recursively define δ(F ) = δ(a, δ(G), δ(H)) if F = a(G) · H, and δ(F ) = init if F = ε. We say that A evaluates F to q if it evaluates its leftmost root to q; and we say it accepts F if q ∈ Final. We assume that all states of A are reachable, by which we mean that for each q ∈ Q there exists a forest that evaluates to q. We briefly note that every Boolean query expressible in the monadic secondorder logic on trees (MSO) is expressible as a forest automaton, and vice versa [28]; more on this later. Forest encodings Given a forest F , the term encoding of F , denoted by enc(F ) is a string in Σ ∪ {⟨ , ⟩} that explicitly lays out a sequence of concatenations and applications that constitutes F : if F is empty, then enc(F ) is the empty string ε; otherwise, F = a(G) · H for some unique a ∈ Σ, G, H, and we recursively define enc(F ) := a ⟨ enc(G) ⟩ enc(H). We say that a string w over Σ ∪ {⟨ , ⟩} is well-nested if there exists a forest F such that enc(F ) = w. We adopt a tokenized view of encodings: we see enc(F ) as a sequence t1 · · · tn where each ti is either an opening tag of the form a ⟨ for some a ∈ Σ or the closing tag ⟩. We will also work with prefixes of these term encodings. We say that a forest F agrees with a word w if w is a prefix of enc(F ) that ends with a symbol from {⟨ , ⟩}; if some F agrees with w, then we might simply say that w is a prefix without indicating F . For a prefix w = w0 c1 ⟨ w1 · · · cd ⟨ wd where w0 , . . . , wd are well-nested words, we call c1 ⟨ , . . . , cd ⟨ the open tags of w, and we will sometimes single out cd ⟨ as the last open tag of w. The depth of a prefix w, written as depth(w), is its number of open tags. We sometimes talk about the nodes in a prefix w, by which we mean the nodes that are common to every forest that agrees with w; equivalently, they are the nodes in the forest encoded by the word w′ = w ⟩ · · · ⟩ , in which w is followed by depth(w) copies of the closing tag. 1 It might seem counterintutive that we work with a model in which computation progresses
leftward and upward, as it is essentially the opposite of what happens when we read the term encoding of a forest, but it proves convenient later on.
4
In this work, algorithms will read an input forest F represented as the string enc(F ) = t1 t2 · · · tn , tag by tag. If, in the current step, the algorithm has read i tags, then we call the prefix t1 · · · ti the current prefix. Model of computation We adopt the computational model of Random Access Machines (RAM) with register length of size Θ(log(n)) where n is the final input size, and arithmetical computations on a single register are assumed to cost constant time. This is one of the standard models for streaming algorithms [10, 24, 21], so we do not linger on the implications of this choice. We want to provide precise guarantees on the space that the algorithm uses at each point of the computation. To this end we assume the RAM has a lazy garbage collection system that only frees unused registers upon demand. At each step, we identify some root registers whose information is directly accessible in the algorithm, and we consider that the space utilized by the algorithm is the number of registers that are reachable from these root registers. This implies that the algorithm might sometimes dispose of a single root register, and this effectively frees multiple registers in memory all at once. Unary MSO queries The evaluation task that we are set out to solve is, given a unary query expressed as an MSO formula φ(x) with a single free firstorder variable x and a forest F over some fixed alphabet Σ, output every node v in F such that F, v |= φ(x). We write Jφ(x)K(F ) for the set of all such nodes in F . A unary MSO query can be equivalently represented using an automaton A over the extended alphabet Σout := Σ ∪ {ǎ | a ∈ Σ}. For a node v in F let F [v] be the result of replacing the label a of v by ǎ, and define a function JAK by JAK(F ) = {v | A accepts F [v]}. Each MSO formula φ(x) can be translated to a forest automaton A such that Jφ(x)K = JAK [24, 22]. In what follows we distinguish between unmarked forests, which are forests over Σ, and marked forests, which are over Σout and contain exactly one node labeled ǎ for some a ∈ Σ. Earliest query answering Consider a query q, given via an MSO formula or an automaton. We are interested in enumerating JqK(F ) while reading enc(F ), but we want to return node v as soon as v is guaranteed to be an answer, and to discard a candidate node v as soon as v is guaranteed to never become an answer. Let us formalize this. Consider a prefix w. We call node v • a definite answer if v ∈ JqK(F ) for every forest F that agrees with w;
• a definite nonanswer if v ∈ / JqK(F ) for every forest F that agrees with w;
• indefinite or candidate otherwise; that is, when v might become an answer in some forests agreeing with w and a nonanswer in others. We write the set of all candidate nodes for w as Cands(q, w).
5
We are interested in the following kind of algorithms. The algorithm reads a streamed forest and keeps a collection of nodes in memory: upon reading the opening tag of a node, the node is either added to the collection, or returned as an answer, or discarded. The collection is also updated: some nodes are returned as answers, some are discarded, and some are kept. We require that each node v is returned (resp. discarded) after reading the shortest prefix w such that v is a definite answer (resp. definite nonanswer) for w. This complies with the classical notion of earliest query answering as it was presented in [12]. Next, we refine this setting by bringing it closer to the machine model, in order to facilitate precise complexity guarantees. Streaming enumeration A streaming evaluation algorithm is an algorithm that receives a query q, and a stream S that reveals the symbols from an input word w one by one from beginning to end—we say that S streams w. We consider a special function yield[S] that upon each call returns the next symbol of w, and after the last symbol it returns a flag end. At the end of the stream, the algorithm should produce the result from evaluating q over w. In this work, we use a more refined notion that we call a streaming enumeration algorithm. We split the evaluation into alternating update phases, where the algorithm preprocesses a data structure that contains the answers, and enumeration phases, in which the answers are printed one by one in a dedicated write-only space. A full run of the algorithm will start with the first call to yield[S], which marks the beginning of the first update phase; then it runs the first enumeration phase to print any definite answers; and then calls yield[S] again to continue with the second update phase, and so on. When yield[S] returns end, the algorithm runs its last update and enumeration phases, and ends. By this point, the entire answer set should have been printed without repeats. In the literature, this type of evaluation algorithm is sometimes called an enumeration algorithm with early output [26]. We measure the resources required by this algorithm across three dimensions: • Update time. This is the maximum number of steps taken in any update phase, namely, between any call to yield[S], and the next enumeration phase. • Enumeration delay. The maximum number of steps, across all enumeration phases, between: (1) beginning an enumeration phase and printing its first output, (2) printing any two consecutive outputs and (3) printing the last output of the current enumeration phase and the moment the phase ends. • Instantaneous space. We measure the space at every step of the computation in terms of the active registers in memory: these are the ones that hold all the accessible information, as specified in the Model of computation paragraph above. The algorithm uses instantaneous space s(i) if this is the maximum number of active registers at the end of i-th enumeration phase for any i ∈ [1, |w| + 1]. 6
After this preamble we can state our main result. Let f (φ) be some computable value that only depends on φ. Theorem 1 (Main result). There is a streaming enumeration algorithm that receives an MSO formula φ(x) and a stream S streaming w = enc(F ) and produces Jφ(x)K(F ). Further, this algorithm: • works with f (φ) update time,
• has constant-delay enumeration, • and uses O( |Cands(φ(x), w[1, i])| + f (φ) · depth(w[1, i]) ) instantaneous space.
3
Warmup: Boolean queries
Suppose that our goal is to solve the problem of earliest query answering for boolean queries. That is, we have a fixed automaton A = (Σ, Q, δ, init, Final), we read a streamed encoding of a forest over Σ, and our task is to determine if the encoded forest is accepted or rejected, and we have to answer yes or no as soon as the answer of the automaton is determined by the already processed prefix of the encoding. We note that this result is implicit in the work of Gauwin et al. [12]; it is only presented here for illustration purposes. Theorem 2. There is an algorithm that receives an MSO formula φ and a stream S streaming w = enc(F ) and answers whether F |= φ as early as possible, with constant update time and f (φ) · depth(w[1, i]) instantaneous space. Reading the term encoding of a forest F corresponds to a DFS on the forest, with children of a given node processed left-to-right. Having read a prefix w of the term encoding of forest F we are in a node w b of F that corresponds to the most recent opening tag that has not been closed yet. If no such tag exists, we are in the virtual root of the forest, labeled with a special symbol $ such that δ($, q, q ′ ) = q. We shall refer to w b as the current node. By the current path we mean the path from the root of the tree containing the current node to the current node. The visited part of the forest consists of nodes whose opening tag we have already read—namely, the nodes in w. All visited nodes can be split into three categories: we have the current node (C, for current), the visited proper descendants of the current node (B, for below), and the remaining visited nodes (A, for above). Nodes from B form a subforest of F , and nodes from A form a context with multiple holes. Indeed, each node in A that lies on the current path has a hole as its rightmost child, directly to the right of the next node on the current path. The last node in A on the current path is the parent of C; it has a hole instead of C. We refer to it as the current hole (see Figure 1). The nodes in the current path correspond to the open tags of w, which are labeled c1 , . . . , cd = c, and the already-seen subforests that descend from each are named B1 , . . . , Bd = B. The union of all of these subforests, minus C and 7
A
c1 .. .
B1
ci .. .
Bi
cd
Bd
B
C
Figure 1: Decomposition of a tree into parts A, B and C B, corresponds to A. We can decompose A into a sequence of contexts: we call A0 a context that is only a hole, and Ai the context with i + 1 holes that is obtained by plugging a node labelled ci with Bi and a hole as children, and another hole as its right sibling. To a forest F we associate a function Fb : Q → Q. We define it recursively by three cases: if F is empty, then Fb(p) = p; if F is the concatenation of two forests F1 and F2 , then we define Fb := Fb1 ◦ Fb2 ; if F is a tree with a root labeled c whose children form the forest F0 , we define Fb(p) := δ(c, Fb0 (init), p). Intuitively, this function represents the final state that is reached once we run the automaton on F after replacing its “initial state from the right” by p. Note that this function is well defined given that the automaton is deterministic and trimmed. We extend this definition to work with d-ary contexts, which extend forests by including d nodes that are labeled with a special symbol □. They are defined as follows: (1) a forest concatenated with a single node labeled □ is a 1-ary context; (2) the result of concatenating a forest, a tree where the children of the root form a d-ary context, and a node labeled □ is a (d + 1)-ary context. b : Qd → Q. If d = 1 and Now, to a d-ary context K we associate a function K b b b 1 , . . . , qd ) := K = F · □ then K = F ; otherwise, let K = F · c(K1 ) · □, then K(q b 1 (q2 , . . . , qd )), q1 ). δ(c, Fb(K These functions help us model the information that we store in a run of the algorithm. At any step of a given run, if the depth of the current node is d, then the prefix read so far is associated to a d-ary context Kcurr . It can be visualized by appending d copies of the string “□ ⟨ ⟩ ⟩” at the end and decoding the resulting forest. The information that we store at each point of the algorithm is a function α : Q → 2{⊥,⊤} that we define as follows b curr (q1 , . . . , qd−1 , q) ∈ Final; • ⊤ ∈ α(q) iff there exist q1 , . . . , qd−1 such that K b curr (q1 , . . . , qd−1 , q) ̸∈ Final; • ⊥ ∈ α(q) iff there exist q1 , . . . , qd−1 such that K b In other words, it correalong with a function β : Q → Q defined as β = B. sponds to the function associated to the forest that descends from the current node c and is part of the current prefix. 8
For a given prefix w, we will call the functions α and β that would be stored after processing w with the algorithm above as the above function of w and the below function of w. Lemma 1. Let w be a prefix, let α, β be its above and below functions, and let c be its last open tag: • α(δ(c, β(q), q ′ )) = {⊤} for all q, q ′ ∈ Q iff every forest that agrees with w is accepted; • α(δ(c, β(q), q ′ )) = {⊥} for all q, q ′ ∈ Q iff every forest that agrees with w is rejected. Proof. Suppose α(δ(c, β(q), q ′ )) = {⊤, ⊥} for some q, q ′ ∈ Q. We deduce that there exist states that accept and states that reject. We use the fact that the automaton is trimmed to find forests that render those states, and we construct a way of completing w that is accepted and one that is rejected. Let w = w0 c1 ⟨ w1 c2 ⟨ · · · wd−1 cd ⟨ wB where cd = c and every wi is well′ nested. Consider an arbitrary suffix wB ⟩ wd′ ⟩ . . . ⟩ w1′ ⟩ that completes the prefix into a forest F that is accepted (resp. rejected). Relying on the notation from the definition of α, we can use the states that are reached after reading w1′ , . . . , wd′ for q1 , . . . , qd , and conclude that ⊤ ∈ α(δ(c, β(q), q ′ )) ( resp. ⊥ ∈ α(δ(c, β(q), q ′ )) ). It remains to show how to maintain c, α, and β. We rely on the following two lemmas. Lemma 2. Let w′ = w c′ ⟨ wd and w′′ = w c′ ⟨ wd c′′ ⟨, where wd is well-nested. Let α′ and β ′ be the functions for the above and below parts corresponding to w′ , and similarly, let α′′ and β ′′ be the functions for the above and below parts corresponding to w′′ . Then, [ α′′ (q) = α′ (δ(c′ , β ′ (q), q ′ )) and β ′′ = id . q ′ ∈Q
For the degenerate case of w′ = wd and w′′ = wd c′′ ⟨ with wd well-nested, the formulas above hold with α′ = αroot and c′ = $, where ( {⊤} q is final , αroot (q) = {⊥} q is not final . Proof. Let A′ be the d-ary context constituting the above part for w′ and B ′ the forest constituting the below part for w′ . Similarly, let A′′ be the (d+1)-context constituting the above part for w′′ and B ′′ the forest constituting the below part for w′′ . Then, B ′′ is empty and A′′ is obtained from A′ by substituting its deepest node labeled □ with c(B ′ · □) · □. The formulas for α′′ and β ′′ follow immediately. The argument for the degenerate case is analogous.
9
Lemma 3. Let w′ = w c′ ⟨ wd and w′′ = w c′ ⟨ wd ⟩, where wd is well-nested. Using the naming convention from Lemma 2, we have α′′ = α
and
β ′′ (q) = β(δ(c′ , β ′ (init), q)) .
Proof. Let A be the d-ary context constituting the above part for w and B the forest constituting the below part for w. Similarly, let A′ be the (d + 1)-ary context constituting the above part for w′ and B ′ the forest constituting the below part for w′ . Finally, let A′′ be the d-ary context constituting the above part for w′′ and B ′′ the forest constituting the below part for w′′ . Then, A = A′′ and B ′′ = B · c′ (B ′ ). Again, the formulas for α′′ and β ′′ follow immediately. Based on Lemmas 2 and 3 we can maintain c, α, and β using a stack. Before going down we push the current ⟨α, β, c⟩ on the stack and compute new α and β using Lemma 2. The new c is read from the stream. Before going up, we pop old ⟨α, β, c⟩ from the stack, and compute new α and β using Lemma 3. Before reading the first tag, we also check if the automaton accepts everything or nothing, and if this is the case we answer accordingly. If not, we process the tags one by one, maintaining α, β, c and return an answer as soon as the criteria in Lemma 1 becomes satisfied. It is evident the updates can be made in constant time and the space taken—size of the stack—is proportional to the tree depth. Thus, Theorem 3 is proven.
4
Unary queries
We now generalize the described solution to unary queries. We assume that a unary query is represented by an automaton A = (Σout , Q, δ, init, Final) that inputs a forest with a single node marked as the answer node. A node v in forest F is returned by the query iff the automaton accepts the forest obtained from F by marking v, as explained in Section 2. Compared to the Boolean case, instead of a single triple ⟨α, β, γ⟩, we need to maintain one triple for each possible marking of the part of the forest read so far. Let ⟨αv , βv , γv ⟩ be the triple for the marking that distinguishes node v, and ⟨α∅ , β∅ , γ∅ ⟩ the triple for the marking that distinguishes no nodes (meaning that the node to be returned has not been read yet). Without loss of generality we can assume that both αv and βv indicate whether the corresponding part of the forest contains the marked node or not: for this, it suffices to assume that the automaton remembers whether a marked node has already been seen; similarly, γv is either a label c or a marked label č. Let Above, Below, and Current be the sets of triples ⟨α, β, γ⟩ for which the marked node is in the part of the forest corresponding to α, β, and γ, respectively. Let Marked = Above ∪ Below ∪ Current and let Unmarked be the set of triples corresponding to unmarked prefixes. As we continue reading the forest, the triples ⟨αv , βv , γv ⟩ and ⟨α∅ , β∅ , γ∅ ⟩ evolve just like in the Boolean case. Moreover, with each opening tag read, we create a new triple, corresponding to the marking that distinguishes the current 10
node, and insert it into our collection. Similarly to the Boolean case, node v can be returned or discarded as soon as ⟨αv , βv , γv ⟩ satisfies the conditions spelled out in Lemma 1. In either case, we consider this to be a deletion of v along with ⟨αv , βv , γv ⟩ from our collection. The challenge is to implement this algorithm with constant cost of updates, deletes, and inserts. Importantly, not only the cost of a single operation must be constant (this is for free), but the total cost of all operations to be performed when a tag is read. For this purpose, we organize the tuples into a suitable data structure.
4.1
Data structure
The data structure stores candidate nodes grouped by their associated triples: at any moment, given a triple ⟨α, β, γ⟩, it provides access to candidates v such that ⟨αv , βv , γv ⟩ = ⟨α, β, γ⟩. The triple ⟨α∅ , β∅ , γ∅ ⟩ will be stored outside of the data structure. The data structure must support adding new candidates, regrouping the candidates as their triples evolve, and extracting candidates with indicated triple. In order to support the evolution of triples, we need access to their previous values. Instead of presenting the outputs via constant-delay enumeration, we will do it via iterators. This is a subtler notion, as they navigate precisely the set of outputs without performing any other extra operations that might be hidden in the constant delay. Abstractly, the multistack data structure maintains a set X of elements along with a labelling h : X → K+ for a fixed alphabet K = K1 ∪ K2 with K1 ∩ K2 = ∅. We think of the word h(x) as a private stack of element x, growing to the right. The color of element x is the element at the top of its stack: if h(x) = k1 k2 · · · kn then the color of x is kn . The following constant-time operations are supported: • Create a new empty structure; • Insert an element x of color k ∈ K1 : add x to X and let h(x) = k; • Extract elements of color k ∈ K: remove them from X and return an iterator giving access to these elements; • Multi-push according to f : K → K2 : append f (k) to h(x) for each element of color k; • Multi-pop: remove the last symbol from h(x) for each x with |h(x)| > 1; • Multi-swap according to a function f : K → K such that f (K1 ) ⊆ K1 and f (K2 ) ⊆ K2 : replace with f (k) the last label of h(x) for each element x of color k. Above, f (Ki ) stands for {f (k) k ∈ Ki }. Note that the extract operation returns an iterator in constant time, but actually iterating over its elements will take linear time. From the definitions of the operations if follows that the multistack satisfies the following invariant: 11
insert(x4 , kb )
extract(kb )
multi-push(f ) f (ka ) = ℓa f (kb ) = ℓb
x1
ka kb
x1
ka kb
x2
ka
x2
ka
x4
kb
x3
kc ka
x1
ka kb
x2
kb
x3
kc ka
x1
ka kb
x1
ka kb
x2
ka
x2
ka ℓa
multi-pop
multi-swap(g) g(ka ) = ℓa g(kb ) = ℓb
x1
ka kb
x2
ka ℓa
ℓb x 1 x2
x3
kc
x3
kc
x1
ka kb
x1
ka
x2
ka
x2
ℓa
ka kb ka
ℓb
ℓb
Figure 2: Examples of operations • all elements of colors from K1 have history of length 1; • all elements of colors from K2 have history of length at least 2. See Figure 2 for an illustration of the data structure operation.
4.2
Algorithm
The algorithm uses a stack over the alphabet Unmarked to maintain the triple ⟨α∅ , β∅ , c∅ ⟩ as in the unary case and a multi-stack over the alphabet K = Marked ∪ Below × {tmp} , split into K1 = Below ∪ Current ∪ Below × {tmp} and K2 = Above, to maintain the set of candidate nodes v colored with ⟨αv , βv , γv ⟩. Additionally, after processing each tag the multistack satisfies the following conditions: • there are no elements of colors from Below × {tmp}; • the length of the history of a candidate node is one plus the distance between the current node and the closest common ancestor of the current node and the candidate node. After processing each tag, we will perform the following emit and flush subroutines: (emit) for each ⟨α, β, γ⟩ ∈ Marked such that Range(⟨α, β, γ⟩) = {⊤} extract elements of color ⟨α, β, γ⟩ and emit the iterator; (flush) for each ⟨α, β, γ⟩ ∈ Marked such that Range(⟨α, β, γ⟩) = {⊥} extract elements of color ⟨α, β, γ⟩ and discard the iterator; where
[ Range ⟨α, β, γ⟩ = α δ(γ, β(q), q ′ ) . q,q ′ ∈Q
When processing opening and closing tags, we use two operations on triples, which are based on Lemmas 2 and 3. 12
• For a triple ⟨α, β, γ⟩ and γ ′ , we define Openγ ′ ⟨α, β, γ⟩ = ⟨α′ , β ′ , γ ′ ⟩ S where α′ (q) = q′ ∈Q α(δ(γ, β(q), q ′ )) and β ′ = id. • For triples ⟨α, β, γ⟩ and ⟨α′ , β ′ , γ ′ ⟩, we define Close ⟨α, β, γ⟩, ⟨α′ , β ′ , γ ′ ⟩ = ⟨α′′ , β ′′ , γ ′′ ⟩ where α′′ = α, β ′′ (q) = β(δ(γ ′ , β ′ (init), q)), and γ ′′ = γ. We begin with both the stack and the multi-stack empty. Before reading any tags, we push the triple ⟨αroot , id, $⟩ to the stack. Recall that ( {⊤} q is final αroot (q) = {⊥} q is not final and $ is a reserved element of Σ such that δ($, q, q ′ ) = q. The stack is now non-empty and it will always be non-empty after a tag is processed, unless an unbalanced closing tag is encountered. When an opening tag c ⟨ is read, • let ⟨α∅ , β∅ , γ∅ ⟩ be the triple at the top of the stack; • push to the stack the triple Openc ⟨α∅ , β∅ , γ∅ ⟩ ; • multi-push according to the function Marked ∋ ⟨α, β, γ⟩ 7→ Openc ⟨α, β, γ⟩ ∈ Above extended by identity to Below × {tmp} (which does not matter because there are no elements of colours from Below × {tmp} in the multi-stack); • insert the current node with colour Openč ⟨α∅ , β∅ , γ∅ ⟩ ∈ Current into the multi-stack; • emit, flush, and continue. When a closing tag ⟩ is read, • pop ⟨α∅ , β∅ , γ∅ ⟩ from the stack; • if the stack becomes empty, terminate with an error; • pop ⟨α∅′ , β∅′ , γ∅′ ⟩ from the stack; • push to the stack the triple Close ⟨α∅′ , β∅′ , γ∅′ ⟩, ⟨α∅ , β∅ , γ∅ ⟩ ; • multi-swap according to the function Below ∪ Current ∋ ⟨α, β, γ⟩ 7→ Close ⟨α∅′ , β∅′ , γ∅′ ⟩, ⟨α, β, γ⟩ , tmp ∈ Below×{tmp} extended by identity to Above ∪ Below×{tmp}; 13
• multi-pop; • multi-swap according to the function Marked ∋ ⟨α′ , β ′ , γ ′ ⟩ 7→ Close ⟨α′ , β ′ , γ ′ ⟩, ⟨α∅ , β∅ , γ∅ ⟩ ∈ Marked , Below × {tmp} ∋ ⟨α, β, γ⟩, tmp 7→ ⟨α, β, γ⟩ ∈ Below ; • emit, flush, and continue. Note that the functions used in multi-swaps respect the split of K into K1 and K2 . In the first multi-swap this is obvious. In the second one, the second rule maps elements of K1 to elements of K1 . To seethe constraint holds for the first rule, recall that Close ⟨α′ , β ′ , γ ′ ⟩, ⟨α∅ , β∅ , γ∅ ⟩ = ⟨α′ , β ◦ β ′ , γ ′ ⟩ where β(q) = δ(β∅ (init), q). Clearly, ⟨α′ , β ′ , γ ′ ⟩ ∈ Above implies ⟨α′ , β ◦ β ′ , γ ′ ⟩ ∈ Above, and similarly for Below and Current. Hence, the first rule also respects the split into K1 and K2 . Correctness of the algorithm follows from Lemmas 1–3 applied separately to each node, the choice of the initial triple pushed to the ordinary stack, and the semantics of the multi-stack operations. The complexity guarantees follow from the guarantees for the multi-stack.
5
Data structure implementation
It remains to show that we can implement the Candidate Data Structure operations to work in constant time. This is not trivial, since a naïve implementation— storing explicit stacks for each element in the structure—would result in a linear number of operations for each multi-push, multi-pop, and multi-swap.
5.1
Intuition
Before defining the implementation let us outline the challenges that arise from the requirements stated in Section 4.1 and how they drive the design given in Section 5.2. Buckets The key insight is that the effect of these operations is the same for all elements of the same color. Instead of physically maintaining separate stacks for each element we can maintain buckets, one for each color. In each bucket we hold a list of elements that currently inhabit that color. If we did not have to maintain the color history—i.e. support popping—the implementation would be straightforward, as all other operations amount to adding to buckets, relabeling, or emptying them. Logs To maintain the history we keep a log of events for each bucket, implemented with a stack. On the stack we put pointers to the heads of the lists that were moved into the given bucket in the previous push. When we push, 14
we move the heads of the lists into their new buckets, which might result in a concatenation of two or more lists. When we pop, we take the pointers to those heads, decouple the lists, and move them back to appropriate buckets. Invalidate Supporting extract introduces nuance. The naïve implementation— walking through the list in the bucket—has two issues. Firstly, it can cause staleness, as log entries might point to nodes that were already emitted; a multi-pop could then reintroduce a node back into the data structure after it was extracted. This could be alleviated by an additional level of indirection in the node that would contain a staleness bit, so that popping could identify and ignore stale nodes. The second issue, however, is that such an implementation does not provide constant delay enumeration: each node has to have its staleness bit flipped before all of them are returned. To obtain our result we cannot touch every node that gets extracted, instead we need to maintain and propagate information about on the level of buckets. The idea is to have extract operations mark the emptied bucket with an Invalidate event on top of its log. During the pop, when we encounter a bucket with a fresh Invalidate event on top of its log, we know that any lists that get moved back from that bucket have been already emitted. Because a push always moves entire buckets, this means that all the source buckets are now stale and we can propagate the Invalidate event back to them. This only works under the assumption that K is two disjoint sets—K1 is never stale and always has an empty log. Otherwise, inserting to a bucket with an Invalidate event would be possible and break the data structure.
5.2
Formal definition
We will now formalize this intuition and provide its implementation in pseudocode (Algorithm 1). The Candidate Data Structure over K = K1 ∪ K2 holds: 1. a global operation counter op; 2. a collection of |K| buckets: (Bk )k∈K , each containing either nothing or a list of candidates defined by two candidate nodes: head and tail, accessible via functions head(·) and tail(·). 3. for each bucket Bk a log Ek : a stack of events; an event can be of one of two kinds: • a Move event: a pointer to a candidate node, a color, and the timestamp of its source multi-push as given by the operation counter; or • an Invalidation event: a token with a timestamp corresponding to the source extract operation. A candidate node is a doubly-linked list node holding a candidate, its direct successor, and direct predecessor. This is sufficient to implement all our operations. We assume a fixed, consistent order of iteration over K.
15
Algorithm 1 Pseudocode of the data structure. 1: procedure Create() 2: op ← 0 3: for k ∈ K do 4: Bk ← None 5: Ek ← new Stack 6: procedure Insert(x, k) 7: N ← new Node(x) 8: if Bk = None then 9: head(Bk ) ← N 10: tail(Bk ) ← N 11: else 12: M ← head(Bk ) 13: head(Bk ) ← N 14: N.next ← M 15: M.prev ← N 16: procedure MultiPop() 17: for k ∈ K do 18: Bknew ← Bk 19: Lk ← new List 20: invSrck ← False , invDestk ← False 21: for k ∈ K2 do 22: while Ek .top.timestamp = op − 1 do 23: e′ ← Ek .pop() 24: if e′ is Invalidate then: 25: invSrck ← True 26: else ▷ e′ is Move 27: let e′ = Move(op∗ , N ∗ , k∗ ) 28: if invSrck then: 29: if k∗ ∈ K2 then: 30: invDestk∗ ← True 31: else 32: ℓ∗ ← (head : N ∗ , tail : tail(Bknew )) 33: Lk∗ .append(ℓ∗ ) 34: if N ∗ .prev ̸= None then 35: tail(Bknew ) ← N ∗ .prev 36: N ∗ .prev.next ← None 37: N ∗ .prev ← None 38: else 39: Bknew ← None 40: 41: 42: 43: 44: 45:
for k ∈ K do for ℓ∗ ∈ Lk do AssignOrConcat(Bknew , ℓ∗ ) if k ∈ K2 and invDestk then Ek .push(Invalidate(op − 1)) op ← op − 1
46: procedure MultiPush(f ): 47: for k ∈ K do 48: Bknew ← None 49: 50: 51: 52: 53: 54:
for k ∈ K do if Bk ̸= None then AssignOrConcat(Bfnew , Bk ) (k) Ef (k) .push(Move(op, head(Bk ), k)) B ← B new op ← op + 1
55: procedure MultiSwap(f ) 56: for k ∈ K do 57: Bknew ← Bk 58: Ekmove ← new Stack 59: 60: 61: 62: 63: 64: 65: 66: 67:
for k ∈ K do if Bk ̸= None then AssignOrConcat(Bfnew , Bk ) (k) while Ek .top.timestamp = op − 1 do Efmove .push(Ek .pop()) (k) for k ∈ K do Bk ← Bknew while Ekmove .top ̸= None do Ek .push(Ekmove .pop())
68: procedure extract(k) 69: if Bk ̸= None then 70: N ← head(Bk ) 71: Bk ← None 72: N ∗ ← new Node(N.candidate) 73: N ∗ .next ← N.next 74: N.candidate ← None 75: N.next ← None 76: if k ∈ K2 then 77: Ek .push(Invalidate(op − 1)) 78: return N ∗ 79: else 80: return None 81: procedure AssignOrConcat(L1 , L2 ) 82: ▷ Auxiliary function 83: if L1 = None then 84: L 1 ← L2 85: else 86: tail(L1 ).next ← head(L2 ) 87: head(L2 ).prev ← tail(L! ) 88: tail(L1 ) ← tail(L2 )
Create. Initialize an empty structure with |K| empty buckets with empty logs, and set op ← 0.
16
Insert x of color k ∈ K1 . Create a candidate node N holding the candidate x. If Bk is empty, set N as the head and tail of Bk ; otherwise, append the current head of Bk after N and set N as the head of Bk . Extract elements of color k. Store head(Bk ) in a node N and set Bk to empty. Return an exact clone of N as the iterator. To ensure that we do not hold onto the memory of the returned list—recall that N may be referenced in an existing M ove event—we nullify N ’s value and successor. Finally, if k ∈ K2 , put an Invalidate event on top of Ek with timestamp of op. Multi-push according to f : K → K2 . Let us call the current buckets (Bkcurr )k∈K . We initialize empty buckets (Bknew )k∈K . For each k ∈ K: • if Bkcurr is empty, there is nothing to be done; otherwise, let L be the list stored in Bkcurr ; • if Bfnew (k) is still empty, then set it to contain L; otherwise, append L after new curr the current list in Bfnew (k) and set tail(Bf (k) ) ← tail(Bk ); • finally, add an entry pointing to head(Bkcurr ) with timestamp op and color k to the log Ef (k) . At the end of the operation we set Bk ← Bknew for each k, discard Bknew , and set op ← op + 1. Multi-pop. Similarly, let us call the current buckets (Bkcurr )k∈K . We initialize a collection of buckets (Bknew )k∈K to the same state as the current buckets. To take into account node staleness we first investigate the tops of all logs Ek for k ∈ K2 : if the top of Ek is an Invalidate event with timestamp equal to op, we remember that the bucket is stale and pop that event. For each color in K2 we also remember whether it should be marked as stale after the pop. Then, the operation proceeds in two phases: first, we detach all nodes that need to be moved from their current lists; after that we perform the move. We allocate |K| lists of nodes: phase one will populate them, such that the k-th list will contain nodes that need to be moved to bucket k ∈ K; phase two will empty the lists and perform the merges. For each k ∈ K2 remove each Move entry in the log Ek with a timestamp equal to op − 1 and process it: • let N be the node pointed to by the event and let ℓ be its color; • if k was detected as stale we can ignore the node as it is guaranteed to have been extracted; however, if ℓ ∈ K2 , we need to mark ℓ to become stale after the pop; • otherwise (if k is not stale), put N into the ℓ-th node list, detach it from its preceding node (if any), and set tail(Bknew ) to that preceding node (or set B new ← None if no such node exists). 17
After phase one we move the lists from Bknew to Bkcurr for each k ∈ K and progressively merge each node from the node lists to the end of its bucket (like in multi-push). Finally, for each color that was marked as becoming stale, we push an Invalidate event with the timestamp of op − 2. At the end of the operation we discard the copies of buckets and set op ← op − 1. Multi-swap according to f : K → K. This operation is equivalent to the multi-push except for the changes to the log. After copying all the buckets we also pop the frames of all logs with timestamp equal to op − 1 and put them to the side as a list (e′k )k∈K . After the bucket manipulation is done we move each e′k to the top of Ef (k) .
5.3
Proof of correctness
The correctness of the data structure hinges on the correctness of the multi-pop. Indeed, it is easy to see that a sequence of operations without any pops would correctly model the interface from Section 4.1. The only delicate part is the invalidation mechanism. An important observation is that the only nodes that are relevant are those which were heads of buckets during any multi-push. All other nodes are simply successors of these (perhaps indirectly) and are therefore always moved and extracted the same way as their heads. We want the data structure to maintain the following invariant: Lemma 4. If in some Ek there is a Move log entry with timestamp op − 1 and a head node that has already been extracted, then there is also an Invalidate entry with timestamp op − 1 at the top of Ek . Proof. This is trivially true when there are no extract operations. Assume an extract on bucket Bk happens. The head of Bk is emitted and Invalidate with timestamp op − 1 is created on top of Ek . Assume there exists a Move log entry with timestamp op − 1, color ℓ, and which points to a node N extracted from Bk . This entry has to reside in Ek , since N is in Bk . Naturally, the condition is satisfied for now. Since N is now absent from the data structure after the extract, the only other Move logs pointing to N have to have a lower timestamp. In particular, if there exist any such entries, then one with timestamp op − 2 exists in Eℓ . When a multi-pop happens, the Invalidate tag is popped, Bk is marked as stale, and the marker is propagated to Eℓ with the timestamp op − 2, hence the invariant is maintained. As long as Lemma 4 holds, the invalidation mechanism succeeds in ensuring that nodes emitted via extract stay out of the buckets and any stale log entries pointing to them are ignored. Complexity analysis. We observe that Insert and Extract take constant time, and Create and MultiPush take O(|K|) time. The cases of MultiPop and MultiSwap are more subtle given that they perform a while-loop inside of a 18
for-loop: we observe that (1) each MultiPush adds at most |K| elements with the same timestamp op at a time, (2) Extract is called at most |K| times for the same timestamp op at a time, and (3) we can inductively argue that MultiPop also adds at most |K| Invalidate events with the same timestamp op at a time; and so, the while-loops in MultiPop and MultiSwap are entered at most |K| entered across all k ∈ K values in the for-loop. We conclude that these procedures also take O(|K|) time. The space taken by the data structure is limited by the number of active candidates and at most |K| entries on logs per each multi-push that was not yet popped, which satisfied the requirements of Section 4.1.
6
Related work
Evaluation of queries over streamed trees has been studied extensively, especially for XML and XPath [17, 4, 24, 29, 18]. This line of work shares our motivation of evaluating queries without materializing the entire input tree, but the works focus on specific query languages or fragments and do not provide an earliestanswering guarantee for arbitrary unary MSO queries. Earliest query answering was studied in works of Gauwin, Niehren, and Tison [11, 13], where the central notions are bounded delay and bounded concurrency. These notions are in spirit close to our work, as they measure logicallyminimal resource requirements: the former measures how long an answer has to remain pending, and the latter how many of these answers have to coexist. The main difference is that they focus on restrictions of languages where these measures can actually be bounded, whereas our results hold for arbitrary MSO queries. Arguably, the closest reference to our work is a recent paper of Muñoz and Riveros [24], which studies streaming enumeration over nested documents for MSO queries. Their framework provides strong enumeration guarantees, including constant update time in data complexity and output-linear delay enumeration (which implies constant delay for unary queries). However, they do not guarantee earliest query answering. They discuss how to perform a form of early answering via ∆-enumeration, and this allows the algorithm to print an output only if could not have been printed at an earlier step. However, earliest query answering has an additional condition: an output should be printed when it is guaranteed to be a solution for any continuation of the tree. As far as we know, there is no way to modify a visibly pushdown annotator A into A′ such that performing ∆-enumeration on A′ simulates earliest query answering for A.
7
Conclusions
We have studied earliest query answering for unary MSO queries over streamed trees, under data complexity. The query, or equivalently the automaton, is fixed, and the algorithm processes the input with constant update time while
19
outputting and discarding answers as soon as the current prefix forces them. Several questions remain open. The first question is whether the construction is tight in combined complexity. In this paper, all constants may depend on the automaton. This is unavoidable to some extent, but the precise dependence on the query is not well understood. In particular, compiling MSO formulas into deterministic automata may incur a large blow-up, and our construction further manipulates objects derived from the state space of this automaton. It would be interesting to determine whether this cost is inherent for earliest query answering, or whether substantially smaller representations are possible for natural query languages such as XPath or JSONPath fragments. A second direction concerns the representation of outputs. We have used an enumeration model in which answers are returned as nodes, via an iterator. This is natural when the output is viewed as a set of positions, but it does not exploit situations where the set of answers has a more concise description. Already over words, one may have queries whose answer set consists, for example, of all positions between the first two occurrences of a given letter. In such cases, enumerating every answer may be less appropriate than returning a symbolic representation of the whole set. Understanding which concise representations are compatible with earliest query answering seems nontrivial: one would need to define when such a representation is itself forced by the current prefix, and how it can be maintained without hiding an implicit enumeration cost. Another practical issue is the interaction between query optimization and parsing optimization. Our model treats the input as a stream of already tokenized events, and charges the algorithm once for each symbol that is read. This abstracts away an important source of efficiency in practical JSONPath engines: systems such as rsonpath [14] and JSONSki [20] do not merely optimize the logical evaluation of a query, but also use the query to guide the lexer. They may scan for relevant structural characters, avoid materialixing irrelevant subtrees, or skip regions of the input that cannot contribute to the answer. From this perspective, skipping is not just an implementation trick, but part of the query optimization problem itself. It would be interesting to develop a model of earliest query answering in which the query optimizer is allowed to choose a parsing strategy together with the streaming evaluation strategy. Such a model should make explicit which fragments of the input may be skipped, what information about them must still be computed, and how the cost of these parsing operations is measured. The earliest setting adds a further difficulty: skipping a fragment is sound only if doing so does not delay an answer that would already be forced by a prefix inside the skipped fragment, and does not discard information needed to reject or maintain pending candidates. Understanding when parsing-level optimizations preserve earliest answers, and how they can be combined with candidate-optimal memory management, seems to be an important step toward applying the present theory to practical JSONPath engines. Finally, JSONPath filters allow comparisons between selected values, and in particular may compare subtrees for equality. Such tests go beyond the 20
finite-state view used in this paper. In a streaming setting, subtree equality is especially problematic: deciding it may require retaining one subtree while the other is being read, or comparing two subtrees whose relevant parts have not yet both appeared in the stream. This interacts badly with both earliest output and space optimality. A natural open problem is to identify fragments with subtree equality that still admit earliest evaluation with constant update time, or to prove that such comparisons necessarily require larger memory, delayed output, or a different output model. This question is related to the automata-theoretic approach to efficient XPath evaluation, in particular the linear-time evaluation result of Bojańczyk and Parys [6], but the combination of subtree equality with earliest streaming evaluation appears to require different techniques.
References [1] S. Abiteboul. Querying semi-structured data. In F. N. Afrati and P. G. Kolaitis, editors, Database Theory - ICDT ’97, 6th International Conference, Delphi, Greece, January 8-10, 1997, Proceedings, Lecture Notes in Computer Science, pages 1–18. Springer, 1997. [2] S. Abiteboul, P. Buneman, and D. Suciu. Data on the web: from relations to semistructured data and XML. Morgan Kaufmann, 2000. [3] R. Alur and P. Madhusudan. Adding nesting structure to words. In O. H. Ibarra and Z. Dang, editors, Developments in Language Theory, pages 1–13, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. [4] C. Barloy, F. Murlak, and C. Paperman. Stackless processing of streamed trees. In L. Libkin, R. Pichler, and P. Guagliardo, editors, PODS’21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Virtual Event, China, June 20-25, 2021, pages 109–125. ACM, 2021. [5] M. Benedikt and C. Koch. XPath leashed. ACM Comput. Surv., 41(1):3:1– 3:54, 2008. [6] M. Bojańczyk and P. Parys. XPath evaluation in linear time. 58, 2011. [7] P. Bourhis, J. L. Reutter, F. Suárez, and D. Vrgoc. JSON: data model, query languages and schema specification. In E. Sallinger, J. V. den Bussche, and F. Geerts, editors, Proceedings of the 36th ACM SIGMODSIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19, 2017, pages 123–135. ACM, 2017. [8] H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, C. Löding, S. Tison, and M. Tommasi. Tree automata techniques and applications, 2008.
21
[9] D. Durner, V. Leis, and T. Neumann. JSON Tiles: Fast Analytics on SemiStructured Data. In Proceedings of the 2021 International Conference on Management of Data, pages 445–458, Virtual Event China, June 2021. ACM. [10] M. Ganardi, L. Jachiet, M. Lohrey, and T. Schwentick. Low-latency sliding window algorithms for formal languages. In A. Dawar and V. Guruswami, editors, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022, IIT Madras, Chennai, India, December 18-20, 2022, LIPIcs, pages 38:1–38:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. [11] O. Gauwin, J. Niehren, and S. Tison. Bounded Delay and Concurrency for Earliest Query Answering. In A. H. Dediu, A. M. Ionescu, and C. MartínVide, editors, Language and Automata Theory and Applications, volume 5457, pages 350–361. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. Series Title: Lecture Notes in Computer Science. [12] O. Gauwin, J. Niehren, and S. Tison. Earliest query answering for deterministic nested word automata. In M. Kutyłowski, W. Charatonik, and M. Gębala, editors, Fundamentals of Computation Theory, pages 121–132, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. [13] O. Gauwin, J. Niehren, and S. Tison. Queries on XML streams with bounded delay and concurrency. Information and Computation, 209(3):409–442, Mar. 2011. [14] M. Gienieczko, F. Murlak, and C. Paperman. Supporting Descendants in SIMD-Accelerated JSONPath. In Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 4, ASPLOS ’23, pages 338–361, New York, NY, USA, 2024. Association for Computing Machinery. [15] G. Gottlob, C. Koch, and R. Pichler. The complexity of XPath query evaluation. In F. Neven, C. Beeri, and T. Milo, editors, Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 9-12, 2003, San Diego, CA, USA, pages 179–190. ACM, 2003. [16] G. Gottlob, C. Koch, and R. Pichler. Efficient algorithms for processing XPath queries. ACM Trans. Database Syst., 30(2):444–491, 2005. [17] G. Gou and R. Chirkova. Efficient algorithms for evaluating xpath over streams. In Proceedings of the 2007 ACM SIGMOD international conference on Management of data, pages 269–280, Beijing China, June 2007. ACM. [18] T. J. Green, A. Gupta, G. Miklau, M. Onizuka, and D. Suciu. Processing XML streams with deterministic automata and stream indexes. ACM Trans. Database Syst., 29(4):752–788, 2004. 22
[19] S. Gössner, G. Normington, and C. Bormann. JSONPath: Query Expressions for JSON, Feb. 2024. [20] L. Jiang and Z. Zhao. JSONSki: Streaming Semi-Structured Data with Bit-Parallel Fast-Forwarding. In ASPLOS, pages 200–211. ACM, 2022. [21] K. G. Larsen, J. Nelson, and H. L. Nguyên. Time lower bounds for nonadaptive turnstile streaming algorithms. In R. A. Servedio and R. Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 803–812. ACM, 2015. [22] M. Lohrey and M. L. Schmid. MSO-enumeration over SLP-compressed unranked forests. TheoretiCS, 5, 2026. [23] S. Melnik, A. Gubarev, J. J. Long, G. Romer, S. Shivakumar, M. Tolton, and T. Vassilakis. Dremel: Interactive analysis of web-scale datasets. Proc. VLDB Endow., 3(1):330–339, 2010. [24] M. Muñoz and C. Riveros. Streaming Enumeration on Nested Documents. ACM Transactions on Database Systems, 49(4):1–39, Dec. 2024. [25] S. Palkar, F. Abuzaid, P. Bailis, and M. Zaharia. Filter Before You Parse: Faster Analytics on Raw Data with Sparser. Proc. VLDB Endow., 11(11):1576–1589, 2018. [26] C. Riveros, N. V. S. Jan, and D. Vrgoc. REmatch: a novel regex engine for finding all matches. Proc. VLDB Endow., 16(11):2792–2804, 2023. [27] J. Robie, M. Dyck, and J. Spiegel. XML Path Language (XPath) 3.1. Recommendation, W3C, Mar. 2017. [28] J. W. Thatcher and J. B. Wright. Generalized finite automata theory with an application to a decision problem of second-order logic. Math. Syst. Theory, 2(1):57–81, 1968. [29] X. Wu and D. Theodoratos. A survey on XML streaming evaluation techniques. VLDB J., 22(2):177–202, 2013.
23