Processing independent and inter-linked documents in XML databases

The extensible markup language (XML) model has recently gained huge popularity because of its ability to represent a wide variety of structured and semi-structured data. Several query languages have been proposed for the XML data model, the most-widely known is XQuery. Traditional XML query processing research has concentrated on data retrieval from independent XML documents and on the associate structures. In this paper, we review these algorithms and structures and show their superiority when processing independent XML documents. However, the direct application of these algorithms to process queries against interlinked XML documents is shown to generate incorrect results. A new algorithm and the associate structures suitable to process queries against both independent and inter-linked XML data are developed and shown to generate correct results.