Lenguajes de consulta de base de datos para consultas eficientes

9

Parece que en los lenguajes de consulta populares para bases de datos relacionales, es posible crear consultas que requerirán muchos recursos para responder. En la práctica, los administradores de bases de datos administran esto limitando la cantidad de memoria por consulta y verificando si hay consultas de larga duración si hay una desaceleración en la base de datos. Esto parece bastante ad-hoc, ¿hay una solución TCS para esto?

¿Existen lenguajes de consulta que solo pueden implementar consultas eficientes?

Si no hay tales idiomas, ¿hay alguna razón teórica para esto?

Algunas razones por las que podría esperar que este tipo de cosas existan o al menos tengan sentido:

  • Tenemos lenguajes de programación que están específicamente diseñados para implementar solo cálculos eficientes (generalmente al tener cierta lógica restrictiva en su sistema de tipos)
  • los lenguajes de consulta populares (como SQL) ya están inspirados en la lógica, por lo que no parece una exageración para los usuarios de bases de datos considerar lógicas más restrictivas.
  • un usuario de base de datos no malintencionado ya intenta preparar consultas que se ejecutan rápidamente, por lo que deberíamos esperar que estos lenguajes de consulta más restrictivos solo obstaculicen a los usuarios maliciosos.

Esta pregunta está inspirada en la intersección de dos preguntas anteriores:

Lenguajes de programación para computación eficiente

¿Por qué funcionan las bases de datos relacionales, dada la complejidad exponencial teórica de la búsqueda de respuestas (en el tamaño de la consulta)?

cc.complexity-theory pl.programming-languages db.databases finite-model-theory Artem Kaznatcheev
fuente
1
¿No es este exactamente el tema de la complejidad descriptiva? tienen caracterizaciones de lenguaje de consultas para varias clases de complejidad.
Kaveh
La complejidad descriptiva es definitivamente una gran parte y guía para los lenguajes de programación para una computación eficiente. Pero no creo que sea tan simple como decir "la complejidad descriptiva usa la lógica" y "las consultas a las bases de datos usan la lógica". En particular, para DC parece que el tamaño de la consulta es fijo y la 'n' proviene del tamaño de las estructuras finitas que aceptan esas consultas. En las bases de datos, el tamaño de la consulta es realmente variable y la base de datos también es variable o quizás un parámetro fijo.
Artem Kaznatcheev
3
También hay resultados para consultas variables, simplemente no son tan sorprendentes como la coincidencia entre la comprobación de modelos y las clases de complejidad bien conocidas. Además, el campo más amplio de la teoría de modelos finitos, de la que forma parte la complejidad descriptiva, tiene varios resultados de expresibilidad directamente relacionados con las bases de datos. Las bases de datos son, después de todo, estructuras teóricas de modelos casi exactamente finitos.
Marc Hamann
1
No pensé en esta correspondencia. Agregué la etiqueta de teoría de modelos finitos. Si usted o @Kaveh desea elaborar sus comentarios y saber cómo adoptar resultados específicos de la complejidad descriptiva de la teoría de modelos finitos en general para producir dichos lenguajes de consulta, ¡realmente me gustaría ver esa respuesta!
Artem Kaznatcheev

Respuestas:

7

Una forma de ver los lenguajes de consulta de la base de datos es a través de la lente de las bases de datos deductivas , donde las consultas se representan como programas lógicos. En esta configuración, el trabajo más relevante relacionado con su pregunta es el análisis de complejidad de los análisis estáticos de McAllester , que observó que puede razonar sobre el tiempo de ejecución de una consulta razonando sobre el número de "disparos de prefijo" en las reglas de su programa. Lo que es un "disparo de prefijo" no es terriblemente complicado, pero lo remitiré al periódico para eso.

En el mundo de la programación funcional, este tipo de cosas se llaman semántica de costos : no significa que solo pueda implementar consultas (programas) eficientes, sino que puede razonar sobre la complejidad asintótica de su programa declarativo de una manera razonable .

Algunos trabajos posteriores sobre implementaciones de las ideas de McAllester incluyen desde reglas de registro de datos hasta programas eficientes con garantías de tiempo y espacio (Liu y Stoller) y Dedalus: registro de datos en tiempo y espacio (Alvaro, Marczak, Conway, Hellerstein, Maier y Sears). Sin embargo, admito que aún no he leído el último de esos dos documentos.

Rob Simmons
fuente