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

概率XML文档中Holistic Twig查询处理算法的研究与实现

作　者: 李亚文
导　师: 王国仁
学　校: 东北大学
专　业: 计算机应用技术
关键词: 概率XML文档概率Holistic Twig查询处理概率标签流过滤处理匹配
分类号: TP311.13
类　型: 硕士论文
年　份: 2009年
下　载: 8次
引　用: 0次
阅　读: 论文下载

内容摘要

传统的数据库管理只处理确定的信息,现在越来越多的数据库应用包含了非确定的信息。XML文档以其自描述性,跨平台交换性等特点,已经成为网络上数据存储和数据交换的标准。互联网上越来越多的结构化或者半结构化的数据采用了XML格式存储和交换,对XML数据的查询处理及其文档过滤的研究显得日益重要。最近,基于XML模型来描述不确定数据越来越引起了大家的兴趣。在概率XML文档的相关查询方法中,传统的查询处理方法是基于possible worlds的,其不足之处主要是,在查询的时候不得不遍历整个XML文档得到每一个possible world,然后在每个possible world上进行查询。鉴于Holistic Twig查询处理方法可以做到一遍扫描原文档即可得到查询处理的所有中间结果,本文改进了传统的Holistic Twig查询方法并将其运用到概率XML的查询中,利用概率标签流来进行查询匹配。应用于概率XML文档中的Holistic Twig算法被称为概率Holistic Twig查询处理算法。概率XML文档相对于普通XML文档,其数据的存在具有一定的概率,利用概率Holistic Twig算法在概率XML文档中进行查询处理的时候,需要对文档中的数据节点编码进行相应的改进。改进后的概率节点编码使得p-TwigStack算法成功地运用于概率XML文档的查询处理,得到了查询所需要的所有的中间结果。另外,由于概率XML文档中数据存在的概率特性,使得查询处理得到的中间结果和最终结果都具有一定的存在概率,低概率的结果无法满足查询要求,为了提高算法的查询效率,本文在算法运行的过程中加入了相应的过滤操作。过滤操作主要包括中间结果生成过程中的过滤和最终结果生成过程中的过滤。在文章的最后,对相关查询处理算法做了比较,主要包括概率Holistic Twig查询处理算法与possible worlds算法相比较的效率分析、概率Holistic Twig算法查询处理的过程中,概率过滤操作对整个算法效率的影响分析等,并且对比较结果给出相应的分析。

全文目录

摘要  5-6
Abstract  6-9
第1章绪论  9-19
  1.1 概率XML文档简介  9-13
    1.1.1 普通XML文档  9-10
    1.1.2 概率XML文档  10-13
    1.1.3 利用XML文档表示概率数据的优势  13
  1.2 概率XML文档中传统查询处理算法  13-16
  1.3 传统Holistic Twig查询处理算法  16-17
  1.4 问题的提出及意义  17
  1.5 论文的组织结构  17-19
第2章概率XML文档基本概念及问题定义  19-25
  2.1 概率XML文档的基本概念  19-21
    2.1.1 概率分布节点  19-20
    2.1.2 Twig查询模式  20-21
    2.1.3 概率阈值  21
  2.2 问题定义  21-24
    2.2.1 概率Holistic Twig算法定义  22
    2.2.2 概率阈值过滤  22-24
  2.3 本章小结  24-25
第3章概率HOLISTIC TWIG查询处理算法  25-39
  3.1 区域编码与概率标签流  25-30
    3.1.1 传统区域编码  25-26
    3.1.2 区域编码改进  26-30
    3.1.3 概率标签流  30
  3.2 p-TwigStack算法  30-33
  3.3 p-Merge算法  33-37
    3.3.1 m-MXD的作用  33-34
    3.3.2 L-branch的作用  34
    3.3.3 生成最终结果  34-37
  3.4 本章小结  37-39
第4章概率HOLISTIC TWIG算法概率过滤  39-53
  4.1 过滤操作的必要性  39-40
  4.2 p-TwigStack概率过滤  40-44
  4.3 p-Merge概率过滤  44-50
    4.3.1 p-Merge顺序概率过滤  44-48
    4.3.2 p-Merge过程概率过滤  48-50
  4.4 本章小结  50-53
第5章实验与性能分析  53-63
  5.1 实验环境  53
  5.2 概率Holistic Twig查询效率分析  53-58
    5.2.1 数据集大小  54
    5.2.2 概率阈值大小  54
    5.2.3 算法效率对比结果分析  54-58
  5.3 概率过滤对查询算法效率影响的分析  58-61
    5.3.1 数据集大小  59
    5.3.2 概率阈值大小  59
    5.3.3 算法效率对比结果分析  59-61
  5.4 本章小结  61-63
第6章结论  63-65
参考文献  65-69
致谢  69-71
攻读硕士期间发表的论文  71

概率XML文档中Holistic Twig查询处理算法的研究与实现

内容摘要

全文目录

相似论文