一种ρ-支配轮廓查询的高效处理算法

An Efficient Processing Algorithm for ρ-Dominant Skyline Query

近年来,作为重要的多目标决策手段的轮廓查询逐渐得到学术界的重视,相继提出了基于不同支配关系的多种轮廓变体查询.首先,通过对实际应用需求进行分析,提出了基于元组对应数值间比例值大小的ρ-支配关系的定义,进而提出了ρ-支配轮廓查询的概念.其次,对ρ-支配轮廓的基本性质进行了细致而深入的分析,在此基础上,提出了基于分支定界的ρ-支配轮廓查询算法(Branch and Boundρ-Dominant Skyline Algorithm,BBDS),避免了对R-树索引的多次访问,从而提高了ρ-支配轮廓查询的执行效率.最后,通过大量的仿真实验对ρ-支配轮廓查询的语义进行分析,并对BBDS算法的性能进行验证.实验结果表明,ρ-支配轮廓查询是轮廓查询语义的扩展和补充,而提出的BBDS算法则是求解ρ-支配轮廓查询的高效算法.

In recent years,as an important operator for multi-decision making,skyline query has attracted much attention from the academia gradually,and a variety of skyline variants based on different dominance relationships have been proposed successively by the database researchers.In this paper,firstly,through making the analysis of practical applications＇ requirements,the ρ-dominance relationship based on the ratio of corresponding values between the tuples is defined,and then the concept of ρ-dominant skyline query based on the ρ-dominance relationship is proposed.Next,by making a detailed and in-depth analysis of ρ-dominance＇s basic properties,a novel algorithm,named Branch and Bound ρ-Dominant Skyline Algorithm（BBDS）,is developed.The BBDS algorithm avoids visiting R-tree index too many times,which can improve the ρ-dominant skyline query implementation efficiency greatly.Finally,through a large number of simulation experiments,the semantic of the ρ-dominant skyline query is analyzed,and meanwhile the performance of BBDS algorithm is verified by the simulation experiments.The simulation experimental results show that ρ-dominant skyline query based on ρ-dominance relationship is a new extension and complement of the traditional skyline query semantic and the BBDS algorithm proposed in this paper is proved to be a highly effective algorithm for solving ρ-dominant skyline queries.