XML上基于SLCA的关键字查询研究

摘要

随着互联网的发展，XML格式逐渐成为数据展现和传输的事实标准。XML上信息获取技术研究也越发重要。自XML语言诞生以来，各种各样的XML结构化查询语言被开发出来，如XPath、XQuery等。但结构化查询语言对用户要求较高，不仅要求掌握一门复杂的查询语言，还要求了解目标XML文件的结构知识。而关键字查询的方式，简单易用，受到用户的喜欢。XML上关键字查询已成为研究的热点。
　　本文工作主要包括:1.通过引入两个有效的剪枝策略和三个定义明确的匹配节点组合概念提出了一个高效的基于SLCA语义的关键字查询算法MMPS;2.提出了关键字查询的返回结果快速分类的算法。
　　为了返回有意义的关键字查询返回结果，SLCA（最小最低公共祖先）的概念被引入到数据管理领域，即返回一棵同时满足两个条件的子树(a)包含所有关键字，(b)这棵树上不包含满足条件b的子树。然而现有的基于SLCA语义的算法在计算SLCA过程中通常会引入大量中间结果的计算，即使最后的返回结果集很小，剪枝策略较简单，效率不高。针对这些不足，本文深入研究SLCA候选和XML上的节点间的关系，提出了两个有效的剪枝策略和三个匹配节点组合概念，基于这些策略和概念提出了一个高效的SLCA关键字查询算法MMPS。在本文实验部分重新实现了当前较优的IMS算法与MMPS算法，并通过在真实数据集和人工数据集上的对比试验，验证了MMPS算法的高效性。
　　另一方面，基于关键字查询返回结果较多，返回的结果有些差别较大的事实，本文提出了对返回结果的快速分类算法，以提高用户体验。本文首先提出了一种利用tag名称做分类的na(i)ve方法，该方法利用外存中的索引得到节点对应的tag信息，而后利用红黑树根据tag信息做分类。这种方法引用了外存索引，IO开销较大，用户体验较差。针对这个不足，本文又提出了一个改进算法，通过引入扩展dewey编码避免了外存索引，减少IO开销。通过实验发现，改进算法的性能远远优于na(i)ve算法，提高了用户体验。

目录

摘要

第一章 绪论

1．1 XML基础知识

1．2 XML数据模型

1．3 XML信息获取技术

1．4 本文主要工作和贡献

1．5 章节安排

第二章 背景知识和相关工作

2．1 XML解析

2．2 XML编码技术

2．2．1 Dewey编码

2．2．2 区间编码

2．3 LCA计算问题

2．3．1 LCA计算问题

2．3．2 基于区间编码的LCA计算

2．4 倒排索引

2．5 本章小结

第三章 关键字查询算法

3．1 问题定义和相关工作

3．1．1 符号定义

3．1．2 基于SLCA语义的Indexed Lookup Eager算法

3．1．3 基于SLCA语义的Incremental Multiway-SLCA算法

3．1．4 相关工作小结

3．2 SLCA性质

3．3 剪枝规则和匹配节点组合概念

3．4 MMPS查询算法

3．5 本章小结

第四章 返回结果处理

4．1 Na?ve分类算法

4．2 改进分类算法

4．2．1 扩展Dewey编码

4．2．2 改进算法主体

4．3 本章小结

第五章 实验结果与分析

5．1 实验设置

5．2 实验一结果与分析

5．3 实验二结果与分析

5．4 本章小结

总结与展望

参考文献

硕士研究生期间主要工作

致谢

声明