随着网络的普及,信息处理技术有了一些新的应用领域,例如,传感器网络,网上在线交易系统,股票行情实时监控。在这些应用中,数据不再是静态的,而是一种实时的、不稳定的流式数据,称之为数据流数据,同时应用系统要求数据的处理结果能够及时地,分批次地,无阻塞地反馈给用户。传统关系数据处理技术突显出其局限性,数据流上的关系查询处理技术成为数据库研究领域的一大热点。在数据查询中,关系连接算法则是一个制约查询处理性能的重要因素。在数据流上的关系连接算法其时间复杂度必须能适应数据流的传输速度实现无阻塞连接,其空间复杂度必须能够充分利用有限的内存空间处理大量的流数据。为了提高其性能,需要维护一个尽量小的连接状态,并利用数据的分布特征设计约束条件来进行状态简化。同时,要充分利用多级存储系统,优化数据在内外存之间的刷新策略。为两个相连接的关系流分别划分内存分区M和外存分区D,利用内存的缓冲作用将数据流上的关系连接划分为MM,MD,DD三个阶段。随着网络的传输速度的变化,连接过程在三个阶段之间按照一定策略进行切换,充分利用网络延迟的间隙,提高连接效率,实现无阻塞连接。优化无阻塞连接算法的关键在于提高内存连接阶段的效率,当内存空间满时,需要将内存数据刷新到外存相应分区,良好的刷新策略对于改进算法的性能至关重要。利用数据分布的特征,对关系连接的输出流,使用基于Bloom Filter结构的关键字统计方法,查找使用频率最低的元组,将统计的结果反馈回内存刷新阶段,在刷新阶段根据统计结果,将使用频率较低元组刷新到外存,提高内存数据的效率。基于输出流的统计分析策略提高了刷新策略的准确性和效率以及无阻塞连接算法的可适用范围。
本文来源: https://www.lw50.cn/article/6a448fa84f116ad2364d14af.html