关键词: 可扩展标示语言, 扩展Dewey, 更新

Abstract: 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 opera-tions 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.

Key words: extensible markup language (XML), extended Dewey (ED), update