Mathematische Gleichheit zweier SQL-Anweisungen

9

Gibt es eine Möglichkeit, die mathematische Gleichheit zweier SQL-Anweisungen zu überprüfen?

Ich habe zwei SQL-Anweisungen:

  • SQL_STATEMENT_1
  • SQL_STATEMENT_2

Das Ausführen beider Anweisungen für Daten und das Vergleichen der Ausgabe hilft überhaupt nicht.

Die Mengenmathematik hinter den Anweisungen muss wie bei einem Gleichungslöser ausgewertet werden.

Außerhalb des Rahmens meiner Frage liegen Dinge wie:

  • andere Vergleiche als Gleichheit (größer als, kleiner als, LIKE, ...)
  • gespeicherte Prozeduren oder Trigger
  • Allgemeine Tabellenausdrücke (WITH)

Im Rahmen:

  • Unterauswahl: WHERE other_id IN (SELECT id FROM other WHERE ...)
  • Tritt bei
database-theory guettli
quelle
Eine Teillösung wäre der Vergleich der Ausführungspläne von 2 Abfragen. Wenn die Ausführungspläne gleich sind, sind sie gleich. Die Beziehung funktioniert jedoch nicht in beide Richtungen. Es kann 2 logisch äquivalente Abfragen mit unterschiedlichen Ausführungsplänen geben.
BuahahaXD
1
@ BuahahaXD: das stimmt nicht. select * from foo where id = 4wird mit Sicherheit den gleichen Ausführungsplan haben wieselect * from foo where id = 2
a_horse_with_no_name
@a_horse_with_no_name Ich habe es auf SQL Server getestet und 2 verschiedene XML-Dateien erhalten. Die Parameter wurden als <ParameterList> -Knoten in die XML-Datei aufgenommen. Optisch waren diese Pläne identisch (Tabellenscan + Auswahl). Aber ich glaube, Sie haben vielleicht Recht, wenn Sie die Ausführungspläne vergleichen.
BuahahaXD
1
@a_horse_with_no_name ist korrekt, wenn es um eindeutige Schlüssel geht. Für alle anderen ist es möglich , zwei verschiedene Ausführungspläne zu haben select * from foo where id = 4und select * from foo where id = 2zu haben, wenn 1) die Indexstatistiken nicht aktuell sind und 2) selbst wenn die Indexstatistiken aktuell sind, die Schlüsselverteilung der ID schief ist (vorausgesetzt, die ID ist kein eindeutiger Schlüssel).
RolandoMySQLDBA

Antworten:

6

Was ist die mathematische Gleichheit zweier SQL-Anweisungen? Für mich sind zwei Abfragen gleichwertig, wenn sie, wenn beide von einem Datensatz gleich sind, dieselbe Ergebnismenge zurückgeben.

Wie Sie bereits betont haben, können SQL-Abfragen, eine Obermenge der relationalen Algebra , sehr komplex sein. Wir können Unterabfragen mischen, gespeicherte Prozeduren und Funktionen ( deterministisch oder nicht) verwenden, sodass Ihre Abfrage eher wie echter Code aussieht . Wenn Sie über diese Art von Fragen sprechen, wird es wirklich schwierig sein. In der Tat ist es wahrscheinlich nicht anders als das Problem "Sind zwei Algorithmen äquivalent".

Unter diesen Bedingungen ist es wahrscheinlich unmöglich.

Jedoch...

... ist es möglicherweise möglich, wenn die beiden Abfragen, die Sie vergleichen möchten, strenge Set-Operationen sind. In diesem Fall können Sie die Abfragen in relationale Algebra konvertieren und anschließend nach Äquivalenzregeln ausarbeiten . Wenn Sie eine Auswahl / Einschränkung mit nichttrivialen booleschen Bedingungen haben, müssen Sie möglicherweise nachweisen, dass diese Bedingungen ebenfalls gleichwertig sind. Sie müssen sich dann auf die boolesche Algebra verlassen und werden wahrscheinlich eine Wahrheitstabelle erstellen .

Wie Sie sehen, wird dies eine Menge Arbeit sein, und soweit ich weiß, gibt es nichts, was all dies automatisch berechnen könnte. Trotzdem habe ich einige Tools gefunden, die Sie möglicherweise nützlich fanden, wenn Sie die Aufgabe angehen möchten:

ForguesR
quelle
Meine Frage betrifft nur festgelegte Operationen. Ich habe die Frage aktualisiert. Es hängt mit dem Problem "Sind zwei Algorithmen äquivalent" zusammen. Aber der Kontext ist begrenzt, nur die grundlegenden Operationen von Mengen, Verknüpfungen und Unterauswahlen sind in meinem Bereich.
Guettli
3

Es ist unmöglich, die semantische Äquivalenz in endlicher Zeit per Definition zu überprüfen, siehe Rices Theorem :

Für jede nicht triviale Eigenschaft von Teilfunktionen gibt es keine allgemeine und effektive Methode, um zu entscheiden, ob ein Algorithmus eine Teilfunktion mit dieser Eigenschaft berechnet.

user63455
quelle
2
Dies ist nur kein Kommentar. Können Sie bitte die Anwendbarkeit von Reis in diesem Zusammenhang erläutern?
Michael Green
Selbst wenn es theoretisch möglich wäre, ist die aktuelle SQL-Standardsyntax so barock, dass es in der Praxis unmöglich wäre
James Anderson
1
Bei der OP-Erklärung sieht es so aus, als ob es bei der Frage eher um logische Äquivalenz als um semantische Äquivalenz geht. Die eigentliche Frage ist: Können wir SQL-Anweisungen in einen mathematischen Ausdruck konvertieren und dann die logische Äquivalenz bewerten?
ForguesR
2

Der dba-Benutzer Lennart hat mich auf dieses Projekt hingewiesen:

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

Cosette ist ein automatisierter Prüfer zum Überprüfen der Äquivalenzen von SQL-Abfragen. Es formalisiert ein wesentliches Fragment von SQL im Coq Proof Assistant und in der symbolischen virtuellen Rosette-Maschine. Es gibt entweder einen formalen Äquivalenznachweis oder ein Gegenbeispiel für ein Paar gegebener Abfragen zurück.

guettli
quelle
1

Eine Möglichkeit besteht darin, einen Parser zu erstellen oder besser einen vorhandenen zu verwenden. Ich glaube, C # hat eine TSQLParser-Klasse und eine Parse () -Methode. Der Parser teilt Ihre Abfrage in Unterklassen auf, die Sie dann vergleichen können.

Matan Yungman
quelle
1

Wenn Sie nach einem auf Mengenlehre basierenden Äquivalenztest suchen, ist es am besten, alle WHEREBedingungen, die in eine Art von JOIN(innerer oder äußerer) umgewandelt werden können , umzuwandeln und die Anweisung überarbeiten zu lassen. Dies schließt IN subselectund EXISTS subselectund alle anderen Bedingungen in der WHEREKlausel ein, die das Wort enthält SELECT. Wenn Sie dies für beide SQL-Anweisungen ausführen, erhalten Sie eine neue FROMKlausel, die die satzbasierte Logik / Mathematik darstellt, an der Sie interessiert sind. Anschließend können Sie die beiden Anweisungen nur visuell vergleichen. Wenn Sie nach einer automatisierten Methode suchen, um all dies zu tun, kenne ich kein Tool, das genau dies kann.

Warteschlange Mann
quelle