Aproximaciones eficientes de consultas conjuntivas

Abstract

Cuando encontrar la respuesta exacta a una consulta sobre una base de datos muy grande es intratable, es natural aproximar la consulta por otra más eficiente que pertenezca a una clase con buenas cotas en la complejidad de evaluación de consultas. En esta tesis estudiamos tales aproximaciones para consultas conjuntivas. Estas consultas son de especial interés en base de datos, y además sabemos muy bien qué clases de consultas admiten una evaluación eficiente, como las consultas acíclicas, o las de (hyper)treewidth acotado. Definimos una aproximación a una consulta Q como una consulta de una de esas clases que discrepa con Q lo menos posible. Nos concentramos en aproximaciones que siempre entregan respuestas correctas. Probamos que para las clases tratables de consultas conjuntivas mencionadas anteriormente, siempre existen aproximaciones y sus tamaños son a lo más polinomiales en el tamaño de la consulta original. Esto se sigue de resultados generales obtenidos que relacionan propiedades de clausura de clases de consultas conjuntivas con la existencia de aproximaciones. Además, probamos que en muchos casos el tamaño de la aproximación es a lo más el tamaño de la consulta original. Presentamos una serie de resultados sobre cómo ciertas propiedades combinatoriales de las consultas afectan a sus aproximaciones y estudiamos cotas en la cantidad de aproximaciones, al igual que la complejidad de encontrar e identificar aproximaciones. Finalmente, consideramos aproximaciones que entregan todas las respuestas correctas y estudiamos sus propiedades.