Myszkorowski K. - Systemy baz danych

l

Krzysztof Myszkorowski

Systemy baz danych

Wydział Fizyki Technicznej Informatyki i Matematyki Stosowanej Politechniki Łódzkiej Łódź 2002

Systemy baz danych

Krzysztof Myszkorowski

Treści

JKIEM ZARZĄDZANIA BAZĄ DANYCH ZWOŻENIA SYSTEMÓW BAZ DANYCH

7

\BSTRAKCJADANYCH

8

:• NIEZALEŻNOŚĆ DANYCH

10

- JĘZYK DEFINIOWANIA DANYCH

10

: JĘZYK MANIPULOWANIA DANYMI

10

- ADMINISTRATOR BAZY DANYCH - UŻYTKOWNICY BAZ DANYCH

11 11

! ARCHITEKTURA SYSTEMU ZARZĄDZANIA BAZĄ DANYCH

12

l

. MODELE DANYCH 1.

7

14

MODEL HIERARCHICZNY

15

li MODEL SIECIOWY

18

13. MODEL RELACYJNY

21

%*ODEL ZWIĄZKÓW ENCJI..........:........^..;.!.....

22

3L1.ENCJE I ZBIORY ENCJI

22

12. ZWIĄZKI MIĘDZY ENCJAMI

22

13. SILNE i SŁABE ENCJE

24

3.4. DIAGRAMY ZWIĄZKÓW ENCJI

...24

3 J. SPECJALIZACJA i GENERALIZACJA

26

3.5.1. Specjalizacja 3.5.2. Generalizacja 3.5.3. Więzy integralności 3.5.4. Dziedziczenie

26 27 27 28

3.6. AGREGACJA 4 RELACYJNY MODEL DANYCH

31 .......................i..............„...:...^......™..

33

4.1. DEFINICJE WSTĘPNE

33

42. ALGEBRA RELACJI

36

4.2.1. Operacje podstawowe 4.2.2. Dodatkowe operatory algebraiczne 4.2.3. Przykłady zastosowań

36 39 43

4.3. JĘZYK MANIPULOWANIA DANYMI SQL

45

4.4. PERSPEKTYWY

54

4.5. OSADZONY SQL

55

4.6. PROJEKTÓW ANIE MODELU RELACYJNEGO NA PODSTAWIE MODELU ZWIĄZKÓW ENCJI

56

;.-&'

-l

5. NORMALIZACJA RELACJI

60

5.1. ZALEŻNOŚCI FUNKCYJNE

61

5.2. TRZECIA POSTAĆ NORMALNA

62

5.3. ROZKŁADY RELACJI 5.4. POSTAĆ NORMALNA BOYCE'A-CODDA

66 68

5.5. CZWARTA POSTAĆ NORMALNA 5.6. PIĄTA POSTAĆ NORMALNA

69 72

6. MODEL OBIEKTOWO ZORIENTOWANEJ BAZY DANYCH

74

6.1. KRÓTKI PRZEGLĄD MODELU COCOON

74

6.2. UOGÓLNIONE OPERACJE AKTUALIZUJĄCE

77

6.3. WARUNKI INTEGRALNOŚCI

78

6.4. ODWZOROWANIE MODELU COCOON NA MODEL RELACYJNY

78

6. 5. TWORZENIE REGUŁ i PROCEDUR

80

LITERATURA

83

l

O

Wstęp

Zagadnienia związane z wykorzystaniem maszyn cyfrowych do przechowywania informacji stanowią jeden z najważniejszych nurtów współczesnej informatyki. Już w momencie udostępnienia komputerów szerokiej grupie użytkowników stało się jasne, że mogą być one znakomitym narzędziem do gromadzenia dużej ilości danych. Szczególne znaczenie miała tu możliwość zapisu informacji w pojemnej pamięci zewnętrznej i wykorzystanie szybkości pracy maszyny do przetwarzania danych, Powstało nowe pole zastosowań komputerów. W latach 1962 1963 sformułowano po raz pierwszy pojecie bazy danych w sposób następujący [4]: Bazą danych nazywamy zbiór danych o określonej strukturze, zapisany na zewnętrznym nośniku maszynowym komputera, mogący zaspokoić potrzeby wielu użytkowników korzystających z niego w sposób selektywny w dogodnym dla siebie czasie. a -R -^g&zr, «b/r Bazy danych umożliwiają wielokrotne odtwarzanie i analizę informacji o pewnych faktach i zdarzeniach mających miejsce w jakimś wycinku rzeczywistości. Jak można się domyśleć, pomiędzy użytkownikiem komputera, a zbiorem danych znajdującym się w pamięci masowej musi istnieć element pośredni. Taki pomost stanowi System Zarządzania Bazą Danych (SZBD). Jest to specjalistyczne oprogramowanie, które umożliwia użytkownikowi wprowadzanie, wyszukiwanie oraz modyfikację danych. System taki realizuje podstawowe zadania związane z zapisem, odczytem i aktualizacją informacji w pamięci masowej. Przez lata w teorii baz danych następowała swoista ewolucja modelu danych w kierunku coraz bardziej naturalnego i uniwersalnego sposobu kodowania informacji. Problematyka obejmująca zapis informacji w pamięci masowej, definicje modelu danych, czy metody komunikacji z użytkownikiem jest niezwykle szeroka. Dlatego też teoria baz danych i przetwarzania informacji w ciągu ostatnich trzydziestu lat stała się jedną z podstawowych dziedzin informatyki i jest szeroko badana przez wielu naukowców na całym świecie. W procesie projektowania można wyróżnić trzy etapy [9]: , , 1. 2. 3.

Specyfikacja wymagań użytkownika; Zapisanie danych w formie akceptowanej przez komputer; Wprowadzanie danych.

. •'

•

•

•

-

"

- -

Pierwszy etap nazywa się konceptualizacją świata rzeczywistego. Etap drugi polega na utworzeniu schematu danych, to znaczy zapisaniu ich w odpowiednim języku. Schemat danych odpowiada określonemu modelowi danych. Etap trzeci oznacza założenie bazy danych. Właściwy kontakt z użytkownikami jest bardzo ważną umiejętnością informatyka. Budowanie systemu zaraz po wysłuchaniu zamówienia klienta wiąże się z ryzykiem. Konieczne jest ustalenie szczegółów. Rozmowy z użytkownikami mogą być trudne, zwłaszcza gdy nie mają oni orientacji w dziedzinie informatyki oraz gdy nie umieją określić precyzyjnie własnych potrzeb. Zaimplementowany system może nie spełniać oczekiwań. Wykonanie projektu daje możliwość pokonania luki w komunikacji z użytkownikiem. Proces projektowania, choć czasochłonny, zapewnia znaczne korzyści. Projektant może przedstawić użytkownikowi swoje zrozumienie tematu i swoje wizje dotyczące przyszłego systemu. Modyfikowanie projektu systemu, a także opracowanie jego kolejnej wersji, celem spełnienia wymagań użytkownika, jest dużo tańsze i mniej kłopotliwe niż poprawianie gotowych i wdrożonych już aplikacji. Czas, który projektant zainwestował w stworzenie właściwej struktury systemu nie jest stracony. Przeciwnie, osiągnięcie celów wyznaczonych przez poprawne metodologie projektowania oznacza oszczędność czasu, ponieważ nie występuje stała potrzeba poprawy źle zaprojektowanej struktury. Praca przy komputerze powinna być dobrze przygotowana. Powinna być finałem wcześniejszych wysiłków i wynikać z dokładnej analizy postawionego zadania i dobrze opracowanego projektu. Szczególne umiejętności są potrzebne, gdy przyszły użytkownik obawia się nowej technologii i jest przeciwny jej wprowadzeniu. Bardzo ważny jest zatem aspekt psychologiczny. Niewłaściwe podejście może całkowicie przekreślić możliwość wdrożenia systemu informatycznego. Potrzebna jest zatem delikatna sztuka dyplomacji oraz prowadzenia negocjacji. Jasna komunikacja z użytkownikami oraz wyjaśnienie ich oczekiwań prowadzi do sukcesu systemu, sprzyja wzrostowi jego wydajności dzięki eliminacji falstartów i nieporozumień. O sukcesie decydują cechy osobowościowe informatyka, a właściwie wszystko to, co rozumie się pod pojęciem kreatywności lub „otwartego umysłu". Właśnie takich ludzi oczekują od szkół wyższych pracodawcy. Znajomość poszczególnych narzędzi informatycznych jest dla nich mniej istotna. Opanowanie nowego narzędzia jest znacznie mniej czasochłonne niż ukształtowanie w sobie cech osobowościowych, które decydują o przydatności dla przedsiębiorstwa. Jest to szczególnie ważne w przypadku informatyków, którzy oprócz znajomości technologii informatycznej muszą dysponować wiedzą z innych dziedzin lub być w stanie i chcieć ją opanować. „Informatyk powinien mieć racjonalny, logiczny umysł, potrafić spojrzeć na system z różnych stron, umieć podzielić go na poziomy podsystemów oraz być w stanie myśleć o systemie zarówno w terminach abstrakcyjnych, jak i fizycznych" [17]. Niniejsze opracowanie dotyczy zagadnień związanych z procesem projektowania baz danych. Nie jest natomiast omawiana fizyczna organizacja baz danych, jak również operacje współbieżne. Rozdział pierwszy zawiera podstawową

terminologię używaną w systemach zarządzania bazą danych. Rozdział drugi opisuje klasyczne modele danych: hierarchiczny, sieciowy oraz relacyjny. Dwa pierwsze są rzadko stosowane. Stanowiły jednak podstawę pierwszych komercyjnie dostępnych systemów. Mają dzisiaj znaczenie historyczne [15]. Omawiany w rozdziale trzecim model związków encjijesi często używany w procesie projektowania. Może stanowić wygodne narzędzie komunikacji między projektantem i użytkownikiem. Daje możliwość abstrakcyjnego, wysokopoziomowego spojrzenia na dane i na problemy, które napotyka informatyk podczas projektowania. Szczegóły transformacji modelu związków encji na model relacyjny zostały przedstawione w rozdziale czwartym. Poza tym rozdział czwarty zawiera omówienie podstawowej terminologii relacyjnego modelu danych, operacji algebry relacji oraz języka SQL (ang. Structured Query Language), który stał się powszechnie przyjętym interfejsem użytkownika. Ze względu na swoją prostotę i przejrzysty sposób reprezentowania informacji model relacyjny zyskał szeroką aprobatę. Relacyjne bazy danych stały się standardem w systemach komercyjnych w latach osiemdziesiątych, wypierając całkowicie systemy sieciowe i hierarchiczne. Był to pierwszy model danych zdefiniowany za pomocą pojęć matematycznych. Skonstruowanie prawidłowej logicznej struktury danych wymaga uwzględnienia zależności między danymi. Teoria projektowania baz danych, zwana również normalizacją, została omówiona w rozdziale piątym. Wreszcie ostatni rozdział opisuje przykład zastosowania do modelowania baz danych podejścia obiektowego.

1. System zarządzania bazą danych

System zarządzania bazą danych (SZBD, ang. database management system - DBMS) składa się ze zbioru powiązanych ze sobą danych oraz zbioru programów zapewniających do nich dostęp. Zbiór tych danych jest zwykle nazywany bazą danych. Głównym celem systemu zarządzania bazą danych jest zapewnienie wygodnego i wydajnego środowiska przy otrzymywaniu informacji z bazy danych oraz przy ich magazynowaniu. Systemy baz danych są budowane celem zarządzania wielkimi zbiorami informacji. Zarządzanie danymi obejmuje zarówno definicję struktur pamiętanych informacji, jak i mechanizmy manipulowania danymi. Ponadto system zarządzania bazą danych musi zapewnić bezpieczeństwo danych przy awariach lub próbach niedozwolonego dostępu. Jeżeli dane mają być używane jednocześnie przez wielu użytkowników (współdzielenie danych), system musi uwzględniać niebezpieczeństwo pojawienia się różnorodnych anomalii. Ze względu na znaczenie informacji dla przedsiębiorstw bazy danych należą do bardzo cennych zasobów. Wynika stąd rozwój dużej ilości koncepcji oraz technik wydajnego zarządzania danymi. W tym rozdziale podany zostanie krótki opis zasad działania systemów baz danych. », - ••**'< -

1.1. Założenia systemów baz danych Rozważmy informacje przechowywane przez bank o swoich klientach i ich oszczędnościach. Rekordy kont oszczędnościowych oraz klientów są zawarte w odpowiednich plikach. Poza tymi plikami system posiada programy umożliwiające manipulację danymi, na przykład zmianę wartości konta, wprowadzanie nowego konta, generowanie miesięcznych raportów. Wymagania stawiane systemowi stale się zmieniają. W miarę upływu czasu, wraz z pojawianiem się nowych potrzeb do systemu będą wprowadzane nowe programy i nowe pliki. Zmiany te zachodzą w długim okresie czasu i są z reguły dokonywane przez różnych programistów. Pliki mogą mieć różne formaty, a programy mogą być napisane w różnych językach. Opisane środowisko jest typowym systemem przetwarzania plików posiadającym następujące wady: Redundancja danych i brak spójności. Przykładowo adres klienta może wystąpić zarówno w pliku zawierającym rekordy kont oszczędnościowych, jak i w pliku zawierającym rekordy kont kredytowych. Mówimy wtedy o redundancji (ang. redundancy) lub nadmiarowości. Redundancja zwiększa koszty przechowywania oraz dostępu. Może także powodować niespójność danych, to znaczy występowanie sprzecznych informacji. Brak zgodności danych powoduje utratę zaufania do systemu. Jeżeli adres klienta się zmieni, to zmiana ta powinna zostać uwzględniona w obu plikach. Koszty redundancji zwiększają się wraz ze wzrostem liczby operacji aktualizujących. Redundancja może być wprowadzona celowo dla zmniejszenia czasu dostępu, umożliwienia zastosowania prostszych metod adresowania lub odtworzenia w przypadku awarii. Wymagany jest zatem kompromis. Często używany jest termin redundancja kontrolowana lub minimalna. Przyjmuje się, że w dobrze zaprojektowanej bazie danych wyeliminowano redundancję szkodliwą. Trudności w dostępie do danych. Przypuśćmy, że urzędnik banku chce znaleźć wszystkich klientów mieszkających w rejonie miasta o kodzie pocztowym 91-123. Telefonuje do działu informatyki i prosi o sporządzenie odpowiedniej listy. Żądanie jest dość niezwykłe. Nie zostało przewidziane wcześniej i nie istnieje odpowiedni program. Jest jednak program generujący listę wszystkich klientów. Urzędnik ma dwie możliwości. Może poprosić swoją sekretarkę, by na podstawie otrzymanej listy podała potrzebne nazwiska. Może także poprosić informatyków o napisanie odpowiedniej aplikacji. Nie są to satysfakcjonujące rozwiązania. Przypuśćmy bowiem, że odpowiedni program został napisany i że kilka dni później ten sam urzędnik potrzebuje, by w tej samej liście wyróżnić klientów, których stan konta przekracza 10 000 PLN. Urzędnik znowu ma dwie możliwości, z których żadna nie jest satysfakcjonująca. System nie pozwala bowiem na wyszukiwanie potrzebnych danych w wygodny i wydajny sposób. Nie nadąża za zmianami zachodzącymi w jego otoczeniu, co jest jego istotną wadą. Dostęp współbieżny. Wzrost wydajności systemu wymaga umożliwienia jednoczesnej pracy wielu użytkownikom. Jeżeli dwóch użytkowników usiłuje w tym samym czasie uzyskać dostęp do tych samych danych, powstaje niebezpieczeństwo niezgodności danych. Przypuśćmy, że dwóch użytkowników usiłuje w tym samym czasie zmniejszyć stan konta o odpowiednio 100 i 200 PLN. Załóżmy, że stan początkowy konta wynosi 1000 PLN. W zależności od momentu uzyskania dostępu przez obu użytkowników stan końcowy konta może wynosić 700, 800 lub 900 PLN. Tylko pierwsza z tych wartości jest prawidłowa. Opisaną sytuację nazywamy konfliktową. System powinien posiadać mechanizmy umożliwiające wykrywanie sytuacji konfliktowych i odpowiednio na nie reagować, by nie dopuścić do niezgodności danych. Porządek wykonania opisanych operacji powinien być równoważny porządkowi sekwencyjnemu. Stan końcowy konta wyniesie wtedy 700 PLN.

Separacja danych. Ze względu na rozproszenie danych w różnych plikach, które mogą występować w różnych formatach, tworzenie nowych aplikacji wyszukujących odpowiednie dane jest pracochłonne. Problemy bezpieczeństwa. Nie każdy użytkownik powinien mieć dostęp do systemu. Na przykład osoba przygotowująca listę płac w banku może tylko widzieć tę część bazy danych, która dotyczy pracowników. Nie może natomiast mieć dostępu do kont klientów. W omawianym systemie nowe aplikacje dodawane są ad hoc i wymuszenie odpowiednich więzów bezpieczeństwa jest trudne. Problemy integralności Dane przechowywane w systemie muszą spełniać określone warunki zwane warunkami integralności (ang. integrity constraints). Na przykład stan określonego typu konta może wynosić poniżej 100 PLN co najwyżej przez okres jednego miesiąca. Taki warunek musi być wbudowany do systemu. Wprowadzanie nowych warunków wiąże się z koniecznością kosztownych zmian odpowiednich programów. Trudności te stały się przyczyną powstania systemów zarządzania bazą danych. Elementami, które umożliwiają realizację stawianych im zadań są [9]: Trwałość danych (ang. data persistency). Oznacza to, że dane są stale dostępne (nie znikają po zakończeniu pracy z komputerem); 2. Efektywny dostęp do dużej liczby danych; 3. Możliwość opisu wycinka rzeczywistości w postaci schematu danych; 4. Języki wyższego rzędu umożliwiające opis schematu danych oraz manipulację danymi (wyszukiwanie, aktualizacja, wprowadzanie, usuwanie); 5. Zarządzanie transakcjami (ang. transaction management). Oznacza to zapewnienie dostępu do danych wielu użytkownikom pracującym w tym samym czasie; . , 6. Syntaktyczna kontrola danych; -*.„.,«», ^-«r.» ^ 7. Semantyczna kontrola danych; 8. Niezależność danych (ang. data independence). Oznacza to, że zmiany definicji danych nie powinny prowadzić do zmian w eksploatacji bazy danych; 9. Ochrona danych; 10. Skuteczne odtwarzanie danych po awariach; 1 1 . Obserwacja, monitorowanie i ocena procesów zachodzących w bazie. • *" • - " ' **>., l.

1.2. Abstrakcja danych Osiągnięcie wysokiej wydajności prowadzi do projektowania złożonych struktur modelujących dane w bazie. Złożoność ta powinna być ukryta przed użytkownikami. System zarządzania bazą danych dostarcza użytkownikom abstrakcyjny obraz danych, ukrywając szczegóły ich przechowywania. Zostało to osiągnięte poprzez zdefiniowanie trzech poziomów abstrakcji: Poziom wewnętrzny. Jest to najniższy poziom abstrakcji określający sposób pamiętania danych. Na poziomie tym opisuje się model wewnętrzny bazy danych, który składa się z wielu wystąpień różnych typów rekordu wewnętrznego. Model wewnętrzny jest zdefiniowany za pomocą schematu wewnętrznego. Poziom ten jest także w literaturze nazywany/eyczwy/H. „,;, ,, ______ Poziom pojęciowy. Jest to wyższy poziom abstrakcji definiujący dane oraz związki między nimi. Opisany na tym poziomie model pojęciowy (zwany również modelem konceptualnym) przedstawia logiczną strukturę bazy danych. Model pojęciowy jest zdefiniowany za pomocą schematu pojęciowego (konceptualnego), który zawiera definicje różnych typów rekordu pojęciowego. Poziom ten opisuje całą bazę danych za pomocą niewielkiej ilości stosunkowo prostych struktur. Implementacja tych struktur może być związana ze złożonymi strukturami poziomu wewnętrznego. Użytkownik poziomu pojęciowego nie potrzebuje ich znać. Model pojęciowy jest używany przez administratora bazy danych, który decyduje o jej zawartości informacyjnej. >? ; J o_» , ; Poziom zewnętrzny. Jest to najwyższy poziom abstrakcji danych. Jest to poziom najbliższy użytkownikowi. Opisuje model zewnętrzny, to znaczy sposób w jaki dane są widziane przez użytkownika. Pomimo użycia prostszych struktur, na poziomie pojęciowym istnieje dość znaczny stopień złożoności wynikający z dużych rozmiarów bazy danych. Wielu użytkowników nie potrzebuje wszystkich zgromadzonych informacji. Odpowiadający potrzebom danego użytkownika obraz danych definiuje się za pomocą schematu zewnętrznego zwanego również podschematem [8]. Dla tej samej bazy danych istnieje jeden model pojęciowy oraz wiele podschematów. Dla zilustrowania różnicy między poziomami abstrakcji danych zastosujemy analogię do koncepcji typów danych w językach programowania. W Pascalu można zadeklarować następujący rekord:

typ klient = record nazwisko: string; ulica: string; miasto: string; end;

**>;r.^s

£

W przypadku banku można zdefiniować kilka typów rekordów opisujących miedzy innymi konta (z polami numer i saldo) oraz pracowników (z polami nazwisko i zarobki). Rekordy na poszczególnych poziomach nie muszą być identyczne. Na poziomie fizycznym rekordy mogą być opisane jako bloki kolejnych komórek pamięci (bajtów). Na poziomie pojęciowym każdy rekord jest opisany przez swoją definicję w postaci podanej wyżej i jednocześnie zdefiniowane są związki między typami rekordów. W końcu, na poziomie zewnętrznym opisane są obrazy danych. Przykładowo osoby przygotowujące listę płac mogą widzieć jedynie tę część bazy danych, która opisuje pracowników banku. Nie mogą oni mieć dostępu do kont klientów. Zupełnie innych danych potrzebują kasjerzy. Mają oni dostęp do kont klientów. Nie mogą mieć natomiast dostępu do informacji dotyczącej zarobków innych pracowników. Między poszczególnymi poziomami muszą istnieć odwzorowania. Odwzorowanie między poziomem pojęciowym i wewnętrznym opisuje sposób w jaki rekordy pojęciowe są odwzorowywane na rekordy fizyczne. Odpowiedniość między modelem zewnętrznym i pojęciowym jest również zdefiniowana za pomocą odpowiedniego odwzorowania. Rysunek l. l przedstawia trzy poziomy abstrakcji danych.

Dostęp do danych zapewnia użytkownikowi język programowania, w którym jest zawarty subjęzyk danych służący do wyszukiwania i pamiętania informacji w bazie danych. Podczas wyszukiwania danych wykonywane są następujące czynności [3]: 1.

Użytkownik zgłasza żądanie dostępu do rekordu zewnętrznego.

2.

System zarządzania bazą danych określa na podstawie schematu zewnętrznego, odwzorowania zewnętrzny/pojęciowy oraz schematu konceptualnego, które rekordy pojęciowe zawierają poła żądanego rekordu zewnętrznego.

3.

System zarządzania bazą danych określa na podstawie schematu konceptualnego, odwzorowania pojęciowy/wewnętrzny oraz schematu wewnętrznego, które rekordy wewnętrzne zawierają pola potrzebnych rekordów pojęciowych.

4.

Po przeczytaniu rekordów wewnętrznych system zarządzania bazą danych buduje wystąpienia rekordów pojęciowych.

5.

Na podstawie rekordów pojęciowych system zarządzania bazą danych buduje wystąpienie rekordu zewnętrznego żądanego przez użytkownika.

6.

System zarządzania bazą danych przesyła odpowiedź do obszaru roboczego użytkownika.

1.3. Niezależność danych

c^ o «

'~

Możliwość modyfikacji definicji schematu na danym poziomie abstrakcji bez konieczności zmian definicji schematu na poziomie wyższym nazywamy niezależnością danych. Wyróżniamy dwa poziomy niezależności danych [8]: Fizyczna niezależność danych. Oznacza możliwość modyfikacji schematu fizycznego bez naruszania schematu pojęciowego i bez konieczności dokonywania zmian w programach użytkowych. Modyfikacje na poziomie fizycznym są przeprowadzane celem zwiększenia wydajności systemu. Logiczna niezależność danych. Oznacza możliwość modyfikacji schematu konceptualnego bez konieczności dokonywania zmian w programach użytkowych. Modyfikacje na poziomie konceptualnym są spowodowane koniecznością zmiany logicznej struktury danych. Logiczna niezależność danych jest trudniejsza do osiągnięcia, ponieważ programy użytkowe silnie zależą od logicznej struktury danych, na której operują. Pojęcie niezależności danych jest podobne do pojęcia abstrakcyjnych typów danych w nowoczesnych językach programowania. W obu przypadkach szczegóły implementacyjne nie są widziane przez użytkowników. Pozwala to koncentrować wysiłek na ogólnej strukturze danych, a nie na szczegółach implementacyjnych.

1.4. Jeżyk definiowania danych

» * , . „ - ,

Schemat bazy danych jest określony za pomocą zbioru definicji wyrażonych w specjalnym języku zwanym językiem definiowania danych (ang. DDL — Data Definition Language). Nie ma on charakteru proceduralnego. Wynikiem kompilacji zdań tego języka jest zestaw tabel przechowywanych w specjalnym pliku zwanym słownikiem danych, który zawiera metadane, czyli dane o danych. Plik ten jest sprawdzany przed odczytem lub modyfikacją danych. Struktura pamięci oraz metody dostępu używane w systemie zarządzania bazą danych są zdefiniowane w specjalnym typie języka definicji danych (ang. data storage and de/lnition language). Wynikiem kompilacji jest zbiór instrukcji określających szczegóły implementacji schematów baz danych, które zwykle są ukryte przed użytkownikiem.

1.5. Jeżyk manipulowania danymi Omówione w punkcie l .2 poziomy abstrakcji odnoszą się nie tylko do definicji danych, ale także do manipulowania nimi, które obejmuje następujące operacje: • • • •

Wyszukiwanie informacji; Wprowadzanie nowych informacji; Modyfikacja istniejących informacji; Usuwanie istniejących informacji.

»

; :

•

Na poziomie fizycznym trzeba zdefiniować algorytmy, które umożliwiają wydajny dostęp do danych. Na wyższych poziomach abstrakcji ważniejsza jest wygoda w użyciu. Język manipulowania danymi (ang. DMŁ — Data Manipulation Language) umożliwia użytkownikom dostęp i manipulowanie danymi zorganizowanymi w odpowiednim modelu. Poza wymienionymi operacjami język manipulowania danymi umożliwia przetwarzanie danych (wykonywanie na nich operacji arytmetycznych i logicznych) oraz tworzenie nowych komponentów bazy danych na podstawie znalezionych informacji. Pytanie o dane jest także nazywane kwerendą (ang. ąuery). Ta część DML, która dotyczy wyszukiwania informacji, nazywa się językiem kwerend (ang. ąuery language). Chociaż technicznie nie jest to poprawne, w praktyce przyjęto te dwa terminy jako synonimy. Do najważniejszych cech języka zapytań należą: • • •

Siła ekspresji. Określa zakres tego, co można w nim wyrazić. Znacznym zwiększeniem siły ekspresji języka jest „osadzenie" go w jakimś języku programowania (np. C, Pascal). Pełność. Oznacza, że można zawsze zapisać kwerendę, która pozwoli odszukać dowolną informację. Łatwość rozszerzeń: (1) Możliwość wykonywania działań arytmetycznych; (2) Możliwość wykonywania operacji agregujących, np. obliczanie średniej arytmetycznej. Osiąga się to przez dołączenie odpowiednich funkcji bibliotecznych.

10

• •

Prostota

• • - * . « . > -4.

Efektywność. (Krótki czas oczekiwania na odpowiedź i minimalny obszar pamięci roboczej). Można wyróżnić dwa główne typy języków manipulowania danymi:

•

Proceduralne (ang. procedural languages), które wymagają od użytkownika określenia jakie dane są potrzebne i jak je znaleźć. Użytkownik musi zbudować kwerendę w postaci procedury będącej opisem przedmiotu pytania oraz metody prowadzącej do uzyskania odpowiedzi. Takie proceduralne kwerendy przypominają programy komputerowe.

•

Nieproceduralne, które wymagają od użytkownika określenia jakie dane są potrzebne bez konieczności określania sposobu ich znalezienia. W językach tych, zwanych także deklaratywnymi (ang. declarative languageś), kwerenda składa się z dwóch części, z których pierwsza opisuje żądany schemat postaci wynikowej, a druga specyfikuje warunki jakie muszą spełniać dane stanowiące odpowiedź na zapytanie. Za wykonanie kwerendy odpowiedzialny jest system zarządzania bazą danych.

Większość komercyjnych systemów baz danych proponuje języki zawierające zarówno elementy proceduralne, jak i nieproceduralne. Nieproceduralne języki manipulowania danymi są zwykle łatwiejsze w użyciu. Mogą jednak generować kod mniej wydajny niż języki proceduralne. Efektywność kodu można zwiększyć poprzez zastosowanie technik optymalizacyjnych.

1.6. Administrator bazy danych Jednym z głównych zadań systemu zarządzania bazą danych jest możliwość kontroli zarówno danych, jak i programów mających do nich dostęp. Osoba (lub grupa osób) sprawująca taką kontrolę jest nazywana administratorem bazy danych. Administrator jest odpowiedzialny za szeroko rozumiany stan bazy danych i reprezentuje interesy właściciela systemu zarządzania bazą danych. Zadania administratora obejmują [3]: „,„„^ Definiowanie schematów; • Ł;, Definiowanie struktury pamięci i metod dostępu; •-•' Modyfikowanie schematów i fizycznej organizacji danych; Specyfikację warunków integralności; , " "" ' (Utrzymywanie kontaktu z użytkownikami; Badanie wydajności i reagowanie na zmiany wymagań; ~St Udzielanie zezwoleń na dostęp do danych; . , . : Bezpieczeństwo bazy danych; j l Kontrolę współbieżności; t Wykonywanie archiwalnych kopii bazy danych; •>•Odtwarzanie poprawnego stanu po awarii; Nadzorowanie pracy programistów systemowych i aplikacyjnych.

~—~„.—„...4 t„,JL".', ~

\ j ----•--"—---——>_*,„-,,*,.„„, j j

JL 1.7. Użytkownicy baz danych Ze względu na sposób współdziałania z systemem wyróżniamy trzy rodzaje użytkowników: •

Programiści zastosowań (ang. application programmers). Są to profesjonaliści, którzy współdziałają z systemem za pomocą komend języka manipulowania danymi, osadzonych w programie napisanym w języku macierzystym (Cobol, PL/1, C). Ze względu na różnice gramatyki DML i języka macierzystego, komendy DML są przetwarzane przez specjalny preprocesor zwany prekompilatorem DML, który je konwertuje na wywołania zwykłych procedur w języku macierzystym. Otrzymany program jest następnie przetwarzany przez kompilator języka macierzystego.

•

Użytkownicy doraźni (ang. casual users). Współpracują oni z systemem tylko za pomocą języka kwerend. Sformułowana przez nich kwerenda jest przetwarzana przez procesor kwerend do postaci zrozumiałej dla systemu zarządzania bazą danych.

•

Użytkownicy parametryczni (ang. parametric users). Nie dysponują oni żadnym językiem. Ich współpraca z systemem polega na wykorzystywaniu napisanych wcześniej aplikacji.

n

1.8. Architektura systemu zarządzania bazą danych

\,;

System zarządzania bazą danych (rys. 1.2) składa się z modułów realizujących poszczególne funkcje. Niektóre z tych fiłnkcji mogą być realizowane przez system operacyjny. W większości przypadków system operacyjny świadczy jedynie najbardziej podstawowe usługi i dlatego projekt musi zawierać interfejs między systemem zarządzania bazą danych i systemem operacyjnym. Do funkcjonalnych elementów systemu zarządzania bazą danych należą:

12

•

Program obsługi plików (ang. flle manager). Jest to program zarządzający alokacją przestrzeni dyskowej i strukturami danych używanych do reprezentowania informacji magazynowanej na dysku. Program zarządzający (ang. database manager). Jest to moduł stanowiący interfejs między przechowywanymi w bazie danymi niskiego poziomu i programami aplikacyjnymi oraz kwerendami zgłaszanymi do systemu. Do zadań tego modułu należą: interakcja z programem obsługi plików, sprawdzanie warunków integralności, zapewnienie ochrony przed niedozwolonym dostępem, odtwarzanie danych po awariach oraz kontrola współbieżnych operacji dokonywanych na bazie danych.

•

Procesor kwerend (ang. ąuery processor). Procesor ten tłumaczy zlecenia wyrażone w języku kwerend na instrukcje niskiego poziomu zrozumiałe dla programu zarządzającego. Ponadto procesor kwerend usiłuje dokonać przekształcenia zapytania użytkownika na równoważną, ale bardziej wydajną postać. Ma to na celu znalezienie lepszej strategii prowadzącej do uzyskania odpowiedzi. Proces ten nazywamy optymalizacją zapytania.

•

Prekompilator DML. Dokonuje on konwersji zleceń języka manipulowania danymi występujących w programach aplikacyjnych do zwykłych wywołań procedur w języku macierzystym. Prekompilator musi współdziałać z procesorem kwerend celem wygenerowania właściwego kodu.

•

Kompilator DDL. Przetwarza zdania wyrażone w języku definiowania danych na postać pozwalającą zorganizować fizyczne struktury bazy danych. Ponadto implementacja systemu musi zawierać następujące elementy:

• • •

Pliki danych; Słownik danych, który zawiera informacje o strukturze bazy danych; Indeksy, które zapewniają szybkie wyszukiwanie danych.

•

,

<,

2. Modele danych

Dane opisujące obiekty rzeczywiste i związki pomiędzy nimi muszą zostać w precyzyjnie określony sposób zapisane w pamięci masowej. W przypadku maszyn cyfrowych oznacza to konieczność przetworzenia nieformalnego opisu do postaci cyfrowej, przy użyciu podstawowych typów danych. W pierwszym okresie rozwoju technologii baz danych przechowywano dane na taśmach magnetycznych w postaci rekordów o stałej strukturze. Każdy rekord zawierał cyfrową reprezentację informacji o obiekcie określonego typu. Rekordy tego samego typu grupowano tworząc pliki. Historycznie stanowią one pierwszą metodę zapisu informacji w pamięci masowej. Ze względu na swoje wady system plików stał się narzędziem niewystarczającym dla zaspokojenia rosnących wymagań przedsiębiorstw i różnego rodzaju instytucji w zakresie przechowywania danych. Zapotrzebowanie na nową technologię stało się motorem rozwoju tej dziedziny informatyki. Efektywne przetwarzanie informacji wymaga właściwej organizacji danych. Powinny one wiernie opisywać rzeczywistość oraz powinna istnieć możliwość zapisania ich w komputerze. Powstaje potrzeba zbudowania modelu danych [7]. Model należy do najczęściej używanych terminów w różnych dziedzinach nauki i techniki. Istnieją modele dotyczące różnorodnych aspektów naszej rzeczywistości. Umożliwiają one przedstawienie obiektu, pojęcia lub zjawiska w postaci abstrakcyjnej. Uzyskuje się przez to większą zrozumiałość i odejście od szczegółów. Tradycyjnie wyróżnia się modele matematyczne oraz fizyczne. W modelach matematycznych do abstrakcyjnego opisu rzeczywistości stosuje się odpowiednią notację i logikę. Modele fizyczne pomagają zrozumieć fizyczne własności rzeczywistego świata za pomocą urządzenia o odpowiednich właściwościach. Modele ekonomiczne natomiast pozwalają badać trendy ekonomiczne i przewidywać rozwój gospodarczy. Określenie struktury bazy danych wymaga zdefiniowania pojęcia modelu danych. Jest to model zapewniający logiczną interpretację danych. Model danych jest zbiorem konceptualnych narzędzi opisujących dane, związki miedzy nimi, semantykę danych oraz warunki integralności. Jego głównymi elementami są [14]: • •

Matematyczny zapis dla wyrażania danych oraz związków między nimi; Operacje na danych służące do wyrażania zapytań oraz innych manipulacji danymi. Można wyróżnić dwie główne grupy modeli danych:

• •

Modele oparte na obiektach; Modele oparte na rekordach.

Do pierwszej grupy należą między innymi modele zorientowane obiektowo. Obiekt zawiera dane oraz procedury, które na nich działają. Procedury te nazywamy metodami. Obiekty zawierające takie same typy danych oraz te same metody są grupowane w klasy. Każdy obiekt posiada swój jednoznaczny identyfikator, niezależny od innych wartości. Obiekty współdziałają ze sobą za pomocą metod. Odpowiednia akcja polega na przesyłaniu komunikatów. Tytułem przykładu rozpatrzmy obiekt reprezentujący konto w banku. Zawiera on zmienne: numeri_konta i saldo oraz metodę ptać_odsetki, która dodaje odsetki do salda. Załóżmy, że dotychczas oprocentowanie kont w banku wynosiło 15% dla wszystkich wkładów. Zarząd wprowadził zróżnicowanie oprocentowania w zależności od wysokości wkładów według następującej zasady: jeśli stan konta przekracza 10 000 PLN, to oprocentowanie wynosi 17%, a dla pozostałych kont 14%. W większości modeli wprowadzenie takiej reguły spowodowałoby konieczność dokonania zmian w programach użytkowych. W modelu zorientowanym obiektowo zmiany należy przeprowadzić tylko wewnątrz metody płać_pdsetki. W modelach drugiej grupy baza danych ma strukturę rekordów o ustalonym formacie. Każdy rekord definiuje ustaloną liczbę atrybutów. W grupie tej można wyróżnić trzy główne podejścia do projektowania baz danych i związane z nimi modele danych. Nazywane są one klasycznymi. Są to modele: hierarchiczne, sieciowe i relacyjne [8].

Rys. 2.1. Struktura hierarchiczna 14

r

2.1. Model hierarchiczny

Kolejnym krokiem w rozwoju baz danych był model hierarchiczny. W modelu tym schemat bazy danych ma postać wielopoziomowego drzewa (rys. 2.1). Dane zapisywane są tu w rekordach różnych typów. Typ rekordu na najwyższym poziomie jest nazywany rekordem głównym. Każdy rekord nadrzędny („rodzic") może mieć wiele rekordów podrzędnych, ale każdy rekord podrzędny może mieć tylko jeden rekord nadrzędny. Oznacza to, że żaden rekord w bazie danych - poza głównym - nie może istnieć bez nadrzędnego. Skasowanie rekordu wiąże się ze skasowaniem wszystkich jego rekordów podrzędnych.

PROJEKTY

p# Pl P2

P3 P4 P5 P6 P7

PRIORYTET

NAZWA

BUDŻET

Kredyt Firm

110000 50000

Bankowość Rachunkowość

Polisa

40000

Ubezpieczenia

Makler

30000

Rynek kapitałowy

Visa

200000

Bankowość

Agent

20000

Ubezpieczenia

1 3 4 2 1 4

Kasa

35000

Rachunkowość

3

RODZAJ

MIASTO Warszawa Łódź Łódź Poznań Kraków Piotrków Trybunalski Łódź

PRACOWNICY

E#

NAZWISKO

El E2

WYKSZTAŁCENIE

WIEK

Kowalski Abowski

Ekonomista Prawnik

E3

Azowski

Matematyk

E4 E5 E6 E7 E8 E9

Dakowski

Informatyk

Dymowski

Fizyk

Nowak

Elektronik

Majewski

Ekonomista

Abacki

Matematyk

Olczak

Informatyk

E 10

Pawlak

Eli E12 E13 E14 E15 E16 E17 E18 E19 E20

Majkowski

Ekonomista Elektronik

Gawroński

Matematyk

Makowski

Informatyk

Nowakowski

Ekonomista

Tomaszewski

Elektronik

Gumowski

Chemik

Kowalski

Architekt

Grabowski

Informatyk

Jodłowski

Informatyk

Markiewicz

Elektronik

43 53 34 41 52 23 38 35 27 58 34 39 52 30 32 44 33 36 28 25

Rys. 2.2. Tabele PROJEKTY i PRACOWNICY dla bazy danych biura projektów

15

KONTRAKTY

p#

E#

WYNAGRODZENIE

Pl Pl Pl Pl Pl Pl

El E2 E6 E7 E10 E18 E20 E4 E9 E10 E14

1000 1000

Pl

P2 P2 P2 P2 P3 P3 P3 P3 P4 P4 P4 P4 P4 P5 P5 P5

2000

1000 4000 2000 6000 5000 8000 3000 4000

E2 E3 E6 E8 El E4 E6 E18 E19

7000 5000 3000

1 000 2000 4000

f ZM

2.

n re

1000 4000 2000

El E2 E19

2000

1000 8000

fc

Rys. 2.3. Tabela KONTRAKTY dla bazy danych biura projektów Przykład 2.1. Tytułem przykładu rozpatrzmy bazę danych dla biura projektów zawierającą informacje o realizowanych projektach oraz o pracownikach biorących w nich udział. Przykładowe dane przedstawiono w tabelach na rysunkach 2.2 i 2.3. Większość przykładów w tym i następnych rozdziałach dotyczy tych danych. Tabela PROJEKTY zawiera kolumny: P#, NAZWA, BUDŻET, RODZAJ, PRIORYTET i MIASTO realizacji projektu. Wartości w kolumnie PRIORYTET są związane z wartościami w kolumnie RODZAJ, które określają dziedzinę projektu. Innymi słowy, znaczenie projektu zależy od jego rodzaju. Tabela PRACOWNICY z kolumnami: E#, NAZWISKO, WYKSZTAŁCENIE i WIEK, opisuje ludzi zatrudnionych w przedsiębiorstwie. Atrybuty P# oraz E# oznaczają odpowiednio numer projektu i numer pracownika. Ostatnia tabela KONTRAKTY dotyczy związku między projektami i pracownikami. Jej atrybutami są: P#, E# oraz WYNAGRODZENIE otrzymywane przez pracownika za udział w realizacji określonego projektu. Należy zauważyć, że nie każdy pracownik uczestniczy w pracy nad jakimkolwiek projektem. Z drugiej strony istnieją projekty, do których nie są przydzieleni pracownicy (mogą być one w fazie wstępnej analizy). » -.''...J PROJEKTY

J

V"

PRACOWNICY Rys. 2.4. Dwupoziomowa hierarchia

Ifr

od

rd A

5*

rc pc kc pc ŁS

bs

Zastosowanie podejścia hierarchicznego wymaga określenia typu rekordu głównego. W postaci hierarchicznej przedstawionej na rysunku 2.4 przyjęto, że jest nim rekord PROJEKTY. Model hierarchiczny omawianego przykładu zawiera siedem drzew, to znaczy tyle, ile jest opisanych projektów. Drzewo dla projektu P l przedstawiono na rysunku 2.5. Pozycja danych WYNAGRODZENIE, charakteryzująca związek między projektami i pracownikami, została umieszczona w rekordzie podrzędnym. Drzewa odpowiadające projektom nierealizowanym składają się jedynie z rekordu głównego. Nazywamy je zdegenerowanymi. Pozostałe zawierają oprócz rekordu głównego wystąpienia rekordu podrzędnego. Ogólnie może istnieć dowolna liczba typów rekordów podrzędnych i dowolna liczba poziomów podrzędności. Język manipulowania danymi musi zawierać dwie podstawowe operacje: • •

Podaj następny, taki że...; Podaj następny dla..., taki że....

Pierwsza operacja odszukuje następny rekord względem pozycji bieżącej. Najczęściej pozycją tą jest ostatnio odszukany rekord. Po frazie „taki że" precyzowany jest warunek wyboru, np. „Podaj numery projektów, których budżet przekracza 10 000". Druga operacja określa kontekst wyszukiwania. Jest nim rekord nadrzędny względem rekordu docelowego. Rozważmy następujące żądanie: „Podaj numery pracowników uczestniczących w realizacji projektu Pl". Znalezienie odpowiedzi na tak postawione pytanie wymaga wyszukania rekordu odpowiadającego projektowi P l, a następnie wszystkich jego rekordów podrzędnych. Bardziej złożony jest natomiast algorytm wyznaczania odpowiedzi na pytanie „Podaj numery projektów, w których uczestniczy pracownik El". Trzeba bowiem przeszukać wszystkie drzewa aby sprawdzić, czy wśród rekordów podrzędnych istnieje rekord odpowiadający pracownikowi El. Jeśli tak, to atrybut P# rekordu nadrzędnego należy do odpowiedzi. Widać więc, że algorytmy wyszukiwania odpowiedzi nie są analogiczne, chociaż oba pytania są względem siebie symetryczne. Zaobserwowana właściwość wynika z zastosowanego modelu, który sam jest asymetryczny. Projekty i pracownicy są w nim traktowani w różny sposób. Informacje o pracowniku są powtarzane wielokrotnie. Liczba powtórzeń jest równa liczbie projektów, nad którymi on pracuje. Powoduje to znaczną redundancję. Asymetria jest główną wadą podejścia hierarchicznego. Powiązanie jeden do wielu może przebiegać tylko w jednym kierunku. Zachodzi zatem konieczność ustalenia struktury hierarchii na samym początku, ponieważ powiązania „rodzic - dziecko" nie mogą być później modyfikowane w sposób dowolny. Hierarchia ta powinna być ściśle związana z rodzajem zadawanych pytań. Opisany przykład bazy danych dla biura projektów jest symetryczny. Zastosowanie do niego modelu asymetrycznego spowodowało powstanie niepożądanych własności. Dotyczą one operacji zmieniających zawartość bazy danych: •

Bez użycia specjalnego rekordu zawierającego „sztuczny" projekt nie można wprowadzić informacji o nowym pracowniku, dopóki nie weźmie on udziału w realizacji jakiegoś projektu.

•

Jeżeli pracownik przestaje uczestniczyć w realizacji danego projektu i jeżeli przy tym był to jedyny jego projekt, to usunięcie rekordu podrzędnego powoduje utratę informacji o tym pracowniku.

•

Każda zmiana danych pracownika wymaga przejrzenia całej bazy danych celem znalezienia wszystkich rekordów, które go opisują i dokonania odpowiednich zmian. W przeciwnym razie baza będzie zawierać sprzeczne dane.

17

2.2. Model sieciowy

,

W roku 1971 Grupa Robocza do Spraw Baz Danych (Database Task Group - DBTG) organizacji CODASYL (Conference on Data Systems Languages) opublikowała pierwsze specyfikacje systemu opartego na modelu sieciowym. Model ten jest pewnym ulepszeniem modelu hierarchicznego i pozwala na definiowanie wskaźników opisujących powiązania miedzy danymi w sposób bardziej elastyczny od statycznej struktury drzewa. W strukturze sieciowej każdy rekord może mieć więcej niż jeden rekord nadrzędny. Baza danych zawiera zbiór rekordów powiązanych ze sobą poprzez wskaźniki. Dzięki dowolności w deklarowaniu powiązań model sieciowy pozwala na łatwą reprezentację powiązań wiele-do-wielu. W ten sposób schemat bazy danych można przedstawić za pomocą zbioru rekordów wraz z siecią powiązań miedzy nimi.

Podstawowym elementem modelu jest kolekcja. Reprezentuje ona związek hierarchiczny miedzy rekordami (rysunek 2.6). Każde wystąpienie kolekcji OM zawiera dokładnie jedno wystąpienie rekordu nadrzędnego O (zwanego także właścicielem - ang. owner) oraz wiele (lub zero) wystąpień rekordu podrzędnego M (członków - ang. memberś). Wystąpienia rekordów podrzędnych tworzą łańcuch, który zaczyna się i kończy w wystąpieniu rekordu nadrzędnego. Żadne z wystąpień rekordu podrzędnego nie może należeć jednocześnie do więcej niż jednego wystąpienia tego samego typu kolekcji. Może natomiast być członkiem różnych typów kolekcji. Ten sam typ rekordu można zdefiniować jako nadrzędny w jednym typie kolekcji i podrzędny w innym. Taką sytuację zilustrowano na rysunku 2.7. Rekordy KIERUNEK l oraz KIERUNEK2 są podrzędne w kolekcji WYDZKIER, której właścicielem jest rekord WYDZIAŁ_A, oraz nadrzędne w kolekcji KIERSTUD zawierającej rekordy studentów na danym kierunku studiów. Ten sam typ rekordu może występować w roli właściciela w dwóch typach kolekcji. Na rysunku 2.8 rekord WYKŁADOWCA l jest rekordem nadrzędnym w kolekcjach WYKPRZED oraz WYKART, których rekordy podrzędne zawierają informacje o prowadzonych przez niego przedmiotach oraz o artykułach naukowych, których jest autorem.

18

Strukturę kolekcji przedstawia się graficznie za pomocą diagramu Bachmana. Rekordy są reprezentowane za pomocą prostokątów. Nazwy kolekcji są umieszczane w elementach owalnych, na drodze powiązań między rekordami nadrzędnym i podrzędnym, Powiązania są skierowane celem określenia podrzędności rekordów. Diagramy Bachmana dla omówionych przykładów przedstawiono na rysunkach 2.9 oraz 2.10.

Rysunek 2.11 przedstawia diagram Bachmana bazy danych dotyczącej biura projektów. Występują tu dwa typy kolekcji: PROJKON i PRACKON, dwa typy rekordów nadrzędnych: PROJEKTY oraz PRACOWNICY oraz jeden typ rekordu podrzędnego KONTRAKTY. Rekord KONTRAKTY jest podrzędny względem dwóch pozostałych rekordów i pełni rolę łącznika. Reprezentuje on związek między nimi oraz zawiera dane powiązań (atrybut WYNAGRODZENIE). Wystąpienia rekordu KONTRAKTY dla danego projektu oraz dla danego pracownika tworzą dwa różne łańcuchy, przy czym każde wystąpienie rekordu KONTRAKTY należy do dwóch łańcuchów, związanych z danym projektem i pracownikiem. Na przykład fakt, że pracownik El uczestniczy w realizacji projektu Pl i uzyskuje za to wynagrodzenie 1000 PLN jest reprezentowany w modelu sieciowym przez rekord KONTRAKTY należący do kolekcji PROJKON i PRACKON, których właścicielami są rekordy reprezentujące projekt Pl oraz pracownika El, i w którym jest zapisana wartość 1000. Język manipulowania danymi musi zawierać dodatkową (w porównaniu z modelem hierarchicznym) operację: „Podaj nadrzędny dla ...", wyszukującą rekord właściciela danego rekordu podrzędnego. Algorytm znajdujący odpowiedź na pytanie: „Podaj numery pracowników uczestniczących w realizacji projektu Pl" jest bardziej złożony w

19

porównaniu z procedurą stosowaną dla modelu hierarchicznego. Po znalezieniu rekordu reprezentującego projekt P l (operacja typu „Podaj następny, taki że ...") należy przeszukać całe wystąpienie kolekcji PROJKON (operacja typu „Podaj następny dla ...") oraz dla każdego rekordu podrzędnego KONTRAKTY znaleźć rekord jego właściciela (operacja „Podaj nadrzędny dla ...") w kolekcji PRACKON. Procedura realizująca żądanie „Podaj numery projektów, w których uczestniczy pracownik El" jest analogiczna. Wynika to z symetrii modelu, w którym nie wyróżniono żadnego z opisywanych obiektów.

Przy operacjach zmieniających zawartość bazy danych nie występują anomalie, takie jak w modelu hierarchicznym: •

Nowy pracownik może być wprowadzony do bazy danych bez konieczności udziału w realizacji jakiegoś projektu. Po utworzeniu odpowiedniego rekordu będzie on właścicielem kolekcji pustej.

•

Jeżeli pracownik przestaje uczestniczyć w realizacji danego projektu, to należy usunąć odpowiednie wystąpienie rekordu KONTRAKTY. Nawet jeżeli był to jedyny jego projekt, to operacja ta nie spowoduje - tak jak w modelu hierarchicznym - utraty danych tego pracownika. Są one zapisane w rekordzie PRACOWNICY. Likwidacja wystąpienia rekordu KONTRAKTY wymaga modyfikacji wskaźników celem uwzględnienia zmian w obu łańcuchach. ,

•

Ze względu na brak redundancji (dane o pracowniku są zapisane w jednym miejscu) zmiana danych pracownika nie wymaga przeglądania całej ba/y danych. Odpowiednia modyfikacja powinna być dokonana tylko w jednym rekordzie.

Model sieciowy pozwala na dosyć swobodne modelowanie obiektów rzeczywistych. Jego wadą jest natomiast znaczna złożoność. Procedury realizujące odpowiedzi na pytania o dane są bardziej skomplikowane w porównaniu z innymi modelami. Język manipulowania danymi zawiera rozbudowane konstrukcje. Złożoność samej sieci oraz języków służących do interakcji z bazą danych spowodowały, że systemy sieciowe zaczęły tracić popularność na rzecz relacyjnych baz danych. , .

: rl-r ....„,,-„,.„. ¥.,.-

3°

-

,„

...

2.3. Model relacyjny Formalne podstawy relacyjnych baz danych zostały zdefiniowane w roku 1970 przez dr Edwarda Codda w publikacji „A Relational Model of Data for Large Shared Data Banks" [2]. Zaproponowana przez niego teoria została oparta o matematyczne pojęcie relacji. W tym ujęciu relacje mają postać prostokątnych tabel, których kolumny oznaczają atrybuty, a wiersze rekordy z danymi. Jest to naturalny sposób przedstawiania danych, to znaczy przystępny, zrozumiały i łatwy do zapamiętania. Tabele na rysunkach 2.2 i 2.3 stanowią model relacyjny bazy danych dla biura projektów. Tabele PROJEKTY i PRACOWNICY opisują określone obiekty, a tabela KONTRAKTY związek między nimi. W modelu relacyjnym obiekty i związki są reprezentowane formalnie w ten sam sposób, to znaczy za pomocą tabel, czyli relacji. Jest to podstawowa własność relacyjnej struktury danych. Fakt, że pracownik El uczestniczy w realizacji projektu Pl jest reprezentowany przez odpowiedni wiersz tabeli KONTRAKTY. Podstawową operacją języka manipulowania danymi w modelu relacyjnym jest „Podaj następny, taki że...". Operacje: „Podaj następny dla... , taki że..." oraz „Podaj nadrzędny dla ..." występujące w poprzednio omówionych modelach są zbędne. Zostały bowiem zdefiniowane, by umożliwić poruszanie się po powiązaniach między danymi. Znalezienie odpowiedzi na pytanie „Podaj numery pracowników uczestniczących w realizacji projektu Pl" wymaga przeszukania tylko relacji KONTRAKTY. Należy znaleźć w niej wszystkie wiersze, w których P# = 'Pl'. Procedura realizująca żądanie „Podaj numery projektów, w których uczestniczy pracownik El" jest analogiczna. Operacje zmieniające zawartość bazy danych nie są skomplikowane. Nie powodują anomalii oraz nie wymagają dodatkowych działań: •

Wprowadzenie nowego PRACOWNICY.

pracownika jest

realizowane

•

Jeżeli pracownik przestaje uczestniczyć w realizacji danego projektu, to należy usunąć odpowiedni wiersz relacji KONTRAKTY. Nie spowoduje to utraty informacji o tym pracowniku.

•

Modyfikacja danych pracownika jest realizowana przez zmianę wartości odpowiednich atrybutów tylko jednego wiersza (brak redundancji) w relacji PRACOWNICY.

),«O'. V -. l> -i" '.

21 sssŁ,

przez

umieszczenie

nowego

wiersza

w

relacji

3. Model związków encji

Model związków encji (ang. Entity-Relationship Model) uzyskał powszechną akceptację jako model przydatny w procesie projektowania. Model ten jest oparty na percepcji świata rzeczywistego składającego się ze zbioru rzeczywistych obiektów zwanych encjami i związków między nimi. Logiczną strukturę bazy danych przedstawia się w tym modelu graficznie za pomocą diagramu związków encji (ang. Entity-Relationship Diagram).

3.1. Encje i zbiory encji Encja jest istniejącym obiektem, dającym się odróżnić od innych obiektów. Encjąjest więc pracownik Jan Kowalski z numerem identyfikacyjnym 12-3456, ponieważ jednoznacznie identyfikuje określoną osobę. Encją jest również projekt P l w biurze projektów lub konto numer 123 w banku PBG. Encją może być zarówno obiekt materialny, na przykład osoba lub książka, jak i obiekt niematerialny wyrażający pojęcia, uczucia itp. Zbiór encji zawiera encje tego samego typu. Zbiór wszystkich osób mających konto w banku można zdefiniować jako zbiór encji KLIENCI. Zbiór encji PRACOWNICY powinien zawierać wszystkich pracowników banku. Zbiory encji nie muszą być zbiorami rozłącznymi. Element zbioru encji OSOBY może należeć do zbioru PRACOWNICY, KLIENCI, do obu jednocześnie lub do żadnego z nich. Encja jest opisana za pomocą swoich atrybutów. Atrybutami encji należącej do zbioru PRACOWNICY mogą być: NUMER^IDENTYFIKACYJNY, NAZWISKO, MIASTO, ULICA, itp. Dla encji ze zbioru KONTA należałoby wybrać atrybuty NUMER i SALDO. Dla każdego atrybutu istnieje zbiór dozwolonych wartości zwanych dziedziną. Dziedziną atrybutu NAZWISKO jest łańcuch znaków, a dziedziną atrybutu NUMER zbiór liczb naturalnych. Atrybut jest funkcją, która odwzorowuje zbiór encji na swoją dziedzinę. Encje można więc opisać za pomocą zbioru par < atrybut, wartość >. Zapis { < NUMERJDENTYFIKACYJNY, 12-3456 >, < NAZWISKO, Kowalski >, < MIASTO, Łódź >, < ULICA, Narutowicza > } przedstawia pracownika o nazwisku Kowalski, numerze identyfikacyjnym 12-3456, mieszkającego w Łodzi przy ulicy Narutowicza. Zbiór encji oraz encja odpowiadają odpowiednio pojęciom typu oraz zmiennej w językach programowania. Baza danych składa się zatem z powiązanych ze sobą zbiorów, z których każdy zawiera dowolną liczbę encji tego samego typu.

3.2. Związki między encjami Między encjami mogą istnieć powiązania. Tworzą one zbiory związków encji. Formalnie związek taki jest matematyczną relacją określoną na n >1 zbiorach encji. Jeśli E\, E2,..., En są zbiorami encji, to zbiór związków encji R jest podzbiorem następującego zbioru: { < ei, e2,..., ea> \ ev e Ei,e2 e E2,... ,ea e £„ }. Tabele PROJEKTY oraz PRACOWNICY na rysunku 2.2 przedstawiają zbiory encji. Tabela KONTRAKTY (rys. 2.3) zawiera zbiór związków między pracownikami oraz projektami, w których realizacji oni uczestniczą. Jest to związek binarny, co oznacza, że uczestniczą w nim dwa zbiory encji. Ogólnie w związkach może występować więcej zbiorów encji. W związku KONTRAKTY mógłby uczestniczyć jeszcze jeden zbiór encji KLIENCI. Zapis < Kowalski, l, ABC > oznaczałby, że pracownik Kowalski bierze udział w realizacji projektu nr l, który jest wykonywany dla klienta ABC. Między tymi samymi encjami mogą istnieć różnego rodzaju związki. Obok związku KONTRAKTY między zbiorami encji PROJEKTY oraz PRACOWNICY można również zdefiniować związek ZARZĄDZA, który określałby kierownika danego projektu. Funkcja, którą encja spełnia w związku, jest nazywana rolą. Najczęściej role występują w postaci niejawnej i nie są definiowane. W pewnych przypadkach jednak określenie ich jest konieczne. Dotyczy to sytuacji, gdy zbiory encji w związku są nierozróżnialne. Klasycznym przykładem jest tu związek PRACUJE DLA między pracownikami przedsiębiorstwa, przedstawiający zależności służbowe. Jest to związek unarny, ponieważ biorą w nim udział encje pochodzące z jednego zbioru. Związek ten można przedstawić w postaci zbioru uporządkowanych par encji należących do zbioru PRACOWNICY. Pierwszy element pary pełni rolę kierownika, a drugi jego podwładnego. Związki tego typu nazywamy rekursywnymi.

22

Związek może być opisany za pomocą swoich atrybutów. Są one nazywane atrybutami powiązań, w odróżnieniu od atrybutów charakteryzujących encje. Atrybutem związku KONTRAKTY jest WYNAGRODZENIE. Atrybut ten określa, ile pieniędzy otrzyma dany pracownik za swój udział w danym projekcie. Zwróćmy uwagę, że WYNAGRODZENIE nie należy do opisu pracownika lub projektu. Opisuje jedynie związek miedzy nimi. Powiązania między encjami można charakteryzować od strony ilościowej. Charakterystyki takie określają minimalną i maksymalną liczbę wystąpień encji w danym związku. Należą one do warunków integralności, które muszą spełniać dane. Niech Z oznacza związek między zbiorami encji EI, E2, ... , £„ •

Z=<

£2,

£„>.

Charakterystykę ilościową związku Z oznaczamy przez Q i definiujemy następująco:

' , ,V

Q (Z) = < (a,, AX («2, &),..., (<*„,#,) >,

,

*,s

gdzie o/ oraz $ oznaczają odpowiednio minimalną i maksymalną ilość wystąpień encji ze zbioru E> w związku Z. Wielkości te określają liczebność (ang. cardinality) związku. Tytułem przykładu rozpatrzmy związek KONTRAKTY = < PROJEKTY, PRACOWNICY>. W biurze projektów mogą istnieć pracownicy, którzy nie biorą udziału w żadnym projekcie. Nie będą oni uczestniczyć w związku KONTRAKTY. Minimalna liczba wynosi więc 0. Trudniej jest określić wartość maksymalną ilości wystąpień danego pracownika w związku. W ilu projektach maksymalnie może on brać udział? Liczba ta może być ograniczona przez zarząd przedsiębiorstwa. Rozpatrzmy teraz zbiór encji PROJEKTY. W bazie danych mogą istnieć projekty, do których nie dokonano jeszcze przydziału kadry. Minimalna liczba również jest równa 0. Trudno jest natomiast jednoznacznie określić wartość maksymalną ilości pracowników zatrudnionych przy realizacji projektów. Mamy więc:

\

Q (KONTRAKTY) = < (O, *), (O, *) > .

Dla związku ZARZĄDZA naturalnym byłoby przyjęcie zasady jednoosobowego kierownictwa i odpowiedzialności. Oznacza to, że jeden projekt byłby związany dokładnie z jednym pracownikiem spełniającym rolę kierownika. Maksymalna wartość wynosiłaby w tym przypadku 1. (Minimalna, jak to wykazano wyżej, jest równa 0). Z iloma natomiast projektami byłby związany pracownik? Wartość minimalna jest równa O (nie każdy musi być kierownikiem). Wartość maksymalna zależy od wielkości obciążenia związanego z kierowaniem projektem. Otrzymujemy: SU"?

4.3*

%

*~

-

3 r , tł ~\ <~

£-

Q (ZARZĄDZA) = < (O,*), (0,1) >. Pomiędzy zbiorami encji A i B mogą istnieć następujące powiązania AB = < A, B >: •

Jeden-do-jednego. Encja ze zbioru A jest związana co najwyżej z jedną encją ze zbioru B oraz encja ze zbioru B jest związana co najwyżej z jedną encją ze zbioru A. Q(AB) = <(k, 1), (k,l)>,

•

gdzie k = O lub k = l .

Jeden-do-wielu. Encja ze zbioru A jest związana z dowolną liczbą encją ze zbioru B. Encja ze zbioru B może być natomiast związana z co najwyżej jedna encją ze zbioru A. Q (AB) = <(*,*), (k,

gdzie k = O lub k = l .

Wiele-do-jednego. Encja ze zbioru A jest związana co najwyżej z jedną encją ze zbioru B. Encja ze zbioru B może być natomiast związana z dowolną liczbą encji ze zbioru A. : Q (AB) = < (k, IX (*,*)>,

gdzie k = O lub k = l .

Wiele-do-wiełu. Encja ze zbioru A jest związana z dowolną liczbą encji ze zbioru B i encja ze zbioru B jest Ł związana z dowolną liczbą encji ze zbioru A. :w

, --;;-"""" — • -

Q(AB)~<(*, *X (*,*)>• ~ " • " . " '

'••""•

Jeśli w związkach jeden-do-wielu i wiele-do-jednego k = l, to mówimy o związku ściśle hierarchicznym.

J

3.3. Silne i słabe encie _ -ł

0-1

- I Ł

ł

•

-«**•» • f .

,

-

\

**

!

,

^ "i ~ X

.

.

,

f

Identyfikację encji uzyskuje się za pomocą ich atrybutów. W zbiorze PRACOWNICY do odróżnienia poszczególnych encji wystarczy atrybut E#. Podobną rolę może także spełniać atrybut złożony E#, NAZWISKO. Sam atrybut NAZWISKO nie jest identyfikatorem, ponieważ mogą istnieć pracownicy o tych samych nazwiskach. Minimalny zbiór atrybutów posiadający własność identyfikacji w zbiorze nazywamy kluczem kandydującym (ang. candidate key). Zbiór atrybutów zawierający dowolny klucz kandydujący nazywa się nadkluczem (ang. superkey). Zbiór encji może posiadać więcej niż jeden klucz kandydujący. Wybrany przez projektanta bazy danych klucz kandydujący nazywamy kluczem głównym (ang. primary key). Istnieją zbiory encji, dla których nie istnieje klucz główny. Tytułem przykładu rozpatrzmy zbiór transakcji bankowych. Transakcja posiada trzy atrybuty: NUMERJTRANSAKCJI, DATA oraz KWOTA. Transakcje na różnych kontach mogą mieć te same numery. Na podstawie zbioru atrybutów nie można więc zbudować klucza głównego. Takie zbiory nazywamy zbiorami encji słabych (ang. weak entity). Encję, która posiada klucz główny nazywamy encją silną (ang. strong entity). Pojęcie silnych i słabych encji jest związane z pojęciem „zależności egzystencji" (ang. existence dependency). Zależność ta należy do warunków integralności. Mówimy, że między encjami x i y występuje zależność egzystencji, jeśli istnienie encji x zależy od istnienia encji y. Oznacza to, że jeśli encja y jest usuwana, to również encja x musi być usunięta. Mówimy, że encja y jest nadrzędna w stosunku do encji x lub że jest jej właścicielem. W powyższym przykładzie transakcje są encjami podrzędnymi (egzystencjalnie zależnymi) w stosunku do kont (encji silnych). Atrybut identyfikujący encje podrzędne w stosunku do określonej encji silnej nazywamy wyróżnikiem (ang. discriminator) lub kluczem cząstkowym (ang. partial key). W zbiorze transakcji bankowych rolę te pełni NUMERJTRANSAKCJI. Klucz główny zbioru encji słabych składa się z klucza głównego nadrzędnej encji silnej oraz wyróżnika.

3.4. Diagramy związków encji Ogólna logiczna struktura bazy danych może być przedstawiona graficznie za pomocą diagramu związków encji, który składa się z następujących elementów: • • • •

Prostokąty, które reprezentują zbiory encji; < . t :* Elipsy, które reprezentują atrybuty; Romby, które reprezentują związki między zbiorami encji; "*' * ^ "m- "Linie, które łączą atrybuty ze zbiorami encji oraz zbiory encji ze związkami.

Każdy składnik modelu ma określoną nazwę. Atrybuty będące kluczami głównymi są podkreślane. Model związków encji bazy danych dla biura projektów przedstawia rysunek 3.1. Diagram składa się z dwóch zbiorów encji: PROJEKTY z atrybutami: P#, NAZWA, BUDŻET, RODZAJ, PRIORYTET i MIASTO oraz PRACOWNICY z atrybutami: E#, NAZWISKO, WYKSZTAŁCENIE i WIEK. Między zbiorami istnieje związek wiele-do-wielu KONTRAKTY z atrybutem WYNAGRODZENIE. Kluczem głównym tego związku jest atrybut złożony P#, E#. - —-—-w- -

Rys. 3.1. Diagram związków encji dla danych z przykładu 2.1

-24

W związku mogą występować więcej niż dwa zbiory encji. Sytuację taką przedstawiono na rysunku 3.2. DCK oznacza związek między trzema zbiorami encji: DOSTAWCY, CZĘŚCI oraz KLIENCI. Do identyfikacji wystąpienia związku potrzebne są klucze główne wszystkich uczestniczących w nim zbiorów encji: D#, C# i K#. Dwa atrybuty nie wystarczą, na przykład parze wartości D#, C# mogą odpowiadać różne wartości K#, ponieważ dostawca może dostarczać daną część wielu klientom (podobnie dla pozostałych par atrybutów kluczowych: D#, K# oraz C#, K#). Na rysunku 3.2 niekluczowe atrybuty zbiorów encji zostały pominięte celem zwiększenia czytelności diagramu. Atrybut ILOŚĆ charakteryzuje związek DCK. Określa ilość danej części dostarczonej danemu klientowi przez określonego dostawcę. ;. •-. •••,.-: -.-..;;;?.>;. v -•.-,•,.£

•

•

;

•-

-

x

... J -;.;;--.--.-

—- ,,-:-:..- t ,

, . . . _ , - - - ^ . -. ;»...-.. ,:;.•..:-,•.:,.-

Role są przedstawiane na diagramach przez etykietowanie linii łączących prostokąty z rombami. Rysunek 3.3 przedstawia zbiór encji PRACOWNICY oraz zależność rekursywną PRACUJE_DLA. ' • ! .'.-

---'

f

Encje słabe oznacza się za pomocą podwójnych prostokątów. Odpowiadające im związki są reprezentowane przez podwójne romby. Rysunek 3.4 przedstawia diagram dla transakcji bankowych. Zbiór encji słabych TRANSAKCJE jest powiązany ze zbiorem encji silnych KONTA przez związek KONTRAN. Wyróżniki zbiorów encji słabych podkreśla się linią przerywaną. ^?• •

25

3.5. Specjalizacja i generalizacja

^ -t..-.

,, .. ( • • * , *.-

„ ->

„,.,.._

W modelu związków encji można uwzględniać poza omówionymi w poprzednich punktach inne, szczególne typy powiązań między danymi. Przy ich konstrukcji stosuje się specjalizację, generalizację i agregację [12]. 3.5.1. Specjalizacja Do zbioru encji mogą należeć podgrupy, które wyraźnie różnią się od pozostałych elementów. Mogą one posiadać swoje specyficzne atrybuty. Proces wyodrębniania grup w zbiorze encji nazywamy specjalizacją. Przykład 3.1. Rozważmy zbiór encji PRACOWNICY z atrybutami NUMER_PRACOWNIKA oraz NAZWISKO (rys. 3.5). Załóżmy, że każdy pracownik należy do jednego z następujących zbiorów: • •

PRACOWNICY_ETATOWI; ZLECENIOBIORCY.

Każda grupa jest opisana przez atrybuty encji zbioru PRACOWNICY plus dodatkowe atrybuty. Atrybutami pracownika etatowego są STANOWISKO oraz URLOP, a zleceniobiorcy - NUMER_ZLECENIA oraz WARTOŚĆ_ZLECENIA. Podstawą podziału jest tryb zatrudnienia.

26 f

Specjalizację można przeprowadzać wielokrotnie. Powstaje wtedy drugi poziom hierarchii. Wśród pracowników etatowych można wyodrębnić grupy w zależności od sposobu obliczania wynagrodzenia: • PRACOWNICY_AKORDOWI; • PRACOWNICY_DNIÓWKOWI; • PRACOWMCYJJMYSŁOWI.

'

•'"*"<"*

•'

,

Na diagramie związków encji specjalizacja jest przedstawiana za pomocą trójkąta z etykietą „iSA" (nazwa pochodzi z języka angielskiego: „is a" - ,jest"). Na rysunku 3.5 przedstawiono specjalizację dla zbioru pracowników. Specjalizacja może być przeprowadzana na podstawie więcej niż jednej cechy. W zbiorze encji PRACOWNICY z przykładu 3.1 można wyróżnić grupy pracowników ze względu na rodzaj wykształcenia. Mbgą zostać utworzone zbiory: EKONOMIŚCI oraz INFORMATYCY. Jeżeli na danym zbiorze przeprowadzana jest więcej niż jedna specjalizacja, to określona encja może należeć do wielu tworzonych zbiorów, na przykład ekonomista zatrudniony na zlecenie należy do zbiorów EKONOMIŚCI oraz ZLECENIOBIORCY. . - . « • ^ v»u • , > ' . « • t- *

3.5.2.Generalizacja

t

- ,

^ "

. » '

' \ ' ,'

e

'

Zbiory encji występujące w związku ISA można rozpatrywać jako zbiory wyższego i niższego rzędu. Podział początkowego zbioru w procesie specjalizacji jest wykonywany metodą zstępującą (ang. top*dawri). Projektowanie związku ISA może również przebiegać w odwrotnym kierunku. W metodzie wstępującej (ang. bottom-up) poszczególne zbiory encji łączy się w jeden na podstawie ich cech wspólnych. Proces ten nazywamy generalizacja. Początkowymi zbiorami dla projektanta mogą być PRACOWNICY_ETATOWI z atrybutami: NUMERJPRACOWNIKA, NAZWISKO, NUMERJCONTRAKTU i URLOP oraz ZLECENIOBIORCY z atrybutami NUMERJPRACOWNIKA, NAZWISKO, NUMER_ZLECENIA i WARTOŚĆJZLECENIA (przykład 3.1). Między zbiorami istnieją podobieństwa wyrażone występowaniem takich samych atrybutów. Na ich podstawie można utworzyć zbiór wyższego rzędu PRACOWNICY. W obu metodach stosowane są różne podejścia. Specjalizacja bazuje na różnicach między encjami danego zbioru. Utworzone w wyniku specjalizacji encje niższego rzędu mają inne atrybuty i uczestniczą w innych związkach niż pozostałe encje zbioru początkowego. Podział tego zbioru encji nie musi obejmować wszystkich jego elementów. Oznacza to, że encja zbioru wyższego rzędu nie musi mieć swojego odpowiednika w zbiorze niższego rzędu. W odróżnieniu od specjalizacji generalizacja bazuje na podobieństwach między zbiorami encji. Zbiór encji wyższego rzędu jest sumą zbiorów początkowych. Każda encja wyższego rzędu musi mieć więc swój odpowiednik w zbiorach niższego rzędu. 3.5.3. Więzy integralności Przy modelowaniu związków ISA można wprowadzać ograniczenia zgodne z wymaganiami użytkownika. Pierwszy typ ograniczeń dotyczy sposobu określenia które encje mogą należeć do zbiorów niższego rzędu. Wyróżnia się tu dwie możliwości: •

Przynależność zdefiniowana za pomocą warunku. Przy wyborze tego wariantu encja należy do zbioru niższego rzędu, jeśli jej atrybuty spełniają zdefiniowany warunek. Załóżmy, że zbiór encji PRACOWNICY z przykładu 3.1 posiada atrybut TRYBJZATRUDNIENIA. Wartość tego atrybutu definiuje przynależność do zbiorów niższego rzędu. Specjalizacja jest przeprowadzana automatycznie. • Przynależność zależna od użytkownika. W tej sytuacji nie istnieje jednoznaczny warunek przynależności. Dodanie encji do zbioru musi być dokonane przez użytkownika za pomocą odpowiedniej operacji. Drugi rodzaj ograniczeń określa czy encja może należeć do więcej niż jednego zbioru niższego rzędu. Zbiory niższego rzędu mogą więc być: •

Rozłączne. Specjalizacja zbioru PRACOWNICYJETATOWI z przykładu 3.1 prowadzi do powstania zbiorów rozłącznych. • Przecinające się. Zbiory PRACOWNICY ETATOWI oraz ZLECENIOBIORCY mogą zawierać te same encje. Etatowy pracownik przedsiębiorstwa (zbiór PRACOWNICYJETATOWI) może wykonywać dodatkową pracę w ramach umowy-zlecenia (zbiór ZLECENIOBIORCY). Ostatnie ograniczenie określa czy każda encja wyższego rzędu musi należeć do przynajmniej jednego zbioru encji niższego rzędu. Mamy więc przynależność: • •

Całkowitą. Obie specjalizacje z przykładu 3. l narzucają przynależność całkowitą. Częściową. Specjalizacja zbioru PRACOWNICY na podzbiory EKONOMIŚCI oraz INFORMATYCY nie narzuca przynależności każdego pracownika do jednego nich. W przedsiębiorstwie mogą być również zatrudnieni pracownicy z innym wykształceniem.

27

Przedstawione ograniczenia narzucają pewne wymagania dotyczące operacji wprowadzania i usuwania encji. Przykładowo warunek przynależności całkowitej wymaga, aby operacja wprowadzania nowej encji wyższego rzędu była związana z wprowadzeniem tej encji do co najmniej jednego zbioru niższego rzędu oraz aby operacja usuwania encji ze zbioru niższego rzędu powodowała jej usunięcie ze zbioru nadrzędnego. Analogiczne reguły obowiązują dla przynależności zdefiniowanej za pomocą warunku. Dla każdego związku ISA usunięcie encji ze zbioru wyższego rzędu wymaga jej usunięcia ze wszystkich zbiorów niższego rzędu, do których należy. 3.5.4. Dziedziczenie Encje niższego rzędu mają własność dziedziczenia cech encji nadrzędnych. Encje zbiorów PRACOWNICY ETATOWI oraz ZLECENIOBIORCY z przykładu 3.1 dziedziczą więc atrybuty NUMER PRACOWNIKA oraz NAZWISKO nadrzędnego zbioru PRACOWNICY. Zbiory te mają zatem po cztery atrybuty: PRACOWNICY_ETATOWI - NUMER_PRACOWNIKA, NAZWISKO, STANOWISKO, URLOP; ZLECENIOBIORCY - NUMER_PRACOWNIKA, NAZWISKO, NUMER_ZLECENIA, WARTOŚĆ_ZLECENIA. Oprócz atrybutów encje niższego rzędu dziedziczą także związki swoich encji nadrzędnych. Model danych z przykładu 3.1 można uzupełnić o związek PRACUJE_W zbioru encji PRACOWNICY ze zbiorem encji DZIAŁY (rysunek 3.6). Jest to związek jeden-do-wielu, ponieważ każdy pracownik może być zatrudniony tylko w jednym dziale. Encje zbiorów PRACOWNICY_ETATOWI oraz ZLECENIOBIORCY biorą udział w związku PRACUJE_W, czyli dziedziczą powiązanie swojego zbioru nadrzędnego PRACOWNICY.

Rys. 3.6. Związek hierarchiczny między zbiorami encji DZIAŁY i PRACOWNICY Zbiory encji z przykładu 3.1 tworzyły hierarchię, to znaczy każdy zbiór mógł występować jako podrzędny tylko w jednym związku ISA. Istnieją jednak sytuacje, w których zbiór encji powinien posiadać więcej niż jeden zbiór nadrzędny. Przykład 3.2. Rozważmy zbiór OSOBY z atrybutami NAZWISKO oraz WIEK (rys. 3.7). Encje tego zbioru oznaczają osoby związane z wyższą uczelnią, czyli pracowników i studentów. Obydwu grupom odpowiadają zbiory encji: PRACOWNICY z atrybutami NUMERJ>RACOWNIKA i STANOWISKO oraz STUDENCI z atrybutami NUMER ALBUMU i ROK STUDIÓW. Są to zbiory podrzędne w stosunku do zbioru OSOBY i dziedziczą one jego atrybuty. Przynależność do jednego ze zbiorów nie wyklucza przynależności do drugiego. Osoba będąca zarówno pracownikiem, jak i studentem posiada wszystkie atrybuty zbiorów OSOBY, PRACOWNICY oraz STUDENCI. Nie występuje potrzeba utworzenia dodatkowego zbioru. Czy na pewno? Jest tak, jeżeli nie istnieją specyficzne cechy osób jednocześnie pracujących i studiujących, cechy których nie mają ani pracownicy, ani studenci. W przeciwnym razie należy utworzyć nowy zbiór PRACOWNICYjSTUDENCI podrzędny w stosunku do zbiorów PRACOWNICY i STUDENCI. Może przy tym powstać zjawisko konfliktu nazw, ponieważ atrybuty są dziedziczone od dwóch zbiorów nadrzędnych - dziedziczenie wielokrotne. W omawianym przykładzie problem ten nie występuje.

Przykład 3.3. Za pomocą związku ISA można wyeliminować encje z atrybutami, których wartości są nieokreślone. Rozpatrzmy zbiór encji OSOBY o atrybutach: NAZWISKO, MIASTO oraz KOD. Załóżmy, że nie znamy kodu wszystkich osób. Wprowadźmy zbiór encji OSOBY_KOD podrzędny w stosunku do zbioru OSOBY (rys. 3.8). Należą do niego encje odpowiadające osobom, których kod jest znany. Mają one tylko jeden atrybut KOD. Pozostałe atrybuty są dziedziczone ze zbioru nadrzędnego. ,_ , ,c

Rys. 3.8. Diagram związków encji do przykładu 3.3

29

T Przykład 3.4.

,

„,-«_-—

Rysunek 3.9 przedstawia model związku unaraego MAŁŻEŃSTWO. Przez zastosowanie związku ISA diagram uzyskuje bardziej czytelną postać (rys. 3.10).

Przykład 3.5. Za pomocą związku ISA można przekształcić kardynalności związku z < (O, *), (O, *) > na < (l, *), (l, *) >. Rozważmy zbiory encji DOSTAWCY i CZĘŚCI oraz ich związek DOSTAWY (rys. 3.11). Powiązanie zbiorów jest typu wiele-do-wiełu: •--.... .„,..-•—— Q (DOSTAWY) = < (O, *),((),*)>.

Istnieją zatem dostawcy, którzy nie dostarczają żadnej części oraz części, które nie są dostarczane. Diagram na rysunku 3.12 przedstawia ten sam związek w innej postaci. Do zbioru D należą tylko encje oznaczające dostawców, którzy dostarczają przynajmniej jedną część. Analogicznie do zbioru C należą encje oznaczające części, które są dostarczane przynajmniej przez jednego dostawcę. Zbiory D i C nie mają dodatkowych atrybutów. Wszystkie ich atrybuty są dziedziczone.

30

3.6. Agregacja Rozpatrzmy diagram związków encji przedstawiony na rysunku 3.13. Między zbiorami encji PRACOWNICY i MASZYNY istnieje związek PRACUJE. Jest to powiązanie wiele-do-wielu. Parze pracownik-maszyna mogą odpowiadać produkty, będące rezultatem pracy. Wydaje się więc, że związki PRACUJE oraz PRODUKUJE można zastąpić jednym z trzema zbiorami encji. Uzyskalibyśmy znaczne uproszczenie diagramu. Niestety taka modyfikacja prowadziłaby do błędnego modelu. W wyniku utworzenia jednego związku każdej parze pracownik-maszyna musi odpowiadać produkt, co jest sprzeczne założeniem.

Model z rysunku 3.13 zawiera redundancję, ponieważ każda para pracownik-maszyna w związku PRODUKUJE występuje także w związku PRACUJE. Do modelowania takiego przypadku można zastosować agregację. Agregacja jest abstrakcją, w której związki są traktowane jak encje wyższego rzędu. W omawianym przykładzie zbiory PRACOWNICY i MASZYNY oraz związek PRACUJE można zastąpić zbiorem encji JEDNOSTKIJPRACY. Rysunek 3.14 przedstawia zmodyfikowany diagram po zastosowaniu agregacji.

31

4. Relacyjny model danych ftf

.- '•••«

»- >,

-.-,-

•

,

, ^, ,,

»-

-,-«,

_.

&0i

4.1. Definicje wstępne Relacyjną bazę danych można nieformalnie traktować jak parę złożoną z następujących składników [9]: • •

?A

Zbioru tabel, w których zawarte są informacje o obiektach i zwiajzkach między nimi; Zbioru zależności semantycznych.

»tł

Opis obiektu lub związku ma postać wiersza, którego składnikami są wartości odpowiednio wybranych w procesie projektowania atrybutów. Wartości pojawiające się w kolumnie muszą należeć do dziedziny atrybutu. Wiersze tabel nazywane są krotkami (ang. tupie). Definicja 4.1. Iloczynem kartezjańskim zbiorów D\, D2,..., DK nazywamy zbiór wszystkich uporządkowanych wartości < d\, d2,..., ^ . da >, takich że d\ eDj, d2 eĄ.,..., d^ e A . '«S

Definicja 4.2. Niech dany będzie skończony zbiór SCH- {A^,A2,..., An }, którego elementy będziemy nazywać atrybutami i niech każdemu atrybutowi A\ e SCH przyporządkowany będzie zbiór wartości A = DOM (A$ zwany dziedziną atrybutu. Relacją 7? rozpiętą na zbiorze SCF/nazywamy dowolny podzbiór iloczynu kartezjańskiego zbiorów D\,D2, ... , D„. Definicja 4.3.

s

~*

• •*:-"s--••

Zbiór nazw atrybutów SCH= {Ai,A2, ..., Aa] nazywamy schematem relacji.

'

J

Relację R o schemacie SCH zapisujemy w postaci R (SCH). Do oznaczenia krotki stosujemy zapis t (SCH). Zbiór atrybutówXbędący podzbiorem schematu Xc SCH nazywamy atrybutem złożonym. Zapis t (X) oznacza więc wartość atrybutu złożonego. Definicja 4.4. Schematem relacyjnej bazy danych określonym na zbiorze atrybutów U nazywamy zbiór schematów relacji { SCHi, SCH2, ..., SCH0}, przy czym SCHV u SCH2 u ... u SCHa = U. Szczególne znaczenie mają atrybuty, na podstawie których można jednoznacznie zidentyfikować krotki relacji., Nazywamy je kluczami. ,,»,„_.•..„, „„„. * * •> . ., . . - . .. .,-...,,%-. f f.-.,rr .•>t~~f>t>--iltjf T,- • f> ,-,; Definicja 4.5.

'

Kluczem A;relacji/? o schemacie ^.'//nazywamy minimalny zbiór atrybutów, taki że:

i

• •

KcSCH; Dla dowolnych krotek t\, (K) = t2(K)=> f, (SCH) = t^(SCH).

Oznacza to, że w relacji ^? nie ma dwóch krotek, które miałyby tę samą wartość klucza. Kluczem relacji PROJEKTY jest P#. Nie istnieją dwa projekty o tym samym numerze. Analogiczną rolę w relacji PRACOWNICY spełnia atrybut E#. W relacji KONTRAKTY nie można jednoznacznie zidentyfikować krotki na podstawie jednego tylko atrybutu. Klucz składa się z dwóch atrybutów: P# i E#. Własność klucza mogą posiadać różne zbiory atrybutów. Nazywamy je kluczami kandydującymi (ang. candidate key). Atrybuty należące do klucza kandydującego nazywamy kluczowymi. W relacji PRACOWNICY rolę klucza, oprócz atrybutu E#, może także spełniać atrybut NAZWISKO, jeśli nie ma dwóch pracowników o tym samym nazwisku. Klucz wybrany przez projektanta bazy danych nazywamy kluczem głównym (ang. primary key). W notacji używanej dla zapisu relacji atrybuty należące do klucza głównego podkreśla się, np. KONTRAKTY (P#, E#, WYNAGRODZENIE).

n

Definicja 4.6.

'.,

;

Nadkluczem relacji R o schemacie SCH nazywamy dowolny zbiór atrybutów X, taki że: •

K c X, gdzieś jest kluczem relacji R.

-

'"

- !

Każdy klucz jest nadkluczem. Nadkluczem jest zbiór atrybutów tworzących schemat relacji. Atrybut (lub grupa atrybutów) jednej relacji może stanowić klucz innej relacji. Nazywamy go kluczem obcym (ang. foreignkey). , Definicja 4.7.

" "

-- ; - -

^^-''-^^

' ^u - •- -

Atrybut X relacji # nazywamy jej kluczem obcym, jeżeli: • •

X nie jest kluczem relacji R; • Wartości atrybutu X są wartościami klucza innej relacji.

-

•» .,» y. , , f ."

W relacji KONTRAKTY kluczami obcymi są atrybuty P# i E#. Ich wartości są wartościami kluczy relacji PROJEKTY i PRACOWNICY. Unikalność klucza relacji należy do warunków integralności, które stanowią zbiór ograniczeń narzuconych na dane zapisane w bazie. Niektórzy autorzy włączają je do definicji schematu relacji. Definicja 4.8. Niech W oznacza zbiór warunków integralności dotyczących relacji R o schemacie SCH. Schematem semantycznym relacji R nazywamy parę ę - (SCH, W) . %,, :; R Przy rozpatrywaniu zbioru relacji (zbioru schematów semantycznych) należy uwzględnić warunki integralności dotyczące wzajemnej zgodności tych relacji.

"

Definicja 4.9.

'

Niech będzie dany zbiór schematów semantycznych relacji 0 = { ę\ , ,, Q) . Jeżeli zbiór Q jest zbiorem pustym, to schemat semantyczny bazy danych nazywamy wolnym. Definicja 4.10.

' '

I

- " " " " - • • ^ P «-^' ;•>»•-«« »«•<,-«*»-«. r< r

Relacyjną bazą danych rozpiętą na schemacie !P nazywamy parę {91, ?0, gdzie 9 = (0, Q), a 9ł jest zbiorem relacji rozpiętych na schematach ze zbioru - { ę} , q>3 , ... , ę„ }, takim że: • • •

Na każdym schemacie ęt - (Xt, W,), l < i < n, rozpięta jest tylko jedna relacja spełniająca zależności ze zbioru W, ; Liczba relacji jest równa liczbie schematów relacji; ; Wszystkie relacje z 9t spełniają zależności z Q. «"— \>---^'A(^v.

Warunki integralności definiujące ograniczenia bieżącego stanu bazy danych nazywamy statycznymi, w odróżnieniu od warunków dynamicznych, które dotyczą przejścia od jednego stanu do drugiego. Operacje zmieniające stan bazy danych na sprzeczny z narzuconymi warunkami powinny być odrzucone. Warunki dynamiczne mogą uwzględniać zależności między wartościami atrybutów nowej i starej krotki (np. wartość atrybutu WYNAGRODZENIE nie może się zmniejszyć). Warunki statyczne obejmują: •

Unikalność klucza relacji. Warunek ten nie dopuszcza do istnienia dwóch krotek o jednakowej wartości klucza. Ponadto żaden z atrybutów kluczowych nie może przyjmować wartości pustej.

•

Warunki integralności krotki. Muszą być one spełnione przez poszczególne krotki niezależnie. Są to najprostsze warunki integralności. Najłatwiej jest je zdefiniować i sprawdzić, na przykład: a) b)

Określony przedział wartości, np. atrybut WYNAGRODZENIE nie może przekraczać l O 000; Lista możliwych wartości, np. atrybut STANOWISKO może przyjmować wartości wynikające ze struktury organizacyjnej przedsiębiorstwa. c) Związki między atrybutami, np. atrybut określający początek imprezy turystycznej musi być datą wcześniejszą niż atrybut określający termin jej zakończenia;

34

d)

Format wartości atrybutu, np. wszystkie znaki atrybutu NAZWISKO powinny być literami.

.< *.~*t~-i *

*-•

•

Warunki wewnętrzne relacji. Dotyczą one wartości atrybutu w różnych krotkach, np. wynagrodzenie pracownika biorącego udział w realizacji projektu nie może przekraczać wynagrodzenia kierownika projektu.

•

Warunki zbioru krotek, np. średnia zarobków w przedsiębiorstwie nie może przekraczać średniej krajowej.

•

Warunki dotyczące kilku relacji, np. suma wynagrodzeń pracowników biorących udział w realizacji projektu (relacja KONTRAKTY) nie może przekraczać budżetu projektu (relacja PROJEKTY).

•

Integralność referencyjna. O naruszeniu integralności referencyjnej (ang. referential integrity), zwanej także integralnością odniesienia, mówimy wtedy, jeżeli w bazie danych istnieje odniesienie (referencja) do obiektu, który nie istnieje. Taki stan może powstać, jeśli po usunięciu krotki nie zostaną zlikwidowane wszystkie referencje do niej. Problem integralności referencyjnej powstaje przy modelowaniu związków miedzy danymi. Wartości atrybutów P# oraz E# występujące w relacji KONTRAKTY muszą także występować w relacjach PROJEKTY i PRACOWNICY. W przeciwnym razie istniałyby odwołania do nie istniejących obiektów. Każdy z atrybutów P# oraz E# jest kluczem obcym relacji KONTRAKTY.

Ze względu na moment sprawdzania warunki integralności można także podzielić na natychmiastowe i odroczone. Warunki natychmiastowe są sprawdzane po operacji zmieniającej stan bazy danych. Dla warunków odroczonych test zgodności jest wykonywany z opóźnieniem. Dopuszcza się w ten sposób chwilową niezgodność bazy danych. Test przeprowadzany jest po zakończeniu transakcji składającej się ze zbioru operacji, z których zaakceptowane są wszystkie lub żadna. Do dziedziny każdego atrybutu należą wartości puste NULL. Stosowanie wartości pustych zwiększa złożoność bazy danych. Powodują one trudności przy dostępie do danych i dlatego powinno się je eliminować, jeżeli jest to możliwe. Najczęstszymi przyczynami występowania wartości pustych są: •

'" ^'K "

Brak znajomości danych. Wartość atrybutu istnieje, ale nie jest znana.

"

•

Zastrzeżenie danych. Wartość atrybutu istnieje, ale nie może być ujawniona. Mogłoby to spowodować konsekwencje prawne, na przykład z powodu naruszenia ustawy o ochronie danych osobowych.

•

Brak możliwości przyporządkowania danych. Wartość atrybutu nie istnieje. Gdyby w relacji PRACOWNICY istniał jeszcze jeden atrybut WYŻSZA_SZKOŁA, to jego wartość istniałaby tylko dla absolwentów wyższych uczelni. Dla pozostałych pracowników atrybut ten byłby nieokreślony.

Wynikiem działań arytmetycznych, w których występuje wartość NULL, jest również wartość NULL. Wynik porównania dowolnej wartości z wartością NULL jest nieokreślony. Przyjmuje nieznaną wartość logiczną (ang. UNKNOWN). Określenie działań logicznych uwzględniających wartości UNKNOWN wymaga zastosowania logiki trójwartościowej [15]. W tabeli na rysunku 4.1 przedstawiono wyniki operacji alternatywy, koniunkcji oraz negacji. Przyjęto, że wartości UNKNOWN odpowiada Vi. Wartości logiczne l i O odpowiadają wartościom TRUE - prawda i FALSEfełsz. . - , - _ .- ., ,-,.„_.„ „„. ,.,-«.-„ ..,„.„, ,-„„«,.,,:„> * ,

X

Y

X OR Y

X AND Y

NOT X

0

0

0

0

1

0

'/2

%

0

1

0

1

1

1

Vi

0

'/2

0 0

Vi

Vi

Vi

Vi

Vi

Vi

Vi

1

Vi 0

Vi

Vi

0

1 I 1

0 Vi

1

1

1 1 1

1

Rys. 4.1. Operacje logiczne z wartością UNKNOWN

l

0 0

£1

4.2. Algebra relacji ^<* •??••«•«: vxi c/'/* ' -- 4 '•> ', -f"

--., > , t , ,*t

Zapytania do relacyjnej bazy danych można przedstawić w postaci zbioru operacji wysokiego poziomu stanowiących algebrę relacji (ang. relational algebra). Żądaną informację otrzymuje się w postaci relacji wynikowej. Na algebrę relacji składają się dwa podstawowe typy operacji: * ** " ' • - !i • •

Operacje mnogościowe: suma, różnica, iloczyn oraz iloczyn kartezjański; Operacje relacyjne: selekcja, projekcja, złączenie i dzielenie.

Operacje: suma, różnica, iloczyn kartezjański, selekcja oraz projekcja są operacjami podstawowymi. Można za ich pomocą wyrazić w algebrze relacji dowolną kwerendę. Wyrażenia używające tylko tych operacji mogłyby dla niektórych kwerend osiągnąć znaczne rozmiary. W tym celu zdefiniowano dodatkowe operatory. 4.2.1. Operacje podstawowe -•» -'•:... f:/:-.vfs»'<>-:;o>r.: ,it:-xm« ««.:€"»'»•»»•» ^-t-!,-^-.- •?•.

(1) Suma

Suma i różnica, podobnie jak inne operacje mnogościowe, są analogiczne w swym działaniu do znanych z teorii mnogości operacji na zbiorach. Sumą relacji R i S jest więc zbiór krotek należących do R lub do S lub do obu tych relacji:

Argumenty operacji są relacjami o jednakowych schematach. Własności sumy: • • •

Idempotentność: Łączność: /?u(Su 7) T; ^ *• ' =^ (/?u5)u ' ' Przemienność:

(2) Różnica Różnicą relacji R oraz S jest zbiór tych krotek relacji R, które nie należą do S:

Argumenty różnicy, podobnie jak w przypadku sumy, muszą być określone na tych samych schematach. Obie operacje nie zmieniają schematu relacji. Przykład 4.1. Niech relacja R zawiera krotki reprezentujące pracowników z wykształceniem informatycznym, a relacja S krotki reprezentujące pracowników, których wiek przekracza 40 lat. Na rysunku 4.2 przedstawiono ich sumę oraz różnicę. (3) Selekcja

,

Selekcja (ang. select) oraz projekcja (ang. projecf) są operacjami unarnymi. Ich argumentem jest jedna relacja. Pozostałe trzy operacje podstawowe działają na dwóch relacjach. Nazywamy je binarnymi. Selekcja polega na wyodrębnieniu z danej relacji R tych krotek, które spełniają pewien warunek F. Operację tę będziemy oznaczać przez ffF (R) . Selekcja nie zmienia schematu relacji. Jej wynikiem jest relacja stanowiąca podzbiór „poziomy" relacji pierwotnej. Można ją opisać następująco:

aF(R) = { f . t < = R A F (f)}. Warunek F jest zdaniem logicznym (predykatem), które w zależności od wartości atrybutów w danej krotce przyjmuje wartość logiczną;?ravrab lub^ofez. Predykat selekcji składa się z formuł o postaci:

t(A) 9 c

lub t(A) 6 t(B),

gdzie 0 = {<,<,=,>,>,ź}, AiB oznaczają atrybuty, c należy do dziedziny atrybutu A. Jeżeli F] i F2 są formułami, to wyrażenia: F/ v F2, Fj A F2 oraz -\Fj są również formułami. 36

R E#

NAZWISKO WYKSZTAŁCENIE

E#

43 53

E10 E13 E16

Makowski Gumowski

Informatyk Chemik

52 44

El E2

Makowski

52

E4

Grabowski Jodłowski

Informatyk Informatyk

36

E5

28

E13 E18

41 52 58

R-S

RuS E#

WIEK

Ekonomista Prawnik Informatyk Fizyk Ekonomista

41 27

Dakowski Olczak

NAZWISKO WYKSZTAŁCENIE Kowalski Abowski Dakowski Dymowski Pawlak

Informatyk Informatyk Informatyk

E4 E9

E19

WIEK

NAZWISKO WYKSZTAŁCENIE

WIEK

E#

NAZWISKO WYKSZTAŁCENIE WIEK

El E2 E4

Kowalski Abowski Dakowski

Ekonomista Prawnik Informatyk

43 53

E9 E18

Olczak Grabowski

Informatyk Informatyk

27 36

41

E19

Jodłowski

Informatyk

28

E5 E9

Dymowski Olczak Pawlak

Fizyk Informatyk Ekonomista

52 27

Makowski Gumowski Grabowski Jodłowski

Informatyk Chemik Informatyk Informatyk

52

E10 E13 E16 E18 E19

58 44 36 28

-1

Rys. 4.2. Suma i różnica relacji z przykładu 4. l f

Operacja selekcji ma następujące własności:

xV\{ i

\

aF,G(R } = oF(ffG (K)) = OG(aF(R)) = aF(R) n aa (R);

•

Przykład4.2.

'•

5

J

' '

~ "

• "--••-•

* -.-»-,»; f

•

-'

-

•- ---

Dla relacji PRACOWNICY i warunków: F= (WYKSZTAŁCENIE = 'Informatyk') oraz G = (WYKSZTAŁCENIE = 'Informatyk' A WIEK > 35) otrzymujemy relacje przedstawione na rysunku 4.3. *s ;-

ffG (PRACOWNICY)

aF (PRACOWNICY) E#

NAZWISKO WYKSZTAŁCENIE

WIEK

E#

NAZWISKO WYKSZTAŁCENIE

WIEK

E4 E9

Dakowski Olczak

Informatyk Informatyk

41 27

E4 E13

Dakowski Makowski

Informatyk Informatyk

41 52

E13

Makowski

Informatyk

52

E18

Grabowski

Informatyk

36

E18 E19

Grabowski Jodłowski

Informatyk Informatyk

36 28

Rys. 4.3. Operacja selekcji relacji z przykładu 4.2

37:

(4) Projekcja

«

t

Nieformalnie można powiedzieć, że wykonanie projekcji Hx (R) relacji R o schemacie SCH na zbiór atrybutów X c SCH polega na obcięciu kolumn związanych z atrybutami ze zbioru SCH - X . Po wykonaniu tej operacji otrzymamy relację stanowiącą podzbiór „pionowy" relacji pierwotnej. Projekcję wykonuje się w celu wyodrębnienia z danej relacji pewnych atrybutów. Liczba krotek w utworzonej relacji może być mniejsza niż w relacji pierwotnej. Wynika to z faktu, że niektóre krotki po zredukowaniu relacji do mniejszego zbioru atrybutów mogą przyjąć te same wartości, a więc nie będą już stanowiły różnych elementów relacji (na przykład liczba rodzajów wykształcenia w relacji PRACOWNICY jest mniejsza niż liczba pracowników). Projekcja dokonuje eliminacji tych powtórzeń. Relacja wynikowa jest rzutem relacji pierwotnej na wybrane atrybuty. Wykonanie projekcji wiąże się ze zmianą schematu. Schemat rzutu zawiera się w schemacie relacji pierwotnej. Relacja wynikowa jest następującym zbiorem krotek:

A Własności projekcji: •

•' *

nx(nr(/?)) = UX(R), jeżeli JTc Y;

Przykład 4.3.

•

,

Na rysunku 4.4 przedstawiono relację otrzymaną w wyniku wykonania projekcji relacji PRACOWNICY na zbiór X= {WYKSZTAŁCENIE}.

Ilx (PRACOWNICY) WYKSZTAŁCENIE Ekonomista Prawnik Matematyk Informatyk Fizyk Elektronik Chemik Architekt Rys. 4.4. Operacja projekcji relacji z przykładu 4.2

(5) Iloczyn kartezjański. Niech R i S będą relacjami o schematach odpowiednio X i Y. Iloczynem kartezjańskim relacji R i S nazywamy następujący zbiór krotek:

RxS={t:3reR A

A t(X) = r(X) A

Krotki relacji będącej iloczynem kartezjańskim są konkatenacjami krotek relacji pierwotnych, a jej schemat zawiera wszystkie atrybuty obu relacji. Realizacja iloczynu kartezjańskiego przebiega przez łączenie wszystkich krotek relacji pierwszej ze wszystkimi krotkami relacji drugiej. Liczba krotek relacji wynikowej jest równa iloczynowi ilości krotek rełacji R oraz S. .. l _

S = OL, (PRACOWNICY). Są to relacje unarne. Relacja R jest zbiorem numerów pracowników. Ich iloczyn kartezjański jest zbiorem wszystkich p numerem pracownika.

3S

Jeżeli w relacjach R i S występują takie same atrybuty, to celem uniknięcia niejednoznaczności należy zastosować nazwy kwalifikowane, na przykład iloczynem kartezjańskim relacji KONTRAKTY oraz PRACOWNICY jest relacja o atrybutach: P#, KONTRAKTY.E#, WYNAGRODZENIE, PRACOWNICY.E#, NAZWISKO, WYKSZTAŁCENIE oraz WIEK. Zauważmy, że w pewnych krotkach iloczynu kartezjańskiego wystąpią różne wartości atrybutów KONTRAKTY.E# oraz PRACOWNICY.E#. ? ;;, . ; ś '

j'

"

'

4.2.2. Dodatkowe operatory algebraiczne

',

•

••'•

' " ' " " " ' " ;

Omówione w tym podpunkcie operacje nie zwiększają mocy algebry relacji. Umożliwiają jednak uproszczenie zapisu poszczególnych kwerend. ( 1 ) Iloczyn

• • : . - . ,

Iloczynem relacji R i S jest zbiór krotek, które występują w obu relacjach. Można go przedstawić za pomocą operacji różnicy:

Przykład 4.5.

<

W wyniku zastosowania operacji iloczynu do relacji z przykładu 4. l otrzymujemy relację przedstawioną na rysunku 4.5. -«„ , .,. ,

RnS E# E4 E13

NAZWISKO WYKSZTAŁCENIE Dakowski Makowski

Informatyk Informatyk

WIEK

41 52

Rys. 4.5. Iloczyn relacji z przykładu 4.1 "Vł»*ii.v,; v j, ', i:(2) Złączenie Jeżeli dwie relacje mają atrybuty pochodzące ze wspólnej dziedziny, to można je względem tej dziedziny połączyć. Powstaje wtedy nowa rozszerzona relacja, której schemat jest równy sumie schematów łączonych relacji. Przykład 4.6.

.

- ,

.,

•

,'>.:-.--,

t

-,»«ł-v

Rozważmy kwerendę: „Podaj nazwiska pracowników biorących udział w realizacji projektu Pl". Do znalezienia odpowiedzi trzeba użyć dwóch relacji: KONTRAKTY, gdzie znajdują się numery pracowników pracujących nad danym projektem oraz PRACOWNICY, gdzie znajdują się ich nazwiska. Pierwszym krokiem jest zbudowanie iloczynu kartezjańskiego tych relacji, następnie dokonanie selekcji krotek według odpowiedniego warunku i w końcu zastosowanie operacji projekcji na atrybut NAZWISKO. Można to wyrazić następująco: ONAZWISKO (^(PRACOWNICY x KONTRAKTY)) , gdzie F=KONTRAKTY.P# = 'P1' A KONTRAKTY.E# = PRACOWNICY.E# . ^•złączenie (0-join) jest kombinacją selekcji i iloczynu kartezjańskiego. Oznaczamy je przez *& gdzie * jest symbolem złączenia, a 6 oznacza predykat selekcji. Złączenie relacji według warunku równości atrybutów o tych samych dziedzinach nazywa się rawnozłączeniem (ang. eąuijoin). Operację 0-złączenia dwóch relacji R i S można przedstawić w postaci:

39*

NAZWISKO (PRACOWNICY V KONTRAKTY) NAZWISKO Kowalski Abowski Nowak Majewski Pawlak Grabowski Markiewicz Rys. 4.6. Nazwiska pracowników biorących udział w realizacji projektu P l - przykład 4.6 Kwerenda z przykładu 4.6 przyjmuje postać (rys. 4.6): ONAZWISKO (PRACOWNICY *F KONTRAKTY). Często warunek F wymaga równości atrybutów, które mają takie same dziedziny i nazwy. ^-złączenie dla takiego warunku nazywa się złączeniem naturalnym (ang. natural joiri). Jest ono oznaczane przez R * S. Przy wykonywaniu złączenia naturalnego, jeden z powtarzających się atrybutów jest usuwany z relacji wynikowej. Przebieg złączenia naturalnego relacji R i S jest następujący: l. 2. 3.

Wyznaczenie iloczynu kartezjańskiego relacji RiS; Wybór z relacji R x S krotek, których wartości wspólnych atrybutów relacji R i S są równe; Wykonanie projekcji usuwającej powtarzający się atrybut .

Złączenie naturalne można przedstawić za pomocą operacji podstawowych:

gdzie Z jest sumą schematów relacji R oraz S , a F jest formułą określoną następująco: F = R.Ai=

A

A

A

Warunek F wymaga równości wszystkich wspólnych atrybutów obu relacji. Zapis R,A\ oznacza atrybut A \ relacji R. Na rysunku 4.7 przedstawiono złączenie naturalne relacji PRACOWNICY i KONTRAKTY. W szczególnym przypadku, gdy relacje R oraz S nie mają wspólnych atrybutów, złączenie naturalne jest ich iloczynem kartezjańskim. .• <

Własności operacji złączenia: • • • •

Idempotentność: R*R = R; Łączność: R* (S* T) = (R* S)* T; Przemienność: R*S = S*R; Prawa rozdzielności:

,

Dla relacji R i S określonych na tych samych schematach:

Jeżeli ponadto relacja T ma taki sam schemat, to:

Niech relacje R oraz S będą określone na schematach odpowiednio X oraz Y. Niech W oraz Z oznaczają zbiory atrybutów. (l)Tlx(R*S)cR oraz Tly(R*S)cS; (2) Jeżeli Z e X, to Uz (R) *R = R;

(3) Jeżeli WuZ=X, to R c UW(R} * Uz (R) ;

{

^ n

. ~

-

-.

-

(4) Jeżeli 7=X, to R*S = Jeżeli ponadto relacje R i S nie mają wspólnych atrybutów, czyli Xr\Y-0, ioR*S = RxS.

PRACOWNICY * KONTRAKTY

E#

NAZWISKO

El El El E2 E2 E2 E3 E4 E4 E6 E6 E6 E7 E8 E9 E10 E10 E14 E18 E18 E19 E19 E20

Kowalski Kowalski

WYKSZTAŁCENIE

WIEK

P#

WYNAGRODZENIE

Ekonomista

43 43 43 53 53 53 34 41 41 23 23 23 38

Pl P4 P5 Pl P3 P5 P3 P2

1000 2000

P4 Pl P3 P4 Pl P3 P2 Pl P2 P2 Pl P4 P4 P5 Pl

4000

Kowalski

Ekonomista Ekonomista

Abowski

Prawnik

Abowski

Prawnik

Abowski

Prawnik

Azowski

Matematyk

Dakowski

Informatyk

Dakowski

Informatyk

Nowak

Elektronik

Nowak

Elektronik

Nowak

Elektronik

Majewski

Ekonomista

Abacki

Matematyk

Olczak

Informatyk

Pawlak

Ekonomista

Pawlak

Ekonomista

Nowakowski

Ekonomista

Grabo wski

Informatyk

Grabowski

Informatyk

Jodłowski

Informatyk

Jodłowski

Informatyk

Markiewicz

Elektronik

35 27 58 58 30 36 36 28 28 25

2000 1000

7000 1000

5000 5000 2000 3000 1000 1000 1000

8000 4000 3000 4000 2000 4000 2000 8000 6000

Rys. 4.7. Złączenie naturalne relacji PRACOWNICY i KONTRAKTY. Realizacja kwerendy z przykładu 4.6 za pomocą złączenia naturalnego wymaga połączenia relacji PRACOWNICY i KONTRAKTY, a następnie wykonania operacji selekcji celem wybrania krotek spełniających warunek P# = 'Pl'. Połączenie następuje względem wspólnego atrybutu E#. Operacja złączenia naturalnego łączy krotki z tą sama wartością E#. Rezultatem złączenia PRACOWNICY * KONTRAKTY jest relacja określona na schemacie (rys. 4.7): X= (E#, NAZWISKO, WYKSZTAŁCENIE, P#, WYNAGRODZENIE}.

*

'

'

W wyniku operacji złączenia powstają rozbudowane relacje, co zwiększa koszt wyszukiwania danych. Rozmiary relacji wynikowych mogą zostać zmniejszone przez taką zmianę kolejności wykonywanych działań, która spowodowałaby zmniejszenie rozmiarów relacji będących argumentami operacji złączenia. W tym celu w kwerendzie z przykładu 4.6 należy najpierw wybrać odpowiednie krotki z relacji KONTRAKTY, czyli wykonać operację selekcji przy warunku P# = 'Pl', a następnie wykonać projekcję na atrybut E#. Otrzymamy wtedy relację: *-• 'nvsm^ «:eto«d rw '-•

*i

=

HĘ* (ap# - TV (KONTRAKTY)) .

,-(t

rf-'-«S8Są;iw*>CI

"'i>ff

Relacja RI ma tylko jeden atrybut i zawiera numery pracowników biorących udział w realizacji projektu Pl. Następnym krokiem jest jej złączenie z relacją PRACOWNICY i wykonanie projekcji na atrybut NAZWISKO. Otrzymujemy relację: ^

= ONAZWISKO (*. * PRACOWNICY) . Wniosek: Celem optymalizacji algorytmów wyszukiwania informacji żądań operacje selekcji oraz projekcji powinny być wykonywane jak najwcześniej. Zmniejsza się w ten sposób liczbę danych, na których jest kontynuowana realizacja kwerendy. • " .\ - , ł ,

(3) Dzielenie

4. ^ f

Operacja dzielenia jest stosowana do wyrażenia kwerend, w których występuje fraza „dla wszystkich". Przykład 4.7.

"

"*~

J

- - "f''"-**?v'*

*

Rozważmy kwerendę: „Znajdź numery pracowników, którzy uczestniczą w realizacji wszystkich projektów, których budżet przekracza 100 000". W wyniku wykonania projekcji jrip#,E# (KONTRAKTY)

"i J.

p# Pl

Pl Pl

Pl Pl Pl Pl

P2 P2 P2 P2 P3 P3 P3 P3 P4 P4 P4 P4 P4 P5 P5 P5

E#

P#

E#

El E2 E6 E7 ElO E18 E20 E4 E9 ElO E14 E2 E3 E6 E8 El E4 E6 E18 E19 El E2 E19

Pl P4

El E6 E18

*

*. i„

Rys. 4.8. Iloraz relacji z przykładu 4.7 otrzymuje się zbiór powiązanych ze sobą par atrybutów P# i E#. Numery projektów o budżecie większym niż 100 000 można uzyskać za pomocą wyrażenia: R2 ~ Tlf# (^BUDŻET > 100 000 (PROJEKTY)) .

: należy znaleźć numery pracowników, które występują w relacji R} z każdym numerem projektu zawartym w R2. j ia to operacja dzielenia. 4 SSedi relacje R i S będą określone na schematach odpowiednio X i Y oraz niech Y c X. Krotka t należy do ilorazu ? -=- S relacji R i S, jeżeli dla każdej krotki s e S istnieje w R krotka r spełniająca następujące warunki: ,-t,„m~v „*>

r W = j(y)

oraz

/-(A^-IO = /(A r -y). - --

--..--...;.,«;-,---.

,,Q

lonz jest zbiorem takich krotek /, dla których konkatenacja krotek t i s należy do relacji R dla każdej krotki s występującej w S. Schemat ilorazu jest różnicą schematów relacji R oraz S. Za pomocą operacji podstawowych iloraz ji /? i S można przedstawić za pomocą następującego wzoru: ' - - ".; *M , | /J * 5 = Or-r W - IL--r ((Fb--r W x S) -/?) . IL-- K(/?) zawiera krotki spełniające warunek r (X- Y) = t (X- Y). Drugi człon wzoru służy do eliminacji autek, które nie spełniają warunku r (Y) = s (Y) . Wyrażenie FLy- r (K) x S określone na schemacie Xłączy każdą j attkę występującą w \\x-y (R) z każdą krotką występującą w S. Wobec tego wyrażenie (Ylx-r(R) x S)- R zawiera z pary krotek z Tix-r(R) i S, które nie występują w R. Jeżeli krotka t' występuje w HX-Y ((Y\x-r(R) * S)- R), to śmieje krotka s w S, która nie tworzy z krotką t' krotki r w R. Zatem t' zawiera wartości atrybutów ze zbioru X - Y, iJóre nie występują w R 4- S. Są to wartości eliminowane z relacji Hx- r (R) • Na rysunku 4.8 przedstawiono relacje R i i ? .?2 z przykładu 4.7 oraz ich iloraz. t ;:

„v"- v;j;„. , , , " . " • ,

^

423. Przykłady zastosowań * tym podpunkcie omówione wcześniej operacje algebry relacyjnej zostaną zilustrowane przykładami wyszukiwania Mnych. Wszystkie przykłady dotyczą modelu danych dla biura projektów (rys. 2.2 i 2.3). Przykład 4.8. j.

"""

' '

', ,

'?

&c ,>. <*«&'

Podaj numery pracowników, którzy biorą udział w realizacji projektu P l.

Wszystkie informacje wymagane w odpowiedzi znajdują się w relacji KONTRAKTY. Należy wybrać krotki w których wtość atrybutu P# jest równa Pl, a następnie dokonać projekcji na atrybut E#. Mamy więc: l Tr

l

(KONTRAKTY)).

Podaj nazwiska pracowników, którzy biorą udział w realizacji projektu Pl (przykład 4.6).

3dację zawierającą numery pracowników uczestniczących w realizacji projektu Pl (kwerenda 1) należy połączyć z -dacją PRACOWNICY, a następnie dokonać projekcji na atrybut NAZWISKO: R2 = nNAzwisKo(PRACOWNICY*(nE#(ap# = Tr(KONTRAKTY))). ~ "' ' W powyższym wyrażeniu projekcja na atrybut E# nie jest formalnie potrzebna. Została ona zastosowana celem zmniejszenia rozmiaru łączonych relacji. 3.

Podaj numery pracowników, którzy nie biorą udziału w realizacji żadnego projektu.

Zbiór numerów pracowników, o których chodzi w kwerendzie, jest różnicą dwóch zbiorów: zbioru numerów wszystkich pracowników oraz zbioru numerów pracowników uczestniczących w realizacji przynamniej jednego projektu. Oba zbiory otrzymuje się przez zastosowanie operacji projekcji na atrybut E# odpowiednio do relacji PRACOWNICY i do relacji KONTRAKTY: .,, „ ,c, #s = F[E# (PRACOWNICY) - HĘ* (KONTRAKTY). 4.

Podaj numery pracowników biorących udział w realizacji wszystkich projektów.

*. «-,-M.—^v. .

Realizacja tej kwerendy wymaga użycia operacji dzielenia. Dzielną jest relacja zawierająca zbiór powiązanych ze sobą numerów pracowników i projektów, a dzielnikiem zbiór numerów wszystkich projektów. Otrzymujemy: /?4 = nw,E# (KONTRAKT Y) ^ RP* (PROJEKT Y). 5.

Podaj nazwiska pracowników, którzy uczestniczą w realizacji przynajmniej jednego projektu, którego budżet przekracza 100 000.

Dla uzyskania odpowiedzi trzeba wykorzystać wszystkie trzy relacje. Z relacji PROJEKTY należy wybrać te krotki, które spełniają warunek kwerendy, czyli:

** t,** , < : , , - *

-„ ^> i * .

'

KS\ = 100000 (PROJEKTY) . Otrzymaną relację trzeba teraz połączyć z relacją KONTRAKTY. Wcześniej jednak, aby zmniejszyć jej rozmiary, wykonajmy projekcję na atrybut P#:

Po połączeniu z relacją KONTRAKTY otrzymujemy:

. . • -v

..-B ••--£ -s.

#53 = KONTRAKTY * RK .

Spośród atrybutów relacji #53 dla dalszego postępowania istotny jest tylko atrybut E# :

Relacja /?54 zawiera numery poszukiwanych pracowników. Celem znalezienia ich nazwisk konieczne jest jej połączenie z relacją PRACOWNICY: !

R55 = PRACOWNICY * RM .

•/.""*

W relacji /Jss znajduje się odpowiedź. Otrzymujemy ją za pomocą projekcji: ; ,,;,

/?56 — IlNAZWISKO (-^55) •

Ostatecznie otrzymujemy:

Ń ;,

#5 = HNAZWISKO (PRACOWNICY * UE# (KONTRAKTY * Uw (CTBUDŻET> 100000 (PROJEKTY)))) . 6.

Podaj numery pracowników, którzy uczestniczą w realizacji przynajmniej tych projektów, nad którymi pracuje Kowalski.

Znalezienie odpowiedzi wymaga realizacji następujących kroków: 1.

*A

Wyznaczenie numeru pracownika o nazwisku Kowalski: *6i = FU (CTNAZWISKO= -KO**M (PRACOWNICY)) .

2.

Wyznaczenie numerów projektów nad którymi on pracuje:

" ..... ^ ^K-^4^'1 « ,*

• .

RV = nP# (KONTRAKTY * R6r) . 3.

Wyznaczenie wszystkich par P#, E#, w których występują numery projektów znalezione w kroku drugim: *63 = nP#>E* (KONTRAKTY*^).

4.

Wyznaczenie numerów poszukiwanych pracowników:

Ostatecznie otrzymujemy:

,

r/.^r-.-^i, ,v

5l

.,ifp

_ . ,,

R<« = np#,E# (KONTRAKTY * RP* (KONTRAKTY * HĘ* (ONAZWSKO-IC.^*? (PRACOWNICY))) + Hw (KONTRAKTY * UE# (ONAZWTSKO= 'Kowalski' (PRACOWNICY))) . Uwaga 1.

-

Rolę dzielnej mogłaby również pełnić relacja otrzymana w wyniku projekcji relacji KONTRAKTY na atrybuty P#, E# : '" ' A *'« = [lp#, E* (KONTRAKTY).

4*

#63 zawiera krotki związane z Kowalskim, co powoduje, że w odpowiedzi wystąpi również wymieniony parownik. Gdybyśmy chcieli tego uniknąć, należałoby od relacji utworzonej w kroku trzecim odjąć relację określającą Kowalskiego w poszczególnych projektach. Relacja R& przyjęłaby następującą postać: #"63 = rUeł (KONTRAKTY * #« - KONTRAKTY * Podaj numery pracowników, którzy uczestniczą w realizacji przynajmniej jednego projektu, nad którym pracuje - rowyższej kwerendzie zastąpiono zwrot „przynajmniej tych projektów" na „przynajmniej jednego projektu", rcracja dzielenia nie jest teraz konieczna. Algorytm wyszukiwania przebiega podobnie jak przy realizacji kwerendy 5: Wyznaczenie numeru pracownika o nazwisku Kowalski: #71= OE# (^NAZWISKO = 'Kowalski' (PRACOWNICY)) . -. ..* s

2. Wyznaczenie numerów projektów nad którymi on pracuje: , 3L

#72 = HM (KONTRAKTY * #71).

Wyznaczenie tych krotek relacji KONTRAKTY, które dotyczą projektów znalezionych w kroku drugim: "

•

,

" ' '*"

#73 = KONTRAKTY * #72 .

Wyznaczenie numerów poszukiwanych pracowników:

^

łv

#74 ~ H&t (#73) •

Ostatecznie otrzymujemy:

„

,

* * * ł—

,"*f

#7 = nE# (KONTRAKTY * Uw (KONTRAKTY * Hm (CTNAZWBKO=KowdskKPRACOWNIC Y)))) . L waga Podobnie jak w kwerendzie poprzedniej relacja wynikowa zawiera krotki związane z Kowalskim. Celem ich wyeliminowania należy dokonać analogicznej modyfikacji relacji #73, czyli t „l 'H

"

#73 = KONTRAKTY* #72-KONTRAKTY* #71.

43. Język manipulowania danymi SQL

*

.««£-..•...,»

^

,

*

Operatory algebry relacji są zasadniczymi elementami grupy języków manipulowania danymi nazywanych językami algebraicznymi. Drugą grupę tworzą języki oparte na rachunku predykatów. W językach tych definiuje się schemat relacji wynikowej oraz określa warunek, który muszą spełniać krotki tej relacji. Najbardziej popularny obecnie język relacyjnych baz danych - SQL (wcześniej znany jako SEQUEL: Structured English Query Language) - stanowi kombinację cech języków algebraicznych i predykatowych. Został on opracowany przez IBM w laboratorium badawczym w San Jose. Język ten stał się standardem i jest używany w większości komercyjnych systemów [16]. SQL obejmuje: •

Język definiowania danych DDL. Są to instrukcje umożliwiające definiowanie schematów relacji, usuwanie relacji, tworzenie indeksów oraz modyfikowanie schematów relacji.

•

Język manipulowania danymi DML. Są to instrukcje umożliwiające wyszukiwanie danych oraz zmieniające stan bazydanych. «, i _-.K•-••.-;-•*,..-..

•

Osadzony SQL. Celem tej postaci języka jest umożliwienie korzystania z niego w ramach klasycznego języka programowania.

• •

Autoryzacja. SQL DDL umożliwia definiowanie praw dostępu do danych.

T

<

*

Integralność danych. SQL DDL zawiera instrukcje definiujące warunki integralności. Operacje, które je naruszają, są niedozwolone.

45

Kontrola transakcji Istnieją instrukcje blokowania danych, zatwierdzania wykonanej transakcji oraz anulowania wprowadzonych zmian. Podstawową operację w języku SQL stanowi blok SELECT - FROM - WHERE: SELECT Al,A2,...,A, FROM /? 1 , J R 2 ,...,J? m WHERE W

:--, ^ -->KJ-:,.*,:-

•

• r -f «t VM.^ ki _

Po słowie SELECT podaje się nazwy szukanych atrybutów rozdzielone przecinkami. Po słowie FROM występują nazwy relacji, do których należą atrybuty. Słowo WHERE poprzedza formułę logiczną W definiującą warunki, które muszą spełniać wyszukiwane dane. Operację SELECT języka SQL można potraktować jak złożenie algebraicznych operacji selekcji i projekcji, z tą jednak różnicą, że nie następuje tu eliminacja powtórzeń występująca w operacji projekcji. Do eliminacji duplikatów służy operator DISTINCT umieszczany za klauzulą SELECT. Poniżej zostaną przedstawione przykłady zastosowań bazujące na relacjach: PROJEKTY, PRACOWNICY, KONTRAKTY. Przykład 4.9.

1.

Podaj numery pracowników, którzy biorą udział w realizacji co najmniej jednego projektu SELECT DISTINCT E# FROM KONTRAKTY w„,Vi^ ,,„v ,

Użycie słowa kluczowego DISTINCT jest konieczne. Numer pracownika w relacji KONTRAKTY powtarza się, jeśli pracownik bierze udział w wielu projektach. 2.

Podaj numery pracowników, którzy biorą udział w realizacji projektu P l (przykład 4.8 - pytanie 1). SELECT E# FROM KONTRAKTY WHERE P# = 'P1'

-~">; -

...

Numery pracowników biorących udział w realizacji danego projektu nie powtarzają się. W relacji KONTRAKTY nie mogą istnieć krotki o takiej samej wartości atrybutu złożonego P#, E# - klucza głównego relacji. Nie występuje zatem potrzeba eliminacji duplikatów. 3.

Podaj numery projektów w kolejności malejących budżetów. SELECT P# FROM PROJEKTY ORDER BY BUDŻET DESC

n

Klauzula ORDER BY określa uporządkowanie wyników zapytania. ASC oznacza kierunek rosnący, a DESC malejący. Uporządkowanie może być określone za pomocą więcej niż jednego atrybutu. Po klauzuli ORDER BY występuje wtedy lista, której każdy element zawiera nazwę atrybutu oraz określenie kierunku (ASC lub DESC). Porządek sortowania odpowiada kolejności atrybutów. 4.

Podaj pełną informację o wszystkich projektach. SELECT * FROM PROJEKTY

Gwiazdka zastępuje nazwy wszystkich atrybutów relacji PROJEKTY. 5.

Podaj nazwiska pracowników, którzy biorą udział w realizacji projektu Pl (przykład 4.8 - pytanie 2). SELECT NAZWISKO FROM PRACOWNICY WHERE E# IN (SELECT E# FROM KONTRAKTY WHERE P# = 'P1')

46

Wyznaczenie odpowiedzi wymaga wykorzystania relacji KONTRAKTY zawierającej numery pracowników -eałizujących projekty oraz relacji PRACOWNICY, w której znajdują się ich nazwiska. Numer poszukiwanego rracownika musi należeć do zbioru, który można opisać za pomocą bloku SELECT - FROM - WHERE. Operator IN >jpowiada matematycznemu symbolowi e należenia do zbioru. Opis zbioru przyjmuje postać ujętego w nawiasy wyrażenia zwanego podzapytaniem. Odpowiedź na podzapytanie w omawianej kwerendzie nie zależy od wartości występujących w zapytaniu głównym. Takie podzapytanie nazywamy zwykłym. Odpowiedź na omawiane pytanie można także wyrazić za pomocą pytania skorelowanego, którego wynik zależy od wierszy zapytania głównego: -• "• ••!''" - V >•"'<:•:

SELECT NAZWISKO FROM PRACOWNICY WHERE 'Pl' IN (SELECT P# FROM KONTRAKTY WHERE E# = PRACOWNICY.E#)

\

•

•

' - • .,••>. ••: •" - " -

—>

.-,-/> , .,

.-.",

,

4,- - , .-< -x :•.>-. • • - , \ ••>.,;•.

*.

.t

•.-«

Dla każdego pracownika jest tworzony zbiór numerów projektów, nad którymi pracuje. Następnie jest sprawdzany warunek przynależności wyrażony operatorem IN. W przedstawionym rozwiązaniu zastosowano w bloku wewnętrznym jawną kwalifikację do bloku zewnętrznego. Jeżeli odwołanie do atrybutu nie zawiera jawnej kwalifikacji, 10 dotyczy ono relacji z bloku lokalnego (podzapytania). Umieszczenie przed operatorem IN operatora negacji NOT wyraża jego zaprzeczenie (matematyczny symbol 2). Nazwiska pracowników nie biorących udziału w realizacji projektu Pl można wyznaczyć za pomocą następującej itwerendy: SELECT NAZWISKO FROM PRACOWNICY WHERE E# NOT IN (SELECT E# FROM KONTRAKTY WHERE P# = 'P1')

'.•:»' >«•„«-. ".

-

•••-»" -"

. >:

,«,,,., ,'•

.

*I -i • „ . - > . . ,

ą

-,..-j .• r^-ft •h.w* K Ł t

f",«

Klauzula WHERE może również zawierać porównania logiczne oraz konstrukcje: BETWEEN - określenie przedziału wartości atrybutu (np. WYNAGRODZENIE BETWEEN 3000 AND 5000), LIKE - określenie wzorca tekstu (np. NAZWA LIKE 'Fin%' - zostaną wyszukane krotki, w których wartość atrybutu NAZWA zaczyna się od 'Fin') oraz NULL - zbadanie czy wartość atrybutu jest określona (np. WYNAGRODZENIE IS NULL) [16]. Wyrażenia logiczne we frazie WHERE mogą być łączone za pomocą operatorów AND, OR i NOT. 6. Podaj numery pracowników z nieokreślonym wynagrodzeniem. SELECT DISTINCTE# FROM KONTRAKTY WHERE WYNAGRODZENIE IS NULL

,

'

' ' *fi •"*. , '

v

_

*1

... • .T

; , ;-*'-;

Przed słowem NULL można umieścić operator negacji NOT, na przykład dla realizacji kwerendy: „Podaj numery projektów, dla których został ustalony budżet". 7.

Podaj numery projektów, których budżety są większe niż budżet dowolnego projektu realizowanego w Warszawie. * SELECT P# FROM PROJEKTY WHERE BUDŻET > ANY (SELECT BUDŻET , FROM PROJEKTY WHERE MIASTO ='Warszawa')

>.

'^^ . • «,J.u.^--

-'

r- i , ^.. ^

Słowo kluczowe ANY stosuje się przy porównywaniu danej wartości z każdym elementem zbioru stanowiącego odpowiedź na podzapytanie. W zbiorze musi istnieć przynajmniej jeden element spełniający warunek, aby wyrażenie zawierające słowo ANY było prawdziwe. Odpowiada to wyrażeniu logicznemu, w którym zastosowano kwantyfikator szczegółowy.

47

8.

Podaj numery projektów, których budżety są większe niż budżet każdego projektu realizowanego w Warszawie. SELECT P# •;••-•.:... FROM PROJEKTY WHERE BUDŻET > ALL (SELECT BUDŻET * -^ FROM PROJEKTY WHERE MIASTO = 'Warszawa')

. .-

t

,

,-,_,,,

• , -.- . • , «-,j ^„./ , „ , > , ,...„.,-.,,

,

Słowo kluczowe ALL stosuje się przy porównywaniu danej wartości ze wszystkimi elementami zbioru stanowiącego odpowiedź na podzapytanie. Wszystkie elementy zbioru muszą spełniać warunek, aby wyrażenie zawierające słowo ALL było prawdziwe Odpowiada to wyrażeniu logicznemu, w którym zastosowano kwantyfikator ogólny. 9.

Podaj nazwiska pracowników biorących udział w realizacji przynajmniej jednego projektu, którego budżet przekracza 100 000 (przykład 4.8 -pytanie 5). ,, , .... „ ••:,»-<*,

* -. ••=: 1-

SELECT NAZWISKO ^sf, FROM PRACOWNICY WHERE E# IN (SELECT E# FROM KONTRAKTY WHERE P# IN (SELECT P# . .. ,. FROM PROJEKTY WHERE BUDŻET > 100 000))

Podzapytanie może być zawarte w innym podzapytaniu. Mówimy, że podzapytania są zagnieżdżone. 10. Podaj numery pracowników, którzy aktualnie nie pracują nad żadnym projektem (przykład 4.8 - pytanie 3). (SELECT E# FROM PRACOWNICY) EXCEPT (SELECTE# FROM KONTRAKTY)

: : . . , . ^ . . , v. N - . - * , — *

.

'

^-a^i"; ' ". ' '

SQL zawiera operacje na relacjach: UNION, INTERSECT oraz EXCEPT, które odpowiadają operatorom algebry relacyjnej: sumy, iloczynu oraz różnicy. To samo pytanie można także wyrazić następująco: SELECT E#

,

FROM PRACOWNICY WHERE NOT EXISTS . . . (SELECT * FROM KONTRAKTY WHERE E # = PRACOWNICY.Ef)

,.;;:,

. " • _ , - -

Wartością logiczną wyrażenia ( EXISTS podzapytanie ) jest TRUE, jeżeli odpowiedź na podzapytanie zawiera przynajmniej jedną krotkę. 1 1 . Podaj numery pracowników z wykształceniem ekonomicznym, którzy uczestniczą w realizacji projektu Pl . (SELECT E# FROM PRACOWNICY WHERE WYKSZTAŁCENIE = 'Ekonomista') . „,.. „ %-^, INTERSECT (SELECT E# ...,* . , . . . . . . . . • ' , : . , , , ; - -eW ^, =^.. FROM KONTRAKTY -^ .-. ' ' WHERE P# = 'P1') -. , . 12. Podaj numery pracowników z wykształceniem ekonomicznym lub którzy uczestniczą w realizacji projektu Pl.

;pr — ™

(SELECT E # ' . - , < • FROM PRACOWNICY WHERE WYKSZTAŁCENIE = 'Ekonomista') UNION • .' - - •-- • (SELECT E# FROM KONTRAKTY WHERE P# = 'Pl')

v. ;

^-

(]

,

, j .,

. ,, f ,

- ti

* , ' . . • j H<*

D. Dla każdego realizowanego projektu podaj jego numer oraz wykształcenie pracowników biorących udział w jego realizacji. ,, .-^ SELECT DISTINCT P#, WYKSZTAŁCENIE ,-~ • ^ FROM KONTRAKTY, PRACOWNICY WHERE KONTRAKTY.E# = PRACOWNICY.E# ;

- , ,.-

,,, r

, -,„,r„ ,.-„« ,,-,.,„„.

W klauzuli FROM może wystąpić kilka relacji. W klauzulach SELECT oraz WHERE mogą być one użyte jako , kwalifikatory. W pytaniu tym zostały połączone dwie relacje: KONTRAKTY i PRACOWNICY względem wspólnego •ybutu E# (operacja złączenia w algebrze relacji). -,;. - - - , , •• v « . « ^ •*. *»x, J ' • ,, - , -s ,1 M. Podaj nazwiska pracowników, którzy biorą udział w realizacji projektu P l. SELECT NAZWISKO

- '•

u

•" ^,

FROM KONTRAKTY X, PRACOWNICY Y WHERE X.E# = Y.E# AND X.P# = 'P1'

-

„ -

%

P-

,^

Zadanie to zostało już przedstawione wcześniej (pytanie 5.). W powyższym rozwiązaniu zastosowano zmienne siatkowe (inne nazwy to alias, etykieta tabelowa, synonim). Występują one w klauzuli FROM za każdą nazwą relacji w jdfcgłości co najmniej jednej spacji. Zmienne krotkowe stosuje się do odróżniania poszczególnych wystąpień relacji wymienionych w klauzuli FROM. « « ł*^ , , ,t r

15. Podaj nazwiska pracowników starszych od Kowalskiego.

*«

SELECT Y.NAZWISKO - : FROM PRACOWNICY X, PRACOWNICY Y WHERE X.NAZWISKO ='Kowalski'AND X. WIEK < Y.WIEK

„^

. . .,-

,

. , . , . ,

ff

Relacja może być łączona sama ze sobą. Złączenie następuje według atrybutu WIEK. W ten sposób z krotką X oznaczającą pracownika Kowalskiego są łączone krotki oznaczające pracowników starszych od niego. 16. Podaj numery pracowników biorących udział w realizacji więcej niż jednego projektu. SELECT DISTINCT E# FROM KONTRAKTY X WHERE E# IN (SELECT E# FROM KONTRAKTY WHERE P#oX.P#)

'* -

',

.,«;.,

, ?

* ^ .«, ,

',

. .

*

,. „»

,.-,,,,

. , . .»,» ~^- ^ '"'" , ^r-ur^-ł r -

Podzapytanie definiuje zbiór numerów pracowników uczestniczących w realizacji projektów, których numery są różne od wartości P# z krotki bloku zewnętrznego. Jeśli zbiór ten zawiera numer pracownika z krotki bloku zewnętrznego, to numer ten należy do odpowiedzi. W SQL istnieją operatory agregowania służące do wykonywania obliczeń na zbiorach danych. Są to: • • • • •

MAX - wyznaczanie maksymalnej wartości; MIN - wyznaczanie minimalnej wartości; AVG - wyznaczanie wartości średniej; SUM - wyznaczanie sumy wartości; COUNT - wyznaczanie liczby krotek.

' '- '

17. Podaj wysokość maksymalnego wynagrodzenia dla projektu Pl .

'•'•*

---.!f • ';",-v.

ft

SELECT MAX (WYNAGRODZENIE) FROM KONTRAKTY WHERE P# = 'P1'

- «•'•>*.-.,-.;-•*'

/'..

18. Podaj liczbę wszystkich projektów. • V"O#.,T:

SELECT COUNT (*) FROM PROJEKTY

-ł-, ; ,

Wynikiem kwerendy jest ilość krotek relacji PROJEKTY. 19. Podaj liczbę pracowników biorących udział w realizacji przynajmniej jednego projektu. SELECT COUNT (DISTINCT E#) FROM KONTRAKTY Użycie słowa kluczowego DISTINCT jest konieczne, ponieważ dany pracownik może uczestniczyć w realizacji wielu projektów i odpowiadające mu krotki mogą wystąpić wielokrotnie. Liczba krotek relacji KONTRAKTY może zatem różnić się od liczby pracowników. * „"!"•

; ».-

, "»«,<,

„»• - •TłfŁ^,* ,v ". i";£-«.—"*

20. Podaj liczbę pracowników biorących udział w realizacji projektu Pl. SELECT COUNT (*) ^ FROM KONTRAKTY WHERE P# = 'P1'

^ -: -

* * i:\*~ i •' ' ' " ' - '

.

' . • ' . '

-'

-,

~

21. Podaj sumę wynagrodzeń wszystkich pracowników biorących udział w realizacji projektu Pl. SELECT SUM (WYNAGRODZENIE) FROM KONTRAKTY WHERE P# = 'P1'

,«-v-V.- - , - • < •

-,-...•,,

22. Podaj łączne wynagrodzenie wszystkich informatyków biorących udział w realizowanych projektach.

-•

SELECT SUM (WYNAGRODZENIE) FROM KONTRAKTY WHERE E# IN (SELECT E# - . •>- FROM PRACOWNICY WHERE WYKSZTAŁCENIE = 'Informatyk')

- ,• -.. ... ,. ..-.--^

...

.,

*,. . (.

Działanie operatora SUM obejmuje zbiór krotek, dla których wartość atrybutu E# należy do zbioru wyznaczonego przez podzapytanie. 23. Podaj numery pracowników pracujących nad projektem Pl, których wynagrodzenie jest najwyższe. SELECT E# ' ' -; - '' • / - ^J-", kśv „ • FROM KONTRAKTY WHERE P# = 'Pl1 AND WYNAGRODZENIE = (SELECT MAX (WYNAGRODZENIE) FROM KONTRAKTY WHERE P# = 'Pl') ~

. " - ->'. - ,: , .ttóm^^yy

Termin ,/iajwyższe wynagrodzenie" oznacza najwyższą wartość w ramach projektu Pl. Podzapytanie bez frazy WHERE oznaczałoby wybór najwyższej wartości spośród wynagrodzeń dotyczących wszystkich projektów. 24. Dla każdego realizowanego projektu podaj jego numer i liczbę pracowników biorących udział w jego realizacji. SELECT P#, COUNT (E#) FROM KONTRAKTY GROUP BY P#

zastosowaniu klauzuli GROUP BY relacja KONTRAKTY została podzielona na grupy z tą samą wartością go atrybutu (w tym przypadku P#). Wartość funkcji COUNT jest obliczana oddzielnie dla każdej grupy, |25, Podaj numery pracowników biorących udział w realizacji więcej niż jednego projektu (pytanie 16). : SELECT E# " FROM KONTRAKTY GROUP BY E# HAYING COUNT (*)> l

"""^ ' ""

r

'

'' -iMW« NJ;, : .

v

,

-

a

" 'A!Sv ^f ,„-,'

;

li GROUP BY często towarzyszy klauzula HAYING. Zawiera ona predykat odnoszący się do grup wierszy (jest riednikiem frazy WHERE dla grup wierszy). W powyższym pytaniu predykat ten zawiera funkcję COUNT, której cią jest liczba krotek w każdej grupie. Jeśli grupa posiada więcej niż jedną krotkę, jest akceptowana i odpowiedni •HBCT pracownika należy do odpowiedzi. '. - Podaj numery pracowników, którzy uczestniczą w realizacji przynajmniej jednego projektu, nad którym pracuje Kowalski (przykład 4.8 - pytanie 7). SELECT DIST1NCT E# i- : FROM KONTRAKTY WHERE P# IN (SELECT P# ' > ' FROM KONTRAKTY WHERE E# IN " ' " ' " "' •• •"<-' (SELECT E# FROM PRACOWNICY WHERE NAZWISKO = 'Kowalski')) .v ;

<

' " J ^H, " •=.--:' 4 -c'4 »••<:-,> " * . i-ł

' '- -' v,

'„-.v, ,„••;„

:.

Celem zwiększenia szybkości wyszukiwania informacji na wybranych atrybutach można zakładać indeksy. ~ukcja: CREATE INDEX WIELKOŚĆ ON PROJEKTY (BUDŻET) ,. _v

,.„, , ^ ,.,, v ., t ^ ,

f

definiuje indeks o nazwie WIELKOŚĆ dla relacji PROJEKTY na atrybucie BUDŻET. Indeksy mogą być tworzone na więcej niż jednym atrybucie. Istnienie indeksów spowalnia jednak wykonywanie operacji zmieniających stan bazy dnych. Wybór indeksowanych relacji powinien zostać poprzedzony analizą najczęściej zadawanych pytań oraz częstości zmian. Do usuwania indeksów służy instrukcja DROP INDEX. Omówione zapytania ilustrują zastosowanie SQL przy wyszukiwaniu danych. Język ten posiada również - echanizmy umożliwiające dokonywanie zmian zawartości bazy danych - polecenia INSERT, DELETE i UPDATE
Wprowadź do relacji PRACOWNICY informację o nowym pracowniku.

.

t

-

.'

,

-,*,&*•£>•<*

INSERT INTO PRACOWNICY (E#, NAZWISKO, WYKSZTAŁCENIE, WIEK) '"' YALUES CE21','Sobolewski','Informatyk', 32) , , <:, Jeżeli lista za nazwą relacji zawiera wszystkie jej atrybuty, to można ją pominąć. Porządek wartości w klauzuli VALUES musi być zgodny z kolejnością atrybutów relacji. Jeżeli wprowadzane wartości dotyczą tylko wybranych atrybutów, to pominiętym atrybutom są przypisywane wartości domniemane, określone w definicji relacji. Najczęściej >est to wartość pusta NULL. Ma ona charakter tymczasowy, to znaczy istnieje, gdy wartości poszczególnych atrybutów nie są jeszcze znane. , ,, % 5 2.

Wprowadź do relacji PROJJOO (PJ, NAZWA, BUDŻET, RODZAJ, PRIORYTET, MIASTO) informacje o tych projektach z relacji PROJEKTY, których budżet przekracza 100 000 PLN. , __ 4 INSERT INTO PROJJOO ...... SELECT P#, NAZWA, BUDŻET, RODZAJ, PRIORYTET, MIASTO FROM PROJEKTY WHERE BUDŻET > 100 000 •>• ~t--j..- >*, „ •-, v , „ ; - , ' > . «c

-,,

* ^ „

Zadanie polega na przepisaniu odpowiednich krotek relacji PROJEKTY do relacji PROJ_100. Zbiór kopiowanych krotek zdefiniowano za pomocą kwerendy. Do usuwania informacji z bazy danych służy operacja DELETE. Usuwać można tylko pełne krotki. .^-..^y.J^.^f,

'"

-.,:. i.-^f.r,

, ,.,,„ ,, ,:,v , „ „^ ^, . ^„^ ^.^

rfax

.j^-f^ s, . .f'ff,t •

Przykładali. 1.

Usuń krotki relacji KONTRAKTY. DELETE FROM KONTRAKTY

2.

*a T

V s

.. l -: j- •> ttucJO i>---

Usuń z relacji PROJEKTY krotki dotyczące projektów, których budżet przekracza 1 00 000 PLN. DELETE FROM PROJEKTY WHERE BUDŻET > 1 00 000

3.

"s

Usuń z relacji KONTRAKTY wszystkie krotki dotyczące projektów, których budżet przekracza 100 000 PLN. DELETE FROM KONTRAKTY WHERE P# IN (SELECT P# FROM PROJEKTY WHERE BUDŻET > 1 00 000)

'

"

' '; '

* '«

,.,',,,

Aktualizację danych przeprowadza się za pomocą operacji UPDATE. Przykład 4.12. 1.

Zwiększyć wartości atrybutu BUDŻET w relacji PROJEKTY o 10%.

UPDATE PROJEKTY SET BUDŻET = BUDŻET * 1.1 2.

,.

~ ~

•

..^X-. -. -

Zwiększyć o 10% wynagrodzenia pracowników biorących udział w realizacji projektu Pl, jeśli nie przekraczają one 1000 PLN. , '" t

UPDATE KONTRAKTY ~. SET WYNAGRODZENIE = WYNAGRODZENIE* 1.1 WHERE WYNAGRODZENIE < 1000 AND P# = T l 1

>

- - •-, • •r .-'•" -L

*„. *" .-^ ,

Wszystkie relacje znajdujące się w bazie danych muszą zostać wcześniej zdefiniowane za pomocą instrukcji CREATE TABLE. Instrukcja ta może zawierać opcje definiujące warunki integralności, które stanowią zabezpieczenie przed niedozwolonymi zmianami. Do modyfikacji definicji służy instrukcja ALTER TABLE, a do usuwania relacji instrukcja DROP TABLE. Przykład 4.13. 1.

a

Utwórz relację KONTA z atrybutami: NUMER, NAZWISKO, DATA, TYP, PROCENT i SALDO oraz ustal atrybut NUMER kluczem głównym. J

' "

,, ń

l ^

CREATE TABLE KONTA (NUMER INTEGER NOT NULL, NAZWISKO CHAR (20), DATA DATĘ, TYP INTEGER, PROCENT DECIMAL (4,2), SALDO FLOAT, PRIMARY KEY (NUMER))

t *i; '

t- ' \<

~

'r'

-

,

/

'

.

f

: - "

•••• • J

-' "i

' •• •"

Ł

"

. ,

;

- , ' • - ' --.,-. .„>« M ~ * . - X - .;

-

' - » : * .

Do typów danych, które mogą występować w instrukcji CREATE należą: • • •

CHAR (n) - typ znakowy o stałej długości; YARCHAR (n) - typ znakowy o zmiennej długości, gdzie liczba n oznacza maksymalną ilość znaków; INTEGER - typ całkowity; SHORTINT - podzbiór typu całkowitego zależny od implementacji; ,«

DECIMAL (p, d) - typ numeryczny, gdzie p oznacza całkowitą ilość cyfr, a d - ilość cyfr po kropce oddzielającej część całkowitą od ułamkowej; ., ,. , ...... , , , , REAL - typ rzeczywisty zmiennopozycyjny; FLOAT - to samo co REAL; DOUBLE PRECISION - typ rzeczywisty podwójnej dokładności; • - . •«- - , t A^ BIT (n) - ciąg bitów o długości n; BIT YARYING (n) - ciąg bitów o długości co najwyżej n; DATĘ -typ dla określania daty, zawierający rok, miesiąc i dzień, oddzielone myślnikiem, np. 1999-12-29; TIME - typ dla określania czasu, zawierający godzinę, minutę i sekundę, oddzielone dwukropkiem, np. 11:07:25; Atrybuty typu DATĘ oraz TIME mogą być porównywane w zwykły sposób, to znaczy za pomocą operatorów nżywanych przy porównywaniu atrybutów liczbowych oraz znakowych. Zapis D ATA l < DATA2 oznacza, że wartość trybutu DATA1 jest datą wcześniejszą od wartości atrybutu DATA2. Porównywanie atrybutów typu TIME jest malogiczne. • •- - -,,- ,-< . Ł » : Dodaj do relacji KONTA atrybut PEŁNOMOCNIK.

-'i' '

ALTER TABLE KONTA ADD PEŁNOMOCNIK* INTEGER .:

••*" *

- •

' • > i,-;*- - -- -•• -.*•

Usuń relację KONTA. DROP TABLE KONTA

'-*^ „:.,'.

" ,4-

•-,,,-.;

Zwróćmy uwagę na różnicę między operacjami: DROP TABLE KONTA oraz DELETE FROM KONTA, Drugie polecenie usuwa wszystkie krotki z relacji KONTA. Definicja relacji zostaje jednak zachowana i można do niej wprowadzać nowe krotki. Operacja DROP TABLE natomiast powoduje usunięcie nie tylko zawartości relacji, lecz także definicji jej schematu. Nowe krotki do relacji KONTA można będzie wprowadzać dopiero po ponownym jej zdefiniowaniu za pomocą instrukcji CREATE TABLE. Oprócz klucza głównego (wiersz PRIMARY KEY w relacji KONTA) można także definiować klucze obce. Załóżmy, że atrybut PEŁNOMOCNIK* w relacji KONTA przyjmuje wartości klucza głównego PK# relacji KLIENCI, w której są opisani wszyscy klienci banku. Powiązanie takie definiuje się przez dodanie wiersza: \t i " FOREIGN KEY PEŁNOMOCNIK* REFERENCES KLIENCI (PK#). Wartości atrybutu można narzucić umieszczając w jego definicji, po słowie kluczowym CHECK, warunek, który -nuszą one spełniać, na przykład: '•"<-

*

"

"f

>

"

.."-.-••-

PROCENT INTEGER CHECK (PROCENT > 0) . Innym rozwiązaniem jest zdefiniowanie dziedziny atrybutu za pomocą instrukcji CREATE DOMAIN: CREATE DOMAIN OPROCENTOWANIE INTEGER CHECK (YALUE > 0)

" . - * . * *

* *"

• '• , i "

*

umieszczenie w definicji relacji KONTA wiersza: -~ -'-i

PROCENT OPROCENTOWANIE.

• ł -

-

r;,,-',-,

, r ^

n

.,

' . -'

,

Bardziej złożone warunki definiuje się za pomocą asercji zwanych także więzami głównymi [15]. •i- --s»*n <-*55:..> r^VN*J!'? -£s.*a^,~;.;

Przykład 4.14. Dla bazy danych biura projektów zdefiniuj następujący warunek: łączna liczba zatrudnionych prawników nie może przekraczać 10 Definicję asercji zapisuje się za pomocą instrukcji CREATE ASSERTION: CREATE ASSERTION PRAWO . CHECK (10 >= SELECT COUNT (*) FROM PRACOWNICY WHERE WYKSZTAŁCENIE ='Prawnik')

-

• - -

Innym aspektem ochrony danych jest zabezpieczenie przed nielegalnym dostępem. Administrator bazy danych ma możliwość przydzielania użytkownikom uprawnień pozwalających na wykonywanie poszczególnych operacji. Są one nadawane za pomocą instrukcji: GRANT listajpraw ON nazwa_relacji TO listajużytkowników .-*<

.-.- 1.. . •

Użytkownicy są rozpoznawani przez swoje identyfikatory. Instrukcja może zawierać frazę WITH GRANT OPTION, która umożliwia użytkownikowi przekazywanie posiadanych uprawnień innym użytkownikom. Do odwoływania uprawnień służy instrukcja REYOKE: REYOKE listajpraw ON nazwa jrelacji FROM listaj Przykład 4.15.

•- ••-«••--» . i r , _w -<«-.;^ „.

.,,--,_

Przydzielić użytkownikowi o identyfikatorze Kowal prawa INSERT i SELECT do relacji PRACOWNICY. GRANT INSERT, SELECT ON PRACOWNICY TO Kowal WITH GRANT OPTION

4.4. Perspektywy

0

^

Termin perspektywa odnosi się do każdej relacji nie należącej do modelu konceptualnego, która jest widziana przez użytkownika. Perspektywa jest więc „relacją wirtualną". Nie zawiera żadnych danych fizycznych. Perspektywy uwzględniają wymagania użytkowników, ich sposób widzenia danych. Są także formą ochrony danych. Do zdefiniowania perspektywy służy instrukcja CREATE YIEW. Definicja zawiera nazwę perspektywy oraz odpowiednią kwerendę. Przykład 4.16.

•

•

-*

,^t.

,

:=

Zdefiniuj perspektywę dotyczącą projektów realizowanych w Warszawie. CREATE YIEW PROJWAR AS SELECT * FROM PROJEKTY WHERE MIASTO ='Warszawa'

• :

-

, •

*

«-»»,-

*

t

• ....

-^ • ,

Atrybuty perspektywy PROJWAR mają takie same nazwy jak atrybuty relacji PROJEKTY. Jeżeli istnieje potrzeba zmiany nazw, to nowe nazwy należy umieścić w instrukcji CREATE YIEW za nazwą perspektywy. Żądaną perspektywę można zdefiniować w następujący sposób: ,

'• *

CREATE YIEW PROJWAR_BIS AS (PROJEKT_NR, TYTUŁ, TYP, KWOTA, RANGA, MIEJSCE) SELECT* v ! „-..,.^, ... l ^ f c s w t . l .,. FROM PROJEKTY 1 WHERE MIASTO ='Warszawa

Perspektywy można wykorzystać do definiowania innych perspektyw, a także do wyszukiwania danych. W zapytaniach nazwy perspektyw mogą występować wszędzie tam, gdzie występują nazwy relacji. Za pośrednictwem perspektywy PROJWAR można wyszukiwać krotki relacji bazowej PROJEKTY, które spełniają warunek MIASTO = 'Warszawa'. Dwukrotne wykonanie takiej samej kwerendy odwołującej się do perspektywy może dać różne wyniki, jeśli relacja bazowa zostanie w międzyczasie zmodyfikowana. Przykład 4.17. Na podstawie perspektywy PROJWAR możemy znaleźć numery projektów realizowanych w Warszawie, których budżet przekracza 100000: .- .-. .-••..*-., -. •, . , „,,,-,. l f* t;* ' 3 > J $•",, 11 Jf f»' " Jt ** *r SELECT P# FROM PROJWAR WHERE BUDŻET > 100 000

- -..-=

... •

.

,i]V

, . , , - " "

Wyznaczenie odpowiedzi na kwerendę wykorzystującą perspektywę wymaga jej przekształcenia do postaci zawierającej relację bazową. Transformacje takie są wykonywane przez SQL. Dla zapytania z przykładu 4.17

54

transformacja polega na dołączeniu warunku MIASTO = 'Warszawa' oraz zastąpieniu nazwy perspektywy nazwą relacji bazowej: , 1

SELECT P#

'

-.•"• li łZ-i1 V

ł**

x

«l/'.U'ł « '

"

-

'.

*

J '

'

FROM PROJEKTY WHERE BUDŻET> 100000 AND MIASTO ='Warszawa'

.-','•

""

"C-:ir*=w.

-'*

—-..-!•...,

,," -',",:

. '. •

Trudniejszy problem stanowią operacje modyfikujące dane za pośrednictwem perspektyw. Trudności są związane z koniecznością wyrażenia tych operacji za pomocą relacji istniejących w bazie danych. Powoduje to pewne ograniczenia. •.AfiŁV *;': tfi:-ii.mti

*"i*iY"1! j:4 Vffv. "V-) -ji-..-Ji .'J- • ,

r

Przykład 4.18.

.

*

: -^

,

,

.

.

•

r.« •«>

-

?

.. v , - . -?

^ :*4-'

Utwórz perspektywę dotyczącą projektów z pominięciem atrybutów BUDŻET, PRIORYTET i MIASTO. CREATE VJEW PROJEKTY_MIN AS SELECT P#, NAZWA, RODZAJ FROM PROJEKTY

^ ^ , / ' * ' '"''

•

...

-

W operacji INSERT wykorzystującej perspektywę PROJEKTY_MIN nie można podać wartości atrybutów BUDŻET, PRIORYTET i MIASTO. We wprowadzanej do relacji PROJEKTY krotce pominiętym atrybutom zostaną przypisane wartości domniemane. Bardziej złożony problem powstaje, gdy w definicji perspektywy występuje kilka relacji. Przykład 4.19. Rozpatrzmy następującą perspektywę:

«''/*•

CREATE VIEW WYMAGANIA AS • «-*" • t- • * ----- SELECT P#, WYKSZTAŁCENIE FROM KONTRAKTY, PRACOWNICY WHERE KONTRAKTY.E# = PRACOWNICY.E# Wykonanie operacji:

,„•...,=

•

INSERT 1NTO WYMAGANIA YALUES ('P21,'Prawnik') wymagałoby wprowadzenia do relacji KONTRAKTY krotki ('P21, NULL, NULL) oraz do relacji PRACOWNICY krotki (NULL, NULL, 'Prawnik', NULL). Atrybut E# w obu krotkach przyjąłby więc wartość NULL. Występujący w definicji perspektywy warunek KONTRAKTY.E# = PRACOWNICY.E# łączący relacje KONTRAKTY i PRACOWNICY nie byłby spełniony dla nowo wprowadzonych krotek, ponieważ wynik porównania, w którym uczestniczy wartość NULL jest nieokreślony (wartość UNKNOWN). Odpowiedź na zapytanie: SELECT * FROM WYMAGANIA

v»

nie zawierałaby więc ostatnio wprowadzonej krotki ('P2', 'Prawnik'). Modyfikacja danych za pośrednictwem perspektyw zdefiniowanych za pomocą więcej niż jednej relacji jest niedozwolona.

4.5. Osadzony SQL Pisanie kwerend w języku SQL jest łatwiejsze niż ich kodowanie w klasycznym języku programowania. Kwerendy są jednak tylko jednym ze składników programów użytkowych. Pozostałe elementy aplikacji muszą być napisane w klasycznym języku programowania. Ponadto nie wszystkie zapytania do bazy danych można wyrazić w SQL. Powstaje więc potrzeba dostępu do bazy danych z poziomu języka programowania. W tym celu kwerendy SQL „zanurza się" w klasycznym języku programowania zwanym językiem macierzystym. Struktury SQL dopuszczalne w języku macierzystym tworzą osadzony SQL (ang, embedded SQL). Program użytkowy zawierający instrukcje SQL jest analizowany przez preprocesor. Osadzone wyrażenia SQL są zastępowane wyrażeniami języka macierzystego. Następnie program użytkowy jest kompilowany. Osadzone instrukcje są poprzedzone frazą EXEC SQL :

55

l EXEC SQL =.-.._

n^-^t,

Do przekazywania wartości miedzy SQL i językiem macierzystym służą kursory. Deklaracja:

EXEC SQL DECLARE C CURSOR FOR SELECT P#, BUDŻET FROM PROJEKTY WHERE BUDŻET >:S

,

-- *, ..H , .

definiuje kursor o nazwie C, którego zakresem jest relacja z atrybutami P# oraz BUDŻET. Relacja ta zawiera krotki odpowiadające projektom o budżetach przekraczających wartość S, gdzie 5 jest zmienną języka macierzystego. Zmienne używane zarówno języku macierzystym, jak i w SQL nazywa się dzielonymi [15]. W instrukcjach SQL są one poprzedzone dwukropkiem. Do otworzenia i zamknięcia kursora służą instrukcje: EXEC SQL OPEN

oraz

EXEC SQL CLOSE

Wartości wyznaczane przez kwerendę stają się dostępne za pomocą instrukcji: EXEC SQL FETCH FROM INTO Instrukcja FETCH wymaga po jednej zmiennej dla każdego atrybutu. Po jej wykonaniu zmiennym zostaną przypisane znalezione wartości atrybutów. W ten sposób wartości krotek stają się dostępne w programie. Dla zdefiniowanego wyżej kursora C należy zastosować następującą instrukcję: EXEC SQL FETCH FROM C INTO :PR_NUM, PRJBUD Instrukcja FETCH zwraca tylko jedną krotkę i przesuwa kursor do następnej. Po otwarciu kursor jest ustawiony na pierwszej krotce. Jeżeli są wymagane wszystkie krotki, to przetwarzanie zakresu kursora musi odbywać się w pętli. Przykład 4.20.

* , .\ „

Obliczyć sumę budżetów projektów realizowanych w Warszawie.

;i?pife'SXifrir

Definicja kursora:

Ą:l
EXEC SQL DECLARE C CURSOR FOR SELECT BUDŻET FROM PROJEKTY WHERE MIASTO = 'Warszawa1 Przetwarzanie kursora: suma = 0; while NOT KONIECJCURSORA {

• «. ^

EXEC SQL FETCH FROM C INTO :pr_bud; suma = suma + pr_bud;

» . - ^ c <*„ \ .»

^sr,

}

KONIECJCURSORA oznacza procedurę badającą czy został osiągnięty koniec zakresu kursora. Przy jej tworzeniu wykorzystuje się zmienne systemowe.

4.6. Projektowanie modelu relacyjnego na podstawie modelu związków encji Model bazy danych w postaci diagramów związków encji może zostać przekształcony na zbiór relacji. Każdemu zbiorowi encji oraz związków encji odpowiada relacja z odpowiednimi atrybutami i kluczem głównym. Proces transformacji nie jest trudny. W tym punkcie zostaną opisane przekształcenia poszczególnych elementów modelu związków encji na relacyjny model danych. Reprezentacją zbioru encji silnych jest relacja, której schemat składa się z atrybutów zbioru i której kluczem głównym jest klucz główny zbioru.

56

Do przedstawienia związku wiele-do-wielu miedzy dwoma zbiorami encji A i B (rys. 4.9) potrzebne są trzy relacje: dwie dla zbiorów encji i jedna dla związku między nimi. Klucz główny relacji AB opisującej związek składa się z kluczy głównych zbiorów A i B. Ponadto do schematu relacji AB należą atrybuty powiązań - atrybut C. Dla diagramu z •ysunku 4.9 otrzymujemy więc następujące relacje: A(Ą,,A 2 , ... ,A„),

B(B,,B2, ... ,Bm),

AB (A,,B,,C) .

W ogólnym przypadku, gdy w związku występuje więcej zbiorów, klucz główny relacji przedstawiającej związek składa się z kluczy głównych wszystkich zbiorów, które w nim uczestniczą.

Powiązanie hierarchiczne między zbiorami encji A (zbiór nadrzędny) oraz B (zbiór podrzędny) (rys. 4.10) można przedstawić za pomocą relacji o dwóch atrybutach A\ oraz B\ - kluczy głównych obu zbiorów. Jej kluczem jest Bt, gdyż zgodnie z definicją związku hierarchicznego, encji podrzędnej odpowiada dokładnie jedna encja nadrzędna. Identyfikator encji nadrzędnej można więc włączyć do schematu relacji przedstawiającej zbiór B. Model związku hierarchicznego składa się zatem z dwóch relacji reprezentujących powiązane zbiory, pr/y czym schemat relacji dla zbioru podrzędnego zawiera klucz główny zbioru nadrzędnego. Diagramowi z rysunku 4.10 odpowiadają następujące relacje:

Jeżeli powiązanie nie jest ściśle hierarchiczne, to znaczy encja ze zbioru B może nie być związana z żadną encją ze zbioru A, atrybut A\ relacji B może przyjmować wartości puste. Inne rozwiązanie polega na przekształceniu diagramu związków encji jak w przykładzie 3.5. Liczba relacji modelujących związki uname (rys. 4.11) zmniejsza się o jeden. Występuje tu bowiem tylko jeden zbiór encji. Dla związku wiele-do-wielu otrzymujemy relacje:

gdzie relacja A reprezentuje zbiór encji, a relacja R związek unarny. Jawna kwalifikacja jest konieczna do określenia roli spełnianych przez atrybuty kluczowe relacji R. Na rysunku 4.11 role zostały oznaczone przez E\ i E2. Przykładem związku unarnego wiele-do-wielu jest związek między częściami i ich składnikami. Każda część występuje w dwóch rolach: zawiera inne części oraz jest składnikiem innych części. Atrybuty E\A\ oraz £2-^i oznaczają odpowiednio składnik oraz część nadrzędną.

Model związku ISA (rys. 4.13) zawiera relacje z takimi samymi kluczami głównymi: • •

A(Ai, A2, ... , A„) - zbiór encji nadrzędnych; B (A,, B,, B2, ... , B,,,) oraz C (A,, C b C2, ... , C„) - zbiory encji podrzędnych.

<

^

A

.,..:.

;,;,;

Jeżeli przynależność w związku ISA jest rozłączna, to rozwiązanie można zmodyfikować bez wprowadzania redundancji przez umieszczenie atrybutów A2, ... ,AB-w schematach relacji B i C: . .

1

A (A,,Aa, ... ,A„); B'(Ą,,A 2 , ... , A,,81,62, - ,B,„) oraz C(A.,,A2, ... ,An,C,,C2, ... ,Cp). ;-,„,,;-

Krotki relacji A' opisują te encje, które nie należą do żadnego ze zbiorów B lub C. Zakłada się więc przynależność częściową. Przy przynależności całkowitej relację A' można usunąć, gdyż jest ona redundantna. Każda encja jest bowiem całkowicie opisana w jednej z relacji ff lub C.

-,

,i

» ,

S

s *

l"

v,

* .

-r> y.* tj *.,- ; j"

: • - >» !

.,* łL-:»; /^

59

5. Normalizacja relacji

Podczas projektowania relacyjnej bazy danych powstaje problem odpowiedniego wyboru różnych schematów relacji. Właściwy projekt powinien zapewnić możliwość zapisywania danych bez redundancji oraz łatwego wyszukiwania żądanych informacji. Najważniejszą metodą prowadzącą do uzyskania projektu o korzystnych właściwościach jest procedura normalizacji. Polega ona na projektowaniu relacji w odpowiednich postaciach normalnych. Do określenia czy relacja znajduje się w jednej ze zdefiniowanych postaci normalnych potrzebne są dodatkowe informacje o modelowanym wycinku rzeczywistości. Są to nałożone na dane więzy zwane zależnościami funkcyjnymi (sng.functional dependencieś). Muszą one zostać zidentyfikowane podczas projektowania. Błędnie zaprojektowane bazy danych posiadają niepożądane właściwości. Ich ilustracją jest następujący przykład: Przykład 5.1. Rozważmy relację UMOWY przedstawioną na rysunku 5.1. Jej schemat powstał w wyniku rozszerzenia schematu relacji KONTRAKTY z przykładu 2.1 o atrybuty NAZWA, BUDŻET, RODZAJ, PRIORYTET i MIASTO. Klucze główne obu relacji są takie same. ,

UMOWY

p#

E#

NAZWA

BUDŻET

RODZAJ

Pl

El E2 E6 E7 E10 E18 E20 E4

Kredyt Kredyt

110000 110000

Bankowość Bankowość

Warszawa Warszawa

1000 1000

Kredyt

110000

Bankowość

Warszawa

2000

Kredyt

110000

Bankowość

Warszawa

1000

Kredyt

110000

Bankowość

Warszawa

4000

Kredyt

110000

Bankowość

Warszawa

2000

Kredyt

110000

Bankowość

Finn

50000

Rachunkowość

P2 P2 P2 P3 P3 P3 P3 P4

E9 E10 E14 E2 E3

Firm

50000

Rachunkowość

Finn

50000

Rachunkowość

Pl Pl Pl Pl Pl

Pl

P2

PRIORYTET

MIASTO

WYNAGRODZENIE

Warszawa

6000

3 3 3 3 4 4 4 4 2

Łódź

5000

Łódź

8000

Łódź

3000

Łódź

4000

Łódź

7000

Łódź

5000

Łódź

3000

Łódź

1000

Poznań

2000

2

Poznań

4000

2

Poznań

1000

2

Poznań

4000

Finn

50000

Rachunkowość

Polisa

40000

Ubezpieczenia

Polisa

40000

Ubezpieczenia

E6 E8 El

Polisa

40000

Ubezpieczenia

Polisa

40000

Makler

30000

P4

E4

Makler

30000

P4

E6

Makler

30000

P4

E18

Makler

30000

Ubezpieczenia Rynek kapitałowy Rynek kapitałowy Rynek kapitałowy Rynek kapitałowy

P4

E19

Makler

30000

Rynek kapitałowy

2

Poznań

2000

P5 P5 P5

El E2 E19

Visa

200000

Bankowość

Kraków

2000

Visa

200000

Bankowość

Visa

200000

Bankowość

1 1 1

Kraków

1000

Kraków

8000

Rys. 5.1. Relacja UMOWY z przykładu 5.1

60?

Zauważmy, że relacja UMOWY powstała w wyniku złączenia relacji KONTRAKTY i PROJEKTY względem atrybutu c ?=. Model danych dla biura projektów wykorzystujący relację UMOWY zawiera redundancję. Informacje o projekcie « powtarzane wielokrotnie. Ilość powtórzeń jest równa liczbie pracowników uczestniczących w jego realizacji. xiczas wykonywania operacji zmieniających zawartość bazy danych występują następujące anomalie: ^ •

Każda aktualizacja danych projektu wymaga przejrzenia całej relacji celem znalezienia wszystkich krotek, które go opisują i dokonania odpowiednich zmian. W przeciwnym razie relacja będzie zawierać sprzeczne dane.

•

Do relacji UMOWY nie można wprowadzić informacji o projekcie przed przypisaniem do niego przynajmniej jednego pracownika.

•

Usuniecie z relacji UMOWY jedynej krotki dotyczącej danego projektu powoduje utratę informacji o tym \ projekcie. r

•lożna je wyeliminować, jeśli zamiast relacji UMOWY zastosujemy relacje o innych schematach. Przy ich : rojektowaniu należy uwzględnić zależności funkcyjne między atrybutami.

5.1. Zależności funkcyjne '*łt^~

l

,\

'^- '

*^ Y

' ,'•

''.r

- T''-, '^^'-'

::^;~i

':•

i

Krotka relacji UMOWY informuje, że pracownik o numerze E# bierze udział w realizacji projektu o atrybutach: P#, \AZWA, BUDŻET, RODZAJ, PRIORYTET, MIASTO i otrzymuje za to określone WYNAGRODZENIE. Dla każdej •artości atrybutu P# istnieje dokładnie jedna wartość każdego z atrybutów: NAZWA, BUDŻET, RODZAJ, -RIORYTET i MIASTO. O atrybutach NAZWA, BUDŻET, RODZAJ, PRIORYTET i MIASTO mówimy, że są --^fikcyjnie zależne od atrybutu P# lub że są przez niego identyfikowane. Definicja 5.1. Niech będzie dany zbiór atrybutów SCH oraz jego podzbiory X i Y. Mówimy, że Y jest funkcyjnie zależny od X, co zapisujemy X -> Y, wtedy i tylko wtedy, gdy dla każdej relacji R rozpiętej na schemacie SCH i dla każdych dwóch krotek t\ oraz *2 należących do R spełniony jest warunek: , , <, .:-•-, "

-

h(X) = h(X) => r,(r» = '2(10-

L-W•>>'.-•;*• .>-*v-x,-*",..,-.i TS Jv

Jeśli .A!" jest kluczem, to zależność X -+ Y jest spełniona dla dowolnego zbioru Y. Zależności funkcyjne mogą istnieć miedzy atrybutami niekluczowymi, na przykład w relacji PROJEKTY występuje zależność RODZAJ -> PRIORYTET. Siektóre zależności są spełnione przez wszystkie relacje. Nazywamy je trywialnymi. Przykładem może być tu zależność X-*X. Uogólniając, zależność X -> 7 jest trywialna, jeśli Y c X. Na podstawie znajomości pewnych zależności funkcyjnych można uzyskać inne. Podstawą procesu wnioskowania są reguły zwane aksjomatami Armstronga: 1. Zwrotność. Jeżeli Y^XcSCH, ioX->Y. 2. Rozszerzanie. Jeżeli X-* Y oraz Ze fFc. SCH, to XW -* YZ . Zapis XZ oznacza zbiór atrybutów { X, Z } . 3. Przechodniość. Jeżeli X-^Y oraz K-»Z, to X-*Z. Aksjomaty Armstronga tworzą zupełny i poprawny zbiór reguł wnioskowania. Oznacza to, że można na ich podstawie uzyskać wszystkie zależności funkcyjne wynikające z pewnego zbioru F zależności funkcyjnych oraz że nie jest możliwe uzyskanie zależności fałszywej. Z aksjomatów Armstronga wynikają następujące reguły przydatne przy wyprowadzaniu nowych zależności: Reguła sumowania. Jeżeli X-* Y oraz X-+ Z, to X~+ YZ . Reguła pseudoprzechodniości. Jeżeli X-* Y oraz YW-tZ, to Reguła rozkładu: Jeżeli X -> Y oraz Ze F, to X -> Z .

v*-#**

Jeżeli w zależności X -> Y, X jest zbiorem atrybutów, to może wystąpić zależność częściowa Y od X. Oznacza to, że Y zależy od pewnego podzbioru X. Definicja 5.2. Atrybut F jest w pełni funkcyjnie zależny od atrybutu X, jeśli jest funkcyjnie zależny od niego i jeśli nie jest funkcyjnie zależny od żadnego jego podzbioru.

:

'-

l

Zależność opisaną w definicji 5.2 nazywamy pełną. Atrybuty: NAZWA, BUDŻET, RODZAJ, PRIORYTET i MIASTO relacji UMOWY są funkcyjnie zależne od klucza głównego P#, E#. Nie jest to jednak zależność pełna, ponieważ są one identyfikowane przez jego część, to znaczy przez numer projektu P#. W pełni funkcjonalnie zależny od klucza głównego jest natomiast atrybut WYNAGRODZENIE. Poza tym zwróćmy uwagę, że atrybut PRIORYTET zależy od atrybutu P# nie bezpośrednio, lecz przez atrybut RODZAJ. Zgodnie z aksjomatem przechodniości zależność P# -» PRIORYTET wynika z zależności P#-> RODZAJ oraz RODZAJ-> PRIORYTET. Zależności wynikające z aksjomatu przechodniości nazywamy przechodnimi lub tranzytywnymi. Definicja 5.3. Atrybut F jest tranzytywnie zależny od atrybutu X, jeśli istnieje atrybut Z, taki że są prawdziwe nietrywialne zależności X~>ZorazZ-» Y. Przykład 5.2. Rozpatrzmy relację R o schemacie SCH = { A, B, C, D, E, F }. Załóżmy, że między atrybutami istnieją następujące zależności funkcyjne: A -> B, A ->• C, CD -» E, CD -> F, B -» E. Udowodnić zależności: A-+E,CD-+ EF, AD -» F. 1. 2. 3.

A -» E. Zależność ta wynika zA-^B oraz B -> E na podstawie aksjomatu przechodniości. CD -> EF. W dowodzie wykorzystuje się regułę sumowania do zależności CD -» E oraz CD -> F. AD -> F. Z reguły rozszerzania zastosowanej do A -» C wynika zależność AD -> CD. Z zależności: AD -> CD oraz CD ->• F wynika AD -> F.

Definicja5.4.

"

^--.^ ^marsta Ł f
,-,.-

^,: ,

v

-.^- -.

Niech będzie dany zbiór F zależności funkcyjnych określonych na schemacie SCH. Zbiór wszystkich zależności funkcyjnych, które można uzyskać na podstawie F nazywamy domknięciem zbioru F i oznaczamy przez F*". Reguły wnioskowania można wykorzystać do określenia klucza relacji. Wartością początkową klucza K jest zbiór wszystkich atrybutów, czyli schemat relacji: K=SCH.

t^i,r*,:.;.

te,-!.-;;,

-

Następnie dokonuje się eliminacji poszczególnych atrybutów. Atrybut A jest eliminowany, jeśli jest spełniony warunek:

K-{A} -> SCH c F*,

'

?

"'-

gdzie F jest zbiorem zależności funkcyjnych między atrybutami należącymi do SCH. Algorytm kończy się, gdy nie istnieje możliwość usunięcia żadnego atrybutu. Do eliminacji atrybutów można wykorzystać następujące twierdzenie: • t J * "' -,v"; --...;."?

Twierdzenie 5.1.

Niech będzie dana relacja R rozpięta na schemacie SCH oraz zbiór F zależności funkcyjnych między atrybutami zbioru SCH. Wtedy: c F"

=>

SCH-{A} -^ SCH c

F",

gdzieś 6 SCH oraz X jest zbiorem atrybutów należących do SCH. Dowód.

.

J

.. . . . i

.....J

/\-'7:..

.

s

""'. . . *

Na podstawie reguły rozszerzania z X —> <<4 otrzymujemy zależność: %

''"'-' :

;

z której wynika teza. i -. '

-

,-

»

(SC/f-^lJu^r -> (SCH-{A})\JA,

" '

*-' "-- •• _

,

' • • ' " '''./"

-

.

5.2. Trzecia postać normalna ,

%

.f,

*

•

,

,

^

,

,.;

,

w

.

Właściwy projekt bazy danych wymaga doprowadzenia relacji do odpowiednich postaci normalnych (ang. normal forms). Pojecie normalizacji zostało wprowadzone przez Codda [2]. Zdefiniował on trzy postacie normalne. Różnice

62

A i

miedzy nimi polegały na strukturze zależności funkcyjnych miedzy atrybutami. Dotyczy to zależności niepełnych oraz tranzytywnych, które powodują redundancję i są przyczyną anomalii. Definicja 5.5.

l

.-/.* ^, , >

\-*.Y«' v ,

Relacja R jest w pierwszej postaci normalnej (INF), jeśli dziedziny jej atrybutów zawierają tylko wartości atomowe (niepodzielne). Wszystkie omawiane do tej pory relacje występują w pierwszej postaci normalnej. Na przecięciu wiersza i kolumny występowały w nich pojedyncze wartości. Powyższa definicja nie obejmuje relacji, których atrybuty są również relacjami. Nazywamy je relacjami zagnieżdżonymi (ang. nested relationś) [10]. Rysunek 5.2 przedstawia przykład relacji zagnieżdżonej. Relacja ta ma cztery atrybuty: A, B, C i D, przy czym tylko tfrybut A przyjmuje wartości pojedyncze. Wartościami atrybutów B i C są relacje unarne. Atrybut D jest bardziej riożony. Odpowiadająca mu relacja zawiera trzy atrybuty, z których jeden - E' również jest relacją (unarną). Dalsze rozważania będą dotyczyć tylko relacji znormalizowanych, czyli występujących co najmniej w pierwszej postaci normalnej.

A *4riT9*«C*

J

,N

EI

B B'

C C'

D'

bi b2

Cl

d,

a3

b2 b3

a4

b4

d2

D E' E" e, e2 e2

C2 C4

d3

ea

Cl

d3 d4

S e3 e2 e4

Ca

C4

F' f, 6

f.

f! f3

Rys. 5.2. Relacja zagnieżdżona

Definicja 5.6.

;

/

•'

"'j

—

t

%Ł

Relacja R jest w drugiej postaci normalnej (2NF), jeśli jest w pierwszej postaci normalnej i każdy jej atrybut niekluczowy jest w pełni funkcyjnie zależny od dowolnego klucza. "•'•

•"-

L. .....,_.,„. ,j

Można zauważyć, że każda relacja, której klucz jest pojedynczym atrybutem występuje w drugiej postaci normalnej. Rysunek 5.3 przedstawia graficznie zależności funkcyjne między atrybutami relacji UMOWY. Ze względu na niepełne zależności funkcyjne relacja ta nie spełnia warunków definicji drugiej postaci normalnej. Właśnie te zależności są przyczyną anomalii wymienionych w punkcie 5.1.

Rys. 5.3. Zależności funkcyjne w relacji UMOWY - przykład 5.1

63

Zostaną one zlikwidowane, jeśli dane zawarte w relacji UMOWY przedstawimy za pomocą dwóch relacji otrzymanych w wyniku wykonania operacji projekcji: KONTRAKTY = lip*, E#, WYNAGRODZENIE (UMOWY) oraz PROJEKTY_BIS = Ylftt, NAZWA, BUDŻET, RODZAJ, PRIORYTET? MIASTO (UMOWY) . Liczby krotek w relacjach KONTRAKTY oraz UMOWY są równe. Relacje PROJEKTY (rys. 2.2) oraz PROJEKTYJBIS mają takie same schematy. Ilość krotek w relacji PROJEKTY jest jednak większa niż w relacji PROJEKTY_BIS (rys. 5.4) o krotki opisujące projekty, do których nie przydzielono pracowników. W relacji UMOWY nie można było ich zapisać. Obie relacje: KONTRAKTY oraz PROJEKTY_BIS spełniają warunki definicji drugiej postaci normalnej. Transformacja usunęła niepełne zależności funkcyjne (rys. 5.5). Podczas przejścia od INF do 2NF nie została utracona żadna informacja. Wszystkie dane zawarte w relacji UMOWY znajdują się również w relacjach KONTRAKTY oraz PROJEKTY BIS. PROJEKTY BIS

p# Pl

NAZWA

BUDŻET

P2

Kredyt Finn

no ooo

P3

Polisa

P4 P5

PRIORYTET

MIASTO

50000

Bankowość Rachunkowość

1 3

Warszawa Łódź

40000

Ubezpieczenia

4

Łódź

Makler

30000

Rynek kapitałowy

2

Poznań

Visa

200000

Bankowość

1

Kraków

RODZAJ

Rys. 5.4. Relacja PROJEKTY^BIS = Yln, NAZWA, BUDŻET,RODZAJ,PRIORYTET, MIASTO (UMOWY)

' - • * ' •

-'

Rys. 5.5. Zależności funkcyjne w relacjach KONTRAKTY oraz ,:.--vi-„:---:^K; w fei;;-R;;jOif«••,-'*' '!"',.

Proces transformacji jest odwracalny. Relację UMOWY otrzymuje się w wyniku złączenia naturalnego relacji KONTRAKTY oraz PROJEKTY_BIS: *,-.•..

ts K

UMOWY = KONTRAKTY * PROJEKTY_BIS.

J

Zauważmy, że taki sam rezultat można otrzymać łącząc relację KONTRAKTY z relacją PROJEKTY. Dokonując takiego złączenia tracimy informację o projektach P6 i P7. W relacji KONTRAKTY nie odpowiadają im bowiem żadne krotki. Model zawierający relacje w 2NF lepiej zatem odpowiada rzeczywistości. Zbiór zależności w relacji PROJEKTY zawiera zależność tranzytywną P# -> PRIORYTET. Jest ona przyczyną następujących anomalii: •

Każda zmiana priorytetu danego rodzaju projektu wymaga przejrzenia całej relacji celem znalezienia wszystkich krotek, w których ten rodzaj występuje i dokonania odpowiedniej aktualizacji. W przeciwnym wypadku relacja będzie zawierać sprzeczne dane.

•

Do relacji PROJEKTY nie można wprowadzić informacji o priorytecie określonego rodzaju projektu, jeśli odpowiedni projekt nie istnieje.

•

Usunięcie z relacji PROJEKTY krotki dotyczącej jedynego projektu danego rodzaju powoduje utratę informacji o priorytecie tego rodzaju projektu.

Zostaną one usunięte, jeśli relacja PROJEKTY zostanie zastąpiona relacjami w trzeciej postaci normalnej (3NF). Definicja 5.7. Relacja R o schemacie SC//jest w trzeciej postaci normalnej (3NF), jeśli dla każdej zależności X -> K, gdzie X c SCH oraz Y cz SCH, zachodzi co najmniej jeden z następujących przypadków: F jest zależnością trywialną; ^ jest nadkluczem relacji R; Y jest atrybutem kluczowym.

V

"i t i

Zgodnie z definicją 5.7 w relacjach w trzeciej postaci normalnej (3NF), nie mogą istnieć niepełne zależności funkcyjne oraz zależności tranzytywne. Druga postać normalna dopuszcza istnienie zależności tranzytywnych. Relacje w 3NF spełniają zatem warunki definicji 5.6, czyli występują również w drugiej postaci normalnej.

l

RP

PR

p# Pl

NAZWA BUDŻET

RODZAJ

P2 P3

Polisa

110000 Bankowość Warszawa 50000 Rachunkowość Łódź 40000 Ubezpieczenia Łódź

P4

Makler

30000

P5

Visa

200 000 Bankowość

Kredyt Finn

Rynek kapitałowy

RODZAJ

PRIORYTET

Bankowość Rachunkowość

1 3 4

Rynek kapitałowy

MIASTO

Ubezpieczenia

Poznań

18*

2

Kraków

Rys. 5.6. Relacje PR i RP w trzeciej postaci normalnej Relacja KONTRAKTY spełnia warunki definicji 5.7. Przekształcenie relacji PROJEKTY do trzeciej postaci normalnej wykonujemy za pomocą operacji projekcji na odpowiednie atrybuty: PR = rU, NAZWA, BUDŻET, RODZAJ. MIASTO (PROJEKTY)

OTÓŻ

RP = FlRODZAJ, PRIORYTET (PROJEKTY) . ,

':

-.-.*>

Podobnie jak poprzednio proces transformacji nie gubi żadnej informacji (rys. 5.6) i jest odwracamy. Relację PROJEKTY można otrzymać przez złączenie relacji PR oraz RP według atrybutu RODZAJ. Wykonanie projekcji spowodowało usunięcie zależności tranzytywnej (rys. 5.7). Otrzymany model zawierający relacje w trzeciej postaci normalnej lepiej odpowiada rzeczywistości. Do relacji RP można wprowadzić informacje o priorytecie projektów z dowolnej dziedziny niezależnie od tego czy projekty takie będą opisane w relacji PROJEKTY.

RODZAJ

Rys. 5.7. Zależności funkcyjne w relacjach PR oraz RP

PRIORYTET

5.3. Rozkłady relacji Podczas normalizacji dana relacja jest zastępowana innymi relacjami. Transformacja polega na rozkładzie relacji. Definicja 5.8. Rozkładem schematu SCH relacji R nazywamy zbiór schematów SCH{ c SCH relacji R\, taki że

^ •* •*•

SCHiUSCH2\J ... u5C//„ = SC//. Zbiory atrybutów SCT/j nie muszą być rozłączne. Przy dokonywaniu rozkładu może nastąpić utrata informacji lub zależności funkcyjnych. Definicja 5.9. Niech będzie dany schemat SCH= { A}, A2, ... , An } oraz zbiór zależności funkcyjnych F między atrybutami A\. Rozkład schematu SCH na zbiór schematów {SCHi,SCH2, ... ,SCHn} nazywamy odwracalnym (ang. losslessjoin decomposition) względem F, jeśli dla każdej relacji R rozpiętej na schemacie SCH i spełniającej F jest spełniony warunek: 5 -y, v-

/? = /?, */? 2 * ... *Ra,

gdzie R{ jest relacją rozpiętą na schemacie SCH^, otrzymaną w wyniku projekcji relacji R na zbiór SCHi. Warunek w definicji 5.9 oznacza, że relacja R jest złączeniem swoich rzutów. Definicja 5.10. Niech będzie dany schemat SCH={Ai,A2, ... ,Aa} oraz zbiór zależności funkcyjnych F między atrybutami A* Rozkład schematu SCH na zbiór schematów { SCHh SCH2, ... , SGHa } zachowuje zależności, jeśli jest spełniony warunek:

gdzie Fj+jest rzutem domknięcia zbioru zależności F na zbiór SCHi (to znaczy zbiorem zależności należących do F^ które zachodzą między elementami Oznacza to, że wszystkie zależności funkcyjne ze zbioru F wynikają z sumy wszystkich zależności określonych na schematach Nie każdy rozkład spełnia warunki definicji 5.9 i 5. 10. ••;.'.-:

Przykład 5.3.

..>>••;>!•.!.

.v.

/••/}•*'".,-.,«-.,,

"

- '

'

'

'

•,

,

Niech SCH ~ { A, B, C, D}iF={A-+B, C - > D } . N a rysunku 5.8 przedstawiono relację R rozpiętą na tym schemacie oraz jej rozkład na relacje S i T o schematach SCHS = { A, B } i SCHj = { C, D } . Między atrybutami relacji S oraz. T istnieją zależności funkcyjne F s = { / 4 - » f i } i Fr={C-»£>}.

A

B

C

D

a! ai a2

b, bi b.

C]

d, d2 d,

C2 Cl

fVt "•"

,

A

B

A

C

ai a2

b, b2

Cl

d, d2

Rys. 5.8. Relacje dla przykładu 5.3

66

C2

Dokonany rozkład zachowuje zależności funkcyjne. Nie spełnia jednak warunku definicji 5.9. Relacja W, otrzymana w wyniku złączenia relacji S i T, zawiera fałszywą informację w postaci krotki, której nie ma w relacji R (rys. 5.9). Przykład 5.4. Rozłóżmy relację R o schemacie { A, B, C } i zależnościach funkcyjnych F = { AB ->• C, C -» B } na relacje: S o schemacie { A, C } i To schemacie { B, C }. Rozkład ten nie zachowuje zależności. Mamy bowiem: Fs = { } oraz FT = { C -> B }. Zależność AB-* C została stracona. '.;• "T , \ ,,,.,,,..,.., . Zawsze jednak można rozłożyć relację R o schemacie SCH na relacje w trzeciej postaci normalnej. Rozkład taki spełnia warunki definicji 5.9 i 5.10. Transformację przeprowadza się względem istniejących zależności funkcyjnych.

l

'V

J

A

B

C

D

ai »i a2 a2

b, b! b2 b.

Cl

d, d2 dt d2

C2 Cl C2

{3:» !£?,

W=S*T Rys. 5.9. Złączenie naturalne rzutów relacji R ~ przykład 5.3

Twierdzenie 5.2.

l

Jeżeli między atrybutami X oraz A relacji R o schemacie SCH istnieje zależność funkcyjna X -» A, przy czym X n A = 0, to relację tę można rozłożyć na relacje:

Dowód

•

" " ' . . . . :

Hf^^t »<~v*-,*-n *etłf.—. ,-,. i

Relacja R zawiera się w złączeniu swoich rzutów (własności złączenia naturalnego). Operacja złączenia relacji S i Tnie może więc gubić krotek relacji R. Z definicji operacji projekcji wynika, że wartości atrybutu X w relacjach R, S i T muszą być takie same. Ponadto, ze względu na zależność X -» A, każdej krotce relacji T odpowiada dokładnie jedna krotka relacji S. Złączenie relacji S i Tnie może więc zawierać krotek dodatkowych, to znaczy nie należących do relacji '• R, co dowodzi odwracalności rozkładu. W procesie normalizacji rozkład jest wykonywany aż do uzyskania wszystkich relacji w 3NF. Przykład 5.5.

" "'

*" »•

1

-Ą

* •**** •;.'$**&-• vfe*tó st .?t

Ą

Dana jest relacja R o schemacie SCH- {A, B, C, D, E}. Między atrybutami istnieją następujące zależności funkcyjne: \ ! F = { A -> B, B -* C, C -^> D, C -> E }. Kluczem relacji jest A. Należy sprowadzić relację R do trzeciej postaci normalnej. Proces przekształcenia wymaga wykonania trzech rozkładów: l.

a

"r

*

"

Dokonujemy rozkładu względem zależności C -> D. Otrzymujemy relacje Rl i R2 o schematach: oraz

{A, B, C, E } .

't 3*3f4ii,-a:^fjtif' ->-..i

Relacja RI jest już w trzeciej postaci normalnej. Dalsze postępowanie będzie dotyczyć relacji R2. 2.

Wykorzystując zależność C -> E otrzymujemy relacje R21 i R22 o schematach: 5C//R2, = { C, E } oraz SCH^ = { A , B, C }.

3.

"""

"'

Z relacji R22 otrzymujemy na podstawie zależności B-*C relacje R221 i R222 o schematach:

= {A,B} .

5C//R221 = { B, C } oraz

Relacja R została przekształcona na cztery relacje R1(C, D), R21(C, E), R221(B, C) oraz R222(A, B) w trzeciej postaci normalnej. Przebieg transformacji przedstawiono graficznie na rysunku 5. 10.

Rys. 5.10. Drzewo rozkładu relacji

5.4. Postać normalna Boyce'a-Codda Warunki narzucone przez definicję trzeciej postaci normalnej nie likwidują wszystkich anomalii. Pokazuje to następujący przykład: Przykład 5.6.

;.

Rozważmy relację R schemacie { P#, C#, D# } (rys. 5.11), gdzie P# oznacza numer projektu, C# - numer części i D# numer dostawcy. Krotka relacji R informuje, że w projekcie P# jest używana część C# dostarczana przez dostawcę D#. Ponadto zakłada się, że każdy dostawca dostarcza tylko jedną część, być może do wielu projektów, oraz że każda cześć może być dostarczana przez wielu dostawców, ale do określonego projektu może ją dostarczać tylko jeden dostawca. Obowiązują zatem następujące zależności funkcyjne: F = { P#, C# -> D#, D# -» C# } (rys. 5.12). Relacja R ma dwa klucze kandydujące: P#, C# oraz P#, D#. Każdy atrybut jest kluczowy. Jeżeli z relacji R usunęlibyśmy krotkę ('Pl', 'Cl', 'Dl'), to utracona zostałaby informacja o tym, że dostawca Dl dostarcza część Cl. Jest to bowiem jedyna krotka związana z tym dostawcą. Do relacji R nie można wprowadzić informacji o dostawie części przez danego dostawcę dopóki nie będzie ona dotyczyła jakiegoś projektu. Przyczyną opisanych anomalii jest zależność D# -> C#. Nie narusza ona jednak definicji 5.7. Relacja R nie zawiera zależności niepełnych lub tranzytywnych. Mimo istniejących anomalii jest w trzeciej postaci normalnej. Opisanych wad nie posiadają relacje spełniające warunki określone przez postać normalną Boyce'a-Codda (BCNF). Definicja 5.11.

''

v i ; "" ' '

-'

—f'^''--" •" •

- .-.: '

* •- .-» .•:> •

Relacja R o schemacie SCH jest w postaci normalnej Boyce'a-Codda (BCNF), jeśli dla każdej zależności X -» Y, gdzie X c SCH oraz Y c SCH, zachodzi co najmniej jeden z następujących przypadków: F jest zależnością trywialną; X jest nadkluczem relacji R.

68

l

f

p# Pl Pl

f

Pl

P2 P2 P2 P3 P3 P3 P3 P4

t i

C#

D#

Cl C2 C3 C2 C3 C4 C2 C3 C4 C5 C5

Dl D2

D3 D2 D3 D4 D5 D3 D4 D6 D6

iii l <•.'.•>>

.

.

„U

Rys. 5.11. Relacja /J dla przykładu 5.6

Definicja postaci BCNF jest mocniejsza od definicji trzeciej postaci normalnej. Nie zawiera ostatniej klauzuli definicji 5.7: „7jest atrybutem kluczowym". Jej naruszenie może nastąpić, gdy relacja posiada co najmniej dwa złożone klucze kandydujące, które mają wspólne atrybuty. Wszystkie atrybuty relacji w postaci BCNF są bezpośrednio zależne od klucza. Nie ma więc tu zależności tranzytywnych. Każda relacja w postaci normalnej Boyce'a-Codda jest zatem także w trzeciej postaci normalnej, ale nie odwrotnie. Relacja R z przykładu 5.6 nie spełnia warunków definicji 5.11 z powodu zależności D# -> C#. Transformacja do postaci normalnej Boyce'a-Codda nie gwarantuje zachowania zależności (przykład 5.4).

i

Rys. 5.12. Zależności &nkcyjne w relacji R z przykładu 5.6

' ^ "W-i?

5.5. Czwarta postać normalna Zależności funkcyjne wykluczają możliwość identyfikacji więcej niż jednej wartości atrybutu przez taką samą wartość innego. Jeśli jest spełniona zależność X -> Y, to nie mogą istnieć dwie krotki z tą samą wartością atrybutu X i różnymi wartościami atrybutu Y. Może jednak wystąpić sytuacja, gdy z jedną wartością atrybutu X jest związany zbiór wartości atrybutu Y. Miedzy X i F występuje wtedy zależność wielowartościowa. Definicja 5.12. Niech będzie dany zbiór atrybutów SCH oraz jego podzbiory X i Y. Mówimy, że Y jest wielowartościowo zależny od X, co zapisujemy X~>—> Y, wtedy i tylko wtedy gdy dla każdej relacji R rozpiętej na schemacie SCH i dla każdych dwóch krotek t\ oraz f 2 należących do R, takich że t\ (X) -12 (X), istnieją kroki /3 i f 4 spełniające warunki:

-Y) = t2(SCH-Y),

Rysunek 5.13 przedstawia graficzną interpretację krotek ti, (2, ?3 i 4. Bezpośrednio z definicji wynika, że zależność wielowartościowa X —»-» Y implikuje inną zależność wielowartościową: X —>—> Z, gdzie Z jest uzupełnieniem sumy zbiorów X oraz Y względem SCH, to znaczy Z = SCH - (X u Y). Zależność nazywamy trywialną, jeśli jest ona spełniona przez każdą relację, której schemat zawiera atrybuty X i Y. Jeżeli Y c X, to zależność Jf-»-> Y jest trywialna. Przy zależności wielowartościowej X —>—> Y w relacji R o schemacie SCH = {X, Y, Z} istnienie krotek (x\, y\, zj) oraz (xi, y2, z2) oznacza istnienie krotek (xls y\, z2) i (xi, jy2, Z]). Dodanie krotki (x\, y2, z2) wymusza więc dodanie krotki (xi, y2, Zi). Zależność wielowartościowa X ->-> 7 wyznacza zbiór wartości atrybutu Y związany z określoną wartością atrybutu X. Zbiór ten jest taki sam niezależnie od wartości innych atrybutów. Można to sformułować następująco: między atrybutami X i F schematu SCH = { X, Y, Z} istnieje zależność wielowartościowa, jeśli dla każdej wartości atrybutu X zbiór wartości atrybutu Y powtarza się dla każdej wartości atrybutu Z. Zauważmy, że dla dowolnych wartości Xi, y\, y2, zt, z2, z tego że: krotki (xj, jj) i (xi, y2) należą do relacji S o schemacie { X, Y} oraz krotki (x\, z\) i (x i, z 2 ) należą do relacji To schemacie {X,Z} wynika, że krotki (x\, y\, Z]), (xi,y\, z2), (%i, y2, z\) i (x\, y2, z2) należą do złączenia S * Trelacji S i T. -.-,.,

X

Y

a h a2, ... ,ak

aw,ak+2, ... ,a,

ai, a2, ... , ak

bk+Lb^z, - ,bi

a1; a2, ... ,ak ai, a2, ... ,ak

ak+1,ak+2, ... ,a. bt,,,^, ... ,b,

Z a!+1,a1+2, bi+i, b)+2, bi+i, bj+2, a i+i; ai+2,

... .ą, ... ,bn ... , b„ ... , a„

Rys. 5.13. Graficzna interpretacja zależności wielowartościowej X -

Twierdzenie 5.3. Niech będzie dany schemat SCH = { X, Y, Z }. Między atrybutami X i F istnieje zależność wielowartościowa X — >— > F wtedy i tylko wtedy, gdy rozkład schematu SCH na schematy { X, Y } oraz { X, Z } jest odwracamy, czyli dla każdej relacji ^rozpiętej na schemacie SCH zachodzi: • , ,

gdzie S i T są relacjami rozpiętymi na schematach odpowiednio { X, Y } i { X, Z } . Z twierdzeń 5.2 i 5.3 wynika, że zależność funkcyjna JST-» Fimplikuje zależność wielowartościową X -»-» F. Przykład 5.7.

Ł

Rozważmy relację R o schemacie { P#, K#, MIASTO }, gdzie P# oznacza numer projektu, K# - numer klienta, MIASTO - siedzibę klienta, (rys. 5.14). Każdy projekt może być wykonywany dla więcej niż jednego klienta i odwrotnie: każdy klient może zamówić wiele projektów. Klienci mogą mieć przedstawicielstwa w wielu miastach. W danym mieście mogą się znajdować siedziby wielu klientów. Między atrybutami nie występują zależności funkcyjne. Każdy atrybut relacji R jest kluczowy. Kluczem głównym jest bowiem złożenie P#, K#, MIASTO. Relacja R spełnia wymagania definicji 5.11, czyli jest w postaci normalnej BCNF. Występują tu jednak pewne anomalie. Z każdą wartością atrybutu K# jest związany pewien zbiór wartości atrybutu MIASTO. Jest on niezależny od zamawianych projektów. Dla każdego projektu muszą być powtórzone, poza numerem klienta, również miasta, w których znajdują się jego przedstawicielstwa. Podobnie, jeśli klient ma siedziby w kilku miastach, to dla każdego miasta muszą być powtórzone numery zamówionych projektów. Istnieje tu zatem redundancja. Wprowadzenie do relacji R informacji o tym, że klient Kl zamówił projekt P3 wymaga utworzenia dwóch krotek z dwiema różnymi wartościami atrybutu MIASTO (Warszawa oraz Łódź - siedziby klienta Kl). Podobne uwagi można sformułować dla powiązania między atrybutami K# i P#. Obydwa związki spełniają warunki definicji 5.12. Są to więc zależności wielowartościowe.

70

p# Pl Pl Pl Pl Pl

KM

MIASTO

Kl

Warszawa

Kl

Łódź

K2 K2 K2

Poznań

P2 P2 P3 P3

Kl Kl

Warszawa

K2 K2

Poznań

P3 P3

K2

Kraków

K3

Warszawa

Wrocław Kraków Łódź Wrocław -•*"

Rys. 5.14, Relacja J? z przykładu 5.7

Anomalie opisane w przykładzie 5.7 zostaną usunięte przez przekształcenie relacji do czwartej postaci normalnej (4NF). :

l

Definicja 5.13. Relacja R o schemacie SCH jest w czwartej postaci normalnej (4NF), jeśli dla każdej zależności wielowartościowej Jf-»-» Y, gdzie X c SCH oraz Y c SCH, zachodzi co najmniej jeden z następujących przypadków: • •

Jf->-> Y jest zależnością trywialną; X jest nadkluczem relacji R . , - , . . , , *'--•>••>••'*

v

*' -

'

* f

Vr

- ^r ,

A -*

Definicja czwartej postaci normalnej różni się od definicji postaci normalnej BCNF tylko użyciem zależności wielowartościowych zamiast zależności funkcyjnych. Jedynymi nietrywialnymi zależnościami wielowartościowymi między atrybutami relacji w czwartej postaci normalnej są zależności funkcyjne. Każda relacja w 4NF jest również w BCNF. Załóżmy, że relacja R o schemacie SCH jest w postaci 4NF i nie jest w postaci BCNF. Istnieje więc nietrywialna zależność X ~> Y, gdzie X nie zawiera klucza. Ze względu na to, że X -> Y implikuje zależność wielowartościowąX ->-> Y, relacja R nie może być w 4NF, co jest sprzeczne z założeniem.

K#

P#

K#

MIASTO

Kl Kl

Pl

Łódź

K2

Pl

Kl Kl K2

K2

P3

K2

Wrocław

K3

P3

K2

Kraków

K3

Warszawa

P2

Warszawa Poznań

Rys. 5.15. Relacje KP i KM w czwartej postaci normalnej

,

Relację R z przykładu 5.7 można przekształcić do czwartej postaci normalnej za pomocą operacji projekcji. Otrzymujemy (rys. 5.15): •'^^••.,^;-„.~,T.,,^„^.^I.^

.y"'-

KP = OKUENT, PROJEKT (R)

oraz

KM = OKLENT, MIASTO (R) •

Relacje KP oraz KM są w czwartej postaci normalnej. Transformację przeprowadza się stosując rozkład tak długo, aż znikną „rzeczywiste" zależności wielowartościowe i powstaną dla nich oddzielne relacje. Należy jednak zaznaczyć, że procedura transformacji nie zawsze zachowuje zależności.

5.6. Piąta postać normalna

i

Poza zależnościami funkcyjnymi oraz wielowartościowymi schematy relacji mogą zawierać zależności związane z odwracalnością ich rozkładów.

R

A

B

C

at ai ai a2

bi

Cl

bt

C2

b2 bi

Cl Cl

Rys. 5.16. Relacja R do przykładu 5.8 Przykład 5.8. [4]

,

,

^_.

Rozważmy relację R przedstawioną na rysunku 5.16. Między jej atrybutami nie istnieją zależności funkcyjne i wielowartościowe. Wykonajmy projekcje (rys. 5.17):

/» = IŁ. B w, e=n*,c(«), S=IL,C(«). Relację T otrzymaną w wyniku złączenia relacji P i Q przedstawiono na rysunku 5.18. Zawiera ona wszystkie krotki relacji R oraz krotkę (a2, b\, c2). Jeżeli złączymy ją z relacją S, to otrzymamy relację początkową R. Relacja R jest więc złączeniem swoich trzech rzutów: .

*-

.

,

_

•

•

•

.

:

•

•

<

.

.

-

.,

-*,»,..:.-•-„

*-*;.*,

...

jt

^.^ - . -

-

.-^^v -

..

Mówimy, że dla relacji R jest spełniona zależność złączeniowa (&ag.join dependency).

p B

B

b,

b, b, b2

C

A

C

Cl

3i

Cl

C2

3i

C2

Cl

a2

Cl

Rys. 5.17. Projekcje relacji R z przykładu 5.8

A

B

C

3l

b, b! b2 bi b,

Cl

aj ai a2 aż

C2 C] Cl C2

Rys. 5.18. Złączenie relacji P i Q do przykładu 5.8 Definicja 5.14.

-*

Niech będzie dany schemat SCH oraz zbiór schematów SCHi, 5O/2, ... , SCHa, takich że SCHt c SCH oraz

^

SCH}\JSCH2V ... uSC/4 = SCH. W schemacie SCH zachodzi zależność złączeniowa *(SCHl,SCH2, ... ,SCHn), jeżeli dla każdej relacji R rozpiętej na schemacie SC7/jest spełniony warunek: P— — KI j? K

$ K.2 p it

...

# KU D ,

gdzie R{ jest relacją schemacie SCH\, otrzymaną w wyniku projekcji relacji R na zbiór SCH\. Warunek w definicji 5.14 oznacza, że relację R można rozłożyć na relacje o mniejszej ilości atrybutów. Jeśli jeden ze schematów SCH, jest równy SCH, to taką zależność złączeniową nazywamy trywialną. Zależności złączeniowe oznaczają sprzężenia między atrybutami. Tytułem przykładu rozważmy relację LPS (L#, P#, S#), gdzie atrybuty L#, P# i S# oznaczają odpowiednio numer lekarza, pacjenta oraz urządzenia medycznego. Krotka relacji LPS oznacza, że lekarz L# bada pacjenta P# za pomocą urządzenia S#. Między atrybutami L#, P# i S# występuje zależność złączeniowa, gdy prawdziwe jest następujące wnioskowanie: Jeśli: • • •

ai',<«rr,,.-..

Lekarz L l bada pacjenta P l, Pacjent P l jest badany za pomocą urządzenia S l, Urządzenie S l jest obsługiwane przez lekarza LI,

*.-;-•

to lekarz LI bada pacjenta P l za pomocą urządzenia Sl. Z reguły nie jest to prawda. Lekarz LI może badać pacjenta P l za pomocą innego urządzenia, pacjent P l może być badany za pomocą urządzenia Sl przez innego lekarza, lekarz LI może za pomocą urządzenia Sl badać innego pacjenta. Definicja 5.15.

mt "'^fl wótew^j sx^a;-

Relacja R o schemacie SCH jest w piątej postaci normalnej (5NF), jeśli dla każdej zależności złączeniowej *(SCHi, SCH2, ... ,SCH„), gdzieSCH^SCH oraz - ,„v> • .-ł r n

= SCH,

^

zachodzi co najmniej jeden z następujących przypadków: • •

*(SCHi,SCH2, ... ,SCHn) jest zależnością trywialną; Każdy zbiór SCH( jest nadkluczem relacji R.

Piąta postać normalna wymaga, by atrybuty relacji nie były sprzężone. Jeśli w relacji LPS istniałyby zależności złączeniowe, to transformacja do postaci 5NF polegałaby na utworzeniu trzech odrębnych binarnych relacji opisujących związki między każdą parą atrybutów. Definicja 5.15 zawiera silniejsze warunki niż definicja 5.13. Każda relacja w 5NF występuje także w 4NF. Piąta postać normalna jest również nazywana w literaturze złączeniową postacią normalną (ang. project-join normalform PJNF).

73

6. Model obiektowo zorientowanej bazy danych %

st

*

ff t. ••':, " _ ._ . :

^

»

^^

r

•*- *-« ,

£

*•»

•s^e-t

'l

*

,

W procesie modelowania projektant bazy danych definiuje pewien zbiór atrybutów mający odzwierciedlać obiekty ze świata rzeczywistego. Dzięki pierwszej postaci normalnej operacje algebry relacyjnej są łatwe do zdefiniowania, a otrzymywane wyniki niemal intuicyjne. Również sama struktura relacji, jako prostokątnej tabeli, wydaje się bardzo czytelna. Właśnie te cechy modelu relacyjnego stały się źródłem jego popularności i szerokiej akceptacji. Taka reprezentacja informacji ma jednak istotne wady. Zależności i związki występujące pomiędzy obiektami rzeczywistymi są często bardzo złożone i zbyt trudne do odzwierciedlenia w płaskich strukturach relacji. Obszerna teoria normalizacji, definiowanie zależności pomiędzy atrybutami oraz proces dekompozycji są zwykle zbyt skomplikowane dla przeciętnego użytkownika systemów relacyjnych. Z drugiej strony nieefektywne schematy relacji mogą być źródłem redundancji. Systemy relacyjne znalazły zastosowanie szczególnie w dziedzinach związanych z operacjami finansowymi, na przykład księgowość, obsługa magazynu lub lista płac, gdzie proste typy danych były zupełnie wystarczające. Wraz z rozwojem systemów informatycznych i przenikaniem techniki komputerowej do szerokiej gamy zastosowań zostały obnażone wszystkie wady i niedoskonałości systemów relacyjnych. Nowe pola zastosowań komputerów, takie jak systemy wspomagania projektowania (ang. Computer Aided Design - CAD), systemy wspomagania tworzenia oprogramowania (ang. Computer Aided Software Engineering - CASE), automatyzacja prac biurowych (ang. Office Automatiori), systemy ekspertowe, przetwarzania obrazu (ang. Image Processing) czy systemy multimedialne, które operują na obrazach, dźwiękach i dokumentach tekstowych, wymagają przechowywania informacji o obiektach złożonych, posiadających pewną wewnętrzną strukturę, reprezentującą w jawny sposób związki agregacji [1]. Model relacyjny, ze względu na swoją prostotę, nie pozwala na wygodne modelowanie złożonych obiektów o zagnieżdżonej postaci. Proste typy danych i atrybuty o wartościach atomowych są niewystarczającym narzędziem dla zapisu tego typu informacji. Ograniczenia systemów relacyjnych stały się powodem dalszych badań w zakresie teorii baz danych. Doprowadziło to do stworzenia systemów obiektowych [5] (ang. object-oriented database systems), w tym systemów z relacjami zagnieżdżonymi [6]. Pierwszym krokiem ku nowemu modelowi danych stało się odrzucenie pierwszej postaci normalnej, jako obowiązującej normy dla relacji. Powstałe w ten sposób relacje zagnieżdżone wzięły swoją nazwę z zagnieżdżonej struktury schematów relacji, występującej w ich definicji. Wartością atrybutu złożonego, o własnym wewnętrznym schemacie, jest pewna relacja. Struktura taka pozwala na reprezentowanie złożonych obiektów i wyrażanie związków agregacji wewnątrz relacji. Modelowanie złożonych obiektów jest teraz prostsze, ponieważ nie wymaga dzielenia zbioru atrybutów na wiele płaskich schematów. Zapamiętywanie wartości obiektów w pojedynczych, zagnieżdżonych krotkach powoduje, że wykonanie złożonego zapytania nie wiąże się z kosztowną i czasochłonną operacją łączenia kilku relacji płaskich. Modelowanie obiektów ze świata rzeczywistego za pomocą struktur zagnieżdżonych pozwala na ograniczenie redundancji, a tym samym ułatwia zachowanie integralności bazy danych i zmniejsza jej objętość. W tym rozdziale opisany został obiektowo zorientowany model bazy danych COCOON (COCOON oznacza Cocoon..Compłex-Object-Orientation based on Nested relations), oparty na relacjach zagnieżdżonych [11]. W modelu tym zaproponowano podejście w kierunku zdefiniowania operatorów aktualizujących, które zapewniają integralność obiektowo zorientowanych baz danych. Proponowane operacje są uogólnione, co oznacza, że mogą być stosowane do różnych typów obiektów. Uogólnione operacje obejmują: insert i delete do tworzenia i likwidowania obiektów, add i remove do dodawania istniejących obiektów do zbioru i do usuwania ich z niego, gain i lose do modyfikowania typu obiektu oraz set do aktualizowania wartości atrybutów. Przy implementacji tej koncepcji na komercyjnej bazie danych wykorzystuje się mechanizm wyzwalaczy. Uaktywniają one odpowiednie procedury, które są wykonywane celem określenia czy operacja aktualizująca jest dozwolona lub jakie dodatkowe operacje powinny być wykonane w celu zapewnienia zgodności bazy danych. Zarys implementacji modelu w systemie zarządzania bazą danych INGRES został przedstawiony w punktach 6.4 i 6.5.

6.1. Krótki przegląd modelu COCOON

„.. : , . . . „ . „

v

Model COCOON został opracowany w Instytucie Systemów Informacyjnych Politechniki w Zurichu, Jest to model obiektowo-fankcyjny. Jego głównymi składnikami są obiekty, funkcje, typy i klasy. Obiektowo zorientowany język modelu COOL jest rozszerzeniem algebry relacji i umożliwia definiowanie danych, ich modyfikację oraz wyszukiwanie. Obiekt jest modelem jednostki obecnej w rzeczywistym świecie. Ma jednoznaczny w systemie identyfikator OID (ang. objęci identifier), który nie ulega zmianie przez cały czas istnienia obiektu i który nie zależy od jego stanu. Obiekty są wystąpieniami typów abstrakcyjnych (ang. abstract data types). Mogą być manipulowane za pomocą swojego interfejsu, jak również uogólnionych operacji aktualizujących. Typy definiują ten interfejs i składają się ze 74

l zbioru funkcji, które mogą być zastosowane do ich wystąpień. Typ opisuje obiekty o tych samych charakterystykach, to znaczy strukturę danych obiektów. Typy mogą być deklarowane jako podtypy innych typów. Podtyp dziedziczy wszystkie funkcje swojego nadtypu. W przypadku dziedziczenia wielokrotnego konieczne jest rozwiązanie konfliktu nazw (można zastosować nazwy kwalifikowane). Podtyp zwykle opisuje bardziej ograniczony zbiór elementów niż nadtyp, ale może także zawierać bardziej szczegółowe informacje. Obiekty mogą być jednocześnie wystąpieniami różnych typów. Nazywa się to wielokrotnym występowaniem w typach (ang. multiple type instantiation). Typ jest zdefiniowany przez nazwę i zbiór funkcji aplikacyjnych. Zbiór ten jest sumą funkcji definiowanych jawnie dla danego typu oraz funkcji dziedziczonych od nadtypów. Funkcje są abstrakcją atrybutów i związków klasycznego modelu relacyjnego. Są one zdefiniowane przez nazwę, typ dziedziny i zakresu oraz mogą być jedno- lub wielowartościowe. Funkcja jednowartościowa przyporządkowuje obiektom pojedynczą wartość, a funkcja wielowartościowa przyporządkowuje im zbiór. Dziedziną funkcji jest zbiór wszystkich obiektów, które są wystąpieniami definiowanego typu. Typ zakresu funkcji jest standardowy (string, integer, real, boolean) lub abstrakcyjny. Można także definiować funkcje odwrotne, co jest istotne przy zachowaniu integralności bazy danych.

Przykład 6.1. Poniżej przedstawiono opis szpitala przy zastosowaniu modelu COCOON. type Wydział isa Ohject = Nazwa: string, Kierownik: Pracownik, Personel: set of Pracownik inverse Pracuje_dla, Zajmuje: set ot Sala inverse Należy_do;

--^

type Klinika isa Wydział = Leczy: set of Pacjent inverse Jest_leczony; type Sala isa Object Numer, integer, Należyjło: Wydział inverse Zajmuje;

*

type Osoba isa Object = Nazwisko: string, Wiek: integer, Dzieci: set of Osoba;

75

type Pracownik isa Osoba = Zarobki: integer, Stanowisko: string, Pracuje_dla: Wydział inverse Personel',

\v»- ?fci fj-

type Lekarz isa Pracownik = Specjalność: string, Tytuł: string:, type Pacjent isa Osoba = Numer_karty: integer, Jestjeczony: Klinika inverse Leczy, Przed_operacją: boolean, Po_pperacji: boolean', Opis ten zawiera osiem typów obiektów. Objęć t jest typem najbardziej ogólnym 5 leży na szczycie hierarchii (rys. 6.1). Każdy obiekt w bazie danych jest jego wystąpieniem. Trzy typy: Wydział, Osoba oraz Sala są bezpośrednimi podtypami typu Object. Typ Osoba ma dwa podtypy: Pracownik oraz Pacjent. Funkcje: Nazwa, Numer, Nazwisko, Wiek, Zarobki, Stanowisko, Specjalność, Tytuł, Numer_karty, Przed_operacją oraz Po_operacji mają standardowe typy zakresów. Typy zakresów funkcji: Kierownik, Należy_do, Pracuje_dla i Jestjeczony są abstrakcyjne (odpowiednio: Pracownik, Wydział, Wydział i Klinika). Wartościami funkcji: Personel, Zajmuje, Leczy i Dzieci są zbiory obiektów o typach abstrakcyjnych (odpowiednio: Pracownik, Sala, Pacjent i Osoba). Funkcje Personel i Pracuje jłla są względem siebie odwrotne. Ich wartości odpowiadają sobie. Wystąpienie typu Pracownik należy do zbioru wystąpień, który jest wartością funkcji Personel typu Wydział. W momencie przesunięcia pracownika na inny wydział wartość funkcji Pracuje_dla musi zostać zmieniona, co pociąga za sobą zmianę wartości funkcji Personel. Odwrotne względem siebie są także pary funkcji: Zajmuje i Należy jło oraz Leczy \ Jestjeczony. Klasy są zbiornikami (ang. containers) dla obiektów danego typu i są ściśle odróżniane od typów. Tworzą one hierarchię klas, na której szczycie znajduje się klasa Objects. Należą do niej wszystkie obiekty bazy danych. Obiekty danej klasy są zawarte w jej nadklasach lub, mówiąc inaczej, klasa zawiera co najmniej te elementy, które są zawarte w jej podklasach. Zawartość klasy jest zbiorem obiektów nazywanych jej członkami. Obiekty mogą jednocześnie należeć do różnych klas. Nazywa się to wielokrotną przynależnością do klas (ang. multiple class membership). Dla każdej klasy można zdefiniować predykat, który musi być spełniony przez każdy należący do niej obiekt. Jeśli predykat definiuje warunek zarówno konieczny, jak i dostateczny przynależności obiektu do danej podklasy, to trzeba w jej definicji użyć słowo kluczowe all. Inne słowo kluczowe some wskazuje na warunek konieczny. Odpowiednio do tego rozróżnia się all- i sowe-klasy. All-klasy zawierają wszystkie obiekty swoich nadklas, które spełniają predykat. Członkowie some-klas muszą być jawnie do nich dodani. Takie obiekty są gromadzone w zbiorze Pmemb (członkowie potencjalni). Dla każdej klasy jest definiowany zbiór klas bazowych. &>me-klasa jest swoją klasą bazową. Dla a//-klasy zbiór klas bazowych składa się ze wszystkich some-klas, z których ta a//-klasa pochodzi. Obiekt należy do klasy, jeśli spełnia jej predykat, jest członkiem potencjalnym klas bazowych i nadklas, a jego typ jest taki sam, jak typ klasy. Obiekt może należeć do zbioru Pmemb nie spełniając predykatu klasy lub nie mając odpowiedniego typu. Nie należy wtedy do klasy, aż do momentu spełnienia tych warunków. Definicja klasy zawiera nazwę klasy, typ członków, nazwy nadklas i opcjonalnie predykat klasy. Dla podanej wyżej hierarchii typów można zdefiniować następujące klasy:

'* "

cłass Wydziały: Wydział some Objects; class Kliniki: Klinika some Wydziały, class Sale: Sala some Objects; class Osoby: Osoba some Objects; class Pacjenci: Pacjent some Osoby; class Pac_przedj3per. Pacjent some Pacjenci where Przed_operacją = true; class Pacjpo_oper: Pacjent all Pacjenci where Po_operacji = true; class Pracownicy: Pracownik some Osoby; class Kierownicy: Pracownik all Pracownicy where Stanowisko = 'Kierownik?; class Lekarze: Lekarz some Pracownicy; ciass Kierownicy Jdinik: Lekarz all Lekarze where Stanowisko = 'Kierownik1; class Profesorowie: Lekarz all Lekarze where Tytuł - 'Profesor1;

Hierarchia zawiera 13 klas (rys. 6.2). Klasa Pacjprzed_oper jest podklasą klasy Pacjenci z tym samym typem członkowskim Pacjent. Jej zawartością jest podzbiór klasy Pacjenci. Predykat w definicji klasy Pac_przed_oper jest warunkiem koniecznym. Zatem nie wszyscy pacjenci, którzy są badani i których stan zdrowia jest obserwowany należą do klasy Pacjrzedjiper. Gdy podejmowana jest decyzja o operacji obiekt musi być w sposób jawny dodany do tej klasy. Ponadto musi być spełniony warunek konieczny. Definicje klas: Wydziały, Kliniki, Sale, Osoby, Pacjenci, Pracownicy oraz Lekarze nie zawierają predykatów. Są to some-khsy (np. nie wszystkie wydziały są klinikami).

i Predykat w definicji klasy Kierownicy Jdinik sprawia, że wszyscy lekarze (to znaczy obiekty należące do klasy Lekarze), którzy go spełniają są również jej członkami. Zatem jest to warunek zarówno konieczny, jak i dostateczny. Podobna sytuacja występuje w klasach: Pac_po_oper, Kierownicy oraz Profesorowie. Obiekt może być nazywany za pomocą zmiennych. Użycie zmiennych umożliwia odwoływanie się do obiektów i do wyników różnych wyrażeń (kwerendy, operacje aktualizujące).

Rys. 6.2. Hierarchia klas

6.2. Uogólnione operacje aktualizujące Operacje aktualizujące języka COOL obejmują: a) zmianę wartości funkcji, na przykład set [Zarobki: =3000] (P), Operacja ta określa zarobki pracownika oznaczonego zmienną P. b) uzyskiwanie i tracenie własności typów, na przykład gain [Lekarz] (P), lose [Lekarz] (P). Operacje te umożliwiają ruch obiektu w hierarchii typów. Utworzenie nowego obiektu jest podzielone na dwie operacje:

77

newCP)

gain [Lekarz] (P). , r„,„„^>s

oraz

^

^«£
Zlikwidowanie istniejącego obiektu może być wykonane za pomocą operacji lose, na przykład. lose [Objęci] (P).

, ..

,,,' . .,

H

Obiekt oznaczony przez P nie jest już wystąpieniem najbardziej ogólnego typu Objęci, co oznacza, że P nie istnieje. c) dodawanie obiektów do klas, na przykład

, «

.fi»'ir„-,>

j

•dd [F] (Le*arw). cl.^ d) usuwanie obiektów z klas, na przykład

*

~ ,. ""**>„ -

'•

"

Bll

° ™*--e.fc

remove [P] (Lekarze).

~"""'

Semantyka powyższych operacji jest definiowana tak, że charakterystyczne dla modelu warunki integralności, takie jak przynależność do klas, hierarchia klas i typów oraz predykaty klas są spełnione automatycznie.

6.3. Warunki integralności

rr

łV

.«

Przy implementacji modelu COCOON na profesjonalnym systemie baz danych można dla zapewnienia integralności wykorzystać mechanizm wyzwalaczy (ang. trigger). W systemie INGRES są one także nazywane regułami aktywnymi (ang. active ruleś) [13]. Mechanizm ten inicjuje akcje, gdy stan bazy danych ulega zmianom. Odpowiednio zdefiniowane reguły zawierają warunki, które są sprawdzane po wykonaniu określonych operacji aktualizujących. Następnie zostają wywołane procedury zapewniające utrzymanie zgodności bazy danych. W modelu COCOON muszą być spełnione następujące warunki integralności: ; • • • •

Wartością funkcji nie może być obiekt, który nie jest wystąpieniem typu zakresu tej funkcji; Obiekt danego typu musi posiadać wszystkie cechy swoich nadtypów; Członek danej klasy musi być wystąpieniem typu tej klasy; ^ Członek danej klasy musi być członkiem wszystkich jej nadklas i spełniać wszystkie konieczne predykaty.

Z tych więzów wynikają reguły, które muszą być sprawdzone przy operacjach aktualizujących. Pierwsze trzy reguły są sformułowane dla operacji lose. Jeśli obiekt traci cechy typu, to musi: • • •

stracić wszystkie cechy swoich podtypów - reguła REG1; być usuniętym z dziedziny i zakresu odpowiednich funkcji - reguła REG2; być usuniętym ze wszystkich klas i zmiennych tego typu - reguła REG3.

Regułę dla operacji gain można sformułować następująco: •

jeśli obiekt uzyskuje cechy typu, to musi uzyskać wszystkie cechy wszystkich swoich nadtypów - reguła REG4.

Warunkiem wykonania operacji set jest zgodność odpowiednich typów, czyli: •

przy zmianie wartości funkcji należy sprawdzić czy odpowiednie obiekty mają właściwy typ (sprawdzenie dziedziny i zakresu) -reguła REG5.

Warunki dla operacji add oraz remove wymagają przetwarzania hierarchii klas:

' ' "" * *

•

jeśli obiekt jest usuwany z klasy (operacja remove), to musi być usunięty ze wszystkich swoich podklas - reguła REG6. • jeśli obiekt jest dodawany do klasy (operacja add), to musi: .-.„,., •„>•;.•-£, 1. 2.

mieć cechy typu tej klasy - reguła REG7; być dodany do wszystkich jej nadklas i o//-klas - reguła REG8.

6.4. Odwzorowanie modelu COCOON na model relacyjny Definicja schematu bazy danych jest przedstawiona za pomocą zbioru relacji. Nazwa relacji utworzonej dla typu niestandardowego jest konkatenacją litery 'T1 i nazwy typu, do której również dodano literę T. Jest to główna tablica

m

l

typu. Jej kluczem jest identyfikator obiektu zwany OBJJD, a jej atrybutami są poszczególne funkcje standardowe typu. Wszystkie typy są także rejestrowane w relacji TTypeT (OBJJD, TypeName), gdzie OBJJD oznacza identyfikator typu. Hierarchia typów jest opisana w relacji TTypeTSubType (TypeTl, TypeT2). Oba atrybuty są identyfikatorami odpowiednio nadtypu i podtypu. Transformacja funkcji zależy od ich zakresu. Funkcje z zakresem standartowym są atrybutami głównej tablicy typu. Dla każdej funkcji, której wartością jest wystąpienie typu abstrakcyjnego i dla funkcji wielowartościowych konieczne jest utworzenie dodatkowej relacji bieżącej. Jej nazwa jest konkatenacją litery T, nazwy typu i nazwy funkcji. W przypadku funkcji wielowartościowej może istnieć więcej niż jedna krotka dla danego obiektu. Atrybutami relacji łączącej są OBJJD obiektu, do którego odnosi się krotka (dziedzina funkcji) oraz OBJJD obiektu, który jest wartością funkcji (zakres funkcji). Nazwa pierwszego atrybutu jest taka sama jak nazwa typu. Drugi atrybut nazywa się Residt.

t TTypeTSubType

TTypeT OBJJD

TypeName

TypeTl

TypeT2

11 12 13 14 15 16 17

ObjectT WydziałT

11 11 11 12 13 13 16

12 13 14 15 16 17 18

18

OsobaT SalaT KlinikaT PracownikT PacjentT LekarzT Rys. 6.3. Relacje rejestrujące typy

Każda funkcja musi być opisana dokładniej. Relacja TFunctionT (OBJJD, FunctionName, Setof) zawiera informację o typie zakresu. Dla funkcji wielowartościowej atrybut Setof jest równy l, dla funkcji jednowartościowej wynosi 0. OBJJD oznacza identyfikator funkcji. Dziedzina funkcji (typ, do którego się ona stosuje) i zakres (typ wyniku) są pamiętane w relacjach TFunctionTDomain (FunctionT, TypeT) oraz TFunctionTRange (FunctionT, TypeT), gdzie FunctionT i TypeT oznaczają odpowiednio identyfikatory funkcji i typu. Funkcje odwrotne są rejestrowane w relacji TFunctionTbwerse (FunctionTl, FunctionT2). Oba atrybuty są identyfikatorami odpowiednich funkcji. Tylko jedna funkcja na parę funkcji jest wprowadzana do relacji. Dla drugiej funkcji tworzona jest perspektywa na podstawie odpowiedniej relacji łączącej. W ten sposób zapewniona jest zgodność obu funkcji odwrotnych przy operacjach aktualizujących. Główne charakterystyki każdej klasy są zawarte w relacji TClassT (OBJJD, ClassName, Selektor, Predykat), która zawiera jedną krotkę dla każdej klasy. Selektor wskazuje czy dany predykat (jeżeli występuje) określa warunek konieczny (some-klasy), czy też zarówno konieczny, jak i dostateczny (a//-klasy). Dla some-klas selektor jest równy O, a dla a//-klas wynosi 1. Hierarchia klas jest opisana w relacji TClassTSubClass (ClassTl, ClassT2). Oba atrybuty są identyfikatorami odpowiednio nadklasy i podklasy. Relacja TClassTElementType (ClassT, TypeT) opisuje związek między klasami i typami. Zbiór członków potencjalnych jest pamiętany w relacji TPmembers (ClassJD, OBJJD). Wszystkie klasy bazowe danej klasy są zebrane w relacji TBases (ClassJD, BaseJD). Dla przykładu danego w punkcie 6.1 powinny zostać utworzone następujące relacje: Relacje typów: TWydzialT(OBJJD,Nazwa); ' r , .' :; ;: r T i,> TKlinikaT (OBJJD); ^ ; TSalaT(OBJJD,Numer); ,« ,„ . . ,,r TOsobaT (OBJJD, Nazwisko, Wiek); TPracownikT (OBJJD, Zarobki, Stanowisko); TLekarzT (OBJJD, Specjalność, Tytuł); TPacjentT (OBJJD, Numerjcarty, Przed_operacją, Po_operacji). Relacje łączące: • •

TWydziałTKierownik (WydziałT, Result); TSalaTNależy_do (SalaT, Result);

79

• •

•

' * *T.t*

TOsobaTDzieci (OsobaT, Result); TPracownikTPracuje dla (Pracownik!, Result) ;

TPacjentTJestJeczony (PacjentT, Result).

Dla funkcji: Personel, Zajmuje oraz Leczy powinny zostać utworzone perspektywy. Zawartość relacji rejestrujących typy, funkcje oraz klasy została przedstawiona na rysunkach 6.3, 6.4 oraz 6.5.

TFunctionTInverse

TFunctionT

OBJJD

FunctionName

Setof

FunctionTl

FunctionTl

21 22 23

Kierownik

22 23

27 25

Zajmuje

0 1 1

24

28

24 25 26 27 28

Leczy NależyJDo

0

Personel

1

Dzieci

1

Pracuje_Dla

0 0

Jest Leczony

TFunctionTRange

TFunctionTDomain

FunctionT

TypeT

FunctionT

TypeT

21 22 23 24 25 26 27 28

12 12 12 15 14 13 16 17

21 22 23 24 25 26 27 28

16 16 14 17 12 13 12 15

Rys. 6.4. Relacje rejestrujące funkcje

6. 5. Tworzenie reguł i procedur Celem zapewnienia integralności danych trzeba utworzyć reguły, które spowodowałyby wykonanie odpowiednich procedur tak, aby opisane w punkcie 6.3 warunki były spełnione. Reguły REGl, REG2 oraz REG4 dotyczą zmiany typu obiektu. Odpowiadające im procedury muszą działać na relacjach, których atrybuty są identyfikatorami typów. Reguły i procedury muszą być utworzone dla każdego typu. Procedura odpowiadająca regule REGl powinna usunąć obiekt ze wszystkich relacji głównych wszystkich podtypów typu obiektu. Dlatego dla każdego podtypu jest generowana procedura zawierająca następujące polecenie SQL-a: DELETE FROM WHERE OBJJD = :obj ; Reguła REG2 dotyczy funkcji. Jeśli obiekt traci typ, to musi być usunięty ze wszystkich relacji łączących, w których ten typ występuje jako dziedzina lub zakres. Odpowiednia procedura musi zatem dla każdej relacji łączącej zawierać jedno z następujących poleceń SQL-owskich: DELETE FROM WHERE = :obj DELETE FROM WHERE Result = :obj . 80

lub

Procedura dla reguły REG4 musi wprowadzić obiekt do głównych relacji wszystkich nadtypów typu obiektu. Celem uniemożliwienia dublowania obiektów należy sprawdzić czy obiekt był już wprowadzony. Dla każdego nadtypu tworzona jest następująca procedura: SELECT COUNT (*) INTO :cnt FROM WHERE OBJJD = :obj; IF (:cnt = 0) THEN INSEKT INTO (OBJJD) YALUES (:obj); ENDIF ; TclassT OBJJD

ClassName

Selektor

31 32 33 34

Object Wydziały Osoby Sale

0 0

35 36 37 38 39 40 41 42 43

Kliniki Pracownicy Pacjenci Lekarze Kierownicy

TClassTSubClass

CIassTl 31 31 31 32 33 33 36 36 38 38 37 37

ClassT2 32 33 34 35 36 37 38 39 40 41 42 43

Predykat

0 0 0 0 0 0

1 1 ]

Kierownicy Jdlinik Profesorowie Pac_przed_oper Pacj)o_oper

0

1

TCłassTElementType

ClassT 31 32 33 34 35 36 37 38 39 40 41 42 43

TypeT 11 12 13 14 15 16 17 18 16 18 18 17 17

Stanowisko = 'Kierownik' Stanowisko = 'Kierownik' Tytuł = 'Profesor1 Obserwacja = true Po_pperacji = true TBases

ClassJD 31 32 33 34 35 36 37 38 39 40 41 42 43

BaseJD 31 32 33 34 35 36 37 38 36 38 38 42 37

Rys. 6.5. Relacje rejestrujące klasy

Przy wprowadzaniu obiektu do relacji umieszczany jest tylko jego OBJJD. Wartości innych atrybutów są nieznane i system wstawia wartość NULL.

81

Procedura dla reguły REG5 (operacja set) sprawdza czy oba odpowiednie obiekty istnieją. Powinny one występować w głównej relacji typu dziedziny lub zakresu. Dla wszystkich funkcji w relacji TFunctionT i nie istniejących w relacji TFunctionTInverse generowana jest następująca procedura: SELECT COUNT(*) INTO :cntl FROM WHERE OBJJD = :objl; SELECT COUNTH INTO :cnt2 FROM WHERE OBJJD = :obj2; , IF (:cntl = 0) OR (:cnt2 = 0) THEN RAISE ERROR 13 "Obiekt nie istnieje"; ENDIF ;

~ (

.^.i,-*

,

'*

Celem określenia nazw typów dziedzin i zakresów trzeba znaleźć ich identyfikatory, które są pamiętane w relacjach odpowiednio TFunctionTDomain i TFunctionTRange, a następnie przeszukać relację TTypeT. Ograniczenie do funkcji nie występujących w relacji TFunctionTinverse zapobiega dublowaniu definiowania reguł. Implementacja operacji add oraz remove jest bardziej złożona. Operacja add jawnie wprowadza obiekty do klasy, lub bardziej dokładnie, do zbioru członków potencjalnych jej klas bazowych. Wykonanie operacji: ''

add [P] (Pac_przed_oper).

't^?

i

r/"~"~

spowoduje włączenie obiektu oznaczonego przez P do klasy Pacj>rzed_oper, jeśli obiekt ten posiada typ tej klasy (Pacjent) oraz jeśli jest spełniony warunek konieczny przynależności, to znaczy wartość funkcji Przedjjperacją wynosi tnie. W przeciwnym wypadku jedynym efektem powyższej operacji będzie włączenie obiektu P do zbioru Pmemb. Jednakże, jeśli później funkcja Przed operacją przyjmie wartość true, obiekt typu Pacjent zostanie włączony do klasy Pacj)rzed_oper automatycznie. Zgodnie z regułą REG7 warunkiem przynależności do klasy jest uzyskanie cech jej typu. Z drugiej strony, jeśli obiekt traci cechy typu klasy, przestaje być jej członkiem - reguła REG3. Obie wspomniane reguły są zatem spełnione. Informacje o członkach potencjalnych różnych klas są zawarte w relacji TPmembers. Jednym z jej atrybutów jest identyfikator klasy bazowej. Celem wykonania operacji add trzeba przeszukać relację TBases i dla każdej klasy bazowej wprowadzić obiekt do relacji TPmembers. Reguła REG8 wymaga również jawnego dodania obiektów do nadklas. Identyfikatory nadklas każdej klasy bazowej można odszukać na podstawie relacji TClassTSubClass. Przed wprowadzeniem obiektu do klasy konieczne jest sprawdzenie czy już on w tej klasie istnieje. Algorytm odpowiadający operacji remove jest podobny. Jednakże reguła REG6 nie wymaga dodatkowych operacji. Usuniecie obiektu z podklas nie jest potrzebne, ponieważ członkowie danej klasy muszą być członkami jej nadklas. Dlatego algorytm powinien jedynie usunąć obiekt z relacji TPmembers dla każdej klasy bazowej. Opisana implementacja umożliwia propagację operacji aktualizujących zgodnie z ogólnymi regułami opartymi na więzach strukturalnych występujących w modelu. Semantyka operacji aktualizujących jest zdefiniowana w ten sposób, że charakterystyczne dla modelu warunki integralności mogą być spełnione automatycznie. Założeniem tej semantyki jest dynamiczna reklasyfikacja podczas operacji aktualizujących, która jest konieczna, ponieważ obiekty mogą dynamicznie zmieniać typy i klasy podczas swojego istnienia. , ,

i

82

r-

Literatura

1.

Catteł R.: Object Data Management: Addison-Wesley, Reading, MA, 1991.

Object-Oriented

and Extended Relational

Database

Systems,

2. Codd E.: A Relational Model for Large Shared Data Banks, Comm. ACM 1970, vol. 13, no 6. 3.

Datę C.: Wprowadzenie do baz danych, WNT, Warszawa 2000.

4.

Delobd C., Miłm M.: Relacyjne bazy danych, WNT, Warszawa 1989.

5.

Kim W.: Wprowadzenie do obiektowych baz danych, WNT, Warszawa 1996.

6.

Levene M.: The Nested Unwersal Relation Database Model. Springer-Yerlag, Berlin Heidelberg 1992.

7.

Lochovsky F., Tsichiritzis D.: Modele danych, WNT, Warszawa 1982.

8.

Martin J.; Organizacja baz danych, PWN, Warszawa, 1983.

9. Muraszkiewicz M, Rybiński H.: Bazy danych, Akademicka Oficyna Wydawnicza RM, Warszawa 1993. 10. Roth M., Korth H,, Silberschatz A.: Extended Algebra andCalculusfor Nested Relational Databases, ACM Transactions on Database Systems 1988, vol 13, no 3. 11. Scholl M., Laasch C., Rich C., Schek H., Tresch M.: The COCOON Object Model. Technical Report, ETH Zurich, Dept. of Computer Science, 1990. 12. Smith J., Smłth D.: Database Abstraction: Aggregation and Generalization, ACM Transactions on Database Systems, 1977, Vol 2, no2. 13. Subieta K.: INGRES. System Zarządznia Relacyjną Bazą Danych, Akademicka Oficyna Wydawnicza PLJ, Warszawa 1994. 14. Ullman J.: Systemy baz danych, WNT, Warszawa 1988. 15. Ullman J., Widom J.: Podstawowy wykład z systemów baz danych, WNT, Warszawa 2000. 16. Welleslay Software: SQL Język relacyjnych baz danych. WNT, Warszawa 1995. 17. Yourdon E.: Współczesna analiza strukturalna, WNT, Warszawa 1996.

l

83