Linguagens de consulta de banco de dados para consultas eficientes

9

Parece que em linguagens de consulta populares para bancos de dados relacionais, é possível criar consultas que exigirão muitos recursos para serem respondidas. Na prática, os administradores de banco de dados gerenciam isso limitando a quantidade de memória por consulta e verificando se há consultas de longa duração, se houver uma desaceleração no banco de dados. Isso parece bastante ad-hoc, existe uma solução TCS para isso?

Existem linguagens de consulta que podem implementar apenas consultas eficientes?

Se não existem tais idiomas, existe uma razão teórica para isso?

Algumas razões pelas quais eu poderia esperar que esse tipo de coisa exista ou pelo menos fazem sentido:

  • temos linguagens de programação projetadas especificamente para implementar apenas cálculos eficientes (geralmente com uma lógica restritiva no sistema de tipos)
  • linguagens de consulta populares (como SQL) já são inspiradas pela lógica, portanto, não parece um exagero para os usuários do banco de dados considerar lógicas mais restritivas.
  • um usuário de banco de dados não malicioso já tenta preparar consultas que são executadas rapidamente, portanto, devemos esperar que essas linguagens de consulta mais restritivas prejudiquem apenas usuários mal-intencionados.

Esta pergunta é inspirada na interseção de duas perguntas anteriores:

Linguagens de programação para computação eficiente

Por que os bancos de dados relacionais funcionam, dada a complexidade exponencial teórica da busca de respostas (no tamanho da consulta)?

cc.complexity-theory pl.programming-languages db.databases finite-model-theory Artem Kaznatcheev
fonte
11
Não é esse exatamente o tópico da complexidade descritiva? eles têm caracterizações de linguagem de consultas para várias classes de complexidade.
Kaveh
A complexidade descritiva é definitivamente uma grande parte e guia para linguagens de programação para computação eficiente. Mas não acho que seja tão simples quanto dizer "complexidade descritiva usa lógica" e "consultas a bancos de dados usam lógica". Em particular, para DC, parece que o tamanho da consulta é fixo e o 'n' vem dos tamanhos de estruturas finitas que essas consultas aceitam. Nos bancos de dados, é realmente o tamanho da consulta que é variável e o banco de dados também é variável ou talvez um parâmetro fixo.
Artem Kaznatcheev
3
também existem resultados para consultas variáveis, elas simplesmente não são tão surpreendentes quanto a correspondência entre a verificação de modelo e as classes de complexidade conhecidas. Além disso, o campo mais amplo da teoria dos modelos finitos, da qual a complexidade descritiva faz parte, possui vários resultados de expressibilidade diretamente relacionados aos bancos de dados. Afinal, os bancos de dados são estruturas teóricas de modelos quase exatamente finitas.
Marc Hamann
11
Eu não pensei sobre essa correspondência. Eu adicionei o tag finito da teoria dos modelos. Se você ou o @Kaveh quiser elaborar seus comentários e saber como adotar resultados específicos da complexidade descritiva da teoria dos modelos finitos em geral para produzir essas linguagens de consulta, eu realmente gostaria de ver essa resposta!
Artem Kaznatcheev

Respostas:

7

Uma maneira de analisar as linguagens de consulta de banco de dados é através das lentes de bancos de dados dedutivos , onde as consultas são representadas como programas lógicos. Nessa configuração, o trabalho mais relevante relacionado à sua pergunta é Sobre a análise de complexidade das análises estáticas de McAllester , que observou que você pode raciocinar sobre o tempo de execução de uma consulta, raciocinando sobre o número de "disparos de prefixo" nas regras do seu programa. O que é um "disparo de prefixo" não é terrivelmente complicado, mas vou lhe referir o artigo para isso.

No mundo da programação funcional, esse tipo de coisa é chamada de semântica de custos : não significa que você pode implementar apenas consultas (programas) eficientes, mas significa que você pode raciocinar sobre a complexidade assintótica de seu programa declarativo de uma maneira razoável. .

Alguns trabalhos posteriores sobre a implementação das idéias de McAllester incluem: desde regras de registro de dados até programas eficientes com garantias de tempo e espaço (Liu e Stoller) e Dedalus: Registro de dados no tempo e no espaço (Alvaro, Marczak, Conway, Hellerstein, Maier e Sears). Admito que ainda não li o último desses dois trabalhos.

Rob Simmons
fonte