Un modelo de flujo de datos para la evaluación de consultas en bases de datos deductivas

Abstract

El presente trabajo estudia la evaluación paralela y distribuida de consultas Datalog con negación estratificada, Utiliza un modelo computacional de flujo de datos que emplea para obtener resultados tanto en la evaluación como en la optimización por reescritura de consultas Datalog. Desde el punto de vista de la evaluación, se ofrece un algoritmo que, al eliminar cómputos redundantes que aún están presentes en la evaluación desarrollada por el algoritmo Semi-Ingenuo, produce una evaluación más eficiente que la desarrollada mediante éste. Por otro lado, el modelo computacional de flujo de datos permite la descomposición funcional del programa sin por ello introducir nuevas fuentes de ineficiencia en la evaluación. Por último, se desarrollan dos nuevos algoritmos de optimización de consultas que mejoran a los actualmente descritos en la literatura, extendiéndolos con nuevas transformaciones que permiten optimizaciones adicionales. Estos algoritmos no solo consideran información sintactica, sino que también utilizan con provecho las restricciones de integridad semántica existentes en la base de datos.