Computación paralela de queries expresados con circuitos booleanos

Abstract

Este trabajo se encuadra como una etapa de un proyecto mayor, en el que utilizamos los circuitos booleanos como un modelo teórico adecuado para la expresión de consultas a una base de datos relacional, estudiando diferentes aspectos de relevancia; en este caso, el grado de paralelización que poseen las mismas. Para ello, consideramos la equivalencia entre lógica de primer orden y una clase restringida de familias de circuitos booleanos. Presentamos cómo transformar una consulta dada a otra equivalente, ambas expresadas en lógica de primer orden, de modo tal que traducida a una subfamilia finita de circuitos booleanos, resulte apropiada para el uso de recursos de paralelismo. Analizamos la profundidad de los circuitos booleanos. Para ello trabajamos sobre los árboles de expresión de las fórmulas, buscando transformaciones sobre los mismos para lograr mínima profundidad en los circuitos booleanos asociados.