Un sistema de bases de datos deductivas con restricciones

Abstract

Las fórmulas de Harrop hereditarias con restricciones se han usado como base para lenguajes de programación lógica. Al igual que la programación lógica da soporte a lenguajes de bases de datos deductivas como Datalog (con restricciones), este marco se usa como base para un sistema de bases de datos deductivas que mejora la expresividad de los sistemas aparecidos hasta el momento. En este trabajo, en primer lugar, se hace una comparativa entre distintos sistemas de bases de datos deductivas, así como de sistemas de bases de datos con restricciones. Más adelante se muestran los resultados teóricos que fundamentan el lenguaje HH¬(C) y una implementación concreta de este esquema que demuestra la viabilidad y expresividad del esquema. Las principales aportaciones con respecto a Datalog son el uso de consultas hipotéticas y cuantificadores universales. El sistema está diseñado de forma que soporta diferentes dominios de restricciones. La implementación incluye diferentes dominios concretos y también funciones de agregación que son habituales en otros lenguajes de bases de datos. El significado del lenguaje se define mediante una semántica de pruebas y el mecanismo operacional se define mediante una semántica de punto fijo que es correcta y completa con respecto a la primera. La semántica de punto fijo fundamenta la implementación del sistema. Para el cómputo de las consultas hipotéticas y de las funciones de agregación se hace uso de una noción de grafo de dependencias más compleja que la que usa Datalog. Este grafo de dependencias se utiliza para definir una estratificación para la base de datos. Además se debe tener en cuenta que la implementación debe estar diseñada contando con el posible crecimiento temporal de la base de datos debido a las consultas hipotéticas. Finalmente se presentan ejemplos del sistema que muestran la expresividad del lenguaje. [ABSTRACT] Hereditary Harrop formulas with constraints have been proposed as a basis for logic programming languages. In the same way that Datalog (with constraints) emerges from logic programming as a deductive database language, such formulas can support a very expressive framework for deductive databases. This work first presents a comparison between deductive database systems and constraint databases. Then, it presents the theoretical foundations of the HH¬(C)language and an implementation that shows the viability and expressive power of the proposal. The main contributions with respect to Datalog are the addition of hypothetical queries and universal quantications. The language is designed in a exible way in order to support different constraint domains. The implementation includes several domain instances, and it also supports aggregates as usual in database languages. The formal semantics of the language is defined by a proof-theoretic calculus, and for the operational mechanism we use a stratified fixpoint semantics, which is proved to be sound and complete w.r.t. the former. The resulting fixpoint semantics constitutes a suitable foundation for the system implementation. Hypothetical queries and aggregates require a more elaborated notion of dependency graph than the common one used in Datalog, which yields to an original stratification for databases. Moreover, the first one demands a sophisticated mechanism that implies a temporary, dynamic grow of the database. Finally, some concrete examples for the system for showing the expresivity of the proponsal are presented.