Efficient Computation of Skyline Queries Over a Dynamic and Incomplete Database

Skyline queries rely on the notion of Pareto dominance, filter the data items by keeping only those data items that are the best, most preferred, also known as skylines, from a database to meet the user's preferences. Skyline query has been studied extensively and a significant number of skyline algorithms have been proposed, mostly attempt to resolve the optimisation problem that is mainly associated with a reduction in the processing time of skyline computations. In today's era, the presence of incomplete data in a database is inevitable. Furthermore, databases are dynamic in nature in which their states change throughout the time to reflect the current and latest information of the applications. The skylines derived before changes are made towards the initial database are no longer valid in the new state of the database. Blindly examining the entire database to identify the new set of skylines is unwise as not all data items are affected by the changes made towards the database. Hence, in this paper we propose a solution, named DyIn-Skyline, which is capable of deriving skylines over a dynamic and incomplete database, by exploiting only those data items that are affected by the changes. Several experiments have been conducted and the results show that our proposed solution outperforms the previous works with regard to the number of pairwise comparisons and processing time.