SkyHash: An evaluation algorithm for skyline queries over relational databases

Marlene Goncalves 1 , Maria E. Vidal 1
1Universidad Simón Bolívar, Departamento de Computación y Tecnología de la Información, Caracas, Venezuela
Autor de Correspondencia: mgoncalves@usb.ve

Ver Arhivo PDF

Resumen

Los lenguajes de consultas Skyline han sido definidos para permitir a los usuarios expresar sus criterios de preferencias. Una consulta Skyline recupera las tuplas no dominadas, es decir, un conjunto de tuplas tal que no existe otra tupla que sea mejor en todos los criterios de usuario. Distintas soluciones han sido propuestas para evaluar consultas Skyline. Esas soluciones pueden ser clasificadas en indexadas o de recorrido secuencial. Sin embargo, no tenemos conocimiento, de que exista alguna solución basada en Hashing. En este trabajo proponemos SkyHash, un algoritmo basado en Hash para consultas Skyline. SkyHash particiona los datos de acuerdo a una función hash y distribuye las tuplas no dominadas y algunas de sus dominadas en una misma partición dependiendo de los valores de la función hash. Así, una fase de filtrado puede ser ejecutada para descartar tuplas dominadas rápidamente. Empíricamente, estudiamos el comportamiento de SkyHash. Nuestros resultados iniciales muestran que el tiempo de SkyHash puede ser considerablemente menor que el tiempo de ejecución de los algoritmos del estado del arte.


Palabras claves:

SkyHash: An evaluation algorithm for skyline queries over relational databases

Marlene Goncalves 1 , Maria E. Vidal 1
1Universidad Simón Bolívar, Departamento de Computación y Tecnología de la Información, Caracas, Venezuela
Autor de Correspondencia: mgoncalves@usb.ve

Ver Arhivo PDF

Abstract

Skyline query languages have been defined to allow users to express their preference criteria. A Skyline query retrieves non-dominated tuples, i.e., a set of tuples such that does not exist another one that is better for all user criteria. Several solutions have been proposed in order to evaluate Skyline queries. These solutions can be classified as indexed or scan-based. To the best of our knowledge, none of the existing solutions are based on Hashing. In this work, we propose SkyHash, a hash-based algorithm for Skyline queries. SkyHash partitions the input data according to a hash function; it distributes non-dominated tuples and some of their dominated ones in the same partition depending on the hash function values. Thus, a filtering phase can be performed to discard dominated tuples quickly. Empirically, we study the behavior of SkyHash. Our initial results show that the execution time of SkyHash may be considerably less than the execution time of state-of-art algorithms.


Keywords: