xml数据的编码方案与结构连接算法研究

《xml数据的编码方案与结构连接算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、华中科技大学硕士学位论文XML数据的编码方案与结构连接算法研究姓名：黄渊申请学位级别：硕士专业：计算机应用技术指导教师：杨薇薇20060511华中科技大学硕士学位论文摘要XML，又称可扩展标记语言，已经实质上成为了Internet上的数据传输标准。由于使用的越来越广泛，如何对这些数据进行有效的存储、查询，已成为当今学术界研究的一个热门课题。而结构连接方法无疑是XML数据查询的核心操作。为了有效的支持结构查询，目前已经提出了XML数据的各种编码方案。全局区间编码方案能够很好的支持结点结构关系的判断，因而在结构连接中被普遍

2、使用。虽然如此，但采用全局区间编码方案的XML文档的更新效率却很差，需要对整个文档进行重新编码。相对的，采用局部区间编码可以很好的解决文档的更新问题，但它不能直接支持对结点的结构关系的判断，无法被结构连接算法所采用。作为两者的结合，前缀编码既能支持结构连接，又有较好的文档更新效率，是一种有前途的编码方案。为了进一步提高文档更新效率，对经典的前缀编码Dewey编码进行了改进，得出了扩展的Dewey编码Ext-Dewey。采用Ext-Dewey编码的XML文档树在进行更新操作时，完全不需要对树中其它结点进行重新编码，效率很

3、高。更进一步，设计了基于Ext-Dewey编码的结构连接算法，并且在匹配父－子关系的算法中，不使用经典算法中常用的栈来保存中间结果，减少了空间开销。针对区间编码，实现了一种优化算法，其不需要使用任何索引结构，就能在某些情况下避免不必要的连接操作，提高算法效率。最后，将此优化策略用于基于Ext-Dewey编码的连接算法上。实验数据表明，基于Ext-Dewey编码的连接算法是正确的，并且优化后的算法较未优化前性能有普遍的提高。关键词：可扩展标记语言，编码方案，结构连接，优化策略I华中科技大学硕士学位论文AbstractXM

4、L,ExtensibleMarkupLanguage,hasactuallybecomethedatatransmissionstandardintheInternet.Andhowtoeffectivelystoreandquerythesedataisahottopicofresearchinacademianow.StructuralJoinmethodisthecoreoperationinqueryingXMLdata.Toeffectivelysupportstructuralquery,variousen

5、codingschemeshavebeenproposed.Globalregionencodingschemeisconvenienttojudgethestructuralrelationship,andwaswidelyusedinstructuraljoinalgorithms.Nevertheless,theefficiencyofXMLdocumentwhichisencodedbyGlobalregionencodingschemeisupdatedpoor.Relatively,canmakeuseof

6、localregionencodingschemetosolvedocuments’updating,butitdoesnotdirectlysupportthestructuralrelationshipofnodes’judgment,andhencecannotbeusedbystructuraljoinalgorithms.Asacombinationofthetwo,prefixencodingschemewhichsupporttojudgenodes’structuralrelationshipandha

7、sgoodfileupdatingefficiencyisapromisingencodingscheme.Tofurtherenhancetheefficiencyofdocuments’updating,baseontheclassicDeweyencodingscheme,providesanexpansionoftheDeweyencodingschemenamedExt-Dewey.WhenupdatingadocumentencodedbyExt-Dewey,noothernodesinthetreenee

8、dbere-encoded.Furthermore,designedthestructuraljoinalgorithmbasedonExt-Deweyencodingscheme,andinthealgorithmmatchingfather-childrelationship,thenon-useofstackwhichisc