More and more information is being stored in XML documents. Quite often, an XML documents may have links that point to other documents (which may be considered as a directed edge between two nodes/documents). These links may point to a whole XML document or one or more fragments in XML documents. XLink and related standards such as XInclude and XPointer may be used to define the links. As an example, a personnel database may be used to store a collection of XML documents each of which represents an employee or a department. An employee document may have a manager link embedded therein that points to another employee document that represents a manager. Additional links may be embedded in an employee document. For example, besides the manager link, the former employee document may comprise another link, say department link, that points to a department document that represents a department.
Operations that involve traversing links may be performed on a collection of interlinked XML documents. An example of interesting operation may be a query that returns a listing of employee-name and manager-name pairs. The straightforward evaluation of this query may require iteration over all employee documents; for each employee-name found in each employee document, a manager link in the employee document may be traversed to retrieve a corresponding manager-name.
In many scenarios, the number of documents in such collections is very large—perhaps in terms of millions. It becomes inefficient (and in some cases infeasible) to operate on such a collection using a single computer or only a small set of computers. It is thus necessary to split the collection over multiple machines in smaller collections (i.e. partitions) to enable parallel concurrent processing.
A disadvantage of these approaches, however, is that XML documents interlinked may end up in different partitions. As a result, the cost of traversing links may be increased because of the performance degradation caused by excessive traversal of links across partition boundaries.
Therefore, a better mechanism, which would better support managing and partitioning large collection of interlinked XML documents, is needed.