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

19

Parece sabido que, para encontrar uma resposta para uma consulta em um banco de dados relacional , é preciso tempo e não é possível se livrar do expoente.QD|D||Q||Q|

Como pode ser muito grande, nos perguntamos por que os bancos de dados funcionam na prática.D

É apenas uma questão de as consultas usuais não serem grandes nas aplicações do mundo real? (É interessante saber qual é o tamanho usual das consultas feitas aos sistemas de bancos de dados relacionais e qual é o tamanho "máximo" das consultas que devem ser efetivamente respondidas por um sistema de banco de dados na prática .)

Notas sobre o expoentenão `removível '|Q|

Para mostrar que o expoentenão é removível, pode-se usar uma consulta perguntando se existe um clique do tamanho no gráfico fornecido pelo banco de dados. Verificar se um gráfico tem um class é um problema NP-complete. Além disso, não é um parâmetro fixo tratável, com o parâmetro . Detalhes podem ser encontrados em, por exemplo, Libkin, L .: Elements Of Finite Model Theory. Springer (2004) ou Papadimitriou, CH, Yannakakis, M .: Sobre a complexidade das consultas ao banco de dados. J. Comput. Syst. Sci. 58 (3), 407-277 (1999)|Q|nnn


imz - Ivan Zakharyaschev
fonte
7
Consultas comuns (como SELECT * FROM users WHERE username="abc" AND passwrod="xyz") são pesquisas simples, que levam O (| D |) para serem executadas. Se houver um índice nos campos relevantes do banco de dados, será usado O (log | D |). Não gosto de bancos de dados, mas não acho que consultas mais complicadas levem um tempo exponencial.
MS Dousti
7
@imz: No seu exemplo, a complexidade é , que ainda é polinomial. Parece que, se houver k junções na consulta, a complexidade é O ( | D | k + 1 ) . Este é um polinômio para k fixo, mas acho que para k grande, a execução da consulta será muito lenta na prática. Portanto, é preciso evitar muitas junções a todo custo. O(|D|2)O(|D|k+1)
MS Dousti
7
A complexidade do tempo é exponencial no comprimento de uma consulta no pior caso . Isso não contradiz que algumas consultas longas sejam rápidas. Os profissionais de banco de dados sabem quais consultas são executadas rapidamente em mecanismos de banco de dados típicos e, de qualquer forma, não contam com o pior caso possível em termos de duração da consulta.
Tsuyoshi Ito
2
@Kaveh: "O livro de Complexidade Descritiva de Immerman teve uma pequena discussão no último capítulo": Muito boa sugestão. Nitpicking: É discutido no penúltimo capítulo. @imz: Você também pode achar útil o poder expressivo do SQL .
MS Dousti
5
@ imz: "Este gráfico tem um n-clique" não é tão comum uma consulta na prática. A maioria das consultas é mais parecida com a sugerida pelo @Sadeq e possui uma estrutura fortemente semelhante a uma árvore. Além disso, para bancos de dados realmente grandes, mesmo uma consulta completamente linear é muito cara e é preciso trabalhar com um esboço do banco de dados.
András Salamon

Respostas:

16

Existem grandes classes de consultas que são "fáceis", mesmo no pior caso. Em particular, se a classe de consultas contiver apenas consultas conjuntivas e cada consulta tiver largura delimitada (por exemplo, largura da árvore, largura do gráfico de incidência, largura fracionada da hiperárvore ou largura submodular), a consulta poderá ser respondida usando algo como uma árvore de junção , juntamente com a enumeração de força bruta para as partes locais da consulta que se desviam da árvore. Isso requer tempo polinomial, com o grau do polinômio determinado pelo parâmetro width.

Parece que muitas consultas encontradas na prática são conjuntivas e têm pouca largura. Portanto, o tempo de execução polinomial tem um baixo grau nesse caso.

Dániel Marx apresentou um artigo no STOC 2010 sobre largura submodular recentemente, cuja versão completa inclui um bom resumo das várias noções de largura e como a formulação do CSP se relaciona com o formalismo do banco de dados (a versão da conferência não possui isso).

  • Dániel Marx, Propriedades de hipertexto tratáveis ​​para satisfação de restrições e consultas conjunturais , 2010. arxiv: 0911.0801

Essa não é uma resposta completa, pois não lida com a complexidade "típica" das consultas ao banco de dados, mas mesmo com a análise do pior caso, existem consultas fáceis.

András Salamon
fonte
6

Pode-se usar as consultas Q_n para verificar se um gráfico, representado como um banco de dados, contém um clique com n elementos. Verificar se um gráfico tem uma clique é um problema completo de NP. Além disso, não é um parâmetro fixo tratável, com o parâmetro n (que significa D ^ n).

mishaz
fonte
Poste explicações adicionais sobre o plano de fundo da pergunta como um "comentário" (não uma "resposta") - com o botão "Adicionar comentário" abaixo da pergunta ou como uma sugestão de edição - com o link "editar" abaixo a questão. "Respostas" não são para discussões e acréscimos à pergunta. (Participar aqui deve ser mais conveniente se você se registrar como um usuário não-anônimo; então é mais fácil de controlar quem disse o quê nas discussões.)
IMZ - Ivan Zakharyaschev
@imz: Ele colocou isso como uma resposta, porque ele não tem o privilégio de comentar. É preciso ter pelo menos 50 representantes. para poder comentar em qualquer lugar.
Tomek Tarczynski
@ Tomk, @ imz, bem, está sendo discutido na meta no momento se devemos permitir comentários usando respostas ou não.
Kaveh
5

Outra maneira de responder a essa pergunta é "eles não"!

Se você fornecer a uma implementação típica do DBMS uma consulta contendo um número muito grande de junções, ela nem passará pela fase de planejamento / otimização (sem falar na avaliação), mesmo se a consulta for acíclica ou tiver uma estrutura muito simples, como András faz alusão ao acima.

Mas, para cargas de trabalho "típicas" do DBMS, essas consultas parecem não surgir.

tjgreen
fonte
11
Para consultas complexas, o resultado da fase de otimização é o plano escolhido aleatoriamente. Isso não é tão ruim quanto parece, porque o caminho da execução ainda pode ser "bom o suficiente", e há muitas outras razões pelas quais a otimização é difícil além da combinatória do número de junções.
Tegiri Nenashi
4

Aqui está uma versão mais preocupada com a realidade da resposta da tigreen, a partir do ponto de uma pessoa que realmente faz uso pesado de bancos de dados (relacionais): O objetivo e a complexidade de seu aplicativo são estruturá-los de uma maneira que exigiriam o mínimo de se une a todas as consultas sempre necessárias quanto possível e é por isso que elas realmente funcionam . Em outras palavras, não espere que os bancos de dados resolvam problemas complexos por conta própria - eles não resolveriam, mas se usados ​​com sabedoria, são um instrumento realmente útil e aplicável.

quem
fonte
0

As uniões são quadráticas em relação aos relacionamentos muitos-para-muitos. Isso é relativamente raro: na prática, a maioria dos relacionamentos e junções é de um para muitos; portanto, levará tempo linear se índices / chaves forem definidos. Consultas com várias associações muitos-para-muitos são um problema sério.

reinierpost
fonte