宗传霞

（烟台南山学院，山东龙口 265713）

0 引言

XML 文档中的关键词检索是以XML 元素为粒度来返回检索结果的，即在返回检索结果时，并不需要将整个文档返回给用户，而只需返回用户感兴趣且符合检索条件的元素集即可，该集合可以看作是原文档的一个片段。因此，XML文档中的关键词检索不但可以使得检索结果更为准确，也使得传输的数据量大大减小。基于父节点的XML 查询优化算法的目的就是返回用户在XML 文档中的最小子树根节点，从而查询出对应于最小子树根节点的最紧致片段。

在XML 查询优化算法中，典型算法主要分为基于索引的搜索算法、基于堆栈的算法和基于扫描的算法。

基于索引的搜索算法基本思想是将XML 数据保存到B+树结构，插入B+树的数据形式为(key，dewey)，这相当于将XML中的数据按照关键词(keyword)和关键词在XML 树中的节点Dewey码进行排序[1]。之后，借助于B+树结构以及Dewey 码的基本运算（大于、小于、子孙码、公共前缀等）计算最小子树根节点。但是，这种算法必须修改B+树结构来支持Dewey 码操作，实现比较复杂。基于堆栈的算法主要是利用栈来进行存储，操作起来相对简单。但是，这种算法空间复杂度很高[2]。基于扫描的算法在时间复杂度和空间复杂度方面都不是很理想[3]。相对来说，在这3种算法中，基于索引的搜索算法应用比其他两种算法广泛。

鉴于这种情况，改进XML 信息查询技术具有必要性和紧迫性，这是基于父节点的XML 查询优化算法研究的主要动力。本文以如何提高其数据信息的查询效率为目的，描述了一种既能够在保证查全率的同时又对其查准率有所提高的基于父节点的XML 查询优化算法。……