Answering XPath Queries over Networks by Sending Minimal Views
by Keishi Tajima, Yoshiki Fukui
Abstract
When a client submits a set of XPath queries to a XML database on a
network, the set of answer sets sent back by the database may include
redundancy in two ways: some elements may appear in more than one
answer set, and some elements in some answer sets may be subelements
of other elements in other (or the same) answer sets. Even when a
client submits a single query, the answer can be self-redundant
because some elements may be subelements of other elements in that
answer. Therefore, sending those answers as they are is not optimal
with respect to communication costs. In this paper, we propose a
method of minimizing communication costs in XPath processing over
networks. Given a single or a set of queries, we compute a
minimal-size view set that can answer all the original queries. The
database sends this view set to the client, and the client produces
answers from it. We show algorithms for computing such a minimal view
set for given queries. This view set is optimal; it only includes
elements that appear in some of the final answers, and each element
appears only once.
XML, XPath, minimal view, query processing, query optimization, query
translation, network, communication cost, redundancy, duplication,
on-line database, digital library, proxy server
Published in Proc. of VLDB, pp.48-59, Aug. 2004, Toronto, Canada
Permission to make digital or hard copies of part or all of this
work for personal or classroom use is granted without fee provided
that copies are not made or distributed for profit or commercial
advantage and that copies bear this notice and the full citation on
the first page.
/ Fax: +81(Japan) 75-753-5978 / Office: Research Bldg. #7, room 404