"XTRACT: Learning Document Type Descriptors from XML Document Collections"
Abstract
XML is rapidly emerging as the new standard for data representation and
exchange on the Web. Unlike HTML, tags in XML documents describe the
semantics of the data and not how it is to be displayed. In addition, an
XML document can be accompanied by a Document Type Descriptor (DTD)
which plays the role of a schema for an XML data collection. DTDs contain valuable
information on the structure of documents and thus have a crucial role in
the efficient storage of XML data, as well as the effective formulation and
optimization of XML queries. Despite their importance, however, DTDs are not
mandatory, and it is frequently possible that documents in XML databases will
not have accompanying DTDs.
In this paper, we propose XTRACT, a novel system for inferring a DTD schema
for a database of XML documents. Since the DTD syntax incorporates the full
expressive power of regular expressions,
naive approaches typically fail to
produce concise and intuitive DTDs. Instead, the XTRACT inference algorithms
employ a sequence of sophisticated steps that involve: (1) finding patterns in
the input sequences and replacing them with regular expressions to generate
"general" candidate DTDs, (2) factoring candidate DTDs using adaptations of
algorithms from the logic optimization literature, and (3) applying the Minimum
Description Length (MDL) principle to find the best DTD
among the candidates.
The results of our experiments with real-life and synthetic DTDs demonstrate the
effectiveness of XTRACT's approach in inferring concise and semantically meaningful
DTD schemas for XML databases.
Copyright © 2003, Kluwer Academic Publishers. All rights reserved.