Beyond Skyline and Ranking Queries: Restricted Skylines
Paolo Ciaccia, Davide Martinenghi · Archivio istituzionale della ricerca (Alma Mater Studiorum Università di Bologna) · 2018
Traditionally, skyline and ranking queries have been treated separately as alternative ways of discovering interesting data in potentially large datasets.While ranking queries adopt a specific scoring function to rank tuples, skyline queries return the set of non-dominated tuples and are independent of attribute scales and scoring functions.Ranking queries are thus less general, but cheaper to compute and widely used.In this paper, we integrate these two approaches under the unifying framework of restricted skylines by applying the notion of dominance to a set of scoring functions of interest.Table 1: Pros and cons of multi-objective optimization approaches.Evaluation criteria ↓ Queries → Ranking Lexicographic Skyline Simplicity of formulation No Yes Yes Overall view of interesting results No No Yes Control of result cardinality Yes Yes No Trade-off among attributes Yes No No Relative importance of attributes Yes Yes NoRanking queries heavily depend on the particular choice of weights in the scoring function, and thus fail to offer an overall view of the dataset.Lexicographic queries enforce a linear priority between attributes, thus even the smallest difference in the most important attribute cannot be compensated by the other attributes (a problem inherited by newer approaches, such as pskylines [5]).Skyline queries provide a good overview of potentially interesting tuples, but may contain too many objects.