Czy operacja „różnica” dodaje wyrazistości do języka zapytań, który już zawiera „dołącz”?

Operator różnicy zbiorów (np. EXCEPTW niektórych wariantach SQL) jest jednym z wielu podstawowych operatorów algebry relacyjnej. Istnieją jednak bazy danych, które nie obsługują bezpośrednio operatora różnicy setów, ale które obsługują LEFT JOIN(rodzaj połączenia zewnętrznego), aw praktyce można tego użyć zamiast operacji ustawiania różnicy, aby osiągnąć ten sam efekt.

Czy to oznacza, że ​​moc ekspresyjna języka zapytań jest taka sama, nawet bez operatora różnicy, o ile LEFT JOINoperator jest utrzymywany? Jak udowodnić ten fakt?

W algebrze relacyjnej najpierw przedstawimy nieformalną definicję lewego (zewnętrznego) złączenia i przejdziemy do udowodnienia, że ​​to zmiana nazwy, selekcji, łączenia i rzutowania może tworzyć różnicę, a także, że różnicę, selekcję i łączenie można wykorzystać do zbudowania różnicy lewe (zewnętrzne) połączenie. W rzeczywistości skończymy w odwrotnej kolejności: pokażemy, jak konstruować lewe złączenia za pomocą różnic, a następnie pokażemy, jak konstruować różnice za pomocą lewych złączeń.

Niech i mają odpowiednio schematy i , gdzie i są zestawami atrybutów w jednym schemacie, ale nie drugim, a jest zbiorem wspólnych atrybutów.$R$$S$$(R', T)$$(T, S')$$R'$$S'$$T$

Niech będzie krotką zerową dla schematu . Oznacza to, że jest to krotka składająca się ze wszystkich wartości zerowych dla każdego atrybutu . Następnie definiujemy lewe łączenie zewnętrzne w następujący sposób: jest zbiorem wszystkich krotek należących do schematu gdzie ...$w = (\epsilon, \epsilon, ..., \epsilon)$$S'$$S'$R LEFT JOIN S$(r, t, s)$$(R', T, S')$

1. $(r, t)$ oznacza krotkę w ;$R$
2. (a) oznacza krotkę S lub (b) s = w ;$(t, s)$$S$$s = w$
3. Jeśli jest w zestawie dla s ≠ w , to ( r , t , w ) nie jest w zestawie.$(r, t, s)$$s \neq w$$(r, t, w)$

Przykład: schemat to ( A 1 , A 2 , A 3 ) , schemat S to ( A 2 , A 3 , A 4 ) , a my mamy ten R = { ( 1 , 2 , 3 ) , ( 4 , 5 , 6 ) } i S = { ( 2 , 3 , 4 $R$$(A_{1}, A_{2}, A_{3})$$S$$(A_{2}, A_{3}, A_{4})$$R = \{(1, 2, 3), (4, 5, 6)\}$ . Przez (1) i (2) otrzymujemy wynik pośredni { ( 1 , 2 , 3 , 4 ) , ( 1 , 2 , 3 , 6 ) , ( 1 , 2 , 3 , ϵ ) , ( 4 , 5 , 6 , ϵ ) } . Do (3) musimy usunąć ( 1 , $S = \{(2, 3, 4), (2, 3, 6)\}$$\{(1, 2, 3, 4),(1, 2, 3, 6), (1, 2, 3, \epsilon),(4, 5, 6, \epsilon)\}$ , ponieważ mamy (na przykład), ( 1 , 2 , 3 , 4 ) , a y = 4 ≠ ε = wag . Pozostaje nam zatem { ( 1 , 2 , 3 , 4 ) , ( 1 , 2 , 3 , 6 ) , ( 4 , 5 , 6 , ϵ ) $(1, 2, 3, \epsilon)$$(1, 2, 3, 4)$$s = 4 \neq \epsilon = w$$\{(1, 2, 3, 4), (1, 2, 3, 6), (4, 5, 6, \epsilon)\}$, oczekiwany wynik dla lewego złączenia.

Twierdzenie: R LEFT JOIN Sjest równoważne z (R EQUIJOIN S) UNION ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w).

Dowód: (R EQUIJOIN S)daje nam wszystko, czego wymagają (1) i (2a). Twierdzimy, że ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w)daje nam to wszystko w formie (r, t, w)wymaganej przez (2b) i (3).

To zobaczyć pierwszy uwagę, że (((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R)jest to zbiór wszystkich krotki w , dla którego nie ma odpowiadającej krotka w S . Aby to zobaczyć, wystarczy zauważyć, że rzutując wspólne atrybuty z R i S (zestaw atrybutów T ) i biorąc pod uwagę różnicę, pozostaje jeden i wszystkie krotki (ze schematem T ), które są reprezentowane w R, ale nie S . Przez z R odzyskujemy wszystkie i tylko te krotki w R, które mają wartości atrybutów w T, które są obecne w R, ale nie w $R$$S$$R$$S$$T$$T$$R$$S$EQUIJOIN$R$$R$$T$$R$$S$; a mianowicie dokładnie zestaw krotek, które do tej pory twierdziliśmy.

Następnie zauważ, że schemat (((PROJECT_T R) DIFFERENCE (PROJECT_T S))jest taki sam jak dla (mianowicie ( R ' , T ) ), podczas gdy schemat w jest S ' . Działanie jest zatem iloczyn, że możemy uzyskać wszystkie krotki postaci ( R , T , W ), w których nie ma ( t , y ) w S odpowiadającego ( r , t ) w R .$R$$(R', T)$$w$$S'$JOIN$(r, t, w)$$(t, s)$$S$$(r, t)$$R$

Aby zobaczyć, że jest to dokładnie zestaw krotek, które musieliśmy dodać R EQUIJOIN Sw celu skonstruowania R LEFT JOIN S, rozważ następujące kwestie: z uwagi na konstrukcję (3) jest spełniony, ponieważ R EQUIJOIN Snie może zawierać jeśli zawiera ( r , t , w ) (gdyby tak się stało, wówczas druga część zawierająca ( r , t , w ) byłaby sprzecznością); jeśli było dodać kolejną ( r , T , W ) nie , to nie będzie to $(r, t, s)$((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w)$(r, t, w)$$(r, t, w)$$(r, t, w)$((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w) w S odpowiadające ( r , t ) w R , a według definicji, ( r , t , s ) również byłoby wsprzeczności (3). To kończy dowód.$(t, s)$$S$$(r, t)$$R$EQUIJOIN$(r, t, s)$R LEFT JOIN S

Teraz pokazujemy, że lewe łączenie może być użyte do skonstruowania różnicy:

Twierdzenie: R DIFFERENCE Sjest równoważne zPROJECT_T(SELECT_{t'=w}(R LEFT JOIN (SELECT_{s=s'}(((S JOIN RENAME_{T->T'}(S)))))))

Dowód: zauważ, że tutaj i S ′ są puste, ponieważ wszystkie atrybuty są wspólne, aby miały sens. Najpierw tworzymy nową relację z S poprzez duplikowanie zestawu atrybutów w S (obsługiwane przez i ), tak aby zawierała krotki ( t , t ′ ) w zestawie atrybutów ( T , T ′ ), gdzie t = t ′ (obsługiwane przez ). Lewe złączenie pozostawia nam krotki formy ( t , t ′$R'$$S'$DIFFERENCE$S$$S$RENAMEJOIN$(t, t')$$(T, T')$$t = t'$SELECT$(t, t')$gdzie lub t ′ = w . Teraz, aby pozbyć się wpisów, które również pojawiają się w S , musimy zachować tylko krotki formy ( t , w ) , która jest obsługiwana przez najbardziej zewnętrzne . Ostatnim pozbywa tymczasowego zestawu atrybutów T ' i pozostawia nas z różnicy pod względem pierwotnego schematu.$t=t'$$t'=w$$S$$(t, w)$SELECTPROJECT$T'$

$R = \{(1, 2), (3, 4), (5, 6)\}$$S = \{(3, 4), (5, 6), (7, 8)\}$$S$RENAME$T'$$\{(3, 4), (5, 6), (7, 8)\}$JOINSELECT$\{(3, 4, 3, 4), (5, 6, 5, 6), (7, 8, 7, 8)\}$LEFT JOIN$R$$\{(1, 2, \epsilon, \epsilon), (3, 4, 3, 4), (5, 6, 5, 6)\}$SELECT$\{(1, 2, \epsilon, \epsilon)\}$PROJECT$\{(1, 2)\}$

LEFT JOIN zaimplementowany przez SQL, nie tworzy relacji jako wyniku (ponieważ niektóre atrybuty wyniku nie będą miały wartości).

Ergo, LEFT JOIN implementowany przez SQL, nie jest bezpośrednim odpowiednikiem żadnego operatora algebry relacyjnej.

Ergo, Operator różnicy relacyjnej nie może być wyrażony jako LEWE DOŁĄCZENIE (ponieważ LEFT JOIN nie może być częścią algebry relacyjnej, ponieważ LEFT JOIN tworzy coś, co nie jest relacją, co narusza zamknięcie algebry).

Każdy zestaw prymitywnych operatorów algebry relacyjnej, który spełnia kryteria zamknięcia , o których wiem, zawsze zawiera albo relacyjną różnicę, albo relacyjną półjednoznaczność.