Circuitos Bowleanos

(1) Computación de Queries a Bases de Datos Relacionales
utilizando Circuitos Booleanos


Gagliardi, Edilma Olinda

Grosso, Alejandro Leonardo

Pereyra, Sonia Raquel
Piffaretti, Patricia

Turull Torres, José María *



{oli, agrosso, turull } @unsl.edu.ar

Universidad Nacional de San Luis
Facultad de Ciencias Físico, Matemáticas y Naturales
Departamento de InformáticaEjército de Los Andes 950
San Luis



ABSTRACT

En este trabajo se muestra la utilización de Subfamilias Finitas de Circuitos Booleanos como un modelo teórico adecuado para la expresión de consultas a una Base de Datos Relacional, cuyo fundamento se basa en la equivalencia demostrada entre Lógica de Primer Orden y una clase restringida de familias de Circuitos Booleanos.
Se destacaun aspecto relevante que surge de utilizar los Circuitos Booleanos para la expresión de consultas a Bases de Datos Relacionales, puesto que constituyen un formalismo apropiado para apreciar la paralelizabilidad de las mismas. También se observa que al considerar aquellas aplicaciones en donde el dominio de la base de datos es fijo, y que se conoce que no se producirán alteraciones sobre la mismaque le modifiquen, conforman casos apropiados para definir consultas a priori expresadas utilizando los Circuitos Booleanos, con el fin de implementarlas a nivel de hardware.
Se describe la implementación de un traductor de consultas expresadas en Lógica de Primer Orden a una Subfamilia Finita de Circuitos Booleanos para una Base de Datos Relacional dada; y la implementación de unevaluador de la consulta expresada como una Subfamilia Finita de Circuitos Booleanos.




PALABRAS CLAVES

Bases de Datos Relacionales, Circuitos Booleanos, Queries, Queries Computables, Lógica de Primer Orden, Cálculo Relacional, Cálculo Proposicional.









* Universidad Nacional de San Luis; Universidad Tecnológica Nacional (FRBA); Subsidio de Universidad CAECEINTRODUCCIÓN


A partir de la traducción demostrada en [DENENBERG 86] entre Lógica de Primer Orden (FO) y una clase restringida de familias de Circuitos Booleanos de tamaño polinomial y profundidad constante (AC0), es posible concebir la utilización de Subfamilias Finitas de Circuitos Booleanos [BALCAZAR 88] como un formalismo adecuado para la expresión de consultas a una Base de DatosRelacional. Allí se muestra cómo realizar la traducción de sentencias expresados en FO a Subfamilias Finitas de Circuitos Booleanos, cuando se considera la axiomatización de clases de estructuras finitas en FO. En el presente trabajo se extiende la traducción a la clase de todas las fórmulas bien formadas en FO, incluyendo no sólo sentencias sino también fórmulas con variables libres.
Un aspectorelevante que resulta al considerar los Circuitos Booleanos como un formalismo para la expresión de consultas a Bases de Datos Relacionales, es que constituyen un modelo teórico adecuado para apreciar la paralelizabilidad de la misma. Esto surge cuando se analiza la relación entre tamaño y profundidad de los circuitos que conforman la familia de circuitos que expresa la consulta y que puedeinfluir en la utilización de computación paralela.
El desarrollo e implementación del presente trabajo consta de dos partes. La primera consiste de un traductor de consultas expresadas en FO (equivalente al Cálculo Relacional orientado a Dominios), a una Subfamilia Finita de Circuitos Booleanos representada en la codificación denominada Standard [BALCAZAR 88] para cada base de datos relacionaldada. La segunda componente es un evaluador, en el cual dada una instancia de base de datos y la consulta expresada como una Subfamilia Finita de Circuitos Booleanos, computa la consulta correspondiente.
Los Circuitos Booleanos considerados aquí, son con grado de entrada limitado a una o dos entradas (bounded fan-in); y con grado de salida limitado a uno (bounded fan-out), obteniéndose...