Update-Oriented Extending Dewey Labeling Scheme
Jingfeng Guo · Jisuanji kexue yu tansuo · 2010
Efficient query processing algorithms that depend on a special labeling scheme are indispensable for extracting desired information from XML data.The extended Dewey(ED) labeling scheme has the feature that for a certain element,all its ancestors' names can be derived from its labels,which greatly reduce the number of scanned elements.However,ED labeling scheme doesn't support update operation,and the encoding and decoding operations severely depend on a finite state transducer(FST) generated from the document type definition(DTD) schema,which makes it infeasible in the case where DTD is changed.This paper proposes a fully dynamic extended Dewey(DED) labeling scheme that can completely avoid the re-labeling operation when inserting new node,and also gives a dynamic FST(DFST) to avoid the invalidation problem of existing labels when the FST needs to be changed.The experimental results show the effectiveness of the DED labeling scheme according to different metrics.