文档介绍：: .
Data our algorithms are efficient
and scalable.
Ó 2006 Elsevier . All rights reserved.
Keywords: XML; Reconstruction; Algorithm; XML subtree reconstruction
1. Introduction
Recently, there has been extensive work in the development of XML storage and management systems.
Such systems fall into two broad categories: relational-based [11,15,29,34,23,26,5,25] and native
[28,19,16,36,37,2] XML databases. The former ones use relational databases and XML-to-Relational data
model mappings to store and query XML documents. The latter ones define a logical model for an XML doc-
ument – as opposed to the data in that document – and store and retrieve documents according to that model,
while it is usually not required to have any particular underlying physical storage model.
* Corresponding author. Tel.: +1 313 5776711; fax: +1 313 5776868.
E-mail addresses: ******@ (A. Chebotko), ******@ (M. Atay), ******@ (S. Lu), ******@
(F. Fotouhi).
0169-023X/$ - see front matter Ó 2006 Elsevier . All rights reserved.
doi:. A. Chebotko et al. / Data & Knowledge Engineering 62 (2007) 199–218
In these systems, the elements selected by an XML query are returned to an application in one of the fol-
lowing two modes [38]: (1) Select mode: the unique identifiers (IDs) of the selected elements are returned to the
application; and the application can extract the contents of these elements later if necessary, or (2) Reconstruct
mode: the XML subtrees, rooted at the selected elements, are extracted and reconstructed from the storage of
XML documents and returned to the application. Therefore, XML subtree reconstruction is one important
component of such systems and its performance has a great impact on the query response time.
While previ