Hispanopedia WikiEn 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 .
Definición formal
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 combinada del problema de evaluación de consultas es su complejidad computacional cuando se mide como una 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 los datos es la complejidad computacional cuando la consulta es fija y cuando la entrada es solo la base de datos. Por ejemplo, decimos que la evaluación de consultas tiene una complejidad de datos en tiempo polinomial para una clase de consultas si, para cada consulta fija Q en 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 cuando la entrada es solo la consulta. Esto también se denomina complejidad de expresión . [2]
Clases de consulta
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 ]
Consultas booleanas y no booleanas
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 ]
Referencias
- ^ Vardi, Moshe Y. (5 de mayo de 1982). "La complejidad de los lenguajes de consulta relacionales (resumen ampliado)". Actas del decimocuarto simposio anual de la ACM sobre teoría de la computación - STOC '82 . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 137–146. doi :10.1145/800070.802186. ISBN 978-0-89791-070-5.
- ^ Abiteboul, Serge; Hull, Richard; Vianu, Victor (2 de diciembre de 1994). Fundamentos de bases de datos: el nivel lógico (1.ª ed.). Reading, Mass.: Pearson. ISBN 978-0-201-53771-0.
- ^ Greco, Gianluigi; Scarcello, Francesco (18 de junio de 2014). "Conteo de soluciones para consultas conjuntivas: Tratabilidad estructural e híbrida". Actas del 33.° simposio ACM SIGMOD-SIGACT-SIGART sobre Principios de sistemas de bases de datos . PODS '14. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 132–143. doi :10.1145/2594538.2594559. ISBN 978-1-4503-2375-8.