Reconstructing XML Subtrees from Relational Storage of XML documents

Numerous researchers have proposed to use relational databases to store and query XML documents. One important component of such systems is the XML subtree reconstruction, which reconstructs the subtrees rooted at the matching nodes of an XML query and returns them to the user as the query result. Existing reconstruction algorithms either do not support recursive XML view schema, or require expensive nested queries or joins of multiple relations. In this paper, we propose an efficient XML subtree reconstruction algorithm, Reconstruct, which overcomes these limitations and uses an efficient stack-based structural join algorithm to recover all the parent-child relationships between elements. One salient advantage of this algorithm is that it employs the inlining feature of the inlining-based storage of XML documents, which is known as one of the best relational XML storage schemes. Both our algorithmic analysis and experimental study show that Reconstruct is efficient and scalable.