eCite Digital Repository

DDE: from dewey to a fully dynamic XML labeling scheme


Xu, L and Ling, TK and Wu, H and Bao, Z, DDE: from dewey to a fully dynamic XML labeling scheme, Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, 29 June - 2 July 2009, Rhode Island, USA, pp. 719-730. ISBN 978-1-60558-551-2 (2009) [Refereed Conference Paper]

Copyright Statement

Copyright 2009 ACM

DOI: doi:10.1145/1559845.1559921


Labeling schemes lie at the core of query processing for many XML database management systems. Designing la- beling schemes for dynamic XML documents is an impor- tant problem that has received a lot of research attention. Existing dynamic labeling schemes, however, often sacri¯ce query performance and introduce additional labeling cost to facilitate arbitrary updates even when the documents actu- ally seldom get updated. Since the line between static and dynamic XML documents is often blurred in practice, we believe it is important to design a labeling scheme that is compact and e±cient regardless of whether the documents are frequently updated or not. In this paper, we propose a novel labeling scheme called DDE (for Dynamic DEwey) which is tailored for both static and dynamic XML docu- ments. For static documents, the labels of DDE are the same as those of dewey which yield compact size and high query performance. When updates take place, DDE can completely avoid re-labeling and its label quality is most re- silient to the number and order of insertions compared to the existing approaches. In addition, we introduce Com- pact DDE (CDDE) which is designed to optimize the per- formance of DDE for insertions. Both DDE and CDDE can be incorporated into existing systems and applications that are based on dewey labeling scheme with minimum e®orts. Experiment results demonstrate the bene¯ts of our proposed labeling schemes over the previous approaches.

Item Details

Item Type:Refereed Conference Paper
Keywords:dynamic data encoding, labeling scheme
Research Division:Information and Computing Sciences
Research Group:Data management and data science
Research Field:Data management and data science not elsewhere classified
Objective Division:Information and Communication Services
Objective Group:Information systems, technologies and services
Objective Field:Information systems, technologies and services not elsewhere classified
UTAS Author:Bao, Z (Dr Zhifeng Bao)
ID Code:92212
Year Published:2009
Web of Science® Times Cited:32
Deposited By:Information and Communication Technology
Deposited On:2014-06-10
Last Modified:2015-02-12

Repository Staff Only: item control page