Bazy Danych II TOM 1

BAZY DANYCH II TOM I: NIEZWYKŁA PODROZ

OPRACOWAŁ FOXER 1

Od autora opracowania W tomie tym znajduje się głównie ogólna teoria dotycząca budowy bazy danych oraz jej projektowania (związki encji, transformacje). Na końcu garść informacji dotycząca bardziej fizycznej budowy, czyli organizacja plików. Nic konkretnego, a jednak zajmuje paręnaście stron.

Spis treści 1

2

3

4

5

Relacyjny model danych .................................................................................................................. 3 1.1

Ogólnie o relacjach .................................................................................................................. 3

1.2

Klucze....................................................................................................................................... 3

1.3

Operacje na relacjach .............................................................................................................. 3

1.4

Operacje połączenia (JOIN) ..................................................................................................... 4

Model związków encji ..................................................................................................................... 6 2.1

Encja ........................................................................................................................................ 6

2.2

Związki encji............................................................................................................................. 6

Transformacja ER do modelu relacyjnego ....................................................................................... 8 3.1

Transformacja encji ................................................................................................................. 8

3.2

Transformacja związków ......................................................................................................... 8

3.3

Transformacje hierarchii encji ................................................................................................. 8

3.4

Transformacja związków wyłącznych ...................................................................................... 8

Normalizacja schematów logicznych relacji .................................................................................... 9 4.1

Zależności funkcyjne................................................................................................................ 9

4.2

Proces normalizacji .................................................................................................................. 9

4.3

Zależności wielowartościowe ................................................................................................ 10

4.4

Postaci normalne ................................................................................................................... 10

Organizacja rekordów w blokach .................................................................................................. 12 5.1

Rodzaje organizacji rekordów w blokach .............................................................................. 12

5.2

Zarządzanie rozmiarem bloku danych................................................................................... 12

5.3

Operacje na rekordach .......................................................................................................... 12

5.4

Rodzaje organizacji plików .................................................................................................... 13

5.4.1

Plik nieuporządkowany.................................................................................................. 13

5.4.2

Plik uporządkowany....................................................................................................... 13

5.4.3

Plik haszowy .................................................................................................................. 14

2

1 Relacyjny model danych 1.1 Ogólnie o relacjach Objaśnienie pojęć: • Baza danych = zbiór relacji • Schemat bazy danych = zbiór schematów relacji • Schemat relacji = zbiór {atrybut, dziedzina,[ograniczenia integralnościowe]} • Relacja = zbiór krotek • Krotka = lista wartości atomowych Relacja posiada następujące cechy: • każdy atrybut relacji ma unikalną nazwę, • porządek atrybutów w relacji nie jest istotny, • porządek krotek w relacji nie jest istotny i nie jest elementem definicji relacji, • wartości atrybutów są atomowe (elementarne), • relacja nie zawiera rekordów powtarzających się. Ograniczenie integralnościowe: • klucz podstawowy (primary key) • klucz obcy (foreign key) • unikalność (unique) • zawężenie domeny/dziedziny (check) • wartość pusta/niepusta (NULL/NOT NULL)

1.2 Klucze Klucz podstawowy relacji (ang. primary key) jest to atrybut lub zbiór atrybutów, którego wartość jednoznacznie identyfikuje krotkę relacji. Z definicji, wartość atrybutu, który zdefiniowano jako klucz podstawowy jest unikalna w obrębie całej relacji i jest niepusta. Klucz obcy relacji (ang. foreign key) jest atrybutem lub zbiorem atrybutów, który wskazuje na klucz podstawowy w innej relacji. Klucz obcy służy do reprezentowania powiązań między danymi (łączenia relacji). Dziedziną wartości klucza obcego jest dziedzina wartości klucza podstawowego, na który ten klucz obcy wskazuje.

1.3 Operacje na relacjach SELEKCJA (SELECT *) Operacja selekcji umożliwia wyodrębnienie podzbioru krotek relacji, które spełniają warunek selekcji. Notacja: σ (). Predykaty są łączone operatorami logicznymi: AND lub OR. PROJEKCJA (PROJECT, czyli SELECT a1, a2…) Umożliwia ona wyodrębnienie (wybór) tylko określonych atrybutów relacji. Notacja: π () Żeby wybrać konkretne atrybuty spełniające warunek selekcji: π( σ ()) KOMPATYBILNOŚC RELACJI Dwie relacje są kompatybilne jeśli mają ten sam stopień i dziedziny odpowiadających sobie atrybutów są takie same.

3

SUMA RELACJI (UNION) Wynikiem tej operacji, oznaczanej przez R SUMA S, jest relacja zawierająca wszystkie krotki, które występują w R i wszystkie krotki, które występują w S, z wyłączeniem duplikatów krotek. UNION ALL nie odrzuca duplikatów, UNION filtruje i odrzuca duplikaty. ILOCZYN RELACJI (INTERSECT) Wynikiem tej operacji, oznaczonej przez R ILOCZYN S, jest relacja zawierająca krotki występujące zarówno w R i S. RÓŻNICA (MINUS) Wynikiem tej operacji, oznaczonej przez R-S, jest relacja zawierająca wszystkie krotki, które występują w R i nie występują w S

1.4 Operacje połączenia (JOIN) Operacja połączenia umożliwia łączenie wybranych krotek z dwóch relacji w pojedynczą krotkę. Notacja: operacja połączenia relacji R(A1, ..., An) i S(B1, ...,Bm), jest oznaczona jako: R S gdzie: • warunek połączeniowy jest zbiorem predykatów połączonych operatorami logicznymi AND • predykaty są postaci: Ai θ Bj o Ai i Bj są atrybutami połączeniowymi o Ai jest atrybutem R, Bj jest atrybutem S o dom(Ai) = dom(Bj), o θ jest operatorem relacyjnym ze zbioru { =, ≠, <, ≤, >, ≥ } Rodzaje łączeń wewnętrznych: • Iloczyn kartezjański (Cross join) • Samozłączenie (Self Join) • Równozłączenie (Equi-join) • Naturalne (Natural Join) • Theta, nierównozłączenia (Theta Join) • Antyzłączenia (Anti join) • Częściowe (Semi Join) Rodzaje połączeń zewnętrznych: • Left outer Join • Right outer Join • Full outer Join Złączenie typu INNER JOIN SELECT kolumna1, kolumna2 FROM tabela1 [INNER] JOIN tabela2 ON wyrażenie_warunkowe W zapytaniu słowo INNER jest opcjonalne. W wyniku tego złączenia pojawią się tylko te wiersze z tabela tabela1 i tabela2, które spełnią warunki wymienionie po klauzuli ON. Jest ona odpowiednikiem znanej instrukcji: SELECT kolumna1, kolumna2, ...,kolumnaN FROM tabela1, tabela2, ...,tabelaN WHERE warunki; Złączenie typu SELF JOIN O złączeniu Self JOIN mówimy, gdy po lewej i prawej stronie złączenia występuje ta sama tabela. W tym typie złączeń za niezbędne uważa się użycie aliasów. SELECT d1.nazwa, d2.nazwa FROM dzialy d1 JOIN dzialy d2 USING (adres) WHERE d1.nazwa != d2.nazwa; 4

Złączenie typu Equi-JOIN Tak naprawdę jest to prawie każde złączenie które do tej pory rozpatrywaliśmy. Charakteryzuje się tym, że w warunku złączenia (czy to występującym w klauzuli ON czy też w warunku WHERE) występuje zwykły znak równości Złączenie typu NATURAL JOIN Notacja: Oznaczamy je jako R*S (wyjątek) Ze złączeniem naturalnym mamy do czynienia, gdy obie kolumny występujące w warunku łączącym są tej samej nazwy. W przypadku tego typu złączenia możemy stosować jedną z czterech możliwych notacji. Najczęściej polecaną notacją jest JOIN ... USING, zaś najbardziej odradzaną jest notacja „NATURAL JOIN” gdyż może się trafić sytuacja gdy będzie więcej dopasowań kolumn o tej samej nazwie niż jedna. SELECT p.imie, p.nazwisko, d.nazwa FROM pracownicy p JOIN dzialy d USING (id_dzialu); SELECT imie, nazwisko, nazwa FROM pracownicy p NATURAL JOIN dzialy d; Złączenie typu Theta Join (u nas: NON-EQUI JOIN) Drugą stroną medalu dla równozłączeń są nierównozłączenia. Tym określeniem oznacza się złączenia w których w warunku występuje inny symbol porównania wartości niż =, np. >, BETWEEN, != Złączenie typu Anti Join Jest to szczególny przypadek nierównozłączeń, w którym łącznikiem jest operator != Złączenie typu Semi Join O złączeniu częściowym mówimy, kiedy w klauzuli SELECT danego złączenia wymieniamy kolumny tylko z jednej z tabel. Ten typ złączenia służy głównie jako sposób filtrowania informacji. Zamiast tego typu często w tym samym celu stosuje się podzapytania. Złączenie typu CROSS JOIN Złączenie CROSS JOIN jest to tzw. złączenie krzyżowe, którego ogólna postać wygląda następująco: SELECT kolumna1, kolumna2, ..., kolumnaN FROM tabela1 CROSS JOIN tabela2; Wykonuje ono iloczyn kartezjański na podstawie łączonych tabel, inaczej mówiąc łączy każdy wiersz tabeli tabela1 z każdym wierszem tabeli tabela2. Jest ona odpowiednikiem znanej instrukcji: SELECT kolumna1, kolumna2, ...,kolumnaNFROM tabela1, tabela2 Złączenie typu LEFT OUTER JOIN Złączenie typu LEFT OUTER JOIN pozwala nam na uwzględnienie w wyniku danych, które nie posiadają swoich odpowiedników w złączanych tabelach. Oznacza to, że jeśli w pierwszej tabeli pojawiają się wiersze, które nie posiadają odpowiedników w drugiej tabeli to zostaną wzięte pod uwagę podczas złączenia ale puste kolumny zostaną wypełnione wartościami NULL. Słowo OUTER jest tutaj opcjonalne. Złączenie typu RIGHT OUTER JOIN Złączenie typu RIGHT OUTER JOIN działa analogicznie do LEFT OUTER JOIN ale w tabeli wynikowej uwzględnia wiersze z drugiej tabeli, które nie posiadają odpowiedników w pierwszej. Złączenie typu FULL OUTER JOIN Złączenie obustronne jest w pewnym sensie sumą złączenia lewostronnego i prawostronnego. Zawiera wszystkie wiersze obu złączonych tabel, w tym te które nie mają swoich odpowiedników.

5

2 Model związków encji Modelowanie - odwzorowanie rzeczywistych obiektów świata rzeczywistego w systemie informatycznym (bazie danych). Rodzaje: • konceptualne o reprezentacja obiektów w uniwersalnym modelu niezależnym od modelu implementacyjnego model związków-encji model UML • implementacyjne o modele wykorzystywane do implementacji modeli konceptualnych o modele danych (relacyjne, obiektowe, itp.)

2.1 Encja Reprezentuje zbiór obiektów opisany tymi samymi cechami (atrybutami, własnościami). Informacje o tych obiektach będą przechowywane w bazie danych Unikalna nazwa encji Atrybut1 (Identyfikator) Atrybut2 (Deskryptor) Atrybut3 (Deskryptor) Definicja pojedynczego atrybutu encji obejmuje: • nazwę, • dziedzinę definiującą: typ danych i maksymalny rozmiar, zbiór dozwolonych • wartości lub zakres dozwolonych wartości, • informację czy są dozwolone / niedozwolone wartości puste, • Opcjonalnie, dla atrybutu można zdefiniować unikalność wartości. Przykład: Pracownicy firmy są opisani numerem PESEL, adresem zamieszkania, pensją i opcjonalnie numerem telefonu. Pracownik # PESEL identyfikator * nazwa obowiązkowe o telefon nieobowiązkowe

2.2 Związki encji Cechy związków • Stopień związku o unarny (binarny rekursywny) , binarny, ternarny, n-arny • Typ asocjacji (kardynalność)j o jeden-do-jeden (1:1), jeden-do-wiele (1:M), wiele-do-wiele (M:N) • Istnienie (klasa przynależności) o Opcjonalny, obowiązkowy Przykład jeden-do-jeden: Posiada Pracownik

Jest własnością

Samochód

6

Obowiązkowość – kreska ciągła. Opcjonalność – kreska przerywana. Przykład jeden-do-wiele: Posiada Jest własnością Samochód Pracownik Pracownik posiada wiele samochodów (Rozdzielenie po stronie samochodów). Pracownik może nie mieć samochodów. Nie ma samochodu bez właściciela. Przykład wiele-do-wiele: Realizuje Pracownik

Realizowany przez

Projekt

Pracownik może brać udział w wielu projektach. Projekty nie istnieją bez pracowników, są realizowane przez przynajmniej jednego. Encja słaba Encja słaba nie posiada swojego identyfikatora, a jej wystąpienia mogą istnieć tylko w kontekście wystąpień encji z nią powiązanych. uczestniczy podlega Realizacja Projekt Pracownik Wynagrodzenie Identyfikatorem encji słabej są wszystkie związki, w które wchodzi ta encja. Związek wchodzący w skład identyfikatora encji jest oznaczany na diagramie jako krótka linia prostopadła do związku umieszczona przy końcu związku. Związek rekursywny podlega Pracownik

kieruje

Związek binarny rekursywny określa powiązanie pomiędzy określonym wystąpieniem encji a innym wystąpieniem tej samej encji. Tego typu związek modelujący zależności hierarchiczne musi być opcjonalnym z obu stron. W przeciwnym przypadku, powstałaby hierarchia nieskończona. Związek ternarny Związek ternarny łączy 3 encje. Jest reprezentowany jako encja mająca związek z trzema innymi. Związek wyłączny należy do Rachunek bankowy

posiada Osoba fizyczna

należy do

posiada

Osoba prawna Związki wyłączne (ang. exclusive relationships) stosuje się wtedy, gdy konkretne wystąpienie encji może w danym momencie wchodzić tylko w jeden z ze związków. Generalizacja Pracownik #PESEL *nazwisko Kontraktowy *Nr kontraktu Godzinowy *stawka Związek generalizacji określa, że pewne encje o wspólnym zbiorze atrybutów można uogólnić i stworzyć encję wyższego poziomu. Encje niższego poziomu w hierarchii generalizacji to encje specjalizacji. Encja wyższego poziomu to encja generalizacji / nadencja. 7

3 Transformacja ER do modelu relacyjnego 3.1 Transformacja encji Transformacja modelu ER jest konieczna, ponieważ jak pamiętamy jest on modelem abstrakcyjnym niezależnym od implementacji. Modelem do którego transformujemy jest model relacyjny. Jest on modelem implementacyjnym baz danych. Transformacji podlegają wszystkie obiekty modelu ER, czyli encje z atrybutami, związki i hierarchie encji. Pracownik # PESEL identyfikator * nazwa obowiązkowe o telefon nieobowiązkowe

Pracownicy PESEL PRIMARY KEY, nazwa NOT NULL, telefon NULL

3.2 Transformacja związków Samochody nrRej PRIMARY KEY marka NOT NULL idPracownika NOT NULL FOREIGN KEY

REFERENCES Pracownicy(IdPracownika)

Związek binarny 1:1 klucz obcy we wskazanej tabeli Związek unarny 1:1 klucz obcy w tej samej tabeli Związek binarny 1:M klucz obcy w tabeli po stronie "wiele" Pracownicy_Projekty IdPracownika REFERENCES Pracownicy(IdPracownika) NrProjektu REFERENCES Projekty(NrProjektu) PRIMARY KEY (IdPracownika, NrProjektu) Związek binarny M:N Związek unarny M:N

tabela tabela

3.3 Transformacje hierarchii encji • • •

Schemat 1: jedna wspólna tabela Schemat 2: dla każdej podencji tworzona tabela zawierająca atrybuty wspólne i specyficzne Schemat 3: o dla atrybutów wspólnych tworzona tabela wspólna o dla każdej podencji tworzona osobna tabela z kluczem i atrybutami specyficznymi o tabela wspólna i tabele powstałe z podencji powiązane ograniczeniami referencyjnymi W schemacie 1 tworzymy jedną tabelę, która zawiera wszystkie atrybuty swoje i z podencji. W schemacie 2 tworzymy dla każdej podencji oddzielną tabelę, która ma atrybuty swoje (podencji) i atrybuty wspólne. W schemacie 3 tworzymy jedną tabelę nadencji i wszystkie tabele podencji. Tabela nadencji ma klucze obce do każdej podencji (są NULL, w praktyce jeden klucz obcy ma wartość, reszta jest pusta – czyli nadencja ma związek tylko z jedną podencją w danej chwili). Nadencja jest wtedy encją słabą. Związek jest opcjonalny po stronie podencji.

3.4 Transformacja związków wyłącznych To samo co dla związków 1:M, z tym że mamy kilka kluczy obcych i są one opcjonalne. Alternatywnie: jedno pole jest kluczem obcym do jednej z encji powiązanych, a drugie wskazuje na typ pola powiązanego. Zależnie od jego wartości będziemy określać, z którą encją jest powiązanie. 8

4 Normalizacja schematów logicznych relacji 4.1 Zależności funkcyjne Dana jest relacja r o schemacie R. X,Y są podzbiorami atrybutów R. W schemacie relacji R, X wyznacza funkcyjnie Y, lub Y jest funkcyjnie zależny od X, co zapisujemy X Y, wtedy i tylko wtedy, jeżeli dla dwóch dowolnych krotek t1, t2 takich, że t1[X] =t2[X] zachodzi zawsze t1[Y] = t2[Y], gdzie ti[A] oznacza wartość atrybutu A krotki ti. Przykłady: • Nazwisko Adres • {Nazwisko, Towar} Cena Z pierwszej zależności funkcyjnej wynika, że adres dostawcy jednoznacznie zależy od nazwiska dostawcy. Natomiast z drugiej zależności funkcyjnej wynika, że cena towaru zależy od kombinacji atrybutów Nazwisko i Towar. Relacje które spełniają nałożone zależności funkcyjne nazywamy instancjami legalnymi. Zależność funkcyjna jest własnością schematu relacji R, a nie konkretnego wystąpienia relacji Zbiór atrybutów Y jest w pełni funkcyjnie zależny od zbioru atrybutów X w schemacie R, jeżeli X Y i nie istnieje podzbiór X’ ⊂ X taki, że X’ Y. Zbiór atrybutów Y jest częściowo funkcyjnie zależny od zbioru atrybutów X w schemacie R, jeżeli X Y i istnieje podzbiór X’ ⊂ X taki, że X’ Y. Zbiór atrybutów Y jest przechodnio funkcyjnie zależny od zbioru atrybutów X w schemacie R, jeżeli X Y i istnieje zbiór atrybutów Z, nie będący podzbiorem żadnego klucza schematu R taki, że zachodzi X Z i Z Y.

4.2 Proces normalizacji Proces normalizacji relacji można traktować jako proces, podczas którego schematy relacji posiadające pewne niepożądane cechy są dekomponowane na mniejsze schematy relacji o pożądanych własnościach. Musi posiadać trzy dodatkowe własności: • Własność zachowania atrybutów - żaden atrybut nie zostanie zagubiony w trakcie procesu normalizacji • Własność zachowania informacji - dekompozycja relacji nie prowadzi do utraty informacji • Własność zachowania zależności - wszystkie zależności funkcyjne są reprezentowane w pojedynczych schematach relacji NADKLUCZ (SUPERKLUCZ) Zbiór atrybutów S ⊆ R, który jednoznacznie identyfikuje wszystkie krotki relacji r o schemacie R. W żadnej relacji r o schemacie R nie istnieją dwie krotki t1, t2 takie, że t1[S] = t2[S]. KLUCZ K Minimalny nadklucz (nie istnieje K’ ⊂ K będący nadkluczem schematu R) Rodzaje kluczy: • Podstawowy (PRIMARY) • Drugorzędny (SECONDARY) Atrybuty: • Podstawowe – należą do któregokolwiek z kluczy • Wtórne – nie należą do żadnego klucza 9

4.3 Zależności wielowartościowe Oznaczamy je X Y. Zależność wielowartościowa występuje w relacji r(R) nie dlatego, że na skutek zbiegu okoliczności tak ułożyły się wartości krotek, lecz występuje ona dla dowolnej relacji r o schemacie R dlatego, że odzwierciedla ona ogólną prawidłowość modelowanej rzeczywistości. Wystąpienie zależności wielowartościowej X Y w relacji o schemacie R = XYZ wyraża dwa fakty: • związek pomiędzy zbiorami atrybutów X i Y; • niezależność zbiorów atrybutów Y, Z; zbiory te są związane ze sobą pośrednio poprzez zbiór atrybutów X. Zależność wielowartościowa X →→ Y w relacji r(R) nazywamy zależnością trywialną, jeżeli • zbiór Y jest podzbiorem X, lub • X∪Y=R

4.4 Postaci normalne Pierwsza postać normalna 1NF Schemat relacji R znajduje się w pierwszej postaci normalnej(1NF), jeżeli wartości atrybutów są atomowe (niepodzielne). Pierwsza postać normalna zabrania definiowania złożonych atrybutów, które są wielowartościowe. Relacje, które dopuszczają definiowanie złożonych atrybutów nazywamy relacjami zagnieżdżonymi. W relacjach zagnieżdżonych każda krotka może zawierać inną relację. Wada – dla każdej krotki relacji zagnieżdżonej tworzymy krotkę relacji znormalizowanej – w krotkach znormalizowanych powtarzają się wiele razy dane z relacji zewnętrznej. Dekompozycja relacji zagnieżdżonych: • Utwórz osobną relację dla relacji zewnętrznej • Utwórz osobną relację dla relacji wewnętrznej (zagnieżdżonej), do której dodaj klucz relacji zewnętrznej • Klucz nowej relacji wewnętrznej (klucz relacji wewnętrznej + klucz relacji zewnętrznej) PO POLSKU: Jeżeli mamy relacje zagnieżdżone, encję rozbijamy na kilka encji i dodajemy klucze obce. Druga postać normalna 2NF Dana relacja r o schemacie R jest w drugiej postaci normalnej (2NF), jeżeli żaden atrybut wtórny tej relacji nie jest częściowo funkcyjnie zależny od żadnego z kluczy relacji r. PO POLSKU: Relacja r ma klucz {X1, X2}. Jeżeli atrybut Y zależy funkcyjnie od klucza składającego się z atrybutów X1 i X2, i dodatkowo atrybut Y zależy funkcyjnie od X1, to Y jest częściowo funkcyjnie zależny od kluczy relacji r. Zachodzi zatem konieczność dekompozycji schematu relacji r na mniejsze relacje. Rozbijamy na takie schematy, by w żadnym nie było częściowej funkcyjnej zależności.

10

Trzecia postać normalna 3NF Dana relacja r o schemacie R jest w trzeciej postaci normalnej (3NF), jeżeli dla każdej zależności funkcyjnej X A w R spełniony jest jeden z następujących warunków: • X jest nadkluczem schematu R, lub • A jest atrybutem podstawowym schematu R PO POLSKU: Problem występuje, gdy mamy zależność przechodnią. Dekomponujemy w taki sposób, by usunąć taką zależność. Zazwyczaj wydzielamy to tak, że to co jest przechodnio zależne wylatuje do oddzielnej encji razem z tym, od czego ma zwykłą zależność. Postać normalna Boyce-Codd (BCNF) Postać normalna Boyce-Codd’a stanowi warunek dostateczny 3NF, ale nie konieczny. Dana relacja r o schemacie R jest w postaci normalnej Boyce’a-Codd’a (BCNF), jeżeli dla każdej zależności funkcyjnej X A w R spełniony jest następujący warunek: X jest nadkluczem schematu R. PO LUDZKU: Wszystko musi zależeć od nadkluczy. Jeżeli atrybut zależy od zbioru atrybutów, który nie jest nadkluczem (może być kilka takich samych układów wartości), trzeba to rozbić na kilka encji. Czwarta postać normalna 4NF Relacja r o schemacie R jest w czwartej postaci normalnej (4NF) względem zbioru zależności wielowartościowych MVD jeżeli jest ona w 3NF i dla każdej zależności wielowartościowej X →→ Y ∈ MVD zależność ta jest trywialna lub X jest nadkluczem schematu Dana jest relacja r o schemacie R, i dany jest zbiór F zależności funkcyjnych dla R. Niech relacje r1 i r2 o schematach, odpowiednio, R1 i R2, oznaczają dekompozycję relacji r(R). Dekompozycja ta jest dekompozycją bez utraty informacji, jeżeli jedna z dwóch zależności jest spełniona: • •

Dekompozycja na relacje w 3NF o R1 ILOCZYN R2 → R1 o R1 ILOCZYN R2 → R2. Dekompozycja na relacje w 4NF o R1 ∩ R2 →→ (R1 - R2) o R1 ∩ R2 →→ (R2 - R1)

11

5 Organizacja rekordów w blokach Organizacja pliku określa sposób uporządkowania rekordów w pliku przechowywanym na dysku. Wybranie właściwej organizacji dla każdego pliku jest zadaniem administratora BD. Media fizyczne tworzą hierarchię pamięci składającą się z pamięci operacyjnej i pamięci zewnętrznej. Pamięć zewnętrzna ma organizację plikową, oznacza to, że jednostką alokacji na dysku jest plik. Natomiast pamięć operacyjna ma organizację blokową. Oznacza to, że jednostką alokacji jest blok. Blok alokowany w pamięci operacyjnej jest wielokrotnością rozmiaru fizycznego bloku dyskowego. Trwałe dane w bazie danych są przechowywane w pamięci zewnętrznej. W czasie pracy bazy danych, poszukiwane dane są odczytywane z plików dyskowych i umieszczane/buforowane w blokach systemu operacyjnego. Bloki te są często nazywane buforami bazy danych. Użytkownicy modyfikują dane w buforach. Zawartość tych buforów jest następnie zapisywana do plików. Rozmiar bloku nigdy nie jest wielokrotnością rozmiaru rekordu. Maksymalna liczba rekordów, która może się zmieścić w bloku jest określana za pomocą tzw. współczynnika blokowania. • Współczynnik blokowania bfr = ⎣(B/R)⎦⎦. (rozmiar bloku B, rozmiar rekordu R). • Wolny obszar w bloku: B – (bfr∗R)

5.1 Rodzaje organizacji rekordów w blokach Dzielona Rekordy w blokach są zorganizowane albo jako dzielone (ang. spanned) albo jako niepodzielne (ang. unspanned). W pierwszym przypadku, rekord, który cały nie mieści się w bloku jest dzielony, a jego części są przechowywane w kilku blokach. Początek rekordu w jednym bloku, koniec w innym. Niepodzielona W przypadku organizacji niepodzielnej rekord, który nie mieści się w całości w bloku jest przenoszony do takiego bloku, w którym zmieści się cały. Zostają więc puste miejsca na końcu bloku.

5.2 Zarządzanie rozmiarem bloku danych Utrzymywanie wolnej pamięci w bloku dla potencjalnych modyfikacji W praktyce, w każdym bloku, niezależnie od organizacji rekordów, pozostawia się część wolnego miejsca. Miejsce to jest wykorzystywane na rozszerzanie się rekordów na skutek modyfikowania wartości ich pól. Definiuje się dwa parametry: • PCTFREE - ile procent rozmiaru bloku pozostanie wolne. • PCTUSED - określa kiedy do bloku można wstawiać rekordy. Jeżeli zajęte więcej procent niż określa PCTUSED, blok nie jest wykorzystywany do wstawiania nowych rekordów.

5.3 Operacje na rekordach Operacje dostępu do pojedynczego rekordu • wyszukiwanie rekordu spełniającego kryterium: Find, FindFirst, FindNext, • usuwanie: Delete, • aktualizację: Update, • wstawianie: Insert. Operacje dostępu do zbioru rekordów: • wyszukiwanie wszystkich rekordów spełniających kryterium: FindAll, • wyszukiwanie rekordów spełniających kryterium z sortowaniem wyników: FindOrdered, • reorganizację pliku: Reorganize (np. posortowanie rekordów wg nowego kryterium). 12

Każda operacja na pliku posiada swój tzw. koszt. Koszt jest konkretną wartością, której miarą może być np. czas wykonania, liczba dostępów do dysku. Koszt jest wartością wynikającą z tzw. modelu kosztów. W celach analizy kosztów dostępu do plików nieuporządkowanch, uporządkowanych i haszowych przyjmiemy następujący model kosztów. • N oznacza liczbę bloków; • każdy blok zawiera R rekordów; • średni czas odczytu/zapisu bloku dyskowego wynosi D; • średni czas przetwarzania rekordu (np., porównanie wartości atrybutu ze stałą) wynosi C; • w przypadku plików haszowych stosujemy funkcję haszową odwzorowującą wartości • rekordów na liczby naturalne; czas obliczenia wartości funkcji haszowej wynosi H;

5.4 Rodzaje organizacji plików 5.4.1

Plik nieuporządkowany

Cechy: • Nagłówek pliku zawierający wskaźnik do bloku danych • Blok danych zawiera wskaźnik do bloku następnego i poprzedniego • Rekordy wstawiane na koniec pliku Operacje: • wstawianie rekordu - rekord jest wstawiany do ostatniego bloku pliku; blok ten jest zapisywany na dysk. o Koszt = 2D+C • wyszukiwanie rekordu: konieczność liniowego przeszukiwania wszystkich bloków. o Średni koszt = 0.5N(D+RC). o maksymalny koszt = N(D+RC) (przejrzenie całego pliku) • przeglądanie pliku o koszt = N(D +RC) - odczyt N stron z kosztem D, dla każdej strony przetworzyć R rekordów z kosztem C • wyszukiwanie z przedziałem wartości o koszt = N(D + RC) - odczyt wszystkich bloków • usuwanie rekordu o koszt wyszukania + koszt (C + D) o średnio: 0.5N(D+RC)+(C+D) o maksymalnie: N(D+RC)+(C+D) • sortowanie jest implementacyjnie trudne, plik sortowany fragmentami mieszczącymi się w pamięci operacyjnej. Każdy posortowany fragment jest łączony z innymi fragmentami. Zalety: • Efektywne wstawianie pojedynczych rekordów i dużych zbiorów rekordów • Efektywne pozostałe operacji w przypadku plików o rozmiarze kilku bloków • Struktura właściwa dla odczytu wszystkich rekordów 5.4.2

Plik uporządkowany

Rekordy w nim składowane są uporządkowane wg wartości tzw. pola porządkującego. Operacje: • przeglądanie pliku o koszt = N(D+RC) , ponieważ wszystkie strony muszą być odczytane • wyszukiwanie rekordu o wyszukiwanie binarne - koszt = D*log2B+C*log2R

13

•

wyszukiwanie z przedziałem wartości - koszt wyszukania pierwszego rekordu + koszt selekcji zbioru rekordów - D*log2B+C*log2R + ND (N- liczba bloków) • wstawianie rekordu o koszt wyszukania miejsca wstawienia rekordu + koszt przepisania średnio połowy rekordów. o Koszt całkowity = 2*(0.5N(D+RC)) • usuwanie rekordu o koszt znalezienia usuwanego rekordu + koszt przepisania średnio połowy rekordów identyczny jak koszt wstawiania. o Koszt całkowity = 2*(0.5N(D+RC)); Problem wstawiania rekordów – przesuwanie rekordów jest nieefektywne. Rozwiązania: • pozostawienie w każdym bloku dyskowym pustego miejsca na wstawiane rekordy • wykorzystanie nieuporządkowanego tymczasowego pliku, zwanego nadmiarowym o Wstawiane rekordy są umieszczane w pliku nadmiarowym, na jego końcu. Okresowo, plik nadmiarowy jest sortowany i scalany z plikiem głównym o Przy takim podejściu wstawianie jest efektywne, ale wyszukiwanie jest kosztowne. Modyfikowanie rekordu • Znalezienie i odczyt modyfikowanego rekordu do bufora o połowienie binarne dla warunku na polu porządkującym o przeszukanie całego pliku dla innego warunku • Modyfikowanie wartości atrybutu nieporządkującego o zmodyfikowanie w buforze i zapis na dysk w to samo miejsce • Modyfikowanie wartości atrybut porządkującego o zmiana pozycji rekordu w pliku o usunięcie rekordu + wstawienie nowego Zalety • Efektywny odczyt rekordów w kolejności pola porządkującego (posortowane) • Znalezienie następnego rekordu, według określonego porządku, jest bardzo proste • Metoda połowienia binarnego do wyszukiwania rekordu z warunkiem opartym o pole porządkujące Wady • Kosztowne wstawianie i usuwanie • Uporządkowanie pliku jest nieprzydatne, gdy wyszukiwanie jest realizowane według wartości pola nie porządkującego 5.4.3

Plik haszowy

Plik o strukturze wykorzystującej technikę haszowania. Podstawą określającą porządek rekordów w pliku jest jedno z pól rekordu zwane polem haszowym. Koncepcja organizacji tego pliku polega na zdefiniowaniu funkcji haszowej, która dla argumentu równego wartości pola haszowego wyznacza pewien wynik. Wynik ten jest adresem bloku dyskowego, w którym powinien znaleźć się dany rekord. Tablica haszowa powinna być zajęta w 70 do 90%, tak aby zapewnić niewielką liczbę kolizji i nie powodować zbyt dużego marnowania obszaru dyskowego. Haszowanie wewnętrzne Przyjmijmy, że dana jest tablica rekordów o M szczelinach. Adresy szczelin odpowiadają indeksom tablicy haszowej. Indeksy te przyjmują wartości od 0 do M-1. Przyjmijmy funkcję haszową postaci: H(K=wartość pola haszowego) -> {0, ..., M-1}. Funkcja ta transformuje wartość pola haszowego do liczby całkowitej z zakresu od 0 do M-1. Kolizja w haszowaniu wewnętrznym Wartość funkcji haszowej dla danej wartości pola haszowego nowego rekordu odpowiada zajętemu już adresowi szczeliny. Rozwiązanie: procedura znajdowania innej lokalizacji dla rekordu: • Adresowanie otwarte – następna wolna lokalizacja 14

• Łańcuchowanie - wskaźniki do nowych lokalizacji • Haszowanie wielokrotne - nowa funkcja haszowa Haszowanie zewnętrzne Wartościami tablicy haszowej są adresy logicznych obszarów dyskowych (LOD). Liczba LOD jest stała i równa liczbie szczelin w tablicy haszowej. LOD jest albo pojedynczym blokiem dyskowym albo zbiorem kolejnych (leżących obok siebie) bloków dyskowych. Funkcja haszowa odwzorowuje wartość atrybutu haszowego w numer LOD Plik dyskowy zawiera tablicę konwersji numerów LOD w fizyczne adresy bloków dyskowych. Kolizja w haszowaniu zewnętrznym LOD, którego numer jest wynikiem działania funkcji haszowej, może pomieścić wiele rekordów. Jednak po zapełnieniu się wszystkich bloków dyskowych alokowany jest obszar nadmiarowy. LOD zawiera wskaźnik do pierwszego rekordu tego obszaru. Kolejny rekord ulegający kolizji w tym samym LOD będzie zapisany w obszarze nadmiarowym, a wskaźnik do tego rekordu znajdzie się w poprzednim rekordzie obszaru nadmiarowego. Haszowanie zewnętrzne – operacje • Poszukiwanie rekordu z warunkiem nałożonym na pole inne niż haszowe o przeszukanie całego pliku + obszaru nadmiarowego • Poszukiwanie rekordu z warunkiem nałożonym na pole haszowe o funkcja haszowa + w przypadku kolizji przeszukanie obszaru nadmiarowego • Usunięcie rekordu z LOD o wyszukanie rekordu (funkcja haszowa + tablica konwersji) i zwolnienie szczeliny o przesunięcie pierwszego rekordu z obszaru nadmiarowego do LOD • Usunięcie rekordu z obszaru nadmiarowego o wyszukanie rekordu (funkcja haszowa) + przeszukanie listy w obszarze nadmiarowym o zwolnienie szczeliny o konieczność utrzymywania listy wolnych szczelin • Wstawienie rekordu o odczyt adresu szczeliny (funkcja haszowa), w przypadku kolizji zaalokowanie szczeliny w obszarze nadmiarowym • Zmodyfikowanie wartości pola haszowego o odczytanie rekordu (funkcja haszowa) o rekord zmienia szczelinę - usunięcie rekordu + wstawienie rekordu z nową wartością • Zmodyfikowanie wartości pola nie-haszowego o odczytanie rekordu (funkcja haszowa) i zmodyfikowanie Wady • Problem porządkowania pliku oraz wyszukiwania rekordów w porządku wartości pola haszowego • Problem stałego rozmiaru przestrzeni adresowej przydzielonej plikowi – częste kolizje

15