stringtranslate.com

Evaluación de consultas

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 .

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:

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

  1. ^ 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.
  2. ^ 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.
  3. ^ 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.