Compact Representation for Answer Sets of n-ary
Regular Queries
Kazuhiro Inaba1 and Haruo Hosoya1
The University of Tokyo, {kinaba,hahosoya}@is.s.u-tokyo.ac.jp

Abstract. An n-ary query over trees takes an input tree t and returns a set of ntuples 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. Despitethat the number of the elements of the answer set can be as large as |t|n , ourrepresentation allows to store the set using only O(3n |t|) space. Several basic
operations on the sets are shown to be efficiently executable on the representation.

1 Introduction
Finite state automaton is a well-known model for representing properties for trees andstrings. The class of queries definable by finite state automata is called regular and is
widely used both in theory and in practice. A number of 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 definedby tree automata. An n-ary query over trees takes an input tree t and returns a set ofn-tuples of the nodes of t. The number of elements in the answer set of an n-ary query
may be as large as |t|n where |t| is the number of the nodes of t. And, usually, storing a 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 random manner; it
is a well-known consequence from the information theory. Note, however, we are interested in more practical, less random queries. Queries defined by tree automata havemuch more structure than random ones. By exploiting the structural characteristics ofregular queries, we can represent the answer sets in some compressed form.
Let us explain the idea by an example. Consider the regularquery “select all pair of nodes (x, y) such that x is in the left
t = v0subtree of the root node and y is in the right subtree of the rootv1
v4node” with the input tree t as in the figure. Then the answer set
consists of nine elements: {(v1 , v4 ), (v2 , v4 ), (v3 , v4 ), (v1 , v5 ),v2 v3 v5 v6(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, insteadof computing the concrete list of elements. For this example, we 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, for the general case with n nodes in both the left and theright subtrees, the answer set can be represented by the expression of 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 ∗ (aslight variant of product)–are necessary for achieving the linear-size representation of
the answer sets of regular queries. We show that for any fixed n-ary regular query andan input tree t, the answer set can always be represented by an expression on ∪· and ∗with every leaf expression being a singleton set of an input node. By sharing common
sub-expressions, the expression can be represented by a dag of size O(3n |t|). 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! The factor 3n is sufficiently low for queries with small nsuch as binary or ternary queries, which are the most cases occur in practice (after all,it is quite rare to run, say, a 100-ary query).
Furthermore, the dag representation is extended to a data structure named SRED
(Set Representation by Expression Dags), which enjoys good time complexity as wellas the size-efficiency. The SRED representation of the answer set can always be computed from the input tree t in time O(3n |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(3n a), where a is the number of theanswers. 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 thefollowing two important operations without decompressing it: (1) S ELECTION: for ananswer 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) where h is theheight of the input tree for binary trees and is the height times log |t| for unranked trees,and (2) P ROJECTION: the set s@i = {vi | (v1 , . . . , vn ) ∈ s} can be computed in timeO(6n h|s@i |). The key idea of SRED is to remember for every sub-expression the least
common ancestor of the nodes contained in the set represented by the sub-expression.
The information allows to locate 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 setsof queries. The size of a CAA is O(nh|t|) which is competitive to our O(3n |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 used in [7]. Though an attempt to represent
the answer sets of regular queries with CAA is given by Filiot and Tison [8] througha decomposition of queries, the space complexity is O(n|t|dϕ ) for some constant dϕdepending on the query, which grows to n in the worst case. Besides, precise complexityof operations like 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
2

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 ofqueries that the FFG algorithm can be applied is more general than our algorithm. The
FFG algorithm can also be used for querying n-tuples of sets of nodes of graphs thathave a tree decomposition, while our algorithm only supports queries for n-tuples ofnodes of trees. It is future work whether our compact representation of the answer sets
can be extended to more general class of queries.

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 endof 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)
where Vt is the disjoint union Vt ∪· Vt of finite sets of nodes, label t : Vt →(2)(2)
Σ (0) ∪· Vt → Σ (2) is the label function, lt t , rt t : Vt → Vt is the left- and rightchild function respectively, and root t ∈ Vt is the root node. 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 no node 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 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 orderrelation v1 ≤t v2 is defined to hold if and only if v2 is reachable from v1 by zero or
finitely many applications of lt t and rt t . We usually omit the subscript t if clear fromthe context. By |t| we denote the number |Vt | of the nodes. We use the notation a⟨v1 , v2 ⟩to denote 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 constantspace independent from |t|. In practice, this implies the assumption that the tree t fits inthe 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 constant time.
In particular, we can test the relation ≤ in constant time by, e.g., the preorder/postordernumbering [10]. Again by the assumption that |t| fits in the address space, preorder andpostorder numbers can be stored in constant space.
A tree language over Σ is a set of trees over Σ. By TΣ , we denote the set of alltrees over Σ. An important class of tree languages are those defined in terms of tree
automata. A bottom-up deterministic tree automaton over Σ is a tuple A = (QA , δA ,FA ) where QA is the set of states, δA : (Σ (0) ∪ Σ (2) × QA × QA ) → QA is thetransition function, and FA ⊆ QA is the set of accepting states. The subscript A isomitted if clear from the context. A run of a tree automaton A on the input tree t is theunique function
ρ : Vt → QA such that ρ(v)if label t (v) ∈ Σ (0) and() = δA (label t (v))(2)
ρ(v) = δA label t (v), ρ(lt t (v)), ρ(rt t (v)) if label t (v) ∈ Σ . The automaton accepts
t if and only 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

3

N -ary Regular Tree Queries

As a basis of our algorithm for computing the compact representation of answer sets, wefirst 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 obtainedby 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(0)(2)
n-tuples of its nodes. Let B = {0, 1}, Σn = Σ (0) × Bn , Σn = Σ (2) × Bn , and Σn =(0)(2)
Σ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 a treem = (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 by marking each selected node vi
with 1. A query defined by a regular language L is called a regular query. In the restof the paper, we assume the regular language L to be given as a tree automaton A suchthat 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 naive 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 is accepted 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 tablecontaining the result of the parallel marking run.
QUERY-RUNA (v)r ← new 2-dimensional array of size |QA | × 2n with each element initialized to ∅if label(v) ∈ Σ (0) thenfor each ((label(v), b0 ) 7→ q0 ) ∈ δA do
r[q0 , b0 ] ← singleton(v, b0 )else if label(v) ∈ Σ (2) thenr1 ← QUERY-RUNA (lt(v)); r2 ← QUERY-RUNA (rt(v))
for each ((label(v), b0 ), q1 , q2 7→ q0 ) ∈ δA do
for each disjoint b0 , b1 , b2 in 00 . . . 00 to 11 . . . 11 do· singleton(v, b0 ) ∗ r1 [q1 , b1 ] ∗ r2 [q2 , b2 ]r[q0 , b0 |b1 |b2 ] ← r[q0 , b0 |b1 |b2 ] ∪return r

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

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
7, for each disjoint iterates over pairs of form (b1 = β11 · · · β1n , b2 = β21 · · · β2n ) ∈(B n )2 such that for all 1 ≤ i ≤ n, at most one of {β0i , β1i , β2i } is 1, with β01 · · · β0n =b0 . The operator | is for bitwise-or and ∪· is disjoint union of sets (the operands areindeed disjoint, as explained later). The operator ∗ is a kind of “product” operation thatcombines 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 havetuples with non-⊥ nodes on the same position, as will be shown in Lemma 1.
4

Let us explain how the algorithm works. Let r = QUERY-RUNA (v) for a nodev ∈ Vt . For each q ∈ QA and b = β1 · · · βn ∈ Bn , r[q, b] is a set of n-tuples overthe 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 andleaves the second 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 “ifthe node v1 is marked as the first component of the answer and no node in the subtree
under v is marked 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[q1 , 10] = {(v, ⊥)} r[q1 , 11] = ∅r[q2 , 00] = ∅r[q2 , 01] = {(⊥, v)} r[q2 , 10] = ∅r[q2 , 11] = {(v, v)}.
The set r[q1 , 00] contains (⊥, ⊥) because if we do not select any node below v, theautomaton 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 theanswer. On the other hand, we have r[q2 , 01] = {(⊥, v)}, because if we choose v as thesecond coordinate, the automaton reaches the state q2 .
The index b of r called flag denotes the already selected coordinates. Formally, thefollowing lemma can be shown by induction on the structure of the tree rooted at v.
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.
The lemma ensures the two disjointness 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 ⊥. For such a case, we have |S ∗ T | =|S| · |T |. Second, ∪· is always taken between disjoint sets, because the operands of ∪· areconstructed by ∗-product over different flags.
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 (sketch; for more detail, consult Claim 1 of [9]). Let v1 , . . . , vn ∈ Vt to be fixedand ρ be the unique run on the tree mark(t, v1 , . . . , vn ) by A. Let v ∈ Vt . For eachi, if v ≤t vi then let ui = vi and βi = 1. Otherwise let ui = ⊥ and βi = 0. We
can prove by induction on the structure of v the following claim: if ρ(v) ̸= q the set
QUERY-RUNA (v)[q, b] is empty for any b ∈ Bn , and if ρ(v) = q then (u1 , . . . , un ) ∈QUERY-RUNA (v)[q, b] if and only if b = β1 · · · βn . By applying the claim to the root
node v = root t , we have (v1 , . . . , vn ) ∈ QUERY-RUNA(root t )[q,11 · · · 11] if and only if
q = ρ(root t ), which, together with the definition of ψL(A) , proves the desired result. ⊓⊔5

What is the 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; theouter loop requires |δA | iterations, the inner loop for b0 , b1 , b2 requires 3n iterations,and inside the loop, one ∪· operation and two ∗ operations are required. Note that theresult of those set operations can be as large as O(|t|n ) in the worst case. As long as we
represent such sets as a concrete collection of tuples, the operation ∗ need to enumerate
all its output elements. Hence it takes at least O(|t|n ) time. Altogether, the total timecomplexity is still high: O(3n |δA ||t|n+1 ). In fact, the complexity can be reduced by a 2pass preprocessing proposed in [9]. Their preprocessing detects, for each node, whether
or not each entry r[q, b] really needs to be computed. By omitting the computations thatturned out not to be need, the complexity is reduced to O(3n |δA |(|t| + a)) where a isthe size of the answer set.
In the next section, we take a completely different approach for reducing the complexity. Rather than changing the structure of the algorithm (like adding preprocessing
passes), we introduce a novel data structure for representing sets of tuples. Just by using
the data structure to represent 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.

4

SRED: Set Representation by Expression Dags

The idea of our compact representation is quite simple. To represent a set s, we use asyntax tree r of an expression that 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). Then wedenote 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 constant time, 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|),and so 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 :ST β1 ···βn ::= emp⟨⟩ | unit⟨⟩ | ne⟨NST β1 ···βn ⟩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
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 the efficiency, we specially treat the empty set (represented by emp⟨⟩) andthe 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
6

EVAL-NE (r)if r ≡ cup⟨v, r1 , r2 ⟩ then
· EVAL-NE(r2 )return EVAL-NE(r1 ) ∪else if r ≡ star⟨v, r1 , r2 ⟩ thenreturn EVAL-NE(r1 ) ∗ EVAL-NE(r2 )else if r ≡ sing⟨v, b⟩ thenreturn singleton(v, b)

EVAL (r)if r ≡ emp⟨⟩ then return ∅else if r ≡ unit⟨⟩ then return {(⊥, · · · , ⊥)}else if r ≡ ne⟨r ′ ⟩ then return EVAL-NE(r ′ )

1:
2:
3:
4:
5:
6:

1:
2:
3:

UNION-AT (v, r1 , r2 )if r1 ≡ emp⟨⟩ thenreturn r2
else if r2 ≡ emp⟨⟩ thenreturn r1
else if r1 ≡ ne⟨r1′ ⟩ and r2 ≡ ne⟨r2′ ⟩ thenreturn ne⟨cup⟨v, r1′ , r2′ ⟩⟩

1:
2:
3:
4:
5:
6:

PRODUCT-AT (v, r1 , r2 )if r1 ≡ emp⟨⟩ or r2 ≡ emp⟨⟩ thenreturn emp⟨⟩
else if r1 ≡ unit⟨⟩ thenreturn r2
else if r2 ≡ unit⟨⟩ thenreturn r1
else if r1 ≡ ne⟨r1′ ⟩ and r2 ≡ ne⟨r2′ ⟩ thenreturn ne⟨star⟨v, r1′ , r2′ ⟩⟩

1:
2:
3:
4:
5:
6:
7:
8:

SINGLETON-AT (v, β1 · · · βn )if β1 · · · βn = 0 · · · 0 thenreturn unit⟨⟩
else return ne⟨sing⟨v, β1 · · · βn ⟩⟩

1:
2:
3:

Fig. 1. Basic Operations on SRED

operands of cup. By avoiding emp⟨⟩ and unit⟨⟩ to occur at non-root position, we canevaluate the syntax-dag by a simple recursion shown in Fig. 1, in the data complexity
proportional to the size of the answer set.
Lemma 3 (E VALUATION ). Assume the disjoint union s1 ∪· s2 can be computed in constant time and the product s1 ∗ s2 can be computed in time O(n|s( 1 ∗ s2 |) for s)1 , s2 (̸= ∅.
Then EVAL(r))(EVAL-NE(r), respectively) runs in time O 3k n|EVAL(r)| (O 3k n
|EVAL-NE(r)| ) where k is the maximum number of star nodes in every path from r to
any leaf.
Proof. The proof is by induction on the structure of r. For the case of emp, unit, sing,and cup nodes, it is trivial and hence omitted here. For the case r ≡ star⟨v, r1 , r2 ⟩, byinduction hypothesis, s1 = EVAL-NE(r1 ) and s2 = EVAL-NE(r1 ) can be computedin 3k−1 n(|s1 | + |s2 |) steps. Since neither s1 nor s2 is empty, their sizes are less than orequal to |s1 ∗ s2 |. Thus, 3k−1 n(|s1 | + |s2 |) is no more than 2 · 3k−1 n|s1 ∗ s2 |. By theassumption, their *-product can be computed in time n|s1 ∗ s2 |. Altogether, the total
time consumption for EVAL(r) in this case is 3k n|s1 ∗ s2 | = 3k n|EVAL-NE(r)| as
desired.
⊓⊔The complexity assumption is satisfied by, for instance, representing the sets by adoubly-linked list of elements. Disjoint union can be implemented by the list concatenation, and the ∗-product is implemented by a double-loop over two operand sets. Note
that, the number k of star node in a path is at most n, because the star operation strictlyincreases the number of non-⊥ coordinates in the element tuples.
The basic three operations used in the algorithm QUERY-RUNA are defined on
SRED as in Figure 1. Note that, to avoid emp⟨⟩ and unit⟨⟩ to occur 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 otheroperand rather than constructing a new cup node. The correctness is easily verified byinduction on the structure of SRED, and we have the following results:
Lemma 4 (Correctness). EVAL(UNION-AT(v, r1 , r2 )) = EVAL(r1 ) ∪· EVAL(r2 ),EVAL(PRODUCT-AT(v, r1 , r2 )) = EVAL(r1 )∗EVAL(r2 ), and EVAL(SINGLETONAT(v, b)) = singleton(v, b).
7

PROJ (i, r)
if r ≡ emp⟨⟩ thenreturn ∅else if r ≡ ne⟨r ′ ⟩ thenreturn PROJ-NE(i, r ′ )

1:
2:
3:
4:

PROJ-NE (i, r)
if r ≡ cup⟨v, r1 , r2 ⟩ thenreturn PROJ-NE(i, r1 ) ∪ PROJ-NE(i, r2 )else if r ≡ star⟨v, r1 , r2 ⟩ (with r1 ∈ NSTβ1 ···βn ) thenif βi = 1 then return PROJ-NE(i, r1 ) else return PROJ-NE(i, r2 )else if r ≡ sing⟨v, β1 · · · βn ⟩ thenreturn {v}

1:
2:
3:
4:
5:
6:

SEL-NE (i, u, r)
SELECT (i, u, r)
1: if r ≡ cup⟨v, r1 , r2 ⟩ and v ≤ u then
if r ≡ emp⟨⟩ then2:
return UNION-AT(v, SEL-NE(i, u, r1 ), SEL-NE(i, u, r2 ))return emp⟨⟩
3: else if r ≡ star⟨v, r1 , r2 ⟩ (with r1 ∈ NSTβ1 ···βn ) and v ≤ u thenelse if r ≡ ne⟨r ′ ⟩ then′if βi = 1 then return PRODUCT-AT(v, SEL-NE(i, u, r1 ), r2 )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 0βi+1 · · · βn )8: else return emp⟨⟩

1:
2:
3:
4:

Fig. 2. Projection and Selection on SRED

Theorem 5. Let S-QUERY-RUNA be a procedure obtained by replacing ∅ in the pro· with UNION-AT(v, x, y), x∗y with PRODUCTcedure QUERY-RUNA with emp⟨⟩, x∪yAT(v, x, y), and singleton(v, b) with SINGLETON-AT(v, b). Then, S-QUERY-RUNA (t)runs in time O(3n |δA ||t|) and outputs a SRED r with at most 3n |δA ||t| nodes, such that
EVAL(r) = QUERY-RUNA (t).
Rather than enumerating the all elements of the answer set, we sometimes want to
extract a sub-part of the answer set. Here, we give an implementation of two important
operations on SRED, namely, PROJECTION and SELECTION. For a set s of n-tuples
and 1 ≤ 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 that the i-th coordinate isu. 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 of queries in a user-specified
order, rather than in the default order of EVALUATION procedure.
On SRED representation of the answer sets, those two operations can be carriedout in time proportional to the height of the input tree. That is, we do not need totraverse the whole structure of SRED, nor to re-traverse the original input tree. Fig. 2
is the implementation, which is straightforwardly obtained from the distributivity of
projection and selection over disjoint union, etc.
Theorem 6 (P ROJECTION ). By using memoization, the procedure PROJ(i, r) computes the set EVAL(r)@i in time O(6n h|δA ||EVAL(r)@i |) where h is the height ofthe original input tree t.
Proof. Correctness is proved by induction on the structure of r, which is omitted here
due to the lack of the space. 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 hash table. Then the body of the procedure PROJ-NE is executed at most once
per each node of r. In fact, it can be shown that PROJ-NE is applied only to the nodes
8

that are an ancestor of a sing⟨v, · · ·⟩ node with v ∈ EVAL(r)@i . By the definition of the
QUERY-RUNA procedure, the number of such sing nodes is at most 2n |EVAL(r)@i |,and for each of them, the number of the ancestors is at most 3n h|δA |. By using listconcatenation for representing set-union1 , the body of PROJ-NE can be executed inconstant time. Hence, we obtain the desired complexity.
⊓⊔
Theorem 7 (S ELECTION ). By using memoization, the procedure SEL(i, u, r) computes the set EVAL(r)[i:u] in time O(3n h|δA |).
Proof. Correctness is proved by induction on the structure of r. For the complexity,
memoization ensures that the procedure SEL-NE is called at most once per each nodeof r. By Lemma 1, the test v ≤ u succeeds only at the node constructed at an ancestor(in the tree t) of u. Hence, SEL-NE is executed only on the nodes constructed at anancestor of u, or their direct child. Since the number of the ancestor nodes is at most hand on each of such nodes at most 3n |δA | SRED-node is created, SEL-NE is executed
only O(3n h|δA |) times, which proves the desired complexity.
⊓⊔
As a corollary, given a tuple (u1 , . . . , un ), we can test whether a SRED contains thetuple in time O(3n nh|δA |) by applying SELECTION n times.
Generalizations to Unranked Trees So far, we have considered only binary trees. In
many applications, however, we are interested in unranked trees with varying numberof 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 encodingof an unranked tree, the first child of each node is mapped to the first child of thecorresponding node in the original unranked tree, and the second child of each node ismapped to the next 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 beconverted to a regular query on the encoded trees. Hence, by first encoding the unranked
input trees and the queries to the binary-tree form and then running S-QUERY-RUNA ,we can compute the linear-size representation of the answer sets of regular queries. One
problem of fc-ns encoding is the time complexity of 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 casefor most XML documents). The problem is that the height of the fc-ns encoded treeis O(h0 w0 ). To deal with such trees, we recommend to use 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 sequenceof leaf nodes corresponds to the 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|).
Application SRED is developed for the XML transformation language MTran [11]. Let
us illustrate the benefits of SRED by the following pseudo code for XML translation:
1

Precisely speaking, since it is not a disjoint union this time, list-concatenation based implementation may cause duplication. It, however, can be remove by a linear time ‘uniq’ algorithm.

9{gather x | x:<person> do<row><col>{gather y | (x//<name>/y) do y}</col>{gather z | 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 thesize of the tree, total running time of the query becomes quadratic, because there may
be linearly many <person> nodes. Rather, as pointed out in [12], it is better to regard thesecond 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 SELEC TION operation followed by the EVALUATION operation, for each x we can obtain thecorresponding 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 (or equivalently, query with SRED directly
followed by EVALUATION) for the same purpose, because its running time is linear under the assumption 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 sizeof the answer set is quadratic. If we use the FFG algorithm, we need O(|t|2 ) working
space for 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.
Thanks This work was supported by the Japan Society for the Promotion of Science.

References
1. Hosoya, H., Pierce, B.C.: Regular expression pattern matching for XML. Journal of Functional Programming 13 (2003) 961–1004
2. Thatcher, J.W., Wright, J.B.: Generalized finite automata theory with an application to adecision problem of second-order logic. Mathematical Systems Theory 2 (1968) 57–811
3. Niwinski, D.: Fixed points vs. infinite generation. In: LICS. (1988) 402–409
4. Gottlob, G., Koch, C., Pichler, R.: Efficient algorithms for processing XPath queries. ACM
Transactions on Database Systems 30 (2005) 444–491
5. Gottlob, G., Koch, C.: Monadic datalog and the expressive power of languages for Web
information extraction. Journal of the ACM 51 (2004) 74–113
6. Neven, F., Bussche, J.V.D.: Expressiveness of structured document query languages basedon attribute grammars. Journal of the ACM 49 (2002) 56–100
7. Meuss, H., Schulz, K.U., Bry, F.: Towards aggregated answers for semistructured data. In:
International Conference on Database Theory (ICDT). (2001) 346–360
8. Filiot, E., Tison, S.: Regular n-ary queries in trees and variable independence. In: International Conference on Theoretical Computer Science (TCS). (2008) 429–443
9. Flum, J., Frick, M., Grohe, M.: Query evaluation via tree-decompositions. Journal of the
ACM 49 (2002) 716–752
10. Dietz, P.F.: Maintaining order in a linked list. In: STOC. (1982) 122–127
11. Inaba, K., Hosoya, H.: XML transformation language based on monadic second order logic.
In: Programming Language Technologies for XML (PLAN-X). (2007) 49–60
12. Berlea, A., Seidl, H.: Binary queries for document trees. Nordic Journal of Computing 11(2004) 41–71

10