Indexing techniques for processing generalized XML documents

The Extensible Markup Language (XML) data model has recently gained huge popularity because of its ability to represent a wide variety of structured (relational) and semi-structured (document) data. Several query languages have been proposed for the XML model, the most-widely used one is the XQuery. An important component of an XQuery is its XPath expression which retrieves a set of XML documents to be manipulated by the associated XQuery. An XPath expression can be of several types, among which are the containment queries. Traditional research of processing containment queries has concentrated on data retrieval from independent XML documents; not much research has been directed towards interlinked XML documents. This paper reviews this area of research and shows the adequacy and correctness of one of the reviewed algorithms when applied to independent XML documents. However, the direct application of this algorithm to process queries against interlinked XML documents is shown to generate incorrect results. To remedy such a situation, two new algorithms and the associated indexing structures are developed and shown to perform correctly in processing both independent and/or inter-linked XML documents. In addition, one of the new algorithms is shown to minimize the storage requirement of the intermediate lists generated throughout its execution and therefore improving further the algorithm's space and time performance.