基于连接操作的反轮廓查询处理算法  

Reverse Skyline Query Processing Algorithms Over Joins

作　　者：信俊昌[1] 王培[1] 王之琼[1,2] 王国仁[1] 郭欣宇[2] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110819 [2]东北大学中荷生物医学与信息工程学院,沈阳110819

出　　处：《小型微型计算机系统》2014年第10期2249-2255,共7页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61100022)资助

摘　　要：反轮廓查询在制定有效的市场决策方面具有重要的作用.随着信息量的增加,数据库中跨表的数据查询变得十分普遍.深入分析了基于数据表连接操作的反轮廓查询处理的性质,结合网格索引结构和两种提前终止策略,提出基本反轮廓连接查询算法(Basic Reverse Skyline Join Algorithm,BRSJ),并通过将半支配操作提至连接操作之前对算法进行了改进,提出改进的反轮廓连接算法(Progressive Reverse Skyline Join Algorithm,PRSJ).实验结果表明,两种提前终止策略可以有效的减少数据访问量,两种算法均能获得很高的性能,并且后者在时间性能上更优于前者.两个算法都大大提高了基于连接操作的反轮廓查询处理的性能.As an important operator for multiple criteria decision making,reverse skyline query processing plays a very important role in market decisions. Given the reason that the amount of information is enormous, the relevant data are mostly built in several data ta- bles. As a result, data query processing among multiple data tables have been commonly used and popular in the data applications. In this paper, the property of reverse skyline query processing algorithms over joins is firstly analyzed, followed by the proposition of two kinds of early termination strategies are discussed. Then, Basic Reverse Skyline Join Algorithm （BRSJ } and Progressive Reverse Sky- line Join Algorithm { PRSJ } are proposed. The first one reduces data visits and put an early end to access the whole dataset by the grid index and these kinds of early termination strategies. And the second one that based on the semi-dominance operator which is put for- ward advanced to join. Finally, our extensive simulation studies showed that both early termination strategies are effective. Also no matter BRSJ and PRSJ can effectively reduce the data visit among multiple data tables, especially, PRSJ is better than BRSJ on time. Both of the algorithms can improve the performance of operator based on join.

关 键 词：连接 反轮廓查询处理 网格索引 半支配 

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