数据流多连接查询算法研究

论文摘要

由于数据流具有实时性、连续性、无界性的特点,传统的数据库管理技术已不能适应对它的处理需求,数据流查询成为数据库理论研究的一个新领域。其中连接查询由于其应用广泛性和复杂性而得到更多的关注,但大多数的研究成果主要是针对二路连接查询,多连接查询作为数据流连接查询的一个重要方面,目前研究的还相对较少。本文首先分析了数据流滑动窗口二路连接查询,包括算法的执行过程及连接代价模型,介绍了目前主要的两种数据流多连接查询方式:多连接算子和连接树。然后,本文在滑动窗口二路连接代价模型的基础上,给出了多连接算子中数据流连接过程的代价模型,针对树型查询提出了最优探测序列判定算法DSTQPS-OPT（Data Stream Tree Query Optimal Probe Sequence）,并针对非树型查询提出了最优探测序列判定算法DSGQPS-OPT（Data Stream General Query Optimal Probe Sequence）。接着,本文对基于线性连接树的多连接查询计划的中间状态进行了分析,并提出了最小中间状态线性连接树生成算法DSLJT-MinIS（Data Stream Linear Join Tree–Minimal Intermediate State）。最后,本文通过实验验证了多连接算子中的数据流连接代价模型的正确性,并通过对比实验证明DSTQPS-OPT算法优于已有的贪婪算法。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究背景及意义
• 1.2 当前研究现状及选题依据
• 1.2.1 国内外研究现状
• 1.2.2 选题依据
• 1.3 论文的研究内容
• 第二章 数据流连接查询
• 2.1 数据流基本概念
• 2.2 数据流查询
• 2.2.1 数据流查询的特征
• 2.2.2 数据流查询的基本运算分类
• 2.2.3 数据流查询面临的挑战
• 2.2.4 数据流查询常用处理技术
• 2.3 基于滑动窗口的数据流二路连接查询
• 2.3.1 滑动窗口及分类
• 2.3.2 滑动窗口连接操作语义及代价模型
• 2.4 基于滑动窗口的数据流多连接查询
• 2.4.1 多连接算子
• 2.4.2 连接树
• 2.4.3 两种机制比较
• 2.5 本章小结
• 第三章 多连接算子中最优探测序列算法研究
• 3.1 引言
• 3.2 多连接算子的连接代价分析
• 3.3 预备知识
• 3.4 树型多连接查询最优探测序列判定算法DSTQPS-OPT
• 3.4.1 算法思想及求解过程
• 3.4.2 算法描述及分析
• 3.4.3 与SQPS-GA 算法比较
• 3.5 非树型多连接查询最优探测序列判定算法DSGQPS-OPT
• 3.5.1 算法思想及求解过程
• 3.5.2 算法描述及分析
• 3.6 本章小结
• 第四章 基于线性连接树的多连接查询计划中间状态研究
• 4.1 引言
• 4.2 基于线性连接树的多连接查询计划中间状态分析
• 4.3 最优线性连接序列生成算法
• 4.3.1 预备知识
• 4.3.2 算法思想及求解过程
• 4.3.3 算法描述及分析
• 4.4 本章小结
• 第五章 实验验证及分析
• 5.1 实验环境
• 5.2 实验验证及分析
• 5.2.1 连接代价模型验证及分析
• 5.2.2 最优探测序列算法比较及分析
• 5.3 本章小结
• 第六章 总结与展望
• 6.1 论文总结
• 6.2 未来工作展望
• 参考文献
• 致谢
• 在学期间的研究成果