On Supporting Structure-Agnostic Queries for XML
Won Kim, Cyber Database Solutions, Austin, Texas, USA
Wol Young Lee and Hwan Seung Yong,
Department of Computer Science and Engineering, Ewha Women’s University,
Seoul, Korea
|
 |
COLUMN
PDF Version |
Abstract
XML has rapidly emerged as the standard for the interchange of data
in numerous application areas. Many software vendors now offer XML
servers to store and retrieve XML documents. To allow for content-based
queries, query languages have also been designed. The query languages
require the users to know the structure of the XML documents and specify
search conditions on the structure. This navigational access to XML
documents is a natural consequence of the hierarchical structure of
XML. However, it is also desirable to allow the users to formulate
structure-agnostic queries against XML documents, to complement the
current navigation-based queries. We have developed a query processor
to evaluate structure-agnostic XML queries. In this article, we motivate
the need for structure-agnostic, that is, non-navigational, queries
against XML, and offer it as a worthy subject of further research and
development.
1 INTRODUCTION
XML [XML00] provides simple yet flexible ways to represent the structure
and contents of arbitrary documents. An XML document is constructed
based on a few simple rules. The core feature of an XML document is
the “element”. An element has a start tag (element name),
data value, and an end tag. Further, an element can have attributes,
can have children elements, and can be empty. The fact that an element
can have children elements is of course what allows it to express hierarchical
structures of arbitrary documents. The simplicity and flexibility of
XML have made it possible for XML to be adopted as the basis of data
interchange standards in a wide variety of application areas, including
electronic business (ebXML, X12, Rosetta Net), financial services (FIXML,
FPML), molecular biology (bioML, SBML, CellML, RNAML), chemistry (CML),
multimedia (SMIL, SVG, MPEG-7), scientific research (RIXML), metadata
management (XMI), web services (WSDL, UDDI), data mining (PMML), etc.
Many XML servers are currently on the market. Some store XML documents
in XML-optimized file systems, while others use relational databases
(by “shredding” XML documents into rows and columns in
tables). XML database servers on the market include Oracle XML DB [Oracle].
DB2 XML Extender [IBM], SQL server 2000 [Hhowlett and Jennings], BEA
Systems, Actuate/Nimble, Poet, BlueStone, eXcelon, IPEDO, XAware, etc.
It is of course necessary for the users to be able to issue “content-based” queries
against XML documents, that is, queries in which search conditions
are specified as predicates (e.g., director = “Luc Besson”,
to retrieve movies directed by “Luc Besson” from a database
of “movie” XML documents).
There have been many proposals for a query language for semi-structured
data in general, and XML in particular. These include Lorel [Abiteboul,
et al], XML-QL [Deutsch et al]. X-Path [Xpath], XSL [XSL], YATL,
Quilt, and XQuery [XQuery]. These query languages require the users
to know
the structure of XML documents, including all the element and attribute
names, data types of the data values, and the hierarchical structure
of the elements. Since a search condition needs to involve an element/attribute
name, which appears somewhere in the hierarchical structure of an
XML document, these query languages force the users to specify the
navigational
access paths to the elements/attributes that are involved in search
conditions. Insofar as XML gives rise to hierarchical structure,
and navigational access to selected parts of an XML document is a natural
access pattern, the navigational content-based query languages clearly
make sense. However, we believe that structure-agnostic, that is,
non-navigational,
content-based query languages for XML, and general semi-structured
data, are also desirable. In other words, we believe that both navigational
and non-navigational query languages are necessary to support all
query needs against XML databases.
2 RATIONALE
A brief review of the history of generational shifts in database systems
can provide a helpful insight to understand the necessity of both
types of query facility for XML. The transition from hierarchical
and network database systems to relational database systems took
place in the 1980s. The hierarchical and network models of data,
in which a record contains physical pointers to other records, made
sense for applications that modeled data that naturally forms hierarchical
structure, such as the bill of materials. Applications had to access
the records by navigation, going from one record to the next records
by following the pointers embedded in the first record. However,
the use of physical pointers was problematic, since the pointers
had to be changed in all the records if the records to which they
pointed changed their physical locations. (Further, if the data structures
used to store the database changed, all the application logic that
made explicit use of the knowledge of the data structures had to
be changed.) The relational model of data explicitly excludes the
use of pointers, both logical and physical, and instead has a record
in one table to be “linked” dynamically to a record in
another table if the two records have a common value in some of the
user-specified fields. This dynamic “linking” of records
in two or more tables is called join. The relational model of data
offers a high degree of “data independence” and makes “ad
hoc content-based” queries possible. “ad hoc content-based” queries
mean queries in which the users only specify the search conditions
on selected columns (and output columns), but not how the data is
to be located and accessed (e.g., navigational paths) or how the
query is to be processed (e.g., using specific access methods such
as indexes or hashing or sorting). The onus of accessing the data
and processing the queries falls entirely on the database system.
To support ad hoc queries, relational database systems had to develop
the query optimizer and query processor modules. The query optimizer
computes the estimated costs of all feasible plans of evaluating
a given query, examining different orderings of tables when joining
them and all the access methods at its disposal. The least-cost plan
(which typically consists of a sequence of query-processing steps)
selected by the query optimzier is passed to the query processor,
which then executes each step of the plan. However, relational database
systems make modeling and querying of data that is naturally hierarchical
in structure awkward and inefficient. The object-relational model
of data, which combines the relational model of data and an object-oriented
model of data, reintroduced the pointer concept of hierarchical and
network database systems in the form of object identifiers. An object
identifier is a logical pointer, not a physical pointer, and makes
it possible to naturally model and access hierarchical structures
of data. Object-relational database systems represent a combination
of the best of both the hierarchical database systems and relational
database systems by allowing both “ad hoc” content-based
queries and navigational queries.
XML has come about completely outside
the database systems domain. The hierarchical structure of elements
in XML certainly called for
query languages that would support navigational access to different
parts of XML documents at different levels of hierarchy. However,
just as the users of database systems have discovered over the past
30 years,
we believe that users of XML databases will benefit significantly
from structure-agnostic, that is, non-navigational, content-based
queries.
Simply put, a good segment of XML users would want to specify in
their queries only the search conditions (and output elements), without
having
to know and specify the detailed hierarchical structure of the XML
documents or have to give hints for efficiently processing the queries.
3 ILLUSTRATIONS
To make the concept concrete, suppose that we have XML documents on
movies, represented as in Figure 1a. If we are to search for movie
titles whose genre is ‘action’, release year is ‘1994’,
and whose stars include ‘Jean Reno’, we would like to
be able to state the search conditions simply as
genre = “action” and year = “1994” and actor
= “Jean Reno”
regardless of the structure of the XML documents. Then a non-navigational
content-based query (in Xquery) that includes the above search conditions
would look something like
for $t in doc()//title
“action” and year = “1994” and
actor = “Jean
Reno”
return $t
The same query, when expressed in navigational style, would look like
for $m in doc ()//movie
where $m/genre[text() = “action”] and
$m/year[text() = “1994”]
and $m/actor
[text() = “Jean Reno”]
return <title>$m/title/text()</title>
Figure 1a. an XML document about a movie (using elements)
Of course, to be able to formulate non-navigational content-based queries
against XML documents, the users would need to know at least the names
of the elements/attributes and data types for the data values. Just
as was the case with relational database systems, the onus of computing
all possible paths along the XML documents’ hierarchical structure
would fall on the query optimizer and query processor of the XML server.
There are a few reasons that we believe that it is imperative that
XML users be able to formulate non-navigational content-based queries,
besides the obvious observation that it can be tedious to have to specify
the navigational paths in a query. First, the flexibility of XML allows
users to specify the same contents in a number of different ways, and
as such it becomes problematic for the users to have to content with
all the disparate ways in which contents may be represented in XML.
At the risk of belaboring the point, let us consider Figures 1b and
1c. These figures show how the same simple contents, represented in
Figure 1a, can be represented in different ways, using element hierarchies,
and attributes. (There are various additional ways.) The same structure-agnostic
query shown previously would work for each of these alternate representations.
The navigational query for Figure 1b would look like
for $m in doc ()//movie
where $m//genre[text() = “action”]
and $m//year[text() = “1994”] and
$m//actor [text() = “Jean Reno”]
return <title>$m//title/text()</title>
(* We note that the above query would also work as navigational query
for Figure 1a. *)
Figure 1b. The same XML document about a movie (using an element hierarchy)
For Figure 1c, the navigational query would look like
for $m in doc ()//movie
where $m/*[@genre = “action”] and $m/*[@year = “1994”]
and
$m/*[actor = “Jean Reno”]
return <title>$m/*/@title</title>
Figure 1c. the same XML document about a movie (using attributes)
Further, the same contents may be organized in a number of different
hierarchical structures. Figures 2a and 2b represent the XML document
of Figures 1 using hierarchical structures. Again the same structure-agnostic
query shown previously would work for each of these alternate representations.
However, the navigational query for Figure 2a would look like
for $y in doc ()//year
where $y[text() = “1994”] // genre[text()
= “action”]
// actor[text()= “Jean Reno”]
return $y//title/text()</title>
Figure 2a. the same XML document about a movie (using an element
hierarchy) For Figure 2b, the navigational query would look like
for $g in doc ()//genre
where $g[@* = “action”] // year[*= “1994”]
// actor[text() = “Jean Reno”]
return <title>$g//title/text()</title>
Figure 2b. The same XML document about a movie
(using an element hierarchy and attributes)
4 CONCLUDING REMARKS
In this article, we discussed why structure-agnostic or non-navigational content-based
query facilities will complement the current navigation-based query languages
for XML. To make the discussion concrete, we showed some examples of how many
different ways in which the same contents may be represented in XML. It is
obvious that once we consider “similar” contents, rather than the
exact same contents, the problem becomes compounded. To retrieve “similar” XML
documents that satisfy certain search conditions, one needs to consider non-identical
XML documents that nonetheless contain some common elements and attributes,
in a wide variety of hierarchical structures. The problem becomes even more
difficult in a distributed, multiple-database environment, including the Web.
Although XML is being touted as “the” standard for data interchange,
it will be used as the basis of data interchange standards for a wide variety
of different application areas, each with its own vocabulary and data semantics.
In other words, there will not be a single universal XML data interchange standard.
As such, even if different segments of the XML users adopt particular data
interchange standards, the need to integrate XML documents across multiple
segments will drive the need for non-navational content-based query facilities.
We have designed and implemented a non-navigational content-based query language
and a query processor for the language. We will report details of our implementation
and experiments in a forthcoming paper. Meanwhile, we believe that non-navigational
query support for XML, in particular, query optimization and query processing,
is an important area for further research, and would like to encourage the
XML data management research community to follow up on our research.
REFERENCES
[XSL] S. Adler, A. Berglund, J. Caruso, S. Deach, T. Graham, P. Grosso, E.
Gutentag, A. Milowski, S. Parnell, J. Richman, and S. Zilles: Extensible Stylesheet
Language (XSL) Version 1.0, W3C Proposed Recommendation Aug. 2001
[Abit1997] S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. L. Wiener, “The
Lorel Query Language for Semistructured Data”, International Journal
on Digital Libraries, Apr. 1997
[Oracle] S. Banerjee, Oracle XML DB, Oracle Corporation Technical White Paper.
release 9.2, Jan. 2002
[XQuery] S. Boag, D. Chamberlin, M. F. Fernandez, D. Florescu, J. Robie, J.
Siméon, XQuery 1.0: An XML Query Language, W3C Working Draft 16 Aug.
2002
[Deut1998] A. Deutsch, M. Fernandez, D. Florescu, A. Levy, and D. Suciu, XML-QL:
A query language for XML, Submitted to the W3C 19 Aug. 1998
[Howl2002] S. Howlett and D. Jennings: “SQL Server 2000 and XML: Developing
XML-enabled data solutions for the web”, MSDN magazine, Jan. 2002
[IBM] IBM Corporation, DB2 XML Extender, IBM Corporation, 2000
[XML] W3C Consortium, XML1.0 (Second Edition), W3C Recommendation 06 Oct. 2000,
available at http://www.w3.org/TR/REC-xml
[XPath] W3C Consortium, XML Path Language (XPath) Version 1.0, W3C Recommendation
16 Nov. 1999
About the authors
|
 |
Won Kim is President
and CEO of Cyber Database Solutions (http://www.cyberdb.com)
and MaxScan (www.maxscan.com) in Austin, Texas, USA. He is also
Dean of Ewha Institute of Science and Technology, Ewha Women's
University, Seoul. Korea. He is Editor-in-Chief of ACM Transactions
on Internet Technology (http://www.acm.org/toit),
and Chair of ACM Special Interest Group on Knowledge Discovery
and Data Mining (http://www.acm.org/sigkdd).
He is the recipient of the ACM 2001 Distinguished Service Award. |
|
|
Wol-Young Lee is a Ph.D. candidate
in the Department of Computer Science and Engineering at Ewha Women’s
University in Seoul, Korea. Her research interests include programming
languages, XML, and database systems). Her email is wylee at ewha.ac.kr.
|
 |
|
Hwan-Seung Yong is associate professor with the Department
of Computer Science and Engineering at Ewha Women’s University
in Seoul, Korea. His research interests include multimedia database
systems, data mining and bioinformatics, Internet computing.
He received a Ph.D. degree in computer engineering, Seoul National
University. His email is hsyong at ewha.ac.kr.
|
Cite this column as follows: Won Kim, Wol Young Lee, Hwan Seung Yong: “On
Supporting Structure-Agnostic Queries for XML”, in Journal
of Object Technology, vol. 3, no. 7, July-August 2004, pp. 27-35. http://www.jot.fm/issues/issue_2004_07/column3
|
