论文部分内容阅读
近几年,随着网络、通信以及传感技术的发展,数据流受到普遍关注;常见的数据流包括Web访问日志数据流、股票价格信息数据流以及网络信息数据流。随着数据流越来越受关注,研究人员提出了一类新的数据模型,即数据流模型。在传统的数据库模型中,查询在静态的数据集上执行,返回查询结果后查询即告结束。在数据流模型中,查询在实时、持续、有序、无界的数据流上持续执行,当数据流中的流数据发生变化时以增量的方式对查询结果进行实时更新。由于数据流是无界的,数据流上的持续查询通常将查询数据限制在最近一段时间或最近某些流数据内,这就是数据流滑动窗口环境下的查询。由于数据流滑动窗口环境下的聚集查询在在线决策支持领域有着广泛的应用,本文对数据流滑动窗口环境下的聚集若干问题进行研究。由于数据流的流速可能非常高、流速可能呈现脉冲、数据量可能非常大以及数据流上的查询对实时性要求比较高,数据流上的查询处理和优化在提高时空性能上充满了挑战。本文首先用可加性、可减性和抽样性三个性质对聚集函数进行分类,分类结果说明了在数据流滑动窗口环境下处理特定聚集查询所能得到的空间性能最优的方法。以这个聚集函数分类为基础,本文对如下四个滑动窗口聚集查询的查询处理和优化方法有所创新,即数据流多滑动窗口环境下的最值查询、数据流滑动窗口环境下的skyline查询、数据流滑动窗口环境下的skyband查询和数据流滑动窗口环境下的集合势查询。具体地说,本文将包含如下五个方面的创新性研究成果:
(1)在聚集函数分类方面,依据在数据流滑动窗口环境下对聚集查询进行查询处理和查询优化所能得到的空间性能最优方法的不同提出对聚集函数进行分类的标准,这个聚集函数分类标准将成为后续工作的理论基础。
(2)在滑动窗口最值查询处理方面,给出利用空间性能最优的抽样大纲在数据流滑动窗口环境下求解最值查询的方法、多个滑动窗口共享同一个抽样大纲的方法以及对抽样大纲的空间性能进行分析和估计的方法。
(3)在滑动窗口skyline查询优化方面,给出对skyline查询的结果集进行大小估计的方法、利用skyline大纲实现最优存储管理的方法以及对空间性能最优的skyline大纲的空间性能进行分析和估计的方法。
(4)在滑动窗口skyband查询优化方面,给出对skyband查询的结果集进行大小估计的方法、利用skyband大纲实现最优存储管理的方法以及对空间性能最优的skyband大纲的空间性能进行分析和估计的方法。
(5)在滑动窗口集合势查询处理方面,给出利用计数Bloom Filter近似求解滑动窗口集合势查询的三个算法并对算法的性能进行详尽的分析和比较。
本文还对给出的在数据流滑动窗口环境下对聚集查询进行查询处理和查询优化的方法进行了详详尽的理论分析,并通过实验验证了理论分析的正确性和我们给出的对滑动窗口聚集查询进行查询处理和查询优化的方法的优越性。