1 Relacyjny model danychWykład 2 S. Kozielski

2 Model danych struktury danych operacje na danychograniczenia integralnościowe

3 Relacyjny model danychrelacje operacje (operatory) algebry relacji więzy referencyjne + ograniczenia dziedzin relacji

4 Relacja (matematyka) X, Y – zbiory,X, Y – zbiory, Iloczyn kartezjański X Y = {(x,y): xX  yY} Dwuczłonowa relacja w X Y = {(x,y): xX  yY  x  y}  X Y N – członowa relacja (relacja stopnia N): podzbiór iloczynu kartezjańskiego X1  X2  X3  ...  XN

5 Relacja – bazy danych Atrybuty: A1, A2, A3, … np.: nazwisko, nrp, kwota, adres Dziedziny atrybutów: DA1, DA2, DA3,... (inaczej domeny: dom(A1), dom(A2)) – zbiory dopuszczalnych wartości atrybutów (typy danych) Schemat relacji: R = { A1, A2, ..., Ap} – podzbiór zbioru atrybutów Relacja r o schemacie R: r(R) - podzbiór iloczynu kartezjańskiego dziedzin atrybutów tworzących schemat DA1  DA2  ...  DAp r(R)  DA1  DA2  ...  DAp

6 Przykład: R = {nrp, nrt, kwota} Dnrp= {1, 2, 3}, Dnrt= {1, 2, 3}, Dkwota= {150, 200, 300} Dnrp  Dnrt  Dkwota= {1, 1, 150 2, 1, 150 3, 1, 150 … 3, 3, 150 3, 3, 200 3, 3, 300} gdzie vi  DAi lub jest specjalną wartością pustą NULL. (A, B, C) ———— a1 b1 c1 - krotka t1. a2 b2 c2 - krotka t2. a3 b3 c3 - krotka t3. a4 b4 c4 - krotka t4. n-ty element krotki t oznaczany jest przez t[An] np. t4[B] = b4.", "width": "800" } 9 Elementarne własności relacjiKażdy atrybut relacji ma unikalną nazwę Porządek atrybutów w relacji nie jest istotny Porządek krotek w relacji nie jest istotny Relacja nie zawiera krotek powtarzających się (wszystkie krotki są unikalne) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/9/Elementarne+w%C5%82asno%C5%9Bci+relacji.jpg", "name": "Elementarne własności relacji", "description": "Każdy atrybut relacji ma unikalną nazwę. Porządek atrybutów w relacji nie jest istotny. Porządek krotek w relacji nie jest istotny. Relacja nie zawiera krotek powtarzających się (wszystkie krotki są unikalne)", "width": "800" } 10 Unikalność krotek relacji a pojęcie kluczaKażdy podzbiór S atrybutów schematu relacji R (S  R), taki że dla każdych dwóch krotek ze zbioru r(R) zachodzi ti [S] ≠ tj [S] jest nazywany superkluczem (super key) relacji Superkluczem jest m.in. cały schemat relacji R Superklucz może posiadać nadmiarowe atrybuty { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/10/Unikalno%C5%9B%C4%87+krotek+relacji+a+poj%C4%99cie+klucza.jpg", "name": "Unikalność krotek relacji a pojęcie klucza", "description": "Każdy podzbiór S atrybutów schematu relacji R (S  R), taki że dla każdych dwóch krotek ze zbioru r(R) zachodzi ti [S] ≠ tj [S] jest nazywany superkluczem (super key) relacji. Superkluczem jest m.in. cały schemat relacji R. Superklucz może posiadać nadmiarowe atrybuty.", "width": "800" } 11 Pojęcie klucza relacjiKluczem K schematu relacji R nazywamy superklucz schematu R o takiej własności, że usunięcie dowolnego atrybutu A z K powoduje, że K’ = K - A nie jest już superkluczem Klucz jest minimalnym superkluczem (zachowującym własność unikalności krotek relacji) Schemat relacji może posiadać więcej niż jeden klucz Wyróżniony klucz: klucz główny (podstawowy) Pozostałe klucze: klucze kandydujące (wtórne) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/11/Poj%C4%99cie+klucza+relacji.jpg", "name": "Pojęcie klucza relacji", "description": "Kluczem K schematu relacji R nazywamy superklucz schematu R o takiej własności, że usunięcie dowolnego atrybutu A z K powoduje, że K’ = K - A nie jest już superkluczem. Klucz jest minimalnym superkluczem (zachowującym własność unikalności krotek relacji) Schemat relacji może posiadać więcej niż jeden klucz. Wyróżniony klucz: klucz główny (podstawowy) Pozostałe klucze: klucze kandydujące (wtórne)", "width": "800" } 12 Inna definicja klucza Kluczem jest minimalny zestaw atrybutów schematu relacji, którego wartości jednoznacznie identyfikują każdą krotkę relacji { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/12/Inna+definicja+klucza+Kluczem+jest+minimalny+zestaw+atrybut%C3%B3w+schematu+relacji%2C+kt%C3%B3rego+warto%C5%9Bci+jednoznacznie+identyfikuj%C4%85+ka%C5%BCd%C4%85+krotk%C4%99+relacji..jpg", "name": "Inna definicja klucza Kluczem jest minimalny zestaw atrybutów schematu relacji, którego wartości jednoznacznie identyfikują każdą krotkę relacji.", "description": "Inna definicja klucza Kluczem jest minimalny zestaw atrybutów schematu relacji, którego wartości jednoznacznie identyfikują każdą krotkę relacji.", "width": "800" } 13 Przykład Pracownicy (nrp, imię, nazwisko, PESEL, NIP, seria_i_nr_dowodu, data_urodzenia, imię_ojca, imię_matki, adres, nazwisko_rodowe, tytuł, zawód, nazwa_zakładu_pracy, adres_zp, staż) Klucze kandydujące: nrp PESEL NIP seria_i_nr_dowodu imię, nazwisko, imię_ojca { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/13/Przyk%C5%82ad.jpg", "name": "Przykład", "description": "Pracownicy (nrp, imię, nazwisko, PESEL, NIP, seria_i_nr_dowodu, data_urodzenia, imię_ojca, imię_matki, adres, nazwisko_rodowe, tytuł, zawód, nazwa_zakładu_pracy, adres_zp, staż) Klucze kandydujące: nrp. PESEL. NIP. seria_i_nr_dowodu. imię, nazwisko, imię_ojca.", "width": "800" } 14 Różne formy opisu stosowane w modelu relacyjnymOpis formalny Opis tablicowy Opis fizyczny (fizycznych struktur d.) relacja tablica (tabela) plik krotka wiersz rekord atrybut kolumna pole schemat relacji nagłówek tablicy typ rekordu { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/14/R%C3%B3%C5%BCne+formy+opisu+stosowane+w+modelu+relacyjnym.jpg", "name": "Różne formy opisu stosowane w modelu relacyjnym", "description": "Opis formalny. Opis tablicowy. Opis fizyczny. (fizycznych struktur d.) relacja. tablica (tabela) plik. krotka. wiersz. rekord. atrybut. kolumna. pole. schemat relacji. nagłówek tablicy. typ rekordu.", "width": "800" } 15 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://images.slideplayer.pl/1/80634/slides/slide_16.jpg", "name": "", "description": "", "width": "800" } 16 Algebra relacji Dane relacje: r(R), s(S)Podstawowe operacje: selekcja, projekcja, złączenie, iloczyn kartezjański, dzielenie, operacje na zbiorach Selekcja w – warunek selekcji (wyrażenie logiczne - predykat) w(r) = {t : t  r  w(t) = True } = p(R) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/16/Algebra+relacji+Dane+relacje%3A+r%28R%29%2C+s%28S%29.jpg", "name": "Algebra relacji Dane relacje: r(R), s(S)", "description": "Podstawowe operacje: selekcja, projekcja, złączenie, iloczyn kartezjański, dzielenie, operacje na zbiorach. Selekcja. w – warunek selekcji (wyrażenie logiczne - predykat) w(r) = {t : t  r  w(t) = True } = p(R)", "width": "800" } 17 Przykład selekcji A B C 2 1 C=2  { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/17/Przyk%C5%82ad+selekcji+A+B+C+2+1+%EF%81%B3C%3D2+%EF%83%9E.jpg", "name": "Przykład selekcji A B C 2 1 C=2 ", "description": "Przykład selekcji A B C 2 1 C=2 ", "width": "800" } 18 Projekcja Niech X  R X(r) = { u : t  r  u = t [X] } = q (X) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/18/Projekcja+Niech+X+%EF%83%8D+R+%EF%81%B0X%28r%29+%3D+%7B+u+%3A+t+%EF%83%8E+r+%EF%83%99+u+%3D+t+%5BX%5D+%7D+%3D+q+%28X%29.jpg", "name": "Projekcja Niech X  R X(r) = { u : t  r  u = t [X] } = q (X)", "description": "Projekcja Niech X  R X(r) = { u : t  r  u = t [X] } = q (X)", "width": "800" } 19 Przykład projekcji A B C AC  { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/19/Przyk%C5%82ad+projekcji+A+B+C+%EF%81%B0AC+%EF%83%9E.jpg", "name": "Przykład projekcji A B C AC ", "description": "Przykład projekcji A B C AC ", "width": "800" } 20 Złączenie (naturalne)r  s = { u : t  r  w  s  t [R  S] = w [R  S]  u[R] = t  u[S] = w} = z (R  S) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/20/Z%C5%82%C4%85czenie+%28naturalne%29.jpg", "name": "Złączenie (naturalne)", "description": "r  s = { u : t  r  w  s  t [R  S] = w [R  S]  u[R] = t  u[S] = w} = z (R  S)", "width": "800" } 21 Przykład złączenia naturalnegor (A, B, C) s (C, D) z (A, B, C, D) ————  ——— = ————— a1 b1 c c1 d a1 b1 c1 d1 a2 b2 c c5 d a4 b4 c1 d1 a3 b3 c3 a4 b4 c1 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/21/Przyk%C5%82ad+z%C5%82%C4%85czenia+naturalnego.jpg", "name": "Przykład złączenia naturalnego", "description": "r (A, B, C) s (C, D) z (A, B, C, D) ————  ——— = ————— a1 b1 c1 c1 d1 a1 b1 c1 d1. a2 b2 c2 c5 d5 a4 b4 c1 d1. a3 b3 c3. a4 b4 c1.", "width": "800" } 22 Ogólna postać złączenia ( - złączenie)r w s = w (r  s) lub r  AB s =  AB (r  s) , gdzie A  R, B  S, dom(A) = dom(B) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/22/Og%C3%B3lna+posta%C4%87+z%C5%82%C4%85czenia+%28%EF%81%91+-+z%C5%82%C4%85czenie%29.jpg", "name": "Ogólna postać złączenia ( - złączenie)", "description": "r w s = w (r  s) lub. r  AB s =  AB (r  s) , gdzie A  R, B  S, dom(A) = dom(B)", "width": "800" } 23 Dzielenie Niech będą dane relacje: r(XY), s(Y)r  s = { u : w  s t  r t [Y] = w  t [X] = u } { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/23/Dzielenie+Niech+b%C4%99d%C4%85+dane+relacje%3A+r%28XY%29%2C+s%28Y%29.jpg", "name": "Dzielenie Niech będą dane relacje: r(XY), s(Y)", "description": "r  s = { u : w  s t  r t [Y] = w  t [X] = u }", "width": "800" } 24 Przykład dzielenia ———— ——— ——— 1 1 1 1 1 2 2 3 1 3 3 2 2 2 3 3 1 3 2r (nrp, nrt) s (nrt) r  s = z (nrp) ———— ——— ——— 2 2 2 3 3 1 3 2 3 3 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/24/Przyk%C5%82ad+dzielenia+%E2%80%94%E2%80%94%E2%80%94%E2%80%94+%E2%80%94%E2%80%94%E2%80%94+%E2%80%94%E2%80%94%E2%80%94+1+1+1+1+1+2+2+3+1+3+3+2+2+2+3+3+1+3+2.jpg", "name": "Przykład dzielenia ———— ——— ——— 1 1 1 1 1 2 2 3 1 3 3 2 2 2 3 3 1 3 2", "description": "r (nrp, nrt) s (nrt) r  s = z (nrp) ———— ——— ——— 1 1 1 1. 1 2 2 3. 1 3 3. 2 2. 2 3. 3 1. 3 2. 3 3.", "width": "800" } 25 Operatory mnogościowe (operacje na zbiorach krotek)Niech będą dane relacje: r(R), s(R) Suma: r  s Różnica: r \ s Iloczyn: r  s Powyższe operacje mogą być rozszerzone na przypadek relacji r(R), s(S), w których R i S są równoliczne, a odpowiadające sobie atrybuty schematów R i S mają identyczne dziedziny { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/25/Operatory+mnogo%C5%9Bciowe+%28operacje+na+zbiorach+krotek%29.jpg", "name": "Operatory mnogościowe (operacje na zbiorach krotek)", "description": "Niech będą dane relacje: r(R), s(R) Suma: r  s. Różnica: r \ s. Iloczyn: r  s. Powyższe operacje mogą być rozszerzone na przypadek relacji r(R), s(S), w których R i S są równoliczne, a odpowiadające sobie atrybuty schematów R i S mają identyczne dziedziny.", "width": "800" } 26 Pytanie Z1 jako wyrażenie algebry relacjiZ1 = nazwa (nazwisko = ‘Jaworek’ (Pracownicy  Wypłaty  Tematy)) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/26/Pytanie+Z1+jako+wyra%C5%BCenie+algebry+relacji.jpg", "name": "Pytanie Z1 jako wyrażenie algebry relacji", "description": "Z1 = nazwa (nazwisko = ‘Jaworek’ (Pracownicy  Wypłaty  Tematy))", "width": "800" } 27 Złączenie tabel Pracownicy Wypłaty nrp nrt kwota 2 300 3 150 1 200 nrpnazwisko adres nrz 1 Lipowski Ruda 2 Grabski Zabrze 3 Jaworek Gliwice { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/27/Z%C5%82%C4%85czenie+tabel+Pracownicy+Wyp%C5%82aty+nrp+nrt+kwota+2+300+3+150+1+200+nrp.jpg", "name": "Złączenie tabel Pracownicy Wypłaty nrp nrt kwota 2 300 3 150 1 200 nrp", "description": "nazwisko. adres. nrz. 1. Lipowski. Ruda. 2. Grabski. Zabrze. 3. Jaworek. Gliwice.", "width": "800" } 28 Pracownicy  Wypłaty nrp nazwisko adres nrz nrt kwota 2 GrabskiZabrze 1 300 3 Jaworek Gliwice 150 Lipowski Ruda 200 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/28/Pracownicy+%EF%81%B7%EF%81%B6+Wyp%C5%82aty+nrp+nazwisko+adres+nrz+nrt+kwota+2+Grabski.jpg", "name": "Pracownicy  Wypłaty nrp nazwisko adres nrz nrt kwota 2 Grabski", "description": "Zabrze. 1. 300. 3. Jaworek. Gliwice. 150. Lipowski. Ruda. 200.", "width": "800" } 29 Pracownicy  Wypłaty  Tematynrp nazwisko adres nrz nrt kwota nazwa kier. 2 Grabski Zabrze 1 300 Pr. przetwor. 3 Jaworek Gliwice 150 Pr. reaktora Lipowski Ruda Pr. zasilacza 200 { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/29/Pracownicy+%EF%81%B7%EF%81%B6+Wyp%C5%82aty+%EF%81%B7%EF%81%B6+Tematy.jpg", "name": "Pracownicy  Wypłaty  Tematy", "description": "nrp. nazwisko. adres. nrz. nrt. kwota. nazwa. kier. 2. Grabski. Zabrze. 1. 300. Pr. przetwor. 3. Jaworek. Gliwice. 150. Pr. reaktora. Lipowski. Ruda. Pr. zasilacza. 200.", "width": "800" } 30 nazwisko = ‘Jaworek’ (Pracownicy  Wypłaty  Tematy)nrp nazwisko adres nrz nrt kwota nazwa kier. 3 Jaworek Gliwice 1 150 Pr. reaktora 2 200 Pr. przetwor. { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/30/%EF%81%B3nazwisko+%3D+%E2%80%98Jaworek%E2%80%99+%28Pracownicy+%EF%81%B7%EF%81%B6+Wyp%C5%82aty+%EF%81%B7%EF%81%B6+Tematy%29.jpg", "name": "nazwisko = ‘Jaworek’ (Pracownicy  Wypłaty  Tematy)", "description": "nrp. nazwisko. adres. nrz. nrt. kwota. nazwa. kier. 3. Jaworek. Gliwice. 1. 150. Pr. reaktora. 2. 200. Pr. przetwor.", "width": "800" } 31 nazwa (nazwisko = ‘Jaworek’ (Pracownicy  Wypłaty  Tematy))Pr. reaktora Pr. przetwor. { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/31/%EF%81%B0nazwa+%28%EF%81%B3nazwisko+%3D+%E2%80%98Jaworek%E2%80%99+%28Pracownicy+%EF%81%B7%EF%81%B6+Wyp%C5%82aty+%EF%81%B7%EF%81%B6+Tematy%29%29.jpg", "name": "nazwa (nazwisko = ‘Jaworek’ (Pracownicy  Wypłaty  Tematy))", "description": "Pr. reaktora. Pr. przetwor.", "width": "800" } 32 Własności operatorów algebry relacjir(R), s(S), z(Z) – dane relacje 1) Przemienność złączeń: r  s = s  r 2) Łączność złączeń: (r  s)  z = r  (s  z) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/32/W%C5%82asno%C5%9Bci+operator%C3%B3w+algebry+relacji.jpg", "name": "Własności operatorów algebry relacji", "description": "r(R), s(S), z(Z) – dane relacje. 1) Przemienność złączeń: r  s = s  r. 2) Łączność złączeń: (r  s)  z = r  (s  z)", "width": "800" } 33 3) Przemienność selekcji i złączeń dla wyrażenia w(r  s)Niech atr(w) – zbiór atrybutów występujących w w Jeśli atr(w)  R, to w(r  s) = (w(r ))  s Jeśli atr(w)  S, to w(r  s) = r  (w(s )) Jeśli w= w1  w2 oraz atr(w1)  R i atr(w2)  S, to w(r  s) = (w1(r ))  (w2(s)) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/33/3%29+Przemienno%C5%9B%C4%87+selekcji+i+z%C5%82%C4%85cze%C5%84+dla+wyra%C5%BCenia+%EF%81%B3w%28r+%EF%81%B7%EF%81%B6+s%29.jpg", "name": "3) Przemienność selekcji i złączeń dla wyrażenia w(r  s)", "description": "Niech atr(w) – zbiór atrybutów występujących w w. Jeśli atr(w)  R, to w(r  s) = (w(r ))  s. Jeśli atr(w)  S, to w(r  s) = r  (w(s )) Jeśli w= w1  w2 oraz atr(w1)  R i atr(w2)  S, to w(r  s) = (w1(r ))  (w2(s))", "width": "800" } 34 Przykłady równoważnej postaci wyrażeńP1=nazwisko (nrz=3kwota>2000 (Pracownicy  Wypłaty)) P1= nazwisko ((nrz=3 (Pracownicy))  (kwota>2000 (Wypłaty))) P2= nazwisko (nazwa = ‘Pr.gen.’ (Pracownicy  Wypłaty  Tematy)) P2= nazwisko (Pracownicy  Wypłaty (nazwa = ‘Pr.gen.’ (Tematy))) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/34/Przyk%C5%82ady+r%C3%B3wnowa%C5%BCnej+postaci+wyra%C5%BCe%C5%84.jpg", "name": "Przykłady równoważnej postaci wyrażeń", "description": "P1=nazwisko (nrz=3kwota>2000 (Pracownicy  Wypłaty)) P1= nazwisko ((nrz=3 (Pracownicy))  (kwota>2000 (Wypłaty))) P2= nazwisko (nazwa = ‘Pr.gen.’ (Pracownicy  Wypłaty  Tematy)) P2= nazwisko (Pracownicy  Wypłaty (nazwa = ‘Pr.gen.’ (Tematy)))", "width": "800" } 35 Drzewo rozbioru wyrażenia algebry relacji – plan realizacji zapytania { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/35/Drzewo+rozbioru+wyra%C5%BCenia+algebry+relacji+%E2%80%93+plan+realizacji+zapytania.jpg", "name": "Drzewo rozbioru wyrażenia algebry relacji – plan realizacji zapytania", "description": "Drzewo rozbioru wyrażenia algebry relacji – plan realizacji zapytania", "width": "800" } 36 Optymalizacja wyrażeń algebry relacji (wykorzystanie przemienności selekcji i złączeń) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/36/Optymalizacja+wyra%C5%BCe%C5%84+algebry+relacji+%28wykorzystanie+przemienno%C5%9Bci+selekcji+i+z%C5%82%C4%85cze%C5%84%29.jpg", "name": "Optymalizacja wyrażeń algebry relacji (wykorzystanie przemienności selekcji i złączeń)", "description": "Optymalizacja wyrażeń algebry relacji (wykorzystanie przemienności selekcji i złączeń)", "width": "800" } 37 P2= nazwisko (nazwa = ‘Pr.gen.’ (Pracownicy  Wypłaty  Tematy)) P2= nazwisko (Pracownicy  Wypłaty (nazwa = ‘Pr.gen.’ (Tematy))) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/37/P2%3D+%EF%81%B0nazwisko+%28%EF%81%B3nazwa+%3D+%E2%80%98Pr.gen.%E2%80%99+%28Pracownicy+%EF%81%B7%EF%81%B6+Wyp%C5%82aty+%EF%81%B7%EF%81%B6+Tematy%29%29.jpg", "name": "P2= nazwisko (nazwa = ‘Pr.gen.’ (Pracownicy  Wypłaty  Tematy))", "description": "P2= nazwisko (Pracownicy  Wypłaty (nazwa = ‘Pr.gen.’ (Tematy)))", "width": "800" } 38 Optymalizacja wyrażeń algebry relacji (dobór kolejności złączeń - 1) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/38/Optymalizacja+wyra%C5%BCe%C5%84+algebry+relacji+%28dob%C3%B3r+kolejno%C5%9Bci+z%C5%82%C4%85cze%C5%84+-+1%29.jpg", "name": "Optymalizacja wyrażeń algebry relacji (dobór kolejności złączeń - 1)", "description": "Optymalizacja wyrażeń algebry relacji (dobór kolejności złączeń - 1)", "width": "800" } 39 Optymalizacja wyrażeń algebry relacji (dobór kolejności złączeń - 2) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/80634/1/images/39/Optymalizacja+wyra%C5%BCe%C5%84+algebry+relacji+%28dob%C3%B3r+kolejno%C5%9Bci+z%C5%82%C4%85cze%C5%84+-+2%29.jpg", "name": "Optymalizacja wyrażeń algebry relacji (dobór kolejności złączeń - 2)", "description": "Optymalizacja wyrażeń algebry relacji (dobór kolejności złączeń - 2)", "width": "800" } 40 Proste reguły optymalizacji wyrażeń algebry relacjiPrzenieść selekcje (i projekcje) jak najwyżej w drzewie rozbioru wyrażenia Wykonać projekcje razem ze złączeniami lub selekcjami Dobrać kolejność złączeń według selekcji najsilniej redukujących

7 Wypłaty  Dnrp  Dnrt  Dkwota2 300 3 150 1 200 Wypłaty  Dnrp  Dnrt  Dkwota

8 Relacja jako zbiór krotekr(R) = {t1, t2, t3, …, tk} Krotka t jest uporządkowaną listą wartości t = < v1,v2 …vp> gdzie vi  DAi lub jest specjalną wartością pustą NULL (A, B, C) ———— a1 b1 c krotka t1 a2 b2 c krotka t2 a3 b3 c krotka t3 a4 b4 c krotka t4 n-ty element krotki t oznaczany jest przez t[An] np. t4[B] = b4

9 Elementarne własności relacjiKażdy atrybut relacji ma unikalną nazwę Porządek atrybutów w relacji nie jest istotny Porządek krotek w relacji nie jest istotny Relacja nie zawiera krotek powtarzających się (wszystkie krotki są unikalne)

10 Unikalność krotek relacji a pojęcie kluczaKażdy podzbiór S atrybutów schematu relacji R (S  R), taki że dla każdych dwóch krotek ze zbioru r(R) zachodzi ti [S] ≠ tj [S] jest nazywany superkluczem (super key) relacji Superkluczem jest m.in. cały schemat relacji R Superklucz może posiadać nadmiarowe atrybuty

11 Pojęcie klucza relacjiKluczem K schematu relacji R nazywamy superklucz schematu R o takiej własności, że usunięcie dowolnego atrybutu A z K powoduje, że K’ = K - A nie jest już superkluczem Klucz jest minimalnym superkluczem (zachowującym własność unikalności krotek relacji) Schemat relacji może posiadać więcej niż jeden klucz Wyróżniony klucz: klucz główny (podstawowy) Pozostałe klucze: klucze kandydujące (wtórne)

12 Inna definicja klucza Kluczem jest minimalny zestaw atrybutów schematu relacji, którego wartości jednoznacznie identyfikują każdą krotkę relacji

13 Przykład Pracownicy (nrp, imię, nazwisko, PESEL, NIP, seria_i_nr_dowodu, data_urodzenia, imię_ojca, imię_matki, adres, nazwisko_rodowe, tytuł, zawód, nazwa_zakładu_pracy, adres_zp, staż) Klucze kandydujące: nrp PESEL NIP seria_i_nr_dowodu imię, nazwisko, imię_ojca

14 Różne formy opisu stosowane w modelu relacyjnymOpis formalny Opis tablicowy Opis fizyczny (fizycznych struktur d.) relacja tablica (tabela) plik krotka wiersz rekord atrybut kolumna pole schemat relacji nagłówek tablicy typ rekordu

15

16 Algebra relacji Dane relacje: r(R), s(S)Podstawowe operacje: selekcja, projekcja, złączenie, iloczyn kartezjański, dzielenie, operacje na zbiorach Selekcja w – warunek selekcji (wyrażenie logiczne - predykat) w(r) = {t : t  r  w(t) = True } = p(R)

17 Przykład selekcji A B C 2 1 C=2 

18 Projekcja Niech X  R X(r) = { u : t  r  u = t [X] } = q (X)

19 Przykład projekcji A B C AC 

20 Złączenie (naturalne)r  s = { u : t  r  w  s  t [R  S] = w [R  S]  u[R] = t  u[S] = w} = z (R  S)

21 Przykład złączenia naturalnegor (A, B, C) s (C, D) z (A, B, C, D) ————  ——— = ————— a1 b1 c c1 d a1 b1 c1 d1 a2 b2 c c5 d a4 b4 c1 d1 a3 b3 c3 a4 b4 c1

22 Ogólna postać złączenia ( - złączenie)r w s = w (r  s) lub r  AB s =  AB (r  s) , gdzie A  R, B  S, dom(A) = dom(B)

23 Dzielenie Niech będą dane relacje: r(XY), s(Y)r  s = { u : w  s t  r t [Y] = w  t [X] = u }

24 Przykład dzielenia ———— ——— ——— 1 1 1 1 1 2 2 3 1 3 3 2 2 2 3 3 1 3 2r (nrp, nrt) s (nrt) r  s = z (nrp) ———— ——— ——— 2 2 2 3 3 1 3 2 3 3

25 Operatory mnogościowe (operacje na zbiorach krotek)Niech będą dane relacje: r(R), s(R) Suma: r  s Różnica: r \ s Iloczyn: r  s Powyższe operacje mogą być rozszerzone na przypadek relacji r(R), s(S), w których R i S są równoliczne, a odpowiadające sobie atrybuty schematów R i S mają identyczne dziedziny

26 Pytanie Z1 jako wyrażenie algebry relacjiZ1 = nazwa (nazwisko = ‘Jaworek’ (Pracownicy  Wypłaty  Tematy))

27 Złączenie tabel Pracownicy Wypłaty nrp nrt kwota 2 300 3 150 1 200 nrpnazwisko adres nrz 1 Lipowski Ruda 2 Grabski Zabrze 3 Jaworek Gliwice

28 Pracownicy  Wypłaty nrp nazwisko adres nrz nrt kwota 2 GrabskiZabrze 1 300 3 Jaworek Gliwice 150 Lipowski Ruda 200

29 Pracownicy  Wypłaty  Tematynrp nazwisko adres nrz nrt kwota nazwa kier. 2 Grabski Zabrze 1 300 Pr. przetwor. 3 Jaworek Gliwice 150 Pr. reaktora Lipowski Ruda Pr. zasilacza 200

30 nazwisko = ‘Jaworek’ (Pracownicy  Wypłaty  Tematy)nrp nazwisko adres nrz nrt kwota nazwa kier. 3 Jaworek Gliwice 1 150 Pr. reaktora 2 200 Pr. przetwor.

31 nazwa (nazwisko = ‘Jaworek’ (Pracownicy  Wypłaty  Tematy))Pr. reaktora Pr. przetwor.

32 Własności operatorów algebry relacjir(R), s(S), z(Z) – dane relacje 1) Przemienność złączeń: r  s = s  r 2) Łączność złączeń: (r  s)  z = r  (s  z)

33 3) Przemienność selekcji i złączeń dla wyrażenia w(r  s)Niech atr(w) – zbiór atrybutów występujących w w Jeśli atr(w)  R, to w(r  s) = (w(r ))  s Jeśli atr(w)  S, to w(r  s) = r  (w(s )) Jeśli w= w1  w2 oraz atr(w1)  R i atr(w2)  S, to w(r  s) = (w1(r ))  (w2(s))

34 Przykłady równoważnej postaci wyrażeńP1=nazwisko (nrz=3kwota>2000 (Pracownicy  Wypłaty)) P1= nazwisko ((nrz=3 (Pracownicy))  (kwota>2000 (Wypłaty))) P2= nazwisko (nazwa = ‘Pr.gen.’ (Pracownicy  Wypłaty  Tematy)) P2= nazwisko (Pracownicy  Wypłaty (nazwa = ‘Pr.gen.’ (Tematy)))

35 Drzewo rozbioru wyrażenia algebry relacji – plan realizacji zapytania

36 Optymalizacja wyrażeń algebry relacji (wykorzystanie przemienności selekcji i złączeń)

37 P2= nazwisko (nazwa = ‘Pr.gen.’ (Pracownicy  Wypłaty  Tematy)) P2= nazwisko (Pracownicy  Wypłaty (nazwa = ‘Pr.gen.’ (Tematy)))

38 Optymalizacja wyrażeń algebry relacji (dobór kolejności złączeń - 1)

39 Optymalizacja wyrażeń algebry relacji (dobór kolejności złączeń - 2)

40 Proste reguły optymalizacji wyrażeń algebry relacjiPrzenieść selekcje (i projekcje) jak najwyżej w drzewie rozbioru wyrażenia Wykonać projekcje razem ze złączeniami lub selekcjami Dobrać kolejność złączeń według selekcji najsilniej redukujących