面向更新的扩展Dewey编码

Update-Oriented Extending Dewey Labeling Scheme

依赖于特定编码方案的高效查询处理算法是有效获取信息的必要手段,扩展Dewey编码以其祖先名称可知性的特点,在处理结构化查询时可显著减少需要扫描的元素数量,加快查询处理的速度。针对扩展Dewey编码不支持更新和依赖于DTD的缺陷,提出一种支持插入操作的动态扩展Dewey编码(DED),可避免执行插入操作时对已有结点的重新编码操作;提出一种支持DTD更新操作的动态有限状态转换器(DFST),可避免由于导出DTD的变化所导致的编码失效问题。最后通过实验验证了该编码的有效性。

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.