Structural Function Inlining Technique
for Structurally Recursive XML Queries*
Chang-Won Park t
Jun-Ki Min t
Chin-Wan Chung t
tInformation Technology Lab., LG Electronics Institute of Technology
tDivision of Computer Science, Korea Advanced Institute of Science and Technology, {jkmin,chungcw}@islab.kaist.
Abstract 1 Introduction
Structurally recursive XML queries are an im-
portant query class that follows the structure
of XML data. At present, it is difficult for
XQuery to type and optimize structurally re-
cursive queries because of polymorphic recur-
sive functions involved in the queries.
In this paper, we propose a new technique
called structural function inlining which in-
lines recursive functions used in a query by
making good use of available type informa-
tion. Based on the technique, we develop a
new approach to typing and optimizing struc-
turally recursive queries. The new approach
yields a more precise result type for a query.
Furthermore, it produces an optimal algebraic
expression for the query with respect to the
type information. When a structurally recur-
sive query is applied to non-recursive XML
data, our approach translates the query into
a finitely nested iterations.
We conducted several experiments with com-
monly used real-life and synthetic datasets.
The experimental results show that the num-
ber of node lookups by our approach is on
the average 3.7 times and up to 279.8 times
smaller than that by the XQuery core's cur-
rent approach in evaluating structurally recur-
sive queries.
*This work was supported by
the Brain
Korea 21 Project.
t This work was performed while the author was with KAIST.
Permission to copy without fee all or part of this material is
granted provided that the copies are not made or distributed for
direct commercial advantage, the VLDB copyright notice and
the title of the publication and its date appear, and notice is
given that copying is by permission of the Very Large Data Base
Endowment. To copy otherwise, or to republish, requires a fee
and/or special permission from the Endowment.
Proceedings of the 28th VLDB Conference,
Hong Kong, China, 2002
XML is the standard language for representing data on
the Web. Because of the growing popularity of XML,
it is crucial to have a flexible query language capable of
querying diverse XML data sources. In this regard, a
standard query language called XQuery [2] is currently
being developed, which is a strongly typed functional
language in which a query is a typed expression. An
important feature of XQuery is its support for recur-
sive queries that follow the structure of XML data.
We refer to this important query class as structurally
recursive queries.
By a structurally recursive query, we mean a query
that involves a recursive navigation ("//")[2], a re-
cursive filtering [2], and function calls to user-defined
structurally recursive functions [3, 11]. Several use
cases [5] and the requirements [4] of XQuery indicate
that structurally recursive queries are frequently used,
and also meet various requirements such as abilities to
query without schema knowledge, to operate on hier-
archy, to transform input structures and create new
structures, and to preserve the relative hierarchy and
sequence of input structures in query results. For ex-
ample, we often write
to retrieve
ments regardless of the structure of data and the loca-
tions of title elements in the data.
In connection to the whole XQuery language, the
XQuery core [10, 11] (a core subset of XQuery) has
been established as well. Every XQuery expression
is mapped to an expression in the XQuery core, re-
vealing the semantics of the original expression. And
then, the mapped expression is typed and optimized
by means of the XQuery core's typing rules and equiv-
alence rules. Thus, the XQuery core serves as an al-
gebra for XQuery, and it is crucial for the XQuery
core to map, type, and optimize structurally recur-
sive queries properly. However, the XQuery core is
still incomplete with regard to structurally recursive
queries [10]. (Section 2 reviews how the XQuery core
types and optimizes a structurally recursive query in
detail.) Several related issues have been raised by the

Get Proceedings 2002 VLDB Conference now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.