Igualdad matemática de dos sentencias SQL

9

¿Hay alguna manera de verificar la igualdad matemática de dos declaraciones SQL?

Tengo dos declaraciones SQL:

  • SQL_STATEMENT_1
  • SQL_STATEMENT_2

Ejecutar ambas declaraciones en los datos y comparar la salida no ayuda en absoluto.

Es necesario evaluar las matemáticas detrás de las declaraciones, como lo hace un solucionador de ecuaciones.

Fuera del alcance de mi pregunta hay cosas como:

  • comparaciones distintas a la igualdad (mayor que, menor que, COMO, ...)
  • procedimientos almacenados o desencadenantes
  • Expresiones de tabla comunes (CON)

En la mira:

  • Subselecciones: WHERE other_id IN (SELECCIONAR ID de otro WHERE ...)
  • UNIONES
database-theory guettli
fuente
Una solución parcial sería comparar los planes de ejecución de 2 consultas. Si los planes de ejecución son los mismos, entonces son iguales. Sin embargo, la relación no funciona en ambos sentidos. Puede haber 2 consultas lógicamente equivalentes que tienen diferentes planes de ejecución.
BuahahaXD
1
@BuahahaXD: eso no es cierto. select * from foo where id = 4seguramente tendrá el mismo plan de ejecución queselect * from foo where id = 2
a_horse_with_no_name
@a_horse_with_no_name Lo probé en SQL Server y obtuve 2 archivos XML diferentes. Los parámetros se incluyeron como un nodo <ParameterList> en el archivo XML. Visualmente, estos planes eran idénticos (exploración de tabla + selección). Pero creo que podría tener razón al comparar los planes de ejecución.
BuahahaXD
1
@a_horse_with_no_name es correcto cuando se trata de claves únicas. Para todos los demás, es posible select * from foo where id = 4y select * from foo where id = 2tener dos planes de ejecución diferentes si 1) las estadísticas del índice no están actualizadas y 2) incluso si las estadísticas del índice están actualizadas, la distribución clave de id es desigual (El ID proporcionado no es una clave única).
RolandoMySQLDBA

Respuestas:

6

¿Cuál es la igualdad matemática de dos declaraciones SQL? Para mí, dos consultas son equivalentes si, cuando se les da el mismo conjunto de datos, devuelven el mismo conjunto de resultados.

Como señaló, las consultas SQL, un superconjunto de álgebra relacional , pueden ser muy complejas. Podemos mezclar subconsultas, usar procedimientos almacenados y funciones ( deterministas o no) que harán que su consulta se parezca más a un código real . Si está hablando de este tipo de consultas, será muy difícil. De hecho, probablemente no es diferente del problema "son dos algoritmos equivalentes".

En esas condiciones, probablemente sea imposible.

Sin embargo...

... podría ser factible si las dos consultas que desea comparar son operaciones de conjunto estrictas. Si es así, puede convertir las consultas a álgebra relacional y luego resolverlas siguiendo las reglas de equivalencia . Si tiene una selección / restricción con condiciones booleanas no triviales, es posible que necesite probar que esas condiciones también son equivalentes. Entonces necesitarás confiar en el álgebra booleana y probablemente terminarás haciendo una tabla de verdad .

Como puede ver, esto va a ser mucho trabajo y, hasta donde yo sé, no existe nada para calcular todo eso automáticamente. Sin embargo, encontré algunas herramientas que pueden resultarle útiles si desea abordar la tarea:

ForguesR
fuente
Mi pregunta es solo sobre las operaciones de configuración. Actualicé la pregunta. Está relacionado con el problema "son dos algoritmos equivalentes". Pero el contexto es límite, solo las operaciones básicas de conjuntos, uniones y subselecciones están dentro de mi alcance.
guettli
3

Es imposible verificar la equivalencia semántica en tiempo finito por definición, ver el teorema de Rice :

para cualquier propiedad no trivial de funciones parciales, no existe un método general y efectivo para decidir si un algoritmo calcula una función parcial con esa propiedad.

usuario63455
fuente
2
Esto simplemente no es un comentario. ¿Puede ampliar la aplicabilidad de Rice a este contexto, por favor?
Michael Green
Incluso si fuera posible en teoría la sintaxis SQL estándar actual es tan barroca que sería imposible en la práctica
James Anderson
1
Con la explicación OP parece que la pregunta es más sobre equivalencia lógica que equivalencia semántica. La verdadera pregunta es: ¿podemos convertir las declaraciones SQL en una expresión matemática y luego evaluar la equivalencia lógica?
ForguesR
2

El usuario de dba Lennart me señaló este proyecto:

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

Cosette es un comprobador automatizado para verificar equivalencias de consultas SQL. Se formaliza un fragmento sustancial de SQL en Coq Proof Assistant y la máquina virtual simbólica Rosette. Devuelve una prueba formal de equivalencia o un contraejemplo para un par de consultas dadas.

guettli
fuente
1

Una forma de hacerlo es crear un analizador sintáctico, o mejor, usar uno existente. Creo que C # tiene una clase TSQLParser y tiene un método Parse (). El analizador dividirá su consulta en subclases que luego podrá comparar.

Matan Yungman
fuente
1

Si está buscando una prueba de equivalencia basada en la teoría de conjuntos, su mejor opción es convertir cualquier WHEREcondición que pueda convertirse en un tipo de JOIN(interno o externo) y refactorizar la declaración. Esto incluye IN subselecty EXISTS subselecty cualquier otra condición en la WHEREcláusula que contiene la palabra SELECT. Si realiza esto en ambas declaraciones SQL, tendrá una nueva FROMcláusula que representa la lógica / matemática basada en conjuntos que le interesa. Luego, puede comparar visualmente las dos declaraciones. Si está buscando una forma automatizada de hacer todo esto, no conozco una herramienta que pueda hacer exactamente esto.

Cola Mann
fuente