Igualdade matemática de duas instruções SQL

9

Existe uma maneira de obter a igualdade matemática de duas instruções SQL?

Eu tenho duas instruções SQL:

  • SQL_STATEMENT_1
  • SQL_STATEMENT_2

Executar as duas instruções nos dados e comparar a saída não ajuda em nada.

O conjunto de matemática por trás das instruções precisa ser avaliado, como um solucionador de equações.

Fora do escopo da minha pergunta estão coisas como:

  • comparações que não sejam igualdade (maior que, menor que, LIKE, ...)
  • procedimentos armazenados ou gatilhos
  • Expressões de tabela comum (WITH)

No escopo:

  • Subseleciona: WHERE other_id IN (SELECT id FROM other WHERE ...)
  • JUNTAS
database-theory guettli
fonte
Uma solução parcial seria comparar os planos de execução de 2 consultas. Se os planos de execução forem os mesmos, serão iguais. No entanto, o relacionamento não funciona nos dois sentidos. Pode haver duas consultas logicamente equivalentes que possuem diferentes planos de execução.
BuahahaXD
11
@BhahahaXD: isso não é verdade. select * from foo where id = 4certamente vai ter o mesmo plano de execução comoselect * from foo where id = 2
a_horse_with_no_name
@a_horse_with_no_name Testei no SQL Server e obtive 2 arquivos XML diferentes. Os parâmetros foram incluídos como um nó <ParameterList> no arquivo XML. Visualmente, esses planos eram idênticos (varredura de tabela + seleção). Mas acredito que você pode estar certo sobre a comparação dos planos de execução.
precisa saber é o seguinte
11
@a_horse_with_no_name está correto quando se trata de chaves exclusivas. Para todos os outros, é possível select * from foo where id = 4e select * from foo where id = 2ter dois planos de execução diferentes se 1) as estatísticas do índice não estiverem atualizadas e 2) mesmo que as estatísticas do índice estejam atualizadas, a distribuição principal do id é desigual (o ID fornecido não é uma chave exclusiva).
RolandoMySQLDBA

Respostas:

6

Qual é a igualdade matemática de duas instruções SQL? Para mim, duas consultas são equivalentes se, ao receberem o mesmo de qualquer conjunto de dados, retornarem o mesmo conjunto de resultados.

Como você apontou, as consultas SQL, um superconjunto de álgebra relacional , podem ser muito complexas. Podemos misturar subconsultas, usar procedimentos e funções armazenados ( determinísticos ou não), o que fará com que sua consulta se pareça mais com código real . Se você estiver falando sobre esse tipo de consulta, será muito difícil. De fato, provavelmente não é diferente do que o problema "são dois algoritmos equivalentes".

Nessas condições, é provavelmente impossível.

Contudo...

... pode ser possível se as duas consultas que você deseja comparar forem operações estritas de conjunto. Nesse caso, você pode converter as consultas em álgebra relacional e, em seguida, resolvê-las seguindo as regras de equivalência . Se você tiver uma seleção / restrição com condições booleanas não triviais, poderá precisar provar que essas condições também são equivalentes. Você precisará confiar na álgebra booleana e provavelmente acabará criando uma tabela de verdade .

Como você pode ver, isso vai dar muito trabalho e, tanto quanto eu sei, nada existe para calcular tudo isso automaticamente. No entanto, eu encontrei algumas ferramentas que você pode achar úteis se quiser executar a tarefa:

ForguesR
fonte
Minha pergunta é apenas sobre operações definidas. Eu atualizei a pergunta. Está relacionado ao problema "são dois algoritmos equivalentes". Mas o contexto é limite, apenas as operações básicas de conjuntos, junções e sub-seleções estão no meu escopo.
guettli
3

É impossível verificar a equivalência semântica em tempo finito por definição, veja o teorema de Rice :

para qualquer propriedade não trivial de funções parciais, não há método geral e eficaz para decidir se um algoritmo calcula uma função parcial com essa propriedade.

user63455
fonte
2
Isso não é apenas um comentário. Você pode expandir a aplicabilidade do Rice nesse contexto, por favor.
22615 Michael Green
Mesmo se fosse teoricamente possível a sintaxe padrão SQL atual é tão barroca seria impossível na prática
James Anderson
11
Com a explicação do OP, parece que a pergunta é mais sobre equivalência lógica do que equivalência semântica. A verdadeira questão é: podemos converter instruções SQL em uma expressão matemática e avaliar a equivalência lógica?
precisa saber é o seguinte
2

O usuário do dba Lennart me apontou para este projeto:

http://cosette.cs.washington.edu/

Cosette é um provador automatizado para verificar equivalências de consultas SQL. Ele formaliza um fragmento substancial de SQL no Coq Proof Assistant e na máquina virtual simbólica do Rosette. Ele retorna uma prova formal de equivalência ou um contra-exemplo para um par de consultas fornecidas.

guettli
fonte
1

Uma maneira de fazer isso é criar um analisador, ou melhor, usar um existente. Eu acredito que C # tem uma classe TSQLParser e tem um método Parse (). O analisador quebrará sua consulta em subclasses que você poderá comparar.

Matan Yungman
fonte
1

Se você estiver procurando por um teste de equivalência baseado na Teoria dos Conjuntos, sua melhor aposta é converter quaisquer WHEREcondições que possam ser convertidas em um tipo de JOIN(interno ou externo) e ter a instrução refatorada. Isso inclui IN subselecte EXISTS subselectoutras condições na WHEREcláusula que contém a palavra SELECT. Se você fizer isso nas duas instruções SQL, terá uma nova FROMcláusula que representa a lógica / matemática baseada em conjunto em que está interessado. Em seguida, você pode comparar visualmente as duas instruções. Se você está procurando uma maneira automatizada de fazer tudo isso, não conheço uma ferramenta que possa fazer exatamente isso.

Queue Mann
fonte