Implementación de un lenguaje de consultas utilizando lógica de primer orden con cuantificadores de punto fijo

Abstract

En este trabajo se considera una extensión de la Lógica de Primer Orden, con distintos tipos de cuantificadores de punto fijo, para expresar consultas a Bases de Datos relacionales permitiendo distintos tipos de iteraciones ausentes en primer orden. Esta extensión fue propuesta en [AVV97]. La motivación es que la Lógica de Primer Orden no permite la expresión de ciertos tipos de consultas a Bases de Datos, como quedó demostrado en [CH80]. Por ello intentamos continuar ampliando su poder expresivo para cubrir una mayor parte del conjunto de consultas posibles de computar sobre una Base de Datos. Con esta extensión se pueden realizar consultas a Bases de Datos que están en la clase EXPTIME. Se muestran aquí algunos aspectos importantes de la implementación de dicho lenguaje, como así también justificación de cotas obtenidas o establecidas. Con este trabajo se contribuye al análisis de distintos tipos de formalismos, con diferentes grados de expresividad para formular consultas a Bases de Datos relacionales.