D(k,l)-索引:一种自适应的XML数据索引

D(k,l)-Index: An Adaptive Structural Summary for XML Data

XML已成为网络上数据表示和交换的一种实际标准。为促进XML的数据和半结构化数据的查询,几种结构概要被提出。它们可以直接从数据中得出,并以索引的方式来估计在XML数据上的路径表达式。在本文中,综合几种索引提出新型数据结构D(k,l)索引。其参数k,l刻画了节点向上和向下的相似度。它考虑各个节点向上路径和向下路径的相似关系,因此它可以有效地支持路径表达式,尤其支持带分支路径表达式的查询,同时,它也可以根据查询情况的变化来动态地改变索引结构,使索引结构更适合当前的查询要求,实验表明我们的方法具有很好的效率和效果。

XML has become the de facto standard of data presentation and exchange on the Web and Internet. To facilitate queries over XML data or semistructrued data, various structural summaries have been proposed. And they are derived directly from the data and serve as indices for evaluating path expressions on XML data. In this paper,D(k, l)-index,a family of efficient approximate index structures is proposed in which data nodes are grouped according to their incoming paths of length up to k and outgoing paths of length up to l. D(k,l)-index fully exploit local similarity of XML data nodes on their upward and downward paths,so that it can be used to evaluate path expressions efficiently,especially for the branching path expressions. At the same time, D(k, l)-index is able to adjust its structure according to the current query load adaptively. In addition, we propose a method in order to adjust the index structure dynamically for a query workload. Preliminary experiments show that our method is very effective and efficient.