关键词: 非完整数据库, Skyline-join查询, 概率Skyline

Abstract: Traditional Skyline-join queries are only available for complete databases. As new application requirements arise, Skyline-join queries in incomplete databases are required in the actual application. Probabilistic Skyline uses probability values to represent the dominance relationship between incomplete tuples, which avoids the issue of dominance loss in the traditional incomplete database Skyline query. Since probabilistic Skyline can’t deal with multi-relational queries, the definition of probability Skyline is extended to make it suitable for multi-relational queries, and the PSkyline-join algorithm based on multi-level grouping is proposed. Firstly, the algorithm performs multi-level grouping on each relation based on the join key value and the missing bitmap. Next, the local Skyline probability upper bound of each group of data items is calculated. After that, the tuples are connected and the global Skyline probability upper bound of the tuples is updated. Finally, two kinds of pruning strategies are designed by using the global Skyline probability upper bound and the global Skyline probability lower bound to efficiently?calculate the global probabilistic Skyline results. Experimental results on the simulated data set demonstrate that PSkyline-join algorithm is tens of times faster than the traditional algorithm.

Key words: incomplete database, Skyline-join queries, probabilistic Skyline