A Persistent Labelling Scheme for XML and tree Databases 1

With the growing importance of XML in data exchange, much research has been done in providing flexible query facilities to extract data from structured XML documents. Thereby, several path indexing, labelling and numbering scheme have been proposed. However, if XML data need to be updated frequently, most of these approaches will need to re-compute existing labels which is rather time consuming. The goal of the research reported in this paper is to design a persistent structural labelling scheme, namely a labelling scheme where labels encode ancestor-descendant relationships and sibling relationship between nodes but need not to be changed when the document is updated. Supported update operations are insertion of new sub-trees, deletion of existing sub-trees and modification of existing nodes.