Skyline and mapping aware join query evaluation

Growing interests in multi-criteria decision support applications have resulted in a flurry of efficient skyline algorithms. In practice, real-world decision support applications require to access data from disparate sources. Existing techniques define the skyline operation to work on a single set, and therefore, treat skylines as an “add-on” on top of a traditional Select-Project-Join query plan. In many real-world applications, the skyline dimensions can be anti-correlated such as the attribute pair {price, mileage} for cars and {price, distance} for hotels. Anti-correlated data are particularly challenging for skyline evaluation and therefore have commonly been ignored by existing techniques. In this work, we propose a robust execution framework called SKIN to evaluate skyline over joins. The salient features of SKIN are: (a) effective in reducing the two primary costs, namely the cost of generating the join results and the cost of dominance comparisons to compute the final skyline of join results, (b) shown to be robust for both skyline-friendly (independent and correlated) as well as skyline-unfriendly (anti-correlated) data distributions. SKIN is effective in exploiting the skyline knowledge in both local within individual data sources and across disparate sources—to significantly reduce the above-mentioned costs incurred during the evaluation of skyline over join. Our experimental study demonstrates the superiority of our proposed approach over state-of-the-art techniques to handle a wide variety of data distributions.

► We propose a robust execution framework called SKIN to evaluate skyline over joins.
► Performing query evaluation at various levels of abstraction enables SKIN to reduce the total number of join results generated and number of dominance comparisons need to compute the skyline results.
► Looking ahead into the mapped output space and facilitates SKIN to exploit this knowledge at the level of both individual sources and the complete query.
► SKIN is robust for both skyline-friendly (independent and correlated) as well as skyline-unfriendly (anti-correlated) data distributions.