基于扩展区间编码的小枝模式查询算法

《基于扩展区间编码的小枝模式查询算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：TP392密级：公开UDC：单位代码：10424学位论文基于扩展区间编码的小枝模式查询算法孙清涛申请学位级别：硕士学位专业名称：计算机软件与理论指导教师姓名：路燕职称：副教授山东科技大学二零一二年六月论文题目：基于扩展区间编码的小枝模式查询算法作者姓名：孙清涛入学时间：2009年9月专业名称：计算机软件与理论研究方向：数据库系统指导教师：路燕职称：副教授论文提交日期：2012年6月论文答辩日期：2012年6月授予学位日期：TwigPatternQueryAlgorithmsbasedonExtendedRegionEncodingADissertat

2、ionsubmittedinfulfillmentoftherequirementsofthedegreeofMASTEROFPHILOSOPHYfromShandongUniversityofScienceandTechnologybySunQingtaoSupervisor:AssociateProfessorLuYanCollegeofInformationScienceandEngineeringJune2012声明本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所公认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于其它任何学术机关作鉴定。硕

3、士生签名：日期：AFFIRMATIONIdeclarethatthisdissertation,submittedinfulfillmentoftherequirementsfortheawardofMasterofPhilosophyinShandongUniversityofScienceandTechnology,iswhollymyownworkunlessreferencedofacknowledge.Thedocumenthasnotbeensubmittedforqualificationatanyotheracademicinstitute.Signature:Da

4、te:山东科技大学硕士学位论文摘要摘要随着XML数据库的蓬勃发展，XML文档存储、索引、查询的研究成为热点。由于XML数据具有分支结构多，数据冗长的特点，这给数据的存储和查询带来了极大的不便。因此，如何对XML文档进行有效的存储和查询，已经成为XML数据库研究的核心问题。为了有效的存储和查询XML数据，研究者提出了许多针对XML文档的编码方案。这些编码方案是通过对XML文档树中的每一个结点赋予唯一编码的方式，来直接判断出结点之间的结构关系，避免对XML文档树的完整遍历。这些编码方案在一定程度上提高了XML数据的查询效率，但它们在存储空间的利用率，结点更新效率，查询速度等方面仍然存在

5、着许多不足。本文在对现有XML文档编码方案进行深入分析比较的基础上，提出了一种支持XML数据更新的扩展区间编码方案。使用该编码方案，可以高效快速的检测出XML文档树中任意两个结点间的双亲/孩子关系，祖先/后裔关系，文档位置关系。同时，该编码减少了结点更新时，重新编码的结点数量，有效地支持XML文档更新。在XML数据库中，小枝模式查询是XML查询处理的核心操作。Twig查询处理的效率很大程度上决定了整个XML查询的处理效率。基于本文提出的PEN编码方案，提出了一种新的小枝模式匹配算法TwigELM。通过该算法可以有效避免中间匹配结果的存取，同时能够更好的处理Twig查询分支中包含父子关

6、系的查询。通过实验，对比了TwigELM算法与经典的Twig查询算法TwigStack，实验表明TwigELM算法在查询效率方面具有更好的性能。关键词：XML，扩展区间编码，小枝模式查询，结构连接山东科技大学硕士学位论文AbstractAbstractWithXMLdatabaseofboomingdevelopment,XMLdocumentstorage,index,inquiresbecamethefocusofresearch.BecausetheXMLdataismorebranchingstructure,thecharacteristicsofthelengthyda

7、ta,tothedatastorageandquerywithgreatinconvenience.Therefore,howtoefficientlystoreandquerytheXMLdocumenthasbecomethecoreissueoftheXMLdatabaseresearch.InordertoefficientlystoreandqueryXMLdata,theresearchersproposeacodingschemeforXML