En teoría de bases de datos , el problema de evaluación de consultas es el problema [ verificación necesaria ] de determinar las respuestas a una consulta en una base de datos. La investigación en teoría de bases de datos tiene como objetivo determinar la complejidad computacional de responder a diferentes tipos de consultas en bases de datos, en particular en bases de datos relacionales .
El problema de evaluación de consultas toma dos entradas: la consulta que se va a responder y la base de datos en la que se va a responder. La salida del problema es el conjunto de respuestas a la consulta en la base de datos. Si las consultas son consultas booleanas , es decir, consultas que tienen una respuesta de sí o no (por ejemplo, consultas conjuntivas booleanas ), entonces el problema de evaluación de consultas es un problema de decisión .
El problema de evaluación de consultas se plantea generalmente para una clase específica de consultas y bases de datos. Por ejemplo, un ejemplo de problema de evaluación de consultas sería el problema de evaluar una consulta conjuntiva en una base de datos relacional .
La complejidad computacional del problema se puede medir de diferentes maneras, [1] para tener en cuenta el hecho de que las dos entradas del problema son diferentes:
La complejidad de la evaluación de consultas se puede estudiar para varias clases de consultas, por ejemplo, consultas acíclicas, consultas conjuntivas , uniones de consultas conjuntivas , Datalog, consultas de ruta regular , etc., hasta formalismos lógicos como la lógica de primer orden o la lógica monádica de segundo orden .
Por ejemplo, para las consultas conjuntivas booleanas , la complejidad de la evaluación de la consulta es polinómica en cuanto a la complejidad de los datos: incluso cae en la clase AC0 . Por el contrario, la complejidad de la consulta y la complejidad combinada son NP-completas [3] por una reducción de la 3-colorabilidad . [ cita requerida ]
La complejidad de la evaluación de consultas se puede estudiar para consultas que devuelven respuestas o para consultas booleanas (consultas de sí/no). Sin embargo, a menudo podemos reducirla al caso de consultas booleanas. Más específicamente, si el número de respuestas a la consulta es siempre polinomial en el tamaño de la base de datos, y si podemos reescribir la consulta a una consulta booleana para cada respuesta, entonces podemos reducir la evaluación de consultas para una consulta no booleana a un número polinomial de muchos problemas de evaluación de consultas booleanas. [ cita requerida ]