Paper 3

A Partitioning Approach for Skyline Queries in Presence of Partial and Dynamic Orders

Authors: Karim Alami, Sofian Maabout

Volume 49 (2021)

Abstract

Consider the case of tourists looking for flight tickets. While one may assume that every tourist does prefer lower price, the preference among the airline companies is on the one hand partial, i.e., some companies may be incomparable, and on the other hand, it is dynamic in the sense that users have different preferences among the companies. In this paper, we address the problem of answering skyline queries in the presence of such partially and dynamically ordered attributes. The main idea of our solution consists in decomposing each query into a set of independent sub-queries with respect to the user’s preference. Our contribution is twofold: (i) we propose an algorithm exploiting the above property to evaluate skyline queries on the fly and (ii) a pre-materialization of some sub-queries in order to optimize a query workload. We demonstrate empirically the efficiency of our proposals regarding its direct competitors.

Keywords: Skyline queries, Partial and dynamic order, Data partitioning, Materialization.