From stars to galaxies: skyline queries on aggregate data
2013 (English)In: Proceedings of the 16th International Conference on Extending Database Technology, 2013, 477-488 p.Conference paper (Refereed)
The skyline operator extracts relevant records from multidimensional databases according to multiple criteria. This operator has received a lot of attention because of its ability to identify the best records in a database without requiring to specify complex parameters like the relative importance of each criterion. However, it has only been defined with respect to single records, while one fundamental functionality of database query languages is aggregation, enabling operations over sets of records. In this paper we introduce aggregate skylines, where the skyline works as a filtering predicate on sets of records. This operator can be used to express queries in the form: return the best groups depending on the features of their elements, and thus provides a powerful combination of grouping and skyline functionality. We define a semantics for aggregate skylines based on a sound theoretical framework and study its computational complexity. We propose efficient algorithms to implement this operator and test them on real and synthetic data, showing that they outperform a direct SQL implementation of up to two orders of magnitude.
Place, publisher, year, edition, pages
2013. 477-488 p.
IdentifiersURN: urn:nbn:se:uu:diva-204583DOI: 10.1145/2452376.2452432ISBN: 978-1-4503-1597-5OAI: oai:DiVA.org:uu-204583DiVA: diva2:640594