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?

database-theory relational-algebra finite-model-theory

— Ken Li
źródło

Aby pokazać, że mają taką samą moc ekspresyjną, pokazuje, że operację różnicową można skonstruować za pomocą operacji lewego połączenia (i ewentualnie innych operacji w RA).

— sxd

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')$

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

Przykład: schemat to , schemat to , a my mamy ten i $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 . Do (3) musimy usunąć $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), , a . Pozostaje nam zatem $(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 . Aby to zobaczyć, wystarczy zauważyć, że rzutując wspólne atrybuty z i (zestaw atrybutów ) i biorąc pod uwagę różnicę, pozostaje jeden i wszystkie krotki (ze schematem ), które są reprezentowane w ale nie . Przez z odzyskujemy wszystkie i tylko te krotki w które mają wartości atrybutów w które są obecne w 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 ), podczas gdy schemat jest . Działanie jest zatem iloczyn, że możemy uzyskać wszystkie krotki postaci w których nie ma w odpowiadającego w . $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 (gdyby tak się stało, wówczas druga część zawierająca byłaby sprzecznością); jeśli było dodać kolejną 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 odpowiadające w , a według definicji, 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ą puste, ponieważ wszystkie atrybuty są wspólne, aby miały sens. Najpierw tworzymy nową relację z poprzez duplikowanie zestawu atrybutów w (obsługiwane przez i ), tak aby zawierała krotki w zestawie atrybutów gdzie (obsługiwane przez ). Lewe złączenie pozostawia nam krotki formy $R'$ $S'$ DIFFERENCE $S$ $S$ RENAMEJOIN $(t, t')$ $(T, T')$ $t = t'$ SELECT $(t, t')$ gdzie lub . Teraz, aby pozbyć się wpisów, które również pojawiają się w , musimy zachować tylko krotki formy , która jest obsługiwana przez najbardziej zewnętrzne . Ostatnim pozbywa tymczasowego zestawu atrybutów 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)\}$

— Patrick87
źródło

(1, 2)

$(1,2)$ SELECT

@Raphael Dzięki za wskazanie, że powinienem do tego używać LaTeXa. Podjąłem w dobrej wierze próbę LaTeX'u w obliczeniach matematycznych i sprawdzeniu kodu wstecz ... daj mi znać, czy jest coś jeszcze, co powinienem zrobić. Dzięki jeszcze raz!

— Patrick87,

Wielkie dzięki! Możesz rozważyć użycie $ $ ... $ $ do tworzenia wciętych (nie wbudowanych) kawałków matematyki. Może to często poprawić czytelność, jeśli jest używane prawidłowo. MathJax obsługuje również numerowane równania, ale nie jestem pewien, jak to zrobić.

— Raphael

Myślę, że twoja logika jest tutaj błędna. Używasz DIFFERENCEdo definiowania LEFT JOIN, a następnie LEFT JOINdo wyrażania DIFFERENCE, co oznacza, że SQL może się bez niego obejść. Aby było to ważne, należy wyrazić LEFT JOINw kategoriach operatorów innych niżDIFFERENCE , a następnie udowodnić, że DIFFERENCEjest to równoważne.

— Janoma

@Janoma Nie sądzę, że jest to wymagane ... staramy się pokazać, że różnicę można wyrazić w postaci lewych złączeń, więc zakłada się funkcjonujące lewe złączenie. Pomyśl o tym: jeśli to, co mówisz, miało sens, mógłbym twierdzić, że LEFT JOIN jest operacją „fundamentalną” lub „konieczną” i żądać, abyś zdefiniował RÓŻNICĘ w kategoriach innych operatorów, ale nie LEFT JOIN. Pokazałem, że każda z nich może symulować drugą, więc ani nie jest bardziej ani mniej „fundamentalna” od drugiej… co czyni RÓŻNICĘ wyjątkową? W prop. logika, NOT i AND są kompletne, podobnie jak OR i NOT; nie potrzebujesz wszystkich trzech.

— Patrick87,

-1

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ść.

— Erwin Smout
źródło