Probabilistic Aggregate Skyline Join Queries: Skylines with Aggregate Operations over Existentially Uncertain Relations

The multi-criteria decision making, made possible by the advent of skyline queries, has been successfully applied in many areas. Though most of the earlier work is concerned with only a single relation, several real world applications require finding the skyline set over multiple relations. Consequently, the join operation over skylines where the preferences are local to each relation and/or on aggregated values of attributes from different relations, has been proposed. In the meanwhile, uncertain datasets are witnessing increasing applications in many scientific and real-life situations. The problem of skyline computation for such datasets becomes even more challenging as every object can be classified as a skyline with some probability. In this paper, we introduce probabilistic aggregate skyline join queries (PASJQ) that ask for objects whose probability of being a skyline from a join of two uncertain relations is over a query probability threshold. The skyline preferences are on both local and aggregate attributes. Since the naive algorithm can be impractical, we propose three algorithms to efficiently process such queries. The algorithms process the skylines as much as possible locally before computing the join to reduce the computation burden of finding skylines from the larger joined relation. Experiments with real and synthetic data exhibit the practicality and scalability of these algorithms with respect to query probability threshold, cardinality, dimensionality and other parameters of the uncertain relations.