Labeling and querying dynamic XML trees

Abstract

With the growing importance of XML in data exchange, much research tends to provide a compact labeling scheme and a flexible query facility to extract data from dynamic XML trees. In this paper, we first propose GRP, namely GRoup based Prefix labeling scheme. Compared to the previous labeling schemes, the total size of labels in GRP is much shorter. Experiment results with synthetic and real life data show that the size of labels with GRP is about 2%-10% of that with the previous labeling scheme. Based on GRP, we further propose GRJ (GRoup based structural Join), a structural join algorithm. GRJ is similar to the hash join algorithm in RDBMS and needs to scan the join data only twice. Furthermore, unlike other structural join algorithms, GRJ can perform efficiently without dependency on the join data sorted or indexed, for the data in the dynamic XML trees are usually unsorted. Finally our experiments show that GRJ is efficient in supporting structural joins on the context of dynamic XML trees. © Springer-Verlag Berlin Heidelberg 2004.