Chase of datalog programs and its application to solve the functional dependencies implication problem

Abstract

[Resumen]Esta tesis presenta resultados en dos áreas principales. Por un lado se presentan resultados en el área de optimización de consultas recursivas (programas datalog recursivos lineales) en sistemas de gestión de bases datos deductivas (o convencionales pero que cumplan las especificaciones de SQL99) y por otro se presentan resultados en la implicación de dependencias funcionales en el modelo de datos deductivo.

Para la optimización de programas recursivos lineales la aproximación adoptada es la de la optimización semántica de consultas que consiste en la utilización de las restricciones, que cumplen las bases de datos sobre las que se ejecutan las consultas, para obtener un programa más eficiente de evaluar. En concreto, se presentan dos algoritmos para la optimización de programas de datolg recursivos lineales cuando la base de datos sobre la que se ejecutan las consultas cumple un conjunto de dependencias funcionales.

El primero se denomina chase de programas datalog y el segundo se denomina cyclic chase de programas datalog. Ambos algortimos persiguen el mismo objetivo (pero siguiendo dos aproximaciones ligeramente distintas), esto es, a partir de un progrma datalog recursivo lineal P y un conjunto de dependencias funcionales F, los dos algoritmos obtienen un programa P' que es equivalente a P cuando ambos (P y P') son evaluados sobre bases de datos que cumplen las dependencias funcionales F.

Los dos algoritmos se basan en la utilización del chase, un procedimiento que originalmente se desarrolló para comprobar si una descomposición (de una relación universal) en distintas relaciones tenía pérdida de información o no. Los dos algoritmos utilizan la idea básica del chase (la igualación de variables siguiendo las dependencias funcionales) para la igualación de variables dentro de los programas datalog.