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

基于XML数据的关键字查询处理研究

作　者: 赵兴敏
导　师: 周军锋
学　校: 燕山大学
专　业: 计算机应用技术
关键词: XML 关键字查询通用性独立性 TDxLCA
分类号: TP391.1
类　型: 硕士论文
年　份: 2013年
下　载: 1次
引　用: 0次
阅　读: 论文下载

内容摘要

随着XML（可扩展标记语言，eXtensible Markup Language）应用领域的不断扩展，基于XML数据的关键字查询技术得到了研究者的广泛关注。对于给定的关键字查询，本文主要研究如何高效返回满足不同查询语义的结果，主要研究内容如下。首先，通过深入比较和分析现有关键字查询处理算法的特点及其适用条件，发现其效率低下的主要原因为：公共祖先重复处理和访问无用结点问题。其次，针对上述问题，提出了一种通用的自顶向下关键字查询处理策略及相应的TDxLCA算法，其中xLCA表示我们的方法可以处理LCA、SLCA以及ELCA语义。TDxLCA算法在传统倒排表上，以自顶向下的方式依次检测所有的公共祖先结点，避免了公共祖先重复处理问题；对于检测到的每个公共祖先结点，TDxLCA算法通过该结点的孩子而不是后代判断其满足性，避免了访问无用结点问题。TDxLCA算法的通用性体现在编码独立性和语义独立性两个方面。编码独立性指基于任意一种现存的路径编码，TDxLCA算法均以相同的时间和空间复杂度处理给定的查询；语义独立性指针对给定的查询，TDxLCA算法可用于处理任意一种语义。再次，针对传统倒排表的冗余存储问题，提出了一种独立于编码方式的分层索引—LList倒排索引。基于LList，提出TDxLCA-L算法，和TDxLCA相比，降低了查询处理的时间复杂度。然后，在LList的基础上结合哈希索引，提出了基于哈希查找的TDxLCA-H和TDxLCA-HO算法，进一步降低查询处理的时间复杂度。最后，基于不同的数据集，通过实验，从运行时间、原子操作次数等方面对算法的高效性和扩展性进行了验证。

全文目录

摘要  5-6
Abstract  6-9
第1章绪论  9-13
  1.1 研究背景  9
  1.2 研究现状  9-11
    1.2.1 查询语义  9-10
    1.2.2 查询算法  10-11
  1.3 研究内容  11-12
  1.4 本文结构  12-13
第2章基础知识概述  13-19
  2.1 XML 相关概念  13-15
    2.1.1 XML 简介  13
    2.1.2 XML 优势  13-14
    2.1.3 数据模型  14-15
  2.2 XML 编码方案  15-16
  2.3 倒排索引  16-17
    2.3.1 传统的倒排索引  16-17
    2.3.2 IDList 倒排索引  17
  2.4 查询语义  17-18
  2.5 本章小结  18-19
第3章基于传统倒排表的 TDELCA 算法  19-34
  3.1 问题分析  19-21
    3.1.1 公共祖先重复处理问题  19-20
    3.1.2 访问无用结点问题  20-21
  3.2 TDELCA 算法  21-27
    3.2.1 算法思想  21-23
    3.2.2 算法描述  23-26
    3.2.3 算法分析  26-27
  3.3 实验  27-33
    3.3.1 实验环境  27
    3.3.2 数据集和查询  27-29
    3.3.3 评价标准  29
    3.3.4 实验结果分析  29-33
  3.4 本章小结  33-34
第4章基于分层倒排表的 TDELCA-L 算法  34-45
  4.1 问题分析  34
  4.2 LList 索引  34-37
  4.3 TDELCA-L 算法  37-39
    4.3.1 算法描述  37-39
    4.3.2 算法分析  39
  4.4 实验结果分析  39-42
  4.5 其它语义的处理  42-43
    4.5.1 SLCA 处理  42
    4.5.2 LCA 处理  42-43
    4.5.3 其它语义  43
  4.6 本章小结  43-45
第5章基于哈希查找的算法  45-56
  5.1 问题分析  45
  5.2 哈希索引  45-46
  5.3 基于哈希查找的基本算法  46-47
    5.3.1 算法描述  46-47
    5.3.2 算法分析  47
  5.4 优化的哈希查找算法  47-50
    5.4.1 算法描述  48-50
    5.4.2 算法分析  50
  5.5 实验结果分析  50-55
  5.6 本章小结  55-56
结论  56-57
参考文献  57-61
攻读硕士学位期间承担的科研任务与主要成果  61-62
致谢  62-63
作者简介  63

基于XML数据的关键字查询处理研究

内容摘要

全文目录

相似论文