R-19.DOC

Rozdział 19

Elementy teorii relacyjnych baz danych

W rozdziale prezentujemy materiał dotyczący matematycznych podstaw relacyjnego modelu danych. Z uwagi na charakter książki[1] nie jest to opis kompletny.

Relacyjny model baz danych stworzony został przez E.F. Codda w roku 1970.

Termin "relacyjna baza danych" oznacza bazę zbudowaną z relacji. Po przeczytaniu poprzednich dwóch rozdziałów, w których koncentrowaliśmy się na opisie tabel, Czytelnik zadaje sobie pewnie pytanie, co wspólnego ma tabela z relacją?

Relacja to abstrakcyjny termin matematyki (którego definicję podajemy poniżej), natomiast tabela jest konkretną reprezentacją relacji. Wynika z tego, że jedna relacja może być odwzorowana za pomocą wielu różnych tabel. W modelu relacyjnym przyjmuje się, że:

-          kolejność wierszy i kolumn w tabelach jest nieistotna (to, że dane Krzysia przechowywane są w czwartym wierszu tabeli Uczeń, jak i to, że wiersz zawierający informacje o imionach rodziców poprzedza wiersz z danymi o telefonie kontaktowym nie ma żadnego znaczenia dla SZBD)

-          wiersze zawierające takie same dane są identyczne.

Natomiast w tabeli przedstawiającej konkretny przypadek relacji identyczne dane przechowywane będą w różnych wierszach. 

Do zdefiniowania terminu relacja potrzebne nam będą dwie podstawowe definicje:

Def.1 Schematem relacji nazywamy zbiór R = {A1,A2,....An};

gdzie: A1,A2,....An są atrybutami (reprezentowanymi poprzez nazwy kolumn).                                                                               

Tabela Uczeń, opisywana w poprzednim rozdziale, jest przykładem schematu relacji                     Uczeń = {ID ucznia, Imię, Nazwisko, Adres, Imiona rodziców, Telefon kontaktowy}

Każdemu atrybutowi A przyporządkowany jest zbiór dopuszczalnych wartości (odpowiada mu typ zmiennych).                                                                                                                                             Na przykład dziedzinami atrybutów w przypadku tabeli Ocena są:

Dom (ID ucznia) = TEKST (5)[2]

Dom (Ocena) = LICZBA (1,1)[3]

Dom (Zdobyta za) = TEKST (50)

Dom (ID przedmiotu) = TEKST (5)

Def.2 Dziedziną relacji o schemacie R = {A1,A2,....An} nazywamy sumę dziedzin wszystkich jej atrybutów Dom (R) = Dom (A1) È Dom (A2) È .... È Dom (An).

Tak więc dziedziną relacji odwzorowanej na tabeli Ocena będzie suma dziedzin wszystkich jej atrybutów: Dom (ID ucznia) È Dom (Ocena) È Dom (Zdobyta za) È Dom (ID przedmiotu).

Def. 3 Relacja o schemacie R = {A1,A2,....An} jest to skończony zbiór r = {t1,t2,....tm} odwzorowań ti : R à Dom (R) takich, że dla każdego j z zakresu  1<=j<=n, zachodzi zależność: ti(Aj) ÎDom (Aj).

Pojedyncze odwzorowanie nosi nazwę krotki i odpowiada mu pojedynczy wiersz tabeli. Przykładem krotki będzie następujący wiersz pochodzący z tabeli Uczeń:

Kolejnym, niezbędnym dla zrozumienia teorii relacyjnych baz danych terminem, jest Klucz. Do zdefiniowania tego terminu konieczne jest wprowadzenie jeszcze dwóch definicji:

Def. 4 Ograniczeniem krotki t relacji r o schemacie R do zbioru atrybutów X Í R nazywamy odwzorowanie będące ograniczeniem krotki t do zbioru atrybutów X, tIX: X à Dom (X)

Na przykład, ograniczeniem krotki z poprzedniego przykładu do zbioru atrybutów X = {ID ucznia, Imię, Nazwisko} będzie krotka:

Def. 5 Relacja r o schemacie R = {A1,A2,....An} spełnia zależność funkcyjną X à Y (X,Y Í R), jeżeli dla każdych dwóch krotek t,u Îr zachodzi warunek: jeśli tIX = uIX to tIY = uIY

To znaczy, że o spełnieniu przez pewną relację zależności funkcyjnej postaci X à Y możemy mówić wtedy, jeżeli w ramach krotek tej relacji wartości atrybutów zbioru X jednoznacznie determinują wartości atrybutów zbioru Y.

Dla relacji przedstawionej za pomocą tabeli Uczeń możemy wskazać następujący zbiór spełniających ją zależności funkcyjnych[4]:

ID ucznia à {Imię, Nazwisko, Adres, Imiona rodziców, telefon kontaktowy}

{Imię, Nazwisko} à {ID ucznia, Adres, Imiona rodziców, telefon kontaktowy}

{telefon kontaktowy, Imię} à {ID ucznia, Nazwisko, Adres, Imiona rodziców}

Przyjrzyjmy się po kolei każdej z wymienionych zależności funkcyjnych.

Ponieważ pole ID ucznia dodaliśmy do bazy Dziennik właśnie po to, aby móc zawsze jednoznacznie określić, którego z uczniów opisują dane atrybuty (takie jak ocena z poszczególnych przedmiotów, Nr szafki, czy Imiona rodziców) możemy być pewni, że wartość tego atrybutu jednoznacznie określa wartości wszystkich pozostałych atrybutów tabeli. Innymi słowy, wartość JBA wskazuje na Jasia Badurę, jego dane personalne , oceny i szafkę w szatni.

Kombinacja imienia i nazwiska ucznia również pozwala nam jednoznacznie określić, o którego z uczniów "chodzi". Jednak, w przeciwieństwie od poprzedniej zależności funkcyjnej, ta jest spełniana w danym momencie, tzn. dla aktualnie przechowywanych w bazie danych. Po dopisaniu do bazy nowego ucznia o identycznym imieniu i nazwisku jak imię i nazwisko ucznia już w bazie zarejestrowanego,  nie będziemy mogli na podstawie imienia i nazwiska jednoznacznie określić pozostałych atrybutów ucznia.

Za pomocą kombinacji imienia i numeru telefonu możemy jednoznacznie zidentyfikować ucznia w bazie. Z dość dużym prawdopodobieństwem moglibyśmy wykorzystywać tę kombinację nie tylko dla aktualnie wprowadzonych danych, ale również w przyszłości — prawdopodobieństwo, że do szkoły zostanie przyjęty uczeń o takim samym imieniu i z takim samym numerem  telefonu kontaktowego jest raczej niewielkie (o ile wykluczyć przypadek rodzeństwa, któremu rodzice dla wygody nadali takie same imiona). Jednak w praktyce staramy się znaleźć i wykorzystać jako klucz zależność  funkcyjną o najmniejszym z możliwych zakresie zbioru X.

Def. 6 Nadkluczem relacji  r o schemacie R = {A1,A2,....An} nazywamy dowolny zbiór atrybutów X Í R taki, że zachodzi zależność funkcyjna X à R. Innymi słowy, o nadkluczu mówimy w przypadku, gdy wartość każdego atrybutu jest jednoznacznie zdeterminowana przez wartość atrybutów zbioru X. Jednym z nadkluczy jest zawsze zbiór wszystkich atrybutów R.

Def. 7 Kluczem relacji  r o schemacie R = {A1,A2,....An} nazywamy każdy minimalny nadklucz, tzn. taki nadklucz, który nie zawiera w sobie żadnego nadklucza. Tak więc zbiór atrybutów X jest kluczem, jeżeli wartość każdego atrybutu w R jest jednoznacznie zdeterminowana przez wartość atrybutów zbioru X i żaden z podzbiorów zbioru X nie posiada już tej własności. Dla każdej relacji można wskazać co najmniej jeden klucz, przy czym najczęściej jest ich więcej.

Spróbujmy znaleźć klucze relacji odwzorowanej na tabelę Uczeń:

Na mocy def. 7 nadkluczem tej relacji jest zbiór X1 = {ID ucznia, Imię, Nazwisko, Adres, Imiona rodziców, telefon kontaktowy}. Ponieważ podzbiór zbioru X2 ={ID ucznia, Imię, Nazwisko} również jest nadkluczem tej relacji, zbiór X1, na mocy def. 7 nie jest kluczem relacji Uczeń. Z tego samego powodu zbiór X2, również  nie jest kluczem relacji. Minimalnym nadkluczem, do jakiego doprowadzi nas te rozumowanie to zbiór X3 = {ID ucznia}. I jest to jeden z poszukiwanych kluczy relacji. Kolejnym kluczem jest zbiór X4 = {telefon kontaktowy, Imię}. Znalezienie następnych kluczy pozostawiamy Czytelnikowi.

Spośród wszystkich kluczy  relacji wyróżnia się jeden (nazywany kluczem głównym lub kluczem podstawowym) w odróżnieniu od  kluczy kandydujących. Atrybuty wchodzące w skład klucza głównego z reguły zaznacza się przez ich podkreślenie. Dla relacji Uczeń wybraliśmy na klucz główny klucz ID ucznia. Efektem powyższych ustaleń jest następujący zapis relacji:

Uczeń = {ID ucznia, Imię, Nazwisko, Adres, Imiona rodziców, telefon kontaktowy}

W rozdziale przedstawiliśmy, w sposób nieco bardziej formalny, informacje zawarte w rozdziałach 17 i 18. Na tak zdefiniowanych relacjach możliwe jest dokonywanie kilku przekształceń. Praktyczne podejście do przekształceń dokonywanych na danych przedstawione zostanie w rozdziale następnym. Osoby, które będą miały pewne trudności z materiałem przedstawionym poniżej powinny najpierw przestudiować rozdział 20, a po jego lekturze jeszcze raz spróbować wrócić do drugiej części bieżącego rozdziału.

Operatory relacyjnych baz danych

Pierwszy typ przekształceń, które można wykonywać na relacjach , wynika z definicji relacji jako pewnego zbioru. Doskonale Czytelnikowi znanym operatorom algebry zbiorów, czyli È Ç -, odpowiadają operatory UNION (suma relacji), INTERSEC (cześć wspólna relacji, przecięcie, przekrój relacji) i MINUS (dopełnienie relacji, różnica relacji).

Na sumę dwóch relacji rÈs składają się wszystkie elementy relacji r i wszystkie elementy relacji s.  Wynikiem przecięcia relacji rÇs jest relacja składająca się z elementów wspólnych relacji r i s. Wynikiem odjęcia relacji r-s jest relacja powstała w wyniku usunięcia z relacji r wszystkich elementów wchodzących w skład relacji s.

Dodatkowo, dla operacji na relacjach zdefiniowane są następujące operatory: selekcji, projekcji, iloczynu kartezjańskiego i złączenia naturalnego. Poniżej podajemy ich definicje.

Def. 8 Selekcją relacji  r o schemacie R = {A1,A2,....An} nazywamy zbiór tych krotek relacji r , w których wartością atrybutu A jest element a, przy założeniu, że  AÎR , a ÎDom(A), co zapisujemy sA=a(r) = {tÎr / t(A)=a}, oraz, dla dowolnego warunku logicznego F, zbiór krotek relacji r spełniających warunek F, co zapisujemy sF(r) = {tÎr / t spełnia warunek F}

Tak więc: s NAZWISKO=JANOWSKA(Uczeń) = {t}; gdzie t jest następującą krotką:

t(ID ucznia)= MJA, t(Imię)= Małgosia,

t(Adres)= Gliwice 35-212, ul. Paśki 3b,

t(Imiona rodziców)= Marcin, Magda, t(Telefon kontaktowy)= 299-717-921

Dla operatora selekcji prawdziwe są następujące twierdzenia:

T1. sF(rÈs) = sF(r) È sF(s); selekcja sumy relacji równa jest sumie selekcji

T2. sF(rÇs) = sF(r) Ç sF(s); selekcja przecięcia relacji równa jest przecięciu selekcji

T3. sF(r-s) = sF(r) - sF(s); selekcja różnicy relacji równa jest różnicy selekcji.

Na podstawie twierdzeń T1 — T3 możemy w dowolny sposób zmieniać kolejność operacji teoriomnogościowych względem selekcji. Zmiana kolejności operacji nie wpłynie na jej wynik.

Def. 9 Projekcją relacji r na zbiór atrybutów XÍR  nazywamy zbiór ograniczeń do atrybutów zbioru X wszystkich krotek relacji r, co zapisujemy p X(r) = {tIX: tÎr}

Tak więc: p Imie, Nazwisko(Nauczyciel)= {Maurycy, Polak; Zdybek, Sęk; Michał, Pasek}

Dla operatora projekcji prawdziwe są następujące twierdzenia:

T4. pX(pY(r)) = p X(r) przy założeniu, że XÍY

T5. pX((rÈs) = p X(r) È p X(s); projekcja sumy relacji równa jest sumie projekcji

T6. sF(p X(r)) = p X(sF (r)); selekcja projekcji równa jest projekcji selekcji

Na przykład:

p Imię...