Algebra relacyjna - Relational algebra

W teorii baz danych , relacyjne algebry jest teorią, która używa struktur algebraicznych z uzasadnionych semantyki do modelowania danych i definiowania zapytań na nim. Teorię wprowadził Edgar F. Codd .

Głównym zastosowaniem algebry relacyjnej jest dostarczenie teoretycznej podstawy relacyjnych baz danych , w szczególności języków zapytań dla takich baz , z których głównym jest SQL . Relacyjne bazy danych przechowują dane tabelaryczne reprezentowane jako relacje . Zapytania dotyczące relacyjnych baz danych często również zwracają dane tabelaryczne reprezentowane jako relacje . Głównym założeniem algebry relacyjnej jest zdefiniowanie operatorów, które przekształcają jedną lub więcej relacji wejściowych w relację wyjściową. Biorąc pod uwagę, że operatory te akceptują relacje jako dane wejściowe i wytwarzają relacje jako dane wyjściowe, można je łączyć i używać do wyrażania potencjalnie złożonych zapytań, które przekształcają potencjalnie wiele relacji wejściowych (których dane są przechowywane w bazie danych) w pojedynczą relację wyjściową (wyniki zapytania). . Operatory jednoargumentowe akceptują jako dane wejściowe pojedynczą relację; przykłady obejmują operatory do filtrowania określonych atrybutów (kolumn) lub krotek (wierszy) z relacji wejściowej. Operatory binarne przyjmują jako dane wejściowe dwie relacje; takie operatory łączą dwie relacje wejściowe w jedną relację wyjściową, na przykład biorąc wszystkie krotki znalezione w dowolnej relacji, usuwając krotki z pierwszej relacji znalezionej w drugiej relacji, rozszerzając krotki z pierwszej relacji o krotki z drugiej relacji spełnianie określonych warunków i tak dalej. Można również uwzględnić inne, bardziej zaawansowane operatory, w przypadku których włączenie lub wyłączenie pewnych operatorów powoduje powstanie rodziny algebr.

Wstęp

Algebra relacyjna poświęcono niewiele uwagi poza czystej matematyki do publikacji EF Codd „s relacyjnym modelu danych w 1970 Codd proponowanym takiej algebry jako podstawa do języków zapytań w bazie. (Patrz rozdział Implementacje .)

Pięć podstawowych operatorów algebry Codda to: wybór , rzutowanie , iloczyn kartezjański (zwany także iloczynem krzyżowym lub łączeniem krzyżowym ), suma zbiorów i różnica zbiorów .

Ustaw operatorów

Algebra relacyjna wykorzystuje sumę zbiorów , różnicę zbiorów i iloczyn kartezjański z teorii mnogości , ale dodaje dodatkowe ograniczenia do tych operatorów.

W przypadku sumy zestawów i różnicy zestawów, dwie zaangażowane relacje muszą być zgodne z unią — to znaczy, że dwie relacje muszą mieć ten sam zestaw atrybutów. Ponieważ przecięcie zbiorów jest definiowane w kategoriach sumy zbiorów i różnicy zbiorów, dwie relacje biorące udział w przecięciu zbiorów również muszą być kompatybilne z sumą.

Aby iloczyn kartezjański został zdefiniowany, dwie zaangażowane relacje muszą mieć rozłączne nagłówki — to znaczy nie mogą mieć wspólnej nazwy atrybutu.

Ponadto iloczyn jest zdefiniowany w inny sposób z jednym z zadanej teorią w tym sensie, że krotka jest uważany za „płytkie” dla celów operacji. Oznacza to, że iloczyn kartezjański zbioru n -krotek ze zbiorem m -krotek daje zbiór "spłaszczonych" ( n  +  m ) -krotek (podczas gdy podstawowa teoria mnogości zalecałaby zbiór dwóch krotek, każda zawierające n- krotkę i m- krotkę). Bardziej formalnie, R × S definiuje się następująco:

${\ Displaystyle R \ razy S: = \ {(r_ {1}, r_ {2}, \ kropki, r_ {n}, s_ {1}, s_ {2}, \ kropki, s_ {m}) | ( r_{1},r_{2},\kropki ,r_{n})\w R,(s_{1},s_{2},\dots ,s_{m})\w S\}}$

Moc iloczynu kartezjańskiego jest iloczynem mocy jego czynników, czyli | R × S | = | R | × | S |.

Projekcja ( Π )

Projekcja jest jednoskładnikowa operacja zapisać jako gdzie jest zbiorem nazw atrybutów. Wynik takiego rzutowania jest zdefiniowany jako zbiór, który uzyskuje się, gdy wszystkie krotki w R są ograniczone do zbioru . ${\ Displaystyle \ Pi _ {a_ {1}, \ ldots, a_ {n}} (R)}$${\displaystyle a_{1},\ldots,a_{n}}$${\ Displaystyle \ {a_ {1}, \ ldots, a_ {n} \}}$

Uwaga: po zaimplementowaniu w standardzie SQL "projekcja domyślna" zwraca multiset zamiast zestawu, a projekcja Π w celu wyeliminowania duplikatów danych jest uzyskiwana przez dodanie DISTINCTsłowa kluczowego .

Wybór ( σ )

Uogólnione wybór jest jednoskładnikowa działanie zapisać jako gdzie φ jest propositional wzór , który składa się z atomów dozwolonej w normalnej selekcji i operatorów logicznych ( a ) ( i ) oraz ( negacja ). Ta opcja wybiera te wszystkie krotki z R , dla których φ ładowni. ${\ Displaystyle \ sigma _ {\ varphi} (R)}$${\ Displaystyle \ klin}$${\displaystyle \lor}$${\displaystyle \neg}$

Aby uzyskać listę wszystkich znajomych lub współpracowników biznesowych w książce adresowej, wybór może być zapisany jako . Wynikiem byłaby relacja zawierająca wszystkie atrybuty każdego unikalnego rekordu, gdzie isFriend ma wartość true lub isBusinessContact jest prawdziwe. ${\ Displaystyle \ Sigma _ {{\ tekst {isFriend = prawda}} \ \ Lor \, {\ tekst {isBusinessContact = prawda}}} ({\ tekst {książka adresowa}})}$

Zmień nazwę ( ρ )

Rename to jednoskładnikowa operacja zapisać jako gdzie wynik jest identyczny R wyjątkiem tego, że b atrybut we wszystkich krotek jest przemianowany na w atrybucie. Jest to po prostu używane do zmiany nazwy atrybutu relacji lub samej relacji. ${\ Displaystyle \ rho _ {a/b} (R)}$

Aby zmienić nazwę atrybutu 'isFriend' na 'isBusinessContact' w relacji, można użyć. ${\ Displaystyle \ rho _ {\ tekst {isBusinessContact / isFriend}} ({\ tekst {adresbook}})}$

Istnieje również notacja, w której nazwa R zostaje zmieniona na x, a atrybuty na . ${\ Displaystyle \ rho _ {x (A_ {1}, \ ldots, A_ {n})} (R)}$${\ Displaystyle \ {a_ {1}, \ ldots, a_ {n} \}}$${\ Displaystyle \ {A_ {1}, \ ldots, A_ {n} \}}$

Sprzężenia i operatory sprzężenia-podobne

Połączenie naturalne (⋈ )

Złączenie naturalne (⋈) to operator binarny zapisany jako ( R ⋈ S ), gdzie R i S są relacjami . Wynikiem łączenia naturalnego jest zestaw wszystkich kombinacji krotek w R i S, które są równe w ich wspólnych nazwach atrybutów. Jako przykład rozważmy tabele Employee i Dept oraz ich naturalne sprzężenie:

Zwróć uwagę, że w wyniku nie pojawia się ani pracownik o imieniu Mary, ani dział zasobów ludzkich.

Można to również wykorzystać do zdefiniowania kompozycji relacji . Na przykład kompozycja Employee i Dept to ich sprzężenie, jak pokazano powyżej, rzutowane na wszystkie atrybuty oprócz wspólnego atrybutu DeptName . W teorii kategorii złączem jest właśnie produkt włóknisty .

Złączenie naturalne jest prawdopodobnie jednym z najważniejszych operatorów, ponieważ jest relacyjnym odpowiednikiem operatora logicznego AND. Zauważ, że jeśli ta sama zmienna pojawia się w każdym z dwóch predykatów, które są połączone operatorem AND, to ta zmienna oznacza tę samą rzecz i oba wystąpienia muszą być zawsze podstawione tą samą wartością (jest to konsekwencja idempotentności logicznego AND) . W szczególności sprzężenie naturalne umożliwia łączenie relacji, które są skojarzone kluczem obcym . Na przykład w powyższym przykładzie klucz obcy prawdopodobnie jest przechowywany od Employee . DEPTNAME do Dept . DeptName a następnie naturalne połączenie Employee and Dept łączy wszystkich pracowników z ich działami. Działa to, ponieważ klucz obcy jest przechowywany między atrybutami o tej samej nazwie. Jeśli nie jest to przypadek, tak jak w kluczu obcym z Dept . Menedżer do pracownika . Nazwij, a następnie te kolumny muszą zostać zmienione przed wykonaniem naturalnego sprzężenia. Takie złączenie jest czasami nazywane equijoin (zobacz θ -join).

Bardziej formalnie semantyka naturalnego sprzężenia jest zdefiniowana w następujący sposób:

${\ Displaystyle R \ Bowtie S = \ lewo \ {r \ filiżanka s \ \ vert \ r \ w R \ \ ziemia \ s \ w S \ \ ziemia \ {\ mathit {zabawa}} (r \ puchar s) \ Prawidłowy\}}$

( 1 )

gdzie Fun(t) jest predykatem, który jest prawdziwy dla relacji t (w sensie matematycznym) jeśli t jest funkcją. Zwykle wymagane jest, aby R i S miały co najmniej jeden wspólny atrybut, ale jeśli to ograniczenie zostanie pominięte, a R i S nie mają wspólnych atrybutów, wówczas naturalne złączenie staje się dokładnie iloczynem kartezjańskim.

Naturalne sprzężenie można symulować za pomocą prymitywów Codda w następujący sposób. Załóżmy, że c ₁ ,..., c _m to nazwy atrybutów wspólne dla R i S , r ₁ ,..., r _n to nazwy atrybutów unikalne dla R i s ₁ ,..., s _k to atrybuty nazwy unikalne dla S . Ponadto załóżmy, że nazwy atrybutów x ₁ ,..., x _m nie znajdują się ani w R ani w S . W pierwszym kroku wspólne nazwy atrybutów w S można zmienić:

${\ Displaystyle T = \ rho _ {x_ {1} / c_ {1}, \ ldots, x_ {m} / c_ {m}} (S) = \ rho _ {x_ {1} / c_ {1}} (\rho _{x_{2}/c_{2}}(\ldots \rho _{x_{m}/c_{m}}(S)\ldots ))}$

( 2 )

Następnie bierzemy iloczyn kartezjański i wybieramy krotki, które mają zostać połączone:

${\ Displaystyle P = \ sigma _ {c_ {1} = x_ {1}, \ ldots, c_ {m} = x_ {m}} (R \ razy T) = \ sigma _ {c_ {1} = x_ { 1}}(\sigma _{c_{2}=x_{2}}(\ldots \sigma _{c_{m}=x_{m}}(R\times T)\ldots ))}$

( 3 )

Na koniec wykonujemy projekcję, aby pozbyć się atrybutów o zmienionych nazwach:

${\ Displaystyle U = \ pi _ {r_ {1}, \ ldots, r_ {n}, c_ {1}, \ ldots, c_ {m}, s_ {1}, \ ldots, s_ {k}} (P )}$

( 4 )

θ -join i equijoin

Rozważ tabele Samochód i Łódź, które zawierają listę modeli samochodów i łodzi oraz ich ceny. Załóżmy, że klientka chce kupić samochód i łódź, ale nie chce wydawać więcej pieniędzy na łódź niż na samochód. Θ -join (⋈ _θ ) od orzeczenia CarPrice ≥ BoatPrice wytwarza spłaszczony pary rzędów, które spełniają orzeczenie. W przypadku korzystania z warunku, w którym atrybuty są takie same, na przykład Cena, warunek może być określony jako Cena = Cena lub alternatywnie sam ( Cena ).

W celu połączenia dwóch stosunków krotki gdzie stan połączenie to nie jest po prostu równość wspólnych cech jest wygodne, aby był bardziej ogólną postać przyłączenia operatora, który jest θ -join (lub teta przyłączenia). Θ -join jest operatorem, które jest zapisane jako lub gdzie i b są nazwami atrybutów, θ jest binarny relacyjną operatora w zbiorze {<, ≤, =, ≠,> ≥} , υ jest wartością stałą, a R i S są relacjami. Wynik tej operacji składa się ze wszystkich kombinacji krotek w R i S, które spełniają θ . Wynik θ -join jest zdefiniowany tylko wtedy, gdy nagłówki S i R są rozłączne, to znaczy nie zawierają wspólnego atrybutu. ${\ Displaystyle {R \ \ bowtie \ S \ atop a \ \ theta \ b}}$${\ Displaystyle {R \ \ Bowtie \ S \ atop \ \ theta \ v}}$

Symulacja tej operacji w operacjach podstawowych jest więc następująca:

R ⋈ _θ S = σ _θ ( R × S )

W przypadku, gdy operator θ jest operatorem równości (=), to złączenie to jest również nazywane equijoin .

Należy jednak zauważyć, że język komputerowy obsługujący naturalne złączenie i operatory selekcji również nie wymaga θ -join, ponieważ można to osiągnąć przez selekcję z wyniku naturalnego sprzężenia (która degeneruje się do iloczynu kartezjańskiego, gdy nie ma współdzielonego atrybuty).

W implementacjach SQL łączenie na predykacie jest zwykle nazywane sprzężeniem wewnętrznym , a słowo kluczowe on umożliwia określenie predykatu używanego do filtrowania wierszy. Ważne jest, aby pamiętać: utworzenie spłaszczonego iloczynu kartezjańskiego, a następnie filtrowanie wierszy jest koncepcyjnie poprawne, ale implementacja używałaby bardziej wyrafinowanych struktur danych, aby przyspieszyć zapytanie sprzężenia.

Półzłącze (⋉) (⋊)

Lewe semijoin jest sprzężeniem podobnym do naturalnego sprzężenia i zapisane jako R ⋉ S , gdzie R i S są relacjami . Wynikiem jest zbiór wszystkich krotek w R, dla których istnieje krotka w S, która jest równa ich wspólnym nazwom atrybutów. Różnica w stosunku do sprzężenia naturalnego polega na tym, że inne kolumny S nie pojawiają się. Rozważmy na przykład tabele Employee i Dept oraz ich częściowe sprzężenie:

Bardziej formalnie semantykę półsprzężenia można zdefiniować w następujący sposób:

R ⋉ S = { t  : t ∈ R ∧ ∃ s ∈ S ( Zabawa ( t ∪ s )) }

gdzie Fun ( r ) jest jak w definicji sprzężenia naturalnego.

Półsprzężenie można symulować przy użyciu naturalnego sprzężenia w następujący sposób. Jeśli a ₁ , ..., a _n są nazwami atrybutów R , to

R ⋉ S = _{1 , .., N} ( R ⋈ S ).${\ Displaystyle \ Pi}$

Ponieważ możemy symulować naturalne sprzężenie za pomocą podstawowych operatorów, wynika z tego, że dotyczy to również semijoin.

W artykule Codda z 1970 roku, semijoin nazywa się ograniczeniem.

Antyzłącze (▷)

Antyjoin, zapisany jako R ▷ S, gdzie R i S są relacjami , jest podobny do semijoin, ale wynikiem antyjoin są tylko te krotki w R, dla których nie ma krotek w S, które są równe w ich wspólnych nazwach atrybutów.

Na przykład rozważ tabele pracownicze i Dept i ich antijoin:

Antyjoin jest formalnie zdefiniowany w następujący sposób:

R ▷ S = { t  : t ∈ R ∧ ¬∃ s ∈ S ( Fun ( t ∪ s )) }

lub

R ▷ S = { t  : t ∈ R , nie jest krotką s o S , która spełnia zabawy ( t ∪ y )}

gdzie Fun ( t ∪ s ) jest jak w definicji złączenia naturalnego.

Antijoin można również zdefiniować jako uzupełnienie semijoin w następujący sposób:

R ▷ S = R  −  R ⋉ S

( 5 )

Biorąc to pod uwagę, antijoin jest czasami nazywane antisemijoin, a operator antijoin jest czasami pisany jako symbol semijoin z kreską nad nim, zamiast ▷.

Dzielenie (÷)

Dzielenie jest operacją binarną zapisaną jako R ÷ S . Podział nie jest zaimplementowany bezpośrednio w SQL. Wynik składa się z ograniczeń krotek w R do nazw atrybutów unikalnych dla R , tj. w nagłówku R , ale nie w nagłówku S , dla którego wszystkie ich kombinacje z krotkami w S są obecne w R . Na przykład zobacz tabele Completed , DBProject i ich podział:

Jeśli DBProject zawiera wszystkie zadania projektu Database, to wynik powyższego podziału zawiera dokładnie tych uczniów, którzy wykonali oba zadania w projekcie Database. Bardziej formalnie semantyka podziału jest zdefiniowana następująco:

R ÷ S = { t [ a 1 ,..., a n ] : t ∈ R ∧ ∀ s ∈ S ( ( t [ a 1 ,..., a n ] ∪ s ) ∈ R ) }

( 6 )

gdzie { ₁ , ..., _n } jest zbiorem nazwami cechą unikalną R i T [ ₁ , ..., _n ] jest ograniczenie t do tego zbioru. Zwykle wymagane jest, aby nazwy atrybutów w nagłówku S były podzbiorem tych z R, ponieważ w przeciwnym razie wynik operacji będzie zawsze pusty.

Symulacja podziału z podstawowymi operacjami wygląda następująco. Zakładamy, że a ₁ ,..., a _n są nazwami atrybutów unikalnymi dla R a b ₁ ,..., b _m są nazwami atrybutów S . W pierwszym kroku projektujemy R na jego unikalne nazwy atrybutów i konstruujemy wszystkie kombinacje z krotkami w S :

T  := π _{a 1 ,..., a n} ( R ) × S

W poprzednim przykładzie T reprezentuje tabelę w taki sposób, że każdy Student (ponieważ Student jest unikalnym kluczem / atrybutem tabeli Completed) jest połączony z każdym danym Zadaniem. Na przykład Eugene miałby dwa wiersze, Eugene → Database1 i Eugene → Database2 w T.

EG: Najpierw załóżmy, że „Completed” ma trzeci atrybut o nazwie „grade”. Tu jest niechciany bagaż, więc zawsze musimy go wyrzucać. W rzeczywistości w tym kroku możemy również usunąć 'Zadanie' z R; mnożenie zakłada go z powrotem.

T  := π _Student ( R ) × S // Daje nam to każdą możliwą pożądaną kombinację, w tym te, które w rzeczywistości nie istnieją w R, i wyłączając inne (np. Fred | kompilator1, który nie jest pożądaną kombinacją)

W kolejnym kroku odejmujemy R od T

relacja :

U  := T − R

W U mamy możliwe kombinacje, które „mogłyby” być w R , ale nie były.

EG: Znowu z projekcjami — T i R muszą mieć identyczne nazwy/nagłówki atrybutów.

U  := T − π _Student,Task ( R ) // To daje nam listę "czego brakuje".

Więc jeśli teraz weźmiemy projekcję na nazwy atrybutów unikalne dla R

wtedy mamy ograniczenia krotek w R, dla których nie wszystkie kombinacje z krotkami w S były obecne w R :

V  := π _{a 1 ,..., a n} ( U )

Np.: Projekt U aż do danego atrybutu (atrybutów) (Student)

V  := π _Student ( U )

Pozostaje więc wziąć rzut R na jego unikalne nazwy atrybutów i odjąć te w V :

W  := π _{a 1 ,..., a n} ( R ) − V

EG: W  := π _Student ( R ) − V .

Wspólne rozszerzenia

W praktyce opisana powyżej klasyczna algebra relacyjna jest rozszerzona o różne operacje, takie jak sprzężenia zewnętrzne, funkcje agregujące, a nawet domknięcie przechodnie.

Połączenia zewnętrzne

Podczas gdy wynik sprzężenia (lub sprzężenia wewnętrznego) składa się z krotek utworzonych przez połączenie pasujących krotek w dwóch operandach, sprzężenie zewnętrzne zawiera te krotki i dodatkowo kilka krotek utworzonych przez rozszerzenie niedopasowanej krotki w jednym z operandów o wartości „wypełnienia” dla każdego atrybutu drugiego operandu. Sprzężenia zewnętrzne nie są uważane za część omawianej do tej pory klasycznej algebry relacyjnej.

Operatory zdefiniowane w tej sekcji zakładają istnienie wartości null , ω , której nie definiujemy, do użycia dla wartości wypełnienia; w praktyce odpowiada to NULL w SQL. Aby kolejne operacje wyboru na wynikowej tabeli miały znaczenie, należy przypisać wartościom null znaczenie semantyczne; w podejściu Codda logika zdań używana przez selekcję jest rozszerzona do logiki trójwartościowej , chociaż pomijamy te szczegóły w tym artykule.

Zdefiniowane są trzy operatory sprzężenia zewnętrznego: lewe sprzężenie zewnętrzne, prawe sprzężenie zewnętrzne i pełne sprzężenie zewnętrzne. (Słowo „zewnętrzne” jest czasami pomijane.)

Lewe sprzężenie zewnętrzne (⟕)

Lewe sprzężenie zewnętrzne jest zapisywane jako R ⟕ S , gdzie R i S są relacjami . Wynikiem lewego sprzężenia zewnętrznego jest zestaw wszystkich kombinacji krotek w R i S, które są równe w ich wspólnych nazwach atrybutów, dodatkowo (w skrócie) do krotek w R , które nie mają pasujących krotek w S .

Jako przykład rozważmy tabele Employee i Dept oraz ich lewe sprzężenie zewnętrzne:

W wynikowej relacji krotki w S, które nie mają wspólnych wartości w wspólnych nazwach atrybutów z krotkami w R, przyjmują wartość pustą , ω .

Ponieważ nie istnieją żadne krotki w Dept z DEPTNAME o Finansów lub wykonawczy , Ohm s wystąpić w otrzymanym związku gdzie krotki w Pracownika mają DEPTNAME o Finansów lub wykonawczego .

Niech r ₁ , r ₂ , ..., r _n będą atrybutami relacji R i niech {( ω , ..., ω )} będzie relacją singletona na atrybutach, które są unikalne dla relacji S (tych, które nie są atrybutami R ). Następnie lewe sprzężenie zewnętrzne można opisać w kategoriach sprzężenia naturalnego (a więc za pomocą podstawowych operatorów) w następujący sposób:

${\ Displaystyle (R \ muszka S) \ filiżanka ((R-\ pi _ {r_ {1}, r_ {2}, \ kropki, r_ {n}} (R \ muszka S)) \ razy \ {(\ omega ,\kropki \omega )\})}$

Prawe sprzężenie zewnętrzne (⟖)

Prawe sprzężenie zewnętrzne działa prawie identycznie jak lewe sprzężenie zewnętrzne, ale role tabel są przełączane.

Prawe sprzężenie zewnętrzne relacji R i S jest zapisane jako R ⟖ S . Wynikiem prawego sprzężenia zewnętrznego jest zestaw wszystkich kombinacji krotek w R i S, które są równe w ich wspólnych nazwach atrybutów, oprócz krotek w S , które nie mają pasujących krotek w R .

Rozważmy na przykład tabele Employee i Dept oraz ich prawe sprzężenie zewnętrzne:

W wynikowej relacji krotki w R, które nie mają wspólnych wartości w wspólnych nazwach atrybutów z krotkami w S, przyjmują wartość pustą , ω .

Ponieważ nie istnieją żadne krotki w Pracownika z DEPTNAME of Production , Ohm s występować w imieniu i EmpID atrybuty powstałego związku gdzie krotki w Dept miał DEPTNAME z produkcji .

Niech s ₁ , s ₂ , ..., s _n będą atrybutami relacji S i niech {( ω , ..., ω )} będzie relacją singletona na atrybutach, które są unikalne dla relacji R (tych, które nie są atrybutami S ). Następnie, podobnie jak w przypadku lewego sprzężenia zewnętrznego, prawe sprzężenie zewnętrzne można symulować za pomocą sprzężenia naturalnego w następujący sposób:

${\ Displaystyle (R \ muszka S) \ filiżanka (\ {(\ omega, \ kropki, \ omega) \} \ razy (S- \ pi _ {s_ {1}, s_ {2}, \ kropki, s_ { n}}(R\muszka S)))}$

Pełne sprzężenie zewnętrzne (⟗)

W efekcie sprzężenie zewnętrzne lub pełne sprzężenie zewnętrzne łączy wyniki lewego i prawego sprzężenia zewnętrznego.

Pełne sprzężenie zewnętrzne jest zapisywane jako R ⟗ S , gdzie R i S są relacjami . Wynikiem pełnego sprzężenia zewnętrznego jest zestaw wszystkich kombinacji krotek w R i S, które są równe w ich wspólnych nazwach atrybutów, oprócz krotek w S , które nie mają pasujących krotek w R i krotek w R , które nie mają pasujących krotek w S w ich wspólnych nazwach atrybutów.

Rozważmy na przykład tabele Employee i Dept oraz ich pełne sprzężenie zewnętrzne:

W wynikowej relacji krotki w R, które nie mają wspólnych wartości w wspólnych nazwach atrybutów z krotkami w S, przyjmują wartość pustą , ω . Krotki w S, które nie mają wspólnych wartości w wspólnych nazwach atrybutów z krotkami w R, również przyjmują wartość pustą , ω .

Pełne sprzężenie zewnętrzne można zasymulować za pomocą lewego i prawego sprzężenia zewnętrznego (a tym samym sprzężenia naturalnego i sumy zbioru) w następujący sposób:

R ⟗ S = ( R ⟕ S ) ∪ ( R ⟖ S )

Operacje na obliczeniach dziedzinowych

W algebrze relacyjnej nie wprowadzono do tej pory niczego, co pozwalałoby na obliczenia na domenach danych (poza oceną wyrażeń zdań z uwzględnieniem równości). Na przykład nie jest możliwe wykorzystanie tylko wprowadzonej do tej pory algebry do napisania wyrażenia, które pomnoży liczby z dwóch kolumn, np. cenę jednostkową z ilością, aby otrzymać cenę całkowitą. Praktyczne języki zapytań mieć takich obiektów, np SQL SELECT umożliwia operacje arytmetyczne definiować nowe kolumny w wyniku , a podobny zakład jest bardziej wyraźnie przez Tutorial D „s słowa kluczowego. W teorii baz danych nazywa się to projekcją rozszerzoną . SELECT unit_price * quantity AS total_price FROM tEXTEND

Zbiór

Co więcej, obliczanie różnych funkcji na kolumnie, jak sumowanie jej elementów, również nie jest możliwe przy użyciu wprowadzonej do tej pory algebry relacyjnej. Istnieje pięć funkcji agregujących, które są zawarte w większości relacyjnych systemów baz danych. Te operacje to Suma, Liczba, Średnia, Maksimum i Minimum. W algebrze relacyjnej operacja agregacji na schemacie ( A ₁ , A ₂ , ... A _n ) jest zapisana w następujący sposób:

${\ Displaystyle G_ {1}, G_ {2}, \ ldots, G_ {m} \ g_ {f_ {1} ({A_ {1}} '), f_ {2} ({A_ {2}} ') ,\ldots ,f_{k}({A_{k}}')}\ (r)}$

gdzie każdy A _j ' , 1 ≤ j ≤ k , jest jednym z oryginalnych atrybutów A _i , 1 ≤ i ≤ n .

Atrybuty poprzedzające g to atrybuty grupujące, które działają jak klauzula „group by” w SQL. Następnie istnieje dowolna liczba funkcji agregacji zastosowanych do poszczególnych atrybutów. Operacja jest stosowana do dowolnej relacji r . Atrybuty grupowania są opcjonalne, a jeśli nie zostaną podane, funkcje agregacji są stosowane w całej relacji, do której zastosowano operację.

Załóżmy, że mamy tabelę o nazwie Konto z trzema kolumnami, a mianowicie Numer_konta, Nazwa_oddziału i Saldo . Chcemy znaleźć maksymalne saldo każdej gałęzi. Jest to realizowane przez _{Nazwa_oddziału} G _{Max( Saldo )} ( Konto ). Aby znaleźć najwyższe saldo ze wszystkich kont niezależnie od branży, możemy po prostu napisać G _{Max( Saldo )} ( Konto ).

Grupowanie jest często zapisywane jako _{Nazwa_oddziału} ɣ _{Max( Saldo )} ( Konto ).

Zamknięcie przechodnie

Chociaż algebra relacyjna wydaje się wystarczająco silna dla większości praktycznych celów, istnieją pewne proste i naturalne operatory relacji , których nie można wyrazić za pomocą algebry relacyjnej. Jednym z nich jest przechodnie zamknięcie relacji binarnej. Mając daną dziedzinę D , niech relacja binarna R będzie podzbiorem D × D . Zamknięcie przechodnie R ⁺ z R jest najmniejszym podzbiorem D × D, który zawiera R i spełnia następujący warunek:

${\ Displaystyle \ forall x \ forall y \ forall z \ lewo ((x, y) \ w R ^ {+} \ klin (y, z) \ w R ^ {+} \ strzałka w prawo (x, z) \ w R^{+}\prawo)}$

Nie istnieje wyrażenie algebry relacyjnej E ( R ) przyjmujące R jako zmienny argument dający R ⁺ . Można to udowodnić za pomocą faktu, że przy danym wyrażeniu relacyjnym E, dla którego twierdzi się, że E ( R ) = R ⁺ , gdzie R jest zmienną, zawsze możemy znaleźć instancję r dla R (i odpowiadającą mu dziedzinę d ) tak, że E ( r ) ≠ r ⁺ .

SQL jednak oficjalnie obsługuje takie zapytania punktów stałych od 1999 r. i miał rozszerzenia specyficzne dla dostawców w tym kierunku znacznie wcześniej.

Wykorzystanie własności algebraicznych do optymalizacji zapytań

Zapytania mogą być reprezentowane jako drzewo , gdzie

• węzły wewnętrzne są operatorami,
• liście to relacje ,
• poddrzewa to podwyrażenia.

Podstawowym celem jest przekształcenie drzew wyrażeń w równoważne drzewa wyrażeń , w których średnia wielkość relacji tworzonych przez podwyrażenia w drzewie jest mniejsza niż przed optymalizacją . Celem drugorzędnym jest próba utworzenia wspólnych wyrażeń podrzędnych w ramach jednego zapytania lub, jeśli w tym samym czasie jest oceniane więcej niż jedno zapytanie, we wszystkich tych zapytaniach. Uzasadnieniem drugiego celu jest to, że wystarczy raz obliczyć wspólne podwyrażenia, a wyniki mogą być używane we wszystkich zapytaniach, które zawierają to podwyrażenie.

Oto zestaw reguł, które można wykorzystać w takich przekształceniach.

Wybór

Najważniejszą rolę w optymalizacji zapytań odgrywają reguły dotyczące operatorów wyboru. Selekcja jest operatorem, który bardzo skutecznie zmniejsza liczbę wierszy w swoim operandzie, więc jeśli selekcje w drzewie wyrażeń zostaną przesunięte w kierunku liści, wewnętrzne relacje (wyrażone przez podwyrażenia) prawdopodobnie się skurczą.

Podstawowe właściwości selekcji

Wybór jest idempotentny (wielokrotne zastosowania tego samego wyboru nie mają dodatkowego efektu poza pierwszym) i przemiennym (kolejność selekcji jest stosowana w nie ma wpływu na ostateczny wynik).

1. ${\ Displaystyle \ Sigma _ {A} (R) = \ Sigma _ {A} \ Sigma _ {A} (R) \ \!}$
2. ${\ Displaystyle \ Sigma _ {A} \ Sigma _ {B} (R) = \ Sigma _ {B} \ Sigma _ {A} (R) \ \!}$

Rozbijanie selekcji ze złożonymi warunkami

Selekcja, której warunkiem jest koniunkcja prostszych warunków, jest równoważna sekwencji selekcji o tych samych indywidualnych warunkach, a selekcja, której warunkiem jest alternatywa, jest równoważna połączeniu selekcji. Tożsamości tych można używać do scalania selekcji, aby mniej selekcji musiało być ocenianych, lub do ich dzielenia, aby selekcje komponentów można było oddzielnie przenosić lub optymalizować.

1. ${\ Displaystyle \ sigma _ {A \ ziemia B} (R) = \ sigma _ {A} (\ sigma _ {B} (R)) = \ sigma _ {B} (\ sigma _ {A} (R) )}$
2. ${\ Displaystyle \ sigma _ {A \ lub B} (R) = \ sigma _ {A} (R) \ filiżanka \ sigma _ {B} (R)}$

Wybór i produkt krzyżowy

Produkt krzyżowy jest najbardziej kosztownym operatorem do oceny. Jeśli relacje wejściowe mają N i M wierszy, wynik będzie zawierał wiersze. Dlatego ważne jest, aby zmniejszyć rozmiar obu operandów przed zastosowaniem operatora iloczynu krzyżowego. ${\displaystyle NM}$

Można to skutecznie zrobić, jeśli po produkcie krzyżowym następuje operator wyboru, np . . Biorąc pod uwagę definicję złączenia, jest to najbardziej prawdopodobny przypadek. Jeśli po produkcie krzyżowym nie następuje operator selekcji, możemy spróbować przesunąć selekcję w dół z wyższych poziomów drzewa wyrażeń, korzystając z innych reguł selekcji. ${\ Displaystyle \ sigma _ {A} (R \ razy P)}$

W powyższym przypadku warunek A jest dzielony na warunki B , C i D przy użyciu reguł podziału dotyczących złożonych warunków selekcji, tak że i B zawiera atrybuty tylko z R , C zawiera atrybuty tylko z P , a D zawiera część A, który zawiera atrybuty z R i P . Zauważ, że B , C lub D są prawdopodobnie puste. Następnie obowiązuje: ${\ Displaystyle A = B \ klin C \ klin D}$

${\ Displaystyle \ sigma _ {A} (R \ razy P) = \ sigma _ {B \ klin C \ klin D} (R \ razy P) = \ sigma _ {D} (\ sigma _ {B} (R )\times \sigma _{C}(P))}$

Operatory selekcji i zestawów

Wybór jest rozdzielczy względem ustawionych operatorów różnicy, przecięcia i sumy. Poniższe trzy reguły służą do wypychania zaznaczenia poniżej operacji zestawu w drzewie wyrażeń. W przypadku różnicy zbiorów i operatorów przecięcia możliwe jest zastosowanie operatora wyboru tylko do jednego z operandów po transformacji. Może to być korzystne, gdy jeden z operandów jest mały, a obciążenie związane z oceną operatora wyboru przewyższa korzyści wynikające z użycia mniejszej relacji jako operandu.

1. ${\ Displaystyle \ sigma _ {A} (R \ setminus P) = \ sigma _ {A} (R) \ setminus \ sigma _ {A} (P) = \ Sigma _ {A} (R) \ setminus P}$
2. ${\ Displaystyle \ sigma _ {A} (R \ filiżanka P) = \ sigma _ {A} (R) \ filiżanka \ sigma _ {A} (P)}$
3. ${\ Displaystyle \ sigma _ {A} (R \ cap P) = \ sigma _ {A} (R) \ cap \ sigma _ {A} (P) = \ sigma _ {A} (R) \ cap P = R\cap \sigma _{A}(P)}$

Wybór i projekcja

Wybór zmienia się z rzutowaniem wtedy i tylko wtedy, gdy pola, do których odwołuje się warunek wyboru, są podzbiorem pól w rzutowaniu. Wykonywanie wyboru przed rzutowaniem może być przydatne, jeśli operand jest iloczynem krzyżowym lub złączeniem. W innych przypadkach, jeśli warunek selekcji jest stosunkowo drogi do obliczenia, przeniesienie zaznaczenia poza projekcję może zmniejszyć liczbę krotek, które należy przetestować (ponieważ projekcja może generować mniej krotek ze względu na eliminację duplikatów wynikających z pominiętych pól).

${\ Displaystyle \ pi _ {a_ {1}, \ ldots, a_ {n}} (\ sigma _ {A} (R)) = \ sigma _ {A} (\ pi _ {a_ {1}, \ ldots ,a_{n}}(R)){\text{ gdzie pola w }}A\subseteq \{a_{1},\ldots ,a_{n}\}}$

Występ

Podstawowe właściwości rzutowania

Projekcja jest idempotentna, więc seria (prawidłowych) projekcji jest równoważna projekcji najbardziej zewnętrznej.

${\ Displaystyle \ pi _ {a_ {1}, \ ldots, a_ {n}} (\ pi _ {b_ {1}, \ ldots, b_ {m}} (R)) = \ pi _ {a_ {1 },\ldots ,a_{n}}(R){\text{ gdzie }}\{a_{1},\ldots ,a_{n}\}\subseteq \{b_{1},\ldots ,b_{ m}\}}$

Operatory rzutowania i scenografii

Projekcja jest dystrybucyjna w stosunku do zestawu.

${\ Displaystyle \ pi _ {a_ {1}, \ ldots, a_ {n}} (R \ filiżanka P) = \ pi _ {a_ {1}, \ ldots, a_ {n}} (R) \ filiżanka \ pi _{a_{1},\ldots ,a_{n}}(P).\,}$

Projekcja nie rozkłada się na przecięcie i nie ustawia różnicy. Kontrprzykłady podaje:

${\ Displaystyle \ pi _ {A} (\ {\ langle A = a, B = b \ rangle \} \ czapka \ {\ langle A = a, B = b' \ rangle \}) = \ pusty zestaw}$

${\ Displaystyle \ pi _ {A} (\ {\ langle A = a, B = b \ rangle \}) \ czapka \ pi _ {A} (\ {\ langle A = a, B = b' \ rangle \ })=\{\langle A=a\rangle \}}$

oraz

${\ Displaystyle \ pi _ {A} (\ {\ langle A = a, B = b \ rangle \} \ setminus \ {\ langle A = a, B = b' \ rangle \}) = \ {\ langle A =a\rangle \}}$

${\ Displaystyle \ pi _ {A} (\ {\ langle A = a, B = b \ rangle \}) \ setminus \ pi _ {A} (\ {\ langle A = a, B = b' \ rangle \ })=\pusty zestaw \,,}$

gdzie zakłada się, że b jest różne od b' .

Przemianować

Podstawowe właściwości zmiany nazwy

Kolejne zmiany nazwy zmiennej można zwinąć w jedną zmianę nazwy. Operacje zmiany nazwy, które nie mają wspólnych zmiennych, mogą być dowolnie porządkowane względem siebie, co można wykorzystać do tworzenia kolejnych zmian nazw sąsiadujących, tak aby można je było zwinąć.

1. ${\ Displaystyle \ rho _ {a/b} (\ rho _ {b/c} (R)) = \ rho _ {a/c} (R) \ \!}$
2. ${\ Displaystyle \ rho _ {a/b} (\ rho _ {c/d} (R)) = \ rho _ {c/d} (\ rho _ {a/b} (R)) \ \! }$

Zmień nazwę i ustaw operatorów

Zmiana nazwy jest dystrybucyjna względem ustawionej różnicy, sumy i przecięcia.

1. ${\ Displaystyle \ rho _ {a/b} (R \ setminus P) = \ rho _ {a/b} (R) \ setminus \ rho _ {a/b} (P)}$
2. ${\ Displaystyle \ rho _ {a/b} (R \ filiżanka P) = \ rho _ {a/b} (R) \ filiżanka \ rho _ {a/b} (P)}$
3. ${\ Displaystyle \ rho _ {a/b} (R \ czapka P) = \ rho _ {a/b} (R) \ czapka \ rho _ {a/b} (P)}$

Produkt i związek

Produkt kartezjański jest rozdzielczy nad zjednoczeniem.

1. ${\ Displaystyle (A \ razy B) \ filiżanka (A \ razy C) = A \ razy (B \ filiżanka C)}$

Realizacje

Pierwszym językiem zapytań opartym na algebrze Codda była Alpha, opracowana przez samego dr Codda. Następnie utworzono ISBL , a ta pionierska praca została doceniona przez wiele autorytetów jako wskazówka , jak przekuć ideę Codda w użyteczny język. Business System 12 był krótkotrwałym relacyjnym DBMS o dużej sile w branży, wzorowanym na przykładzie ISBL.

W 1998 roku Chris Date i Hugh Darwen zaproponowali język o nazwie Tutorial D, przeznaczony do wykorzystania w nauczaniu teorii relacyjnych baz danych, a jego język zapytań również czerpie z pomysłów ISBL. Rel jest implementacją Samouczka D .

Nawet język zapytań SQL jest luźno oparty na algebrze relacyjnej, chociaż operandy w SQL ( tabele ) nie są dokładnie relacjami i kilka użytecznych twierdzeń o algebrze relacyjnej nie ma zastosowania w odpowiedniku SQL (prawdopodobnie ze szkodą dla optymalizatorów i/ lub użytkowników). Model tabeli SQL jest torbą ( multiset ), a nie zestawem. Na przykład wyrażenie jest twierdzeniem dla algebry relacyjnej na zbiorach, ale nie dla algebry relacyjnej na workach; omówienie algebry relacyjnej na workach patrz rozdział 5 podręcznika "Complete" autorstwa Garcii-Moliny , Ullmana i Widoma . ${\ Displaystyle (R \ filiżanka S) \ setminus T = (R \ setminus T) \ filiżanka (S \ setminus T)}$

Zobacz też

Bibliografia

Dalsza lektura

Praktycznie każdy podręcznik akademicki dotyczący baz danych zawiera szczegółową analizę klasycznej algebry relacyjnej.

• Imieliński, T. ; Lipski, W. (1984). „Relacyjny model danych i algebr cylindrycznych” . Journal of Computer and System Sciences . 28 : 80–102. doi : 10.1016/0022-0000(84)90077-1 .(Dla relacji z algebrami cylindrycznymi ).

Zewnętrzne linki

• SZCZUR. Programowy tłumacz algebry relacyjnej na SQL
• Filmy z wykładami: Przetwarzanie algebry relacyjnej — wprowadzenie do tego, jak systemy baz danych przetwarzają algebrę relacyjną
• Notatki do wykładu: Algebra relacyjna – szybki samouczek adaptacji zapytań SQL do algebry relacyjnej
• Relacyjne – graficzna implementacja algebry relacyjnej
• Query Optimization (Strona usunięta; Najbliższe alternatywy: Standford Query Optimization 2 , Badania Microsoft Query Optimization w systemach relacyjnych , Artykuł Stanford: Query Optimization )Ten artykuł jest wprowadzeniem do wykorzystania algebry relacyjnej w optymalizacji zapytań i zawiera liczne cytaty, aby dowiedzieć się więcej dogłębne badanie.
• Relacyjny system algebry dla Oracle i Microsoft SQL Server
• Pireal – eksperymentalne narzędzie edukacyjne do pracy z algebrą relacyjną
• DES – narzędzie edukacyjne do pracy z algebrą relacyjną i innymi językami formalnymi
• RelaX - Relational Algebra Calculator (oprogramowanie open-source dostępne jako usługa online bez rejestracji)
• RA: tłumacz algebry relacyjnej
• Tłumaczenie SQL na algebrę relacyjną