Computación de queries a bases de datos relacionales utilizando circuitos booleanos

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 destaca un 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 misma que 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 un evaluador de la consulta expresada como una Subfamilia Finita de Circuitos Booleanos.