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

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