Równość matematyczna dwóch instrukcji SQL

9

Czy istnieje sposób sprawdzenia równości matematycznej dwóch instrukcji SQL?

Mam dwie instrukcje SQL:

  • SQL_STATEMENT_1
  • SQL_STATEMENT_2

Uruchamianie obu instrukcji na danych i porównywanie danych wyjściowych wcale nie pomaga.

Zestaw matematyki za wyrażeniami musi zostać oceniony, podobnie jak solver równań.

Poza zakresem mojego pytania są takie rzeczy jak:

  • porównania inne niż równość (większa niż, mniejsza niż LIKE, ...)
  • procedury składowane lub wyzwalacze
  • Typowe wyrażenia tabelowe (Z)

W zakresie:

  • Wybiera: WHERE other_id IN (WYBIERZ id ​​z innego GDZIE ...)
  • ŁĄCZY
database-theory guettli
źródło
Częściowym rozwiązaniem byłoby porównanie planów wykonania 2 zapytań. Jeśli plany wykonania są takie same, są one równe. Jednak związek nie działa w obie strony. Mogą istnieć 2 logicznie równoważne zapytania, które mają różne plany wykonania.
BuahahaXD
1
@BahahahaXD: to nieprawda. select * from foo where id = 4z pewnością będzie miał taki sam plan wykonania jakselect * from foo where id = 2
a_horse_w_no_name
@ a_horse_with_no_name Przetestowałem to na SQL Server i otrzymałem 2 różne pliki XML. Parametry zostały uwzględnione jako węzeł <ParameterList> w pliku XML. Wizualnie plany te były identyczne (skanowanie tabeli + wybór). Ale wierzę, że masz rację, porównując plany wykonania.
BuahahaXD
1
@ koń_nazwa_nazwa jest poprawny, jeśli chodzi o unikalne klucze. Dla wszystkich innych, to jest możliwe select * from foo where id = 4i select * from foo where id = 2mieć dwóch różnych planów wykonania jeśli statystyki 1) indeks nie są up-to-date i 2) nawet jeśli statystyki indeksu są up-to-date, klucz podziału id jest koślawe (podany identyfikator nie jest unikalnym kluczem).
RolandoMySQLDBA

Odpowiedzi:

6

Jaka jest matematyczna równość dwóch instrukcji SQL? Dla mnie dwa zapytania są równoważne, jeśli podane oba te same dane z dowolnego zestawu danych, zwracają ten sam zestaw wyników.

Jak wskazałeś, zapytania SQL, nadzbiór algebry relacyjnej , mogą być bardzo złożone. Możemy mieszać podkwerendy, korzystać z procedur przechowywanych i funkcji ( deterministycznych lub nie), dzięki czemu zapytanie wygląda bardziej jak prawdziwy kod . Jeśli mówisz o tego rodzaju zapytaniach, będzie to naprawdę trudne. W rzeczywistości prawdopodobnie nie różni się od problemu „są równoważne dwa algorytmy”.

W tych warunkach jest to prawdopodobnie niemożliwe.

Jednak...

... może być wykonalne, jeśli dwa zapytania, które chcesz porównać, to ściśle ustawione operacje. Jeśli tak, możesz przekonwertować zapytania na algebrę relacyjną, a następnie opracować je zgodnie z regułami równoważności . Jeśli masz wybór / ograniczenie z nietrywialnymi warunkami logicznymi, możesz skończyć z koniecznością udowodnienia, że ​​warunki te są również równoważne. Musisz wtedy polegać na algebrze boolowskiej i prawdopodobnie skończysz robić tabelę prawdy .

Jak widać, będzie to dużo pracy i, o ile wiem, nie istnieje nic, aby to wszystko obliczyć automatycznie. Niemniej jednak znalazłem kilka narzędzi, które mogą okazać się przydatne, jeśli chcesz rozwiązać to zadanie:

ForguesR
źródło
Moje pytanie dotyczy tylko ustawionych operacji. Zaktualizowałem pytanie. Jest to związane z problemem „są równoważne z dwoma algorytmami”. Ale kontekst jest ograniczony, tylko podstawowe operacje na zestawach, złączeniach, podselekcjach są w moim zakresie.
guettli
3

Z definicji nie można sprawdzić równoważności semantycznej w skończonym czasie, patrz twierdzenie Rice'a :

dla dowolnej nietrywialnej właściwości funkcji częściowych nie ma ogólnej i skutecznej metody decydowania, czy algorytm oblicza funkcję częściową z tą właściwością.

użytkownik63455
źródło
2
To nie jest tylko komentarz. Czy możesz rozszerzyć zakres zastosowania ryżu w tym kontekście?
Michael Green
Nawet gdyby było teoretycznie możliwe średnia składni SQL jest obecny barokowy więc byłoby niemożliwe w praktyce
James Anderson
1
Z wyjaśnieniem OP wygląda na to, że pytanie dotyczy bardziej równoważności logicznej niż równoważności semantycznej. Prawdziwe pytanie brzmi: czy możemy przekonwertować instrukcje SQL na wyrażenie matematyczne, a następnie ocenić logiczną równoważność?
ForguesR
2

użytkownik dba, Lennart, wskazał mi ten projekt:

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

Cosette jest automatycznym narzędziem do sprawdzania równoważności zapytań SQL. Formalizuje znaczny fragment SQL w Coq Proof Assistant i symbolicznej maszynie wirtualnej Rozeta. Zwraca formalny dowód równoważności lub kontrprzykład dla pary podanych zapytań.

guettli
źródło
1

Jednym ze sposobów jest zbudowanie parsera lub, lepiej, użycie istniejącego. Wierzę, że C # ma klasę TSQLParser i ma metodę Parse (). Analizator składni podzieli zapytanie na podklasy, które można następnie porównać.

Matan Yungman
źródło
1

Jeśli szukasz testu ekwiwalencji opartego na Teorii Setów, najlepszym rozwiązaniem jest konwersja dowolnych WHEREwarunków, które można przekształcić w rodzaj JOIN(wewnętrzny lub zewnętrzny) i refaktoryzacja instrukcji. Obejmuje to IN subselecti EXISTS subselectwszelkie inne warunki w WHEREklauzuli zawierającej to słowo SELECT. Jeśli wykonasz to na obu instrukcjach SQL, otrzymasz nową FROMklauzulę, która reprezentuje logikę / matematykę opartą na zestawach, którymi jesteś zainteresowany. Następnie możesz po prostu wizualnie porównać obie instrukcje. Jeśli szukasz zautomatyzowanego sposobu robienia tego wszystkiego, nie znam narzędzia, które potrafi to dokładnie zrobić.

Kolejka Mann
źródło