数据流的无阻塞连接算法研究

摘要

数据流是近年来数据库技术发展的一个重要领域。数据集成系统将不断由远程终端产生的数据，通过网络传送到本地做进一步处理。其中数据流上的连接操作是数据流查询的支撑技术，应用范围十分广泛。由于数据流环境下的数据大小可能远远超过内存存储能力，所以难以得到全部结果解。加上网络中存在的不稳定性，使得数据到达本地经常出现阻塞现象，从使得结果不能持续性的生成。交互式和实时系统往往要求结果的精确性和无阻塞的持续产生。
　　 对于内存有限时的数据流连接，可以借助于外存达到无阻塞的得到精确结果的目的。在网络中断时，将外存数据作为数据，通过执行外部连接来保证结果产生的无阻塞性，这种渐进式的连接方式还可以得到精确结果集。
　　 将一个完整的数据块作为外部连接的事务单位是一种通常的方法，但在数据流连接的中后期，随着交换到外存的数据增多，数据块的势也会相应增大，要在有限网络中断间隔时间内启动外部连接越来越困难。根据不稳定网络中存在的长尾效应，将外部连接的事务单位细化，即采用细粒度的外部连接单位的方法，充分利用有限的中断时间，使得在数据流的中后期也可以有效启动外部连接。将经典的无阻塞连接算法中的事务单位分为多个子任务处理，这种细粒度的方法可以有效提高在线结果产生数。为减少外连趟数和有效利用有限剩余内存空间，对外存块采用了改进的替换选择树进行排序连接。还通过减少内存冗余字段，使用一种执行时间和产出结果估计的成本估测等方法来提高连接结果数。
　　 空间数据流的连接方法与等值连接不同，由于涉及连接范围上的交叉连接，对应连接块所在的数据块号可能不一致，采用以往的等值连接的方式在空间数据连接中并不适用。提出一种基于空间数据流的无阻塞连接算法。采用基于结果统计的方法进行理论建模，设计一种高效的交换策略用于网络不稳定时的内存管理，设计代价估算公式作为不稳定网络下的数据连接的策略。
　　 非周期性数据流连接往往需要根据走势特征来确定预期分布，但如何确定数据块的分布走势，如何在数据流下动态划分数据块都是研究的重要问题。提出一种变换高斯分布下的数据流连接算法。通过采样统计确定当前高斯中心点，并以此为中心划分数据块。将已确定的数据连接块作为元数据来描述预测方程，从得到高效的内存交换策略。

目录

文摘

英文文摘

论文说明：主要符号对照表

声明

1 绪论

2 两种改进的无阻塞连接算法

3 一种新的细粒度无阻塞连接算法

4 基于频率的空间数据流连接算法

5 基于时间演化的无阻塞数据流连接算法

6 总结与展望

致谢

参考文献

附录