Evaluación de consultas

En la teoría de bases de datos , el problema de evaluación de consultas es el problema ^{[ 1 ]} 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 sobre bases de datos, en particular sobre 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 sobre la que se debe responder. El resultado del problema es el conjunto de respuestas a la consulta en la base de datos. Si las consultas son booleanas , es decir, 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 suele plantear para una clase específica de consultas y bases de datos. Por ejemplo, un ejemplo del 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, ^{[ 2 ]} para tener en cuenta el hecho de que las dos entradas del problema son diferentes:

• La complejidad combinada del problema de evaluación de consultas es su complejidad computacional cuando se mide en función de las dos entradas, es decir, la consulta y la base de datos, como es habitual en la complejidad computacional.
• La complejidad de datos es la complejidad computacional cuando la consulta es fija y la entrada es simplemente la base de datos. Por ejemplo, decimos que la evaluación de una consulta tiene una complejidad de datos polinomial para una clase de consultas si, para cada consulta fija Q de esa clase, dada una base de datos D , podemos calcular las respuestas a Q en D en tiempo polinomial.
• Con menos frecuencia, podemos estudiar la complejidad de la consulta , que es la complejidad computacional cuando la base de datos es fija y la entrada es solo la consulta. Esto también se denomina complejidad de la expresión . ^{[ 3 ]}

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 regulares , etc., hasta formalismos lógicos como la lógica de primer orden o la lógica monádica de segundo orden .

Por ejemplo, para consultas conjuntivas booleanas , la complejidad de la evaluación de la consulta es polinómica en 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 ^{[ 4 ]} por una reducción de la 3-colorabilidad . ^{[ 5 ]}

La complejidad de la evaluación de consultas puede estudiarse 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 como una consulta booleana para cada respuesta, entonces podemos reducir la evaluación de una consulta no booleana a un número polinomial de problemas de evaluación de consultas booleanas. ^{[ 6 ]}