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

基于FTContainsExpr的扩展模式树匹配技术研究

作　者: 张子鋆
导　师: 汪卫
学　校: 复旦大学
专　业: 计算机软件与理论
关键词: XML查询 扩展模式树 模式树匹配 SLCA
分类号: TP312.2
类　型: 硕士论文
年　份: 2009年
下　载: 44次
引　用: 0次
阅　读: 论文下载
 

内容摘要


XML采用树形模型来表示数据,XML文档上的查询通常被表示成小枝模式。与此同时,XML文档上关键字的检索也因其直观、友好的查询接口而被广泛研究。为了更好地整合数据管理领域与信息检索领域对XML文档查询技术的研究成果,W3C提出XQuery Full-Text作为XQuery的补充。它可以对XML数据中的结构信息与文本信息进行无缝地查询。本文针对XQuery Full-Text中具有合取关键字查询语义的FTContainsExpr表达式提出了相应的扩展模式树及其模式匹配问题。扩展模式树匹配问题由于关键字包含关系的引入而呈现出问题的特殊性。我们首先针对该问题设计了基于Dewey编码的解决方案,DILPathStack算法和DeweyPathStack算法。DILPathStack算法首先计算关键字结点的SLCA,然后利用它们来指导DeweyPathStack算法对结构化路径进行匹配。SLCA的计算可以有效减少在DeweyPathStack算法执行过程中各数据流无效结点的入栈,避免了无意义的栈操作,从而使得整个匹配过程更加高效。然后,针对DILPathStack算法和DeweyPathStack算法仍然存在的弊端,我们提出了基于区间编码的、直接对所有扩展模式树普适的匹配算法ILETwigStack。它对扩展模式树进行了重构,将扩展模式树中的每个关键字结点组收缩归并为一个查询单点,以它们的SLCA数据结点流来取代原始关键字结点流,重构后的扩展模式树能够用TwigStack算法进行匹配。这种方法既降低了扩展模式树的结构复杂度又大量减少了初始数据流结点的数量。实验结果表明,在对扩展模式树的处理效率上,ILETwigStack算法均胜于DILPathStack算法和传统的TwigStack算法。

全文目录


摘要  5-6
Abstract  6-7
第一章 绪论  7-14
  1.1 XML基础  7-9
  1.2 XML查询语言  9-11
    1.2.1 XPath  9-10
    1.2.2 XQuery  10-11
    1.2.3 XQuery Full-Text  11
  1.3 XML解析器  11-12
  1.4 本文工作和贡献  12-13
  1.5 文章结构  13-14
第二章 背景知识和相关工作  14-24
  2.1 XML数据模型  14-16
  2.2 经典模式树与模式匹配  16-17
  2.3 XML编码技术  17-20
    2.3.1 基于区间的编码  17-19
    2.3.2 基于路径的编码  19-20
  2.4 XML结构查询处理方法  20-21
  2.5 XML关键字检索处理方法  21-22
  2.6 本章小结  22-24
第三章 查询语义和扩展模式树匹配问题  24-27
  3.1 FTContainsExpr表达式的查询语义  24-25
  3.2 扩展模式树及其匹配问题  25-26
  3.3 本章小结  26-27
第四章 基于Dewey编码的扩展模式树匹配算法  27-38
  4.1 算法提出的动机  27-28
  4.2 预备知识  28-29
  4.3 符号定义和数据结构  29-30
  4.4 算法伪码  30-32
  4.5 算法解释与分析  32-34
  4.6 算法示例  34-37
  4.7 本章小结  37-38
第五章 基于区间编码的扩展模式树匹配算法  38-56
  5.1 算法提出的动机  38
  5.2 基于区间编码的LCA问题的解决方案  38-46
    5.2.1 LCA问题、RMQ问题与LCA问题到RMQ问题的规约  39-42
    5.2.2 RMO问题解决方案的逐步求精  42-46
  5.3 基于区间编码的SLCA问题的解决方案  46-52
    5.3.1 符号定义  46-47
    5.3.2 SLCA问题的一个朴素解法  47-48
    5.3.3 SLCA问题的一个快速算法  48-52
  5.4 算法设计思想与伪码  52-55
  5.5 本章小结  55-56
第六章 实验结果与分析  56-62
  6.1 实验环境  56-57
  6.2 实验结果  57-58
  6.3 实验分析  58-61
  6.4 本章小结  61-62
第七章 总结与展望  62-63
参考文献  63-66
硕士研究生期间主要工作  66-67
致谢  67-68

相似论文

  1. 基于XQuery的联系人管理系统开发,TP311.52
  2. 基于XML图形化查询转换技术的研究与应用,TP311.13
  3. XSemantic：基于语义扩展的XML关键字检索技术研究,TP391.3
  4. 基于SLCA的XML关键字查询研究与改进,TP311.13
  5. XML在关系数据库中存储和查询方法的研究,TP311.13
  6. 基于刻面分类模式的构件检索技术研究,TP311.52
  7. XML模式树匹配查询算法的研究与改进,TP312.2
  8. 自治异构数据源的集成查询处理,TP311.13
  9. 原生XML数据库存储与索引关键技术研究,TP311.13
  10. XML查询处理结构中的一种逻辑优化算法,TP301.6
  11. RDF-XML文档的索引查询技术研究与实现,TP311.52
  12. 基于索引的XML查询技术研究,TP312.2
  13. XML查询缓存中替换策略的研究与设计,TP312.2
  14. 多版本XML文档的查询处理,TP311.11
  15. XML数据查询技术研究,TP312.2
  16. 关于XML数据库存储和访问技术研究,TP311.13
  17. XQuery查询语言研究,G354
  18. XML查询语言XQuery及其扩展研究,TP311.13
  19. XML技术及其在信息技术考试系统中的研究与应用,TP311.52
  20. XML技术研究及在水利信息系统中的应用,TP399

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 程序语言、算法语言
© 2012 www.xueweilunwen.com