XML TRANSFORMATION LANGUAGE BASED ON
MONADIC SECOND ORDER LOGIC
by
Kazuhiro Inaba

A Master Thesis

Submitted to
the Graduate School of the University of Tokyo
on February 28, 2006
in Partial Fulfillment of the Requirements
for the Degree of Master of Sciencein Information Science
Thesis Supervisor: Haruo Hosoya
Assistant Professor of Information ScienceABSTRACT
Although monadic second-order logic (MSO) has been a foundation of XML queries, little
work has attempted to take MSO formulae themselves as a programming construct. Indeed,
MSO formulae are capable of expressing (1) all regular queries, (2) deep matching without
explicit recursion, (3) queries in a “don’t-care semantics” for unmentioned nodes and (4) nary queries for locating n-tuples of nodes. While previous frameworks for subtree extraction(path expressions, pattern matches, etc.) each had some of these properties, none has satisfied
all of them.
In this thesis, we have designed and implemented a practical XML transformation language called MTran that fully exploits the expressiveness of MSO. MTran is a language
based on “select-and-transform” templates similar in spirit to XSLT. However, we specialize
our templates for expressing structure-preserving transformation so as to avoid any recursive
calls to explicitly be written. Moreover, we allow templates to be nested so as to make useof an n-ary query that depends on the n − 1 nodes selected by the preceding templates.
For the implementation of the MTran language, we have developed, as the core part, an
efficient evaluation strategy for n-ary MSO queries. This consists of (a) an exploitation of
the existing MONA system for the translation from MSO formulae to tree automata and (b)our novel query evaluation algorithm for tree automata. Although a linear time algorithm
has been known for nullary and unary queries, the best known algorithm for n-ary queries
takes O(rt + s) time in the worst case where t is the size of the input document, s is thatof the output, and r is the size of potential matches during the query calculation, which cangrow up to tn−1 in the worst case. We have developed a more efficient O(t + s) algorithm forn-ary queries by using partially lazy evaluation of set operations.

Acknowledgements

We would like to thank Professor Haruo Hosoya for his invaluable comments andsuggestions. We gratefully acknowledge Professor Mizuhito Ogawa for the discussionof our ideas. We have also learned a great deal from discussions with the members of
the Principle of Programming Languages seminar in the University of Tokyo.

Contents

1 Introduction1

1.1

XML Transformation Language . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Our Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2.1

Monadic Second Order Logic . . . . . . . . . . . . . . . . . . .

2

1.2.2

XML Transformation with MSO . . . . . . . . . . . . . . . . .

4

1.2.3

Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.3.1

Query Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.3.2

Language Design . . . . . . . . . . . . . . . . . . . . . . . . . .

9Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

1.3

1.4

2 Language

11

2.1

Binary Trees and XML representation . . . . . . . . . . . . . . . . . .

11

2.2

Query Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

2.2.1

Core Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

2.2.2

Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.2.3

Auxiliary Syntax . . . . . . . . . . . . . . . . . . . . . . . . . .

15Transformation Templates . . . . . . . . . . . . . . . . . . . . . . . . .

18

2.3.1

Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

2.3.2

Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.3.3

Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.3

3 Evaluation Algorithm
3.1

26

Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.1.1

Queries over trees . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.1.2

Tree Automata . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.2

From MSO to Tree Automata . . . . . . . . . . . . . . . . . . . . . . .

28

3.3

N -ary Query Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . .

28

i

3.4

3.3.1

Basic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . .

28

3.3.2

Our Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

Transformation Template Evaluation . . . . . . . . . . . . . . . . . . .

38

3.4.1

39

Efficient N-ary Queries Using Context Information . . . . . . .

4 Experiments
4.1

4.2

41

Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

4.1.1

XHTML Table of Contents . . . . . . . . . . . . . . . . . . . .

41

4.1.2

Linguistic Queries . . . . . . . . . . . . . . . . . . . . . . . . .

44

4.1.3

Relax NG Simplification . . . . . . . . . . . . . . . . . . . . . .

45

Preliminary Performance Evaluation . . . . . . . . . . . . . . . . . . .

48

4.2.1

49

N -ary query performance . . . . . . . . . . . . . . . . . . . . .

5 Conclusion and Future Work

52

5.1

Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

5.2

Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

References

54iiChapter 1
Introduction

1.1

XML Transformation Language

Extensible Markup Language (XML [1]) is a language to represent tree-like data,
standardized by World Wide Web Consortium (W3C). XML is becoming more andmore commonly adopted in many areas as standard data formats such as XHTML,RDF, SVG, MathML, etc. To cover these increasing demands, flexible and expressiveframework for XML processing is desired.
XML processing is essentially a process of XML transformation. We query datafrom input XML documents, convert them into another desired XML format, andoutput them. For XML queries, as an analogy to first-order logic being a basis for
relational queries, monadic second-order logic (MSO) has gradually stabilizing its position as a foundation. For example, there have been proposals for XML query languages
whose expressivenesses are provably MSO-equivalent [2, 3] and for theoretical models
for XML transformation with MSO as a sublanguage for node selection [4, 5]. However, little attempt has been made for bringing MSO logic formulae themselves into
an actual language system for XML processing.
The goal of our work is to design and implement a practical XML transformation
language based on MSO queries. We implement a language MTran, and in particular,
address the following two challenges:• a surface language design for XML transformation that leverages the strength of
MSO queries, and• an efficient algorithm to process MSO queries.

1Regularity
Pattern

No Recursion

Don’t care

N-ary

»

»
»

Path
Datalog

»

MSO

»

»
»

»

»

»

Table 1.1: Comparisons between query languages

1.2

Our Approach

1.2.1

Monadic Second Order Logic

MSO is first-order logic extended with second-order variables ranging over sets ofdomain elements—i.e., tree nodes, in the setting of XML queries—in addition to firstorder variables ranging over domain elements themselves. Why do we think that suchlogic is suitable for writing queries on XML documents? The reasons are fourfold.
• The class of all regular queries can be captured.
• No explicit recursions are required to locate nodes distant from context nodes.
• There is no need to mention the nodes that are irrelevant to the query (“don’tcare semantics”).
• N -ary queries are naturally expressible.
While existing languages such as path expressions [6, 7, 8, 9, 10, 11], pattern matches[12, 13], and monadic datalog queries [3] have some of these properties, MSO is the
only language that has all of them, as we argue below.
Regularity
A query over trees is called regular when there is an equivalent tree automaton with
an appropriate alphabet (Section 3.1.2). MSO is known to be able to express all regularqueries [14], while most of existing path-based node selection languages (including
XPath [6], currently the most popular path language) do not have this property. This
lack of regularity does not only indicate theoretical weakness in expressive power,
but also has a practical impact since it fails to be able to represent even slightly
complicated conditions for node selection. An obvious example is that one cannot
write “select every node that conforms to a specified schema for XML” since schemas
written in usual schema languages like DTD [1], XML Schema [15], and RELAX NG
2

[16] heavily rely on regular expressions for trees (in particular, RELAX NG schemas
can represent any regular tree languages) and thus exceed the expressiveness of thosepath-based selection languages. As a more realistic example, the following query“select, from an XHTML document, every <h2> node that appears between
the current node and the next <h1> node from the current node in the
document order”
is naturally expressible in MSO as we will see in Section 4.1.1, whereas it is not inmost path languages.
No recursion
The way that MSO formulae express retrieval conditions is in a sense logically direct and, in particular, it does not require recursively defined constraints for reachingnodes that are located in arbitrarily deep positions. Several query languages such regular expression patterns and monadic datalog, while being able to capture all regularqueries, incur recursive definitions for deep matching. As a result, even an extremely
simple query like “select all <a> elements in the input document” needs an explicit
recursion. Writing down recursion is often tedious work and in particular unfriendly
to naive programmers; it is much more helpful to be able to express such a simple
query like
x in <a>as in MSO.
Don’t-care semantics
The directness of MSO’s way of expression also allows us to completely avoid
mentioning nodes that are irrelevant to the query. It is in contrast to some languages
such as regular expression patterns, where we need to specify conditions that the whole
tree structure should satisfy. For example, suppose that we want to write a query that
retrieves the set of nodes x whose at least one child node labeled <b>. In regularexpression patterns, we would write as follows
x as ~[Any, b[Any], Any]where we have to “mention” the siblings and the content of the <b> node by the wildcard Any to complete the pattern. In MSO, on the other hand, we can write in thefollowing way
3

ex1 y: x/y & y in <b>where we only refer to the nodes of our interest: the node x itself and the child <b>node y. No condition is ever explicitly specified for other irrelevant nodes, even by
wildcards. This “don’t-care semantics” might not be advantageous for specifying avery complicated constraint such as conformance to a schema, while it makes most ofusual queries extremely concise.
N -ary queries
An n-ary query locates n-tuples of nodes of the input XML tree that simultaneously
satisfy a specified condition. MSO, as it is a formal logic, can naturally express n-ary
queries by formulae with distinct n free variables. For example, the following ternaryquery
ex1 p: p/x & p/y & p/z &x in <a> & y in <b> & z in <c>expresses the condition that given three nodes x, y, and z share a common parent nodep and are tagged with <a>, <b>, and <c>, respectively. Although path-based querylanguages like XPath suit to express binary queries that express relations between apreviously selected node and another, they cannot represent general n-ary queries.
Similarly, monadic datalog can express arbitrary unary MSO formulae but not any
higher-arity queries.
1.2.2

XML Transformation with MSO

MSO by itself is thus a powerful specification language for node selection. However,
our aim is to further make use of MSO formulae for the transformation of XML
documents. Then, the question is: what is a language design principle that fully
exploits the high expressive power of MSO?
Structure-preserving transformation
Since it is one of MSO’s advantages that we can select nodes in any depth withno explicit recursions, it would paradigmatically be smooth if we can also express atransformation of trees of any depth without any recursions. For example, given an
input document where <A> elements may be nested one inside another, consider thetransformation that encloses every <A> element in the input document by a new <B>element. In our language, this transformation can be written by the following one line:4{visit x :: x in <A> :: B[x]}Here, we first select all the <A> elements by the MSO formula ”x in <A>” andthen transform each of these elements accordingly to the rule “B[x],” i.e., enclose theelement by the <B> tag. The whole output is the reconstruction of the input tree where
each select element is replaced by the result of its local transformation.
Compare the above program in our language with the same transformation written
in XSLT:<xsl:stylesheet version="1.0" ...>
<xsl:template match="A"><B><A><xsl:apply-templates/></A></B></xsl:template><xsl:template match="@*|node()"><xsl:copy><xsl:apply-templates/></xsl:copy></xsl:template></xsl:stylesheet>
In this, we similarly select all the <A> elements (by an XPath expression) and then,for each selected element, we create a <B> element containing an <A> element. The
most important difference, however, is that XSLT requires us to explicitly write arecursive application of the template to the child nodes (<xsl:apply-templates/>)
for computing the content of the <A> element. Our design principle is to eliminate such
explicit recursion for avoiding the necessity to follow the data flow for understanding
the program, thus making transformation more intuitively readable and writable fornaive programmers.
Choice of visit and gather
In MSO, we only need to mention the nodes that are relevant to the query and candirectly jump into them without any navigation. We would like to lift this concept to
our transformation language. Above, we have illustrated a transformation that jumps
directly to each matched node and replaces it with an output fragment. In this case,the nodes that are not matched are retained in the result. However, in general, we
provide two choices for the treatment of such unmatched nodes, either to keep themor to drop them. These correspond to the keywords visit and gather, respectively,
5and can be specified by the user for each use of an MSO formula. For example, thefollowing<root>{gather x :: x in <A> :: B[x]}</root>is similar to the previous example except that it uses gather instead of visit. As
a result, the root element of the output XML contains a list of all <A> elements
appearing in the input XML, each wrapped by a <B> element.
Nested templates
XSLT uses XPath binary queries for selecting a node with respect to a single
previously selected node, i.e., the context node. Our language pushes this approach
further for exploiting MSO’s capability to express general n-ary queries. Specifically,
we allow templates to be nested and an inner MSO formula to refer to variables thatare bound in the outer templates. For example, see the following program:
List[{gather p :: p in <map> ::{gather n :: p/<name>/n ::{gather v :: p/<value>/v ::Pair[ n ", " v ]}}}]Figure 1.1: A transformation using binary queriesThis program converts a document representing a one-to-many mapping, e.g.,<mapping><map><name>Hello</name><value>1</value><value>2</value></map><map><name>World</name>6<value>3</value><value>4</value></map></mapping>
to another representing a many-to-many mapping:<List><Pair>Hello, 1</Pair><Pair>Hello, 2</Pair><Pair>World, 3</Pair><Pair>World, 4</Pair></List>Note that the selection conditions for the variables n and v both depend on theouter variable p. Although this example only uses binary queries, it is easy to seethat we can also specify higher-arity queries in the same framework. Another point of
this example is that, inside the scope where we have already selected a node for n, we
can directly refer to the variable p that is bound in the two-block outer scope. Notethat such flexibility, which is not present in XSLT, can naturally be obtained by the
combination of logic formulae with free variables and nested templates with lexicalscoping.
1.2.3

Algorithm

In order to implement a practical system for our transformation language, what
we critically need is an efficient evaluation algorithm for n-ary MSO queries, that is,
one that takes, as inputs, an MSO formula with n free variables and a tree structure
and calculates the set of n-tuples that satisfy the formula. Our language system uses
an n-ary query algorithm for the following two situations.
• selection of tuples of nodes that simultaneously satisfy the condition, and• selection of nodes that satisfy the condition relative to nodes already selected byprevious queries.
The second point has first been pointed out by Berlea et al. [17] in the context of
their language based on binary queries, but can easily be extended to our case withn-ary queries. To illustrate this point, let us see again the example in Figure 1.1. Firstof all, notice that, even if we do not have an n-ary query algorithm, we can process7

the transformation using only a unary query algorithm. That is, we first locate all the<map> elements in the input document. Then, for each <map> element, we execute theinner formula p/<name>/n, interpreting it as a unary query on the variable n under
the fixed the binding of the variable p to the map element. Unfortunately, this strategy
is inefficient since the above formula is evaluated as many times as the number of the<map> elements present in the input document; since a unary query takes a linear
time in the size of the input, the binary query that we wanted would take a quadratic
time. Berlea et al.’s observation was that this could be improved if there is an efficientalgorithm for binary queries that evaluates, in our example, the above formula only
once for locating all pairs of an element and a <name> element that are in the parentchild relation.
We have developed an efficient implementation strategy for n-ary MSO queries.
This consists of usual two steps: (1) compilation of MSO formulae to tree automataand (2) evaluation of n-ary queries represented by tree automata. The first step is wellknown to take a non-elementary time in the worst case. Our approach is to exploit the
MONA system [18], which has an established reputation in its compact and efficient
representation of MSO formulae by tree automata with binary decision diagrams andis experimentally shown to work quickly for large formulae even of dozens of kilobytes[19]. We have also made a preliminary experiment and confirmed that, for many
typical examples of XML queries, MONA yields an enough performance. (Section 4.2)
For the second step, we have developed a novel linear-time algorithm for n-ary
queries. The previously best known result was Berlea and Seidl’s O(rt + s) algorithm
for binary queries where t is the size of the input document, s is the number of output
tuples, and r is the size of potential matches during the query calculation. Since r
may grow up to t, their algorithm takes a quadratic time in the worst case. Whengeneralized to n-ary queries, r may grow up to tn−1 and the total worst case complexity
is O(tn ). We have improved Berlea’s algorithm and obtained an O(t + s) algorithm
for general n-ary queries. We have achieved this by using partially lazy operations on
sets of nodes so as to eliminate unnecessary computation of potential matches.

1.3

Related Work

1.3.1

Query Algorithm

Several algorithms for MSO queries have been proposed. For unary queries, Nevenand den Bussche have given a linear-time, two-pass algorithm based on boolean attribute grammars [20]. Koch [3], in his XML query language Arb based on monadic
8

datalog, has developed a different linear-time, two-pass algorithm using selecting tree
automata, which exactly captures the class of unary MSO queries.
The binary query algorithm proposed by Berlea and Seidl [17], which has beenused for the implementation of the fxt functional XML transformer [21], is the basisof our algorithm presented in this paper. We have shown that their worst case timecomplexity O(t2 + s) can be improved to O(t + s) (where t and s are respectively
the sizes of the input and the output) by using lazy set operations, and furthermore
our strategy can be generalized it to n-ary queries without sacrificing the linear timecomplexity.
Niehren et al.[22] have presented a linear time algorithm for n-ary MSO queries
in the restricted case where the query is essentially a Cartesian product of n unary
queries. They have shown that existential runs of unambiguous tree automata capture
this class of queries and presented an effective algorithm to decide the unambiguity oftree automata. However, as far as we can tell from our experiences using our language,
almost all n-ary queries appearing in practical settings use variables in a dependent
way and thus do not fulfill their restriction. (See, for example, the MSO queries shownin Chapter 4).
1.3.2

Language Design

DTL [4] and its generalization TL [5] are theoretical models for XML transformation that use, like us, MSO formulae for node selection. However, their purpose of
research is to seek for theoretical properties of transformation models whereas ours is
to obtain a concrete design and an efficient implementation technique for a transformation language leveraging the full strength of MSO. Thus, on one hand, they havefound desirable properties such as decidability of precise typechecking, which is notknown for our language. On the other hand, we have incorporated a number of design considerations not present in their languages. Specifically, our language allows
transformation of arbitrarily deep trees without recursion, while theirs incurs explicit
recursion; ours provides the choice of retaining and dropping for nodes not selected byqueries, while theirs allows only the second; ours allows nested templates to make useof n-ary queries, while their is limited to binary queries.
Nakano has proposed an XML transformation language XTiSP [23] that has visit
and invite constructs. Although these look similar to our visit and gather, they
have slightly simpler semantics (e.g., they can go only forward) for their primary
purpose of stream processing. Also, XTiSP uses path expressions for node selection

9and thus is limited to binary queries.

1.4

Structure of the Thesis

The rest of this thesis is organized as follows. In Chapter 2, we introduce theformal syntax and semantics of our MTran language. We first argue about the querypart of MTran, and then explain the whole transformation language. Chapter 3 gives adetailed explanation of our query algorithm of n-ary MSO formulae after a brief review
of some known facts on MSO and tree automata. In Chapter 4, we give slightly bigger
examples in MTran, and show how the expressiveness of MSO is useful in practice.
Chapter 5 concludes this thesis and suggests possible directions for future work.

10Chapter 2
Language

2.1

Binary Trees and XML representation

Definition 1. Let Σ be an alphabet set. A binary tree t over Σ is a mapping froma finite prefix-closed set P os(t) ⊆ {l, r}∗ into Σ. An element p ∈ P os(t) is called aposition or a node of t, and the alphabet t(p) ∈ Σ assigned to p is called the label ofp. The empty sequence node ε is called the root of t.
Our goal is to handle XML documents, which in general are not binary trees but are
unranked trees (trees whose each node has an arbitrary number of child nodes). Since
our algorithm to query XML is designed to use binary trees, we encode an unranked
tree as a binary tree using a widely accepted encoding. The first child of a node in
unranked trees is regarded as the left child of the node in the encoded binary tree,
and the right neighboring sibling in unranked trees is encoded as the right node of thenode. Figure 2.1 shows an example of this encoding.
In MTran, XML documents are modeled as trees containing three types of node:element nodes, attribute nodes, and text nodes. The alphabet Σ for the model tree isFigure 2.1: Encoding an unranked tree(left) to a binary tree(right)

11

msg
item
@lang
"en"

item
@lang

"Hello""fr""Bonjour"

Figure 2.2: The binary tree representation of the example XML
the union of element names, attribute names, and text content appearing in the input
document. For example, the following XML document:<msg><item lang="en">Hello</item><item lang="fr">Bonjour</item></msg>
is modeled as a tree with Σ = {msg, item, @lang, "en", "Hello", "fr", "Bonjour"}.
Here, the symbol @ of @lang represents that this name is for attributes. Attribute nodes
are treated as children of the belonging element node inserted before other ordinary
child nodes. We distinguish attributes nodes from other nodes only by means of thelabels. Thus, the previous example is represented as shown in the binary tree in
Figure 2.2.
Our current implementation does not support comments and processing instructions, and simply ignores them. Also, it does not yet treat XML namespaces. Thoseare left as future work.

2.2

Query Expressions

Query expressions specify conditions of nodes that we want to extract from the
input XML documents, and can be embedded in transformation templates. In thissection, we first describe the core syntax of query expressions. We next define thesemantics of expressions in the core syntax. We then give syntax sugars on top of thecore primitives for the convenient and reusable description of queries.

122.2.1

Core Syntax

As we mentioned in the introduction, we adopt Monadic Second-Order Logic(MSO) formulae as our query language. MSO is a kind of logic that allows the use of
second-order variables ranging over sets of domain elements in addition to first-ordervariables ranging over domain elements themselves. The following BNF defines thecore syntax:
x ∈ First-order variable symbols
X ∈ Second-order variable symbols
e ∈ XML element namesa ∈ XML attribute names

p ::= x | root
S ::= X | <e> | @a | <*> | @* | #ϕ ::= p = p | S = S | p in S
| ~ϕ | ϕ&ϕ | ϕ|ϕ | ϕ=>ϕ
| ex1 x:ϕ | all1 x:ϕ | ex2 X:ϕ | all2 X:ϕ| firstChild(p,p) | nextSibling(p,p)
A first-order term is denoted by p and a second-order term by S. The first-orderconstant symbol root denotes the root node of the input tree. Each constant set
symbol <e> denotes the set of element nodes labeled e in the input XML document,
and each constant set symbol @a denotes the set of attribute nodes labeled @a similarly.
Th other three second-order terms <*>, @*, and # are called wild-card terms denoting
the set of any element nodes, any attribute nodes, and any text nodes, respectively.
The last two constructs of ϕ are the primitives to describe the property of tree
structures. As its name shows, firstChild(p,q) becomes true if and only if the firstchild of node p is q. The relation nextSibling(p,q) is defined similarly. These two
primitives correspond to the edge relations in the binary tree encoding we introducedin Section 2.1.
Example 1. The following query requires that for a node x, this node and all its left
descendants are element nodes labeled as a:ex2 R: (x in R&

all1 y:all1 z:(y in R & firstChild(y,z) => z in R)&

all1 w:(w in R => w in <a>))13

2.2.2

Semantics

Now we give the semantics for MSO formulae. We first define the interpretationof terms.
Definition 2. Let Σ be an alphabet and t be a binary tree over Σ. Under an assignment γ that maps each first-order variable to an element of Pos(t), first-order terms
are interpreted as follows:
γ[x] = γ(x)γ[root] = ε
Also, under an assignment Γ for second-order variables, second-order terms are interpreted as follows:
Γ[X] = Γ(X)
Γ[<e>] = {p | t(p) = e}
Γ[@a] = {p | t(p) = @a}[Γ[<*>] ={p | t(p) = e}e∈Σ

Γ[@*] =[

{p | t(p) = @a}@a∈ΣΓ[#] =[{p | t(p) = "s"}"s"∈ΣDefinition 3. An MSO formula ϕ is interpreted under a binary tree t over Σ, afirst-order assignment γ, and a second-order assignment Γ, as follows:t, γ, Γ ² p1 = p2⇐⇒ γ[p1 ] = γ[p2 ]t, γ, Γ ² S1 = S2⇐⇒ Γ[S1 ] = Γ[S2 ]t, γ, Γ ² p in S⇐⇒ γ[p] ∈ Γ[S]t, γ, Γ ² ~ϕ⇐⇒ t, γ, Γ 6² ϕt, γ, Γ ² ϕ1 &ϕ2⇐⇒ t, γ, Γ ² ϕ1 and t, γ, Γ ² ϕ2t, γ, Γ ² ϕ1 |ϕ2⇐⇒ t, γ, Γ ² ϕ1 or t, γ, Γ ² ϕ2t, γ, Γ ² ex1 x:ϕ⇐⇒ there exists a ∈ Pos(t) s.t. t, γx:=a , Γ ² ϕt, γ, Γ ² all1 x:ϕ⇐⇒ for all a ∈ Pos(t) t, γx:=a , Γ ² ϕt, γ, Γ ² ex2 X:ϕ⇐⇒ there exists A ∈ 2Pos(t) s.t. t, γ, ΓX:=A ² ϕt, γ, Γ ² all2 X:ϕ⇐⇒ for all A ∈ 2Pos(t)14t, γ, ΓX:=A ² ϕ

t, γ, Γ ² firstChild(p1 , p2 )⇐⇒ γ(p1 ).l = γ(p2 )t, γ, Γ ² nextSibling(p1 , p2 )⇐⇒ γ(p1 ).r = γ(p2 )Here, γx:=a represents a variable assignment that maps the variable x to a and theother variables to the same nodes as γ does. An assignment ΓX:=A for second-ordervariables is defined similarly. The dot operator . used in the definition of firstChildand nextSibling denotes the concatenation of sequences from {l,r}.
2.2.3

Auxiliary Syntax

Macro Expressions
Programmers can define their own macros for frequently used formulae by the formm ∈ Macro names
V ::= var1 x | var2 X
MacroDef ::= pred m(V , · · · ,V ) = ϕ;where each of V can be either a first-order or a second-order variable declaration. We
also augment the syntax for formulae as follows
T ::= p | S
ϕ ::= . . . | m(T , · · · ,T )where macro call form m(T1 , · · · , Tn ) is expanded to its definition whose parametervariables are replaced with the supplied arguments. Note that macro definitions cannot
be recursive. Macros are useful not only for concise description of queries, but also for
efficient static processing by separate compilation.
Path Expressions
Our core syntax has only two primitive relations on tree nodes, firstChild andnextSibling. This reflects our encoding of XML into binary trees described in Section 2.1. Although these two primitives have sufficient expressiveness, it would be
convenient if one can directly use relations based on the unranked view of the input
XML tree. For this purpose, we define four relations by macros as shown in Figure 2.3.
Namely, the relation p_cs(p,C) asserts that the set of all children of the node p (inthe unranked view) is C, and the relation p_c(p,c) asserts that c is one of the children
15

¶

³

pred p_cs( var1 p, var2 C ) =all1 c: (c in C <=>firstChild(p,c) | ex1 b: (b in C & nextSibling(b,C)));
pred p_c( var1 p, var1 c ) =ex2 C: (p_cs(p,C) & c in C);
pred a_ds( var1 a, var2 D ) =all1 d: (d in D <=>p_c(a,d) | ex1 b: (b in D & p_c(b,d)));pred a_d( var1 p, var1 d ) =ex2 D: (a_ds(a,D) & d in D);µ´
Figure 2.3: Representing unranked view in binary MSO

of p. The macros a_ds and a_d define similar relations except that these are based on
the ancestor-descendant relationship in the unranked view.
Since those relations are frequently used in XML queries, we specially define a
syntax to use those relations for mimicking XPath [6] expressions.
D ::= / | //U ::= x | S | p:S
ϕ ::= . . . | U DU D · · · DU | /U D · · · DU
Here, D stands for path delimiters and U stands for path units. The expression p/q(p//q) means that the node denoted by p is the parent (respectively, an ancestor) of
the node denoted by q in the original unranked tree. In other words, p/q is equivalent
to p_c(p,q) and p//q is equivalent to a_d(p,q). When applied to second-orderterms, such a path expression has an existential meaning. For example, p/<tag> isa shorthand for ex1 x: p_c(p,x) & x in <tag>. When applied to a pair of firstand second-order terms p:S, the expression simultaneously declares that p in S andthe term p satisfies the very path expression. For instance, the expression x:<a>/y isequivalent to x in <a> & x/y, and thus also equivalent to x in <a> & p_c(x,y).
When more than two units are connected by path delimiters, it has a conjunctive
meaning. For example, x/y/z stands for p_c(x,y) & p_c(y,z). Delimiter-prefixed
16

¶

³

pred doc_next( var1 p, var1 q ) =firstChild(p,q) | nextSibling(p,q)| ex1 r: (r//p & nextSibling(r,q));pred doc_orders( var1 p, var2 Q ) =all1 q: (q in Q <=>doc_next(p,q) | ex1 b: (b in Q & doc_next(b,q));pred doc_order( var1 p, var1 q ) =ex2 Q: doc_orders(p,Q) & q in Q;µ´
Figure 2.4: Document Orders

expressions /U1 D1 . . . Dn Un represent absolute paths from the root node. When U1 isa first-order term, the expressions are interpreted as root=U1 &U1 D2 . . . Dn Un . WhenU1 is a second-order term, the interpretation is root:U1 D2 . . . Dn Un .
As an example, the path expression/<a>//<b>/x:<c>/@dis equivalent to the following formula without path expressions:ex1 s: ex1 t: root in <a> & s in <b> & x in <c> & t in @d &a_d(root,s) & p_c(s,x) & p_c(x,t)
Order Relations
Another frequently used primitive in terms of XML processing is pre-order relations(often called document order relations) among tree nodes. We also define this relation
as a macro doc order as shown in Figure 2.4 and provide a short-hand syntax asfollows:
ϕ ::= . . . | p < pAn expression p1 < p2 is equivalent to doc order(p1 , p2 ).

17

2.3

Transformation TemplatesThis section describes the syntax and semantics of MTran, an XML transformation
language based on MSO.
2.3.1

Overview

Most of the definitions except for gather and visit expressions are straightforward. A gather expression, as its name shows, gathers all nodes in the input tree thatsatisfies the specified MSO query expression. For example, the template{gather x :: x in <B> :: x}
with the input<A><B><C>ddd</C></B><C><B>eee</B></C><B><C><B>fff</B></C></B></A>
is evaluated to the list of nodes:<B><C>ddd</C></B><B>eee</B><B><C><B>fff</B></C></B><B>fff</B>
Note that gather expression gathers all nodes that match the query regardless of
their inclusion relations. When we want to obtain only outermost nodes, we need to
explicitly specify the condition in the query expression like:{gather x :: x in <B> & ~ex1 y:(y//x & y in <B>) :: x}or more simply:{gather x :: x in <B> & ~<B>//x :: x}This query states “x is labeled B and none of the ancestors of x is labeled B,” andtherefore only the outermost B nodes are gathered in this case. A query to retrieve
only innermost nodes can also be written similarly.

18Semantics of visit
A visit expression visits every node that satisfies the associated query formulaein the subtree specified by the from clause (or the whole input tree if the from clauseis not supplied). Each node that is matched by one of the queries is transformed
according to the corresponding template, and the other unmatched nodes are left
unchanged. The result of the visit expression is the list of trees obtained after thetransformation above. This is a rough semantics of our visit expressions. However,there are subtle behaviors in details. To illustrate these, let us consider the following
template that encloses each B node with a Mark tag:{visit x :: x in <B> :: Mark[x]}Our semantics of visit expressions contains two kinds of recursion. We first
explain the first one of them, namely, recursion on input trees. The template produces,e.g., from the input<A><B><C>ddd</C></B><C><B>eee</B></C></A>
the result:<A><Mark><B><C>ddd</C></B></Mark><C><Mark><B>eee</B></Mark></C></A>
Programmers do not need to write an explicit recursion to search and transform B nodes
located deeply inside the tree structure. Instead, the recursive behavior is embeddedin the semantics.
The second kind of recursion, namely, a recursion on generated trees, appears when
we deal with nested elements. All B nodes are enclosed by Mark tag even if some of
the Bs are nested. When we feed the input document<A><B><C><B>fff</B></C></B></A>
the result is as follows:
19

<A><Mark><B><C><Mark><B>fff</B></Mark></C></B></Mark></A>First, the outer B is transformed with the specified template Mark[x], and then we perform another visitation into the generated tree. (Note that in the case such recursion
is not desired, we can specify the same condition used in the last gather example.)
This recursion is performed in order to transform other nodes from the original input
tree that are embedded in the generated nodes. We don’t retransform newly generated nodes, nor the nodes already applied the transformation in the current visit
expression. MTran is intended to be a language for one-pass transformation, and thus
our semantics applies transformations only to the nodes from the original input tree.
In the rest of this section, we formally define the syntax and the semantics of thelanguage.
2.3.2

SyntaxA whole program consists of a list of user-defined macros and a template, wheretemplates are defined by the following syntax.
EL ::= E ∗E ::= x| "s"| e[EL]| @a[EL]| {gather x :: ϕ :: EL}| {visit x (:: ϕ :: EL)∗ }| {visit x from y (:: ϕ :: EL)∗ }E stands for expressions and EL for expression lists. A visit expression without fromclause is a syntax sugar for {visit x from root ...}.
2.3.3

Semantics

Internal form
MTran internally handles three different forms of XML representation. One is
the normal textual representation as defined in the XML standard [1]. Another is20the binary encoding of XML trees described in Section 2.1, which is used in ourquery algorithm to represent input trees. The last one is the internal form, which
is a suitable representation for both input and output trees during the evaluationof our transformation templates. The internal trees I (trees in the internal form) isconstructed as follows:
I ::= (n, p)
n ::= e[I ∗ ] | @a[I ∗ ] | "s"p ∈ {0, 1}∗ ∪ {⊥}First part of the nodes of the internal form represents an unranked tree structure.
Second part maintains the position where the node inhabited in the input tree. In thecase of a node that is not from input tree (i.e. when the node is newly constructedaccording to the template), ⊥ is assigned. We use this positional information only
for the evaluation of visit expressions, which has to traverse and search the nodes
derived from input trees embedded inside the result of associated templates, as welater explain. For the final output as an XML document, positional information is
dropped.
An internal node e[ . . . ] corresponds to a standard XML element node <e> . . . </e>,
and @a[ . . . ] corresponds to an attribute a" . . . ". Note that the above definition may
yield an invalid XML, such as repeated attributes elem[@x[...] @x[...]] or nontext nodes inside attributes @x[elem[...]]. Since MTran currently does not exploit
any kind of type checking, such ill-formed XMLs are detected at runtime and resultin an error.
Definition 4. A conversion function conv from a pair of binary tree t and its node p
into the internal form is defined as follows:kz }| { (e[conv (t, p.l), . . . , conv (t, p.l r · · · r)], p) t(p) = e
conv (t, p) =(@a[conv (t, p.l)], p)t(p) = @a("s", p)t(p) = "s"kz }| {
where k is the maximum number such that p.l r · · · r ∈ Pos(t)Interpretation
An EL and E is interpreted under an input binary tree t, and a first-order variableassignment γ, and denotes a list of internal trees.
21

Now we give the semantics of expressions and expression lists. The interpretationof an expression list E1 · · · Ek is simply the concatenation of the interpretations of
E1 , E2 , · · · , and Ek :JE1 . . . , Ek K(t, γ) = concat [ JE1 K(t, γ) · · · JEk K(t, γ) ]Here, [. . . ] notation represents lists, and concat is the concatenation of all the given
lists. The interpretation of expressions are as follows:
JxK(t, γ) = conv (t, γ(x))
J"s"K(t, γ) = [ ("s", ⊥) ]Je[EL]K(t, γ) = [ (e[JELK(t, γ)], ⊥) ]J@a[EL]K(t, γ) = [ (@a[JELK(t, γ)], ⊥) ]¯
J{gather x::ϕ::EL}K(t, γ) = concat [ JELK(t, γx:=p ) ¯ p ∈ Pos(t), γx:=p ² ϕ ]J{visit x from y::ϕ1 ::EL1 :: . . . ::ϕk ::ELk }K(t, γ) = vis(Pos(t), conv (t, γ(y)))
wherevis(V,(n, p)) =concat [vis(V \{p}, I)| I ∈ JEL1 K(t, γx:=p )]






concat [vis(V \{p}, I)| I ∈ JEL2 K(t, γx:=p )]








concat [vis(V \{p}, I)| I ∈ JELk K(t, γx:=p )]





[(e[concat [vis(V, I)| I ∈ IL]], p)]





[(@a[concat [vis(V, j)| I ∈ IL]], p)] [("s", p)]

if p ∈ V and t, γx:=p ² ϕ1
if p ∈ V and t, γx:=p ² ϕ2..
.
if p ∈ V and t, γx:=p ² ϕk
if n = e[IL]if n = @a[IL]if n = "s"More than one condition in the definition of vis may be satisfied at a time. In thatcase, the first case is chosen.
The notation [f (x) | x ∈ List (, a condition on x)] is a list comprehension. Firstthe elements in the List that fail to satisfy the condition are filtered out, then thefunction f is applied to each remained elements and yields a result list of the form[f (xi1 ) · · · f (xin )]. Here the set Pos(t) is treated as a list of elements ordered by the
document order. All MSO queries in gather and visit expressions are evaluatedunder an empty second-order variable assignment (therefore omitted in the above
definitions) since we only bind first-order variables in translation templates.
Let us see the formal definition of the vis function. It takes two parameters. The
first parameter V denotes the set of input nodes that are not yet transformed in the22current evaluation of the visit expression. The second parameter (n, p) denotes thenode currently visited. When the node matches one of the query formulae, if the nodeis from the input tree and still not transformed, then the node is replaced by the list ofnodes generated from the associated template. Then again we recursively visit thesenodes; recording the current node to be already visited (the second kind of recursion
explained in the preceding subsection). When no query formulae match the node, we
just recursively go down in the tree (the first kind of recursion).
To see more clearly the subtlety of our semantics, let us consider a slightly modified
version of the previous example, which encloses each B node with a B tag:{visit x :: x in <B> :: B[x]}Consider the input <B><C><B>hello</B></C></B>. This input tree is converted to aninternal tree by conv function:(B[(C[(B[("hello", lll)], ll)], l)], ε)The vis function is first applied to this whole internal tree. This time p is ε, whichmatches the condition x in <B> and evaluated to the result of B[x] expression, i.e.
(B[(B[(C[(B[("hello", lll)], ll)], l)], ε)], ⊥)Then we revisit this generated node with the first argument V \ {ε}. Although current
node is labeled B again, the value of p is ⊥, which does not satisfy the condition to
apply transformation. Next node is again p = ε, but this time, ε is already removed
from V . Therefore we don’t transform this node anymore, and go down more deeply.
Next node is labeled C, which does not satisfy the query expression x in <B>. We get:(B[("hello", lll)], ll)This node p = ll matches the query and is transformed similarly to the case of p = ε.
The final result of the whole visit expression successfully becomes:(B[(B[(C[(B[(B[("hello", lll)], ll)], ⊥)], ε)], ⊥)that each B node in the input is doubled. Finally the MTran processor should output
the result in the standard XML format as follows:<B><B><C><B><B>hello</B></B></C></B></B>

23

Termination
Since the semantics of visit expressions is defined in terms of rather complicatedrecursion, it is not clear whether its evaluation terminates for any input trees. Therefore we give a proof of termination of whole transformation templates for any inputs.
To prove the termination of the vis function and visit expressions, we first prove
the following lemma.
Lemma 1. In each step of recursion in the vis function, the pair (V, I) of arguments always strictly decreases in the lexicographical order, where V is ordered by set-inclusion
and I is ordered by the descendant-ancestor order of internal trees.
Proof. Case analysis based on the definition of vis function. When any one of theϕj query expression is satisfied, the recursive application of vis is done with the firstargument V \ {p}, which strictly decreases from V that contains p. When none of
the ϕj is satisfied, the recursive application of vis is done with the first argument V
unchanged and the second argument with the elements of IL, which is the subpart ofI. Thus in the arguments (V, I) strictly decrease also in this case.
Using this result, we can prove the termination of a visit expression.
Lemma 2. Assuming the termination of each subexpression list ELi , evaluation of avisit expression under any input tree t and an assignment γ terminates.
Proof. Since the semantics of a visit expression is actually a evaluation of vis function. We have to prove the termination of the vis function. Since both set-inclusion for
finite sets and descendant-ancestor ordering are well-founded relations, by Lemma 1,
vis function is guaranteed to do well-founded recursion, which terminates in finite
steps. Each step of the recursion also terminates since it just evaluates MSO queries(whose deterministic terminating algorithm is given in the next chapter), evaluates
subexpression list ELi (that is assured to terminated by the assumption), and concatenates several lists. Combining these results yields the termination of the whole vis
function.
Now we finally prove the termination of any transformation templates.
Prop 1. Evaluation of E and EL always terminates.
Proof. By simultaneous induction on the structure of E and EL. For EL, since evaluation of each Ei terminates by the induction hypothesis, evaluation of the wholeexpression also terminates. For E, we need to prove six cases. The case of variable24expressions x resolves to the termination of conv function, which is clear from thedefinition of the function. The case of "s" expression is trivial. The cases of e[EL],@a[EL], and gather expressions are straightly derived from the induciton hypothesis.
The case of visit expressions is already proven by Lemma 2.

25

Chapter 3
Evaluation Algorithm

We describe our evaluation strategy for the MTran language in this chapter. In this,efficient evaluation of MSO query expressions is particularly a difficult problem andexplained in detail. Our MSO query evaluation consists of usual two steps as shown in
Figure 3.1 : (1) compilation of MSO formulae to tree automata and (2) evaluation of nary queries represented by tree automata. In this chapter, we first review known facts
on tree automata in Section 3.1, and then explain about these two steps in Sections 3.2
and 3.3. Finally in Section 3.4, we explain how to integrate the query algorithm into
our evaluation strategy for whole translation templates.

Figure 3.1: Execution Model

3.1

Preliminaries

3.1.1

Queries over trees

First we formalize the concept of queries.
Definition 5. An n-ary query for binary tree over Σ is a function q that maps eachtree t to a set of n-tuples A of its positions.
A tree language over Σ is a set of trees. A query can also be defined in terms oftree languages.
26

Definition 6. Let B = {0, 1}. An n-ary query defined by a tree language L over
Σ × Bn is a function q such thatq(t) = {(v1 , . . . , vn ) ∈ Pos(t)n |∃β1 , . . . , βn : Pos(t) → B∀i.∀v ∈ Pos(t).(βi (v) = 1 ⇐⇒ v = vi )& t × β1 × · · · × βn ∈ L}

where the product t × s of trees is a function defined as (t × s)(v) = (t(v), s(v)).
Intuitively, each βi in the definition above represents selection marks corresponding
to the i-th members of tuples. That is, a query defined by a language L selects a tuple(v1 , . . . , vn ) on a tree t if and only if L contains a tree where β1 , . . . , βn respectively
mark the elements v1 , . . . , vn as 1.
Note that we only consider selection marks that select exactly one node vi in an
input tree. In general, a tree language over Σ × Bn may contain a tree that has nomarked nodes, or more than one marked nodes. But such a language defines exactly
the same query as the language with all ill-marked trees removed.
3.1.2

Tree Automata

An important class of tree languages and queries is defined in terms of tree automata.
Definition 7. Let Σ be an alphabet. A bottom-up deterministic tree automaton over
Σ is a tuple (Σ, Q, δ, q0 , F ) where Q is a set of states, δ : Q × Q × Σ → Q is a transition
function, q0 ∈ Q is an initial state, and F ⊆ Q is a set of accepting states.
Definition 8. A run of a bottom-up deterministic tree automaton on a binary treet is a mapping ρ : Pos(t) → Q such that ρ(v) = δ(ρ(v.l), ρ(v.r), t(v)) for each nodev ∈ Pos(t). When v.l or v.r does not belong to the domain Pos(t), we use q0 insteadof ρ(v.l) or ρ(v.r). The run ρ is called accepting if ρ(ε) ∈ F . Note that a run is
uniquely determined from any tree t. In this case, we say that the tree is accepting.
Each tree automaton defines a tree language, which contains all trees accepted by
the automaton. Thus, we can regard a tree automaton over Σ × Bn as an n-ary queryover Σ.
Definition 9. An n-ary query over Σ is regular if there exists a bottom-up deterministic tree automaton that defines the query.

27

3.2

From MSO to Tree Automata

An MSO formula with n free first-order variables can naturally be seen as an nary query. A formula ϕ(~x) whose free variables are ~x = (x1 , . . . , xn ) defines a query
q(t) = {~v ∈ Pos(t)n | t ² ϕ(~v )}. It is well-known that there is an exact correspondence
between MSO and tree automata.
Theorem 1. [14, 24] For every MSO formula ϕ(~x) with n free variables, there exists
a bottom-up deterministic tree automaton A over Σ × Bn that defines the equivalent
query. Also for every bottom-up deterministic tree automaton A over Σ × Bn , there
exists an equivalent MSO formula with n free variables.
We evaluate n-ary MSO queries using this equivalence. That is, we first compile
every given MSO formula into an equivalent automaton. We exploit the MONA system [18] for this compilation. MONA is a remarkably efficient implementation and isexperimentally shown to work in practice for large formulae, even though this compilation step is well known to take a non-elementary time in the worst case. We makesome experiments in Section 4.2.
One note must be added here about the alphabets Σ. A tree automaton is definedon top of some fixed alphabet Σ and its run and acceptance is defined only on binary
trees over the Σ. Our algorithm, however, takes encoded XML documents as input
trees, which may have arbitrary set of labels. To absorb this difference, we always
add an extra symbol others to Σ of each automaton, and defines the compilationof MSO formulae, the run, and the acceptance of the automaton over the alphabetΣ ∪ {others}. Any label on input trees that does not belong to Σ is uniformly treatedas an others for these automata.

3.3

N -ary Query Algorithm

In this section, we explain our novel algorithm for n-ary queries. First, in Section 3.3.1, we introduce an algorithm that is essentially no different from the binary
query algorithm proposed by Berlea and Seidl, and formalize its extension to generaln-ary queries. Section 3.3.2 explains our improvements to the algorithm.
3.3.1

Basic Algorithm

Definition 6 yields a naive evaluation algorithm for n-ary queries represented bytree automata. That is, for every n-tuples of nodes of a given input tree t, generate28the corresponding selection mark βi ’s as in the definition and calculate the bottom-up
run of the automaton. If the run is accepting, the tuple belongs to the result set ofthe query. There can be |t|n n-tuples where |t| is the size of the input tree, and eachrun of a tree automaton takes O(|t|) time. So the total time complexity of this naive
algorithm is O(|t|n+1 ).
This high time complexity can be improved by sharing intermediate results among
calculations of the runs corresponding to the n-tuples in the following way. Our n-ary
query algorithm assigns a set m(v, q) of n-tuples of nodes to each pair of a node v oft and a state q of automaton.
Intuitively, m(v, q) is the set of tuples such that, if the tree is marked according to
the tuple, then the bottom-up run on the tree reaches the state q at the node v. We
call such m a marking run of an automaton. Let us consider an example of a ternary
query. If it is the case that (rl, r, ⊥) ∈ m(r, q1 ), this means that the automaton
reaches the state q1 at the node r, when the node rl is selected as the first element,
the node r is selected as the second element, and no node in the subtree rooted at r
is selected as the third element. The ⊥ element represents the last condition.
A marking run can be calculated in a bottom-up fashion. Each m(v, q) is calculated
from that of the children of v, as the union of all products of m(v.l, qL ) and m(v.r, qR )where qL and qR are the states transitable to the state q by appropriate markings.
Formally, we define marking runs as follows. For the sake of efficient calculation, we
define each m(v, q) as a disjoint union of sets ms (v, q), where s ∈ Bn . A sequence of bits
s represents non-bottom elements of the tuples in ms (v, q). That is, if (u1 , . . . , un ) ∈ms1 ...sn (v, q), then ui 6= ⊥ if and only if si = 1 for every i.
Definition 10. A marking run of a deterministic bottom-up tree automaton (Σ ×
Bn , Q, δ, q0 , F ) on a tree t is a set of functions m = {ms | s ∈ Bn }. Each ms is anfunction of type {l, r}∗ × Q → 2{Pos(t)∪{⊥}} defined as follows. When v ∈/ Pos(t),m0···0 (v, q0 ) = {(⊥, . . . , ⊥)}ms (v, q) = ∅if s 6= 0 · · · 0 or q 6= q0

and when v ∈ Pos(t), it is recursively defined as
ms (v, q) =[©

¯
ml (v.l, qL ) ∗ mr (v.r, qR ) ∗ {sing(v, c)} ¯ qL , qR ∈ Q,

l, r, c ∈ Bn ,δ(qL , qR , (t(v), c)) = q,ª(l, r, c) ∈ sub(s)29The tuple sing(v, c) is defined as a tuple (u1 , . . . , un ) such that ui = v if ci = 1 andui = ⊥ if ci = 0. For each s ∈ Bn , we define sub(s) ⊆ (Bn )3 by the set of splitting(l, r, c) of s such that ∀i.(si = 1 ⇐⇒ exactly one of li , ri , and ci is 1). The asterisk
product ∗ is defined as follows:
S ∗ T = {(u1 , . . . , un ) | (s1 , . . . , sn ) ∈ S, (t1 , . . . , tn ) ∈ T,
(ui = si & ⊥ = ti ) or (⊥ = si & ui = ti )}Using a marking run, we can obtain the query result as:[

m1...1 (ε, q)q∈F

ExampleBefore we discuss the evaluation algorithm, let us clarify a little complicated definition of marking runs by example. Consider the following tree t over Σ = {a, b}
defined as

:b
l:a

r:b
rl:b

rr:b

(for the sake of clarity, we present each node by a pair n:L where n is its position
from {l, r}∗ and L is its label from Σ) and the automaton (Σ × B2 , Q, δ, q0 , F ) withthe set of states Q = {q0 , q1 , q2 , q3 }, the accepting states F = {q2 }, and the transition
function δ defined as follows:δ(q0 , q0 , (s, 00)) = q0

for any s ∈ Σδ(q0 , q0 , (b, 01)) = q1
δ(q0 , q1 , (b, 10)) = q2
δ(q0 , q2 , (s, 00)) = δ(q2 , q0 , (s, 00)) = q2
δ(qi , qj , x) = q3

for any qi ∈ Q, s ∈ Σfor any other cases

This automaton defines a binary query that selects all pairs of a node and its right childboth labeled b, i.e. (ε, r) and (r, rr) for the above tree. Intuitively, q0 represents thestarting state, and q1 represents the state where the automaton finds a b node as the30second element. The accepting state q2 means that the automaton finds a desired pair.
When the automaton recognized that the marked pair is not an answer for the query,it goes to the junk state q3 . When the input tree is ill-marked, that is, when morethan one nodes are selected for the same side of the pair, the automaton also moves
to q3 . For simplicity of explanation, we here introduce the junk state q3 to construct
an automaton that rejects all ill-marked trees. Note that we do not always have to
introduce such a state for ill-marked trees, since the query defined by an automaton is
not affected by whether or not the automaton accepts ill-marked trees, as we alreadystated.
Marking runs on automata representing binary queries consists of four functions
2

m00 , m01 , m10 , and m11 of the type {l, r}∗ × Q → 2{Pos(t)∪{⊥}} . We first calculate
those functions on leaf nodes {l, rl, rr}. Since the set m00 (p, q0 ) is defined to be{(⊥, ⊥)} for p ∈/ Pos(t) and ms (p, q) = ∅ for other s, q, we only need to consider thecase qL = q0 and qR = q0 in the Definition 10. Thus, for each leaf node e we have:m00 (e, q) = {(⊥, ⊥) | δ(q0 , q0 , (t(e), 00)) = q}
m01 (e, q) = {(⊥, e) | δ(q0 , q0 , (t(e), 01)) = q}
m10 (e, q) = {(e, ⊥) | δ(q0 , q0 , (t(e), 10)) = q}
m11 (e, q) = {(e, e) | δ(q0 , q0 , (t(e), 11)) = q}
The concrete values of ms is shown in the following tables:
Table 3.1: m00 (v, q)

Table 3.2: m01 (v, q)

q0

q1

q2

q3

q0

q1

q2

q3

l:a

{(⊥,⊥)}

∅

∅

∅

l:a

∅

∅

∅

{(⊥,l)}

rl:b{(⊥,⊥)}

∅

∅

∅

rl:b

∅

{(⊥,rl)}

∅

∅

rr:b

{(⊥,⊥)}

∅

∅

∅

rr:b

∅

{(⊥,rr)}∅∅Table 3.3: m10 (v, q)
q0

q1

q2

q3

l:a

∅

∅

∅

{(l,⊥)}

rl:b

∅

∅

∅

rr:b

∅

∅

∅

Table 3.4: m11 (v, q)
q0

q1

q2

q3

l:a

∅

∅

∅

{(l,l)}{(rl,⊥)}

rl:b

∅

∅

∅

{(rl,rl)}{(rr,⊥)}

rr:b

∅

∅

∅

{(rr,rr)}

For example, the entry m01 (rr, q1 ) = {(⊥, rr)} means that if the first bit is not marked

31

for any nodes and the second bit of the node rr is marked, then the automaton reaches
state q1 at the node rr.
Next let us calculate m for the node r:b, which can be constructed from m forrl:b and rr:b. We demonstrate the calculation of the two cases that are actuallyrequired for obtaining the result of the query. The first case is m11 (r, q2 ):m11 (r, q2 ) =[{ml (rl, qL ) ∗ mr (rr, qR ) ∗ {sing(r, c)} |δ(qL , qR , (b, c)) = q2 ,(l, r, c) = sub(11)}Seeing the definition of the transition function δ, there are three choice of qL , qR , andc to satisfy the condition δ(qL , qR , (b, c)) = q2 . Namely, the case {qL = q0 , qR = q2 , c =00}, the case {qL = q2 , qR = q0 , c = 00}, and the case {qL = q0 , qR = q1 , c = 10}.
Only the last case is significant, since ml (rl, q2 ) and mr (rr, q2 ) are empty. Thus, wehave:m11 (r, q2 ) =[{ml (rl, q0 ) ∗ mr (rr, q1 ) ∗ {(r, ⊥)} | (l, r, 10) = sub(11)}= m00 (rl, q0 ) ∗ m01 (rr, q1 ) ∗ {(r, ⊥)} ∪ m01 (rl, q0 ) ∗ m00 (rr, q1 ) ∗ {(r, ⊥)}= {(⊥, ⊥)} ∗ {(⊥, rr)} ∗ {(r, ⊥)} ∪ ∅ ∗ {(⊥, ⊥)} ∗ {(r, ⊥)}= {(r, rr)}
The other interesting case is m01 (r, q1 ). There is only one choice of qL , qR , and c inthis case:m01 (r, q1 ) = m00 (rl, q0 ) ∗ m00 (rr, q0 ) ∗ {(⊥, r)}= {(⊥, r)}Finally, we show the calculation of m11 (ε, q2 ), which is the result of the query. As wellas in the case of m11 (r, q2 ), we have three choice of qL , qR , and c. This time, two cases
are significant.
[m11 (ε, q2 ) =∪=[{ml (l, q0 ) ∗ mr (r, q1 ) ∗ {(ε, ⊥)} | (l, r, 10) = sub(11)}{ml (l, q0 ) ∗ mr (r, q2 ) ∗ {(⊥, ⊥)} | (l, r, 00) = sub(11)}m00 (l, q0 ) ∗ m01 (r, q1 ) ∗ {(ε, ⊥)} ∪ m01 (l, q0 ) ∗ m00 (r, q1 ) ∗ {(ε, ⊥)}∪ m00 (l, q0 ) ∗ m11 (r, q2 ) ∗ {(⊥, ⊥)}={(⊥, ⊥)} ∗ {(⊥, r)} ∗ {(ε, ⊥)} ∪ ∅ ∗ {(⊥, ⊥)} ∗ {(ε, ⊥)}∪ {(⊥, ⊥)} ∗ {(r, rr)} ∗ {(⊥, ⊥)}= {(ε, r), (r, rr)}
32

Complexity
Naive bottom-up calculation of m still takes O(|t|n+1 ) time, since we need to
calculate m1...1 that grows up to O(|t|n ) in the worst case for all |t| nodes.
Berlea and Seidl has proposed an algorithm for binary queries in [17], based on
the bottom-up calculation of m. They used their formalism of regular queries basedon push-down forest automata, but the same approach is applicable also for simple
tree automata. They took two-phase approach to avoid operating on large m11 sets.
During the first phase, only m00 , m01 , and m10 are calculated as in Definition 10. In theSsecond phase, they collect the elements of q∈F m11 (ε, q) from each node through one
Sextra top-down run. This is possible since m11 (v, Qc ) ≡ q∈Qc m11 (v, q) is definable
in terms of m11 (v, l, Q1 ) and m11 (v, r, Qr ) for appropriate Q1 and Q2 in the followingway:
m11 (v, Qc ) ={m00 (v.l, qL ) ∗ m11 (v.r, qR ) ∗ {(⊥, ⊥)} | δ(qL , qR , (t(v), 00)) ∈ Qc }∪{m11 (v.l, qL ) ∗ m00 (v.r, qR ) ∗ {(⊥, ⊥)} | δ(qL , qR , (t(v), 00)) ∈ Qc }∪ (other terms that do not contain the m11 of child nodes) ...
= m11 (v.r, {qR | ∃qL .m00 (v.l, qL ) 6= ∅, δ(qL , qR , (t(v), 00)) ∈ Qc })∪ m11 (v.l, {qL | ∃qR .m00 (v.r, qR ) 6= ∅, δ(qL , qR , (t(v), 00)) ∈ Qc })∪ (others...)
They have concluded that their algorithm runs in O(rt + s) time where t is the sizeof input documents and r is the maximum size of m10 ’s and m01 ’s – potential matches– and s is the number of the result tuples. Union operation in the definition of m10
and m01 takes the time proportional to the size of operand sets (r), and the calculationis repeated t times. The size r of potential matches may be smaller compared to t inpractical cases, but it is O(t) in the worst case. Therefore the total time complexity
is O(t2 ). As Berlea et al. mentioned (but did not formalize), their algorithm can begeneralized to n-ary queries, and the complexity is O(tn ) time. This has been the best
known result for the n-ary MSO query problem.
We have improved this result by optimizing the intermediate set operations andachieved O(t + s) time complexity for n-ary queries. We give the detail in next subsection.

33

3.3.2

Our Algorithm

Our strategy is rather straightforward. We calculate the whole marking run including m1...1 directly following Definition 10, using lazy set operations.
As we have seen in the previous example, not all intermediate sets are necessaryfor query outputs: only the sets associated with a node and a state that can finallylead to acceptance at the root node are useful. In the previous example, the marking
run m consists of 100 sets – the product of 4 kinds of bits, 5 nodes, and 4 states –but few of them are actually required to calculate the result of the query. If we could
know whether the value of each ms (v, q) is required for the final result, and avoid
unnecessary calculations, it would improve the efficiency.
Our algorithm delays set operations like unions and products for non-empty sets
until actually enumerating the final result, yet still eagerly does calculations on empty
sets (∅) and unit sets (a singleton set of the tuple whose all elements are the bottom:{(⊥, · · · , ⊥)}). We show that by this approach the time complexity of n-ary query
reduces to O(t + s), linear in the size of the input and the output.
Partially Lazy Set Operations
We first define lazy set operations required to calculate marking runs. Here is our
implementation of the set data type and operations over it in Objective Caml [25].
Only two operations, union and product, are necessary.
¶³

type node_set_ne= Singleton of (node option) list
| Unionof node_set_ne * node_set_ne| Productof node_set_ne * node_set_neµ´

The type of non-empty sets. The node option type is a type that can be either None(⊥) or Some x where x can be any value of type node. Elements of the sets are length-nlists of node options. Unions and products are represented as an operation tree thatsymbolically represents a set. When it comes to the point where the actual membersof the set are required, the operation tree is evaluated to an explicit form.

34

¶

³

type node_set= Empty| UnitSet| NonEmpty of node_set_neµ´

The type of sets of nodes. To deal with emptiness, empty sets and non-empty sets arestrictly distinguished.
¶³

let union a b = match (a,b) with
| Empty,s| s,Empty| UnitSet,s | s,UnitSet-> s-> UnitSet| NonEmpty s1, NonEmpty s2 -> NonEmpty (Union s1 s2)
let product a b = match (a,b) with
| Empty,s| s,Empty| UnitSet,s | s,UnitSet-> Empty-> s| NonEmpty s1, NonEmpty s2 -> NonEmpty (Product s1 s2)µ´Union and product operation. An empty set and a unit set is dealt as a specialcase. That is, when one of the arguments is an empty set (a unit set, respectively),
the set operation is explicitly performed at that point. This is to avoid delayed unnecessary computations of the left operand of the form like Product(LargeSet, ∅)(Product(LargeSet, {⊥, . . . , ⊥)})). These special treatments are essential for linear
time complexity. Note that each definition of union and product contains one patternmatching and two applications of data constructors, therefore either operation can bedone in constant time.
We next show the function to convert an operation tree to the actual list of elementsthat belong to the set represented by the operations tree.

35

¶

³

(* ’a option list -> ’a option list -> ’a option list *)let prod_one a b =match (a, b) with| (None::al,| (b::bl) -> b :: prod_one al bla::al, None::bl) -> a :: prod_one al bl| _ -> raise "should not happen"(* ’a option list list -> ’a option list list-> ’a option list list *)let prod sa sb acc =fold_right (fun a acc ->fold_right (fun b acc -> (prod_one a b)::acc) sb acc) sa accµ´

The function prod is to calculate the asterisk product exactly as in Definition 10 andappend them to the list acc.
¶³(* ’a node_set -> ’a list list *)let to_list = function| Empty-> []| UnitSet-> raise "should not happen"| NonEmpty s -> let rec f s acc = function| Singleton vs -> vs::acc| Uniona b -> f a (f b acc)

| Producta b -> prod (f a []) (f b []) acc

in map (map (fun (Some e)->e)) (f s [])µ´

The function to list is the main routine, which converts a symbolic operation tree
to an actual set of tuples. Since this function is assumed to be applied to the set that
represents the result of the query, it does not consider the case of UnitSet, whichmeans that no node is selected. For Singleton, we just create a singleton list. For
Product, we use the prod function that is already defined. For Union operation, justconcatenating two lists will work fine. To see this, let us review the Definition 10. Our
query algorithm always takes the union of two sets in the form[ml (v.l, qL ) ∗ mr (v.r, qR ) ∗ {(...)}

l,r,c

where ml (v.l, qL ) consists of tuples whose all elements belong to the subtree rooted36

at v.l, and mr (v.r, qR ) consists of tuples in the subtree rooted at v.r. This meansthat the ith element of a tuple in the set ml (v.l, qL ) ∗ mr (v.r, qR ) belongs to thesubtree of v.l if and only if the ith bit of l is 1. Thus, if l 6= l0 or r 6= r0 , the set
ml (v.l, qL ) ∗ mr (v.r, qR ) and the set ml0 (v.l, qL ) ∗ mr0 (v.r, qR ) are always disjoint.
This is why simple concatenation works well.
Complexity
Using these lazy set operations, we can calculate all operation trees corresponding
to ms including m1...1 , by simply following Definition 10. As shown in the definition,
all ms for each node v can be constructed as the union of the set of ml (. . . ) ∗ mr (. . . ) ∗{v, . . . , v}. Since there are |Q|2 choices for qL and qR , and at most 3n choices for(l, r, c), using lazy set operations, we can construct the operation trees corresponding
to ms in O(3n |Q|2 ) steps. Thus, to calculate marking runs for all nodes in the treetakes O(3n |Q|2 t) time, which is linear to the size of the input tree.
To show the total complexity of query evaluation is linear, we next show that theevaluation of operation trees to obtain the list of elements in the denoted set willtake only linear time with respect to the size of the output list. The following lemmaassures that the to list function can be evaluated in linear time to the size of the set
denoted by the argument.
Lemma 3. Let |s| be the length of the resulting list of operation tree s. The inner
function f s acc in the definition of to list can be evaluated in O(3k n|s|) time where
n is the arity of the query, and k is the maximum number of Product nodes in eachpath from the root to a leaf node of the operation tree s.
The maximum number of Product nodes on each path are limited to n in ouralgorithm, since we only generate Product nodes between non-empty non-unit sets.
Such products strictly decrease the number of ⊥ in each tuple, and the tuples weconsider here are always n-tuples. Therefore we can derive O(3n n|s|) time from thislemma. The whole query computation ends in O(3n (|Q|2 t + n|s|)) time. When thequery formula is fixed, the values 3n , |Q|2 , and n are just constant factors, so we obtainthe complexity O(t + |s|). The proof of Lemma 3 can be done by simple induction on
the structure of the arguments of type node set ne:
Proof. The Singleton case is trivial. For the Union case, by induction hypothesis, (fb acc) is evaluated in O(3k n|b|) time and then (f a ...) is evaluated in O(3k n|a|)time. So totally O(3k n|a| + 3k n|b|) = O(3k n|s|) time is consumed. For the Product37

case, by induction hypothesis, (f a []) is evaluated in O(3k−1 n|a|) time and then (fb []) is evaluated in O(3k−1 n|b|) time. Since the prod operation is O(n|a||b|), total
complexity is O(3k−1 n|a| + 3k−1 n|b| + n|a||b|) < O(3k n|a||b|) = O(3k n|s|)
ExampleRunning our algorithm on the previous example in the explanation of basic algorithm, we obtain m11 (ε, q2 ) as the following operation tree
NonEmpty(
Union(
Product( Singleton [⊥;r],

Singleton [ε;⊥] ),Product( Singleton [⊥;rr], Singleton [r;⊥] )))instead of a concrete set {(ε, r), (r, rr)}. By evaluating this tree using the to list
function, we get the desired result: [[r; rr]; [ε; r]].
Two features of the algorithm has eliminated unnecessary calculation. Th firstpoint is its laziness. By delaying the actual construction of the sets, we only need to
calculate the sets contained in the query result m11 (ε, q2 ).
The second point is its eager evaluation for empty and unit sets. As a consequenceof this strategy, resulting NonEmpty trees never contain subtrees that represent empty
sets. Any calculations of sets that are taken a product between an empty set areskipped in this algorithm.

3.4

Transformation Template Evaluation

Evaluation of gather or visit expressions themselves are clear from the definitionof semantics. For gather expressions, we first obtain the set of nodes that satisfied
the specified query expression. Then for each node in the result, we bind the node
to the specified variable, and recursively evaluate the associated subtemplates. All
resulting trees from subtemplates are concatenated to form the result of whole gather
expression. For visit expressions, we first obtain the query result and for each nodein the input we record information whether the node matched each query. Then
we recursively transform the specified subtree as the vis function in the semantics.
The issue is, how to integrate the query algorithm introduced in Section 3.3 into theevaluation strategy for whole transformation templates.

38

3.4.1

Efficient N-ary Queries Using Context Information

Naive implementation of the semantics in Section 2.3.3 will evaluate each queryas an unary query, by fixing the other variables than the one to be queried in outer
templates. However, as we already discussed in Section 1.2.3, we do not take thisstrategy. Instead, we evaluate each query as an n-ary queries, where n is the numberof free variables of the query expression. Consider the following case:{gather x :: φ(x) :: {gather y :: ψ(x,y) :: ...}}
We evaluate only once the expression ψ(x, y) as a binary query, and obtain a list of 2tuples [(v1x , v1y ) . . . (vsx , vsy )] that each tuple satisfies the expression. This list is referred
as an table to obtain the list of all ys for each x bound by the outer template. In thisway, each query is evaluated only once per one input document. Thus, the total time
consumed for queries will be the sum of the time of each query.
This strategy, however, still has some waste. Obviously, we only need the lists ofy(vix , vi ) such that the node vix satisfies the query expression φ(x). Not all results of
ψ(x, y) are necessary. This could be a problem, since as we proved in the preceding
subsection, each query takes O(3n (|Q|2 t + ns)) time that depends on the size of query
result s.
One way to handle this problem is to rewrite the query expression as follows:{gather x :: φ(x) :: {gather y :: φ(x) & ψ(x,y) :: ...}}
Pushing outer query expressions into inner queries and concatenating them conjunctively. This rewriting keeps the result of transformation unchanged, and reduces thesize of result from inner binary queries. Only the pairs (vix , viy ) satisfying φ(vix ) is obtained. Although this rewriting solution indeed reduces the size of s, it causes anothercomplexity problem. Due to the complication of the query formula from ψ(x,y) toφ(x) & ψ(x,y), the size |Q| of compiled automaton may increase. The parameter |Q|
affects the total time complexity in quadratic order and cannot be ignored.
We developed a slightly modified version of n-ary query algorithm to remedy thisproblem. We now are able to reduces the query result as same as the rewriting approach
while keeping the size of automata unchanged, by using the result of outer queries(namely, context information) during the query evaluation of inner queries.
We first execute the outermost unary query φ(x) in the same way as explainedin the previous subsection, and obtain the list of results Rx = [ux1 . . . uxk ]. We next
execute the inner query ψ(x,y) with one modification to the definition of a marking

39

run:
ms (v, q) =[©

¯
ml (v.l, qL )∗mr (v.r, qR ) ∗ {sing(v, c)} ¯
qL , qR ∈ Q,

l, r, c ∈ Bn ,δ(qL , qR , (t(v), c)) = q,(l, r, c) ∈ sub(s),∀i.var [i] 6= y&ci = 1 =⇒ v ∈ Rvar [i]ªwhere var [i] is the variable that corresponds to the i-th selection mark of an automaton.
In this modified definition, we select each node v as a marked node for variable x only
when v is contained in Rx . Final result obtained in this way thus only contains tuples
y(vix , vi ) such that vix ∈ Rx . Checking the extra condition (underlined part) does notincur any additional time complexity blowup, since by processing outer queries earlier
than inner ones, we can always have each Rvar [i] already constructed and its inclusion
can be determined in constant time using any appropriate data structure such as
hash-tables.

40

Chapter 4
Experiments

In this chapter, we conduct several experiments of MTran language. In Section 4.1,
we give experiments on expressiveness by writing several transformation templates in
MTran. In Section 4.2, we measure the execution time of several examples in oursystem and confirm that it yields an enough performance.

4.1

ExamplesIn this section, we give several example templates written in MTran and demonstrate its expressiveness. The first example is a template to generate the table ofcontents from a given input XHTML document. The second example is a templateusing linguistic queries. The third example is a simplification of RELAX NG schemas.
4.1.1

XHTML Table of Contents

The first example shown in Figure 4.1 is a template to add a table of contents toa given input XHTML documents. That is, it retrieves the heading elements fromthe input document, constructs a table of contents as a tree of itemized lists thatreflect the hierarchical structure of the input, and prepends the table to the original
document. More specifically, the template converts the flat structure of h2, h3, h4,
and h5 in the input to an explicit hierarchy using ul and li itemization. For example,
the template transforms the input<html><head><title>Title</title></head><body><h1>Title</h1><h2>Chapter 1</h2>

41

¶

³

pred subheading(var1 a, var1 b, var2 B, var2 A) =b in B & a<b & all1 x:(a<x & x in A => b<x);{visit b :: /<html>/b:<body> :: body[h1["index"]ul[ {gather h2 :: h2 in <h2> ::li[ {gather t :: h2/t :: t} ul[{gather h3 :: subheading(h2,h3,<h3>,<h2>) ::li[ {gather t :: h3/t :: t} ul[{gather h4 :: subheading(h3,h4,<h4>,<h3>) ::li[ {gather t :: h4/t :: t} ul[{gather h5 :: subheading(h4,h5,<h5>,<h4>) ::li[ {gather t :: h5/t :: t} ]} ]]} ]]} ]]} ]{gather c :: b/c :: c}]}µ´Figure 4.1: Example: Table of Contents<h3>Section 1.1</h3> <p>The quick</p><h4>Section 1.1.1</h4> <p>brown fox</p><h3>Section 1.2</h3> <p>jumps over</p><h2>Chapter2</h2><p>the lazy</p><h3>Section 2.1</h3> <p>dog.</p><h2>Chapter3</h2></body></head>to the following XHTML document:<html><head><title>Title</title></head><body><h1>Index</h1><ul> <li>Chapter 1 <ul><li>Section 1.1 <ul>42

<li>Section 1.1.1 <ul/></li></ul></li><li>Section 1.2 <ul/></li></ul></li><li>Chapter 2 <ul><li>Section 2.1 <ul/></li></ul></li><li>Chapter3 <ul/></li> </ul><h1>Title</h1> (...snip... the same content as the input follows)</body></head>Let us explain the overall structure, using the transformation template on h3 elements. The part of the template related to h3 elements is as follows:¶³

ul[ {gather h3 :: subheading(h2,h3,<h3>,<h2>) ::li[ {gather t :: h3/t :: t}
...
]} ]
µ

´

By the query subheading(h2,h3,<h3>,<h2>) we gather all h3 elements that are subheadings of already selected h2 elements. For each selected h3 element, we generate
a list item with its content to be the copies of all child elements of the corresponding
h3 element ({gather t::h3/t::t}). We nest similar transformations on h4 and h5
elements inside each list item and constructs the whole hierarchy.
The macro subheading(a,b,B,A) intuitively means as follows:“The node b belongs to the set B, and it appears after the node a andbefore any nodes x in A placed after a in the document order”
Thus, for example, the query subheading(h2,h3,<h3>,<h2>) gathers the nodes h3
labeled <h3> and appearing between the current h2 and the next node labeled <h2>
if such <h2> exists, or otherwise all <h3> nodes appearing between the current h2
and the end of the input. In other word, it gathers all sections (<h3>) in the current
chapter (<h2>).
Although each sub-relation – “a node is labeled B”, “a node appears after anothernode in document order”, and so on – is expressible in almost all query languages,
several languages such as XPath fails combining them up into one subheading predicate. This is because XPath cannot express a conjunction of two or more relations and43

an universal quantification in general, while MSO, which has regular expressiveness,
naturally represent such combinations by using logical operators, as we have seen.
4.1.2

Linguistic Queries

The second example is taken from a motivating example of LPath language developed by Bird, Chen, Davidson, Lee, and Zheng [26]. LPath is an extension to
XPath that supports linguistic queries. In the field of linguistics, parsed sentences arecommonly represented as labeled trees. An example of such tree looks like:<S id="1"><NP id="2">I</NP><VP id="3"><V id="5">saw</V><NP id="6"><NP id="7"><Det id="9">the</Det><Adj id="10">old</Adj><N id="11">man</N></NP><PP id="8"><Prep id="12">with</Prep><NP id="13"><Det id="14">a</Det><N id="15">dog</N></NP>
</PP>
</NP>
</VP>
<N id="4">today</N></S>

The authors of LPath argued that there are mainly three requirements for linguistic
queries: “subtree scoping” that restricts the scope of queries in a specified subtree,“edge alignment” condition to state whether a node is leftmost (or rightmost) withina particular subtree, and “immediately follow” relationship. A node q is defined to
immediately follow p when p appears immediately after q in some proper analysis [27],where a proper analysis is a sequence obtained by several reverse applications of given
grammar productions to a given sentence, e.g., NP saw NP today is an example ofproper analysis for the sentence “I saw the old man with a dog today.”
LPath extends XPath to support the three features above, and enables us to write
many queries that are not expressible in XPath. The authors give the following as test
cases:Q1 Find noun phrases that immediately follow a verb.
44

Q2 Within a given verb phrase, find nouns that follow a verb which is a child of theverb phrase.
Q3 Find all verb phrases that are comprised of a verb, a noun phrase, and a prepositional phrase.
All these queries are already expressible in our MSO queries without any extensions
as show in Figure 4.2. In LPath implementation, “immediately following” relation was
defined algorithmically and its equivalence to the definition based on proper analyses
needed to be proved. Using second-order variables, we can define the relation directlyin terms of the concept of proper analyses. First we prepare a macro to assert that a
set A is a proper analysis.
¶³

pred proper_analysis(var2 A) =all1 x: (x in A <=> ~(A//x | x//A));µ´That is, a proper analysis A is a set of positions such that for any node x, if x belongs
to A then all ancestors and descendants of x do not belong to A, and otherwise there
exists an element of x being an ancestor or a descendant of x. Using this macro, the“p immediately follows q” relation can be expressed directly through the definition “insome proper analysis p appears immediately after q.”¶³

pred imm_follow(var1 x, var1 y) =ex2 A: (proper_analysis(A) & x in A & y in A & x<y& ~ex1 z:(z in A & x<z & z<y));pred follow(var1 x, var1 y) =ex2 A: (proper_analysis(A) & x in A & y in A & x<y);µ´The imm follow relation can be directly read as “in some proper analysis A that
contains both x and y, there exists no z appearing between x and y (i.e., y appears
just after x.” By virtue of the existence of second-order variables, the condition like“in some proper analysis” is naturally representable as ex2 A: (proper analysis(A)...) in MSO.
4.1.3

Relax NG Simplification

RELAX NG specification [16] defines several simplification rules for transforming a
RELAX NG schema into a simpler syntax. Although many of the transformations areeasily realizable in traditional XML transformation languages, some of them require a

45

¶

³

pred

leftmost(var1 x) = ~ex1 y: nextSibling(y,x);

pred rightmost(var1 x) = ~ex1 y: nextSibling(x,y);
pred lmd(var1 a, var1 d) =a//d & all1 x:(a//x//d | x=d =>leftmost(x));

pred rmd(var1 a, var1 d) =a//d & all1 x:(a//x//d | x=d => rightmost(x));
pred comp(var1 c, var1 y1, var1 y2, var1 y3) =lmd(c,y1) & imm_follow(y1,y2) & imm_follow(y2,y3) & rmd(c,y3);pred Q1(x) =ex1 v:(v in <V> & imm_follow(v,x) & x in <NP>);
pred Q2(x) =ex1 vp: ex1 v: (vp:<VP>/v:<V> & follow(v,x) & vp//x:<N>);
pred Q3(x) =ex1 v: ex1 np: ex1 pp:(v in <V> & np in <NP> & pp in <PP> & _ in <VP>
& comp(_,v,np,pp));test[
Q1[ {gather x :: Q1(x) :: x} ]Q2[ {gather x :: Q2(x) :: x} ]Q3[ {gather x :: Q3(x) :: x} ]]µ´Figure 4.2: Example: Linguistic Queries46

more sophisticated approach. We take up their “empty element” rule as an example.
The empty element in RELAX NG schema means an empty sequence of nodes. Hereis an excerpt from their specification:
In this rule, the grammar is transformed so that an empty element does
not occur as a child of a group, interleave, or oneOrMore element or as
the second child of a choice element. A group, interleave or choiceelement that has two empty child elements is transformed into an empty
element. A group or interleave element that has one empty child element
is transformed into its other child element. A choice element whose second
child element is an empty element is transformed by interchanging its twochild elements. A oneOrMore element that has an empty child element istransformed into an empty element. The preceding transformations areapplied repeatedly until none of them is applicable any more.
Without a sufficient expressive query language, achieving the desired result requires
us to repeat the above transformations many times until none of them is applicable
any more. By using MSO’s ability to capture all regular queries, we can write thecondition whether a node should finally be converted to an empty element, as follows:¶³
pred convertible_to_empty(var2 Empty) =all1 x: (x in Empty <=>x in <empty>| x in <group>& all1 y: (x/y => y in Empty)| x in <interleave> & all1 y: (x/y => y in Empty)| x in <choice>& all1 y: (x/y => y in Empty)| x in <oneOrMore>& all1 y: (x/y => y in Empty);

pred emp(var1 x) =ex2 E: (convertible_to_empty(E) & x in E);µ´Using the predicate, the empty element simplification can be executed as a one-passtransformation, which is more efficient than repeated transformations.
Figure 4.3 shows the implementation in MTran. We assume that the input is avalid RELAX NG schema, and that each group and interleave node has exactly
two children. If a node x is convertible to empty, then we output an empty node.
Otherwise, if x is a group or interleave element with an empty child, we translate
the node to the other child that is non-empty. If the node x is a choice node, then
47

¶

³

{visit x:: emp(x) ::empty[]:: (x in <group> | x in <interleave>) & ex1 y:(x/y & emp(y)) ::{gather y :: x/y & ~emp(y) :: y}:: x in <choice> ::choice[ {gather y :: x/y &emp(y) :: y}{gather y :: x/y & ~emp(y) :: y} ]}µ´Figure 4.3: empty element simplification

we bring the empty child before, as stated in the simplification rule. Any other node
is kept unchanged (which is ensured by the semantics of visit).
The example above shows the advantage of no-recursion of both MSO and oursemantics of visit expressions. Regular expressiveness of MSO enables us to check
whether a node is convertible to empty by a single query emp(x), without writing
any explicit recursive tree traversals. The semantics of visit expressions eliminates
the necessity to explicitly write down a recursive application of the transformationin the template for group, interleave, and choice elements. Without our implicit
recursion semantics, we would had to specify that we need to recursively transformgathered elements y.

4.2

Preliminary Performance Evaluation

The experiments presented in this section are use the three examples we havepresented in the preceding section. All benchmarks are run on Windows XP SP2
operating system on a 1.6GHz AMD Turion processor with 1GB RAM, using MONA
1.4 as a backend compiler of MSO formulae. We have implemented our system in
C++ programming language and compiled in GNU C++ Compiler [28].
Our implementation strategy of transformation templates consists of two steps:(1) compilation of MSO formulae to tree automata using MONA system as explainedin Section 3.2 and (2) query evaluation and transformation with the compiled tree
automaton. We experiment on each step separately.
Table 4.1 shows the total time spent for compiling all query expressions in each48

TableOfContents

0.970

Linguistic

0.655

RelaxNG

0.553

Table 4.1: Compilation Time (sec)program. Although compilation of MSO formulae to tree automata is known to takehyper-exponential time in the theoretical worst case, the experiment shows that at least
for these three examples of XML queries, our strategy yields enough performance.
We measure the performance of our evaluation algorithm using randomly generated
XML documents of different sizes as inputs. Table 4.2 shows the result. We can confirm
that the transformations are also executed in practical time consumption.
10KB

100KB

1MB

TableOfContents

0.038

0.320

3.798

Linguistic

0.063

0.429

4.050

RelaxNG

0.068

0.540

5.684

Table 4.2: Evaluation Time (sec)

4.2.1

N -ary query performance

To demonstrate the efficiency of our n-ary query algorithm and template evaluation
strategy, we compare the performances of same transformation between MTran andtraditional XSLT processors: XT [29] and Xalan-C [30]. For benchmark, we write,
both in MTran and XSLT, a transformation that appends, to the content of each h2
element, the content of its preceding h1 element.
¶³

pred preceding(var h1, var x) =h1 in <h1> & h1<x & all1 y:(y in <h1> & y<x => ~h1<y);{visit x :: x in <h2> ::h2[ {gather c :: x/c:# :: c} " - "{gather h1 :: preceding(h1,x) :: {gather c::h1/c:#::c}} ]
}
µ

´

49

¶

³

<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"><xsl:template match="h2"><h2><xsl:value-of select="."/> <xsl:value-of select="preceding::h1[1]"/></h2></xsl:template><xsl:template match="@*|node()"><xsl:copy><xsl:apply-templates/></xsl:copy></xsl:template></xsl:stylesheet>µ´As we explained in Section 3.4.1, MTran processes the query preceding(h1,x) as abinary query and evaluates it only once. On the other hand, XT and Xalan-C evaluate
the XPath query preceding::h1[1] for each node h2. This difference becomes clear
in the case that the input document contains a large number of h2 elements. Our
O(t + s) algorithm evaluate the binary query preceding(h1,x) in MTran version in
linear time with respect to the size of the input, while XT and Xalan-C evaluate
the unary query preceding::h1[1] in linear time and repeats the evaluation for thenumber of h2 times. Table 4.3 and Figure 4.4 show that the evaluation time for thefollowing form of inputs<html><h1>aaa</h1><h2>bbb</h2> <h2>bbb</h2> ... <h2>bbb</h2></html>varying the number of h2 elements from 1000 to 9000. MTran performs the transformations linearly, while XT and Xalan-C incur quadratic blowup.
(size)

1000

2000

3000

4000

5000

6000

7000

8000

9000

MTran

0.155

0.293

0.433

0.580

0.767

0.898

1.020

1.261

1.430

Xalan-C

0.155

0.416

0.850

1.442

2.242

3.175

4.289

5.579

7.040

XT

1.014

2.537

5.077

8.834

15.65723.78832.87042.48356.327

Table 4.3: Evaluation Time(sec)

50

10
MTran
Xalan-Cxt
8time(sec)

6

4

2

0
0

2000

4000

6000
size

Figure 4.4: Evaluation Time

51

8000

10000

Chapter 5
Conclusion and Future Work

5.1

Conclusion

We designed and implemented an XML transformation language MTran, which
adopts monadic second-order logic formulae as the query language. We showed fouradvantages of MSO: expressiveness to capture all regular queries, elimination of recursions, don’t-care semantics that allows us not to mention the nodes irrelevant to aquery, and natural n-ary queries. We have developed a tree automata based algorithm
for efficient processing of n-ary queries. Our algorithm improved the worst case timecomplexity from the previously known best result O(tn + s) to O(t + s), linear in thesize of the input and the output. Using MONA system as a backend MSO compiler,
we have implemented the algorithm in our MTran interpreter.

5.2

Future Work

Full-scale XML processing
Many issues still remain as future work. One direction is the full-scale language
design and implementation to support all features of XML documents. Adding support for namespaces, comments, and processing instructions to current MTran is not
so a difficult problem. The largest theme in this direction is the support of texttransformations. Our current implementation only can copy or remove text nodes,
and has no support for the manipulation of the content of text nodes. Although it ispossible to extend our language with many built-in string manipulation functions, weplan to investigate more expressive and coherent approach: text transformation basedon MSO. The advantages of MSO like regular expressiveness or don’t-care semantics
also could be applied in the field of text transformation. Moreover, by integrating the52language for XML and text transformation, uniform manipulation of structured andunstructured data format (such as, comma separated texts) would be achieved.
Static Type Checking
Static type checking is an important problem for programming languages. Many
researches [5, 31, 32, 33] have been done in the area of type checking for regulartree languages. We would like to investigate how those results are applicable to ourlanguage. Type checking problem for our distinct semantics of visit expressions isparticularly interesting. Also we wish to study query optimization based on type
information. The MONA system, which we adopted as a backend of MTran language,
exploits a kind of automata optimization based on static information through guided
tree automata [34]. We are considering the use of guided tree automata for optimization
over types.
’Move’ Transformation
As stated in Chapter 1, MSO is well-suited to describe relations between distantnodes. Our language leverages this advantage. Accumulation of distant nodes isachieved through gather expressions and simultaneous translation of distant nodes isrealized by visit expressions. Nevertheless it is awkward in our language to describe
a transformation that moves one node to another distant place in the input tree while
keeping the other nodes unchanged.
We are already able to express such transformation through visit and gather
expressions, by visiting and erasing the node to be moved, and on another front visiting
the destination of the move and gathering the node from original position. However,this approach seems to be redundant that we need to write the same query in twoplaces (in the visit expression for erasing and in the gather expression). Nodemoving transformation is occasionally required in practice, and should be solved in
more concise manner. We plan to investigate the language design to achieve concise
move transformation as further research.

53

References[1] Tim Bray, Jean Paoli, C. M. Sperberg-McQueen, Eve Maler, and Fran¸ois Yergeau.
Extensible Markup Language (XML) 1.0 (Third Edition). http://www.w3.org/
TR/REC-xml, Feb 2004.
[2] Frank Neven. Automata, logic, and xml, 2002.
[3] Christoph Koch. Efficient processing of expressive node-selecting queries on xml
data in secondary storage: A tree automata-based approach. In VLDB, pages
249–260, 2003.
[4] Sebastian Maneth and Frank Neven. Structured document transformations basedon XSL. In DBPL, pages 80–98, 1999.
[5] Sebastian Maneth, Thomas Perst, Alexandru Berlea, and Helmut Seidl. XML
type checking with macro tree transducers. In PODS, 2005.
[6] James Clark and Steve DeRose. XML path language (XPath) version 1.0. http://www.w3.org/TR/xpath, Nov 1999.
[7] Serge Abiteboul, Dallan Quass, Jason McHugh, Jennifer Widom, and Janet L.
Wiener. The Lorel query language for semistructured data. International Journal
on Digital Libraries, 1(1):68–88, 1997.
[8] Peter Buneman, Mary F. Fernandez, and Dan Suciu. UnQL: A query language
and algebra for semistructured data based on structural recursion. VLDB Journal,9(1):76–110, 2000.
[9] Alin Deutsch, Mary Fernandez, Daniela Florescu, Alon Levy, and Dan Suciu.
XML-QL: A Query Language for XML, 1998. http://www.w3.org/TR/NOTE-xml-ql.
[10] Anne Brüggemann-Klein and Derick Wood. Caterpillars: A context specification
technique. Markup Languages, 2(1):81–106, 2000.

54

[11] Makoto Murata. Extended path expressions for XML. In Proceedings of Symposium on Principles of Database Systems (PODS), pages 126–137, 2001.
[12] Haruo Hosoya and Benjamin C. Pierce. Regular expression pattern matching forXML. Journal of Functional Programming, 13(6):961–1004, 2002. Short version
appeared in Proceedings of The 25th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 67–80, 2001.
[13] Véronique Benzaken, Giuseppe Castagna, and Alain Frisch. CDuce: An XMLcentric general-purpose language. In Proceedings of the International Conference
on Functional Programming (ICFP), pages 51–63, 2003.
[14] J. W. Thatcher and J. B. Wright. Generalized finite automata with an application
to a decision problem of second-order logic, 1968.
[15] David C. Fallside. XML Schema Part 0: Primer, W3C Recommendation. {http://www.w3.org/TR/xmlschema-0/}, 2001.
[16] James Clark and Makoto Murata. RELAX NG. {http://www.relaxng.org},
2001.
[17] Alexandru Berlea and Helmut Seidl. Binary queries. In Extreme Markup Languages 2002, August 2002.
[18] Nils Klarlund, Anders Møller, and Michael I. Schwartzbach. MONA 1.4. http://www.brics.dk/mona/, 1995.
[19] Nils Klarlund, Anders Møller, and Michael I. Schwartzbach.

MONA imple-

mentation secrets. International Journal of Foundations of Computer Science,13(4):571–586, 2002. World Scientific Publishing Company. Earlier version in
Proc. 5th International Conference on Implementation and Application of Automata, CIAA ’00, Springer-Verlag LNCS vol. 2088.
[20] Frank Neven and Jan Van den Bussche. Expressiveness of structured document
query languages based on attribute grammars. In PODS ’98. Proceedings ofthe seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of
database systems, pages 11–17. ACM press, 1998.
[21] Alexandru Berlea and Helmut Seidl. fxt - a transformation language for XML
documents. In XML Conference And Exposition 2001, Dec 2001.

55

[22] Joachim Niehren, Laurent Planque, Jean-Marc Talbot, and Sophie Tison. N-ary
queries by tree automata. In DBPL, Aug 2005.
[23] Keisuke Nakano. An implementation scheme for XML transformation languages
through derivation of stream processors. In The 2nd ASIAN Symposium on Programming Languages and Systems, volume 3302 of Lecture Notes in Computer
Science, pages 74–90, 2004.
[24] J. R. Büchi. Weak second-order arithmetic and finite automata. Zeitschrift fürmathematische Logik und Grundladen der Mathematik, 6:66–92, 1960.
[25] Xavier Leroy, Damien Doligez, Jacques Garrigue, Jérôme Vouillon, and Dider
Rémy. The Objective Caml system. Software and documentation available on theWeb, {http://pauillac.inria.fr/ocaml/}, 1996.
[26] Steven Bird, Yi Chen, Susan Davidson, Haejoong Lee, and Yifeng Zheng. Extending XPath to support linguistic queries. In Informal Proceedings of the Workshop
on Programming Language Technologies for XML PLAN-X 2005, pages 35 – 46,
2005.
[27] A. Halevy, Z. Ives, P. Mork, and I. Tatarinov. Piazza: Data management infrastructure for semantic web applications, 2003.
[28] GNU compiler collection. http://gcc.gnu.org/.
[29] Bill Lindsey and James Clark. XT version 20051206. http://www.blnz.com/xt/,
Dec 2005.
[30] The Apache Software Foundation. Xalan c++ 1.10. http://xml.apache.org/
xalan-c/, Feb 2004.
[31] Haruo Hosoya, Jérôme Vouillon, and Benjamin C. Pierce. Regular expression
types for XML. ACM SIGPLAN Notices, 35(9):11–22, 2000.
[32] Dan Suciu. Typecheking for semistructured data, 2001.
[33] Nils Klarlund, Thomas Schwentick, and Dan Suciu. Xml: Model, schemas, types,
logics, and queries. In Logics for Emerging Applications of Databases, pages 1–41,
2003.
[34] Morten Biehl Christiansen, Nils Klarlund, and Theis Rauhe. Algorithms for
guided tree automata, 1997.

56