基于区间编码的xml索引研究及优化

《基于区间编码的xml索引研究及优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、南开大学硕士学位论文基于区间编码的XML索引研究及优化姓名：肖璞申请学位级别：硕士专业：计算机软件与理论指导教师：李耀国20090401摘要XML作为网络数据交换和信息集成的工具，以其自描述性、跨平台交换性等特点，成为新一代的网络语言。互联网上越来越多的结构化或半结构化的数据采用XML格式存储和交换，随着XML数据量的不断增长，要求更有效的数据管理能力和更快、更精确的查询。因此，对XML数据的索引及其结构查询的研究显得日益重要。为了有效的支持XML查询，特别是结构查询，目前已有很多文献提出了XML数据

2、的各种编码方案。这些编码方案更多地是将关注点放在如何设计编码结构以改进索引空间，以及在进行结构查询时所花费的时间代价较小，而对于支持XML文档数据的更新问题则很少进行深入的探讨。如何既能改进XML索引的结构查询效率，又能降低文档更新的维护代价，这是本文研究的主要内容。本文基于区间编码的索引编码方案，提出了一种改进的优化方案，将从索引结构、结构连接查询和文档更新维护三个方面对该方案进行研究。本文的主要研究工作如下：(1)改进区间预留算法。针对该算法中人为预留区间存在一定的缺陷与不足，采用按照节点密度进行

3、区间分配，从而对索引空间进行有效合理地分配，提高其空间利用率。(2)在结构连接查询中，对参与连接的节点集进行先序排序，使其满足块间有序；在Stack．Tree算法的基础上利用分块有序的节点编码信息跳过那些无需参与连接的祖先或后代节点，从而快速完成结构连接。(3)对于XML文档更新算法引入假设检验方法进行决策分析。在数据更新时，通过判断当前的区间划分是否在可接受的范围内，来降低将来文档在更新时需要重新划分区间的机率，从而达到对区间的有效划分和利用，降低对XML文档的维护代价。最后，本文开发了原型系统对提

4、出的索引方案进行了一系列实验。实验结果表明基于区间编码的索引优化方案具有较好的性能。关键词：XML区间编码结构连接假设检验AbstractAsatoolofdataexchangeandinformationintegrationinnetwork，XMLhasbecomeanewgenerationofWeblanguageforitsfeaturesofself-descriptive，exchangeincross—platform，etc．Anincreasingnumberofstructu

5、redorsemi—structureddataarestoredandexchangedasXMLformatinInternet．WiththevolumeofXMLdataisgrowing，werequiremoreefficientdatamanagementcapabilitiesandfaster,moreprecisequeries．Therefore，thestudyofindexanditsstructurequeriesforXMLdataisincreasinglyimport

6、ant．Atpresent，manypapersproposedavarietyofencodingschemeforXMLdatainordertosupportXMLquerieseffectively,especiallystructurequeries．MostofthemfocusonhowtOdesigntheencodingstructuretOimprovetheindexencodingspaceandspendlesstimeinstructural-joinqueries．How

7、ever,thereareraregooddiscussesforsupportingupdatedXMLdocuments．HowtoimprovetheefficiencyofXMLstructurequeriesaswellasreducemaintenancecostsforupdatedXMLdocuments，whichisthemaincontentsofthispaper．Thispaperraisesanimprovedandoptimizedindexencodingschemeb

8、asedonregionencodingonthreeareas：indexstructure，structural-joinqueriesandmaintenanceforupdatedXMLdocuments．Themainresearchworkinthispaperisasfollows：(1)Improveregionreservealgorithms．Aimingatsomedefectsandshortcomingsofman-madere