数据流与磁盘存贮表的连接计算算法  

Algorithm of Joining Data Stream with Disk- based Relation

作　　者：杜威[1,2,3] 邹先霞[4,3] 

机构地区：[1]广东警官学院计算机系,广东广州510232 [2]广州市公共安全重点研究基地,广东广州510232 [3]武汉大学软件工程国家重点实验室,湖北武汉430070 [4]暨南大学计算机系,广东广州510632

出　　处：《控制工程》2014年第6期904-908,912,共6页Control Engineering of China

基　　金：公安部技术研究计划项目(2014JSYJB048);广东省自然科学基金(S2012010008831);武汉大学软件工程国家重点实验室开放基金(SKLSE2012-09-37)

摘　　要：数据流与存贮表的连接查询经常出现在主动式数据仓库的维护中,与传统的关系数据库的连接计算不同,数据流快速处理的要求不允许将数据流先存入磁盘再计算,而计算机内存无法存储无界增长的数据流,因此数据流查询采用先处理再存储结果的计算方式。数据流与存贮表的连接计算算法重点要解决内存开销和处理速率二个问题。MESHJOIN算法最早提出将存贮表划分为若干个数据块,将数据块交替放入内存与数据流窗口完成连接计算。在MESHJOIN算法思想的基础上将存贮表的内存数据块也划分为若干逻辑分区,每次连接计算仅替换其中的一个逻辑分区,有效地降低了数据流滑动窗口所需的I/O代价,从而提高滑动窗口的计算速率。最后通过实验对二种算法在内存开销和计算速率进行了比较。In an active data warehouse, an important problem of data integration is the join of a continuous incoming data stream with a disk - based relation. Since data stream is infinite and is quickly processed, it is impossible for joining data stream with disk - based relation to a- dopt blocking join algorithms of traditional relational database. So data stream processing is first queried and then stored results. The memory cost and the service rate are two important factors for the join algorithm of a data stream with a disk - based relation. The algorithm of MESH- JOIN researched on how to join a stream with disk - based relation and proposed that a disk - based relation is divided into several blocks. The paper thinks the heavy I/0 cost every iteration as a result of replacing whole memory block of disk - based relation. The paper proposes that the memory block is divided into a number of logical partitions, and then every iteration only one logical partition of memory block is re- placed. The result shows that the service rate of the join is increased by way of decreasing the I/O cost for one loop iteration. In the end the comparison of the memory cost and the service rate between two algorithms is made by the experiment.

关 键 词：数据流 连接计算 磁盘存储表 逻辑分区 速率 

分 类 号：TP311.131[自动化与计算机技术—计算机软件与理论]