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

XML文档小枝模式匹配查询算法研究

作　者: 白山
导　师: 陶世群
学　校: 山西大学
专　业: 计算机软件与理论
关键词: XML 小枝模式查询匹配算法查询节点流 SAX解析
分类号: TP311.10
类　型: 硕士论文
年　份: 2009年
下　载: 38次
引　用: 0次
阅　读: 论文下载

内容摘要

由于XML具有自描述性和可扩展性等特点,能够满足WEB上对数据描述和存储的需求,因而使得XML正在成为Web上数据表示和交换的事实上的标准。随着XML格式数据的快速增长和广泛应用,对XML数据的查询、转换和存储的研究受到了广泛关注。在XML文档的查询技术研究中,基于小枝模式匹配的结构连接查询是关键的核心内容。对于XML结构查询,可以对XML文档树中的结点或边进行编码,通过编码直接判断结点之间的结构关系,而无需对原XML文档树进行遍历,从而将XML结构查询的计算转化为结构连接的计算。目前对XML文档的编码方法有区间编码、路径编码、前缀编码等。因此,随着不同编码方案的研究,各种相应的结构查询算法也提了出来。对于XML文档基于结构连接的小枝模式匹配查询,是从文档树中查找与查询模式匹配的结点,然后将查找到的匹配结果再组装成最终符合查询表达式的完整树结构。TwigStack是一个典型的关于小枝模式匹配的结构连接查询算法。它采用链栈的数据结构作为缓存,对查询节点流进行整枝计算,从而避免了无用中间结果的产生。基于此算法,又提出了一系列改进的算法。其中Twig~2Stack和TwigList算法分别采用层次关系的堆栈结构和列表结构,避免了复杂的归并过程,进一步提高了查询效率。在我们对小枝模式匹配查询的研究中,发现TwigStack算法对查询节点流在结束时的处理上存在着不足;在对TwigList算法的分析中,发现可以将XML文档的SAX解析应用于查询过程,从而避免了对XML文档进行编码,能进一步提高查询效率。本文的主要工作是:(1)提出了BSTwigStack小枝模式匹配查询算法。该算法增强了原有的TwigStack算法,给出了XML文档在查询节点流结束时的查询匹配处理策略。(2)提出了BSTwigList小枝模式匹配查询算法。针对XML文档的结构特点,在结合XML文档的基于事件的SAX解析方式的基础上,改进了TwigList算法。BSTwigList算法能够应用于节点流模式的小枝查询,在文档解析的同时可以进行模式匹配查询,避免了以往查询算法需要先对文档节点进行编码索引的步骤,使得XML文档在更新时,无需对编码文件进行重新编码和维护,从而减少了查询所需的存储空间,提高了查询效率。(3)最后通过对算法进行的实验和数据测试,给出了算法查询时间响应及性能分析图表,进一步验证了改进的查询算法的有效性。在对以上算法的研究和实现当中,本文所研究的只是XPath查询的一个片段,对于其他形式的XPath查询,仍然有待于进一步的研究;另外本文考虑的只是一种静态XML文档节点数据流的小枝模式匹配查询,而对于在网络环境下的多用户的动态数据流小枝模式匹配查询,还要加以更进一步的研究。这些将成为今后下一步研究的重点和方向。

全文目录

中文摘要  8-10
ABSTRACT  10-12
第一章引言  12-16
  1.1 课题研究背景  12
  1.2 国内外研究现状  12-15
  1.3 论文的主要工作和组织结构  15-16
第二章 XML文档查询的相关知识  16-23
  2.1 XML文档基本概念  16-18
    2.1.1 XML文档及其模型  16-17
    2.1.2 XML文档编码  17-18
  2.2 XML文档解析  18-19
  2.3 XML文档查询语言  19-20
  2.4 XML文档查询技术  20-23
第三章 XML小枝查询算法BSTwigStack  23-30
  3.1 相关概念和定义  23-24
  3.2 小枝栈算法TwigStack  24
  3.3 改进的小枝栈算法BSTwigStack  24-29
    3.3.1 小枝栈算法BSTwigStack的数据结构及其函数说明  25-26
    3.3.2 BSTwigStack算法  26-27
    3.3.3 BSTwigStack的运行过程  27-28
    3.3.4 BSTwigStack的算法分析  28-29
  3.4 本章小结  29-30
第四章 XML小枝查询算法BSTwigList  30-40
  4.1 概述  30
  4.2 TwigList算法  30-34
    4.2.1 TwigList算法的数据结构说明  30
    4.2.2 TwigList算法  30-32
    4.2.3 TwigList算法的运行过程  32-34
  4.3 改进的XML数据流BSTwigList算法  34-39
    4.3.1 BSTwigList算法说明  34-35
    4.3.2 BSTwigList算法  35-36
    4.3.3 BSTwigList算法的运行过程  36-39
  4.4 本章小结  39-40
第五章实验及数据测试和分析  40-45
  5.1 实验设置  40
  5.2 实验系统流程图  40-41
  5.3 算法测试及性能比较  41-43
    5.3.1 数据测试集  41
    5.3.2 性能分析比较  41-43
  5.4 本章小结  43-45
第六章结论及工作展望  45-46
参考文献  46-49
附录  49-50
致谢  50-51
个人简况及联系方式  51-52

相似论文

基因调控网络模型描述语言研究,Q78
支持XML数据查询的F&B索引结构的研究,TP311.13
LXI自动测试系统集成技术研究,TP274
基于网络的服装款式设计系统的研究与实现,TS941.2
基于MDA的界面自动生成方法的研究,TP311.5
C++代码缺陷检测系统的研究与设计,TP311.53
基于Web的科学计算遗留应用共享技术研究,TP393.09
基于XML的异构数据交换系统的设计与实现,TP311.52
电子公文传输管理系统在电大系统中的设计与实现,TP311.52
概率XML数据上关键字检索算法的研究与实现,TP391.3
行政审批电子监察系统数据交换的设计与实现,TP311.52
概率XML文档中Holistic Twig查询处理算法的研究与实现,TP311.13
保留语义约束的XML与关系数据库双向转换技术研究,TP311.13
SOA架构在高校信息化系统中整合技术的应用,TP311.52
基于银行综合前置平台的金融服务支付系统的设计与实现,TP311.52
基于观察者模式的银行主动服务系统的设计与实现,TP311.52
江北区企业信用信息系统设计与实现,TP311.52
物联网业务模型描述语言的研究与实现,TN929.5
基于服务总线的模具企业信息集成系统,TP311.52
基于FDT/DTM技术设备管理系统的研究与开发,TP311.52
基于SOA的协同制造异构系统的数据集成研究,TP311.13