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

支持XML数据查询的F&B索引结构的研究

作　者: 刘显敏
导　师: 李建中
学　校: 哈尔滨工业大学
专　业: 计算机科学与技术
关键词: XML 树模型有向无环图模型 F&B索引查询处理
分类号: TP311.13
类　型: 硕士论文
年　份: 2008年
下　载: 58次
引　用: 0次
阅　读: 论文下载

内容摘要

XML(可扩展标记语言),作为网络上数据表示和信息交换的工具,以其自描述性、独立于平台等特点,已经成为新一代的网络语言。随着XML的广泛应用,XML上的索引及其相关技术的研究就显得十分重要。本文以解决XML最重要的结构索引——F&B索引在实际应用中的问题为目标,就F&B索引的创建、存储、执行查询等问题进行了研究。本文的工作及主要贡献包括如下几个方面:首先,从节省内存空间的角度出发,针对XML树模型和有向无环图模型,分别提出了新的F&B索引创建算法SAJ和SAM。理论分析表明树模型上的SAJ算法的空间性能优于现有的算法,有向无环图模型上的SAM算法的时间、空间性能均优于现有的算法。实验结果表明这两个算法是正确、高效的,并且有良好的可扩展性。其次,着眼于F&B索引使用中占用内存空间过大的问题,基于聚簇的思想,提出了一种新的基于磁盘的F&B索引结构——EDF&B索引,大大节省了使用F&B索引所占用的空间代价。实验结果表明,该索引结构的冗余量很小适合实际应用。最后,将现有的F&B索引查询处理算法扩展到EDF&B索引上,提出了基于EDF&B索引的新的查询处理算法,并用实验验证了该算法的高效性和EDF&B索引的有效性。

全文目录

摘要  4-5
Abstract  5-9
第1章绪论  9-15
  1.1 研究的目的与意义  9-10
    1.1.1 目的  9-10
    1.1.2 意义  10
  1.2 XML 简介  10-12
    1.2.1 XML 及其相关标准  10-11
    1.2.2 XML 及其相关标准  11-12
  1.3 相关工作  12-14
  1.4 本文工作及结构  14-15
第2章 XML 及F&B 索引预备知识  15-21
  2.1 XML 简介  15-17
    2.1.1 语义标签  15-16
    2.1.2 格式规范的XML  16-17
  2.2 XML 数据模型  17
  2.3 XML 查询  17-18
  2.4 F&B 索引的结构性质  18-20
    2.4.1 结构索引  18-19
    2.4.2 F&B 关系  19
    2.4.3 F&B 索引  19-20
  2.5 本章小结  20-21
第3章树模型上F&B 索引创建算法  21-34
  3.1 引言  21-22
  3.2 预备知识  22-24
    3.2.1 数据模型  22-23
    3.2.2 基于FB 关系的F&B 索引  23-24
  3.3 F&B 索引的创建算法SAJ  24-30
    3.3.1 定义及符号说明  24-25
    3.3.2 SAJ 算法  25-28
    3.3.3 SAJ 算法的分析  28-30
  3.4 实验结果及分析  30-33
    3.4.1 F&B 索引构建所需空间  30-31
    3.4.2 F&B 索引构建时间  31
    3.4.3 SAJ 算法可扩展性  31-32
    3.4.4 实验小结  32-33
  3.5 本章小结  33-34
第4章有向无环图模型上F&B 索引创建算法  34-48
  4.1 引言  34-35
  4.2 预备知识  35-37
    4.2.1 XML 有向无环图模型  35
    4.2.2 XML 有向无环图的流模型  35-36
    4.2.3 F&B 索引  36-37
    4.2.4 PT 算法  37
  4.3 SAM 算法  37-42
    4.3.1 SAM 算法概览  38-39
    4.3.2 扫描和划分  39-41
    4.3.3 合并  41-42
    4.3.4 构建F&B 索引  42
  4.4 SAM 算法的分析  42-44
    4.4.1 SAM 算法的正确性  43-44
    4.4.2 SAM 算法的复杂性分析  44
  4.5 实验  44-47
    4.5.1 实验配置  44
    4.5.2 比较实验  44-46
    4.5.3 可扩展性实验  46-47
  4.6 本章小结  47-48
第5章磁盘F&B 索引及其查询处理算法  48-62
  5.1 基于磁盘的F&B 索引  48-52
    5.1.1 基本存储结构  48-51
    5.1.2 索引大小测评  51-52
  5.2 基于遍历的BFS 和DFS 算法  52-54
  5.3 基于区间编码的RangeFetch 算法  54-55
  5.4 基于集合交运算的SegSJ 算法  55-56
  5.5 自底向上的BTU 算法  56-58
  5.6 实验及其分析  58-60
    5.6.1 同其他系统性能比较  58-60
    5.6.2 BTU 算法同其它遍历方法的比较  60
  5.7 本章小结  60-62
结论  62-63
参考文献  63-67
攻读学位期间发表的学术论文  67-69
致谢  69

相似论文

基因调控网络模型描述语言研究,Q78
海量多数据库集成系统的查询处理研究,TP311.13
大规模稀疏关系数据索引技术研究,TP311.132.3
面向动态文档集的大规模文本索引构建技术的研究,TP391.3
面向海量邮件的检索系统研究与实现,TP393.098
LXI自动测试系统集成技术研究,TP274
基于网络的服装款式设计系统的研究与实现,TS941.2
基于MDA的界面自动生成方法的研究,TP311.5
Bicluster数据分析软件设计与实现,TP311.52
C++代码缺陷检测系统的研究与设计,TP311.53
网络搜索引擎的相关技术研究,G354
基于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