Una Extensión al Optimizador de PostgreSQL para Consultas Skyline

Fabiola R. Di Bartolo L. 1
1Departamento de Computación y Tecnología de la Información, Universidad Simón Bolívar, Caracas, Venezuela
Autor de Correspondencia: fabiola@gia.usb.ve

Ver Arhivo PDF

Resumen

Las consultas Skyline han surgido como una respuesta a la necesidad de resolver consultas que involucran preferencias de usuarios. El Skyline resuelve las preferencias estableciendo un orden parcial entre las tuplas inducido por los criterios de preferencias de usuario. Diversos trabajos sobre la optimización de consultas Skyline han sido presentados debido a que el conjunto Skyline puede ser pequeño con respecto al conjunto de datos de entrada. En este trabajo, se describe una extensión a PostgreSQL que incorpora dos algoritmos de optimización de consultas Skyline, denominados dPeaQock y ePeaQock, los cuales están basados en programación dinámica y algoritmos evolutivos, respectivamente. Nuestro estudio experimental confirma que los algoritmos propuestos presentan un comportamiento adecuado sobre datos sintéticos y reales.


Palabras claves:

A PostgreSQL Optimizer Extension for Skyline Queries

Fabiola R. Di Bartolo L. 1
1Departamento de Computación y Tecnología de la Información, Universidad Simón Bolívar, Caracas, Venezuela
Autor de Correspondencia: fabiola@gia.usb.ve

Ver Arhivo PDF

Abstract

Skyline queries have emerged as an answer to necessity of solving queries that involve user preferences. The Skyline solves preferences establishing a partial order between the tuples induced by user's preference criteria. Several works about optimization of Skyline queries have been presented due to Skyline set may be small with respect to the input data set. In this work, we describe a PostgreSQL extension that incorporates two optimization algorithms of Skyline queries, called dPeaQock and ePeaQock, which are based on Dynamic Programming and Evolutionary Algorithms, respectively. Our experimental study confirms that the proposed algorithms present an adequate behavior over synthetic and real data.


Keywords: