Compact Representation for Answer Sets of n-ary Regular Queries
Kazuhiro Inabaa , Haruo Hosoyaba National Institute of Informatics, 2-1-1, Hitotsubashi, Chiyoda-ku, Tokyo, Japanb The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo, Japan

Abstract
An n-ary query over trees takes an input tree t and returns a set of n-tuples of the nodes of t. In this paper, a compact
data structure is introduced for representing the answer sets of n-ary queries defined by tree automata. Despite thatthe number of the elements of the answer set can be as large as |t|n , our representation allows storing the set using
only O(|t|) space. Several basic operations on the sets are shown to be efficiently executable on the representation.
Key words: Tree Automata; Data Structure; XML

1. Introduction
The finite state automaton is a well-known model for representing properties for trees and strings. The class ofqueries definable by finite state automata is called regular and is widely used both in theory and in practice. A numberof query formalisms are shown to be equivalent or subsumed by regular queries. Examples of such formalisms include,
regular expression pattern [1], monadic second-order logic [2], µ-calculus [3], Core XPath [4], monadic Datalog [5],Boolean attribute grammar [6], etc.
In this paper, we are interested in the space complexity of the n-ary queries defined by tree automata. An n-ary
query over trees takes an input tree t and returns a set of n-tuples of the nodes of t. The number of elements in theanswer set of an n-ary query may be as large as |t|n where |t| is the number of the nodes of t. Also, usually, storinga set of |t|n elements requires at least c|t|n space where c is the space required to store a single element (in this case,one n-tuple of nodes). The O(|t|n ) space consumption is unavoidable if the elements are chosen in a perfectly randommanner; it is a well-known consequence from information theory. Note, however, we are interested in more practical,
less random queries. Queries defined by tree automata have much more structure than random ones. By exploiting
the structural characteristics of regular queries, we can represent the answer sets in some compressed form.
Let us explain the idea by an example. Consider the regular query “select all pair of nodes (x, y) such that x is in
the left subtree of the root node and y is in the right subtree of the root node” with the input tree t as in Figure 1. Thenthe answer set consists of nine elements: {(v1 , v4 ), (v2 , v4 ), (v3 , v4 ), (v1 , v5 ), (v2 , v5 ), (v3 , v5 ), (v1 , v6 ), (v2 , v6 ), (v3 ,v6 )}. Obviously, if an input tree has n nodes both in the left and the right subtrees, the size of the answer set will be n2 ,which is quadratic in the number 2n + 1 of the nodes. Our approach for avoiding the quadratic blow-up is to represent
the answer set by a symbolic expression, instead of computing the concrete list of elements. For this example, we
can represent the answer set by the expression {v1 , v2 , v3 } × {v4 , v5 , v6 } where × denotes the product of two sets.
Counting the number of variables vi and the operator, the length of the expression is 7 instead of 9. Analogously, forthe general case with n nodes in both the left and the right subtrees, the answer set can be represented by an expressionof length 2n + 1, which consumes only linear space with respect to the size of the input tree.
The contribution of our work is in establishing the expression-based compact representation as illustrated above.
In fact, only two operators–∪· (disjoint union) and ∗ (a slight variant of product)–are necessary for achieving thelinear-size representation of the answer sets of regular queries. We show that for any fixed n-ary regular query and an
input tree t, the answer set can always be represented by an expression on ∪· and ∗ with every leaf expression beinga singleton set of an input node. By sharing common sub-expressions, such an expression can always be represented
Email addresses: kinaba@nii.ac.jp (Kazuhiro Inaba), hahosoya@is.s.u-tokyo.ac.jp (Haruo Hosoya)
Preprint submitted to Theoretical Computer Science

June 8, 2010*t = v0
v1
v2

v4
v3

v5 v6

Figure 1: Sample Input

∪
∪
{v
}
∪ 3 ∪ {v6}{v1} {v2}{v4} {v5}Figure 2: Query Result in Expression-Based Representation

by a dag of size at most 4 · 3n |δA ||t| where |δA | is the size of the deterministic automaton representing the query.
That is, regardless of the arity n of the query, the data complexity with respect to the size |t| of the input is always
linear! As an instance, Figure 2 shows the expression-dag (just a tree in this case) representation of the query result of
the previous example. The factor complexity 3n is sufficiently low for queries with small n such as binary or ternary
queries, which are the most common cases occur in practice; after all, it is quite rare to run, say, a 100-ary query.
Our dag-based representation is named SRED (Set Representation by Expression Dags), which enjoys good timecomplexity as well as size-efficiency. The SRED representation of the answer set can always be computed fromthe input tree t in time O(3n |δA ||t|), regardless how large the actual answer set is. Also, evaluation (or we could
say, decompression) of a SRED to yield the concrete list of answer tuples can be done in time O(n2 |a|), where|a| is the number of the answers. By combining these two steps, we obtain an algorithm for regular queries in
the optimal data complexity O(|t| + |a|). More than that, on SRED, we can carry out the following important
operations without decompressing it: (1) S ELECTION: for an answer set s, the SRED representation of the set s[i:u] ={(v1 , . . . , vi−1 , vi+1 , . . . , vn ) | (v1 , . . . , vi−1 , u, vi+1 , . . . , vn ) ∈ s} can be computed in time O(3n h|δA |) where his the height of the input tree for binary trees and is the height times log |t| for unranked trees, (2) P ROJECTION:
the set s@i = {vi | (v1 , . . . , vn ) ∈ s} can be computed in time O(3n h|δA ||s@i |). Besides the expression-based
representation, another key idea of SRED is to remember for every sub-expression the least common ancestor of thenodes contained in the set represented by the sub-expression. The information allows locating the leaf expressions
containing each input node in time proportional only to the height of the expression-dag.
Related Work. SRED has much similarity to the Complete Answer Aggregate (CAA) introduced by Meuss, Schulz,
and Bry [7] as a compact representation of answer sets of queries. The size of a CAA is O(h|t|) which is competitive
to our O(|t|). CAA is also suitable for applying several operations such as membership testing. The main advantage
of our work is that it supports arbitrary regular queries, which is strictly more expressive than the query language usedin [7]. Though an attempt to represent the answer sets of regular queries with CAA is given by Filiot and Tison [8]through a decomposition of queries, the space complexity is O(|t|dϕ ) for some constant dϕ depending on the query,which grows to n in the worst case. Furthermore, precise complexity of operations such as selection or projection for
CAA was not estimated.
An algorithm (FFG algorithm) for answering regular n-ary queries in the optimal time complexity O(|t| + |a|) is
shown by Flum, Frick, and Grohe [9]. Since no compact data structure was used in their work, the FFG algorithm
requires O(|a|) space to be carried out. In fact, our algorithm can be regarded as a space-efficient variant of the FFG
algorithm. The expression dag generated in our algorithm precisely corresponds to the set operations executed in the
FFG algorithm. On the other hand, the class of queries that the FFG algorithm can be applied to is more general than
our algorithm. The FFG algorithm can also be used for querying n-tuples of sets of nodes of graphs that have a tree
decomposition, while our algorithm only supports queries for n-tuples of nodes of trees. It will be future work to
determine whether our compact representation of the answer sets can be extended to more general classes of query.
Another related area of research is becoming hot recently, namely, linear-delay enumeration of MSO query results[10, 11]. In their algorithms, the input tree of a query is first converted to an intermediate data structure that allows
linear-delay enumeration of the query results. Since the intermediate data structure is of linear size with respect to the
input tree, it can also be used as a compact representation of the answer set. Compared to our SRED representation,
however, their data structures are concentrated only for linear-delay enumeration and other operations such as selection
or projection are not supported.
2

Outline. The paper is organized as follows. In Section 2, we introduce basic notations on trees and tree languages.
Section 3 presents a simple but inefficient algorithm for executing n-ary queries on binary trees, as the basis of ourmain algorithm. Then, in Section 4, we give our main results. We introduce the SRED data structure as a compact
representation of set of tuples, and show that just by using SRED, the previous naı̈ve algorithm can be turned into one
that efficiently produces a compact answer-set representation. Section 5 shows an application to XML processing.
Section 6 concludes.
2. Preliminaries
In this paper, we mainly consider binary trees, in which every node has either zero or two children. Generalization
to the trees with other arity is briefly mentioned in the end of Section 4. Let Σ be a finite alphabet that is a disjoint
union of two alphabets Σ(0) and Σ(2) . A binary tree (or simply, a tree) over Σ is a tuple t = (Vt , label t , lt t , rt t , root t )
(0)
(2)
(0)
(2)
where Vt is the disjoint union Vt ∪· Vt of finite sets of nodes, label t : Vt → Σ(0) ∪· Vt → Σ(2) is the label(2)function, lt t , rt t : Vt → Vt is the left- and right- child function respectively, and root t ∈ Vt is the root node. We(0)(2)
call the nodes in Vt leaf nodes, and the nodes in Vt branching nodes. We require a tree to satisfy the following
conditions: (1) rooted: there is no node v ∈ Vt such that lt t (v) = root t or rt t (v) = root t , (2) acyclic: there is nonode v ∈ Vt that is reachable from itself by finite applications of lt t and rt t , and (3) tree-formed: for any non-root
node v ∈ Vt \ {root t }, there exists a unique node u called the parent of v such that lt t (u) = v ∨ rt t (u) = v. A
structure only satisfying (1) and (2) is called a dag. For v1 , v2 ∈ Vt , the binary order relation v1 ≤t v2 is defined tohold if and only if v2 is reachable from v1 by zero or finitely many applications of lt t and rt t . We usually omit thesubscript t if clear from the context. By |t| we denote the number |Vt | of the nodes. We use the notation a⟨v1 , v2 ⟩ todenote a node v such that label t (v) = a, lt t (v) = v1 , and rt t (v) = v2 .
For a tree t, we assume that each node v ∈ Vt can be stored on memory in constant space independent from |t|.
In practice, this implies the assumption that the tree t fits in the address space of the computer and each node can be
represented by a single pointer. We also assume that the operations label , lt, rt, and ≤ can be executed in constanttime. In particular, we can test the relation ≤ in constant time by, e.g., the preorder/postorder numbering [12]. Again
by the assumption that |t| fits in the address space, preorder and postorder numbers can be stored in constant space.
A tree language over Σ is a set of trees over Σ. By TΣ , we denote the set of all trees over Σ. An importantclass of tree languages is defined in terms of tree automata. A (bottom-up deterministic) tree automaton over Σ is atuple A = (QA , δA , FA ) where QA is the set of states, δA : (Σ(0) ∪ (Σ(2) × QA × QA )) → QA is the transition
function, and FA ⊆ QA is the set of accepting states. The subscript A is omitted if clear from the context. A run
of a tree automaton A on the input( tree t is the unique function) ρ : Vt → QA such that ρ(v) = δA (label t (v)) iflabel t (v) ∈ Σ(0) and ρ(v) = δA label t (v), ρ(lt t (v)), ρ(rt t (v)) if label t (v) ∈ Σ(2) . The automaton accepts t if andonly if ρ(root t ) ∈ FA . By L(A), we denote the set of trees accepted by A. A tree language is said to be regular if it
is equal to L(A) for some tree automaton A.
3. N-ary Regular Tree Queries
As a basis of our algorithm for computing the compact representation of answer sets, we first explain a basic
bottom-up algorithm for regular queries with O(|t|n+1 ) time complexity, which has already been known in the literature. Our new algorithm is obtained by changing the data structure used in the algorithm, as explained later in
Section 4.
An n-ary query for trees over Σ is a function ψ that maps each tree t ∈ TΣ to a set of n-tuples of its nodes. Let
(0)
(2)
(0)
(2)
B = {0, 1}, Σn = Σ(0) × Bn , Σn = Σ(2) × Bn , and Σn = Σn ∪· Σn . For a tree language L ⊆ Σn , an n-ary
query defined by L is the function ψL (t) = {(v1 , . . . , vn ) | mark (t, v1 , . . . , vn ) ∈ L} where mark (t, v1 , . . . , vn ) is atree m = (Vt , label m , lt t , rt t , root t ) with label m (v) = (label t (v), b1 · · · bn ) where bi = 1 if v = vi and 0 otherwise.
Intuitively, a query defined by a language L selects a tuple (v1 , . . . , vn ) if and only if L contains a tree obtained bymarking each selected node vi with 11 . A query defined by a regular language L is called a regular query. In the rest
1 In general, L may contain “ill-marked” trees that have two or more nodes marked as b = 1 for the same i and hence can never be in the range
iof mark . Such trees, however, are simply ignored and have no effect on the definition of ψL .

3

of the paper, we assume the regular language L to be given as a tree automaton A such that L = L(A). Nevertheless,our algorithm can be applied, without changing the data complexity, to many other query formalisms as long as they
define regular languages by first compiling them into tree automata and then running the algorithm.
The most naı̈ve algorithm for a regular n-ary query is, to try all possible markings. Given an automaton A overΣn and a tree t, for all (v1 , . . . , vn ) ∈ Vtn we generate the marked tree mark (t, v1 , . . . , vn ) and test whether it isaccepted by A. If it is, (v1 , . . . , vn ) is an answer and hence we output it. This algorithm takes O(|t|n+1 ) time,
because computing each run of A takes O(|t|) time and we try |t|n runs in total.
Another approach is to try all marking parallelly by a single bottom-up run. The following recursive procedure
QUERY-RUNA takes a node v of t and computes a table containing the result of the parallel marking run.
QUERY-RUNA (v)
1: r ← new 2-dimensional array of size |QA | × 2n with each element initialized to ∅2: if label (v) ∈ Σ(0) then3:for each ((label (v), b0 ) 7→ q0 ) ∈ δA do
4:
r[q0 , b0 ] ← singleton(v, b0 )5: else if label (v) ∈ Σ(2) then6:
r1 ← QUERY-RUNA (lt(v))
7:r2 ← QUERY-RUNA (rt(v))
8:for each ((label (v), b0 ), q1 , q2 7→ q0 ) ∈ δA do
9:for each disjoint b0 , b1 , b2 in 00 . . . 00 to 11 . . . 11 do
10:r[q0 , b0 |b1 |b2 ] ← r[q0 , b0 |b1 |b2 ] ∪· singleton(v, b0 ) ∗ r1 [q1 , b1 ] ∗ r2 [q2 , b2 ]11: return r
By singleton(v, β1 · · · βn ) we denote the singleton set {(u1 , . . . , un )} where ui = v if βi = 1 and ui = ⊥ if
βi = 0. Here, ⊥ is a special symbol not contained in Vt . In line 9, for each disjoint iterates over pairs of theform (b1 = β11 · · · β1n , b2 = β21 · · · β2n ) ∈ (Bn )2 such that for all 1 ≤ i ≤ n, at most one of {β0i , β1i , β2i }is 1, with β01 · · · β0n = b0 . Note that b0 is determined by the outer δA loop and fixed during each single innerloop. The operator | is for bitwise-or and ∪· is disjoint union of sets (the operands are indeed disjoint, as explainedlater). The operator ∗ is a kind of “product” operation that combines two sets of tuples, defined as follows: S ∗ T ={(u1 , · · · , un ) | (s1 , · · · , sn ) ∈ S, (t1 , . . . , tn ) ∈ T, ∀i : (ui = si ∧ ⊥ = ti ) ∨ (⊥ = si ∧ ui = ti )}. For example,{(v1 , ⊥, ⊥), (v2 , ⊥, ⊥)} ∗ {(⊥, ⊥, v3 ), (⊥, ⊥, v4 )} is equal to {(v1 , ⊥, v3 ), (v1 , ⊥, v4 ), (v2 , ⊥, v3 ), (v2 , ⊥, v4 )}. Let
us remark that we never take ∗-product of sets that have tuples with non-⊥ nodes on the same position, as will beshown in Lemma 1.
Let us explain how the algorithm works. Let r = QUERY-RUNA (v) for a node v ∈ Vt . For each q ∈ QA andb = β1 · · · βn ∈ Bn , r[q, b] is a set of n-tuples over the set Vt ∪ {⊥}. A tuple in (Vt ∪ {⊥})n is called a partial answer
to the query. For example, (v1 , ⊥) is a partial answer that selects the node v1 as the first coordinate and leaves thesecond coordinate to be selected later. Intuitively, r[q, b] is the set of partial answers α such that, if a tree is marked
according to α, then at the node v, the run of the automaton A reaches the state q. For example, if (v1 , ⊥) ∈ r[q, b],
it means that “if the node v1 is marked as the first component of the answer and no node in the subtree under v ismarked as the second component, A reaches the state q at node v”. As an example, let us assume v to be a leaf
node labeled σ ∈ Σ(0) and A to define a binary query. Suppose δA has the following four rules: δA ((σ, 00)) = q1 ,δA ((σ, 01)) = q2 , δA ((σ, 10)) = q1 , and δA ((σ, 11)) = q2 . Then, the table r = QUERY-RUNA (v) is:r[q1 , 00] = {(⊥, ⊥)} r[q1 , 01] = ∅r[q2 , 00] = ∅r[q2 , 01] = {(⊥, v)}

r[q1 , 10] = {(v, ⊥)} r[q1 , 11] = ∅r[q2 , 10] = ∅r[q2 , 11] = {(v, v)}.

The set r[q1 , 00] contains (⊥, ⊥) because if we do not select any node below v, the automaton reaches the state q1 . On
the other hand, the set r[q2 , 00] is empty, because we cannot reach the state q2 at node v if we do not select any node.
Similarly, r[q1 , 01] is empty, because we cannot reach the state q1 if we select the second coordinate of the answer.
On the other hand, we have r[q2 , 01] = {(⊥, v)}, because if we choose v as the second coordinate, the automaton
reaches the state q2 .
The index b of r called flag denotes the already selected coordinates; the i-th coordinate of the elements of r[q, b]
is non-⊥ if and only if the i-th bit of b is 1. Thus we have the following lemma.
4Lemma 1. Let r = QUERY-RUNA (v) for some v and (u1 , . . . , un ) ∈ r[q, β1 · · · βn ]. For all 1 ≤ i ≤ n, we have(ui ∈ Vt and v ≤t ui ) if βi = 1, and ui = ⊥ if βi = 0.
Proof. The proof is by induction on the structure of the tree rooted at v. If v is a leaf node, r[q, b] is either empty (thecase ((label (v), b) 7→ q) ∈/ δA ) or a singleton set singleton(v, b). The lemma obviously holds for the empty case, andthe latter case is also immediate from the definition of singleton(v, b).
If v is a branching node, by the construction of the set r[q, b], the condition (u1 , . . . , un ) ∈ r[q, b] implies that
we have (u1 , . . . , un ) ∈ singleton(v, b0 ) ∗ r1 [q1 , b1 ] ∗ r1 [q2 , b2 ] for some q1 , q2 ∈ QA and disjoint b0 , b1 , b2 ∈ Bn
with b0 |b1 |b2 = b. Now, assume that the i-th bit (βi ) of b is 0, which at the same time means that the i-th bits of
b0 , b1 , and b2 is 0. By the definition of singleton and the induction hypothesis, the i-th coordinate of each elementof singleton(v, b0 ), r1 [q1 , b1 ], and r2 [q1 , b2 ] is ⊥. Hence, from the definition of ∗, ui also has to be ⊥ in this case.
Contrarily assume βi = 1, which means that exactly one of the i-th bits of b0 , b1 , and b2 is 1. Then, if we take any
three tuples (s1 , . . . , sn ) ∈ singleton(v, b0 ), (t1 , . . . , tn ) ∈ r1 [q1 , b1 ], and (w1 , . . . , wn ) ∈ r2 [q2 , b2 ], exactly one ofsi , ti , and wi is non-⊥ due to the induction hypothesis. Let us call x the non-⊥ node. We have v ≤t x, because
si = v, and by induction hypothesis lt(v) ≤t ti and rt(v) ≤t wi if they are not ⊥. The definition of ∗ tells us that ui
is one of such-chosen x, which is non-⊥, and v ≤t x as desired.
The lemma ensures two disjointness properties in the procedure QUERY-RUNA . First, the ∗-product is always
taken between the sets with disjoint selected-coordinates. That is, we need to compute S ∗ T only for the sets S, T
such that (. . . , vi , . . .) ∈ S and (. . . , ui , . . .) ∈ T implies either vi or ui is ⊥. This holds because in line 10 (∗ occurs
only here) of the QUERY-RUNA algorithm, the flags b0 , b1 , and b2 are disjoint. Note that, for such a case, we have
|S ∗ T | = |S| · |T |. Second, ∪· is indeed taken between disjoint sets. This is because the operands of ∪· (whose only
one occurrence is in line 10) are constructed by ∗-product either over different flags or over different states, i.e., theunion is of the form singleton(v, b0 ) ∗ r1 [q1 , b1 ] ∗ r2 [q2 , b2 ] ∪· singleton(v, b′0 ) ∗ r1 [q1′ , b′1 ] ∗ r2 [q2′ , b′2 ] where either(b0 , b1 , b2 ) ̸= (b′0 , b′1 , b′2 ) or (q1 , q2 ) ̸= (q1′ , q2′ ). Disjointness in the former case follows from Lemma 1, and in thelatter case it follows from the determinism of the automaton A.
The answer set of the query can be calculated from the result of QUERY-RUNA applied to the root node, namely,r = QUERY-RUNA (root t ). For each q ∈ FA , recall that the set r[q, 1 · · · 1] is the set of tuples such that “if the tree
is marked according to the tuple, A reaches the state q at the root node”, which is by definition the answer set.
∪
Theorem 2. ψL(A) (t) = q∈FA QUERY-RUNA (root t )[q, 11 · · · 11].
Proof. Let v1 , . . . , vn ∈ Vt be fixed and ρ be the unique run on the tree mark (t, v1 , . . . , vn ) by A. Let v ∈ Vt . Let
partial (v) = (u1 , . . . , un ) with ui = vi if v ≤t vi and otherwise ui = ⊥. Let flags(v) = β1 · · · βn with βi = 1 ifv ≤t vi and otherwise βi = 0. We can prove for all v in Vt the following claim:
for all q ∈ QA , partial (v) ∈ QUERY-RUNA (v)[q, flags(v)] if and only if q = ρ(v).
We have (v1 , . . . , vn ) ∈ QUERY-RUNA (root t )[q, 11 · · · 11] if and only if q = ρ(root t ), by applying the claim to theroot node v = root t . It, together with the definition of ψL(A) , proves the desired result.
Proof of the claim is done by induction on the structure of the tree rooted at v. Consider the case when v
is a leaf. From the leaf-node case of the QUERY-RUNA procedure, we have QUERY-RUNA (v)[q, flags(v)] =singleton(v, flags(v)) = {partial (v)} when ((label (v), flags(v)) 7→ q) is in δA , and otherwise it is empty. Thisalready shows the claim for the leaf case, because the discriminating condition is equivalent to q = ρ(v).
Consider the case when v is a branch node. Let r1 = QUERY-RUNA (lt(v)) and r2 be that of rt(v). We firstshow the “if” direction; assume q = ρ(v). Let q1 = ρ(lt(v)), q2 = ρ(rt(v)), b0 = β1 · · · βn where βi = 1
iff v = vi , b1 = flags(lt(v)), and b2 = flags(rt(v)). Note that flags(v) = b0 |b1 |b2 , and by the assumption
q = ρ(v), it must be the case q = δA ((label (v), b0 ), q1 , q2 ); the line 10 of the procedure QUERY-RUNA is executedin this variable binding. That is, the set QUERY-RUNA (v)[q, flags(v)] is a superset of singleton(v, b0 ) ∗ r1 [q1 , b1 ] ∗r2 [q2 , b2 ]. By the induction hypothesis, the latter set contains the unique element of the product singleton(v, b0 ) ∗{partial (lt(v))} ∗ {partial (rt(v))}, which is partial (v) as desired. For the “only if” direction, assume partial (v) ∈QUERY-RUNA (v)[q, flags(v)]. From the construction of this set in QUERY-RUNA , it implies that for some disjoint b0 |b1 |b2 = flags(v) and q1 , q2 ∈ QA with δA ((label (v), b0 ), q1 , q2 ) = q, it must be the case partial (v) ∈singleton(v, b0 ) ∗ r1 [q1 , b1 ] ∗ r2 [q2 , b2 ]. But by Lemma 1, it can only happen when b1 = flags(lt(v)), b2 =5flags(rt(v)), partial (lt(v)) ∈ r1 [q1 , b1 ], and partial (rt(v)) ∈ r2 [q2 , b2 ]; other entries of r1 and r2 cannot generate partial (v) by ∗-product. Now, from the induction hypothesis we obtain q1 = ρ(lt(v)) and q2 = ρ(rt(v)), andtherefore, ρ(v) = q.
What is the time complexity of this algorithm? For each node v ∈ Vt , the procedure QUERY-RUNA is applied
exactly once. In other words, the procedure is called |t| times. In the body of the procedure, the case for Σ(2)labels is computationally harder; the outer loop requires |δA | iterations, the inner loop for b1 , b2 requires at most 3n
iterations (for each of n bits we have 3 choices–the bit belongs to either b1 , b2 , or none of the two), and inside theloop, one ∪· operation and two ∗ operations are required. Note that the result of those set operations can be as large asO(|t|n ) in the worst case. As long as we represent such sets as a concrete collection of tuples, the operation ∗ needto enumerate all its output elements. Hence it takes at least O(|t|n ) time. Altogether, the total time complexity is stillhigh: O(3n |δA ||t|n+1 ).
One approach for reducing the complexity is to do some preprocessing before running the algorithm, as proposedby Flum, Frick, and Grohe [9]. Their algorithm consists of 3-passes over the input tree; the first two passes detect,for each node, whether or not each entry r[q, b] really needs to be computed. The last pass is essentially the same as
QUERY-RUNA , but skipping the computation for “unneeded” entries r[q, b]. This optimization leads to the complexity O(3n |δA |(|t| + |a|)) where |a| is the size of the answer set. The complexity of this strategy with respect to the data
size seems optimal in some sense; if the size of the input is |t| and the size of the output is |a|, even just reading andwriting those data already takes O(|t| + |a|) time, doesn’t it?
Yes, it is optimal–as long as you write down all the elements of the answer set as the output. In the next section,
to avoid the issue, we propose here to use a compressed representation of the answer set, whose size can be boundedby O(|t|).
4. SRED: Set Representation by Expression Dags
In this section, we propose a novel data structure named SRED for representing the answer sets of n-ary regularqueries. The size of SRED is always bounded by the input size O(|t|), regardless how large the actual set it represents
is. Just by using the data structure instead of normal sets in the QUERY-RUNA procedure, we obtain linear running
time with respect to |t|, as well as a compact representation of the answer set. We first give the formal definitionof SRED, then show how easily and efficiently it can be adapted to the QUERY-RUNA algorithm, and finally, show
several important set-operations can be directly applied to SRED.
4.1. Definition
The idea of our compact representation is quite simple. To represent a set s, we use a syntax tree r of an expressionthat evaluates to s. For example, let r1 and r2 be the root nodes of the syntax-tree representations of sets s1 and s2(we write s1 = Jr1 K and s2 = Jr2 K, respectively). Then we denote the set s1 ∪· s2 by the tree r = cup⟨r1 , r2 ⟩. To
denote the set Jr1 K ∪· (Jr2 K ∗ Jr3 K), we use cup⟨r1 , star⟨r2 , r3 ⟩⟩. Note that, by allowing sharing of subtrees (i.e., using
syntax-dags instead of syntax-trees, which allows a node like cup⟨r1 , r1 ⟩), each operation can be executed in constanttime, because it is just a creation of one new node. Since the algorithm QUERY-RUNA carries out set operations at
most O(3n |δA ||t|) times, under this representation of sets, the running time of QUERY-RUNA is in O(3n |δA ||t|), andso is the size of the output dag representing the answer set.
Let us formally explain the syntax-dag-based representation, which we call SRED (Set Representation by Expression Dags). An answer set of an n-ary query over a tree t is represented by a dag of the following BNF, for
β1 · · · βn ∈ Bn \ {0 · · · 0}:
ST β1 ···βn ::= emp⟨⟩ | ne⟨NST β1 ···βn ⟩ST 0···0 ::= emp⟨⟩ | unit⟨⟩
NST β1 ···βn ::= cup⟨v, NST β1 ···βn , NST β1 ···βn ⟩ with v ∈ Vt
| star⟨v, NST α1 ···αn , NST γ1 ···γn ⟩ with v ∈ Vt and αi ⊕ γi = βi
| sing⟨v, β1 · · · βn ⟩ with v ∈ Vt
6

EVAL (r)1: if r ≡ emp⟨⟩ then2:
return ∅3: else if r ≡ unit⟨⟩ then4:
return {(⊥, · · · , ⊥)}5: else if r ≡ ne⟨r ′ ⟩ then6:
return EVAL-NE(r′ )EVAL-NE (r)1: if r ≡ cup⟨v, r1 , r2 ⟩ then2:
return EVAL-NE(r1 ) ∪· EVAL-NE(r2 )3: else if r ≡ star⟨v, r1 , r2 ⟩ then4:
return EVAL-NE(r1 ) ∗ EVAL-NE(r2 )5: else if r ≡ sing⟨v, b⟩ then6:
return singleton(v, b)

PRODUCT-AT (v, r1 , r2 )UNION-AT (v, r1 , r2 )1: if r1 ≡ emp⟨⟩ or r2 ≡ emp⟨⟩ then
1: if r1 ≡ emp⟨⟩ then2:
return emp⟨⟩
2:
return r2
3: else if r1 ≡ unit⟨⟩ then
3: else if r2 ≡ emp⟨⟩ then4:
return r2
4:
return r1
5: else if r1 ≡ ne⟨r1′ ⟩ and r2 ≡ ne⟨r2′ ⟩ then 5: else if r2 ≡ unit⟨⟩ then6:
return ne⟨cup⟨v, r1′ , r2′ ⟩⟩6:
return r1
7: else if r1 ≡ ne⟨r1′ ⟩ and r2 ≡ ne⟨r2′ ⟩ then
SINGLETON-AT (v, β1 · · · βn )8:return ne⟨star⟨v, r1′ , r2′ ⟩⟩1: if β1 · · · βn = 0 · · · 0 then2:
return unit⟨⟩
3: else4:
return ne⟨sing⟨v, β1 · · · βn ⟩⟩Figure 3: Basic Operations on SRED

where a ⊕ c = b if and only if a ̸= c and b = 1 or a = b = c = 0. Note that, for enabling fast navigation
as will be explained later, we record the node v ∈ Vt at each operator. Also for efficiency, we specially treat theempty set (represented by emp⟨⟩) and the unit set ({(⊥, . . . , ⊥)}, represented by unit⟨⟩), so that they do not occur
at operand positions. For example, cup⟨v, emp⟨⟩, emp⟨⟩⟩ is ill-formed because emp⟨⟩ occurs as operands of cup.
We call a node labeled emp, unit, or ne a set-node, and a node labeled cup, star, or sing a neset-node (ne stands
for non-empty). For a neset-node r ∈ NST β1 ···βn , we denote by dim(r) the number of 1s in β1 · · · βn . Notethat we have dim(sing⟨v, β1 · · · βn ⟩) ≥ 1, dim(cup⟨v, r1 , r2 ⟩) = dim(r1 ) = dim(r2 ), and dim(star⟨v, r1 , r2 ⟩) =dim(r1 ) + dim(r2 ).
By avoiding emp⟨⟩ and unit⟨⟩ to occur at non-root position, we can evaluate the syntax-dag by a straightforward
recursion shown in Figure 3, in a time complexity proportional to the size of the answer set.
· 2 can be computed in constant time and the productLemma 3. Assume the disjoint union s1 ∪s( s1 ∗s2 can be computed)
in time O(n|s1 ∗ s2 |) for s1 , s2 ̸= ∅. Then for a neset-node r, EVAL-NE(r) runs in time O (k + 1)n|EVAL-NE(r)|where k = dim(r) − 1.
Proof. Without loss of generality, we assume the disjoint union s1 ∪· s2 to take one unit computation step, products1 ∗ s2 to take n|s1 ∗ s2 | steps, and singleton(v, b) to take n steps. Under the assumption, we prove by induction thatthe computation of EVAL-NE(r) takes at most T (k, r) = 2((2k + 1)n|EVAL-NE(r)|) − 1 steps.
If r is a node labeled sing, we have k ≥ 0 and thus T (k, r) ≥ 2n − 1 ≥ n.
If r ≡ cup⟨v, r1 , r2 ⟩, by induction hypothesis, s1 = EVAL-NE(r1 ) and s2 = EVAL-NE(r2 ) can be computed intime T (k, r1 ) + T (k, r2 ) = 2((2k + 1)n|EVAL-NE(r)|) − 2 steps (note that |EVAL-NE(r)| = |EVAL-NE(r1 )| +· the obtained computation|EVAL-NE(r2 )|, because it is disjoint union). Adding one unit computation step for the ∪,steps is equal to T (k, r) as desired.
If r ≡ star⟨v, r1 , r2 ⟩, by induction hypothesis, s1 = EVAL-NE(r1 ) and s2 = EVAL-NE(r2 ) can be computedin T (k1 , r1 ) + T (k2 , r2 ) steps for some k1 + k2 + 1 = k. Note that neither s1 nor s2 is empty, because return· Thus, their sizes |s1 |, |s2 | are less than or equal tovalues of EVAL-NE are built up only from singleton, ∗, and ∪.

7

EVAL-NE-1BY1 (r, callback)1: if r ≡ cup⟨v, r1 , r2 ⟩ then2:
EVAL-NE-1BY1(r1 , callback )3:
EVAL-NE-1BY1(r2 , callback )4: else if r ≡ star⟨v, r1 , r2 ⟩ then5:
EVAL-NE-1BY1(r1 , λp.EVAL-NE-1BY1(r2 , λq.callback (p ∗ q)))6: else if r ≡ sing⟨v, b⟩ then7:
callback (singleton(v, b))
Figure 4: One-by-one generation of the element tuples of a SRED|s1 | · |s2 | = |s1 ∗ s2 | = |EVAL-NE(r)|. The total number of steps can be estimated as follows:
T (k1 , r1 ) + T (k2 , r2 ) + n|s1 ∗ s2 | = 2((2k1 + 1)n|s1 |) − 1 + 2((2k2 + 1)n|s2 |) − 1 + n|s1 ∗ s2 |≤ 2((2k1 + 2k2 + 2)n|s1 ∗ s2 |) − 2 + n|s1 ∗ s2 |= 2(2kn|s1 ∗ s2 |) − 2 + n|s1 ∗ s2 |≤ 2((2k + 1)n|EVAL-NE(r)|) − 1=

T (k, r).

Theorem 4 (E VALUATION ). Under the same complexity assumption on ∪· and ∗ as in Lemma 3, for a set-node r, theset EVAL(r) can be computed in time O(n2 |EVAL(r)|).
Proof. Immediately follows from Lemma 3, because by definition of dim, the number k is at most n − 1.
The complexity assumption is satisfied by, for instance, representing the concrete sets by a doubly-linked list oftuples. Disjoint union can be implemented by the list concatenation, and the ∗-product is implemented by a doubleloop over two operand sets. Purely functional catenable lists [13] might be an option, in particular when it is desirable
to avoid destructive updates. Another interesting implementation is shown in Figure 4. Instead of constructing thewhole set of tuples, it generates each element tuple one-by-one; it takes a procedure callback and calls it back for eachelement tuple. It also has the same time complexity as the normal EVAL-NE.
The reader may notice that the evaluation EVAL(r) visits every node below r at least once. Hence, from Theorem 4, we can conclude that the number of nodes below r is O(n2 |EVAL(r)|). In fact, we are able to give a tighter
upper-bound.
Theorem 5 (O UT-S IZE -B OUND ). For a set-node r, the number of nodes of a dag rooted at r is at most 2n|EVAL(r)|.
Proof. Proof is by induction on structure of a neset-node r, showing that the procedure EVAL-NE is called at mostS(k, r) = 2(k + 1)|s| − 1 times during the computation of s = EVAL-NE(r), where k = dim(r) − 1. If this isproved, the desired bound 2n|EVAL(r)| immediately follows from the fact k ≤ n − 1.
If r is a node labeled sing, the number of procedure calls is 1, which is bounded by S(k, r) ≥ S(0, r) = 1. Ifr ≡ cup⟨v, r1 , r2 ⟩, the number of procedure calls is S(k, r1 )+S(k, r2 )+1 = 2(k+1)|EVAL-NE(r)|−2+1 = S(k, r).
If r ≡ star⟨v, r1 , r2 ⟩, the number of procedure calls is S(k1 , r1 ) + S(k2 , r2 ) + 1 for some k1 + k2 + 1 = k. Using
the fact that |EVAL-NE(r1 )| and |EVAL-NE(r2 )| is no more than |EVAL-NE(r)|, this is bounded by S(k, r).
Note that this is the worst case estimation. In many cases, particularly when |EVAL(r)| is large compared to theoriginal input tree of the query, the number of nodes is much smaller than the bound as will be shown in the next
subsection. What we can tell from Theorem 5 is that, even in the worst case, we are not losing much. Since it is a setof n-tuples, Representation of the same set in an uncompressed form at least requires n|EVAL(r)| space, which only
differs by a constant-factor from ours.

84.2. N-ary Query Algorithm Using SREDThe basic three operations used in the algorithm QUERY-RUNA are defined on SRED as in Figure 3. Note that,to avoid emp⟨⟩ and unit⟨⟩ to occuring in operand positions, we deal with the nodes specially. For example, since∅ ∪ s = s for any set s, when either one of the operands of the UNION-AT operation is an emp⟨⟩ node, it returns
the other operand rather than constructing a new cup node. The correctness of those short-cuts are based on easy
set-theoretic equations, and summarized in the following two lemmas.
Lemma 6. The following four properties hold.
1. EVAL(emp⟨⟩) = ∅,2. EVAL(SINGLETON-AT(v, b)) = singleton(v, b),
3. EVAL(UNION-AT(v, r1 , r2 )) = EVAL(r1 ) ∪· EVAL(r2 ), and
4. EVAL(PRODUCT-AT(v, r1 , r2 )) = EVAL(r1 ) ∗ EVAL(r2 ).
Proof. The property 1 and 2 hold by the definition of EVAL. The property 3 follows from ∅ ∪· s = s ∪· ∅ = s. Notethat in the implementation of UNION-AT we have not explicitly considered the case when r1 or r2 is unit⟨⟩, because
it is covered by the emp⟨⟩ cases; disjointness implies that unit⟨⟩ can be added only to emp⟨⟩. The property 4 is fromthe equations ∅ ∗ s = s ∗ ∅ = ∅ and {(⊥, . . . , ⊥)} ∗ s = s ∗ {(⊥, . . . , ⊥)} = s.
Lemma 7. Let S-QUERY-RUNA be a procedure obtained by replacing (1) ∅ in the procedure QUERY-RUNA
with emp⟨⟩, (2) x ∪· y with UNION-AT(v, x, y), (3) x ∗ y with PRODUCT-AT(v, x, y), and (4) singleton(v, b)
with SINGLETON-AT(v, b). Then, EVAL(S-QUERY-RUNA (t)[q, b]) = QUERY-RUNA (t)[q, b] for any t ∈ TΣA ,q ∈ QA , and b ∈ Bn .
Proof. Clear from Lemma 6, by induction on the structure of r.
Now, we have the following two main theorems of this paper: the answer set of an n-ary regular query canefficiently be computed as a SRED in linear time with respect to the size of the input, and it is also compact; its size
is linear, no matter how large the actual answer set is.
Theorem 8 (Q UERYING ). For any n-ary regular query ψL(A) and a tree t, we can compute a SRED r that represents
the answer set (i.e., EVAL(r) = ψL(A) (t)) in time O(3n |δA ||t|).
Proof. Let r′ = S-QUERY-RUNA (t). We can compute the desired SRED r by combining all r′ [q, 1 · · · 1]’s with q ∈FA by UNION-AT. From Theorems 2 and 7, this satisfies the equation EVAL(r) = ψL(A) (t) (here, representing the∪ operation in Theorem 2 by UNION-AT is justified because it is indeed a disjoint union, due to the premise that A is
deterministic). The complexity analysis goes similar to the case of QUERY-RUNA . The procedure S-QUERY-RUNA
is applied once for each node in t (that is, the procedure is invoked at most |t| times), and at each node, the innermost
loop body (line 10) is executed at most 3n |δA | times. Different from the case of QUERY-RUNA , this time, set
operations UNION-AT and PRODUCT-AT in the loop body run in constant time. Hence, the total time complexity of
S-QUERY-RUNA is O(3n |δA ||t|). The last union-phase requires at most |FA | − 1 execution of UNION-AT, whosetime consumption can asymptotically be ignored.
Theorem 9 (I N -S IZE -B OUND ). The number of nodes of the SRED r in Theorem 8 is at most 4 · 3n |δA ||t| + |FA | − 1.
Proof. Clear from the proof of Theorem 8 (note that in each loop body, up to 4 nodes are created).
Before developing further algorithms on SRED, it is worth remarking here that Theorem 8 combined with Theorem 4 can be used to derive the “optimal” data complexity for regular queries.
Corollary 10 (It follows also from Corollary 4.5 of [9]). The time complexity of n-ary regular query with respect tothe data size is O(|t| + |a|), where |t| is the size of the input node, and |a| is the size of the output answer set.

9

PROJ (i, r)
1: if r ≡ emp⟨⟩ then2:
return ∅3: else if r ≡ ne⟨r ′ ⟩ then4:
return PROJ-NE(i, r′ )PROJ-NE (i, r)
1: if r ≡ cup⟨v, r1 , r2 ⟩ then2:
return PROJ-NE(i, r1 ) ∪ PROJ-NE(i, r2 )3: else if r ≡ star⟨v, r1 , r2 ⟩ (with r1 ∈ NSTβ1 ···βn ) then4:
if βi = 1 then return PROJ-NE(i, r1 ) else return PROJ-NE(i, r2 )5: else if r ≡ sing⟨v, β1 · · · βn ⟩ then6:
return {v}

SEL-NE (i, u, r)
SEL (i, u, r)
1: if r ≡ cup⟨v, r1 , r2 ⟩ and v ≤ u then
1: if r ≡ emp⟨⟩ then2:
return UNION-AT(v, SEL-NE(i, u, r1 ), SEL-NE(i, u, r2 ))2:
return emp⟨⟩
3: else if r ≡ star⟨v, r1 , r2 ⟩ (with r1 ∈ NSTβ1 ···βn ) and v ≤ u then
3: else if r ≡ ne⟨r ′ ⟩ thenif βi = 1 then return PRODUCT-AT(v, SEL-NE(i, u, r1 ), r2 )4:
return SEL-NE(i, u, r′ ) 4:
5:else return PRODUCT-AT(v, r1 , SEL-NE(i, u, r2 ))6: else if r ≡ sing⟨v, β1 · · · βn ⟩ and v = u then7:
return SINGLETON-AT(v, β1 · · · βi−1 βi+1 · · · βn )8: else return emp⟨⟩
Figure 5: Projection and selection on SREDThis way of using SRED just as an intermediate structure can be regarded as a different presentation of essentiallythe same algorithm as that of [9]. As mentioned before, in [9], the complexity was achieved by running two preprocessing phases that determine whether each entry r[q, b] (in their notation, Sat t,q ) at each node contributes to thefinal query answer, and skipping the computation of the unneeded part. Two cases are considered to be unneeded: thecase that we can never reach states in FA at the root node starting from the state q, and the case that the set r[q, b] istaken a product with the empty set afterward in the computation. In our algorithm, the former case is dealt with by
splitting the construction of a SRED structure and the evaluation of it; the construction has low complexity, and theevaluation is only done on the states that reach FA states. The latter case is detected by the special treatment of emp⟨⟩
node in the PRODUCT-AT procedure; a SRED that is taken product with an emp⟨⟩ set is discarded and thus is neverevaluated. Despite the similarity, we believe that our presentation is much simpler and easier to understand. In ouralgorithm, structure of the first naı̈ve algorithm QUERY-RUNA is kept unchanged, and only just a few set-operations
are replaced with (almost trivially correct) SRED-based operations in Figure 3.
4.3. Direct Manipulation of SREDSRED is not only useful as an intermediate data structure for generating the concrete result of answer tuples. In
fact, it allows manipulation of the represented set directly on SRED, without evaluation. Here, we give an implementation of two important operations on SRED, namely, PROJECTION and SELECTION. For a set s of n-tuples and1 ≤ i ≤ n, PROJECTION s@i = {vi | (v1 , . . . , vn ) ∈ s} is the set of i-th coordinates of s. Given an element u,
SELECTION s[i:u] = {(v1 , . . . , vi−1 , vi+1 , . . . , vn ) | (v1 , . . . , vi−1 , u, vi+1 , . . . , vn )} is the set of tuples in s such thatthe i-th coordinate is u. As an example of a use-case of the two operations, consider the following scenario: first
we apply PROJECTION @1 to an answer set, sort the result in some preferable order, and with each element u of the
projected set, apply SELECTION [1:u] to get the remaining coordinates. In this way, we can enumerate the answers ofqueries in a user-specified order on the first coordinate, rather than in the default order of EVALUATION procedure.
On SRED representation of the answer sets, those two operations can be carried out in time proportional to theheight of the input tree. That is, we do not need to traverse the whole structure of SRED, nor to re-traverse the original
input tree. Figure 5 is the implementation, which is straightforwardly obtained from the distributivity of projection
and selection over disjoint union, etc.
Theorem 11 (P ROJECTION ). By using memoization, the procedure PROJ(i, r) computes the set EVAL(r)@i in timeO(min(m, 3n h|δA ||EVAL(r)@i |)) where h is the height of the original input tree t, and m is the number of nodes ofr.
10

SIZE (r)SIZE-NE (r)1: if r ≡ emp⟨⟩ then
1: if r ≡ cup⟨v, r1 , r2 ⟩ then2:
return 0
2:
return SIZE-NE(r1 ) + SIZE-NE(r2 )3: else if r ≡ ne⟨r ′ ⟩ then
3: else if r ≡ star⟨v, r1 , r2 ⟩ then4:
return SIZE-NE(r′ ) 4:
return SIZE-NE(r1 ) × SIZE-NE(r2 )5: else if r ≡ sing⟨v, β1 · · · βn ⟩ then6:
return 1
Figure 6: Computing the size of the set represented by a SRED

Proof. Correctness immediately follows from the following set-theoretic properties of projection: ∅@i = ∅, (s1 ∪·s2 )@i = (s1 )@i ∪ (s2 )@i , (s1 ∗ s2 )@i = (s1 )@i if the i-th coordinates of s1 is non-⊥ and (s1 ∗ s2 )@i = (s2 )@iotherwise, and {(u1 , . . . , un )}@i = {ui } for ui ̸= ⊥.
For the complexity, we assume the procedure PROJ-NE to be memoized, i.e., if it is applied to the same arguments
second time, it immediately returns the previous result in constant time. We can implement such memoization byusing a hash table. Then the body of the procedure PROJ-NE is executed at most once per each node of r. Actually,
the procedure PROJ-NE is applied only to the nodes in NST β1 ···βn with βi = 1. The number of such nodes is at
most 4 · 3n |δA |h|EVAL(r)@i |, because to have βi = 1, it must have a descendant node of the form sing⟨v, · · ·⟩ withv ∈ EVAL(r)@i . Since such a SRED node is created only at the ancestor nodes of v in the original input tree (whose
number is at most h|EVAL(r)@i |) and at each of such ancestors at most 4 · 3n |δA | SRED nodes are created, we obtain
the bound on the number of the nodes. By using list-concatenation for representing set-union2 , the body of PROJ-NE
can be executed in constant time. Hence, we obtain the desired complexity.
Theorem 12 (S ELECTION ). By using memoization, the procedure SEL(i, u, r) computes the SRED representation of
the set EVAL(r)[i:u] in time O(min(m, 3n h|δA |)) where m is the number of nodes of r.
Proof. Correctness immediately follows from the following set-theoretic properties of selection: ∅[i:u] = ∅, (s1 ∪·s2 )[i:u] = (s1 )[i:u] ∪· (s2 )[i:u] , (s1 ∗ s2 )[i:u] = (s1 )[i:u] ∗ s2 if the i-th coordinates of s1 is non-⊥ and (s1 ∗ s2 )[i:u] =s1 ∗ (s2 )[i:u] otherwise, and {(u1 , . . . , un )}[i:u] = {(u1 , . . . , ui−1 , ui+1 , . . . , un )} for ui = u. The side conditionv ≤ u in lines 1 and 3 is justified by Lemma 1; if the comparison does not hold, EVAL-NE(r) cannot contain u.
For the complexity, memoization ensures that the procedure SEL-NE is called at most once per each node of r.
Since the test v ≤ u succeeds only at the node constructed at an ancestor (in the tree t) of u, the procedure SEL-NE
is executed only on the nodes constructed at an ancestor of u, or their direct child. Note that the number of theancestor nodes in the input tree is at most h, and on each of such nodes at most 4 · 3n |δA | SRED-node is created. By,
multiplying them, we obtain the desired complexity.
Corollary 13 (M EMBERSHIP ). Given a SRED r and a tuple (u1 , . . . , un ) of nodes, we can test whether (u1 , . . . , un )is in EVAL(r) or not in time O(n min(m, 3n h|δA |)).
Proof. Repeat SELECTION n times.
Another interesting operation that can easily be executed on SRED without evaluation is, counting of the size ofthe represented set.
Theorem 14 (S IZE ). By using memoization, given a SRED r, the size of the represented set |EVAL(r)| can becomputed in time O(m) where m is the number of nodes of r.
Proof. Figure 6 shows the implementation. By memoization, the procedure SIZE-NE is called m times, and the
body of the procedure runs in constant time. Correctness follows from the following facts: |s1 ∪· s2 | = |s1 | + |s2 |,|s1 ∗ s2 | = |s1 | × |s2 |, and |{(u1 , . . . , un )}| = 1.
2 Precisely speaking, since it is not a disjoint union this time, list-concatenation based implementation may cause duplication. It, however, canbe removed by a linear time ‘uniq’ algorithm.

11Note that, the procedure SIZE-NE is computing the size of the represented set for all nodes in r. By using the size
information, the one-by-one enumeration procedure shown in Figure 4 is improved to a log-delay enumerator.
Corollary 15 (L OG -D ELAY-E NUM ). For a SRED r, we can enumerate the elements of EVAL(r) in log-delay afterO(m) time preprocessing. That is, in the enumeration process, the time required to output adjacent two elements areO(log2 |EVAL(r)|) for any adjacent pairs, and also the first element is generated in O(log2 |EVAL(r)|) time.
Proof. By using the size information obtained by SIZE-NE, without loss of generality we can assume |EVAL-NE(r1 )|≤ |EVAL-NE(r2 )| in line 1 to 3 of the EVAL-NE-1BY1 procedure, (otherwise swap r1 and r2 , which only changes
the order but not the enumerated set). Note that this implies 2 · |EVAL-NE(r1 )| ≤ |EVAL-NE(r)|.
Then, we can show that during the computation of EVAL-NE-1BY1(r, f ), we enter the procedure EVAL-NE-1BY1
at most log2 (|EVAL-NE(r)|) + k + 1 times between any two successive calls for f (and between the beginning of
the computation and the first call to f ), where k = dim(r) − 1. The same estimation log2 (|EVAL-NE(r)|) + k + 1
applies also to the number of times we leave the procedure between two successive calls for f (and between the lastcall to f and the end of the computation, under the assumption that tail-calls are optimized away). This proves thecorollary.
The proof of the above statement is by induction on structure of r. When r ≡ sing⟨v, β1 , . . . , βn ⟩, only one
call to f is made and between the call and the start of the computation of EVAL-NE-1BY1(r, f ), exactly one call to
EVAL-NE-1BY1 is made. Since log2 (|EVAL-NE(r)|) + k + 1 ≥ 1, we have proved the inductive statement for thiscase. When r ≡ cup⟨v, r1 , r2 ⟩, interval of two successive calls to f is at most max(log2 (|EVAL-NE(r1 )|) + k +1, log2 (|EVAL-NE(r2 )|) + k + 1) ≤ log2 (|EVAL-NE(r)|) + k + 1 by induction hypothesis. The delay to the first callto f is 1 + log2 (|EVAL-NE(r1 )|) + k + 1, which is less than or equal to log2 (|EVAL-NE(r)|) + k + 1, because of
our assumption on the size of r1 . Between the last call to f and the end of the computation, the number of times weleave the procedure can be made at most log2 (|EVAL-NE(r2 )|) + k + 1 ≤ log2 (|EVAL-NE(r)|) + k + 1; since thesecond call to EVAL-NE-1BY1 is a tail-call, return from the call can directly leave the whole computation3 . Whenr ≡ star⟨v, r1 , r2 ⟩, the delay is at most 1 + (log2 (|EVAL-NE(r1 )|) + k1 + 1) + (log2 (|EVAL-NE(r2 )|) + k2 + 1) forsome 1 + k1 + k2 = k. Since we have (log2 (|EVAL-NE(r1 )|) + log2 (|EVAL-NE(r2 )|)) = log2 (|EVAL-NE(r)|), theinduction statement is now proved.
4.4. Generalizations to Unranked Trees
So far, we have considered only binary trees. In many applications, however, we are interested in unranked trees
with varying number of child nodes. For example, in XML trees [14] such as XHTML documents, the number ofchildren may not be two, or even, may differ even between two nodes with the same label (e.g., an <ol> (orderedlist) node can have have an arbitrary number of <li> (list item) child nodes).
To deal with unranked trees, we encode such trees to binary trees. A widely used encoding is fc-ns encoding. In
a binary tree obtained as the fc-ns encoding of an unranked tree, the first child of each node is mapped to the firstchild of the corresponding node in the original unranked tree, and the second child of each node is mapped to thenext sibling in the unranked tree. It is a folklore result that the encoding preserves the regularity of queries, i.e., any
regular query for unranked trees can be converted to a regular query on the encoded trees. Hence, by first encoding theunranked input trees and the queries to the binary-tree form and then running S-QUERY-RUNA , we can compute thelinear-size representation of the answer sets of regular queries. One problem of fc-ns encoding is the time complexityof operations on SRED that depends on the factor h, the height of the tree. Suppose an original unranked tree has smallheight h0 and nodes with large number w0 (≃ |t|) of children (which is often the case for most XML documents).
The problem is that the height of the fc-ns encoded tree is O(h0 w0 ). To deal with such trees, we recommend using
another encoding, namely, the bb encoding, to reduce the complexity to O(h0 log w0 ). In bb encoding, the list ofchildren of each node is encoded to a balanced binary tree whose left-to-right sequence of leaf nodes corresponds tothe child sequence in the original tree. Such an encoding also preserves regularity, because the ‘first-child’ and the‘next-sibling’ relations remain regular. Moreover, since the height of a balanced binary tree is in the logarithmic orderof the number of the leaves, the height of the bb-encoded tree reduces to O(h0 log |t|).
3 Such tail-call optimization is performed in almost all practical compilers for popular programming languages. Even if it does not, the tailrecursion can easily be rewritten to an iteration by while-loop manually.

12

5. Application
SRED is developed for the XML transformation language MTran [15]. Let us illustrate the benefits of SRED by
the following pseudo code for XML translation:{gather x where x:<person> do<row><col>{gather y where x//<name>/y do y}</col>{gather z where z:<person> & document-order(z,x) do<col>· · ·</col>}</row>}The program takes a document containing a list of <person> elements and generates some triangular matrix table. The first query “x:<person>” lists up all the <person> elements, and for each of them, the second query“x//<name>/y” selects a descendant y of x labeled <name> (for simplicity, we assume that such y uniquely exists). If we really run for each x the second query, which takes in general O(|t|) time where |t| is the size of the tree,
total running time of the query becomes quadratic, because there may be linearly many <person> nodes. Rather, as
pointed out in [16], it is better to regard the second query as a binary query for selecting pairs (x, y). By using SRED,the answer set of such a binary query can be computed in linear time. Furthermore, by the SELECTION operation
followed by the EVALUATION operation, for each x we can obtain the corresponding y in time O(h0 log |t|). Total
running time reduces to O(h0 |t| log |t|). So far, we could have used the FFG algorithm [9] (or equivalently, querywith SRED directly followed by EVALUATION) for the same purpose, because its running time is linear under theassumption that y uniquely exists for each x. Consider, then, the third query that selects all <person> elements z
preceding x in the document order (preorder). Similarly, we run the query as a binary query for selecting pairs (x, z).
In this case, the size of the answer set is quadratic. If we use the FFG algorithm, we need O(|t|2 ) working spacefor carrying out the binary-query based approach. While, with SRED, it requires only O(|t|) working space. This
makes feasible to run the transformation over larger inputs, which could not be done without SRED due to memory
shortage.
6. Conclusion and Future Work
The paper introduced a data structure named SRED (Set Representation by Expression Dags), which allows representing answer sets of regular tree queries compactly. Here is the summary of its performance for the n-ary query
defined by an automaton with transition function δA , with an input tree t and an output set a:
Q UERYING
O(3n |δA ||t|)

E VALUATION
O(n2 |a|)Size (number of nodes) of SRED (= m)at most min(2n|a|, 4·3n |δA ||t|)Regardless how large the output answer set is, the time for computing its SRED representation is independent of it;
it is always linear with the size of the input. Evaluation (or decompression) of SRED only depends on the size ofthe answer set and is independent from the input size. The size of the SRED representation stays at the minimum ofthem. Thus, for a large answer set (e.g., |a| ≃ |t|n ), SRED works as a concise representation of the set, and even fora small (|a| ≪ |t|) answer set that could not benefit from the compression, it works no worse than non-compressed
representations. Furthermore, SRED allow several kinds of direct manipulations on the represented sets, without
decompression:
P ROJECTION
O(min(m, 3n h|δA ||p|))(|p| is the size of the projected set)

S ELECTION
O(min(m, 3n h|δA |))

S IZE
O(m)

In the paper, we have used the total deterministic tree automaton as a representative of regular queries. One
possible direction for future work is to extend the SRED representation to support other query formalisms directly,
rather than through a conversion to a deterministic automaton. In fact, the algorithms given in this paper works without
any change for partial deterministic automata, and, as long as it is unambiguous, for non-deterministic ones. It seems
an interesting question whether there is a possibility to support arbitrary non-deterministic tree automata.
13

Acknowledgments
We would like to thank the anonymous reviewers for their helpful comments. This work was partly supported by
the Japan Society for the Promotion of Science.
References[1] H. Hosoya, B. C. Pierce, Regular expression pattern matching for XML, Journal of Functional Programming 13 (2003) 961–1004. doi:
10.1017/S0956796802004410.
[2] J. W. Thatcher, J. B. Wright, Generalized finite automata theory with an application to a decision problem of second-order logic, Mathematical
Systems Theory 2 (1968) 57–811. doi:10.1007/BF01691346.
[3] D. Niwinski, Fixed points vs. infinite generation, in: Logic in Computer Science (LICS), 1988, pp. 402–409. doi:10.1109/LICS.
1988.5137.
[4] G. Gottlob, C. Koch, R. Pichler, Efficient algorithms for processing XPath queries, ACM Transactions on Database Systems 30 (2005)
444–491. doi:10.1145/1071610.1071614.
[5] G. Gottlob, C. Koch, Monadic datalog and the expressive power of languages for Web information extraction, Journal of the ACM 51 (2004)
74–113. doi:10.1145/962446.962450.
[6] F. Neven, J. V. D. Bussche, Expressiveness of structured document query languages based on attribute grammars, Journal of the ACM 49(2002) 56–100. doi:10.1145/505241.505245.
[7] H. Meuss, K. U. Schulz, F. Bry, Towards aggregated answers for semistructured data, in: International Conference on Database Theory(ICDT), 2001, pp. 346–360. doi:10.1007/3-540-44503-X 22.
[8] E. Filiot, S. Tison, Regular n-ary queries in trees and variable independence, in: International Conference on Theoretical Computer Science(IFIP TCS), 2008, pp. 429–443. doi:10.1007/978-0-387-09680-3 29.
[9] J. Flum, M. Frick, M. Grohe, Query evaluation via tree-decompositions, Journal of the ACM 49 (2002) 716–752. doi:10.1145/602220.
602222.
[10] G. Bagan, MSO queries on tree decomposable structures are computable with linear delay, in: Computer Science Logic (CSL), 2006, pp.
167–181. doi:10.1007/11874683 11.
[11] B. Courcelle, Linear delay enumeration and monadic second-order logic, Discrete Applied Mathematics 157 (2009) 2675–2700. doi:
10.1016/j.dam.2008.08.021.
[12] P. F. Dietz, Maintaining order in a linked list, in: ACM Symposium on Theory of Computing (STOC), 1982, pp. 122–127. doi:10.1145/
800070.802184.
[13] C. Okasaki, Amortization, lazy evaluation, and persistence: Lists with catenation via lazy linking, in: Foundations of Computer Science(FOCS), 1995, pp. 646–654. doi:10.1109/SFCS.1995.492666.
[14] T. Bray, J. Paoli, C. M. Sperberg-McQueen, E. Maler, Extensible markup language (XMLTM ), http://www.w3.org/XML/ (2000).
[15] K. Inaba, H. Hosoya, XML transformation language based on monadic second order logic, in: Programming Language Technologies for
XML (PLAN-X), 2007, pp. 49–60.
[16] A. Berlea, H. Seidl, Binary queries for document trees, Nordic Journal of Computing 11 (2004) 41–71.

14