论文部分内容阅读
随着近年来Web Service的蓬勃发展, XML ( extensible markup language)越来越多地活跃在数据交换和存储领域,用XML表示的半结构化数据得到越来越普遍的应用,XML已经成为Internet上信息表示和交换的重要标准。然而,由于一方面XML数据大幅增长,另一方面XML数据存在着非常大的冗余,如何有效的存储和查询大规模的XML数据成为当前研究的一个热点问题。当处理大数据量XML数据时,首要的是为之建立行之有效的磁盘存储结构。为此,本文首先提出了一种基于F&B索引的XML数据的磁盘压缩存储结构LDF&B,其优点在于:一方面,LDF&B摒除了传统存储方法中相同的值信息重复存储带来大量冗余的问题;另一方面,该结构引入的同带索引与反向索引结构将具有相同性质的节点聚集在一起,使得可以快速的定位到满足条件的节点集,很好的支持了其上的查询处理。其次,我们给出了基于LDF&B存储结构的一系列查询处理算法。第一、对于含值的查询,在过滤掉大量的不满足条件的中间结果的同时,减少了大量中间结果的匹配操作,高效的实现了Disk-based F&B[1]中无法处理的含值的查询,并且相对于正向先匹配结构信息后判断值信息的算法,查询的效率也有着显著的提高。第二、对于分支查询的处理,相比于Join的方法,所需遍历的节点数量得到很大程度的降低,并且无须保存中间结果即可得到最终结果集,内存开销极小,使得分支查询的处理效率明显提高。第三、对于单路径查询的处理,本文提出的方法可以迅速定位出匹配查询条件的结点,减少了需遍历的节点数量,提高了查询处理效率。最后,我们对LDF&B上的查询处理算法进行优化,借助LDF&B中的辅助信息,寻找查询的优化执行顺序,进一步的提高了单路径查询处理的效率。理论分析与实验结果均说明本文的算法具有较好的伸缩性与很高的查询执行效率。