学位论文 > 优秀研究生学位论文题录展示

基于索引的XML小枝模式匹配问题的研究

作　者: 宋然
导　师: 洪晓光
学　校: 山东大学
专　业: 计算机软件与理论
关键词: XPath 区间编码 XML索引技术小枝模式查询
分类号: TP311.13
类　型: 硕士论文
年　份: 2011年
下　载: 23次
引　用: 0次
阅　读: 论文下载

内容摘要

Internet发展到至今已经完全渗入到人们生活工作的各个方面。作为半结构化语言XML已经成为一种最重要的数据载体,在Web服务、电子商务、数字图书馆等诸多网络等领域的数据描述标准。研究表明,当今国内外研究的重点集中在以下两点：如何有效查询和管理XM数据与如何方便用户从海量的XML数据中提取他们所需要的信息。因此,许多对XML数据查询的研究就由此出现了,从而使得XML数据查询成为XML数据管理领域的一个热点。本文从XML数据库系统角度出发,透彻分析了目前存在的XML文档树的小枝查询技术与面临的不足。通过研究与改进编码方案来快速的组织XML文档,并且根据XML查询的特性,本文提出了一种新的索引REI,这是一种有着简单的数据结构和严谨的逻辑结构的索引技术。同时,为了进一步提高查询的效率,本文的索引还利用了改进的区间编码方案来组织和引用XML数据。基于以上的研究,本文还对XML文档的查询做了细致研究。XML查询中的路径表达式可以表示为树状查询独立地描述查询要求。XML数据查询主要分为单路径和多分支路径查询。在这两种路径查询方面,XML查询都可表示成小枝模式查询,在XML数据库中找到所有出现的小枝模式是当前XML查询处理的核心操作。基于这个思想,本文提出了一种新的基于索引的查询模型。在借鉴已有相关算法的优点,摒弃其中诸多缺点的基础上,采用改进的区间编码快速判断结点之间的祖先-后裔或父-子关系,并利用索引REI,进一步设计了一种新的高效的算法RE-TWIG,该算法可以有效的减小查询中的复杂度和冗余,快速的得到目标结点。本文的主要工作和创新点有以下几个方面：1、研究了主流XML文档的结点编码方案,研究了小枝路径索引的分解方法与查询方式。根据本文查询算法的特点,采用改进的区间编码方式,以此快速的判断结点直接的逻辑关系。2、本文提出了一种索引REI来存储XML文档。对于任何XML索引,在设计与实现的过程中都要考虑到XML查询的基本特征,其中包括逻辑结构的保存以及基于结构信息快速判断结点间的关系,除了以上两点还必须做到一条：满足高效处理XML查询的请求。通过其与将经典索引进行的数据集对比实验的结果来看,对本文提出的索引完全符合这一要求。3、在前两点研究的基础上,提出、设计并实现了一种基于改进区间编码和REI索引的小枝模式查询算法。该算法包括目标结点筛选和小枝查询模式匹配两部分。并通过实验给予了性能验证。为了便于对以上研究点的理解,论文以一个XML文档树的例子为依据,举了一个通用查询实例,详细展示了算法运行的全部过程。本文对如何有效的建立XML数据库索引以及查询技术方面进行了深入的探索,为更好的解决此问题提供一种行之有效的思路和方法。本文的课题基础也是目前XML查询领域中应用比较广泛的技术,不但为如何更好的进行XML文档树编码和索引的设计提供了思路和方法,同时也为基于索引的小枝查询的研究提供了一定的帮助,这使本文课题研究既具有探索性的理论研究价值,也具有一定的应用价值和现实意义。

全文目录

摘要  10-12
ABSTRACT  12-14
第一章绪论  14-21
  1.1 课题研究背景  14-15
  1.2 XML小枝查询相关研究  15-19
    1.2.1 XML文档查询相关研究  15-16
    1.2.2 XML结构连接相关研究  16-18
    1.2.3 当前面临的问题  18-19
  1.3 研究内容和主要工作  19-20
  1.4 本文的组织结构  20-21
第二章基于编码的XML文档查询模型  21-31
  2.1 背景知识  21-25
    2.1.1 XML文档树结构  21-22
    2.1.2 XML DTD与Schema  22-23
    2.1.3 XML的查询语言XPath  23-25
  2.2 文档结点编码方案  25-27
    2.2.1 区间编码  25-27
    2.2.2 前缀编码  27
  2.3 XML小枝路径查询  27-30
    2.3.1 路径查询模式  27-28
    2.3.2 路径查询分解  28-29
    2.3.3 传统路径查询算法  29-30
  2.4 本章小结  30-31
第三章 XML文档索引REI的构建  31-41
  3.1 XML索引与分类  31-32
    3.1.1 结点记录类索引  31-32
    3.1.2 结构摘要类索引  32
  3.2 XML索引REI的数据结构  32-34
    3.2.1 结点签名Signature  32-33
    3.2.2 小枝类型与小枝类型集合  33-34
  3.3 REI索引表的逻辑结构  34-38
    3.3 1 小枝类型索引表  34-35
    3.3.2 小枝-根索引表与小枝-叶索引表  35-36
    3.3.3 签名-标签索引表  36-37
    3.3.4 XML索引应满足的因素  37-38
  3.4 索引效率的实验分析  38-40
    3.4.1 实验设定  38
    3.4.2 评价指标  38-39
    3.4.3 实验方案  39
    3.4.4 实验结果及分析  39-40
  3.5 本章小结  40-41
第四章基于REI索引的小枝模式查询研究  41-52
  4.1 引言  41
  4.2 相关问题  41-43
    4.2.1 相关算法的不足  41-42
    4.2.2 RE-TWIG的编码方式  42-43
  4.3 基于REI索引的小枝查询算法  43-48
    4.3.1 算法思想  43-44
    4.3.2 基于TWT的结点筛选算法  44-45
    4.3.3 基于区间编码的结点匹配算法  45-46
    4.3.4 算法实例说明  46-48
  4.4 实验部分  48-50
    4.4.1 实验设定  48
    4.4.2 实验方案  48-49
    4.4.3 实验结果  49-50
  4.5 小结  50-52
第五章总结和展望  52-54
  5.1 本文工作总结  52
  5.2 未来工作展望  52-54
参考文献  54-58
致谢  58-59
攻读学位期间发表的学术论文目录  59-60
在读期间参与科研项目情况  60-61
学位论文评阅及答辩情况表  61

基于索引的XML小枝模式匹配问题的研究

内容摘要

全文目录

相似论文