基于不完全约束XML查询处理关键技术的研究.doc

国内图书分类号：TP312 国际图书分类号：621.3 工学硕士学位论文 基于不完全约束的 XML 查询处理 关键技术研究  万方数据  硕 士 研 究 生 导 师 申请学位级别 学 科 、 专 业 所 在 单 位 授予学位单位  ： ： ： ： ： ：  李义国 郭景峰 教授 工学硕士 计算机应用技术 信息科学与工程学院 燕山大学 Classified Index: TP312 U.D.C.621.3 Dissertation for the Master Degree in Engineering KEY TECHNIQUES ON XML QUERY PROCESSING BASED ON PARTIALLY SPECIFIED  万方数据  Candidate: Supervisor: Academic Degree Applied for: Speciality: University:  Li Yiguo Prof. Guo Jingfeng Master of Engineering Computer Application Technology Yanshan University 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文《基于不完全约束的 XML 查询处理关键技术研究》，是本人在导师指导下，在燕山大学攻读硕士学位 期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外 不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的 个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人 承担。  作者签字：  日期：  年  月  日  燕山大学硕士学位论文使用授权书 《基于不完全约束的 XML 查询处理关键技术研究》系本人在燕山大学 攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归 燕山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。 本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向 有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权 燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文的 全部或部分内容。  必威体育官网网址□，在 本学位论文属于 不必威体育官网网址□。 (请在以上相应方框内打“√” )  年解密后适用本授权书。  作者签名： 导师签名：  日期： 日期：  年 年  月 月  日 日  万方数据 摘要 XML 自 1998 年由 W3C 提出之后，已经成为因特网上数据表示和数据 交换的标准，受到越来越多的关注。各行各业都采用 XML 来描述本领域的 信息。随着 XML 应用的不断扩展，XML 数据量日益膨胀，如何有效管理 XML 数据并提供高效的查询处理方法成为迫切需要解决的问题。根据查询 表达式含有结构信息的特点，已有的查询处理机制可分为结构化查询机制、 关键字查询机制和混合查询机制。本文工作针对已有混合查询处理机制存 在的问题展开研究，主要研究了以下内容： 首先，分析和总结了已有的 XML 查询方法，针对已有方法不能高效处 理包含“*”结点的 PSTP 查询的问题，提出一种从 PSTP 查询推断普通结 构化查询的方法，基于此，提出一种基于扩展 Dewey 编码的高效查询处理 算法 EDPS，可以在仅扫描一遍元素的情况下，处理任意形式的 PSTP 查询， 包括一般形式的 Twig 查询、不包含“*”结点的 PSTP 查询和包含“*”结 点的 PSTP 查询。 其次，本文利用 XML 文档的模式信息和文档中的路径信息，提出了基 于 DTD 模式的优化方法来去除无用的查询路径，用以降低 EDPS 算法的时 间复杂度。 最后，编程实现了 EDPS、TwigStack、TSGeneric、TJFast 和 pTwigStack 五种算法，并在不同的数据集上，通过比较扫描元素数量、运行时间以及 扩展性三个指标，对以上五种算法的查询性能进行了实验比较，验证了 EDPS 算法的高效性。 关键词 XML；查询处理；PSTP 查询；扩展 Dewey；Samepath 轴 万方数据 Abstract XML has become a de facto standard of data representation and exchange in the Internet and it has been accepted in many fields since it was put forward by W3C in 1998. All walks of life use XML to describe their information.