Relacja matematyczna R: r í D1 ´ D2 ´



Pobieranie 93,8 Kb.
Data29.10.2017
Rozmiar93,8 Kb.

BAD420 – Podstawy relacyjnego modelu danych i algebra relacji str.


RELACJA MATEMATYCZNA R:

R  D1  D2  ...  Dn = {(d1, d2, ... ,dn) : di  Di, i = 1,2,...n}, Di – zbiór. R jest więc zbiorem ciągów.


RELACJA W SENSIE CODD’A:

Zbiór atrybutów: {A1, A2, ... } – zbiór symboli zwanych atrybutami.

Dziedzina atrybutu: D = dom(A) – zbiór wartości (prostych) atrybutu A,
NULL  dom(A) dla każdego atrybutu A.
Krotką (ang. tuple) typu U = {A1, ..., An} nazywamy zbiór par:

t = [A1 : a1, ..., An : an], gdzie ai  Di, dla i = 1, ..., n.


Każdy zbiór par powyższej postaci jest funkcją z U w zbiór wartości V = D1  ...  Dn,

zatem krotka jest funkcją, t : U V taką, że dla każdego A  U, t(A)  D.


Relacją typu U nazywamy dowolny skończony podzbiór zbioru wszystkich krotek typu U.
OZNACZENIA:


  • KROTKA(U) – zbiór wszystkich krotek typu U.

  • KROTKA() = {} – zbiór zawiera jedną krotkę pustą , (typu , o długości zero).

  • null(U) - krotka null-owa typu U, dla każdego atrybutu A  U, null(A) = NULL.




  • REL(U) - zbiór wszystkich relacji typu U.

  • REL() = {, {}}, gdzie:

 - pusta relacja typu , nie zawierająca żadnej krotki;

{} - relacja typu  z jedną krotkę pustą.



  • U, X, Y, V, W – zbiory atrybutów (typy relacji),

  • R(U), S(X) - relacje typu U, X, gdy typ wynika z kontekstu, to piszemy R, S

  • t(U), r(X), ... - krotki typu U, X , gdy typ wynika z kontekstu, to piszemy t, r

  • zamiast: r = {(A1, a1), ..., (An, an)} piszemy: r = (a1, ..., an) (domyślne uporządkowanie atrybutów w typie relacji i takie same uporządkowanie wartości w krotce);

  • zamiast R({A, B}) piszemy R(A, B)

  • zamiast R(X  Y) piszemy R(X, Y)


OPERACJE NA RELACJACH (ALGEBRA RELACJI):

  • mnogościowe (suma, różnica, przekrój, dopełnienie)

  • relacyjne (projekcja, selekcja, przemianowanie, iloczyn kartezjański, złączenie, podzielenie)


OPERACJE MNOGOŚCIOWE NA RELACJACH:

Suma, różnica, przekrój, dopełnienie (ograniczone znaczenie praktyczne)

Operandy: R(U), S(U) - relacje jednakowego typu U. Wynik T – relacja typu U.
Suma mnogościowa (ang. union)

 T = R S = {t | t  R  t  S}. Wynik T jest relacją typu U



Rozszerzenia:

uwzględnienie kompatybilności atrybutów (zgodności atrybutów). Mówimy, że atrybut A jest kompatybilny z atrybutem B, jeśli dom(A)=dom(B).

sumy zewnętrzne (otwarte, ang. outer union)

niech Z = X  Y,

relacja R uzupełniana jest o kolumny Z – X, które wypełniane są wartościami NULL, mamy R’(Z),

relacja S uzupełniana jest o kolumny Z – Y, które wypełniane są wartościami NULL, mamy S’(Z), przyjmujemy:

 R(X) outer union S(Y) = R’(Z)  S’(Z).
Różnica mnogościowa (ang. difference)

 T = R S = {t | t  R  t  S}.



Przekrój (ang. intersection)

 T = R S = {t | t  R  t  S}.


Dopełnienie (ang. complement)

T = – R T(X) = KROTKA(X) – R (X), gdzie KROTKA (X) oznacza relację pełną i musi ona być zbiorem skończonym, co nie zawsze jest realne. W praktyce dopełnienie nie jest więc stosowane.




OPERACJE RELACYJNE:

Ograniczenie krotki:

r(U) - krotka typu U, X U.

t(X) - nazywamy ograniczeniem krotki r do zbioru X,

t = X(r), (lub t = r[X]) dla każdego A X , t(A) = r(A).



Złączenie krotek:

Krotki r(X), s(Y) są naturalnie złączalne w.it.w., gdy mają równe wartości na wspólnych atrybutach, tj. na zbiorze X  Y.

Krotkę t(X  Y) - nazywamy złączeniem naturalnym (ang. natural join) krotek r i s,

 t(X  Y) = r(X) >< s(Y)  X(t) = r  Y(t) = s.

Właściwości operacji na krotkach:

r[] =  – wynikiem ograniczenie krotki do zbioru pustego jest krotka pusta,

r >< s = s >< r – złączenie krotek jest przemienne,

r >< (s >< t) = (r >< s) >< t – złączenie krotek jest łączne,

r ><  = r – krotka pusta jest elementem neutralnym (jednostkowym) dla złączenia.
Projekcja, rzut (ang. projection) relacji:

Niech R(U) będzie relacja typu U i niech X  U. Relację T(X) nazywamy projekcją R na X,

co oznaczamy T = R[X] lub T = X (R), w.i t.w., gdy:

 T = {t |  r  R. t = X(r)}

Szczególny przypadek:

(R) = if R =  then  else {},

gdzie {} - relacja typu  złożona z jednej krotki pustej.
Selekcja (ang. selection):

Niech A, A'  U, v  V,   {=, , <, , >, , like, ... },



Warunkiem selekcji nazywamy wyrażenie E o następującej składni:

E ::= A  v | A  A' | (E) | E | E  E | E  E


Relację T nazywamy selekcją relacji R względem warunku selekcji E,

co zapisujemy: T = E (R) lub T = R/E/, w.i t.w., gdy:

 T = {t  R | E(t) = TRUE}.

Obliczanie E(t):

(A  v)(t) = t(A)  v

(A  A' ) = t(A)  t(A' )

(E)(t) = (E(t))

(E  E' )(t) = E(t)  E'(t)

(E  E' )(t) = E(t)  E'(t)


Uwaga: Języki relacyjnych baz danych (np. SQL) opierają się na logice trójwartościowej o wartościach: TRUE, FALSE i UNKNOWN („nieznana”).

t(A)  NULL = UNKNOWN,

NULL  v = unknown dla każdego v, również równego NULL.
Przemianowanie (ang. renaming):

Niech R(U) będzie relacją typu U, a A i B niech będą atrybutami, przy czym A  U, B  U. Niech W = U – {A}  {B}. Relację T(W) nazywamy przemianowaniem w relacji R atrybutu A na atrybut B, co oznaczamy T = AB(R), w.i t.w., gdy

 T = {t |  r  R. t = U – {A}(r) >< [B : r(A)]}.

Iloczyn kartezjański (ang. cross join, Cartesian product)

Niech R(X) i S(Y) będą relacjami, gdzie X = {A1, ..., An}, Y = {B1, ..., Bm}. Oznaczmy: R.X = {R.A1, ..., R.An,}, S.Y = {S.B1, ..., S.Bm}.

Iloczynem kartezjańskim R i S nazywamy relację T typu R.X  S.Y, co oznaczamy
T = R S, w.i t.w., gdy:


 T = {t | R.X(t)  R  S.Y(t)  S }.
Do wyniku należą więc wszystkie możliwe kombinacje „każdy-z-każdym” krotek z R i z S.

Uwaga: W iloczynie kartezjańskim atrybuty są prefiksowane nazwami relacji, z których pochodzą aby uzyskać niepowtarzalność atrybutów w typie relacji. Możliwy jest też inny sposób ujednoznacznienia nazw, np. poprzez uwzględnienia pozycji atrybutu lub dowolne przemianowanie.

Złączenie (ang. join):

Relację T(X  Y) nazywamy złączeniem naturalnym (ang. natural join) relacji R(X) i S(Y), co zapisujemy: T = R >< S, w.it.w., gdy

 T = {t | X(t)  R  Y(t)  S}.

Inaczej:  T = R >< S = {t |  r  R.  s  S. t = r >< s}.

Specjalne przypadki:

jeśli X = Y, to R >< S = R  S; jeśli X  Y = , to R >< S = R  S;


Właściwości (dla relacji R typu U)

R >< {} = R; R ><  = ,

R >< X(R) = R, X  U, R  X(R) >< Y(R), X  Y = U,

R >< S = S >< R R >< (S >< T) = (R >< S) >< T


Ogólna postać złączenia: -złączenie, theta-złączenie (-join):

Niech R(X), S(Y) – będą relacjami, gdzie X = {A1, ..., An}, Y = {B1, ..., Bm} i niech

  {=, , <, , >, , like, ... }.

Warunkiem złączenia nazywamy wyrażenie F o następującej składni:

F ::= R.A  S.B | (F) | F | F  F | F  F


Relację T nazywamy -złączeniem relacji R i S względem warunku złączenia F, co zapisujemy: T = R >< F S, w.it.w., gdy

 T = {t  R  S | E(t) = TRUE}.

-złączenie jest więc selekcją z iloczynu kartezjańskiego: R >< F S = F (R  S).
Złączenia zewnętrzne (ang. outer join):

złączenie zewnętrzne lewostronne (ang. left outer join)

Relację T(X  Y) nazywamy złączeniem zewnętrznym lewostronnym relacji R(X) i S(Y), co oznaczamy T = R +>< F S, w. i t.w., gdy:

 T={t | t  R  S  F(t) = TRUE}  {X(t)  null(Y – X) | t  R  S  F(t)  TRUE},

tzn. do wyniku należą wszystkie krotki relacji R (lewy operand) połączone albo z dopasowaną krotką z relacji S, albo uzupełniona wartościami NULL, gdy brak dopasowanej krotki (krotka s jest dopasowana do r, jeśli F(r >< s) = TRUE).



złączenie zewnętrzne prawostronne (ang. right outer join)

Relację T(X  Y) nazywamy złączeniem zewnętrznym prawostronnym relacji R(X) i S(Y), co oznaczamy T = R ><+ F S, w. i t.w., gdy:

 T={t | t  R  S  F(t) = TRUE}  {Y(t)  null(X – Y) | t  R  S  F(t)  TRUE},

tzn. do wyniku należą wszystkie krotki relacji S (prawy operand) połączone albo z dopasowaną krotką z relacji R, albo uzupełniona wartościami NULL, gdy brak dopasowanej krotki.



złączenie zewnętrzne pełne (ang. full outer join)

Relację T(X  Y) nazywamy złączeniem zewnętrznym pełnym relacji R(X) i S(Y), co oznaczamy T = R +><+ F S, w. i t.w., gdy:  T = R +>< F S  R ><+ F S.


Podzielenie (ang. division):

Niech X  U. Relację T(U – X) nazywamy podzieleniem relacji R(U) przez S(X), co oznaczamy T = R S, w. i t.w., gdy

 T = {t  U – X(R) |  s  S. t >< s  R}.

  1. T(U-X) = R(U) S(X) = U-X (R)- U-X ((U-X (R)  S) - R)


  2. Niech N = count(S), n = count(R[t,X]), gdzie t  R[U-X], jeśli n = N to tT(U-X)


Oznaczenia:

Projekcja: X (R) lub R[X]

Selekcja: E (R) lub R/E/

Złączenie: R >< F S


ZADANIA
1. Niech A1 = {a, b, c, d}

A2 = {x, y, z}

A3 = {a, b, c, d}

A4 = {1, 2, 3, 4, 5, 6}

A5 = {x, y, z}

A6 = {m, n, p, u, v}


R1 A1 A2 R2 A1 A2 A4 R3 A3 A5

a x a y 1 a x

a y b y 2 a z

b x c z 1 c x

d z d x 3 d z

a z a y 2

a x 4

a x 5



R4 A1 A4 A6 R5 A1 A2 R6 A2

a 1 m a x x

b 1 p a z y

c 3 p b x z

c 4 u c z

Dla podanych niżej operacji algebry relacji



  1. obliczyć wynik wykonania operacji (podać postać tablicy wynikowej)

  2. napisać zapytanie w języku SQL realizujące podaną operację




    1. R1(A1, A2)  R5(A1, A2); R1(A1, A2)  R3(A3, A5) (atrybuty kompatybilne)

    2. – R1(A1, A2)

    3. R1(A1, A2) – R5(A1, A2)

    4. R1(A1, A2)  R5(A1, A2)

    5. R2[A1, A2]

    6. R2|(A1=a A2 =x) A4 3| (podać kolejne kroki wartościowania)

    7. R1(A1, A2) R6(A2)

    8. R3  R5 (iloczyn kartezjański)

    9. R3 >< A1=A3 R5

    10. R3 +>< A1=A3 R5

    11. R3 ><+ A1=A3 R5

    12. R3 +><+ A1=A3 R5

2. Zbiór operacji mnogościowych (suma, różnica, przekrój dopełnienie) nie jest minimalny, np. jeżeli zdefiniowana jest suma i dopełnienie to:
RS = - (-R  -S)

R-S = R(-S) = -(-RS)


Zdefiniuj podobne związki jeżeli przyjąć, że dane są:

  1. suma i różnica

  2. przekrój i dopełnienie

  3. przekrój i różnica



3. Udowodnij (korzystając z definicji) następujące własności operatora selekcji:

  1. E (RS) = E (R)  E (S)

  2. E1E2 (R) = E1 (E2 (R)) = E2 (E1 (R)) = E1 (R)  E2 (R)

  3. E1E2 (R) = E1 (R) E2 (R)




©operacji.org 2017
wyślij wiadomość

    Strona główna