数据流系统中查询处理机制的研究与实现

摘要

本文首先介绍了当前数据流理论和数据流系统的研究概况,然后说明了数据流上查询处理功能模块在实时数据流系统中的位置及其作用;在分析了数据流上窗口操作实现过程中可能出现的各种问题之后,我们针对这些问题提出了一种分级窗口的维护策略,并进一步介绍了分级窗口的特点、适用范围和维护方式,在原型系统RealStream中也实现了这种策略;然后对数据流上常见的几种窗口结构进行了分析,并给出了各种类型窗口的具体实现方法;最后在以分级窗口为底层架构的基础之上,对整个查询处理中的各个功能模块进行理论分析与具体实现的介绍.

目录

文摘

英文文摘

独创性声明及学位论文版权使用授权书

第一章前言

1.1数据流

1.2数据流系统简介

1.3研究现状

1.3.1 STREAM

1.3.2 TelegraphCQ

1.3.3 Aurora

1.3.4其他系统

1.4数据流系统查询处理机制简介

1.4.1数据流查询处理机制

1.4.2数据流查询处理的特点

1.4.3查询计划

1.5课题来源

1.6本文组织结构

第二章数据流管理系统RealStream

2.1 RealStream运行结构

2.2 RealStream查询处理基础结构

2.2.1元组相关结构

2.2.2操作符模块

2.2.3其他数据结构

2.3小结

第三章窗口技术与分级窗口维护策略

3.1窗口技术

3.1.1窗口的定义

3.1.2窗口的分类

3.1.3窗口的结构设计

3.1.4窗口的语法

3.2数据流系统中窗口问题

3.3分级窗口的定义

3.4分级窗口的维护

3.4.1分级窗口的维护

3.4.2分级窗口维护算法

3.4.3结构指针

3.5应用实例

3.6分级窗口的数据共享

3.6.1查询对流窗口的共享

3.6.2流窗口和操作符窗口对元组的共享

3.6.3共享数据的一致性

3.7性能测试与评价

3.7.1分级窗口维护的性能测试

3.7.2共享分级窗口的内存性能

3.8分级窗口在RealStream中的应用

3.9小结

第四章窗口结构的设计及其实现

4.1流窗口设计

4.1.1流窗口结构

4.1.2窗口控制器结构

4.1.3流窗口维护算法

4.2快照式(Snapshot)窗口

4.2.1基于时间的快照式窗口

4.2.2基于元组数量的快照式窗口

4.3界标式(Landmark)窗口

4.3.1基于时间的界标式窗口

4.3.2基于元组数量的界标式窗口

4.4滑动式(Sliding)窗口

4.4.1基于时间的滑动式窗口

4.4.2基于元组数量的滑动式窗口

4.5不需窗口的查询处理方式

4.6窗口的清理

4.6.1最小覆盖(Minimum Overlay)

4.6.2引用计数(Reference Count)

4.7小结

第五章查询执行模块的设计与实现

5.1查询执行模块的结构设计

5.1.1查询处理模块组织结构

5.1.2操作符序列

5.1.3查询执行过程

5.2连接操作符的设计与实现

5.2.1常用连接算法

5.2.2数据流上的连接形式

5.2.3连接算法的性能分析

5.2.4多流上的连接操作

5.2.5连接操作符的实现

5.3选择操作符的设计与实现

5.3.1选择操作的定义和特点

5.3.2选择操作的设计

5.3.3选择操作符的实现

5.4投影操作符的设计与实现

5.4.1投影操作符的定义和特点

5.4.2投影操作符的设计

5.4.3投影操作符的实现

5.5聚集操作符的设计与实现

5.5.1聚集操作种类及特点

5.5.2聚集操作符的设计

5.5.3聚集操作符的数据结构

5.5.4聚集操作符的实现

5.6调度器与数据池

5.7小结

第六章总结与展望

6.1 RealStream查询处理实现的总结

6.2未来的工作

参考文献

致谢

攻硕期间参加的项目与发表的论文