Wprowadzenie
Bazy danych i ich użytkownicy
a) Wprowadzenie
Baza danych jest zbiorem powiązanych danych.
Baza danych jest abstrakcyjnym informatycznym odzwierciedleniem wybranego fragmentu rzeczywistości nazywanego „miniświatem”. Zmiany w tym świecie są odzwierciedlane w bazie danych.
Baza danych jest logicznie spójnym zbiorem danych posiadających określone znaczenie.
Baza danych jest projektowana, budowana i wypełniana danymi dla określonych celów. Ma określoną grupę użytkowników korzystających w określony sposób z zawartej w niej informacji.
Każda baza danych posiada:
swoje źródło danych;
swoich użytkowników;
związki z reprezentowaną rzeczywistością.
Systemem zarządzania bazą danych (SZBD) nazywamy zbiór programów umożliwiających tworzenie i eksploatację bazy danych.
SZBD jest oprogramowaniem ogólnego przeznaczenia ułatwiającym procesy definiowania, konstruowania i przetwarzania baz danych dla różnych aplikacji. SZBD nie zawiera warstwy wizualizacji.
Definiowanie bazy danych polega na specyfikacji typów danych przechowywanych w bazie danych.
Konstruowanie bazy danych polega na zapamiętaniu danych na nośniku kontrolowanym przez SZBD.
Przetwarzanie polega na generowaniu zapytań do bazy danych w celu wyszukania potrzebnych danych, uaktualnianiu danych zgodnie ze zmianami zachodzącymi w „miniświecie” i generowaniu raportów o zawartych danych.
w meta-bazie danych jest pamiętana semantyka danych;
moduł zarządzania transakcjami ma zapewniać spójność danych;
moduł zarządzania dostępem do danych odpowiada za fizyczną reprezentację danych.
Przykład:
Poniżej przedstawiono przykłady danych jakie mogą być przechowywane w bazie danych.
Student
Nazwisko |
Nr_indeksu |
Rok |
Kierunek |
Nowak Kowalak |
18175 335573 |
I II |
Informatyka Telekomunikacja |
Wykład
Nazwa |
Nr_wykładu |
Ilość |
Prowadzący |
Struktury danych Bazy danych Kompilatory |
CS201 CS100 CS203 |
15 15 15 |
Misiek Morzy Nawrocki |
Grupa
No_grupy |
Nr_wykładu |
Semestr |
Rok |
85 92 |
CS201 CS445 |
Letni Zimowy |
93 93 |
Oceny
Nr_indeksu |
No_grupy |
Nr_wykładu |
Ocena |
18175 19551 33573 |
92 101 112 |
CS100 CS445 CS100 |
4 5 3 |
b) Bazy danych a przetwarzanie plików
Baza danych to dane + meta-baza (oprócz danych są także przechowywane informacje o semantyce danych).
Niezależność programów i danych (np. w języku Clipper istnieje silne powiązanie między danymi a programem).
Abstrakcyjna reprezentacja danych.
Różnorodność sposobów widzenia danych.
c) Aktorzy na scenie
Administrator bazy danych - DBA (posiada narzędzia diagnostyczne, stroi bazę danych).
Projektanci bazy danych (modelowanie konkretnej rzeczywistości).
Analitycy systemowi i programiści aplikacji (modelowanie konkretnej rzeczywistości).
Użytkownicy końcowi (najważniejsza grupa - to dla nich zbudowano system)
okazjonalni użytkownicy;
naiwni użytkownicy;
dobrze przygotowani użytkownicy.
d) Pracownicy poza sceną
Projektanci i implementatorzy SZBD.
Projektanci i implementatorzy narzędzi wspomagających.
Operatorzy i personel pomocniczy.
e) Zalety SZBD
Zmniejszenie nadmiarowości przechowywanych danych.
Współdzielenie danych.
Autoryzacja dostępu do danych.
Wielość interfejsów do danych.
Reprezentacja złożonych związków pomiędzy danymi.
Ograniczenia integralnościowe.
Backup & Recovery.
f) Kiedy nie stosować SZBD
wysoki początkowy koszt inwestycji;
potrzeba nowego lub dodatkowego sprzętu;
nadmiarowość w zakresie współbieżnego dostępu, bezpieczeństwa, odtwarzania, definiowania ograniczeń;
jednoużytkowość;
proste bazy danych i proste aplikacje bez przyszłości;
wymagania czasu rzeczywistego.
g) Kierunki rozwoju systemów baz danych
Systemy relacyjne Systemy postrelacyjne.
Systemy baz wiedzy.
Systemy rozproszonych baz danych.
systemy homogeniczne;
systemy heterogeniczne.
Systemy obiektowych baz danych.
Systemy czasu rzeczywistego.
Systemy aktywnych baz danych.
Koncepcja i architektura SZBD
a) Modele danych, schematy i instancje
Fundamentalną cechą systemów baz danych jest to, że zapewniają one pewien poziom abstrakcji widzenia danych przez użytkowników przesłaniając szczegóły dotyczącej fizycznej organizacji danych.
Model danych to zbiór koncepcji stosowanych do opisu struktury bazy danych.
Model ma za zadanie wprowadzić pośrednią warstwę abstrakcyjną, która pozwala łatwiej analizować obiekty świata rzeczywistego.
Struktura obejmuje:
typy danych, związki pomiędzy danymi i ograniczenia nałożone na dane;
zbiór operacji służących do definiowania, wyszukiwania i uaktualniania bazy danych.
Kategorie modeli danych
konceptualne modele danych (niezależne od programów modele związków encji);
implementacyjne modele danych (modele zaimplementowane w SZBD, np. relacyjny, obiektowy);
fizyczne modele danych (postaci plików).
Schematy i instancje
Schemat bazy danych
opis bazy danych - schemat bazy danych: definiowany w trakcie projektowania bazy danych;
graficznie schemat bazy danych jest reprezentowany przez diagram schematu.
Baza danych
dane w bazie danych nazywamy instancją bazy danych (wystąpieniem lub instancją bazy danych).
Użytkownicy końcowi modyfikują stan bazy danych.
b) Architektura SZBD
Trzypoziomowa architektura systemu bazy danych ANSI/SPARC:
niezależność fizyczna i logiczna danych;
rozdzielenie schematu bazy danych i danych;
różnorodność sposobów widzenia danych.
Poziom wewnętrzny schemat wewnętrzny: opisuje fizyczną organizację bazy danych. Schemat wewnętrzny stosuje fizyczny model danych i opisuje ścieżki dostępu do danych oraz fizyczną organizację danych.
Poziom pojęciowy (konceptualny) schemat konceptualny: opisuje strukturę bazy danych z punktu widzenia globalnego użytkownika. Opisuje encje, związki pomiędzy nimi, atrybuty i ograniczenia. Schemat pojęciowy stosuje konceptualny lub implementacyjny model danych.
Poziom zewnętrzny (lub perspektywiczny) schematy zewnętrzne (perspektywiczne): każdy schemat zewnętrzny opisuje bazę danych z punktu widzenia jednej grupy użytkowników. Schemat zewnętrzny stosuje konceptualny lub implementacyjny model danych.
Przez zastosowanie modelu trzypoziomowego osiągnięto fizyczną i logiczną niezależność danych, co upraszcza utrzymywanie systemu. Zmiany na poziomie koncepcyjnym mogą zostać częściowo przesłonięte przez poziom zewnętrzny.
c) Języki baz danych
Język definiowania danych (DDL).
Język definiowania struktury wewnętrznej (SDL).
Język manipulowania danymi (DML).
Język sterowania danymi (DCL).
Język zapytań.
d) Interfejsy SZBD
Interfejs wykorzystujący menu.
Interfejs graficzny.
Interfejs szablonów (forms-based interface).
Interfejs programowy.
Interfejs języka naturalnego.
e) Środowisko systemu baz danych
Cykl życia systemu baz danych
Cyklem życia systemu baz danych nazywamy zbiór kroków niezbędnych do zaprojektowania globalnego schematu logicznego bazy danych, alokacji danych w sieci komputerowej oraz zdefiniowanie lokalnych schematów baz danych.
Analiza wymagań miniświata
Projekt logiczny
W tym kroku jest realizowany projekt schematu pojęciowego bazy danych opisującego wszystkie dane i ich wzajemne powiązania. Do projektowania wykorzystujemy model związków encji (ER model). Model ten transformujemy następnie do modelu implementacyjnego (np. modelu relacyjnego).
Innymi słowy podejmuje się decyzje: jakie dane mają być przechowywane w bazie danych? jaki schemat pojęciowy zostanie wykorzystany? Stosuje się obiektowe lub strukturalne narzędzia CASE (strukturalne w przypadku modelu ER).
Modelowanie diagramów ER
Dane przedsiębiorstwa są analizowane i modelowane za pomocą diagramów ER.
Integracja perspektyw
Wśród wielu analityków mogą występować różnice w postrzeganiu świata zewnętrznego, np. jeden stwierdzi, że klient składa zamówienie, a inny, że klient zamawia produkty. Wymaga to integracji perspektyw.
Fragmenty schematu pojęciowego tworzone przez niezależnych projektantów są integrowane w jeden schemat globalny, rozwiązywane są niespójności nazw encji i związków. Wykonywana jest analiza synonimów, agregacja i generalizacja.
Transformacja modelu ER do modelu relacyjnego
Diagram ER jest transformowany do modelu relacyjnego - otrzymujemy schemat logiczny relacyjnej bazy danych w postaci schematów relacji.
Kolejne transformacje: model zewnętrzny model pojęciowy (EER) model implementacyjny (relacyjny).
Wyróżniamy trzy typy relacji:
relacja encji,
relacja encji z kluczem obcym (posiada dodatkowe atrybuty z relacji co wynika z istnienia związków między encjami),
relacja związku (jeśli jest typ asocjacji N:M., to tworzy się relację zawierającą atrybuty charakteryzujące związek oraz klucze obce do wiązanych relacji).
Customer
cust_id |
cust_name |
… |
|
|
|
Product
prod_no |
prod_name |
qty_in_stock |
|
|
|
Order
order_no |
sales_name |
cust_no |
|
|
|
Order_line
order_no |
prod_no |
|
|
Salesperson
sales_name |
addr |
dept |
job_level |
vacation_days |
|
|
|
|
|
Normalizacja schematów relacji
Otrzymany schemat bazy danych może być nie do przyjęcia z punktu widzenia jego własności użytkowych (np. duży koszt użytkowania, anomalie, itp.).
Dysponując informacją na temat zależności funkcyjnych i wielowartościowych (FD i MVD) dokonujemy normalizacji schematów relacji (3NF, BCNF, 4NF, 5NF).
Zalecenie: gdy będziemy implementować atrybuty wielowartościowe w modelu relacyjnym, to powinniśmy zaimplementować je jako osobne encje powiązane z relacją początkową; odpadnie wtedy potrzeba normalizacji do 4NF.
np. dana jest zależność funkcyjna
job_level vacation_days
Salesperson
sales_name |
addr |
dept |
job_level |
|
|
|
|
Sales_vacation
job_level |
vacation_days |
|
|
Denormalizacja
Normalizacja może prowadzić do pogorszenia efektywności przetwarzania zapytań. Denormalizacja polega na rozszerzeniu relacji o dodatkowe atrybuty w celu poprawy efektywności. Denormalizacja polega na uwzględnieniu częstości zapytań, ich priorytetów, wolumenów danych.
Denormalizacja nie jest bynajmniej odwrotnością normalizacji. Model relacyjny jest prosty, jednak ceną jest prymitywny zbiór typów danych i niska efektywność (w celu realizacji zapytania potrzeba dużo kosztownych operacji połączenia).
Założenie: 90% zapytań ma następujący charakter:
Kto obsługiwał klienta o nazwisku „Koszlajda”?
Customer
cust_id |
cust_name |
… |
|
|
|
Order
order_no |
sales_name |
cust_no |
|
|
|
Customer
cust_id |
cust_name |
sales_name |
|
|
|
Rozproszenie danych
Celem SZBD jest zapewnienie spójności dwojakiego rodzaju:
spójność wewnętrzna - dane w bazie danych odwzorowują świat rzeczywisty
spójność zewnętrzna - kopie replik relacji są spójne.
Replikacja ma związek z:
wzrostem efektywności korzystania z bazy danych
wzrostem kosztów związanych z utrzymywaniem spójności replik.
Mechanizmy replikacji:
synchroniczna
asynchroniczna.
Faza rozproszenia danych składa się z dwóch kroków:
fragmentacji danych (schemat fragmentacji)
alokacji danych (schemat alokacji)
W tej fazie uwzględniane jest środowisko fizyczne (m.in. konfiguracja sieci).
Schemat fragmentacji opisuje odwzorowanie typu 1:N fragmentacji schematu relacji na podrelacje. Podrelacje stanowią logiczne jednostki fizyczne rozproszone na jednym lub wielu stanowiskach.
Fragmentacja wynika z późniejszego sposobu korzystania z danych.
Schemat alokacji opisuje fizyczną alokację podrelacji - tj. przypisanie danej podrelacji do stanowiska.
1:1 - rozproszona niereplikowana baza danych (tzn. jeden fragment znajduje się na jednym stanowisku)
1:N - rozproszona replikowana baza danych, rozproszona w pełni replikowana baza danych (tzn. każdy fragment znajduje się na każdym stanowisku), rozproszona częściowo replikowana baza danych.
Cele projektu bazy danych w środowisku rozproszonym:
separacja fragmentacji i alokacji relacji (pierwsza jest logiczna, druga fizyczna)
kontrola replikacji
niezależność od lokalnego SZBD.
Cele: minimalizacja czasu odpowiedzi, minimalizacja kosztów komunikacji, maksymalizacja dostępności.
W bazie danych mamy daną x. Ponieważ baza jest replikowana, mamy trzy repliki x1, x2 i x3. Użytkownik wysyła transakcję T modyfikującą daną x. System sam musi dokonać modyfikacji replik. W przypadku replikacji synchronicznej, uaktualnianie replik zachodzi w ramach tej samej transakcji. Jest to bardzo niewygodne, bo gdy w trakcie takiej dość długiej transakcji zostanie napotkana jakaś przeszkoda, to cała transakcja zostanie wycofana. Aby zwiększyć prawdopodobieństwo uaktualnienia replik wprowadzono replikację asynchroniczną. W przypadku replikacji asynchronicznej transakcja modyfikuje tylko jedną kopię repliki danej. Następnie system uruchamia osobne transakcje, po jednej dla każdej innej repliki. Mamy tu separację transakcji, co może doprowadzić do powstania realizacji nieuszeregowalnej. Informacje o transakcjach są zapisywane w specjalnym pliku log. W razie awarii systemu, będzie on potem wiedział jakie transakcje aktualizacji musi jeszcze wykonać.
Projekt schematu logicznego lokalnej bazy danych i projekt fizyczny
Celem tej fazy jest projekt schematu logicznego lokalnej bazy danych, zdefiniowanie struktur fizycznych i określenie metod dostępu.
SQL (model relacyjny)
create table customer
( cust_no integer,
cust_name char(15),
cust_addr char(30),
sales_name char(15),
prod_no integer,
primary key (cust_no),
foreign key (sales_name) reference salesperson,
foreign key (prod_no) reference product);
Projekt fizyczny obejmuje zdefiniowanie indeksów i klastrów.
create [unique] index indexname on relation (columnname [asc|desc], columnname)
create unique index nazw_ind on customer (cust_name desc)
Implementacja bazy danych, jej strojenie, modyfikacje i monitorowanie
Projektowanie systemów informatycznych
Wprowadzenie
Klient określa potrzeby, problemy i wymagania dotyczące określonego przedsiębiorstwa X, fragmentu działalności przedsiębiorstwa X lub fragmentu działalności uogólnionego przedsiębiorstwa. Wynikiem pracy informatyków jest produkt - system informatyczny, którego jądrem jest baza danych.
Metodyka budowy oprogramowania:
strategia,
analiza,
projektowanie,
implementacja,
testowanie,
wdrażanie,
eksploatacja.
Program kursu
Proces projektowania bazy danych
Cel modelowania danych
Model związków encji
Metodyka budowy diagramów związków encji
Projektowanie struktur logicznych bazy danych
Projektowanie rozproszonej bazy danych
Funkcja
Dekompozycja funkcji
Zdarzenia
Zależności funkcji
Diagramy przepływu danych (DFD)
Powiązanie funkcji z danymi
Generowanie aplikacji na podstawie DFD
Designer 2000
Integracja danych
Utrata kontroli nad zaległymi płatnościami, wysłanymi zamówieniami, wyrobami w procesie produkcji, itp.
Pracownicy tracą czas na ewidencję tych samych danych w różnych formatach oraz ręczne robienie zestawień sumowań.
Działy marketingu, finansów i planowania produkcji sygnalizują brak potrzebnych informacji.
Raporty dla kierownictwa dostarczane są z tygodniowym lub dwutygodniowym opóźnieniem.
Format prezentacji danych dla niektórych działów jest nieodpowiedni - utrudnione wydobywanie istotnych informacji.
Brak dostępu do określonych informacji pomimo istnienia ich w bazie danych.
Brak możliwości realizacji pewnych zadań z powodu braku określonych danych.
Budowa systemu informatycznego od podstaw.
Przebudowa i modernizacja istniejącego systemu.
Integracja istniejących systemów i programów komputerowych.
Cykl życia systemu a proces projektowania bazy danych
Projektowanie bazy danych jest integralną częścią procesu budowy systemu informatycznego.
Inżynieria informacji: zbiór metod, technik, zasad, notacji i narzędzi wykorzystywanych w procesie projektowania bazy danych.
Najtrudniejszym zadaniem jest konstrukcja modelu informacyjnego - pojęciowego schematu bazy danych.
Projektowanie bazy danych
Jakie dane nas interesują?
Jak te dane będą reprezentowane?
Jak ten dane będą składowane?
Analiza potrzeb informatycznych użytkownika.
Konstrukcja diagramu związków encji.
Wybór modelu danych na poziomie logicznym.
Transformacja modelu pojęciowego do logicznego.
Normalizacja struktur logicznych.
Określenie sposobu składowania danych.
Określenie mechanizmów dostępu do danych.
brak automatyzacji procesu modelowania (narzędzia do rysowania, weryfikacja składniowa, słownik projektu)
półautomatyczna transformacja schematu pojęciowego do schematu logicznego
projekt struktur fizycznych wspomagany przez SZBD
w pełni automatyczna implementacja bazy danych.
Cel modelowania danych
Otrzymanie dokładnego modelu potrzeb informacyjnych przedsiębiorstwa/organizacji (to nie jest takie proste; proces ten jest wspomagany poprzez wypełnianie ankiet przez pracowników).
Dekompozycja i strukturalizacja problemu (pomaga w zrozumieniu funkcjonowania przedsiębiorstwa).
Sformalizowanie opisu z wykorzystaniem języka graficznego - jednoznaczność i czytelność.
Mechanizm efektywnej komunikacji pomiędzy analitykiem i użytkownikiem, pomiędzy analitykami systemu, a nawet pomiędzy użytkownikami.
Poprawa jakości i efektywności projektowania bazy danych.
Opis danych niezależny od struktur logicznych i fizycznych.
Niezależność od implementacji pozwala na zastosowanie modelu do integracji istniejących baz danych.
Podstawa do zrozumienia procesów realizowanych w przedsiębiorstwie i jego reorganizacji.
Możliwość prezentacji potrzeb informacyjnych na różnym poziomie ogólności.
Modelowanie danych na diagramach związków encji
Tłumaczenie wybranych terminów
Rodowód modelu związków encji
sposób reprezentacji znaczenia słów
znaczenie słowa opisane za pomocą powiązań z innymi słowami.
is-part-of służy do modelowania jak dana rzecz może być skonstruowana z komponentów
isa służy do modelowania dziedziczenia
is-associated-with służy do modelowania zależności między encjami
Model związków encji Chena
Encje - byty
Atrybuty - cechy encji
Związki - opisują powiązania między encjami
Hierarchie
Encja to rzecz, o której chcemy przechowywać informacje.
Encja kryje w sobie wiele obiektów, czyli tzw. wystąpień encji.
Nazwy encji powinny być rzeczownikami w liczbie pojedyncznej.
Obiekt rzeczywisty może być reprezentowany w modelu tylko przez jedną encję.
Każda encja musi posiadać unikalny identyfikator.
Każda encja ma swoje własne atrybuty (cechy).
pracownik, samochód, budynek, produkt, itp.
konto bankowe, zamówienie, grupa pracownicza, itp.
choroba pracownika, przyznanie nagrody, itp.
znajomość języka obcego, stan magazynowy produktu, itp.
dany pracownik może posiadać określony samochód
dany samochód jest własnością określonego pracownika
Pracownik posiada samochód.
Samochód jest własnością pracownika.
narność - liczba argumentów (1, 2 lub 3)
nazwa (w notacji Chena jedna nazwa; w notacji Oracle - dwie nazwy - zależnie od punktu widzenia)
typ asocjacji (1:1, 1:N, M:N)
klasa przynależności (obligatoryjny lub opcjonalny).
Istnieją powiązania pomiędzy obiektami typu PRACOWNIK i SAMOCHÓD.
Ile samochodów może posiadać pracownik? Ilu pracowników może być właścicielami jednego samochodu?
Czy każdy pracownik musi posiadać samochód? Czy musimy znać właściciela każdego samochodu?
Czy dany samochód może stać się własnością innego pracownika?
Każdy projekt może być wykonywany tylko dla jednego klienta.
Każdy klient może zlecić wykonanie jednego lub wielu projektów.
Każdy pracownik może brać udział w jednym lub wielu projektach.
Każdy projekt może być realizowany przez jednego lub wielu pracowników.
Każdy pracownik może kierować jednym działem.
Każdy dział może być kierowany przez jednego pracownika.
Nie każdy pracownik musi posiadać samochód.
Często nie wiemy, czy pracownik posiada samochód.
Każdy samochód (o którym chcemy przechowywać informacje) musi być własnością określonego pracownika.
Każdy pracownik może posiadać jeden lub więcej samochodów.
Każdy samochód musi być własnością jednego pracownika.
Każdy samochód dostawczy musi posiadać jeden lub wiele przeglądów technicznych.
Każdy przegląd techniczny musi dotyczyć jednego konkretnego samochodu.
Każdy pracownik może posiadać jeden stopień naukowy.
Każdy stopień naukowy może zostać zdobyty przez jednego lub wielu pracowników.
Określony pracownik daną rolę może pełnić w jednym lub wielu projektach.
W określonym projekcie daną rolę może pełnić jeden lub wielu pracowników.
Określony pracownik w danym projekcie może pełnić tylko jedną konkretną rolę.
Specjalizacje dziedziczą wszystkie atrybuty generalizacji.
Każde wystąpienie generalizacji jest zawsze wystąpieniem jednej ze specjalizacji.
Związki zatrudniony w i zatrudniony na dotyczą pracowników krajowych i zagranicznych.
Związek pracował w jest specyficzny dla pracowników krajowych.
Specjalizacje dziedziczą wszystkie związki generalizacji (związek między generalizacją jest dziedziczony w specjalizacji ale nie odwrotnie).
Encje NAPRAWA ŚRODKA TRWAŁEGO i NAPRAWA WYPOSAŻENIA nie posiadają specyficznych atrybutów.
Specjalizacje posiadają wyłącznie specyficzne związki.
Każde wystąpienie encji NAPRAWA musi być powiązane albo ze środkiem trwałym albo z elementem wyposażenia.
hierarchia generalizacji - generalizowane podzbiory są rozłączne, np. pracownik jest albo adiunktem albo pracownikiem technicznym (na diagramie obok linii symbolizującej dziedziczenie pojawia się literka „d”);
hierarchia podzbiorów - specjalizacje mogą się nakładać (literka „o” na diagramie); tego nie da się zamodelować w notacji Oracla.
Ograniczenie, jakiego typu i z jakiego przedziału wartości mogą być przyjmowane przez dany atrybut.
Notacja: nazwa_projektu - VARCHAR(25), wynagrodzenie - NUMBER(8,2)
Ograniczenie, że dla wszystkich wystąpień encji, wartości danego atrybutu muszą być określone.
Opcjonalność - pewne atrybuty nie muszą zostać zdefiniowane - wykorzystujemy wtedy wartości puste.
Obligatoryjność oznaczana jest przez znak „*” obok atrybutu, a opcjonalność przez „o”.
Notacja: nazwisko o drugie_imię (opcjonalność)
Wartości atrybutu lub kombinacji atrybutów muszą być unikalne wśród wszystkich wystąpień encji.
Notacja: # symbol_projektu
Dodatkowe ograniczenia na wartości przyjmowane przez dany atrybut definiowane za pomocą wyrażeń logicznych i odwołań do innych atrybutów.
Przykłady: check (day(data_wypłaty)<>niedziela), check(data_zakończenia>data_rozpoczęcia)
Ograniczenie na kolejność wartości przyjmowanych przez dany atrybut.
Przykład: kawaler, żonaty, wdowiec
Ograniczenie, że wszystkie wystąpienia encji muszą posiadać wystąpienie danego związku.
Wszystkie wystąpienia związku lub kombinacji związków muszą być unikalne w zbiorze wszystkich wystąpień encji.
Ograniczenie, że każde wystąpienie encji może posiadać tylko jedno wystąpienie związku spośród związków objętych łukiem.
Uniemożliwia modyfikację raz określonego powiązania.
silne (pojedynczy prostokąt) - istnieją niezależnie do innych encji;
słabe (podwójny prostokąt) - nie mogą istnieć samodzielnie lecz tylko w powiązaniu z innymi encjami (przez co nie muszą posiadać unikalnych atrybutów).
Każda encja musi mieć zdefiniowany sposób identyfikacji pojedynczych wystąpień.
Unikalny identyfikator może być atrybutem, kombinacją atrybutów, kombinacją związków lub kombinacją związków i trybutów.
liczba atrybutów zapewniających unikalność > 2,
wartości atrybutu unikalnego mają duże rozmiary,
często modyfikujemy wartości atrybutów unikalnych,
Identyfikacja stanu magazynowego odbywa się w oparciu o określony produkt i określony magazyn.
Poszczególne pozycje zamówień identyfikowane są przez wskazanie zamówienia i podanie numeru pozycji.
wiele unikalnych identyfikatorów na najniższym poziomie,
jeden unikalny identyfikator na najwyższym poziomie.
wspólne, naturalne atrybuty hierarchii encji,
atrybut sztuczny dodany na poziomie generalizacji,
kombinacje związków generalizacji,
kombinacje związków i atrybutów generalizacji.
Unikalny identyfikator jest dziedziczony przez wszystkie specjalizacje.
Umożliwia identyfikację wystąpień wszystkich specjalizacji.
Dla każdej specjalizacji na najniższym poziomie (liście hierarchii) definiujemy niezależnie unikalne identyfikatory.
Metodyka konstruowania diagramów związków encji
Wyraźnie wyeksponowane obiekty, opisane zbiorem informacji, w naturalny sposób modelujemy jako encje.
Czy dana rzecz lub cecha, nazwana z użyciem rzeczownika jest atrybutem opisującym encję, czy jest samodzielną encją?
Gdy sam jest opisany dodatkowymi informacjami.
Gdy chcemy pamiętać dynamiczny zbiór wartości tego atrybutu niezależnie od istnienia opisywanego obiektu.
Gdy stwierdzamy, że atrybut może dla jednego obiektu przyjmować wiele wartości (współczesne systemy są znormalizowane i wartość atrybuty w danej krotce jest atomowa).
Czy dany fakt (nazwany z użyciem czasownika), dotyczący znanych już obiektów, jest związkiem łączącym określone encje, czy jest nową encją?
Kiedy chcemy każde powiązanie pomiędzy dwoma obiektami (np. pracownikiem i językiem obcym) opisać dodatkowymi atrybutami dotyczącymi tego powiązania (np. stopień znajomości języka).
Bezpośredni związek typu „wiele do wielu” przekształcony został na pośredni związek „wiele do wielu” (poprzez encję ZNAJOMOŚĆ JĘZYKA OBCEGO).
Związek M:N zastępujemy encją i dwoma związkami 1:N.
Związki 1:N są obligatoryjne po stronie „wiele”, niezależnie od obligatoryjności/opcjonalności związku M:N.
Obligatoryjność związku M:N przenosimy jako obligatoryjność związków 1:N po stronie „jeden”.
gdy chcemy każde wystąpienie związku opisać dodatkowymi atrybutami,
gdy narzędzie CASE nie umożliwia rysowania związków n-arnych.
Bezpośrednia n-arna zależność przekształcona została na zależność pośrednią (poprzez encję E).
Związek n-arny zastępujemy encją i n-arnymi związkami 1:N.
Związki 1:N są obligatoryjne po stronie „wiele”, niezależnie od obligatoryjności lub opcjonalności związku n-arnego.
Obligatoryjność związku n-arnego przenosimy jako obligatoryjność związków 1:N po stronie „jeden”.
Atrybut jest nazywany złożonym, gdy jego wartość dla jednego wystąpienia encji jest złożeniem kilku bardziej elementarnych wartości.
W definicji encji umieszczamy tylko atrybuty elementarne.
Atrybuty elementarne można w sposób nieformalny grupować przez stosowanie przedrostków w nazwach atrybutów.
Atrybut jest nazywany wielowartościowym, gdy posiada wiele wartości dla jednego wystąpienia encji.
Atrybut wielowartościowy modelujemy za pomocą dodatkowej encji, którą następnie łączymy związkiem 1:N z encją pierwotną („wiele” po stronie nowej encji).
Agregacja to obiekt (często abstrakcyjny) zbudowany z innych, bardziej elementarnych obiektów.
grupa pracownicza (składająca się z pracowników),
oddział firmy (składający się z działów),
samochód (składający się z podzespołów).
Wprowadzamy nową encję reprezentującą agregację.
Nową encję łączymy związkiem 1:N z encją, która modeluje obiekty tworzące agregację.
Czy poszczególne rodzaje zabawek posiadają specyficzne atrybuty?
Czy poszczególne rodzaje zabawek posiadają specyficzne związki?
Czy chcemy przechowywać informacje dotyczące danego rodzaju zabawek?
Hierarchia danych to struktura o topologii drzewa utworzona z powiązanych wzajemnie obiektów.
pracownik - pracownicy - pracownicy …
oddział firmy - dział firmy - zespoły
produkt - podzespoły - inne podzespoły …
encja i związek rekurencyjny (hierarchia na tej samej encji).
encje i związki 1:N (hierarchie z encjami różnych typów).
encja ze związkiem rekurencyjnym i encja klasyfikującą (nakładanie powyższych dwóch).
charakter statyczny - brak elementu czasu
charakter dynamiczny - brak elementu czasu
możliwość wersjonowania
opis zdarzenia, moment zajścia zdarzenia
moment rozpoczęcia i zakończenia
opis zdarzenia, odwołanie do zegara czasowego
opis merytoryczny, odwołanie do zegara czasowego (np. roku akademickiego, okresu rozrachunkowego)
Historyczne wersje modyfikowanych danych modelujemy za pomocą dodatkowej encji.
Jeden z atrybutów nowej encji pełni rolę stępla czasowego.
brak elementu czasu
opis stanu bieżącego
aktualne wynagrodzenie
poprzednie wersje wynagrodzenia
moment zmiany lub okres czasu
aktualne zajmowane stanowisko - brak elementu czasu
aktualne i poprzednie stanowiska zajmowane przez pracownika - okresu czasu
Transformacja modelu EER do modelu relacyjnego
Wprowadzenie
relacje encji
związek binarny typu asocjacji m:n, 1:n, 1:1
związek unarny typu asocjacji m:n
związek ternarny, hierarchie generalizacji i podzbiorów.
relacje encji z kluczem obcym
związek binarny typu asocjacji 1:n, 1:1
związek unarny typu asocjacji 1:1 lub 1:n
relacje związków
związek binarny typu asocjacji m:n
związek unarny typu asocjacji m:n
związek ternarny.
Reguły transformacji
każdy związek rozpatrujemy niezależnie,
związki typu 1:1 i 1:n generują relacje encji z różnymi kluczami obcymi - integrujemy te relacje,
atrybuty związkami wędrują wraz z kluczem obcym.
Projektowanie schematów baz danych
Podstawowe pojęcia
identyfikatory - jednoznacznie identyfikują każdą encję;
klucze - klucz jest zbiorem atrybutów, który jednoznacznie identyfikuje krotkę (krotka jest odpowiednikiem instancji w relacyjnej bazie danych).
redundancja danych - pewne dane się powtarzają co zwiększa zapotrzebowanie pamięci, pojawia się problem zachowania spójności redundantnych danych;
anomalia wprowadzania danych - nie można zapamiętać dostawcy i jego adresu, który chwilowo nie dostarcza żadnych towarów;
anomalia usuwania danych - usunięcie wszystkich towarów dostarczanych przez tego samego dostawcę powoduje również usunięcie jego adresu;
anomalia uaktualniania danych - w niektórych przypadkach jest konieczne wielokrotne wprowadzanie tych samych danych.
dekompozycja relacji z utratą informacji,
dekompozycja relacji bez utraty informacji.
nazwa pisana dużymi literami oznacza schemat relacji, czyli zbiór atrybutów;
nazwa pisana małymi literami oznacza relację, czyli schemat relacji + wypełnienie atrybutów.
Nazwisko → Adres
Nazwisko, Towar → Cena
odzwierciedlają cechy fizyczne;
odzwierciedlają zasady prawne.
klucze proste - zbiór identyfikujący relacji jest zbiorem jednoelementowym;
klucze złożone - to klucze nie będące kluczami prostymi.
atrybuty podstawowe: atrybut X jest podstawowy w schemacie R jeżeli należy do któregokolwiek z kluczy schematu R;
atrybuty wtórne: atrybut X jest wtórny w schemacie R jeżeli nie należy do żadnego z kluczy schematu R.
Normalizacja
attribute preservation property - żaden atrybut nie zostanie zagubiony w trakcie procesu normalizacji;
lossies join property - dekompozycja relacji nie prowadzi do utraty informacji;
dependency preservation property - wszystkie zależności funkcyjne są reprezentowane w pojedynczych schematach relacji.
zewnętrzną - posiadającą atrybuty spoza relacji zagnieżdżonej;
wewnętrzną - posiadająca atrybuty relacji zagnieżdżonej + atrybut będący kluczem obcym do relacji zewnętrznej (klucz ten staje się atrybutem połączeniowym w przypadku łączenia relacji).
redundacja danych - nazwisko będzie się pojawiało tyle razy ile jest projektów
nazwy i lokacje projektów są zależne od numerów - numerów będzie tyle ile osób
trudności w modyfikacji
mamy nowy projekt, ale nie możemy go wprowadzić tak długo, aż nie przydzieli mu się jakiegoś pracownika
nie można wprowadzić pracownika, dopóki nie będzie pracował w jakimś projekcie.
Zależności wielowartościowe
związek pomiędzy zbiorami atrybutów X i Y;
niezależność zbiorów atrybutów Y i Z - zbiory te są związane ze sobą pośrednio poprzez zbiór atrybutów X.
t1[X] = t2[X] = t3[X] = t4[X]
t3[Y] = t1[Y] i t4[Y] = t2[Y]
t3[R-X-Y] = t2[R-X-Y] i t4[R-X-Y] = t1[R-X-Y]
zbiór Y jest podzbiorem X, lub
X Y = R (tzn. nie ma zbioru Z).
Dekompozycja na podrelacje w 3NF
R1 R2 → R1
R1 R2 → R2
Dekompozycja na podrelacje w 4NF
R1 R2 →→ R1 R2
R1 R2 →→ R2 R1
R1 R2 = {N}
R1 R2 = {Jo} i R2 R1 = {Jp}
{N} →→ Jo i {N} →→ Jp
bazowe - istnieją fizycznie
wirtualne - nie istnieją fizycznie
perspektywy (view)
migawki (snapshot).
acykliczne - można przedstawić w postaci grafu acyklicznego (wierzchołki to schematy relacji a łuki to atrybuty połączeniowe)
cykliczne - w grafie jest cykl.
zależność ta jest trywialna;
każdy podschemat Ri, i = 1, 2, …, p jest nadkluczem schematu R.
Projektowanie struktur fizycznych
Struktury fizyczne plików
pamięć operacyjna;
pamięć zewnętrzna.
primary: cache i operacyjna (elektroniczna)
secondary: zewnętrzna dyskowa (magnetyczna, optyczna)
tertiary: zewnętrzna taśmowa, CD, WORM (magnetyczna, optyczna).
ze względu na rozmiar bazy danych;
odporność pamięci zewnętrznej na awarie;
koszt jednostkowy.
Czasu przesunięcia głowicy na odpowiedni cylinder (seek time),
Czasu potrzebnego na obrót dysku by wskazany blok znalazł się pod głowicą (rotational time),
Czasu potrzebnego na przesłanie danych z dysku (transfer time).
rekordy - typy rekordów i typy danych;
rekordy o stałej i zmiennej długości.
organizacja dzielona (spanned);
organizacja niedzielona (unspanned).
alokacja ciągła (contignous allocation);
alokacja łączona (linked allocation);
alokacja segmentowa (clusters, extents);
alokacja indeksowa (indexed allocation).
Operacje na plikach
wyszukiwania: Find, Read, FindNext;
usuwania: Delete;
aktualizacji: Update;
wstawiania: Insert.
FindAll;
FindOrder;
Reorganize.
organizacji plików;
metod dostępu.
Pliki nieuporządkowane
wstawianie rekordów: rekord jest wstawiany do ostatniego bloku pliku; blok tej jest zapisywany na dysk,
wyszukiwanie rekordu: konieczność liniowego przeszukiwania wszystkich bloków (średnio b/2 bloków),
usuwanie rekordu: liniowe przeszukiwanie i zapis bloków na dysk. Pozostaje zwolniona pamięć - konieczność periodycznej reorganizacji pliku w celu odzyskania pamięci.
aktualizacja.
Pliki uporządkowane
plik jest uporządkowany;
znalezienie następnego w kolejności rekordu jest bardzo proste;
jeżeli warunek wyszukiwania rekordu oparty jest na wartości pola porządkującego to można stosować przeszukiwanie binarne.
wstawianie i usuwanie rekordów: konieczność zachowania porządku w pliku
podejście z przesuwaniem pliku (średnio 1/2 rekordów do przesunięcia ),
pozostawienie wolnej pamięci w bloku,
tworzenie nieuporządkowanego pliku rekordów, tzw. overflow lub transaction file, a następnie łączenie go z plikiem głównym;
modyfikowanie rekordów.
Transformacja klucza - haszowanie.
Identyfikacja klucza - indeksowanie.
Grupowanie klucza - cluster.
Haszowanie
metoda dostępu powinna być maksymalnie niezależna od tego, w jaki sposób realizowany jest dostęp do krotek,
wynika to z charakterystyki funkcjonalnej algorytmów haszowania,
konstrukcja TUPLEID przy PAGEID jest bardzo prosta.
folding;
hashing.
problem porządkowania pliku oraz wyszukiwania rekordów w porządku wartości pola haszowego,
problem stałego rozmiaru przestrzeni adresowej przydzielonej plikowi.
haszowanie kongruencyjne: H(kij) = Kb mod B;
potęgowanie: podnosimy Kb do potęgi n (n*31 bitów) i wybieramy log2B bitów jako adres strony;
transformacja bazowa: wartość Kb jest transformowana do systemu liczbowego o podstawie r. Część cyfr nowej reprezentacji jest wybierana jako adres;
dzielenie przez wielomian: technika CRC;
analiza numeryczna: user-specyfic hashing;
kodowanie.
jeżeli B parzyste, to dla dowolnego parzystego Ki reszta jest również parzysta;
załóżmy B=x*y i załóżmy, że wartości kluczy są budowane następująco: ki=k0+i*y, to
wierzchołki wewnętrzne;
wierzchołki liście.
Indeksy
ordering key field - wartość pola indeksowego (atrybutu, który indeksujemy)
pointer to disc block - wskaźnik na blok + offset w bloku (lub wskaźnik na adres bloku)
indeks podstawowy (primary index)
indeks zgrupowany (clustering index)
indeks drugorzędny lub wtórny (secondary index)
liczba rekordów indeksu odpowiada liczbie bloków pliku;
indeks podstawowy jest indeksem rzadkim (tzn. mamy wskaźniki do bloków a nie do rekordów);
liczba bloków indeksu jest dużo mniejsza od liczby bloków pliku;
przeszukiwanie binarne na pliku indeksowym (gdyż pliki indeksowe są zawsze uporządkowane).
przeszukiwanie binarne pliku indeksowego;
wskaźnik do bloku lub do rekordu (gdy wskaźniki do rekordu to wtedy jest to indeks gęsty);
wymaga więcej pamięci aniżeli indeks podstawowy;
stosowanie indeksu wtórnego daje większą względną poprawę efektywności wyszukiwania aniżeli indeks podstawowy.
Wiele rekordów indeksowanych z tą samą wartością K(i) dla różnych rekordów pliku danych.
Zastosowanie rekordów indeksowych zmiennej długości - <K(i), P1(i), P2(i), …,Pk(i)>.
Zastosowanie rzadkiego indeksu do bloku rekordów wskaźników (patrz rysunek poniżej).
dla każdego wierzchołka: K1 < K2 < … < Kq-1
dla wszystkich wartości x w poddrzewie wskazanym przez Pi spełnione są następujące warunki:
Każdy wierzchołek wewnętrzny posiada następującą strukturę
Dla każdego wierzchołka K1 < K2 < … < Kq-1
Dla każdej wartości klucza x w poddrzewie wskazywanym przez wskaźnik Pi spełnione są następujące warunki:
Każdy wierzchołek ma co najwyżej p wskaźników do poddrzew.
Każdy wierzchołek, za wyjątkiem korzenia i liści, posiada co najmniej (p/2) wskaźników do poddrzew. Korzeń posiada co najmniej 2 wskaźniki do poddrzew, za wyjątkiem sytuacji, gdy jest on jedynym wierzchołkiem w grafie.
Wierzchołek o q wskaźnikach do poddrzew (q p) posiada q - 1 wartości kluczy.
Wszystkie liście znajdują się na tym samym poziomie. Liście posiadają strukturę zbliżoną do struktury wierzchołków wewnętrznych - liście nie posiadają wskaźników do poddrzew.
Każdy wierzchołek wewnętrzny posiada następującą strukturę
Dla każdego wierzchołka wewnętrznego K1 < K2 < … < Kq-1
Dla każdej wartości klucza x w poddrzewie wskazywanym przez wskaźnik Pi spełnione są następujące warunki:
Każdy wierzchołek wewnętrzny ma co najwyżej p wskaźników do poddrzew.
Każdy wierzchołek wewnętrzny, za wyjątkiem korzenia i liści, posiada co najmniej (p/2) wskaźników do poddrzew. Korzeń , jeżeli jest wierzchołkiem wewnętrznym posiada co najmniej 2 wskaźniki do poddrzew.
Wierzchołek o q wskaźnikach do poddrzew (q p) posiada q - 1 wartości kluczy.
Każdy liść posiada następującą strukturę
Dla każdego liścia K1 < K2 < … < Kq-1
Wskaźnik Pri jest wskaźnikiem do bloku danych zawierającego rekord o wartości klucza Ki.
Każdy liść posiada co najmniej (p/2) wartości kluczy.
Wszystkie liście znajdują się na tym samym poziomie.
Grupowanie klucza
Zarządzanie współbieżnym wykonywaniem transakcji
Wstęp
logiczna L = {X, Y, Z, …}
fizyczna D = {x, y, z, …}
niereplikowany
replikowany
pielęgnacja synchroniczna
pielęgnacja asynchroniczna
monowersyjny
wielowersyjny
Pojęcie transakcji
efekt wykonania jego transakcji będzie niezależny od transakcji innych użytkowników i ich liczby,
efekt wykonania transakcji będzie stanem poprawnym.
logiczna jednostka obliczeń z punktu widzenia użytkownika
atomowa jednostka obliczeń z punktu widzenia SZBD
elementarna jednostka odtwarzania z punktu widzenia odtwarzania transakcji w SZBD
Niespójność stanu bazy danych wynikająca z awarii systemu. W wyniku awarii systemu wykonana została jedynie część operacji składających się na daną transakcję.
Błędy wynikające ze współbieżnego wykonywania transakcji. Przeplatające się operacje współbieżnie wykonywanych transakcji wpływają na siebie w niekontrolowany sposób.
Utrata danych wynikająca z awarii systemu. Wyniki zakończonych transakcji buforowane w pamięci operacyjnej zostały utracone w wyniku awarii systemu.
Begin_transaction: początek wykonywania transakcji.
Read, Write: operacje odczytu i zapisu danych w bazie danych.
End_transaction: zbiór operacji zapisu i odczytu składający się na transakcję został wyczerpany.
Commit: zatwierdzenie wyników transakcji.
Rollback: wycofanie wyników transakcji.
System zgłasza gotowość do przeprowadzenia transakcji.
System potwierdza wykonanie transakcji.
opóźnić (delay)
od razu przerzucić do routput
przerwać (abort).
= { oj : 1 j ni}, jest zbiorem operacji na bazie danych, należących do jednej z kategorii: {R - odczyt, W - zapis, C - zatwierdzenie transakcji, A - wycofanie transakcji};
Ti jest relacją porządkującą zbiór .
V jest zbiorem węzłów odpowiadających operacjom transakcji Ti ,
A jest zbiorem krawędzi reprezentujących porządek na zbiorze operacji.
sekwencyjne (relacja porządkująca transakcji jest relacją całkowitego porządku),
współbieżne (relacja porządkująca transakcji jest relacją częściowego porządku).
zależne od danych (wsadowe),
niezależne od danych (interakcyjne).
zapytaniowe (read only - nie zawierają operacji zapisu),
uaktualniające (read write - mogą zawierać operacje zapisu).
syntaktyczny - zakładający znajomość jedynie zbioru przetwarzanych danych;
semantyczny - zakładający znajomość semantyki operacji i danych oraz znajomość ograniczeń integralnościowych.
Pojęcie realizacji transakcji
Dla dowolne pary operacji oi , oj () takich, że żądają one dostępu do tej samej danej i co najmniej jedna z nich jest operacją zapisu, zachodzi oi r oj lub oj r oi.
Uszeregowalność
(Tj, Ti) A;
Jeżeli Tj T0, Ti Tf i istnieje operacja Tk : w(x) (), Tk T0, to (Tk, Tj) A lub (Ti, Tk) A;
Jeżeli Tj T0, to (T0, Tj) A;
Jeżeli Tj = T0, Ti Tf i istnieje operacja Tk : w(x) (), Tk T0, to (Ti, Tk) A;
Jeżeli Ti = Tf i istnieje operacja Tk : w(x) (), to (Tk, Tj) A.
Algorytmy synchronizacji współbieżnych transakcji
Algorytmy blokowania dostępu do danych
blokadę współdzieloną (shared lock),
blokadę wyłączną (exclusive lock).
dana niezablokowana 0
dana zablokowana dla odczytu R (współdzielona S)
dana zablokowana dla zapisu W (wyłączna X)
LR(x) - założenie blokady R
LW(x) - założenie blokady W
UNR(x) - zdjęcie blokady R
UNW(x) - zdjęcie blokady W
faza blokowania (ekspansji)
faza odblokowywania (zwijania)
System chce nałożyć na daną x blokadę R, gdyż tego wymaga transakcja T1. Dana ta nie była dotychczas blokowana, więc nie ma żadnych przeszkód by nałożyć nań blokadę.
System chce ponownie nałożyć na daną x blokadę R, bo teraz wymaga tego transakcja T2. Ponieważ dwie blokady R są kompatybilne, więc nałożenie nowej blokady nie napotyka przeszkód.
Jednak, gdy system chce przekształcić blokadę R w blokadę W, gdy tego wymaga transakcja T1, to nie może tego zrobić, gdyż, na daną jest nałożona dodatkowa blokada R. Operacja ta trafia do kolejki operacji oczekujących na zwolnienie zasobów (wait).
Tutaj powtarza się identyczna sytuacja co w punkcie 3.
Wykrywanie i rozwiązywanie.
Zapobieganie.
Unikanie.
jednoznacznie identyfikowalne (uniquely defined), czyli dane;
pool, czyli głównie pamięć;
M z N, czyli urządzenia (dyski, procesory, itp.).
stan zegara czasu rzeczywistego,
identyfikator stanowiska.
wait-die: Transakcja Ti próbuje uzyskać blokadę na danej X, tymczasem dana ta jest już zablokowana przez transakcję Tj. Jeżeli TS(Ti) < TS(Tj) (Ti jest starsza Tj) wtedy transakcja Ti będzie czekać na zwolnienie blokady. W przeciwnym wypadku Ti będzie wycofana i restartowana z tym samym znacznikiem czasowym.
wound-wait: Transakcja Ti próbuje uzyskać blokadę na danej X, tymczasem dana ta jest już zablokowana przez transakcję Tj. Jeżeli TS(Ti) < TS(Tj) (Ti jest starsza Tj) wtedy transakcja Tj będzie wycofana i restartowana z tym samym znacznikiem czasowym. W przeciwnym wypadku Ti będzie czekać na zwolnienie blokady.
no waiting: Transakcja Ti próbuje uzyskać blokadę na danej X, tymczasem dana ta jest już zablokowana przez transakcję Tj. Transakcja Ti będzie wycofana i restartowana z pewnym opóźnieniem czasowym.
cautious waiting: Transakcja Ti próbuje uzyskać blokadę na danej X, tymczasem dana ta jest już zablokowana przez transakcję Tj. Jeżeli transakcja Tj nie czeka na uzyskanie innej blokady, Ti będzie czekać na zwolnienie blokady przez Tj. W przeciwnym wypadku Ti będzie wycofana i restartowana.
IR (współdzielona) - transakcja zamierza uzyskiwać blokady typu R na poszczególnych obiektach składowych;
IW (wyłączna) - transakcja zamierza uzyskiwać blokady typu W na poszczególnych obiektach składowych;
RIW (mieszana) - transakcja blokuje wszystkie obiekty składowe blokadą typu R, a na niektórych zamierza uzyskiwać blokady typu W.
Żądanie uzyskania blokady W na danym obiekcie jest pośrednim żądaniem ustawienia blokad W na wszystkich obiektach składowych.
Żądanie uzyskania blokady R lub RIW na danym obiekcie jest pośrednim żądaniem ustawienia blokad R na wszystkich obiektach składowych.
Zanim transakcja uzyska blokadę typu IR lub R na danym obiekcie, musi uzyskać blokadę typu IR na co najmniej jednym zawierającym go obiekcie wyższego poziomu.
Zanim transakcja uzyska blokadę typu IW, RIW lub W na danym obiekcie, musi uzyskać blokadę typu IW na wszystkich zawierających go obiektach wyższego poziomu.
Zanim transakcja zwolni blokadę na danym obiekcie musi wpierw zwolnić wszystkie blokady z obiektów składowych.
Algorytmy znaczników czasowych
Read_TS(x) - największy znacznik czasowy spośród wszystkich transakcji, które pomyślnie odczytały tę daną.
Write_TS(x) - największy znacznik czasowy spośród wszystkich transakcji, które pomyślnie zapisały tę daną.
System chce odczytać daną x (pierwsza operacja). Ponieważ Read_TS(x)=6, TS(T1)=8 i 6<8, więc operacja odczytu zostaje wykonana (patrz wyżej na algorytm dla operacji Read). Ponieważ Read_TS(x) < TS(T1), zmianie ulega znacznik czasowy Read_TS(x) przyjmując wartość 8.
Podobna sytuacja co w punkcie 1. Tym razem transakcja T2 chce odczytać daną y. Ponieważ Read_TS(y)=6, TS(T2)=9 i 6<9, więc dana zostaje odczytana i od teraz Read_TS(y)=9.
Transakcja T1 chce dokonać operacji zapisu. Ponieważ Read_TS(y)=9, TS(T2)=8, czyli 9>8, to (patrz wyżej algorytm operacji Write) transakcja T1 jest wycofywana. W tej sytuacji zostają także wycofane wyniki operacji z punktu 1 i od teraz Read_TS(x) znowu wynosi 6.
Algorytmy optymistyczne
Faza odczytu: Transakcje czytają dane z bazy danych. Wprowadzane modyfikacje są przechowywane w lokalnych obszarach roboczych transakcji.
Faza walidacji: Wykonywana jest walidacja uszeregowalności transakcji. Transakcje niespełniające kryterium uszeregowalności są wycofywane i restartowane.
Faza zapisu: Jeżeli faza walidacji zakończy się pomyślnie, modyfikacje transakcji są wprowadzane do bazy danych.
(Ri Wi) Wj = i Ti zakończyła swoją fazę odczytu zanim Ti zakończyła swoją fazę odczytu.
Wielowersyjne bazy danych
Uszeregowalność wielowersyjna
h : → jest takim odwzorowaniem operacji odczytu {ri(x)∈ (τ)} w zbiór operacji zapisu {wj(x)∈ (τ)}, że dla każdej operacji odczytu ri(x)∈ (τ) , jeżeli h(ri(x))=wj(x), to wj(x) pwr ri(x).
Algorytm wielowersyjnego blokowania dwufazowego (dwuwersyjny)
dana niezablokowana 0
dana zablokowana dla odczytu R
dana zablokowana dla zapisu W
dana zablokowana do akceptacji C
Wielowersyjny algorytm znaczników czasowych
Read_TS(xi) - największy (najpóźniejszy) znacznik czasowy ze zbioru wszystkich transakcji, które pomyślnie odczytały i-tą wersję danej x.
Write_TS(xi) - znacznik czasowy transakcji, która utworzyła i-tą wersję danej x.
Odtwarzanie transakcyjne
Pojęcia wstępne
ulotna (volatile)
trwała (nonvolatile)
zostaną usunięte w wyniku zastosowania strategii LRU,
zostaną zapisane na dysku po zadanym czasie.
Format logu
atomowa
trwała
w momencie akceptacji transakcji
w momencie przepełnienia bufora (double-buffered disk write)
może się okazać, że zapisaliśmy na dysk strony uaktualnione przez nie zaakceptowane transakcje,
może się okazać, że nie zapisaliśmy na dysk stron uaktualnionych przez zaakceptowane transakcje.
ROLLBACK
ROLL FORWARD
Poprawność odtwarzania
zapis na dysk jest realizowany w sposób atomowy (read after write - zaraz po zapisie system czyta daną, by upewnić się, że została ona zapisana poprawnie)
akceptacja transakcji + zapis bufora logu − akcja atomowa
Punkty kontrolne
do momentu inicjacji (startup) systemu
do stanu określonego przez użytkownika (administratora)
procedura ROLLBACK - większość transakcji to krótkie transakcje aktualizacji - stosunkowo efektywna
procedura ROLL FORWARD - konieczność przetworzenia całego pliku logu - niska efektywność
punkt kontrolny akceptacyjnie spójny (commit-consistent checkpointing)
punkt kontrolny spójny z pamięcią podręczną (cache-consistent checkpointing)
punkt kontrolny rozmyty (fuzzy checkpointing)
Punkt kontrolny akceptacyjnie spójny
Do momentu zakończenia procedury nie są inicjowane nowe transakcje.
Przetwarzanie transakcji jest kontynuowane do momentu zakończenia i akceptacji wszystkich transakcji aktywnych..
Bufor logu jest zapisywany na dysk do pliku logu. Wszystkie brudne strony w buforze zostają zapisane na dysk.
Po wykonaniu kroków 1-3 system zapisuje specjalny rekord logu (CKPT) na dysk, co kończy procedurę tworzenia punktu kontrolnego.
Punkt kontrolny spójny z pamięcią podręczną
Do momentu zakończenia procedury nie są inicjowane nowe transakcje.
Zostaje zawieszone wykonywanie transakcji aktywnych.
Bufor logu jest zapisywany na dysk do pliku logu. Wszystkie brudne strony w buforze zostają zapisane na dysk.
Po wykonaniu kroków 1-3 system zapisuje specjalny rekord logu (CKPT, List) na dysk, co kończy procedurę tworzenia punktu kontrolnego. List zawiera listę aktywnych transakcji w momencie tworzenia punktu kontrolnego.
Rozmyty punkt kontrolny
Brudne strony, które pojawiły się w buforze w okienku czasowym (CKPTN-2, CKPTN-1), tj. były brudne w momencie tworzenia punktu kontrolnego CKPTN-1, są zapisywane na dysku
Do momentu zakończenia procedury nie są inicjowane nowe transakcje
Bufor logu uzupełniony o specjalny rekord logu postaci (CKPTN, List) jest zapisywany na dysk do pliku logu (List zawiera listę aktywnych transakcji w momencie tworzenia punktu kontrolnego)
Zbiór brudnych stron w buforze, które powstały w okienku czasowym (CKPTN-1, CKPTN), jest zaznaczany specjalnym znacznikiem w katalogu bufora (informacja ta nie jest zapisywana na dysku). Koniec procedury tworzenia punktu kontrolnego.
Dodatki
Wykorzystanie pliku logu
time-domain addressing - zastosowanie pliku logu do odtwarzania wersji na podstawie operacji,
accounting - naliczanie kosztów (każdy rekord logu dotyczy transakcji o określonym identyfikatorze, który w najprostszym przypadku może identyfikować użytkownika),
performance analisys - analiza efektywności,
analiza poprawności ograniczeń integralnościowych,
określanie wąskich gardeł w systemie.
Log Manager
hermetyzacja: jest on odpowiedzialny za poprawne wypełnienie nagłówka rekordu logu,
startup,
careful writes.
Log Sequence Number
Transakcje w środowisku rozproszonym
Optymalizacja zapytań
Wykonywanie zapytań w relacyjnych bazach danych
Definicja problemu
reguły transformacji służące do generowania przestrzeni stanów dla danego zapytania,
algorytm przeszukiwania przestrzeni stanów pozwalających na przechodzenie między poszczególnymi stanami,
funkcja kosztu, która jest stosowana do każdego ze stanów.
o równomierności rozkładu wartości atrybutów,
o niezależności atrybutów.
Typy optymalizatorów
Klasyfikacja ze względu na podejście
Klasyfikacja ze względu na algorytmy przeszukiwania przestrzeni stanów
Klasyfikacja ze względu na sposób generowania planów
Klasyfikacja ze względu na ziarno optymalizacji
Fizyczne operacje na bazie danych
Implementacja operacji selekcji
adresowanie otwarte,
łańcuchowanie - w bloku b znajduje się wskaźnik do bloku n, gdzie znajdują się rekordy, które miały trafić do b,
wielokrotne adresowanie - stosuje się kolejno inne funkcje haszujące.
Implementacja operacji połączenia
Inne operacje
operacja projekcji
operacja sortowania
operacja agregacji
operacja sumy zbiorów
operacja iloczynu zbiorów
operacja różnicy zbiorów
operacja iloczynu kartezjańskiego
usuwanie duplikatów ze zbioru
Optymalizacja składniowa
Problemy optymalizacji
model planu,
funkcja kosztu,
algorytm przeszukiwania przestrzeni.
Modele planu wykonania
Pracownicy - jednym z atrybutów jest identyfikator instytutu, w którym pracuje pracownik (Id_Inst),
Instytuty - atrybutami są m.in.: identyfikator instytutu (Id_Inst) i budżet isntytutu (Budżet).
Algorytmy przeszukiwania
pełne przeszukiwanie (exhaustive search)
programowanie dynamiczne
heurystyki
optymalizacja składniowa
Iterative Improvement
Simulated Annealing
Tabu Search
Stan − akceptowalny plan wykonania zapytania.
Przestrzeń stanów − zbiór wszystkich możliwych stanów.
Ruch − wygenerowanie i przejście do nowego stanu.
Sąsiad − stan osiągany ze stanu bieżącego za pomocą jednego ruchu.
Koszt stanu − wartość funkcji kosztu dla danego planu zapytania.
Minimum lokalne − stan, dla którego żaden z sąsiadów nie posiada niższego kosztu.
Minimum globalne − stan o najniższym koszcie w przestrzeni stanów (rozwiązanie optymalne).
Wybierz losowo stan początkowy.
Przeszukuj przestrzeń stanów przez wykonywanie ruchów, akceptując tylko sąsiadów z niższym kosztem, aż do osiągnięcia minimum lokalnego.
Powtarzaj kroki 1. i 2. do momentu spełnienia warunku kończącego optymalizację.
Zwróć najlepsze znalezione minimum lokalne.
Wybierz losowo stan początkowy.
Dobierz początkową temperaturę T.
Redukując stopniowo T przeszukuj przestrzeń stanów, akceptując zawsze sąsiadów z niższym kosztem i akceptując sąsiadów o wyższym koszcie z prawdopodobieństwem e-C/T.
Gdy system zostanie zamrożony zwróć najlepszy znaleziony stan.
Wybierz losowo stan początkowy.
Przeszukuj przestrzeń stanów przez wykonywanie ruchów, pamiętając na liście Tabu ostatnio odwiedzone stany. Aby wykonać ruch:
wygeneruj zbiór sąsiadów, którzy nie figurują na liście Tabu,
wykonaj ruch w stronę najlepszego znalezionego sąsiada.
Powtarzaj krok 2. do momentu spełnienia warunku kończącego optymalizację.
Zwróć najlepszy znaleziony stan.
Funkcja kosztu
dostęp do pamięci masowej: szukanie, czytanie i zapis bloków dyskowych (podstawowa część kosztów),
koszt składowania wyników pośrednich (materializacja),
czas przetwarzania,
zajętość pamięci operacyjnej,
koszty komunikacyjne
liczba rekordów w pliku,
liczba bloków danych zajmowanych przez plik,
średnia zajętość bloku,
średnia długość rekordu,
liczba różnych wartości danego atrybutu,
wartości minimalna i maksymalna każdego atrybutu,
rozkład wartości,
wysokość indeksu,
liczba liści w indeksie,
współczynnik uporządkowania indeksowanego atrybutu.
Optymalizacja w systemach rozproszonych
Systemy rozproszone
Cele rozpraszania danych
świat jest rozproszony, autonomia (struktura systemu informatycznego powinna odpowiadać strukturze fizycznej przedsiębiorstwa)
wzrost dostępności danych
wzrost niezawodności (upadek jednego stanowiska nie blokuje całego systemu)
wzrost efektywności
dane bliżej producentów danych
dane bliżej konsumentów danych
równoległość przetwarzania
otwartość systemu - możliwość rozbudowy
koszt (koszt systemu rozproszonego jest z reguły niższy niż koszt systemu zcentralizowanego).
Klasyfikacja SRBD
systemy rozproszone
systemy równoległe
homogeniczne SRBD (na każdym stanowisku działa ten sam SRBD)
heterogeniczne SRBD (na każdym stanowisku może działać inny SRBD, np. Oracle, Progress, Sybase; podstawowym problemem jest tutaj zagwarantowanie współpracy wielu różnych SZBD)
sfederowane (półautonomiczne)
wielobazowe (autonomiczne)
systemy replikowane
systemy niereplikowane
TP Light (umożliwiają budowanie systemów rozproszonych w oparciu o jeden system SZBD)
TP Heavy - monitory transakcji (X/Open DTP) (jest to dodatkowe oprogramowanie spoza SZBD i umożliwiające dostęp do oddzielnych baz danych)
Fragmentacja
fragmentacja pozioma do fragmentów pionowych
fragmentacja pionowa do fragmentów poziomych
fragmenty definiujemy wybierając odpowiedni predykat selekcji odpowiadający dominującym transakcjom, np.
fragmenty powinny być rozłączne a ich suma powinna odtwarzać oryginalną relację (oczywiście nie dotyczy to powielających się przy fragmentacji pionowej unikalnych kluczy)
relacja vs rekord - problem optymalizacji wielkości fragmentaryzowanej jednostki.
Alokacja danych
Problem alokacji danych
scentralizowana baza danych
niereplikowana RBD
całkowicie replikowana RBD
częściowo replikowana RBD
read availability (dostępność do odczytu)
write availability (dostępność do zapisu)
update time (czas pielęgnacji kopii) - im więcej kopii tym więcej danych do uaktualnienia (koszt rośnie wykładniczo)
storage cost (koszt przechowywania kopii fragmentów) - wzrasta proporcjonalnie do liczby kopii
local processing time (czas lokalnego przetwarzania)
query time (czas realizacji zapytania) - zwiększenie liczby kopii zwiększa efektywność, dzięki czemu użytkownik krócej czeka na realizację jego zapytania
Specyfikacja systemu aplikacji
globalny schemat pojęciowy
schemat fragmentacji relacji
zbiór transakcji i ich częstość
bezpieczeństwo: autoryzacja dostępu
odtwarzanie: częstość i wolumeny operacji odtwarzania
integralność: ograniczenia referencyjne i integralnościowe, dziennik
Konfiguracja systemu
topologia sieci
pojemność kanałów komunikacyjnych
metoda dostępu do medium
informacja o stanowiskach i ich mocy obliczeniowej
konsumenci i producenci danych
zarządzanie transakcjami (algorytmy)
koszt pamiętania danych
koszt przetwarzania danych
koszt komunikacji
czas odpowiedzi systemu na zapytanie użytkownika (zakładamy, że system optymalizuje wykonanie zapytania)
przepustowość (sumaryczny czas odpowiedzi)
Strategie alokacji danych
Algorytm „najlepszego dopasowania” dla niereplikowanych RBD
Relacja R1 zostanie zapamiętana na stanowisku S4
Relacja R2 zostanie zapamiętana na stanowisku S5
Relacja R3 zostanie zapamiętana na stanowisku S2
Algorytm „optymalizacji zysku” (ABS) dla replikowanych RBD
Algorytm „progresywnej alokacji fragmentów” (PFA) dla replikowanych RBD
Nowe struktury indeksów dla magazynów danych
Wprowadzenie
przeszukiwanie indeksu jest szybsze, bo plik indeksu jest mniejszy niż plik relacji,
plik indeksowy jest plikiem uporządkowanym, stąd możliwe jest stosowanie szybszego przeszukiwania binarnego zamiast liniowego.
OLTP - obsługa bieżącej działalności firmy
OLAP - przetwarzanie analityczne w celu wspomagania decyzji (dane się nie zmieniają a nas interesuje analiza statystyczna na podstawie danych archiwalnych).
Pojęcia podstawowe
Indeks w postaci B+-drzewa
Mapa bitowa (ang. bitmap)
Krotność atrybutu (ang. cardinality)
Indeks bitmapowy (ang. bitmapped index)
zbiór map bitowych - jedna mapa dla każdej unikalnej wartości atrybutu relacji
w postaci B+-drzewa z mapami bitowymi w liściach (ta struktura jest lepsza)
Indeks bitmapowy w postaci B+-drzewa
Operacje na mapach bitowych
Indeks bitmapowy - zalety
Mały rozmiar dla atrybutów o małej krotności (małej liczby możliwych wartości)
przykład:
Szybkość przetwarzania
przetwarzanie w RAM (gdy indeks będzie mały, to będzie się w całości mieścił w RAM, co przyspieszy dostęp do danych)
przetwarzanie 64 bitów w jednym cyklu zegara
szybkie operacje AND, OR, NOT, COUNT na mapach bitowych
funkcja COUNT operuje na indeksie bitmapowym
zmniejszenie liczby operacji I/O
Indeks bitmapowy - wady
Duży rozmiar dla atrybutów o dużej krotności (rozmiar indeksu dość gwałtownie rośnie wraz ze wzrostem krotności atrybutu)
przykład:
zmniejszenie rozmiaru przez
kompresję map bitowych
transformację do B+-drzewa
Koszty uaktualniania indeksów w trakcie pracy systemu (jest to znacznie poważniejsza wada)
Uaktualnianie indeksu
mapa bitowa dla wstawianej wartości już istnieje
uaktualnij mapę
mapa bitowa dla wstawianej wartości nie istnieje
utwórz mapę
w obu przypadkach uaktualnij długość wszystkich istniejących map bitowych
atrybut przyjmuje jedną z wartości istniejących w relacji
uaktualnij mapy dla starej i nowej wartości atrybutu
atrybut przyjmuje nową wartość
utwórz nową mapę bitową dla nowej wartości
uaktualnij mapę bitową dla starej wartości
usunięto krotkę, której atrybut posiadał wartość występującą w relacji tylko raz
usuń mapę bitową dla wartości tego atrybutu
usunięto krotkę, której atrybut posiadał wartość występującą w relacji wielokrotnie
uaktualnij mapę bitową dla usuniętej wartości
w obu przypadkach utrzymuj tzw. mapę usuniętych krotek
Odwzorowywanie mapy bitowej w adresy rekordów
Rekordy o stałej długości
Rekordy o zmiennej długości
Indeks połączeniowy
B+-drzewo (jak na rysunku powyżej)
indeks połączeniowy z mapami bitowymi w liściach bitmapowy indeks połączeniowy
Nowe struktury indeksów w komercyjnych SZBD
Ocena efektywności indeksów bitmapowych i B-drzew
Środowisko pomiarowe
Oracle7 Server Release 7.3.2.1.0
SPARCserver 630 MP
2 SuperSPARC 50MHz, 128MB RAM
Sun Solaris 2.5
statystyki tkprof
Optymalizator kosztowy
Efektywność indeksów - rozmiary
Efektywność przetwarzania
Podsumowanie
Nowe rodzaje indeksów dla magazynów danych:
bitmapowe
połączeniowe
bitmapowe połączeniowe
Własności indeksów bitmapowych zalety
mały rozmiar dla atrybutów o niskiej krotności
przechowywanie w RAM
szybkie wyszukiwanie
zmniejszenie liczby operacji I/O („wąskie gardło”)
efektywne przetwarzanie map bitowych: AND, OR, NOT, COUNT
szybkie przetwarzanie dla operatorów równościowych w warunkach selekcji
Własności indeksów bitmapowych wady
złożony proces uaktualniania indeksów
mniejsza efektywność dla operatorów innych niż równościowe
Modelowanie danych - projektowanie baz danych
Modelowanie funkcji / procesów
Modelowanie przepływów danych
Narzędzia CASE
Symptomy braku integracji:
Integracja producentów i konsumentów danych:
Cykl życia systemu informatycznego |
Proces projektowania bazy danych |
Strategia i Analiza |
Pojęciowe modelowanie danych |
Projektowanie |
Projektowanie struktur logicznych Projektowanie struktur fizycznych |
Implementacja |
(utworzenie bazy danych) |
Wdrożenie |
(przeniesienie danych) |
Eksploatacja |
(strojenie bazy danych) |
Problemy:
1. Pojęciowe modelowanie danych
2. Projektowanie struktur logicznych
3. Projektowanie struktur fizycznych
Automatyzacja procesu za pomocą narzędzi:
Jest to podejście strukturalne, którego podstawową zaletą jest prostota w zrozumieniu. Według tego podejścia świat jest zbiorem encji i powiązań między nimi. W podejściu obiektowym cały świat to zbiór (hierarchia) obiektów mających własności behawioralne.
Termin angielski Termin polski
semantic network sieć semantyczna
attribute atrybut
attribute domain dziedzina wartości atrybutów
entity encja
relationship związek
cardinality of relationship stopień asocjacji związku
entity relationship model model związków encji
Koncepcja sieci semantycznych (Quillian 1968)
Notacja Chena [1976]
Konstruktory modelu:
Oprócz notacji Chena istnieje jeszcze wiele innych, komercyjnych (np. notacja firmy Oracle). Zasadniczą różnicą jest to, że w notacji Chena związkowi można nadawać atrybuty, co nie jest możliwe w notacjach komercyjnych.
Mimo to, większość diagramów będzie tu przedstawiana w notacji Oracla.
I. ENCJE
Encja i wystąpienie encji
Obiekty w świecie rzeczywistym
Firma zatrudnia pracowników. Chcemy znać dane personalne każdego pracownika (imię, nazwisko, adres zamieszkania i numer telefonu).
Identyfikacja wspólnych cech obiektów Model
Encja Wystąpienia encji
Własności encji:
Obiekty materialne i niematerialne
Obiekty materialne
Obiekty niematerialne
Zdarzenia
Fakty
II. ZWIĄZKI
Związki i powiązania
Związki wyrażają powiązania między obiektami w świecie rzeczywistym
Pracownicy firmy posiadają różnej marki samochody.
Pomiędzy pracownikami i samochodami istnieją powiązania:
Identyfikacja powiązań o wspólnych cechach Model
Związek i jego interpretacje
Nazwy związku, będące jego interpretacją, powinny być tak dobierane, aby było możliwe budowanie zdań w języku naturalnym:
Własności związków
Cechy związku:
Wiemy, że:
Chcemy wiedzieć:
Jakiej użyć notacji?
Stopnie asocjacji
Stopnie asocjacji - notacje graficzne:
Stopień asocjacji związków 1:N
Powiązania o charakterze „jeden do wielu”
Firma realizuje projekty zlecone przez różnych klientów. Dany projekt wykonywany jest dla jednego konkretnego klienta a dany klient może zlecić wykonanie wielu projektów.
Związek „jeden do wielu”:
Interpretacja związku:
Stopień asocjacji związków M:N
Powiązanie o charakterze „wiele do wielu”
Projekty są realizowane przez pracowników. Każdy projekt jest realizowany przez jednego lub wielu pracowników. Każdy pracownik może brać udział w realizacji jednego lub wielu projektów.
Związek „wielu do wielu”:
Interpretacja:
Stopień asocjacji związków 1:1
Powiązania o charakterze „jeden do jednego”
Działy firmy kierowane są przez pracowników. Dany dział może być kierowany tylko przez jednego pracownika (kierownika działu), a dany pracownik może kierować nie więcej niż jednym działem.
Związek „jeden do jednego”:
Interpretacja:
Opcjonalność i obligatoryjność związków
Opcjonalność i obligatoryjność - notacje graficzne:
Opcjonalność w świecie rzeczywistym:
Obligatoryjność w świecie rzeczywistym:
Jednostronna obligatoryjność
Interpretacja:
Dwustronna obligatoryjność
Firma posiada samochody dostawcze. Dla każdego samochodu musimy znać dane dotyczące ostatniego przeglądu technicznego. Każdy przegląd techniczny, o którym przechowujemy informacje musi dotyczyć jednego z samochodów firmy.
Interpretacja:
Dwustronna opcjonalność
Każdy pracownik może (ale nie musi) posiadać stopień naukowy oraz istnieją stopnie naukowe, które nie muszą być zdobyte przez żadego z pracowników.
Interpretacja:
Narność związków
Związek unarny
Łączy encję z samą sobą.
Związek binarny
Powiązania dwóch rodzajów obiektów Związek dwóch wystąpień encji
Związek ternarny
Notacje graficzne:
Powiązania trzech obiektów Związek trzech wystąpień encji
Interpretacja:
III. HIERARCHIA ENCJI
Hierarchia encji
Często okazuje się, że wiele encji posiada wiele cech wspólnych, przez co część informacji jest powielana. Encje takie możemy łączyć w hierarchie (generalizować je).
Dziedziczenie atrybutów
Firma zatrudnia pracowników krajowych i zagranicznych. Wszyscy pracownicy są opisani pewnymi wspólnymi atrybutami, ale zarówno pracownicy krajowi jak i zagraniczni posiadają atrybuty specjalne.
Własności hierarchii encji:
Dziedziczenie związków
Każdy pracownik jest zatrudniony na określonym stanowisku w jednym z działów firmy. W odniesieniu do pracowników krajowych chcemy wiedzieć, w jakich zakładach byli poprzednio zatrudnieni.
Własności hierarchii encji:
Hierarchia encji bez specyficznych atrybutów - ŁUK
Chcemy przechowywać opis każdej naprawy dotyczącej środków trwałych i elementów wyposażenia. Opis naprawy w oby przypadkach jest podobny.
Hierarchia encji
Łuk
Własności:
Zaletą przyjętego modelu jest jego prostota. Wynikają jednak z tego pewne wady - nie da się zamodelować wszystkiego co występuje w świecie rzeczywistym.
W modelu Chena mamy dwa rodzaje hierarchii encji:
Własności atrybutów - ograniczenia integralnościowe
Dziedzina wartości
Obligatoryjność
Unikalny identyfikator
Zawężenie dziedziny wartości
Dynamika wartości
Własności związków - ograniczenia integralnościowe
Obligatoryjność
Unikalność
Wzajemne wykluczanie (łuk)
Nieprzenoszalność
Unikalny identyfikator encji
W klasycznym modelu Chena istnieją dwa rodzaje encji:
W oraclowym CASE istnieje założenie, że występuje jedynie jeden typ encji - encje silne.
Naturalne atrybuty identyfikujące. Na jeden lub kilka rzeczywistych atrybutów nakładamy ograniczenie unikalności.
Sztuczny atrybut identyfikujący
W przypadku, gdy:
do zbioru naturalnych atrybutów encji dodajemy sztuczny atrybut pełniący rolę unikalnego identyfikatora.
Związki identyfikujące
Na co najmniej dwa związki nakładamy ograniczenie unikalności.
Identyfikatory złożone
Ograniczenie unikalności nakładamy jednocześnie na atrybut lub kilka atrybutów i związek lub klika związków.
Unikalne identyfikatory w hierarchii encji
Metody definiowania unikalnego identyfikatora w hierarchii encji:
Generalizacja musi posiadać unikalny identyfikator (choćby sztuczny).
Unikalny identyfikator na poziomie generalizacji:
Własności:
Unikalne identyfikatory na poziomie specjalizacji:
Tłumaczenie wybranych terminów
Termin angielski Termin polski
composite attribute atrybut złożony
multivalued attribute atrybut wielowartościowy
aggregation agregacja
top-down approach podejście od ogółu do szczegółu
bottom-up approach podejście od szczegółu do ogółu
Atrybut czy encja?
Problem:
Przykład:
Pracownik pracuje w instytucie. Który wariant wybrać?
Gdy chcemy przechowywać np. adres instytutu, nr telefonu, itp., to wybierzemy wariant a - INSTYTUT jest nową encją powiązaną z encją PRACOWNIK. Natomiast, gdy ważne jest tylko miejsce zatrudnienia, wtedy wybierzemy wariant b - INSTYTUT jest atrybutem encji PRACOWNIK.
Atrybut traktujemy jako nową encję:
Związek czy encja?
Problem:
Przykład 1
Produkty przechowujemy w magazynach. Chcemy wiedzieć, w jakich magazynach przechowywany jest dany produkt oraz, jakie produkty przechowujemy w danym magazynie. Czy wystarczy związek „wiele do wielu”?
Przykład 2
Pracownicy znają języki obce (modelowane jako encja). Opisz sytuację, w której wystarczy związek pomiędzy pracownikiem i językiem obcym oraz sytuację, w której potrzebna jest nowa encja.
Zastępowanie związku M:N encją
Kiedy zastępujemy związek M:N nową encją?
Część ograniczeń wynika z narzędzia (konkretnego CASE'a) a część z modelu relacyjnego.
Przykład:
Własności:
Zastępowanie związku n-arnego encją
Kiedy związek n-arny zastępujemy nową encją?
Przykład:
Własności:
Atrybuty złożone
Modelowanie atrybutów złożonych:
Atrybuty wielowartościowe
Modelowanie atrybutów wielowartościowych:
W komercyjnym modelu relacyjnym, który jest znormalizowany, nie można definiować atrybutów wielowartościowych, gdyż atrybut w każdej krotce musi być atomowy.
Agregacja
Przykłady agregacji:
Modelowanie agregacji:
Hierarchia encji vs. agregacja
Różne rodzaje obiektów w świecie rzeczywistym
Firma produkuje trzy rodzaje zabawek: mechaniczne, gry planszowe i pluszowe maskotki.
Hierarchia encji:
Agregacja:
Który model jest prawidłowy?
W hierarchii podklasy się wykluczają - jest to pewne ograniczenie. Agregacja jest bardziej elastyczna, można zamodelować wszystko - byle było to zgodne z rzeczywistością.
Hierarchia danych
Przykłady powiązań hierarchicznych:
Modelowanie hierarchii danych
Modelowanie czasu
Dane ponadczasowe:
zbiór stanowisk, marki samochodów, miasta, itp.
Dane opisujące stan aktualny:
wynagrodzenie, koszt surowców, cena sprzedaży, itp.
Dane opisujące zdarzenia nieregularne:
przyznanie nagrody, zakup towaru, itp.
Dane opisujące nieregularne okresy czasu:
urlop pracownika, wypożyczenie książki, itp.
Dane opisujące zdarzenia regularne:
wypłata dla pracownika, pobranie składki, itp.
Dane opisujące regularne okresy czasu:
przyznany budżet, pula miejsc - w danym okresie czasu, itp.
Wersjonowanie danych
Wartości niektórych atrybutów zmieniają się w czasie. Chcemy przechowywać pewne informacje historyczne o tych atrybutach. Każdemu atrybutowi przyporządkowujemy nową niezależną encję (np. POPRZEDNIE WYNAGRODZENIE). Wersjonować można: atrybuty, encje, związki i hierarchie.
Wersjonowanie atrybutów
Wersjonowanie związków
Transformacja schematu pojęciowego do modelu relacyjnego generuje trzy typy relacji:
Relacje te zawierają te same informacje co odpowiadające im encje. Transformacja taka występuje w przypadku każdej encji powiązanej z innymi encjami jednym z poniższych związków:
Dotyczy to encji powiązanych następującymi związkami:
do relacji wchodzą dodatkowe atrybuty wynikające ze związków.
Relacje zawierające klucze obce wszystkich encji należących do związku. Transformacja taka występuje zawsze w odniesieniu do jednego z poniższych związków:
Wartości puste są dopuszczalne podczas transformacji wyłącznie w relacjach encji dla kluczy obcych encji opcjonalnych. Nie są natomiast dopuszczalne w relacjach encji dla kluczy obcych encji obowiązkowych. Wartości puste nie są również dopuszczalne w relacjach związków dla kluczy obcych.
a) Dwie encje - związek binarny
Każdy student ma jednego sponsora; jeden sponsor sponsoruje jednego studenta.
Student (Emp_no, …, Spon_emp_no)
Sponsor (Spo_emp_no, …)
Wartości puste są zabronione dla atrybutu Spon_emp_no relacji Student.
Jedna z encji jest transformowana do relacji encji przy zachowaniu takiej samej nazwy i takich samych atrybutach, jednym słowem jest to kopia z modelu. Tu taką encją jest Sponsor. Natomiast druga z encji jest transformowana do relacji encji z kluczem obcym, którym jest klucz do relacji pierwszej. Tu taką relacją jest Student. Kluczem obcym jest atrybut Spon_emp_no.
Obligatoryjność lub dowolność w modelu związków encji, po przetransformowaniu, przejawia się w ograniczeniach integralnościowych wpisywanych do relacji.
Przykładowo implementacja bazy danych może wyglądać następująco:
create table Student
( . . .
Snazwisko Char(20) foreign key Snazwisko reference Sponsor,
. . . )
Klucz obcy służy łączeniu relacji i jest on atrybutem innej relacji. Istnieje tu niebezpieczeństwo utraty integralności, stąd konieczne jest zdefiniowanie akcji jakie mają być przez system podejmowane przy usuwaniu krotek z połączonych relacji.
* * *
Każdy wydział posiada jednego szefa; jeden pracownik może być szefem jednego wydziału.
Wydział (Dept_no, …, Emp_no)
Pracownik (Emp_no, …)
Wartości puste są zabronione dla atrybutu Emp_no relacji Wydział.
Atrybut Emp_no relacji Wydział stanowi identyfikator kierownika wydziału. Można także utworzyć takie relacje:
Wydział (Dept_no)
Pracownik (Emp_no, …, Dept_no)
w których relacja Pracownik byłaby relacją z kluczem obcym. Byłoby to poprawne ale nieekonomiczne.
* * *
Pewne PC komputery są przydzielone inżynierom (chociaż nie wszystkim).
Inżynier (Emp_no, …, PC_no)
PC (PC_no, …)
Wartości puste są dopuszczalne dla atrybutu PC_no relacji Inżynier.
* * *
Jeden pracownik pracuje dokładnie w jednym instytucie; jeden instytut zatrudnia wielu pracowników.
Pracownik (Emp_no, …, Dept_no)
Instytut (Dept_no, …)
Wartości puste są zabronione dla atrybutu Dept_no relacji Pracownik.
W przypadku związku 1:1 mogliśmy klucz obcy umieścić w zasadzie w dowolnej relacji. W przypadku związku 1:n. postępujemy zawsze tak samo: encja po stronie 1 jest transformowana do relacji encji natomiast encja po stronie n jest transformowana do relacji encji z kluczem obcym.
* * *
Każdy inżynier może posiadać co najwyżej jedną sekretarkę; jedna sekretarka może pracować dla wielu inżynierów.
Inżynier (Emp_no, …, Sec_emp_no)
Sekretarka (Sec_emp_no, …)
Wartości puste są dopuszczalne dla atrybutu Sec_emp_no relacji Inżynier.
* * *
Inżynierowie mogą należeć do wielu stowarzyszeń; stowarzyszenia zrzeszają wielu inżynierów.
Inżynier (Emp_no, …)
Stowarzyszenie (Stow_no, …)
Należy_do (Stow_no, Emp_no, …)
Wartości puste są zabronione dla atrybutów Stow_no i Emp_no relacji Należy_do.
Tutaj mamy do czynienia ze związkiem n:m. Koniecznie tworzymy dodatkową relację o nazwie związku (tu: Należy_do). Kluczem relacji Należy_do jest klucz złożony z dwóch kluczy obcych.
Jednym słowem związek encji wyrażony na diagramie a jest równoważny diagramowi b, gdyż ich transformacje do modelu relacyjnego dają takie same wyniki.
b) Jedna encja - związek unarny
Związek unarny typu 1:1 jest zawsze obowiązkowy lub zawsze opcjonalny dla obu stron związku. Pojawiają się tu także role przedstawiane w postaci kluczy obcych.
Każdy student ma jednego kolegę za partnera w projekcie.
Student (Stud_no, …, Pa_stud_no)
Wartości puste są zabronione dla atrybutu Pa_stud_no relacji Student.
Następuje tu automatyczna transformacja do relacji encji z kluczem obcym:
* * *
Każdy student może mieć jednego kolegę za partnera w projekcie.
Student (Stud_no, …, Pa_stud_no)
Wartości puste są dopuszczalne dla atrybutu Pa_stud_no relacji Student.
W przypadku związku typu 1:n klucz obcy relacji występuje w relacji podstawowej i jego wartość może być wartością pustą jeżeli klasa przynależności jest dowolna.
* * *
Inżynierowie są podzieleni na grupy; każda grupa może mieć jednego lidera.
Inżynier (Emp_no, …, Lid_emp_no)
Wartości puste są dopuszczalne dla atrybutu Lid_emp_no relacji Inżynier.
Atrybut Lid_emp_no jest identyfikatorem lidera grupy.
* * *
Inżynierowie są podzieleni na grupy; każda grupa ma jednego lidera.
Inżynier (Emp_no, …, Lid_emp_no)
Wartości puste są zabronione dla atrybutu Lid_emp_no relacji Inżynier.
* * *
Każdy projekt ma powiązania z innymi projektami.
Projekt (Proj_no, …)
Powiązania (Proj_no, Rel_proj_no, …)
Wartości puste są dopuszczalne dla atrybutów Proj_no i Rel_proj_no relacji Powiązania.
Następuje transformacja do dwóch relacji, z których jedna jest reprezentacją związku.
c) Związki ternarne
Każdy inżynier używa jednej księgi rozchodów dla jednego projektu. Różni inżynierowie używają różnych ksiąg rozchodów dla tego samego projektu. Żaden inżynier nie stosuje tej samej księgi rozchodów dla różnych projektów.
Inżynier (Emp_no, …)
Projekt (Proj_no, …)
Księga (Księga_no, …)
Używa (Emp_no, Proj_no, Księga_no, …)
lub Używa (Emp_no, Proj_no, Księga_no, …)
lub Używa (Emp_no, Proj_no, Księga_no, …)
Wartości puste są zabronione dla atrybutów Emp_no, Proj_no i Księga_no relacji Używa.
* * *
Każdy inżynier występuje w danym projekcie w różnej funkcji.
Inżynier (Emp_no, …)
Projekt (Proj_no, …)
Funkcja (Funkcja_no, …)
Używa (Emp_no, Proj_no, Funkcja_no, …)
Wartości puste są zabronione dla atrybutów Emp_no, Proj_no i Funkcja_no relacji Używa.
Każda encja jest transformowana do relacji encji i dodatkowo związek jest transformowany do relacji encji z kluczem złożonym.
* * *
Każdy pracownik jest zatrudniony w kilku projektach, ale może być zatrudniony co najwyżej w jednym projekcie zlokalizowanym w jednym miejscu.
Inżynier (Emp_no, …)
Projekt (Proj_no, …)
Lokalizacja (Loc_no, …)
Używa (Emp_no, Proj_no, Loc_no, …)
Wartości puste są zabronione dla atrybutów Emp_no, Proj_no i Loc_no relacji Używa.
* * *
Uczniowie uczestniczą w realizacji projektów pod nadzorem instruktorów. Instruktor nadzoruje jednego ucznia w nie więcej niż jednym projekcie. Uczeń uczestniczy w realizacji danego projektu pod nadzorem co najwyżej jednego instruktora.
Uczeń (Emp_no, …)
Projekt (Proj_no, …)
Instruktor (Inst_no, …)
Nadzoruje (Emp_no, Proj_no, Inst_no, …)
lub Nadzoruje (Emp_no, Proj_no, Inst_no, …)
Wartości puste są zabronione dla atrybutów Emp_no, Proj_no i Inst_no relacji Nadzoruje.
Identyfikator ucznia musi wejść do klucza.
d) Hierarchie generalizacji i podzbiorów
Każdą encję transformujemy do relacji encji. W encji generalizacji są wszystkie atrybuty wspólne. W encjach będących specjalizacjami pojawiają się tylko atrybuty wspólne. Klucz jest nadawany na poziomie generalizacji i jest dziedziczony przez wszystkie encje specjalizacji (tu: Emp_no). W encji generalizacji pojawia się także atrybuty, który mówi względem czego następuje specjalizacja (tu: Job).
Pracownik (Emp_no, Job, atr. wspólne)
Inżynier (Emp_no, atr. specyficzne)
Sekretarka (Emp_no, atr. specyficzne)
Technik (Emp_no, atr. specyficzne)
Pracownik (Emp_no, atr. wspólne)
Student_zaoczny (Emp_no, atr. specyficzne)
Dział_związkowy(Emp_no, atr. specyficzne)
e) Związki między encjami
Encje mogą być w ogólności powiązane wieloma zależnościami. W takim przypadku stosujemy następujące reguły transformacji:
Dany jest zbiór atrybutów U = {A1, A2, …, An} oraz informacja o zależnościach między tymi atrybutami (FD, MVD).
Projektowanie logicznej struktury relacyjnej bazy danych polega na zdefiniowaniu schematu logicznego bazy danych B, to jest, na zdefiniowaniu schematów relacji tworzących tę bazę danych w taki sposób, aby schematy te posiadały pożądane własności ułatwiające eksploatację bazy danych.
Część osób zaczyna od razu od zaprojektowania schematu bazy danych, co jest podejściem niepoprawnym. Zamiast przechowywania danych baza musi zarządzać danymi i wykonywać szereg czynności. Schematem implementacyjnym jest schemat relacyjny, czyli tablice dwuwymiarowe.
Z każdą encją są związane atrybuty. Istnieją dwie grupy atrybutów:
Weźmy przykładową encję:
Dostawca
Nazwisko |
Adres |
Towar |
Cena |
Nowak Nowak Nowak … Kucia Kucia |
Czajcza 5 Czajcza 5 Czajcza 5 … Krucza 10 Krucza 10 |
Deska Śrubka_1 Śrubka_2 … Deska Śrubka_1 |
1500 100 150 … 2000 110 |
Podczas implementowania zawsze pojawia się problem: jakie atrybuty mają tworzyć klucz? Np. atrybuty Nazwisko lub Adres nie mogą być kluczami, ale zbiór Nazwisko-Adres-Towar już jest kluczem.
System pilnuje, by nie można było wpisać do klucza wartości pustej oraz by był on unikalny (wartość pusta zmienia logikę przetwarzania).
Powyższa relacja jest zła, gdyż ma kilka cech, które są wadami z punktu widzenia efektywności przetwarzania.
Problem spójności danych - należy tak modyfikować zawartość bazy danych, aby odpowiedź nie zależała od formy pytania.
Cechy relacji Dostawca:
Powyższe niepożądane cechy znikną, gdy relację Dostawca zdekomponujemy na dwie relacje:
Adres_dostawcy Dostawy
Nazwisko |
Adres |
|
Nazwisko |
Towar |
Cena |
Nowak
… Kucia
|
Czajcza 5
… Krucza 10
|
|
Nowak Nowak Nowak … Kucia Kucia |
Deska Śrubka_1 Śrubka_2 … Deska Śrubka_1 |
1500 100 150 … 2000 110 |
Zapytanie:
Podaj adresy dostawców dostarczających towarów: „deska”, „śrubka_1”, … .
Gdy połączymy powyższe relacje (atrybut połączeniowy: Nazwisko), to otrzymamy wyjściową relację Dostawcy.
Jednak koszt takiej dekompozycji jest duży. Zapytanie do jednej relacji jest tańsze niż zapytanie z wykorzystaniem połączenia dwóch relacji, gdyż to ostatnie wymaga więcej operacji odczytu danych z dysku.
Weźmy przykładową encję:
Pożyczki
Oddział |
Nr_konta |
Kwota |
Nazwisko |
III PKO III PKO V NBP V NBP I PKO BGŻ BGŻ |
17 23 5 10 77 17 21 |
1 1.5 3 1.5 3 1 1.3 |
Nowak Kowalski Zimoch Kusiak Puc Walusiak Mijal |
Z niejasnych powodów zdekomponowaliśmy ją na dwie relacje:
Konta_pożyczkowe Pożyczkobiorcy
Oddział |
Nr_konta |
Kwota |
|
Kwota |
Nazwisko |
III PKO III PKO V NBP V NBP I PKO BGŻ BGŻ |
17 23 5 10 77 17 21 |
1 1.5 3 1.5 3 1 1.3 |
|
1 1.5 3 1.5 3 1 1.3 |
Nowak Kowalski Zimoch Kusiak Puc Walusiak Mijal |
Przeprowadzona przez nas dekompozycja jest niepoprawna, gdyż nie można poprawnie odtworzyć relacji początkowej.
Poniższa relacja stanowi próbę odtworzenia relacji początkowej: Konta_pożyczkowe
Pożyczkobiorcy (wg. atrybutu połączeniowego Kwota).
Pożyczki
Oddział |
Nr_konta |
Kwota |
Nazwisko |
III PKO III PKO III PKO III PKO V NBP V NBP V NBP V NBP I PKO V NBP BGŻ BGŻ BGŻ |
17 17 23 23 5 5 10 10 77 77 17 17 21 |
1 1 1.5 1.5 3 3 1.5 1.5 3 3 1 1 1.3 |
Nowak Walusiak Kowalski Kusiak Zimoch Puc Kusiak Kowalski Puc Zimoch Walusiak Nowak Mijal |
Powyższa relacja zawiera wiele nowych krotek, które nie istniały w relacji początkowej. System nie wie, które krotki są poprawne, a które nie. Stąd całą tą relację musimy uznać za niepoprawną.
Widać więc, że można mieć do czynienia z dwoma rodzajami dekompozycji:
Zgodnie z ideą normalizacji nie można definiować relacji nieprawdziwych.
Przyjęty model jest ubogi i nie można wyrazić w nim wszystkich zależności występujących między atrybutami.
Identyfikatory jednoznacznie identyfikują encję. Deskryptory nie identyfikują, ale zależą od identyfikatorów.
* * *
Założenia:
Niech schemat bazy danych posiada n atrybutów A1, A2, …, An. Atrybuty te tworzą tzw. uniwersalny schemat relacji R = A1, A2, …, An.
Zależność funkcyjna (FD):
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].
Zależność funkcyjna określa zależność pomiędzy atrybutami. Jest to własność semantyczna, która musi być spełniona dla dowolnych wartości krotek relacji. 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 relacji.
Zależności funkcyjne w relacji Dostawca:
t1[X]= t2[X] i X→Y, to zachodzi zawsze t1[Y]= t2[Y]
Cechy charakterystyczne zależności funkcyjnej:
Nadkluczem (superkey) schematu relacji R = {A1, A2, …, An} nazywamy zbiór atrybutów S R, który jednoznacznie identyfikuje wszystkie krotki relacji r o schemacie R. Innymi słowy, w żadnej relacji r o schemacie R nie istnieją dwie krotki t1, t2 takie, że t1[S]= t2[S].
Kluczem (key) K schematu relacji R nazywamy minimalny nadklucz, tzn. taki, że nie istnieje K'K będące nadkluczem schematu R. Innym słowy, kluczem nazywamy taki zbiór identyfikujący relacji, którego żaden podzbiór nie jest zbiorem identyfikującym relacji.
Wyróżniamy klucze:
W ogólności w relacji można wyróżnić wiele kluczy, które nazywamy kluczami potencjalnymi (candidate keys). Wybrany klucz spośród kluczy potencjalnych nazywamy kluczem podstawowym (primary key), a pozostałe kluczami drugorzędnymi (secondary key).
Taki podział kluczy prowadzi do podziału atrybutów:
a) Wprowadzenie
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.
Jednak nie każda dekompozycja jest poprawna. Poniżej zbiór reguł Armstronga - reguły wyprowadzania pozwalające z danego zbioru zależności funkcyjnych FD wyprowadzić logicznie wszystkie możliwe zależności funkcyjne FD+ (plusik oznacza domknięcie zbioru).
Proces normalizacji musi posiadać trzy dodatkowe własności:
Ostatnia własność mówi o zależnościach, które stanowią minimalne pokrycie, tzn. takich, z których można wyprowadzić wszystkie pozostałe.
b) Pierwsza postać normalna (1NF)
Pierwsza postać normalna
Schemat relacji R znajduje się w pierwszej postaci normalnej (1NF), jeżeli wartości atrybutów są atomowe (niepodzielne).
Płeć
Imię |
Płeć |
Piotr, Jan, Tomasz Janina, Anna, Maria |
męska żeńska |
Powyższa relacja jest nieznormalizowana jeżeli chcemy się dostać do każdej osoby, ale jest znormalizowana, jeżeli chcemy tylko rozróżniać łańcuchy „Piotr, Jan, Tomasz” itp. Zależy to więc od implementacji.
Zakładamy jednak, że chcemy przechowywać dane o pojedynczych osobach. W takim przypadku najprostszym rozwiązaniem jest utworzenie jednej krotki dla jednej osoby.
Relacja Płeć w 1NF
Imię |
Płeć |
Piotr Jan Tomasz Janina Anna Maria |
męska męska męska żeńska żeńska żeńska |
Pierwsza postać normalna zabrania definiowania złożonych atrybutów, które są wielowartościowe. Relacje, które dopuszczają definiowanie takich złożonych atrybutów nazywamy relacjami zagnieżdżonymi (nested relations). W relacjach zagnieżdżonych każda krotka może zawierać inną relację.
W przypadku relacji zagnieżdżonych podstawowym sposobem normalizacji (lepszym od rozpisywania wierszy) jest dekompozycja na dwie relacje:
Faktem jest jednak to, że gdyby poprawnie przeanalizować schemat pojęciowy, to po przetransformowaniu do relacji nie trzeba by było normalizować! Atrybut złożony modelujemy przecież jako encję z kluczem obcym.
W poniższym przykładzie relacja EMP_PROJ posiada relację zagnieżdżoną PROJS. Dekomponujemy ją więc na dwie relacje: EMP_PROJ1 (zewnętrzną) i EMP_PROJ2 (wewnętrzną).
EMP_PROJ (SSN, ENAME, {PROJS (PNUMBER, HOURS)})
EMP_PROJ (SSN, ENAME, {PNUMBER, HOURS})
EMP_PROJ
|
|
PROJS |
|
SSN |
ENAME |
PNUMBER |
HOURS |
12345678 |
Smith |
1 2 |
32.5 7.5 |
66543723 |
Narayan |
3 |
40.5 |
43432266 |
English |
1 2 |
20.0 20.0 |
33333333 |
Wong |
2 3 10 20 |
10.0 10.0 10.0 10.0 |
EMP_PROJ1 EMP_PROJ2
SSN |
ENAME |
|
SSN |
PNUMBER |
HOURS |
Istnienie pierwszej postaci normalnej wynika głównie z ograniczeń produktów komercyjnych nie dopuszczających atrybutów wielowartościowych.
c) Druga postać normalna (2NF)
Pełna zależność funkcyjna
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.
Druga postać normalna
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.
II wersja 2NF (mniej ważna)
Dana relacja r o schemacie R jest w drugiej postaci normalnej (2NF), jeżeli każdy atrybut wtórny tej relacji jest w pełni funkcyjnie zależny od klucza podstawowego relacji r.
Poniżej przedstawiono schemat dekompozycji do 2NF
Jeżeli mamy dwie relacje postaci:
Ri = (K, A1, A2, …, Ak)
Rj = (K, B1, B2, …, Bk)
gdzie K jest identycznym kluczem, a A i B to pozostałe argumenty, to tworzymy nową relację w operacji połączenia (merge):
R = (K, A1, A2, …, Ak, B1, B2, …, Bk)
Przykład:
Mamy następującą relację (strzałkami zaznaczono zależności funkcyjne):
EMP_PROJ
SSN |
PNUMBER |
HOURS |
ENAME |
PNAME |
LOCATION |
fd1
fd2
fd3
Jakie mamy tu problemy?
Te wszystkie problemy wynikają z tego, że relacja EMP_PROJ jest nieznormalizowana.
Relacja nie znajduje się w 2NF, gdyż np. Ename jest tylko częściowo, a nie w pełni, zależny od klucza, bo istnieje podzbiór klucza (jest nim SSN), od którego Ename też jest zależny funkcyjnie.
Jeżeli X→Y, to możemy do X dokleić jakiś atrybut A i zależność pozostanie AX→Y, gdyż A nie ma znaczenia.
Rozbiliśmy relację EMP_PROJ na trzy relacje - wszystkie wymienione wyżej wady zniknęły.
EP1
SSN |
PNUMBER |
HOURS |
EP2
SSN |
ENAME |
EP3
PNUMBER |
PNAME |
LOCATION |
Znaczenie relacji:
EP1 - Uczestniczy
EP2 - Pracownik
EP3 - Projekt
d) Trzecia postać normalna (3NF)
Weźmy przykładową encję:
Pracownicy_PP
Nazwisko |
Instytut |
Wydział |
Brzeziński Morzy Koszlajda Królikowski … Babij Kordus Sroczan |
I. Informatyki I. Informatyki I. Informatyki I. Informatyki … ElektroEnerg. ElektroEnerg. ElektroEnerg. |
Elektryczny Elektryczny Elektryczny Elektryczny … Elektryczny Elektryczny Elektryczny |
Mimo, że relacja ta jest w 2NF mamy tu redundacje i anomalie przy modyfikacji.
Klucz: Nazwisko
Zależności funkcyjne:
Nazwisko → Instytut
Nazwisko → Wydział
Instytut → Wydział
Przechodnia zależność funkcyjna
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.
Zależność funkcyjna X→Y jest zależnością przechodnią jeżeli istnieje podzbiór atrybutów Z taki, że zachodzi X→Z, Z→Y i nie zachodzi Z→X lub Y→Z.
Trzecia postać normalna
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:
a) X jest nadkluczem schematu R, lub
b) A jest atrybutem podstawowym schematu R.
II wersja 3NF
Dana relacja r o schemacie R jest w trzeciej postaci normalnej (3NF), jeżeli jest w drugiej postaci normalnej i żaden atrybut wtórny nie jest przechodnio zależny od podstawowego klucza schematu R.
Wynika stąd, że relacja Pracownicy_PP nie jest w 3NF, bo posiada ona zależność funkcyjną Instytut → Wydział.
Dekomponujemy więc tę relację na dwie mniejsze, co likwiduje nasz e problemy.
Pracownicy_PP_1 Pracownicy_PP_2
Nazwisko |
Instytut |
|
Instytut |
Wydział |
Brzeziński Morzy Koszlajda |
I. Informatyki I. Informatyki I. Informatyki |
|
I. Informatyki … ElektroEnerg. |
Elektryczny … Elektryczny |
Królikowski … Babij Kordus Sroczan |
I. Informatyki … ElektroEnerg. ElektroEnerg. ElektroEnerg |
|
|
|
Przykład:
Mamy relację Grunty. Atrybut Id_Własności jest unikalny na terenie kraju, a Id_gruntu jest unikalny na terenie województwa. Wynika stąd, że para Id_Własności, Id_gruntu jest kluczem alternatywnym.
Grunty
Id_Własności |
Województwo |
Id_gruntu |
Obszar |
Cena |
Stopa_podatku |
fd1
fd2
fd3
fd4
Sprowadzamy tę relację do 3NF (dekomponujemy do trzech relacji: Grunty_1A, Grunty_1B i Grunty_2)
Grunty_1
Id_Własności |
Województwo |
Id_gruntu |
Obszar |
Cena |
Grunty_2
Województwo |
Stopa_podatku |
Grunty_1A
Id_Własności |
Województwo |
Id_gruntu |
Obszar |
Grunty_1B
Obszar |
Cena |
e) Postać normalna Boyce-Codd'a (BCNF)
Postać normalna Boyce-Codd'a stanowi warunek dostateczny 3NF, ale nie konieczny.
Do relacji Grunty z poprzedniego przykładu dodajemy nową zależność funkcyjną Obszar Województwo. Część specjalistów twierdzi, że taka zależność nie wpłynie na dekompozycję, a część twierdzi, że wprowadzi ona dużą redundację. Ci ostatni zaproponowali postać BCNF - jest to 3NF z usuniętym drugim warunkiem.
Grunty
Id_Własności |
Województwo |
Id_gruntu |
Obszar |
Cena |
Stopa_podatku |
Załóżmy, że w relacji Grunty mamy tylko dwa województwa. Co więcej, załóżmy, że działki w pierwszym województwie mają rozmiar 0.5, 0.6 i 0.7 h; natomiast działki w drugim województwie mają rozmiar 1, 1.2, 1.4 h. Ta informacja może być powielona w tysiącach krotek relacji Grunty oraz, po dekompozycji, w relacji Grunty_1A.
Relacja Grunty jest nadal w trzeciej postaci normalnej (Województwo jest atrybutem podstawowym), ale nie jest w BCNF.
Grunty_1A
Id_Własności |
Województwo |
Id_gruntu |
Obszar |
Relację powyższą dekomponujemy dalej. Czasami jednak dekompozycja do BCNF gubi pewne zależności funkcyjne.
Grunty_1A1
Id_Własności |
Obszar |
Id_gruntu |
Grunty_1A2
Obszar |
Województwo |
Postać normalna Boyce-Codd'a
Schemat relacji R jest w postaci BCNF, jeżeli dla każdej zależności funkcyjnej X→A w R, X jest nadkluczem schematu R.
Loty
Lot |
Dzień_tygodnia |
Typ_samolotu |
106 106 106 106 206 206 206 206 |
poniedziałek czwartek poniedziałek czwartek środa piątek środa piątek |
134 154 154 134 747 767 767 747 |
Języki
Nazwisko |
Język_obcy |
Język_programowania |
Nowak Nowak Nowak Nowak Nowak Nowak |
angielski włoski angielski włoski czeski czeski |
Basic Fortran Fortran Basic Basic Fortran |
Powyższe relacje to iloczyny kartezjańskie atrybutów. Niezmiernie komplikuje to aplikację przetwarzania danych.
Modyfikacja:
Lot 106 będzie dodatkowo odbywał się w środę i na tę linię wprowadzamy, dodatkowo, nowy typ samolotu - 104.
Główną wadą jest to, że trzeba zajrzeć do bazy danych przed wykonaniem modyfikacji. Zajrzeć trzeba po to, by dowiedzieć się np. jakiego typu samoloty latają na locie 106.
Lot
Lot |
Dzień_tygodnia |
Typ_samolotu |
106 106 106 106 106 106 106 106 106 |
poniedziałek czwartek poniedziałek czwartek poniedziałek czwartek środa środa środa |
134 154 154 134 104 104 134 154 104 |
Kłopoty znikną, gdy powyższe relacje zdekomponujemy na dwie mniejsze:
Lot_1 Lot_2
Lot |
Dzień_tygodnia |
|
Lot |
Typ_samolotu |
106 106 206 206 … 106 |
poniedziałek czwartek środa piątek … środa |
|
106 106 206 206 … 106 |
134 154 747 767 … 104 |
Język_1 Język _2
Nazwisko |
Język_obcy |
|
Nazwisko |
Język_programowania |
Nowak Nowak |
angielski włoski |
|
Nowak Nowak |
Basic Fortran |
Nowak |
czeski |
|
|
|
Zależności wielowartościowe są konsekwencją wymagań pierwszej postaci normalnej, która nie dopuszcza, aby krotki zawierały atrybuty wielowartościowe.
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.
Lot →→ Dzień_tygodnia
Lot →→ Typ_samolotu
Nazwisko →→ Język_obcy
Nazwisko →→ Język_programowania
Wystąpienie zależności wielowartościowej X→→Y w relacji o schemacie R = XYZ wyraża dwa fakty:
Lot_3
Lot |
Dzień_tygodnia |
Typ_samolotu |
106 106 106 206 206 |
poniedziałek czwartek czwartek środa piątek |
134 154 134 747 767 |
Relacja Lot_3 jest nierozkładalna.
Jest tu zależność między atrybutami Lot a parą Dzień_tygodnia, Typ_samolotu.
Niech R oznacza schemat relacji, natomiast X, Y są rozłącznymi zbiorami atrybutów schematu R i Z = R - (XY).
Relacja r(R) spełnia zależność wielowartościową X→→Y, jeżeli dla dwóch dowolnych krotek t1, t2 z r(R) takich, że t1[X]=t2[X], zawsze istnieją w r(R) krotki t3, t4 takie, że spełnione są następujące warunki:
Z symetrii powyższej definicji wynika, że jeżeli w relacji r(R) zachodzi X→→Y, to zachodzi również X→→[R-X-Y]. Ponieważ R-X-Y = Z, to powyższy fakt zapisujemy czasami w postaci: X→→Y | Z.
Przykładowo mając dwie krotki:
106 poniedziałek 134
106 czwartek 154
to istniałaby zależność wielowartościowa między atrybutami Dzień_tygodnia a Typ_samolotu, gdyby istniały także krotki:
106 poniedziałek 154
106 czwartek 134
a) Trywialna zależność wielowartościowa
Zależność wielowartościową X→→Y w relacji r(R) nazywamy zależnością trywialną, jeżeli
Zależność nazywamy trywialną, gdyż jest ona spełniona dla dowolnej instancji r schematu R - nie specyfikuje ona zatem żadnego ograniczenia w stosunku do schematu R.
b) Czwarta postać normalna
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 R.
Inaczej mówiąc relacja jest w 4NF, gdy zawiera tylko jedną zależność wielowartościową w dodatku trywialną lub lewa strona zależności jest nadkluczem.
Dekompozycja relacji na podrelacje bez utraty informacji
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 co najmniej jedna z poniższych zależności funkcyjnych:
należy do F+.
Zapis R1 R2 → R1 oznacza, że iloczyn atrybutów schematów R1 i R2 relacji wyznacza relację R1. Atrybut połączeniowy jest kluczem schematu R1 lub R2.
Dana jest relacja r o schemacie 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 co najmniej jedna z poniższych zależności wielowartościowych jest spełniona:
Atrybut połączeniowy relacji R1 i R2 to R1 R2. Wyznacza on różnice R1 R2 i R2 R1.
Przykład:
Mamy relację R = {N, Jo, Jp}, gdzie N →→ Jo i N →→ Jp. Dekomponujemy R na dwie podrelacje: R1 = {N, Jo} i R2 = {N, Jp}
Mamy teraz, że:
c) Zależność połączeniowa i piąta postać normalna
Agenci
Agent |
Firma |
Produkt |
Kulczyk Kulczyk Kulczyk Kulczyk Nowak Nowak Misiek |
Volkswagen Volkswagen Audi Audi Ford Ford Nissan |
samochody ciężarówki samochody ciężarówki samochody ciężarówki samochody |
R1 R2 R3
Agent |
Firma |
|
Agent |
Produkt |
|
Firma |
Produkt |
Kulczyk Kulczyk Nowak Misiek |
Volkswagen Audi Ford Nissan |
|
Kulczyk Kulczyk Nowak Nowak |
samochody ciężarówki samochody ciężarówki |
|
Volkswagen Volkswagen Audi Audi |
samochody ciężarówki samochody ciężarówki |
|
|
|
Misiek |
samochody |
|
Ford |
samochody |
|
|
|
|
|
|
Ford Nissan Nissan |
ciężarówki samochody ciężarówki |
Dopiero dekompozycja umożliwiła na wprowadzenie danych o tym, że Nissan produkuje ciężarówki. Danych tych nie można było wprowadzić do relacji Agenci, gdyż nikt nie zajmował się sprzedażą ciężarówek Nissana.
Rodzaje relacji:
Tworzenie perspektywy z trzech relacji bazowych:
create view Agencji (agent, firma, produkt)
as select agent, firma, produkt
from R1, R2, R3
where R2.agent = R2.agent
and R1.firma = R3.firma
and R2.produkt = R3.produkt
Zapytania:
Schematy baz danych powinny mieć charakter acykliczny.
Zależność połączeniowa
Niech R = {R1, R2, …, Rp} oznacza zbiór schematów relacji, zdefiniowany nad zbiorem atrybutów U = {A1, A2, …, An}, takich, że R1 R2 … Rp = U. Mówimy, że relacja r(U) spełnia zależność połączeniową, oznaczaną przez JD[R1, R2, …, Rp], jeżeli można ją zdekomponować bez utraty informacji na podrelacje r1(R1), r2(R2), …, rp(Rp).
Zachodzi wówczas następujący warunek:
r(U) = r1(R1)
r2(R2)
…
rp(Rp)
Zauważmy, że zależność wielowartościowa jest szczególnym przypadkiem zależności połączeniowej, dla której n = 2.
Zależność połączeniowa JD[R1, R2, …, Rp] jest trywialna, jeżeli jeden ze schematów Ri, i = 1, 2, …, p jest równy R.
Istnieje dekompozycja relacji na wiele schematów tak, że po połączeniu otrzymujemy relację początkową.
Piąta postać normalna
Schemat relacji R jest w piątej postaci normalnej (5NF lub PJNF), jeżeli dla każdej zależności połączeniowej JD w schemacie R zachodzi:
Innymi słowy 5NF to dekompozycja schematu relacji na większą liczbę schematów relacji. Czasami nie jest możliwa dekompozycja na 2 podschematy bez utraty informacji a jednocześnie można utworzyć więcej niż 2 podschematy bez utraty informacji.
a) Wprowadzenie
Jednym z podstawowych elementów, które mają wpływ na czas realizacji transakcji, mają struktury fizyczne plików. Np. system Oracle nie wyprowadza na zewnątrz struktury fizycznej plików natomiast system Ingres to umożliwia.
Media fizyczne tworzą hierarchię pamięci składającą się z dwóch kategorii:
Hierarchia pamięci:
Dane w bazie danych są pamiętane w długim odcinku czasu w pamięci zewnętrznej z trzech powodów:
Dane bazy danych są pamiętane w pamięci zewnętrznej. W celu przetwarzania, potrzebne dane są ściągane do pamięci operacyjnej i po przetworzeniu są z powrotem zrzucane na dysk. Dane w pamięci operacyjnej są buforowane.
b) Buforowanie bloków dyskowych
Pojawia się jeden problem, którym jest zupełnie inny sposób przetwarzania danych w pamięci operacyjnej a pamięci dyskowej. Jednym z elementów, który wpływa na pracę bazy danych jest styk między pamięcią operacyjną a zewnętrzną pamięcią dyskową. Styk ten to tzw. przestrzeń buforów, gdyż znajdują się w niej bufory usprawniające przesyłanie danych między obydwoma rodzajami pamięci (głównie chodzi o złagodzenie różnicy czasowej). Dobrze by było, gdyby strony, ramki i bloki dyskowe miały takie same rozmiary. Każda strona znajdująca się w buforze posiada licznik fix. Jeżeli jakiś proces zaczyna korzystać ze strony, to licznik ten jest zwiększany o 1. Gdy proces przestaje korzystać ze strony, to licznik ten jest dekrementowany (unfix). Jeżeli w buforze brakuje miejsca na sprowadzenie potrzebnej strony, wyrzuca się jakąś stronę, która posiada wyzerowany licznik fix. Dzięki buforom, w pamięci znajduje się tylko jedna kopia danej strony, która jest współdzielona między korzystającymi z niej procesami. Podstawowym problemem jest tutaj migotanie stron. Jeżeli proces potrzebuje dostać się do jakiejś strony, to najpierw jest sprawdzane, czy nie ma jej w buforze (buffermanager). Jeżeli jej tam nie ma, to brakującą stronę trzeba sprowadzić z dysku (filemanager). Proces otrzymuje adres strony w buforze. Najpowszechniejszą metodą zarządzania buforami jest LRU (least recently used).
c) Alokacja plików na dysku
Relacja to plik dyskowy składający się z pewnej liczby bloków dyskowych. Bloki te mogą być rozrzucone po całym dysku. Takie rozproszenie jest niekorzystne, gdyż wydłuża czas dostępu do danych.
Czas dostępu do danych dyskowych składa się z:
Dążymy do tego, by pliki danej relacji zajmowały spójne obszary na dysku. Daje to przyspieszenie dostępu ok.100-1000 razy w stosunku do dysku zdefragmentowanego. Przydzielanie spójnych obszarów nie jest jednak takie proste.
Przykład:
seek time = 10ms
1/2 rotational time = 5ms
1000 bloków po 1KB
transfer time = 10MB/s
gdy układ bloków jest sekwencyjny, to czas dostępu = 10 + 5 + 100 = 115ms
gdy układ bloków jest rozproszony, to czas dostępu = 1000 * (10 + 5 + 0.1) = ok. 15s
Zakładamy, że mamy rekordy o stałej długości.
d) Współczynnik blokowania
rozmiar bloku B; rozmiar rekordu R,
współczynnik blokowania: bfr = (B/R)
wolny obszar B-(bfr*R) rekordów.
Typy organizacji:
e) Alokacja bloków pliku na dysku
Rodzaje alokacji:
W praktyce najczęściej stosowana jest alokacja segmentowa, tzn. początkowo przydzielamy plikowi 32KB, a następnie, w miarę potrzeb, przydzielamy po 4KB.
f) Deskryptory plików
Operacje typu record_at_a_time (przetwarzanie pojedynczych rekordów):
Operacje typu set_at_a_time (przetwarzanie grup rekordów):
Nas oczywiście interesuje efektywność struktur fizycznych z punktu widzenia efektywności operacji na plikach.
Optymalizacja struktur fizycznych dotyczy:
Podstawową organizacją nieuporządkowaną jest stóg (heap).
Plik nieuporządkowany jest podstawową strukturą fizyczną plików.
Operacje:
Dodatkowa operacja:
Oprócz wstawiania rekordów wszystkie powyższe operacje wymagają liniowego przeszukiwania bloków.
Problem sortowania pliku - tzw. sortowanie zewnętrzne (jest to operacja bardzo złożona).
Rekordy pliku są porządkowane według pola porządkującego (ordering field). Prowadzi to do organizacji typu plików uporządkowanych (ordered) lub sekwencyjnych (sequencial).
Zalety:
Algorytm: Przeszukiwanie binarne
Plik posiada b bloków: 1, 2, …, b. Rekordy są uporządkowane rosnąco. Szukamy rekordu o wartości K. Przeszukiwanie binarne realizuje średnio log2(b) dostępów do bloków.
l 1; u b;
while ( u > l ) do
begin
i ( l + u ) + div 2;
read block i of the file into the buffer;
if K < ordering field value of the first record in the block
then u ( i -1 )
else if K > ordering field value of the first record in the block
then l ( i + 1 )
else if record with the ordering field value = K is in the buffer
then goto found
else goto notfound
end;
goto notfound
Uporządkowanie pliku nic nie daje, gdy wyszukiwanie jest realizowane według wartości pola nieporządkującego.
Problemy:
* * *
CREATE TABLESPACE nazwa
DATAFILE filename1 [SIZE n [k | m]]
(, filename2 …)
[DEFAULT STORAGE [INITIAL n][NEXT n][MAXEXTENS n][MINEXTENS n][POINCREASE n]]
Relacja jest przechowywana w jednym lub kilku plikach systemu operacyjnego. Tablespace to przestrzeń dyskowa, zbiór plików, które SZBD ma do dyspozycji.
DEFAULT STORAGE -- przestrzeń przyznawana domyślnie przez administratora
INITIAL - użytkownik sam określa ile paczek pamięci zostaje przydzielonych początkowa
NEXT - rozmiar dodawanych porcji
MAXEXTENS, MINEXTENS -- maks. i min. liczba paczek
POINCREASE -- o ile ma zostać powiększona pamięć (procentowo)
Mówiąc o optymalizacji struktur fizycznych ma się na myśli przede wszystkim metody dostępu do danych.
Istnieją trzy grupy metod dostępu:
Jest to próba takiego przechowywania danych, by sama struktura ułatwiała swobodny dostęp do plików. Tablica haszowa umożliwia zwiększenie efektywności wykonywania niektórych operacji na relacjach. Tablica taka posiada M szczelin, w których przechowywanych jest R adresów bloków dyskowych zawierających rekordy pliku relacji. Adres bloku dyskowego otrzymuje się w oparciu o wartość pola haszowego
Plik wykorzystujący technikę haszowania nosi nazwę pliku haszowego lub bezpośredniego.
Pole haszowe - klucz haszowy.
Idea polega na zdefiniowaniu funkcji haszowej (hash function), która zastosowana do pola haszowego zwraca adres bloku dyskowego, w którym znajduje się poszukiwany rekord.
a) Haszowanie wewnętrzne
|
NAME |
SSN |
JOB |
SALARY |
0 |
|
|
|
|
1 |
|
|
|
|
2 |
|
|
|
|
|
|
. . . |
|
|
M-2 |
|
|
|
|
M-1 |
|
|
|
|
Danych jest M szczelin (slots), których adresy odpowiadają indeksom tablicy haszowej.
Funkcja haszowa:
h (hash_field_value) (0, M-1)
Najczęściej spotykaną funkcją haszową jest funkcja h(K) = K mod M
Argumentami funkcji haszowej muszą być liczby.
Pola nienumeryczne są transferowane do liczb całkowitych przed zastosowaniem funkcji haszowej.
Operacja ta nosi nazwę foldingu.
Algorytm transformacji
temp 1;
for i = 1 to 20 do
temp temp * code(K[i]);
hash_address temp mod M;
Funkcja dostępu do pliku haszowego może być zadeklarowana następująco:
PAGEID hash(FILEID fileid, char *keyvalue, int keylength)
Zwraca ona najczęściej PAGEID:
Podstawowe procedury wyróżniają dwa kroki:
Dwa kroki procedury haszowania: folding i hashing. Wartości kluczy zwykle pochodzą z rozległej dziedziny, w której wartości aktualne nie są rozproszone równomiernie. Pierwszym krokiem jest konwersja wartości kluczy w ich reprezentację numeryczną (folding). Następnie te wartości numeryczne są transformowane w poprawne adresy z dostępnej przestrzeni adresowej. Przetransformowane klucze muszą tworzyć adresy równomiernie rozkładające się w dostępnej przestrzeni.
Zasadniczym problemem w przypadku organizacji haszowej jest problem kolizji. Żadna funkcja haszowa nie gwarantuje bowiem, że różnym wartościom pola haszowego będą odpowiadały różne adresy szczelin.
Wynika to z tego, że zbiór możliwych wartości pola haszowego jest najczęściej znacznie większy od przestrzeni adresowej tablicy haszowej. Kolizja ma miejsce wtedy, gdy wartość funkcji haszowej dla danej wartości pola haszowego nowego rekordu odpowiada adresowi szczeliny, w której znajduje się już inny rekord. Proces znajdowania innej lokalizacji dla danego rekordu nosi nazwę rozwiązania kolizji.
Trzy podstawowe metody rozwiązania kolizji:
Adresowanie otwarte (open addressing)
„Gdy dana lokacja jest zajęta, to weź następną wolną lokację.”
Algorytm adresowania otwartego
i hash_address;
if location i is occupied then
begin
i ( i + 1 ) mod M;
while ( i hash_address) and location i is occupied
do i ( i + 1 ) mod M;
if ( i = hash_address)
then all position are full;
else new_hash_address i;
end;
Łańcuchowanie (chaining)
Całą tablicę haszową dzielimy na dwie części: przestrzeń adresową i przestrzeń przepełnienia. Każda lokacja posiada wskaźnik przepełnienia, który domyślnie wynosi -1. Gdy nastąpi kolizja, to wybieramy pierwszą wolną szczelinę z przestrzeni przepełnienia a adres tej szczeliny wstawiamy do pola wskaźnika szczeliny, gdzie nastąpiła kolizja.
Wielokrotne haszowanie
Wraz z kolejną kolizją bierzemy inną funkcję haszującą.
* * *
Każdy algorytm rozwiązania kolizji wymaga własnych algorytmów wstawiania, usuwania i wyszukiwania rekordów.
Cechą dobrej funkcji haszowej jest zapewnienie równomiernego rozkładu rekordów w obrębie przestrzeni adresowej tablicy haszowej.
Zalecany rozmiar tablicy haszowej: r / M (0.7 0.9)
r - liczba rekordów jakie musimy pamiętać
M - liczba szczelin w tablicy haszowej
Wady:
b) Haszowanie zewnętrzne
W haszowaniu zewnętrznym funkcja haszowa adresuje blok (bucket).
Dobra funkcja haszująca - kryteria oceny
Dobra funkcja haszująca to taka, która odwzorowuje wartości kluczy, rozłożone nierównomiernie w obrębie dużej dziedziny, w przestrzeń adresową krotek, o znacznie mniejszym rozmiarze (proporcjonalnym do liczby istniejących krotek), w taki sposób, że wynikowe adresy są równomiernie rozłożone w obrębie przestrzeni adresowej.
Podstawowe kategorie funkcji haszujących:
Problem: Jak dobrać wartość B.
Dane:
r - liczba krotek do zapamiętania;
bfr - liczba krotek w bloku.
B = (r/bfr)
Wady:
H(ki) = ki mod B = k0 mod (x*y) + (i*y) mod (x*y) = r0 + i mod x
Zalecana wartość B:
B = next_higher_prime r / (bfr*0.8)
Estymacja liczby kolizji
B = r / (bfr*ut)
Table: Average bucket utilization and resulting number of overflows in hash-based access method. If a tuple cannot be stored in the bucket whose address is computed by the hash function, additional accesses to overflow buckets are required. This table shows the average number of additional accesses per tuple if the hash file is accessed with randomly selected key values (uniform distribution). The average length of the overflow chain is displayed as a function of the page size and the page utilization. This table is based on computations is van der Pool [1973].
Page |
Maximum Number of Tuples Per Page (Bucket) |
||||||
utilization |
1 |
2 |
3 |
5 |
10 |
20 |
40 |
.50 |
0.500 |
0.177 |
0.087 |
0.031 |
0.005 |
0.000 |
0.000 |
.60 |
0.750 |
0.293 |
0.158 |
0.066 |
0.015 |
0.002 |
0.000 |
.70 |
1.167 |
0.494 |
0.286 |
0.136 |
0.042 |
0.010 |
0.001 |
.80 |
2.000 |
0.903 |
0.554 |
0.289 |
0.110 |
0.036 |
0.009 |
.85 |
2.832 |
1.316 |
0.827 |
0.449 |
0.185 |
0.069 |
0.022 |
.90 |
4.495 |
2.146 |
1.377 |
0.777 |
0.345 |
0.144 |
0.055 |
.92 |
5.740 |
2.768 |
1.792 |
1.024 |
0.467 |
0.203 |
0.083 |
.95 |
9.444 |
4.631 |
3.035 |
1.769 |
0.837 |
0.386 |
0.171 |
Haszowanie dla atrybutów nieunikalnych
(brak danych)
c) Inne techniki haszowania zewnętrznego
Haszowanie dynamiczne
Chcemy, by haszowanie było dynamicznie rozszerzalne wraz z liczbą bloków dyskowych pliku.
Przykład:
Pod uwagę bierzemy tylko ostatni bit.
h(Morzy) = 7 = 00000111
h(Jezierski) = 6 = 00000110
h(Brzeziński) = 5 = 00000101
teraz dochodzi nam Kowalski: h(Kowalski) = 11 = 00001011
Powinien trafić do bloku B, ale nie ma tam miejsca. Dokładamy więc blok C i redystrybuujemy zawartość bloku B, między bloki B i C. Lecz teraz, szukając bloku, musimy brać pod uwagę dwa ostatnie bity.
Liczba bloków jest zmienna. Na początku plik otrzymuje tylko jeden blok. Budowana jest następnie drzewiasta struktura katalogu (indeks) o dwóch typach wierzchołków:
Algorytm wyszukiwania dla haszowania dynamicznego
h hash value of record;
t root node of directory;
i 1;
while t is an internal node of the directory do
begin
if ith bit of h is a 0
then t left son of t;
else t right son of t;
i i + 1;
end;
search the bucket whose address is in node t;
Jeżeli funkcja haszowa rozprasza rekordy równomiernie, to indeks jest zbalansowany.
Haszowanie rozszerzalne
Haszowanie liniowe
W powyższych metodach wykorzystujemy dodatkową strukturę danych. W haszowaniu liniowym nie mamy żadnej dodatkowej struktury. Szczeliny w tablicy haszowej są ponumerowane od 0 do M-1. Funkcja haszowa to h()=KmodM. Gdy nastąpi przepełnienie to rozdzielamy bloki od 0 do i i dystrybuujemy je funkcją Kmod2M. Początkowo i=0. Po następnym przepełnieniu funkcja haszowa ma postać Kmod4M. Wadą takiego rozwiązania jest przypadkowość dzielenia.
Podstawową metodą przyspieszania dostępu do danych jest wykorzystanie indeksów.
a) Typy indeksów
Indeks jest zakładany na atrybucie relacji - atrybut ten nosi nazwę atrybutu indeksowego (indexing field).
Indeks jest to uporządkowany plik rekordów o stałej długości i o dwóch polach:
Typy indeksów:
b) Indeks podstawowy
Indeks jest zakładany na atrybucie, który jest unikalny i porządkujący. Plik z relacją jest uporządkowany wg. atrybutu porządkującego. Kolejne wskaźniki indeksów odpowiadają początkom kolejnych bloków.
Każdy rekord indeksu posiada wartość klucza podstawowego pierwszego rekordu w bloku oraz wskaźnik (adres) tego bloku. i-ty rekord indeksu ma postać <K(i), P(i)>.
K(i) - wartość klucza, P(i) - adres bloku
Charakterystyka:
Przykład:
Rozmiar pliku r = 30000 rekordów
Rozmiar bloku B = 1KB
Rozmiar rekordu R = 100B
Rekordy o stałej długości, organizacja niedzielona
bfr = (B/R) = 10 rekordów/blok
b = (r/bfr) = 3000 bloków
Przeszukiwanie binarne na pliku danych wymaga średnio (log2b) = (log23000) = 12 dostępów.
Załóżmy, że pole indeksowane ma długość V = 9B, wskaźnik do bloku P = 6B. Zakładamy indeks podstawowy. Rozmiar indeksu Ri = 15B.
bfri = (B/Ri) = (1024/15) = 68 rekordów/blok
ri = b = 3000 maksymalna liczba rekordów indeksu
bi = (ri/bfri) = (3000/68) = 45 bloków
Przeszukiwanie binarne na pliku indeksowym wymaga średnio (log2bi) = (log245) = 6 dostępów.
Podsumowując, liczba wymaganych dostępów do danych z użyciem indeksu podstawowego wymaga 7 dostępów.
Przykład ten ilustruje zysk osiągany przez wprowadzenie indeksów. Założenie pliku indeksowego wiąże się z większym zapotrzebowaniem na pamięć dyskową (45 bloków na plik indeksów). Zysk to ok. 40% na czasie kosztem ok. 1% pamięci.
Problem: Wstawianie i usuwanie rekordów z pliku danych.
Wstawienie nowego rekordu wymaga nie tylko przesunięcia rekordów w pliku danych ale również wymaga zmian w pliku indeksowym.
c) Indeks zgrupowany
Jeżeli rekordy pliku są uporządkowane fizycznie według wartości pola niekluczowego - to pole takie nazywamy polem grupującym (clustering field). Indeks zdefiniowany na takim polu nazywamy indeksem zgrupowanym (clustering index).
Wskaźnik wskazuje na pierwszy rekord bloku, w którym zaczyna pojawiać się dana wartość atrybutu.
Drobna modyfikacja. Indeks zgrupowany z oddzielnymi blokami dla każdej wartości pola grupującego. W blokach znajdują się dodatkowe wskaźniki do bloków następnych.
d) Indeks drugorzędny - wtórny
Indeks jest to uporządkowany plik rekordów o stałej długości i o dwóch polach. Pole, na którym jest zakładany indeks wtórny jest polem nieporządkującym i nazywamy je polem indeksowanym. Może istnieć wiele indeksów wtórnych dla pojedynczej relacji (pliku).
Indeks wtórny jest indeksem gęstym - jednemu rekordowi indeksu odpowiada jeden rekord pliku danych.
Indeks drugorzędny zakładany jest na atrybut nieporządkujący i nieunikalny.
Charakterystyka:
Przykład:
Rozmiar pliku r = 30000 rekordów
Rozmiar bloku B = 1KB
Rozmiar rekordu R = 100B
Rekordy o stałej długości, organizacja niedzielona
bfr = (B/R) = 10 rekordów/blok
b = (r/bfr) = 3000 bloków
Przeszukiwanie liniowe na pliku danych wymaga średnio b/2 = 1500 dostępów do bloków.
Przeszukiwanie binarne na pliku danych wymaga średnio (log2b) = (log23000) = 12 dostępów.
Załóżmy, że pole indeksowane ma długość V = 9B, wskaźnik do bloku P = 6B. Zakładamy indeks wtórny. Rozmiar indeksu Ri = 15B.
bfri = (B/Ri) = (1024/15) = 68 rekordów/blok
ri = 30000 maksymalna liczba rekordów indeksu
bi = (ri/bfri) = (30000/68) = 442 bloki
Przeszukiwanie binarne na pliku indeksowym wymaga średnio (log2bi) = (log2442) = 9 dostępów.
Podsumowując, liczba wymaganych dostępów do danych z użyciem indeksu wtórnego wymaga 10 dostępów (ten dodatkowy 1 dostęp to dostęp do pliku danych).
Indeks jest zakładany najczęściej na polu niekluczowym. Indeks taki jest implementowany w trojaki sposób:
Poniżej indeks wtórny założony na polu niekluczowym i zaimplementowany z wykorzystaniem poziomu pośredniego.
e) Indeks wielopoziomowy
Idea indeksu wielopoziomowego - zredukowanie czasu przeszukiwania indeksu. Przeszukiwanie binarne wymaga log2bi dostępów do bloków indeksu zajmującego bi bloków. Każdy krok przeszukiwania redukuje dwukrotnie rozmiar analizowanego indeksu. W przypadku indeksu wielopoziomowego, w każdym kroku redukujemy bfri-krotnie rozmiar analizowanego indeksu. Współczynnik bfri dla indeksu wielopoziomowego nosi nazwę fan-out indeksu (fo). Przeszukiwanie indeksu wielopoziomowego wymaga średnio (logfobi) dostępów do bloków pliku indeksowego.
Przykład:
Jeżeli I poziom indeksu posiada ri rekordów i bfri = fo, to poziom ten potrzebuje (ri/fo) bloków. Liczba ta jest jednocześnie liczbą r2 rekordów poziomu II. Najwyższy poziom indeksu t = (logfo(r1))
Poniżej dwupoziomowy indeks podstawowy.
Przykład:
Rozmiar pliku r = 30000 rekordów
Rozmiar bloku B = 1KB
Rozmiar rekordu R = 100B
Rekordy o stałej długości, organizacja niedzielona
bfr = (B/R) = 10 rekordów/blok
b = (r/bfr) = 3000 bloków
Przeszukiwanie liniowe na pliku danych wymaga średnio b/2 = 1500 dostępów do bloków.
Przeszukiwanie binarne na pliku danych wymaga średnio (log2b) = (log23000) = 12 dostępów.
Załóżmy, że pole indeksowane ma długość V = 9B, wskaźnik do bloku P = 6B. Rozmiar indeksu Ri = 15B. Zakładamy obecnie, że indeks podstawowy z pierwszego przykładu został przekształcony w indeks wielopoziomowy.
bfri = (B/Ri) = (1024/15) = 68 rekordów/blok
ri = 30000 maksymalna liczba rekordów indeksu
Liczba bloków indeksu na poziomie I wynosi b1 = (ri/bfri) = (30000/68) = 442 bloki
b2 = (b1/bfri) = (442/68) = 7 bloków
b3 = (b2/bfri) = (7/68) = 1 blok
t = 3
Przeszukiwanie pliku indeksowego wymaga 1 + t = 4 dostępów.
Mamy plik danych składający się z 3000 bloków. Zakładamy na pliku indeks złożony z 442 bloków (A). Budujemy indeks dla pliku indeksowego (B) - daje to 6 bloków. Rekordami pierwszego z nich byłyby pierwsze rekordy z pierwszych 68 bloków z owych początkowych 442. Na ten indeks nakładamy następny indeks (C). Otrzymaliśmy w ten sposób indeks 3-poziomowy. Przyspiesza on (tu ok. 1000-krotnie) czas dostępu do danych kosztem pamięci. Podstawowym problemem jest pielęgnacja pliku indeksowego, który musi pozostać uporządkowany.
Problem: problem wstawiania i usuwania rekordów pociąga za sobą konieczność modyfikacji indeksu (np. wstaw rekord K = 45). Problem ten rozwiązuje się przez pozostawienie w blokach pliku indeksowego wolnej przestrzeni. Indeks taki nazywamy dynamicznym indeksem wielopoziomowym. Najczęściej implementujemy taki indeks korzystając ze struktur typu B-drzewo lub B+-drzewo.
Chcielibyśmy, aby modyfikacje nie propagowały się na cały indeks (tzn. by wstawienie lub usunięcie rekordu nie zmuszało do modyfikacji całego indeksu) lecz dotyczyły ograniczonego obszaru. W systemie Oracle indeks dynamiczny posiada strukturę B+-drzewa.
f) S-drzewa i B-drzewa
S-drzewo
S-drzewem (search tree) rzędu p nazywamy takie drzewo, że każdy wierzchołek tego drzewa posiada co najwyżej p-1 wartości szukanych i p wskaźników do poddrzew w porządku
<P1, K1, P2, K2, …, Pq-1, Kq-1, Pq>
gdzie q p. Pi jest wskaźnikiem pustym lub wskaźnikiem do poddrzewa.
W każdej chwili S-drzewo spełnia dwa ograniczenia:
Ki-1 < x < Ki dla 1 < i < q
x < Ki dla i = 1
Ki-1 < x dla i = q
Struktura drzewa:
Struktura węzła S-drzewa:
Przykład S-drzewa rzędu p=3:
Z każdym S-drzewem są związane procedury wstawiania i usuwania wartości. Nie gwarantują one jednakże, że tworzone i modyfikowane dynamicznie S-drzewo jest zrównoważone. Innym problemem jest problem niewykorzystanej pamięci.
B-drzewo
B-drzewo jest S-drzewem z dodatkowymi ograniczeniami. Ograniczenia te mają na celu zagwarantowanie, że drzewo jest zrównoważone i że wolna przestrzeń (na skutek usuwania rekordów) nie będzie zbyt duża.
B-drzewo rzędu p definiujemy następująco:
<P1, <K1, Pr1>, P2, <K2, Pr2>, …, <Pq-1, Krq-1>, Pq>
gdzie q p. Pi jest wskaźnikiem do poddrzewa. Pri jest wskaźnikiem do bloku danych zawierających rekord o wartości klucza Ki.
Ki-1 < x < Ki dla 1 < i < q
x < Ki dla i = 1
Ki-1 < x dla i = q
Każdy wierzchołek to jeden rekord.
Pi - wskaźnik do poddrzewa, w którym przechowywane są wartości kluczy
Ki - wartość klucza
Pri - wskaźnik do bloku danych o kluczu Pi
Struktura węzła B-drzewa:
B-drzewo rzędu p=3. Sekwencja wprowadzanych wartości: 8, 5, 1, 7, 3, 12, 9, 6:
Przykład:
Jak obliczyć p?
Wartość klucza V = 9B; wskaźnik do bloku P = 6B. Rozmiar bloku B = 512B.
Każdy wierzchołek ma co najwyżej p wskaźników do poddrzew, p - 1 wskaźników do danych i p - 1 kluczy:
(p*6)+(( p-1)*(6+9)) 512
21 * p 512
p = 25
B+-drzewo
Zdecydowana większość implementacji indeksów wielopoziomowych stosuje wariant struktury B-drzewa o nazwie B+-drzewo.
Wynika z tego, że czas dostępu do dowolnego rekordu jest stały i zależy tylko od wysokości drzewa.
W B+-drzewie wskaźniki do bloków danych znajdują się wyłącznie w wierzchołkach liści drzewa. Oznacza to, że liście i wierzchołki wewnętrzne drzewa posiadają różną strukturę.
Struktura wierzchołków wewnętrznych B+-drzewa jest następująca:
<P1, K1, P2, K2, …, Pq-1, Kq-1, Pq>
gdzie q p. Pi jest wskaźnikiem do poddrzewa.
Ki-1 < x Ki dla 1 < i < q
x Ki dla i = 1
Ki-1 < x dla i = q
Struktura liści B+-drzewa jest następująca:
<<K1, Pr1>, <K2, Pr2>, …, <Pq-1, Krq-1>, Pnext>
gdzie q p. Pri jest wskaźnikiem do bloku danych, natomiast Pnext jest wskaźnikiem do następnego liścia B+-drzewa.
Przykład:
Jak obliczyć p?
Wartość klucza V = 9B; wskaźnik do bloku P = 6B. Rozmiar bloku B = 512B.
Każdy wierzchołek wewnętrzny posiada co najwyżej p wskaźników do poddrzew p - 1 kluczy:
(p*6)+(( p-1)*9) 512
15 * p 512
p = 34
Wewnętrzny węzeł B+-drzewa:
Liść B+-drzewa:
Przykładowa sekwencja wstawiania: 8, 5, 1, 7, 3, 12, 9, 6:
Przykładowa sekwencja usuwania: 5, 12, 9:
Struktura cluster umożliwia przechowywanie w tych samych blokach dyskowych rekordów z różnych relacji.
Przykładowo mamy dwie relacje:
Pracownik Departament
Nazwisko |
… |
Id_depart |
|
Id_depart |
Nazwa |
… |
Morzy |
… |
10 |
|
10 |
Instytut Informatyki |
… |
… |
… |
… |
|
… |
… |
… |
Predefined join - w jednym bloku dyskowym będą przechowywane wszystkie krotki o jednakowej wartości pola Id_depart z relacji Pracownicy i odopowiedni wiersz z relacji Departament:
Morzy |
… |
10 |
||
… |
… |
… |
||
10 |
Instytut Informatyki |
… |
||
Struktura taka ma wypełnienie 2/3 p.(B+-drzewo ma 1/2 p). Poza tym każdy cluster posiada wskaźniki do następnego i poprzedniego, natomiast liść w B+-drzewie ma tylko wskaźnik do następnego liścia.
Zarządzanie współbieżnym wykonywaniem transakcji tak naprawdę określa liczbę użytkowników mogących współbieżnie odwoływać się do tych samych danych.
Model SBD (systemu bazy danych): SBD = {BD, , C()}
a) Baza danych BD:
zbiór relacji widziany przez użytkownika; zakładamy, że wszystkie dane reprezentuje ten sam poziom abstrakcji
zbiór danych (strony, pliki, rekordy w blokach dyskowych) widziany przez SZBD
Użytkownik tworzy zapytania w logicznej bazie danych a system operuje w fizycznej bazie danych.
SRBD (system rozproszonej bazy danych)
W najprostszym przypadku jednej danej logicznej X odpowiada jedna dana fizyczna x = (n, v), gdzie n to nazwa a v to wartość.
W przypadku systemów rozproszonych zakłada się często, że pewne dane są replikowane (tzn. tworzone są kopie, które są rozlokowywane w systemie). Jednej danej logicznej X odpowiada k kopii (replik) x1, x2, … xk ; chcielibyśmy, by repliki były spójne
Repliki tworzymy ze względów efektywnościowych i niezawodnościowych. Repliki trzeba pielęgnować.
ROWA (read-one-write-all) - dane można odczytać z dowolnej repliki, ale zapis danych musi dotyczyć wszystkich replik w celu utrzymania spójności.
Wszystkie repliki są modyfikowane w ramach jednej transakcji; gdy nie uda się zmodyfikować choćby jednej z nich, to cała transakcja jest wycofywana i ostatecznie nie modyfikuje się żadnej. Jest bardzo kosztowna.
Pielęgnacja replik odbywa się poza transakcją - mimo to są to transakcje powiązane.
SRBD może być:
Każda operacja zapisu kasuje starą wersję.
Pojedyncza dana fizyczna x pojawia się jako sekwencja n różnych wersji x1, x2, …, xn tworzonych w różnych chwilach czasowych. Operacja zapisu nie usuwa starej wersji lecz tworzy nową. Dane nie są nadpisywane lecz przechowywane są jej wszystkie wersje.
b) Zbiór transakcji zainicjowanych w systemie przez użytkowników: = (1, 2, …, m)
c) Kryterium poprawności C(), określające kiedy współbieżne wykonanie zadań zleconych przez użytkowników jest poprawne a kiedy nie jest.
a) Definicja
Transakcja jest sekwencją logicznie powiązanych operacji na bazie danych, która przeprowadza bazę danych z jednego stanu spójnego w inny stan spójny. Systemy bazy danych umożliwiają łączenie operacji w transakcje i gwarantują poprawne zarządzanie transakcjami.
Innymi słowy - transakcja jest to dowolna sekwencja operacji zdefiniowana przez użytkownika i z jego punktu widzenia niepodzielna. Realizacja transakcji to podejście all-or-nothing, czyli, gdy choćby jedna operacja nie może zostać wykonana, to cała transakcja jest wycofywana.
Użytkownik oczekuje, że:
Przykład:
Transakcja przelewu kwoty N z konta A na konto B:
begin
// odejmij kwotę N z konta A;
update konta
SET stan = stan - N
where id_konta = A;
// dodaj do konta B kwotę N;
update konta
SET stan = stan + N
where id_konta = B;
commit;
end
Transakcja to:
b) Problemy zarządzania transakcjami
Z punktu widzenia użytkownika, transakcja nie została wykonana. SZBD musi posiadać mechanizmy umożliwiające dokończenie transakcji (REDO) oraz umożliwiające wycofanie się z tego, co zostało już zrobione (UNDO).
Użytkownik gwarantuje systemowi, że zdefiniowana transakcja jest spójna i poprawna. Jeżeli transakcja jest składniowo poprawna, to jest także poprawna semantycznie. Jednak współbieżne wykonanie poprawnych transakcji nie musi być poprawne, stąd system musi wprowadzić mechanizmy poprawnego wykonywania transakcji współbieżnych - moduł zarządzania spójnością.
System powinien posiadać mechanizm dziennika (BACKUP).
c) Własności transakcji
A(tomicity) C(onsistency) I(solation) D(urability)
Są to własności transakcji z punktu widzenia użytkownika.
Atomowość. Zbiór operacji wchodzących w skład transakcji jest niepodzielny; albo zostaną wykonane wszystkie operacje transakcji albo żadna.
Spójność. Poprawne wykonanie transakcji przeprowadza bazę danych z jednego stanu spójnego do innego stanu spójnego.
Tak naprawdę, to spójność musi zostać zagwarantowana przez użytkownika. Spójność jest tu synonimem poprawności.
Izolacja. Transakcje są od siebie logicznie odseparowane. Mogą wzajemnie oddziaływać na siebie w taki sposób jak gdyby były wykonywane sekwencyjnie.
Trwałość. Wyniki zatwierdzonych transakcji nie mogą zostać utracone, niezależnie od awarii systemu.
d) Diagram stanów transakcji
Użytkownik może definiować dowolnie złożone transakcje. Na bazie danych mogą być nałożone dowolnie złożone ograniczenia integralnościowe.
Z punktu widzenia poprawności można brać pod uwagę tylko operacje odczytu i zapisu. Pozostałe operacje (obliczenia) nie mają wpływu na poprawność. Stąd transakcja Ti jest sekwencją operacji na bazie danych, przy czym mamy cztery typy operacji:
Ti: r(x) |
read - odczyt |
Ti: w(x) |
write - zapis |
Ti: c |
commit - zatwierdzenie wyników |
Ti: a |
rollback - wycofanie wyników nie w pełni wykonanej transakcji |
Mamy dwa etapy potwierdzania:
Przykład:
|
Begin_transaction; |
UPDATE pracownicy SET płaca = 1.15 * płaca WHERE staż > 5;
|
Read (A); Write (A); ... Read (Z); Write (Z); |
COMMIT; |
Commit; |
e) Anomalie współbieżnego wykonywania transakcji
Fakt, że użytkownik zdefiniuje poprawne transakcje nie gwarantuje, że zbiór transakcji wykonywanych współbieżnie da wynik poprawny.
Lost update (zagubiona aktualizacja) |
|
Dirty read |
|
Incorrect Summary |
|||
T1 |
T2 |
|
T1 |
T2 |
|
T1 |
T2 |
read(X); X := X-N;
write(X); read(Y);
Y := Y+N; write(Y); commit; |
read(X); X := X+M;
write(X); commit; |
|
read(X); X := X-N; write(X);
read(Y); abort;
|
read(X); X := X+M; write(X); commit;
|
|
read(X); X := X-N; write(X);
read(Y); Y := Y+N; write(Y); |
sum := 0;
read(X); sum := sum+X; read(Y); sum := sum+Y; commit;
|
Poniżej przykład zagubionej aktualizacji.
f) Zarządzanie współbieżnością transakcji
Problem: Współbieżne wykonywanie transakcji może być przyczyną niespójności bazy danych.
Współbieżne wykonywanie zbioru transakcji wymaga zarządzania kolejnością realizacji przeplatających się operacji różnych transakcji.
Z punktu widzenia struktury systemu mamy bazę danych i przed nią moduł zarządzania współbieżnością (CC - concurrency control).
CC stosując jakiś algorytm generuje realizację wyjściową gwarantując, że nie pojawią się anomalie. Moduł CC może daną transakcję:
Ten rodzaj zarządzania, nazywany zarządzaniem współbieżnością transakcji, polega na takim uporządkowaniu operacji wchodzących w skład współbieżnie wykonywanych transakcji, które będzie wolne od anomalii.
Poprawne uporządkowania operacji zbioru współbieżnych transakcji są wynikiem zastosowania algorytmu zarządzania współbieżnością transakcji. Rozmiar zbioru poprawnych uporządkowań jest miarą stopnia współbieżności, i co za tym idzie, miarą jakości danego algorytmu.
g) Model transakcji
Transakcją Ti nazywamy uporządkowaną parę:
Ti = (, Ti ),
gdzie:
Relacja porządkująca określa która operacja jest wykonywana przed którą.
Przykład:
Ti = ( = {r1(x), r2(y), w1 (x), w2(y), c}, Ti = {(r1(x),w1(x)), (w1(x), r2(y)), (r2(y), c)} )
Tak zdefiniowana transakcja może być reprezentowana przez graf skierowany:
G = (V, A),
gdzie:
Przykład:
h) Klasyfikacja transakcji
1. Ze względu na uporządkowanie operacji:
2. Ze względu na tryb przetwarzania danych:
3. Ze względu na rodzaj operacji:
i) Modele współbieżności
Ze względu na informacje, które posiada moduł CC definiujemy modele współbieżności:
Nie ma tu żadnych ograniczeń w dostępie do danych.
Mamy tu dostęp do dodatkowych informacji.
Nie ma potrzeby kontrolowania operacji wykonywanych na danych nie powiązanych.
a) Definicja
Chcemy wprowadzić kryterium, które pozwoli odpowiedzieć na pytanie: czy dana transakcja jest poprawna? Stąd wprowadzamy pojęcie realizacji.
Realizacją (historią) r zbioru transakcji nazywamy częściowo uporządkowany zbiór:
r() = (() , r ),
gdzie:
(Odwrócone to znak uogólnionej sumy prostej).
Realizacja zawierająca tylko operacje zatwierdzonych transakcji nazywana jest zaakceptowaną projekcją. (Dalsze rozważania dotyczyć będą tyko realizacji spełniających powyższy warunek.)
Relacja r zachowuje relacje porządkujące z poszczególnych transakcji, gdyż składa się z tychże relacji.
Realizacja jest potrzebna, by móc analizować zbiór operacji grupy transakcji i stwierdzić, czy jest on poprawny, czy nie.
Realizacja opisująca przykład zagubionej aktualizacji ma postać:
Relacja r jest przedstawiona przez kolejność operacji (od lewej do prawej).
Zakładamy, że każda realizacja rozpoczyna się hipotetyczną transakcją T0 (składającą się z operacji zapisu wszystkich danych tworzących początkowy stan bazy danych) i kończy się hipotetyczną transakcją Tf (składającą się z operacji odczytu wszystkich danych - odczytu stanu końcowego bazy danych). Ponadto zakładamy, że wszystkie operacje należące do transakcji kończącej się operacją rollback są odrzucane. Nas interesują tylko zaakceptowane transakcje.
Przykład:
Mamy bazę danych o dwóch wartościach (x i y). Mamy także dwie transakcje (T1 i T2). Każda z transakcji składa się z operacji. Pytanie: czy taka realizacja jest poprawna czy nie?
r: w0(x), w0(y), c0, r1(x), r2(x), w1(x), r1(y), w2(x), c2, w1(y), c1, rf(x), rf(y), cf ;
Graf realizacji GR(r()) = (V, A) jest grafem skierowanym, który reprezentuje daną realizację. Węzły grafu odpowiadają operacjom ze zbioru () natomiast krawędzie grafu reprezentują relację częściowego porządku r.
Przykład:
b) Realizacje sekwencyjne i współbieżne
Mówimy, że dana realizacja jest sekwencyjna, jeżeli dla każdych dwóch transakcji, wszystkie operacje jednej z nich poprzedzają wszystkie operacje drugiej. W przeciwnym wypadku realizacja jest współbieżna.
c) Stan i perspektywa bazy danych
Stan bazy danych jest zbiorem wartości wszystkich danych bazy danych.
Obraz bazy danych widziany przez transakcję Ti jest zbiorem wartości odczytywanych przez nią danych.
d) Równoważność realizacji
Mówimy, że dwie realizacje r() = (() , r ) i r'() = (() , r' ) są obrazowo równoważne (view equivalent), jeżeli dla każdej transakcji Ti , widziany przez nią w realizacji r() obraz bazy danych jest identyczny z obrazem bazy danych widzianym przez tę samą transakcję w realizacji r'().
Mówimy, że dwie realizacje r() = ((),r ) i r'() = ((),r' ) są stanowo równoważne (state equivalent), jeżeli dla dowolnego początkowego stanu bazy danych, stan bazy danych po wykonaniu zbioru transakcji zgodnie z realizacją r(τ) jest identyczny ze stanem bazy danych po wykonaniu zbioru transakcji zgodnie z realizacją r'().
Mówimy, że dwie realizacje r() = ((),r ) i r'() = ((), r' ) są równoważne, jeżeli są one stanowo równoważne i obrazowo równoważne.
Cały problem polega na tym, że powyższych kryteriów nie można wykorzystać do konstruowania algorytmów.
a) Kryterium uszeregowalności realizacji
Jest to fundamentalne kryterium.
Realizacja r zbioru transakcji jest poprawna jeżeli jest ona równoważna jakiejś sekwencyjnej realizacji tego zbioru transakcji. Realizację taką nazywamy realizacją uszeregowalną.
Realizacja każdego zbioru transakcji sekwencyjnych jest poprawna. Z punktu widzenia tego kryterium nieważna jest kolejność przybywania transakcji do systemu.
Przykład:
Czy realizacja jest poprawny?
r(): T1: r(x), T2: r(x), T1: w(x), T1: c, T2: w(x), T2: c
Aby powyższa realizacja była poprawna, musi być równoważna jednej z poniższych:
r1(): T1: r(x), T1: w(x), T1: c, T2: r(x), T2: w(x), T2: c
r2(): T2: r(x), T2: w(x), T2: c, T1: r(x), T1: w(x), T1: c
Załóżmy, że początkowo x=1000. W wyniku wykonania realizacji r() otrzymujemy x=1100. Wykonania realizacji r1() i r2() dają x=1200. Brak jest więc równoważności stanowej, wobec czego realizacja r() nie jest poprawna.
Problem sprawdzania, czy transakcja jest poprawna jest silnie NP-zupełnym. Uszeregowalność można sprawdzić budując graf uszeregowalności.
b) Graf uszeregowalności
Grafem uszeregowalności dla realizacji r() nazywamy skierowany graf SG(r()) = (V, A) taki, w którym zbiór wierzchołków V odpowiada transakcjom ze zbioru , natomiast zbiór krawędzi jest zdefiniowany następująco:
Jeżeli istnieje dana x, i operacje Ti : r(x), Tj : w(x) (), takie, że Ti : r(x) czyta wartość danej x zapisanej przez operację Tj : w(x), to:
Graf uszeregowalności jest poligrafem, tzn. między dwoma wierzchołkami może istnieć wiele łuków, stąd jego konstrukcja jest problemem NP-zupełnym.
c) Kryterium uszeregowalności realizacji
Dana realizacja r() jest uszeregowalna wtedy i tylko wtedy, gdy można skonstruować dla niej acykliczny skierowany graf uszeregowalności SG(r()).
W praktyce kryterium to nie jest stosowane, gdyż trzeba by było sprawdzić wszystkie grafy uszeregowalności dla danego zbioru transakcji. W praktyce stosuje się kryterium D-uszeregowalności. Wszystkie algorytmy wykorzystywane w praktyce bazują na kryterium D-uszeregowalności.
d) D-uszeregowalność realizacji
Dwie operacje oi(x), oj(y) współbieżnej realizacji są konfliktowe, wtedy i tylko wtedy, gdy są spełnione następujące trzy warunki:
1. x = y. Operacje na różnych danych nigdy nie są konfliktowe.
2. i j. Operacje konfliktowe muszą należeć do różnych transakcji.
3. Jedna z dwóch operacji oi lub oj musi być operacją zapisu.
Konflikt następuje wtedy, gdy dwie operacje oi i oj żądają dostępu do tej samej danej x, przy czym jedna z nich to operacja zapisu.
Dwie transakcje Ti, Tj są konfliktowe jeżeli zawierają wzajemnie konfliktowe operacje.
Mówimy, że operacja oi(x) poprzedza operację oj(y) w realizacji r(), co zapisujemy jako oi(x) oj(y), jeżeli operacje te są konfliktowe i oi(x) r oj(y).
Mówimy, że transakcja Ti poprzedza transakcję Tj w realizacji r(), co zapisujemy jako Ti Tj, jeżeli zawierają odpowiednio operacje oi(x) i oj(x), między którymi zachodzi związek poprzedzania.
Mówimy, że dwie realizacje r() = (() , r ) i r'() = (() , r' ) są konfliktowo równoważne, jeżeli dla każdej pary operacji oi(x) i oj(x) w realizacji r(), takich, że oi(x) oj(y), zachodzi również oi(x) oj(y) w realizacji r'().
D-uszeregowalność jest zawężeniem pojęcia poprawności.
e) Kryterium D-uszeregowalności realizacji
Realizacja r() zbioru transakcji jest D-uszeregowalna wtedy i tylko wtedy, gdy jest ona konfliktowo równoważna dowolnej sekwencyjnej realizacji .
Każda realizacja D-uszeregowalna jest uszeregowalna ale nie odwrotnie.
f) Graf D-uszeregowalności realizacji
Grafem D-uszeregowalności dla realizacji r() nazywamy skierowany graf DSG(r()) = (V, A), taki, w którym zbiór wierzchołków V odpowiada transakcjom ze zbioru , czyli V = {}, natomiast zbiór krawędzi A = {(Ti, Tj) : Ti Tj}.
Graf D-uszeregowalności jest bardzo prosty w konstrukcji.
D-uszeregowalność ogranicza stopień współbieżności ale jej wyznaczenie jest łatwe obliczeniowo.
Realizacja r() zbioru transakcji jest D-uszeregowalna wtedy i tylko wtedy, gdy jej graf D-uszeregowalności jest acykliczny.
Przykład:
Czy zbiór transakcji jest poprawny (zaznaczono konflikty)?
Graf D-uszeregowalności:
Cykl w grafie oznacza, że realizacja nie jest poprawna.
Poprawność transakcji możemy sprawdzać na bieżąco budując graf D-uszeregowalności i sprawdzając, czy nie pojawił się cykl.
Problem określania poprawnego uporządkowania akcji współbieżnie wykonywanych transakcji jest rozwiązywany za pomocą metod, które możemy podzielić na trzy grupy:
1. Algorytmy blokowania dostępu do danych - uszeregowanie transakcji wynika z kolejności uzyskiwanych blokad (algorytm blokowania dwufazowego).
2. Algorytmy znaczników czasowych - uszeregowanie transakcji wynika z wartości znaczników czasowych związanych z transakcjami.
3. Algorytmy optymistyczne - walidacja poprawności uszeregowania.
Wychodzi się z założenia, że mało prawdopodobne jest wykonanie współbieżnych operacji na tych samych danych.
W metodzie blokowania (locking method) z każdą daną x jest związana blokada (lock). Ściśle biorąc, blokada może być związana z jednostką dostępu do danej, na przykład ze stroną pamięci wirtualnej zawierającą całą daną lub jej część. Zakłada się, że każda transakcja przed odczytem lub zapisem danej musi założyć odpowiednią blokadę na tej danej oraz, że wszystkie blokady założone przez transakcję zostaną zdjęte przed zakończeniem jej wykonywania. Zakładanie blokad danych, do których transakcja żąda dostępu, eliminuje dostęp do nich przez inne transakcje w czasie, gdy ograniczenia integralnościowe mogą być przejściowo naruszone.
Wyróżniamy dwa podstawowe typy blokad:
Operacje na danej nie powodujące jej uaktualnienia powinny być poprzedzone założeniem blokady współdzielonej. Operacje uaktualniające daną powinny być poprzedzonej założeniem na niej blokady wyłącznej.
Mamy dwa typy blokad: do zapisu i do odczytu.
Ze względu na proces blokowania, dane w bazie danych mogą występować w jednym z trzech stanów:
a) Kompatybilność blokad
Mówimy, że dwie blokady są zgodne (compatibile), jeżeli mogą być ustawione na tej samej danej przez dwie różne transakcje. W przeciwnym razie mówimy o blokadach niezgodnych.
Lock1 - blokada założona przez pewną transakcję na danej x.
Lock2 - blokada, która może być założona przez inną transakcję na danej x.
|
|
Lock2 |
|
|
|
R |
W |
Lock1 |
R |
|
- |
|
W |
- |
- |
b) Konwersja blokad
Transakcja posiadająca blokadę określonego typu na danej może dokonać jej konwersji w blokadę innego typu.
Lock1 - blokada założona przez transakcję na danej x.
Lock2 - blokada, na którą ta transakcja chce zmienić blokadę już posiadaną.
|
|
Lock2 |
|
|
|
R |
W |
Lock1 |
R |
|
|
|
W |
- |
|
c) Implementacja algorytmów blokowania
Struktury danych:
dana |
tid |
blokada |
|
dana |
tid |
blokada |
kolejka |
x1 |
T1 |
W |
|
x1 |
T2 |
R |
1 |
x2 |
T1 |
R |
|
x1 |
T3 |
W |
2 |
x2 |
T2 |
R |
|
x2 |
T4 |
W |
1 |
x3 |
T1 |
W |
|
|
|
|
|
Operacje: LOCK, R_lock, W_lock, Unlock
LOCK(X, tid) {0, R, W}
R_lock(X, tid) begin
B: if (LOCK(X, tid) = 0 or LOCK(X, tid) = R)
then LOCK(X, tid) R;
else begin
< insert into queue(X) and wait (until lock manager wakes up the transaction)>;
go to B;
end;
end R_lock;
W_lock(X, tid) begin
B: if LOCK(X, tid) = 0
then LOCK(X, tid) W;
else begin
< insert into queue(X) and wait (until lock manager wakes up the transaction)>;
go to B;
end;
end W_lock;
Unlock(X, tid) begin
if LOCK(X, tid) = W
then begin
LOCK(X, tid) 0;
< wake up one of the waiting transactions, if any >;
end;
else if LOCK(X, tid) = R
then begin
LOCK(X, tid) 0;
if (number_of_read_locks_on_X = 0) then
begin
< wake up one of the waiting transactions, if any >;
end;
end;
end Unlock;
Przykład:
T1 |
T2 |
R_lock(T1, Y) |
R_lock(T2, X) |
read(Y) |
read(X) |
unlock(Y) |
unlock(X) |
W_lock(T1, X) |
W_lock(T2, Y) |
read(X) |
read(Y) |
X := X + Y; |
Y := Y + X; |
write(X); |
write(Y); |
unlock(X) |
unlock(Y) |
Wartości początkowe: X = 20, Y = 30
Wyniki sekwencyjnych realizacji transakcji T1 i T2 :
(T1 T2 ) : X = 50, Y = 80; (T1 T2 ) : X = 70, Y = 50;
Realizacja współbieżna:
T1 |
T2 |
R_lock(T1, Y) |
|
read(Y) |
|
unlock(Y) |
|
|
R_lock(T2, X) |
|
read(X) |
|
unlock(X) |
|
W_lock(T2, Y) |
|
read(Y) |
|
Y := Y + X; |
|
write(Y); |
|
unlock(Y) |
W_lock(T1, X) |
|
read(X) |
|
X := X + Y; |
|
write(X); |
|
unlock(X) |
|
Wynik realizacji współbieżnej: X = 50, Y = 50 (realizacja nieuszeregowalna)
Idea algorytmu blokowania: zanim zostanie zrealizowana operacja, na daną zostanie nałożona blokada; następnie zostanie wykonana operacja; na końcu blokada zostanie zdjęta.
System dysponuje czterema operacjami:
Jednakże realizacje niepoprawne nadal pozostają niepoprawnymi, bez względu na to, czy zastosowano blokady, czy też nie.
d) Algorytmy blokowania dwufazowego
Najszerzej stosowanym w praktyce algorytmem metody blokowania jest algorytm blokowania dwufazowego (two-phase locking) oznaczony przez 2PL. Istotą tego algorytmu jest wymagania, aby wykonywanie każdej transakcji przebiegało w dwóch fazach:
W fazie tej transakcja musi uzyskać blokady wszystkich danych, do których będzie dokonywać dostępu. Moment założenia wszystkich żądanych blokad, równoznaczny z zakończeniem fazy blokowania, jest nazywany punktem akceptacji (commit point).
W fazie tej następuje zdejmowanie wszystkich nałożonych blokad. Ponadto w fazie tej nie można zakładać nowych blokad.
W algorytmie 2PL odczyt danej jest możliwy natychmiast po nałożeniu blokady tej danej, a więc w fazie blokowania, natomiast zapis jest możliwy dopiero w po osiągnięciu przez transakcję punktu akceptacji, a więc w fazie odblokowywania. Ściśle biorąc, operacja zapisu jest wykonywana następująco. Założenie blokady wyłącznej jest równoznaczne z wykonaniem tzw. zapisu wstępnego w obszarze roboczym związanym z zapisywaną daną. Zapis właściwy jest realizowany dopiero w fazie odblokowywania, w momencie zdejmowania blokady tej danej na podstawie zawartości obszaru roboczego. Taka procedura gwarantuje atomowość transakcji.
Algorytm podstawowy:
1. Każda operacja read(X) danej transakcji T musi być poprzedzona operacją R_lock(X, T) lub W_lock(X, T).
2. Każda operacja write(X) danej transakcji T musi być poprzedzona operacją W_lock(X, T).
3. Operacje unlock(x,T) dla danej transakcji T są wykonywane po zakończeniu wszystkich operacji read i write.
Algorytm statyczny: (1., 2., 3.)
4. Wszystkie blokady muszą być uzyskane przed rozpoczęciem transakcji (przez predeklarowanie zbioru odczytywanych i modyfikowanych danych) .
Algorytm restryktywny: (1., 2.)
3. Operacje unlock(x,T) dla danej transakcji T są wykonywane po operacji commit lub rollback.
T1 |
T2 |
R_lock(T1, Y) |
|
read(Y) |
|
W_lock(T1, X) |
|
|
R_lock(T2, X) |
read(X) |
(wait) |
X := X + Y; |
(wait) |
write(X); |
(wait) |
unlock(Y) |
(wait) |
unlock(X) |
(wait) |
|
read(X) |
|
W_lock(T2, Y) |
|
read(Y) |
|
Y := Y + X; |
|
write(Y); |
|
unlock(X) |
|
unlock(Y) |
Przykład:
Kolejne kroki:
Wystąpiło zakleszczenie.
Algorytm blokowania dwufazowego gwarantuje D-uszeregowalność realizacji.
e) Zakleszczenia transakcji
T1 |
T2 |
R_lock(T1, Y) |
|
read(Y) |
|
|
R_lock(T2, X) |
|
read(X) |
|
W_lock(T2, Y) |
W_lock(T1, X) |
(wait) |
(wait) |
(wait) |
(wait) |
(wait) |
dead |
lock |
Przykład:
Strategie walki z zakleszczeniem w systemach operacyjnych:
Generalnie w systemie komputerowym wyróżnia się zasoby:
Mówiąc o zakleszczeniu w systemach operacyjnych ma się na myśli raczej zasoby ostatniego typu. W systemach baz danych w centrum zainteresowania są zasoby pierwszego typu, czyli dane. Z tego też względu nie stosuje się tam metody unikania, natomiast stosuje się wykrywanie i rozwiązywanie oraz zapobieganie.
Deadlock detection & resolution
Buduje się graf oczekiwania (wait-for-graph) i sprawdza się, czy nie ma cykli (cykl oznacza zakleszczenie).
Graf oczekiwania
Deadlock prevention
Idea: nie można dopuścić do zakleszczenia. Stosuje się testy. Jednak w systemach baz danych istnieją różne problemy.
Problem 1.
Transakcje rozproszone żądają dostępu do wielu baz danych. Lokalne systemy zarządzania mogą stwierdzić, że zakleszczenia nie ma, podczas gdy może wystąpić zakleszczenie globalne. Wykrycie czegoś takiego jest bardzo kosztowne.
Problem 2.
Autoryzacja dostępu - ktoś może zdalnie uruchomić jakąś transakcję, która może zablokować bazę danych.
f) Algorytmy zapobiegania zakleszczeniom
Każda transakcja przybywając do systemu otrzymuje jednoznaczny identyfikator - etykietę czasową (znacznik czasowy) posiadającą dwa pola:
Algorytmy wykorzystujące znaczniki czasowe transakcji - TS(T), nadawane w momencie przybywania transakcji do systemu.
Znacznie rzadszym jest przypadek, aby transakcja starsza żądała dostępu do zasobu blokowanego przez transakcję młodszą.
Powyższe algorytmy bardzo łatwo połączyć z algorytmem blokowania dwufazowego.
Algorytmy nie korzystające ze znaczników czasowych.
Powyższe dwa algorytmy zapobiegają zakleszczeniu, gdy miał zamiar się pojawić. Mają jednak także tę wadę, że transakcje mogą być restartowane nawet, gdy zakleszczenie nie miało zamiaru się pojawić.
Stosuje się także algorytm time-out, w którym transakcja czeka na zablokowany zasób przez jakiś czas i po jego upływie jest restartowana. Istnieje tu jednak duża trudność z określeniem optymalnej długości tego odcinka czasu.
g) Ziarnistość blokowania
Potrzeba konstruowania hierarchicznych algorytmów blokowania wynika z konieczności rozwiązania tzw. problemu ziarnistości blokad (granularity). Problem ten polega na doborze rozmiaru blokowanej jednostki, a wynika ze sprzecznych wymagań efektywnościowych transakcji żądającej dostępu do małej lub dużej liczby danych. Mówiąc obrazowo, wykonanie transakcji żądającej dostępu do trzech danych wymaga założenia i zdjęcia trzech blokad, a do tysiąca danych - tysiąca blokad. Stąd problem określenia optymalnego rozmiaru jednostki blokady. Maksymalizacja współbieżności zbioru małych transakcji wymaga drobnej ziarnistości blokad, natomiast minimalizacja kosztu blokowania danych dla dużych transakcji wymaga grubej ziarnistości blokad.
Hierarchia ta oznacza, że można blokować pojedyncze krotki, albo całe relacje lub wręcz można zablokować bazę danych.
W systemach baz danych napotyka się na szereg problemów:
Problem 1 - koszt zakładania blokad. Zamiast zakładać 100 blokad na sąsiadujących rekordach łatwiej i szybciej jest założyć jedną tylko blokadę ale na całej relacji.
Problem 2 - fantomy. Przykładowo szukamy pracownika o rudych włosach i niebieskich oczach. System dla każdej krotki relacji Pracownicy założy blokadę do odczytu, sprawdzi krotkę, po czym zdejmie blokadę. Jeżeli w trakcie wykonywania tej transakcji dojdzie jakaś nowa krotka spełniająca kryterium poszukiwawcze, to blokada ominie tę krotkę i nie zostanie ona przedstawiona użytkownikowi.
W hierarchicznych algorytmach blokowania wyróżnia się dwa rodzaje blokad: podstawowe i intencjonalne.
Blokady podstawowe są tymi blokadami, które rozważaliśmy omawiając niehierarchiczną metodą blokowania. Wyróżniamy zatem blokadę podstawową do odczytu (współdzieloną), oznaczoną przez R, oraz blokadę podstawową do zapisu (wyłączną), oznaczoną przez W. Różnica w porównaniu z blokadami rozpatrywanymi poprzednio polega na tym, że zakładając blokadę podstawową na określonym poziomie hierarchii ziaren blokujemy implicite wszystkie następniki tej jednostki w hierarchii. Np. blokując relację blokujemy jednocześnie w taki sam sposób wszystkie jej krotki. Jednakże stosując wyłącznie mechanizm blokad podstawowych i gwarantując nienaruszalność warunku zgodności typów blokad, nie możemy zapewnić, że w przypadku współbieżnej realizacji transakcji spójność bazy danych nie zostanie naruszona.
W celu zapewnienia poprawności hierarchicznego blokowania danych należy zatem zagwarantować, że po założeniu przez transakcję blokady podstawowej na danym ziarnie R w hierarchii ziaren, żadna inna transakcja nie uzyska zgodnej z nią blokady żadnego ziarna będącego poprzednikiem ziarna R.
Jednym z możliwych rozwiązań tego problemu jest wprowadzenie blokad intencjonalnych (intention lock). Założenie blokady intencjonalnej na danym poziomie hierarchii ziaren oznacza, że na niższym poziomie jest założona blokada podstawowa. Typy blokad intencjonalnych zależą bezpośrednio od typów blokad podstawowych.
Ideą blokowania intencjonalnego jest to, by blokowanie zaczynać na poziomie relacji i schodzić potem do poziomu krotek.
Blokady intencjonalne :
Zgodność omówionych typów blokad przedstawiono w tabelce:
|
|
Blokada żądana |
||||
|
|
IR |
IW |
R |
RIW |
W |
|
IR |
|
|
|
|
- |
Blokada |
IW |
|
|
- |
- |
- |
ustawiona |
R |
|
- |
|
- |
- |
|
RIW |
|
- |
- |
- |
- |
|
W |
- |
- |
- |
- |
- |
Reguły blokowania intencjonalnego
(timestamp ordering)
Znacznik czasowy (timestamp) transakcji T, czyli TS(T), jest jej unikalnym identyfikatorem. Znaczniki są przydzielone transakcjom w kolejności, w której transakcje pojawiają się w systemie zarządzania bazą danych.
Z każdą daną (x) w bazie danych związane są dwie wartości znaczników czasowych:
Algorytm ten jest łatwy w implementacji i ma wbudowany mechanizm zapobiegania zakleszczeniu. Jeśli nie ma blokad, to transakcja realizuje dostęp do danych zgodnie z kolejnością etykiet czasowych.
Implementacja algorytmu znaczników czasowych
Read(Ti, x) begin
if (TS(Ti) < Write_TS(x)) then
< abort Ti and restart it with a new timestamp >;
else begin
< read x >;
Read_TS(x) max ( Read_TS(x), TS(Ti) );
end;
end Read;
Write(Ti, x) begin
if (TS(Ti) < Read_TS(x) or TS(Ti) < Write_TS(x)) then
< abort Ti and restart it with a new timestamp >;
else begin
< write x >;
Write_TS(x) TS(Ti);
end;
end Write;
Przykład:
Kolejne kroki:
Kaskadowe wycofywanie blokad
Algorytmy optymistyczne zarządzania współbieżnością transakcji przeprowadzają transakcje przez trzy stany:
Z każdą transakcją Ti związane są czasy rozpoczęcia poszczególnych faz transakcji oraz utrzymywane są zbiory danych odczytywanych Ri i modyfikowanych Wi.
W fazie walidacji transakcji Ti, dla każdej transakcji Tj, która została zatwierdzona lub znajduje się w fazie walidacji sprawdzane jest czy spełniony jest jeden z warunków:
1. Transakcja Tj zakończyła swoją fazę zapisu zanim transakcja Ti rozpoczęła swoją fazę odczytu.
W jednowersyjnych bazach danych istnieje niski stopień współbieżności algorytmów synchronizacji transakcji.
Konfliktowość operacji:
operacja operacja |
read(x) |
write(x) |
read(x) |
|
− |
write(x) |
− |
− |
Zwiększając liczbę wersji zwiększamy stopień współbieżności.
Dana wielowersyjna:
Konfliktowość operacji:
operacja operacja |
read(x) |
write(x) |
read(x) |
|
|
write(x) |
|
− |
Wielowersyjną realizacją wr zbioru transakcji τ nazywamy częściowo uporządkowany zbiór operacji tych transakcji:
wr(τ) = ((τ), pwr, h),
gdzie:
W tym przypadku każda dana może być przechowywana w postaci zbioru wersji.
Przykład:
Mamy dwie transakcje. T1 to typowy przykład transakcji audit (przebiega po danych sumując je). Natomiast T1 czyta dane x i y, dodaje do nich po 500 i zapisuje je do bazy danych.
Zakładamy, że system jest jednowersyjny. Wobec tego transakcja T1 chcąc odczytać daną y (przedostatnia operacja) może się ubiegać o dostęp tylko do jednej (ostatniej) wersji tej danej, a więc y1. W efekcie realizacja ta nie jest D-uszeregowalna, gdyż graf jest cykliczny - realizacja nie jest więc poprawna i transakcja T1 będzie musiała być zrestartowana.
Gdyby system był wielowersyjny, to mielibyśmy kolejne wersje danych x i y: x0, y0, x1, y1, …. W takim przypadku T1 chcąc odczytać daną y (przedostatnia operacja) może otrzymać dostęp do starszej wersji tej danej (y0). W tym przypadku realizacja będzie poprawna i transakcja T1 nie będzie musiała być restartowana.
Rozpatrzmy jednak taką realizację:
r(): T1: r(x), T1: w(x), T2: r(x), T2: w(x), T3: r(x), T3: w(x)
Każda z transakcji dodaje do danej x liczbę 100. Zakładamy, że na początku x=100.
W systemie jednowersyjnym realizacja ta jest poprawna. Natomiast w systemie wielowersyjnym realizacja ta nie musi być poprawna, gdyż operacja T2: r(x) może dotyczyć starszej wersji danej x, czyli x0=0, a nie wersji ostatniej (x1=100).
W systemie jednowersyjnym wzorcem poprawności była realizacja sekwencyjna (patrz definicja uszeregowalności). Natomiast w systemach wielowersyjnych sam fakt, że realizacja jest sekwencyjna, już nie wystarcza. Potrzebna jest dodatkowa informacja o numerze wersji danej, której dotyczy dana operacja.
Standardowa sekwencyjna realizacja wielowersyjna
Sekwencyjna realizacja wielowersyjna jest standardowa, jeżeli dla dowolnej operacji odczytu Ti : r(x) nie istnieje operacja zapisu Tj : w(x) taka, że spełniony byłby warunek:
h(Ti: r(x)) pwr Tj: w(x) pwr Ti: r(x)
Tu wyjaśnia się, dlaczego dodatkowym elementem realizacji wielowersyjnej (patrz definicja) jest funkcja h. To właśnie ona określa, którą wersję danej należy odczytać przy operacji odczytu. W realizacji standardowej transakcja musi czytać ostatnio zapisaną wartość danej.
Kryterium uszeregowalności wielowersyjnej
Wielowersyjna realizacja wr(τ) zbioru transakcji τ jest uszeregowalna wtedy i tylko wtedy, gdy jest ona równoważna dowolnej standardowej sekwencyjnej realizacji wielowersyjnej zbioru transakcji τ.
Standardowa realizacja sekwencyjna stanowić będzie wzorzec poprawności realizacji w systemie wielowersyjnym.
Ze względu na proces blokowania, dane w bazie danych mogą występować w jednym z czterech stanów:
Proces akceptacji danych jest realizowany jako część operacji zatwierdzania transakcji. Procesowi akceptacji podlegają dane modyfikowane przez transakcje.
Kompatybilność blokad
Dwie blokady są kompatybilne jeżeli mogą być ustawione na tej samej danej przez dwie różne transakcje.
blokada uzyskana blokada żądana |
R |
W |
C |
R |
|
|
- |
W |
|
- |
- |
C |
- |
- |
- |
Read(x, tid) begin
B: if (LOCK(x, tid) = C)
then begin
< insert into queue(x) and wait (until lock manager wakes up the transaction) >;
go to B;
end;
else begin
LOCK(x, tid) ← R;
< read x >;
end;
end Read;
Write(x, tid)
begin
B: if (LOCK(x, tid) = 0 or LOCK(x, tid) = R)
then begin
LOCK(X, tid) ← W;
< create new version x' >;
end;
else begin
< insert into queue(x) and wait (until lock manager wakes up the transaction) >;
go to B;
end;
end Write;
Certify(x, tid) begin
B: if (number_of_read_locks_on_x = 0) then begin
LOCK(X, tid) ← C;
< replace old version x with x' >;
end;
else begin
< wait (until lock manager wakes up the transaction) >;
go to B;
end;
end Certify;
W wielowersyjnej bazie danych dla każdej danej x przechowywanej w postaci wielu wersji (x = <x0, x1, …, xn>) utrzymywana jest jej historia:
H(x) = {(Read_TS(x0), Write_TS(x0)), …, (Read_TS(xn), Write_TS(xn))}
gdzie:
Tak więc dla każdej i-tej wersji danej x jest przechowywana para (Read_TS(xi), Write_TS(xi)). Transakcja Ti , która chce odczytać daną x, musi odczytać taką k-tą wersję danej x, że Write_TS(xk) < TS(Ti).
Operacja odczytu jest wykonywana zawsze i transakcja odczytująca nigdy nie zostanie odrzucona. Niestety nie da się tego samego zagwarantować dla operacji zapisu.
Read(Ti, x) begin
< read xk, such that Write_TS(xk)=max{Write_TS(xj):Write_TS(xj)≤TS(Ti)} >;
if (Read_TS(xk) < TS(Ti)) then
Read_TS(xk) ← TS(Ti);
end Read;
Komentarz do funkcji Read:
Jeżeli transakcja Ti chce odczytać daną x, to należy wyznaczyć wersję, która zostanie faktycznie odczytana. Wybiera się tę wersję xk, która jest najpóźniejsza ze zbioru wersji spełniających warunek Write_TS(xk) < TS(Ti). Następnie, jeżeli Read_TS(xk) < TS(Ti), to etykiecie Read_TS(xk) przypisuje się wartość etykiety TS(Ti).
Write(Ti, x) begin
if (exists xk, such that Write_TS(xk)≤TS(Ti)≤Read_TS(xk))
then
< abort Ti and restart it with a new timestamp >;
else begin
< write xk >;
Write_TS(xk), Read_TS(xk) ← TS(Ti);
end;
end Write;
Komentarz do funkcji Write:
Jeżeli transakcja Ti chce zapisać daną x, to sprawdza się czy istnieje taka wersja xk, dla której Write_TS(xk) ≤ TS(Ti) ≤ Read_TS(xk). Jeżeli taka wersja istnieje, to transakcja Ti jest odrzucana (restartowana z nową etykietą czasową). Jeśli natomiast taka wersja nie istnieje, to tworzona jest nowa wersja danej xl, przy czym etykietom Write_TS(xl) i Read_TS(xl) przypisuje się wartość etykiety TS(Ti).
Liczba wersji możliwych do utworzenia jest ograniczona zasobami systemu. Nie można tworzyć w nieskończoność nowych wersji pamiętając jednocześnie wszystkie poprzednie. W końcu zabraknie pamięci i trzeba będzie zacząć kasować wersje najstarsze.
Pamięć:
Pamięcią ulotną jest pamięć operacyjna, a pamięcią trwałą jest pamięć dyskowa. Napotyka się na problemy na styku tych dwóch typów pamięci, gdyż różnią się one organizacją, sposobem i szybkością dostępu. Trzeba zagwarantować odwzorowanie między tymi pamięciami. Toteż na styku tych pamięci umieszcza się specjalne bufory I/O mające na celu zmniejszenie liczby kosztownych operacji dostępu do wolnej pamięci dyskowej. Bloki dyskowe najczęściej są sprowadzane do bufora i pamiętane tam jako strony w buforze. Informacje o tym, jakie bloki dyskowe znajdują się w buforze, są przechowywane w tablicy bufora (lookaside table). Chcemy, aby dane, które trafiły do bufora były w nim trzymane jak długo się da. Niestety w końcu zabraknie w buforze miejsca i trzeba będzie jakąś stronę zrzucić na dysk aby zrobiło się miejsce na dane aktualnie potrzebne. Do zarządzania buforem stosuje się strategię LRU, wg. której na dysk zostaje zrzucona strona najmniej używana. Co jednak zrobić, gdy dane znajdujące się na stronie przechowywanej w buforze zostaną zmienione. Czy od razu zrzucić tę stronę na dysk zabezpieczając się przed niespójnością danych znajdujących się w PAO i danych znajdujących się na dysku? Otóż podejście takie byłoby wysoce nieefektywne.
Nie chcemy zapisywać strony na dysk za każdym razem, gdy strona jest aktualizowana przez transakcję.
Wniosek: Często aktualizowane strony pozostają w buforze aż:
Mówimy, że strona w buforze jest „brudna”, jeżeli zastała uaktualniona przez transakcję od czasu jest ostatniego zapisu na dysk. Brudne strony mogą pozostawać w buforze jeszcze długo po tym, jak uaktualniające je transakcje zostały zaakceptowane.
Problem: Wystąpił zanik napięcia. Jeżeli aktualizowane strony nie były zapisywane na dysk, to tracimy informacje o aktualizacjach.
Z kolei zapisywanie strony na dysk zaraz po jej aktualizacji może doprowadzić do niespójności, jeśli okazałoby się później, że transakcja, która dokonała modyfikacji, nie została zaakceptowana. Transakcja zostanie więc odrzucona, ale zmiany przez nią wprowadzone pozostaną. System musi zapewnić atomowość i trwałość transakcji oraz dostarczyć mechanizm wycofania transakcji (wycofania zmian wprowadzonych przez nie zaakceptowaną transakcję).
Większość systemów bazuje na mechanizmie tworzenia rekordu logu.
W momencie wystąpienia aktualizacji system zapisuje ten fakt w postaci tzw. rekordu logu (log entry) w buforze logu (log buffer). Co pewien czas bufor logu jest zapisywany na dysk do pliku sekwencyjnego - pliku logu (log file).
Jednak by zagwarantować poprawność mechanizmu odtwarzania transakcji system musi zapewnić rozsądne operowanie rekordem logu i plikiem logu. Trzeba sobie odpowiedzieć na pytania: Jakie powinny być struktury rekordu i pliku logu? Jak często bufor logu powinien być zapisywany na dysk?
Załóżmy, że mamy dwie współbieżne transakcje operujące na danych, z których każda znajduje się na innej stronie:
r1 = T1 : r(a,50) T1 : w(a,20) T2 : r(c,100) T2 : w(c,50) T2 : c T1 : r(b,50) T1 : w(b,80) T1 : c .........
r(a,50) oznacza, że czytana jest dana a mająca wartość 50
w(a,20) oznacza, że danej a jest przypisywana wartość 20
Po operacji T1 : c wystąpiła awaria. Załóżmy, że aktualne wartości danych na dysku są następujące:
a = 50
b = 80 dane niespójne
c = 100
ograniczenie integralnościowe: a + b = 100
Zakładając, że aktualizacja danych na dysku jest realizowana zgodnie ze strategią LRU (wyłącznie), to dane na dysku mogą być niespójne.
Transakcja T2, która została zaakceptowana, nie wprowadziła zmiany do bazy danych - została więc złamana zasada trwałości.
Załóżmy, że strategia zapisu jest następująca: strona jest zapisywana na dysk natychmiast po jej aktualizacji w buforze.
Awaria wystąpiła po wykonaniu T2 : c
a = 20
b = 80 dane niespójne
c = 50
Transakcja T1, która nie została zaakceptowana, wprowadziła zmiany do bazy danych - została więc złamana zasada atomowości.
Transakcja:
Procedura odtwarzania bazy danych (database recovery) po awarii, korzystając z informacji zawartej w rekordach logu i stanu bazy danych przechowywanego na dysku, przeprowadza bazę danych do stanu, który odzwierciedla wszystkie, lub żadną, operacje aktualizacji transakcji aktywnych w momencie wystąpienia awarii.
Procedura odtwarzania jest kompromisem między efektywnością a poprawnością. System musi mieć możliwość odtworzenia (dokończenia) transakcji zaakceptowanych (by zapewnić trwałość) i cofnięcia zmian wprowadzonych przez transakcje nie zaakceptowane (by zapewnić atomowość).
System transakcyjny, inicjowany ponownie po awarii, nie pamięta intencji logiki transakcji, które były aktywne w momencie awarii.
Taki system nazywamy syntaktycznym. Pamięta on tylko co dana transakcja zrobiła, nic nie wie jednak o tym co dana transakcja chciała zrobić. System semantyczny posiada dodatkową wiedzę o transakcji, np. o ograniczeniach integralnościowych, o typie transakcji. Niestety system taki jest trudny w implementacji, stąd wszystkie systemy komercyjne bazują na modelu syntaktycznym.
Zapewniając poprawność odtwarzania transakcji w naszym przykładzie otrzymamy:
Transakcja T2 zaakceptowana; T1 wycofana. Stąd, stan spójny po awarii:
a = 50
b = 50 dane spójne
c = 50
Jak to się stało, że dane są spójne?
Poniżej przedstawiono tworzenie rekordów logu przez poszczególne operacje realizacji z naszego przykładu:
Operacja |
Rekord logu |
T1 : r(a,50) |
(S,1) - wstaw rekord logu początku transakcji T1, nie wpisuje się rekordów logu dla operacji odczytu, w tym przypadku jest to operacja początku transakcji. |
T1 : w(a,20) |
(W, 1, a, 50, 20) - T1 zapisuje rekord logu dla operacji aktualizacji kolumny a. Wartość 50 (before image), 20 - after image. |
T2 : r(c,100) |
(S, 2) - wstaw rekord logu początku transakcji T2. |
T2 : w(c,50) |
(W, 2, c, 100, 50) - T2 zapisuje rekord logu dla operacji aktualizacji kolumny c. Wartość 100 (before image), 50 - after image. |
T2 : c |
(C, 2) - rekord akceptacji transakcji T2 - (zapisz bufor logu na dysk). |
T1 : r(b, 50) |
|
T1 : w(b, 80) |
(W, 1, b, 50, 80) - T1 zapisuje rekord logu dla operacji aktualizacji kolumny b. Wartość 50 (before image), 80 - after image. |
T1 : c |
(C, 2) - rekord akceptacji transakcji T1 - (zapisz bufor logu na dysk). |
(S, 1) - informacja o tym, że w systemie rozpoczęły się operacje transakcji nr 1 (start); taki rekord logu jest zapisywany w buforze logu w momencie napotkania pierwszej instrukcji danej transakcji. Normalnie operacja odczytu (read) nie powoduje wygenerowania rekordu logu. Tutaj wyjątkowo stało się inaczej, bo operacja ta była pierwszą operacją transakcji nr 1.
(W, 1, a, 50, 20) - informacja o tym, że transakcja nr 1 zapisuje (write) daną a, przy czym poprzednią wartością tej zmiennej było 50, a nową wartością jest 20.
(C, 2) - informacja o potwierdzeniu (commit) transakcji nr 2.
Rekord logu pojawia się również dla operacji insert i delete.
Bufor logu jest zapisywany do pliku logu w dwóch sytuacjach:
Czy informacje zapisane w boforze logu są wystarczające do odtworzenia spójnego stanu bazy danych?
Jednak bufor logu także znajduje się w pamięci operacyjnej, która jest ulotna. Pojawia się więc kolejne pytanie: co się stanie, gdy w wyniku awarii bufor logu, zawierający informacje niezbędne do odtworzenia spójnego stanu bazy danych, nie zostanie zapisany w pliku logu?
Na skutek działania strategii LRU i innych okoliczności mogą wystąpić dwa problemy:
Przykład problemu 1:
Załóżmy, że wystąpiła awaria systemu po wykonaniu operacji T1 : w(b,80) (rekord (W, 1, b, 50, 80) został zapisany do bufora logu).
Bufor logu został zapisany na dysk w momencie akceptacji transakcji T2.
Transakcja T2 została zaakceptowana; transakcja T1 nie.
Po ponownej inicjacji systemu po awarii, operacje aktualizacji wykonane przez transakcję T1 muszą zostać wycofane!
Właściwy stan spójny bazy danych ma następującą postać:
a = 50
b = 50 dane spójne
c = 50
Procedura odtwarzania musi sobie poradzić z obydwoma przedstawionymi problemami.
Procedura odtwarzania po awarii jest wykonywana w dwóch fazach:
W fazie ROLLBACK, rekordy pliku logu są odczytywane w odwrotnej kolejności (od końca). W fazie tej procedura odtwarzania wykonuje operacje UNDO wszystkich operacji aktualizacji transakcji, które nie zostały zaakceptowane.
UNDO polega na wczytaniu do buforu danej strony, „odkręceniu” jej aktualizacji i zapisaniu strony na dysk. Poprzednia wartość danej jest pobierana z rekordu logu.
W fazie tej tworzymy także listę transakcji zaakceptowanych. Lista ta jest potrzebna w fazie następnej.
W fazie ROLL FORWARD, rekordy pliku logu są odczytywane w oryginalnej kolejności (od początku). W fazie tej procedura odtwarzania wykonuje operacje REDO wszystkich operacji aktualizacji transakcji, które zostały zaakceptowane.
REDO polega na wczytaniu do buforu danej strony, powtórzeniu jej aktualizacji i zapisaniu strony na dysk. Nowa wartość danej jest pobierana z rekordu logu.
Rekord logu |
Faza ROLLBACK |
1. (C, 2) |
Wstaw T2 do listy transakcji zaakceptowanych. |
2. (W, 2, c, 100, 50) |
T2 na liście transakcji zaakceptowanych - nie rób nic. |
3. (S, 2) |
Transakcja T2 pasywna. |
4. (W, 1, a, 50, 20) |
T1 nie należy do listy transakcji zaakceptowanych. Wykonaj UNDO operacji aktualizacji - dana a przyjmuje wartość 50. |
5. (S, 1) |
Transakcja T1 pasywna. Ponieważ wszystkie transakcje są pasywne, zakończ fazę ROLLBACK. |
Rekord logu |
Faza ROLL FORWARD |
6. (S, 1) |
Brak akcji. |
7. (W, 1, a, 50, 20) |
T1 nie należy do listy transakcji zaakceptowanych - nie rób nic. |
8. (S, 2) |
Brak akcji. |
9. (W, 2, c, 100, 50) |
Transakcja T2 jest na liście transakcji zaakceptowanych. Wykonaj REDO operacji aktualizacji - dana c przyjmuje wartość 50. |
10. (C, 2) |
Brak akcji. |
11. |
Zakończyliśmy przeglądanie pliku logu - zakończ procedurę odtwarzania. |
W jaki sposób możemy zapewnić, że wszystkie rekordy logu konieczne do zapewnienia poprawności procedury odtwarzania zostaną zapisane na dysku?
Poprawność procedur ROLLBACK i ROLL FORWARD:
a) ROLL FORWARD - operacje REDO
Transakcja nie jest zaakceptowana jeżeli nie zostanie zapisany bufor logu. Jeżeli bufor logu zostanie zapisany, to wszystkie rekordy logu, zapisywane do bufora sekwencyjnie, znajdą się na dysku co gwarantuje poprawność realizacji procedury ROLL FORWARD.
b) ROLLBACK - operacje UNDO
Musimy zagwarantować, że wszystkie aktualizacje wprowadzone przez nie zaakceptowane transakcje zostaną cofnięte. Nie zagwarantowaliśmy uprzednio, że strony zmodyfikowane przez nie zaakceptowane transakcje nie zostaną zapisane na dysku (np. przez LRU). Czy może to stwarzać problemy przy odtwarzaniu? TAK.
r1: T1 : r(a,50) T1 : w(a,20) T2 : r(c,100) T2 : w(c,50) T2 : c T1 : r(b,50) T1 : w(b,80) T1 : c .........
Rozwiązanie A: zawiesić działanie procedury LRU.
Wszystkie brudne strony pozostają w buforze do momentu akceptacji transakcji - procedura UNDO nie jest wówczas potrzebna.
Rozwiązanie B: zmodyfikować LRU.
Rozwiązaniem jest technika WAL (write ahead log).
Technikę WAL można w skrócie określić stwierdzeniem: zanim zapiszesz coś na dysk najpierw zapisz na dysk bufor logu.
System bazy danych utrzymuje specjalny licznik, który generuje rosnącą sekwencję tzw. log sequence number (LSN). LSN jest liczbą całkowitą, przypisywaną do każdego rekordu logu zapisywanego do bufora logu. SBD przechowuje również najmniejszą wartość LSN strony, od czasu ostatniego zapisu bufora na dysk. Oznaczamy ją LSN_BUFFMIN. Jest to unikalna liczba dla całego systemu. Ponadto, dla każdej strony w buforze danych, system pamięta wartość ostatniej LSN operacji, która aktualizowała daną na tej stronie. Oznaczamy ją przez LSN_PGMAX.
Reguła modyfikacji LRU jest następująca. Dana strona w buforze może zostać zapisana na dysk (zgodnie z LRU), wtedy i tylko wtedy gdy jej LSN_PGMAX < LSN_BUFFMIN.
Poniższy rysunek przedstawia sytuację, kiedy LSN_PGMAX = 8 a LSN_BUFFMIN = 11, więc strona może zostać zapisana na dysk.
Gdyby jednak, dana x została zmodyfikowana przez operację, której rekord logu miałby LSN = 12, to wtedy nie został by spełniony warunek, że LSN_PGMAX < LSN_BUFFMIN i trzeba by było poszukać innej strony.
Reguła ta gwarantuje, że dana strona nie zostanie zapisana na dysku, jeżeli wcześniej nie zostanie zapisany na dysku odpowiedni rekord logu.
Plik logu jest plikiem sekwencyjnym. Jeśli plik taki był tworzony przez kilkanaście godzin, to może on być bardzo długi. Pojawia się więc pytanie:
Do jakiego stanu należy się cofnąć wykonując procedurę ROLLBACK?
Także: od którego stanu powinna startować procedura ROLL FORWARD?
Problem:
Punkt kontrolny (checkpoint) - nowy punkt na osi czasu, od którego i do którego są realizowane procedury ROLLBACK i ROLL FORWARD.
Punkty kontrolne są numerowane kolejnymi liczbami całkowitymi.
Trzy podejścia do tworzenia punktów kontrolnych w systemie bazy danych:
Podejścia te są podejściami od najprostszego do najbardziej skomplikowanego.
Po uruchomieniu procedury tworzenia punktu kontrolnego wykonywane są następujące kroki:
Procedura tworzenia akceptacyjnie spójnego punktu kontrolnego przypomina procedurę zamknięcia systemu i wymaga zatrzymania bieżącego przetwarzania transakcji.
Przykład:
rozmiar buforów - 200 MB
rozmiar strony - 4 KB
50 000 stron - niech połowa z nich jest brudna
czas zapisu strony - 25 ms
czas tworzenia punktu kontrolnego - 625 s
Jak widać główną wadą takiego podejścia jest długi czas tworzenia punktu kontrolnego.
Transakcje pozostają aktywne w trakcie realizacji procedury tworzenia punktu kontrolnego. Brudne strony w buforze oraz bufor logu zostają zapisane na dysku.
Bufor = pamięć podręczna dysku ⇒ nazwa punktu kontrolnego
W trakcie tworzenia punktu kontrolnego, wszystkie aktywne transakcje zostają zawieszone (zawieszone zostaje wykonywanie ich operacji, w szczególności, operacji I/O). Zysk - nie jest konieczne oczekiwanie na zakończenie długoterminowych transakcji.
Jednym słowem podejście jest tu bardzo podobne jak przy tworzeniu punktu kontrolnego akceptacyjnie spójnego. Podstawową różnicą jest to, że nie czekamy na zakończenie aktywnych transakcji nie pozwalając im inicjować żadnych nowych operacji, w szczególności operacji wejścia/wyjścia.
Po uruchomieniu procedury tworzenia punktu kontrolnego wykonywane są następujące kroki:
Procedura odtwarzania z użyciem punktu kontrolnego spójnego z pamięcią podręczną.
Dana jest następująca realizacja:
r1: T1 : r(a,10) T1 : w(a,1) T1 : c T2 : r(a,1) T3 : r(b,2) T2 : w(a,3) T4 : r(c,5) CKPT
T3 : w(b,4) T3 : c T4 : r(b,4) T4 : w(c,6) T4 : c awaria
Sekwencja rekordów logu dla powyższej realizacji:
(S, 1)
(W, 1, a, 10, 1)
(C, 1)
(S, 2)
(S, 3)
(W, 2, a, 1, 3)
(S, 4)
(CKPT, (List = T2, T3, T4))
(W, 3, b, 2, 4)
(C, 3)
(W, 4, c, 5, 6)
(C, 4)
awaria
Po utworzeniu punktu kontrolnego, następujące wartości danych zostaną zapisane na dysku:
a = 3
b = 2
c = 5
Załóżmy, że wynik pozostałych operacji aktualizacji nie został zapisany na dysku, dane nie zostały więc zmienione.
Rekord logu |
Faza ROLLBACK |
1. (C, 3) |
Akceptacja transakcji T3. T3 na liście transakcji aktywnych. |
2. (W, 3, b, 2, 4) |
Transakcja zaakceptowana; czekaj na procedurę ROLL FORWARD. |
3. (CKPT, (List = T1, T2, T3)) |
Transakcje aktywne T2 i T4 nie zostały zaakceptowane. |
4. (S., 4)) |
Usuń T4 z listy aktywnych transakcji. |
5. (W, 2, a, 1, 3) |
T2 nie zaakceptowana; wykonaj UNDO; a=1. |
6. (S, 3) |
Transakcja zaakceptowana. |
7. (S, 2) |
Usuń T2 z listy aktywnych transakcji; lista aktywnych transakcji pusta - stop ROLLBACK. |
Zauważmy, że odczytując rekord CKPT w pliku logu system dysponuje listą transakcji aktywnych w momencie tworzenia punktu kontrolnego. Usuwając z niej transakcje zaakceptowane otrzymujemy listę transakcji, których operacje muszą zostać cofnięte (UNDO). Procedura ROLLBACK jest wykonywana tak długo, aż zostaną wycofane wszystkie takie operacje.
Cofamy się więc tak daleko, aż napotkamy rekord (S, n) dla każdej aktywnej transakcji Tn.
Rekord logu |
Faza ROLL FORWARD |
8. (CKPT, (List = T1, T2, T3)) |
Przeskocz w pliku logu do tego rekordu. Transakcja T3 zaakceptowana. |
9. (W, 3, b, 2, 4) |
ROLL FORWARD; b=4. |
10. (C, 3) |
Ostatni rekord logu. Koniec procedury ROLL FORWARD. |
Celem procedury ROLL FORWARD jest wykonanie operacji REDO dla wszystkich operacji należących do zaakceptowanych transakcji, których aktualizacje mogły nie zostać zapisane na dysku. Procedura ROLL FORWARD może rozpocząć swoje działanie zaczynając od znacznika CKPT, ponieważ wiemy z konstrukcji punktu kontrolnego, że wszystkie wcześniejsze aktualizacje musiały zostać zapisane na dysku.
Zauważmy, że w chwili awarii wartości danych na dysku były następujące:
a = 3
b = 2
c = 5
Po zakończeniu procedury odtwarzania wartości danych będą następujące:
a = 1 (ze względu na krok 5)
b = 2 (ze względu na krok 9)
c = 5
Wynika to z faktu, że transakcje T1 i T3 zostały zaakceptowane; natomiast transakcje T2 i T4 musza zostać wycofane.
Celem tego podejścia jest zredukowanie do minimum czasu potrzebnego na utworzenie punktu kontrolnego. Ponieważ czas utworzenia punktu kontrolnego jest zdeterminowany głównie przez czas zapisu brudnych stron na dysku, w tym podejściu główny nacisk jest położony na minimalizację czasu zapisu brudnych stron.
Procedura odtwarzania z rozmytym punktem kontrolnym wykorzystuje dwa ostatnio utworzone punkty kontrolne. Idea jest następująca. W momencie tworzenia punktu kontrolnego CKPTN system zaznacza zbiór wszystkich brudnych stron, które zebrały się w buforze od momentu utworzenia punktu kontrolnego CKPTN-1. Zakładamy, że strony te zostaną zapisane na dysku do momentu tworzenia następnego punktu kontrolnego - CKPTN+1. Pomiędzy utworzeniem kolejnych punktów kontrolnych jest dostatecznie dużo czasu na to, aby zapisać te brudne strony na dysku. Reszta stron zostanie zapisana w momencie tworzenia kolejnego punktu kontrolnego. Reasumując, wszystkie strony, które były brudne w momencie tworzenia punktu kontrolnego CKPTN-1 zostaną ostatecznie zapisane na dysku w chwili tworzenia kolejnego punktu kontrolnego CKPTN.
Rozmyty punkt kontrolny nie jest więc punktem na osi czasu.
Wprowadzenie rozmytego punktu kontrolnego wymaga zmodyfikowania procedury odtwarzania przedstawionej uprzednio dla punktu kontrolnego spójnego z pamięcią podręczną. Procedura ROLL FORWARD rozpoczyna swoje działanie od znacznika CKPTN-1, jeżeli ostatnio utworzonym punktem kontrolnym był punkt CKPTN.
Po uruchomieniu procedury tworzenia punktu kontrolnego CKPTN są wykonywane następujące kroki:
Dodatkowe wykorzystanie logu:
Log jest plikiem sekwencyjnym. Każdy zapis, wprowadzenie lub usunięcie obiektu transakcyjnego generuje dostęp do logu. Bardzo łatwo może się okazać, że log może stanowić wąskie gardło. Aby temu przeciwdziałać w systemie znajduje się kilka buforów logu.
Log jest temporalną bazą danych. Log przechowuje kompletną historię zmian wszystkich obiektów. Początkowo był używany wyłącznie dla odtwarzania transakcji. Obecnie jego znaczenie jest szersze. Umożliwia tzw. time-domain addressing of objects.
W systemie jednowersyjnym każda dana to jakaś nazwa plus wartość. Jednak system taki charakteryzuje się bardzo małym stopniem współbieżności. Powstały więc systemy wielowersyjne oparte o koncepcję Reeda. Według tej koncepcji, dana to nazwa i sekwencja wersji utworzonych w konkretnych chwilach czasowych. Pojawiła się także nowa koncepcja wielowersyjności (koncepcja Herliby'ego) - zamiast przechowywania sekwencji wersji można przechowywać początkową wersję danej oraz sekwencję operacji, które tworzyły wersje kolejne. Operacje takie są zapisywane w pliku logu. Na podstawie początkowej wersji danej oraz zapamiętanych operacji można odtworzyć dowolną wersję danej. Podejście to nie zwiększa stopnia współbieżności.
Log jest również używany dla analizy efektywności (performance analisys) i naliczania kosztów (accounting) oraz określania wąskich gardeł w systemie.
Log Manager zapewnia interfejs do tablicy logu (log table) zawierającej rekordy logu. Każdy rekord posiada nagłówek, zawierający nazwę RM i identyfikator transakcji. Każdy rekord logu posiada unikalny klucz - log sequence number (LSN).
Związki Log Manager'a z innymi usługami
Log Manager odwzorowuje tablicę logu na rosnący zbiór plików sekwencyjnych systemu operacyjnego.
Po co Log Manager:
Proste systemy posiadają tylko jedną tablicę logu. Systemy rozproszone mogą posiadać jedną lub więcej tablic na pojedynczym stanowisku. Powodem utrzymywania większej liczby logów są względy efektywnościowe i autonomia stanowisk. Log może być wąskim gardłem. Rozwiązaniem tego problemu może być utrzymywanie wielu logów dla wielu obiektów.
Niektórzy zarządcy zasobów, w pewnych sytuacjach, trzymają własną tablicę logu.
Odwzorowanie tablicy logu na pliki
Log jest implementowany przy użyciu plików sekwencyjnych. Ostatnio wygenerowane pliki (4 lub 5) są dostępne on-line i wypełniane jeden po drugim. Zwyczajowo, pliki są duplikowane, aby pojedyncza awaria pamięci nie prowadziła do awarii logu.
Pliki logu stosują standardowe nazwy plików zakończonych wzorcem LOGA00000000 i LOGB00000000. Log Manager przechowuje tylko jeden rekord do opisu logu.
struct log_files
{
filename a_prefix; // katalog dla "a" log file
filename b_prefix; // katalog dla "b" log file
long index; // indeks bieżącego pliku
};
Jest to podstawowa informacja przechowywana w tzw. kotwicy logu (log anchor). Kotwica logu jest przechowywana w pamięci operacyjnej i zapisana co najmniej dwa razy na dysku.
Każdy rekord logu posiada unikalny identyfikator nazywany log sequence number (LSN). Liczba ta mogłaby być wykorzystana np. jako indeks do pliku logu. Stąd LSN składa się z numeru pliku i offsetu rekordu w ramach tego pliku. Definicja LSN:
typedef struct
{
long file; // number of log file in log directory
logn rba ; // relative byte address
} LSN;
LSN Null_SW = (0,0); // null LSN is used to end pointer chains
Jest to 8-bajtowa liczba całkowita. LSNs rosną monotonicznie, tzn. jeżeli rekord logu A został utworzony po rekordzie logu B, to LSN(A) > LSN(B).
Dany jest LSN rekordu. Lokalizacja rekordu jest realizowana zgodnie z następującym schematem. lsn.file określa record's file index (NNN), który implikuje nazwy dwóch plików a_prefix.logaNNN i b_prefix.logbNNN. Poszukiwany rekord startuje od numeru lsn.rba.
Gdyby powszechnie zaakceptowano standardy XA i XA+, to można by kupić sam moduł Transaction Manager i komunikować się zdalnie z pozostałymi modułami.
Transakcja jest rozproszona, pojawiają się różne problemy. Kto i gdzie ma tworzyć log? Log jest najczęściej tworzony w dwóch miejscach, lokalnie w Log Manager oraz tam, gdzie realizowano operacje tej transakcji. Trzeba także zmodyfikować strukturę rekordu logu - każdy rekord musi posiadać nagłówek będący identyfikatorem modułu Resource Manager, którego dotyczyła operacja generująca rekord.
Pośrednia postać zapytania - zapytanie w postaci algebry relacji.
Optymalizator próbuje znaleźć najlepszy plan wykonania zapytania.
Plan wykonania zapytania dany jest najczęściej w postaci grafu, w którym wierzchołki są operacjami, a łuki przedstawiają kolejność wykonywania operacji oraz dane przesyłane między operacjami.
Optymalizacja zapytań polega na znalezieniu optymalnego stanu w przestrzeni stanów zawierającej wszystkie możliwe plany wykonania danego zapytania. Stan optymalny jest to stan o najmniejszej wartości funkcji kosztu.
Dla danego zapytania Q poszukujemy planu zapytania (query execution plan) QEP(Q), który będzie się charakteryzował najmniejszym kosztem, czyli będzie minimalny z punktu widzenia pewnej funkcji kosztu. Planów wykonania zapytania Q może być wiele, więc rozpatrujemy przestrzeń wszystkich możliwych planów EQ i staramy się znaleźć plan optymalny.
Optymalizator zapytań jest charakteryzowany przez:
musimy umieć wygenerować przestrzeń wszystkich możliwych stanów - korzystamy z reguł transformacji (np. zmiana metody, zmiana argumentów wewnątrz metody),
przeszukiwanie przestrzeni; gdy przestrzeń jest mała, to każdemu planowi można przypisać koszt i wybrać plan optymalny; gdy przestrzeń jest mała, to można nie być w stanie przeszukać jej całej; można przeanalizować co najwyżej tylko podzbiór przestrzeni (które stany przejrzeć, a które nie?, chcemy, by podzbiór ten zawierał interesujące plany),
z każdym planem jest związana wartość funkcji kosztu, która zależy od: kosztu dostępu do dysku, kosztu przetwarzania, kosztu komunikacji (w środowisku rozproszonym).
Poniższy przykład uzasadnia potrzebę optymalizacji.
Przykład:
SELECT imię, nazwisko, adres
FROM osoby
WHERE płeć ='M' AND dochody>2500000000;
Plany i koszty wykonania:
1. koszt = N/2 + 1
2. koszt = 2 + 1
Optymalizacja jest oparta na tzw. współczynniku selektywności (selectivity). Mówi on jaki jest stosunek liczby różnych wartości atrybutu do liczby wszystkich wartości (w ogólności - do liczby krotek relacji). System oszacowując koszt wykonania zapytania bierze pod uwagę obecność indeksów, a jeśli indeksy są założone, to bierze pod uwagę ich wysokość. Preferowane będą indeksy o mniejszej wysokości.
Idea współczynnika selektywności opiera się na dwóch założeniach:
Np. mamy relację składającą się 2000 krotek i mającą atrybut Miasto o liczności 50 (zbiór 50 miast). Optymalizator opierając się na założenia pierwszym dojdzie do wniosku, że selektywność atrybutu Miasto wynosi 1/50, więc operacja selekcji najprawdopodobniej zwróci 2000/40 = 40 krotek. Ponieważ najczęściej mamy do czynienia z normalnym rozkładem wartości atrybutów toteż założenie pierwsze jest ostro krytykowane.
a) regułowe
Podajemy pewne reguły, np. „najpierw obsługuj operacje binarne, potem operacje połączenia, a na końcu grupowanie”. Następnie, w oparciu o te reguły, na podstawie struktury (składni) zapytania generowany jest jeden plan wykonania zapytania. Główną wadą tego podejścia jest to, że wygenerowany plan silnie zależy od składni zapytania.
b) kosztowe
Idea: generujemy wszystkie możliwe plany, dla każdego obliczamy koszt i wybieramy plan o najmniejszym koszcie.
Założenia: istnieje możliwość wygenerowania wszystkich możliwych planów (w miarę sensownych) oraz dla każdego planu istnieje możliwość sensownego wyznaczenia (oszacowania) kosztu jego wykonania. W praktyce założenia te mogą być trudne do spełnienia, np. gdy przestrzeń stanów jest bardzo duża. Poza tym błędy w oszacowaniu kosztu mogą okazać się drogie.
a) dokładne (wyczerpujące - exhausitive)
Generowane i przeszukiwane są wszystkie plany. Dla dużych zapytań algorytm ten jest nie do przyjęcia ze względu na długi czas optymalizacji. Algorytm ten jest więc nieskalowalny.
b) heurystyczne
Generowany jest tylko jeden plan.
c) kombinatoryczne
Zakładamy, że przestrzeń wszystkich możliwych planów jest tak ogromna, że nie jesteśmy w stanie wygenerować wszystkich planów. Przeglądamy więc tylko podzbiór przestrzeni planów i wybieramy najlepszy plan z tego zbioru (klasyczne metody optymalizacji kombinatorycznej). Zakłada się, że algorytm taki powinien być skalowalny.
a) statyczne
Faza optymalizacji w całości przypada przed fazą wykonania zapytania. Generowany jest jeden plan, według którego przebiegnie faza wykonania. Może się tu zdarzyć, że w wyniku błędnego oszacowania kosztu tego planu, faktycznie zostanie wykonany plan o znacznie większym koszcie - nic tu jednak nie można na to poradzić. Mimo tej poważnej wady podejście to jest stosowane w większości systemów komercyjnych.
b) dynamiczne
W fazie optymalizacji tworzony jest wstępny plan. Później w czasie wykonywania zapytania, po wykonaniu danej operacji, sprawdza się o ile koszt wykonania tej operacji różni się od kosztu przewidywanego. Jeżeli różnica jest mała, to kontynuuje się wykonanie zapytania według założonego planu. Jeśli różnica ta jest duża, to tworzy się nowy plan i wykonuje go od początku. Zapobiega to propagacji błędu oszacowania kosztu wykonania planu.
c) hybrydowe (parametryczne)
W fazie optymalizacji generuje się kilka planów. W fazie wykonywania zapytania, w razie dużych błędów oszacowania, następuje dynamiczne przełączanie między planami.
a) ziarnem jest pojedyncze zapytanie
Każde zapytanie jest optymalizowane niezależnie od innych. Podejście stosowane w większości systemów komercyjnych.
b) ziarnem jest zbiór zapytań
Mamy zbiór zapytań, które w swej strukturze mają fragmenty, które z punktu wykonania można uznać za identyczne. Po co optymalizować te fragmenty osobno dla każdego zapytania, skoro można taki fragment zoptymalizować tylko raz, a wszystkie zapytania skorzystają z wyniku optymalizacji. Wystarczy następnie dokonać optymalizacji specyficznych operacji każdego zapytania.
Optymalizacja taka może okazać się bardzo efektywna w systemach OLAP, w których zapytania są bardzo skomplikowane i silnie skorelowane.
(OP1) σIdPrac=120(PRACOWNICY) Operacja ta mówi: „znajdź pracownika, którego IdPrac wynosi 120”.
(OP2) σpłaca>7500(PRACOWNICY)
(OP3) σpłeć='K' AND płaca>5000(PRACOWNICY)
(OP4) σprzepracował>200 AND IdProj=15(UCZESTNICZY)
Operacja selekcji sprowadza się do przeszukiwania rekordów zawartych w blokach dyskowych pliku relacji.
Operacje przeszukiwania zbioru rekordów
S1. Przeszukiwanie liniowe: Odczytaj wszystkie rekordy pliku i sprawdź, czy wartości atrybutów spełniają warunek zapytania.
Procedura ta jest stosowana w przypadku plików nieuporządkowanych.
S2. Połowienie binarne: Metodą połowienia binarnego znajdź pierwszy rekord, który spełnia warunek zapytania. Następnie odczytaj kolejne rekordy spełniające warunek zapytania.
Procedura ta jest stosowana w przypadku plików uporządkowanych, ale na których nie założono indeksów.
S3. Zastosowanie indeksu drugorzędnego (B+-drzewo): Wyznacz identyfikator (lub zbiór identyfikatorów) rekordów spełniających warunek zapytania.
S4. Zastosowanie indeksu zgrupowanego (B+-drzewo): Wyznacz identyfikator (lub zbiór identyfikatorów) rekordów spełniających warunek zapytania.
S5. Zastosowanie indeksu podstawowego (B+-drzewo): Wyznacz identyfikator (lub zbiór identyfikatorów) rekordów spełniających warunek zapytania.
S6. Zastosowanie funkcji mieszającej: Wyznacz wartość identyfikatora rekordu.
Procedura ta wykorzystuje tzw. plik haszowy, w którym rekordy są rozmieszczane w blokach dyskowych zgodnie z pewną funkcją haszującą. Funkcja haszująca jest zdefiniowana na określonym atrybucie relacji i zwraca adres rekordu. Teoretycznie zysk jest taki, że dla określonej wartości atrybutu bezpośrednio jest wyznaczany adres bloku, w którym znajduje się szukany rekord.
W praktyce jednak istnieje problem kolizji, który może być rozwiązywany przez różne mechanizmy:
S7. Zastosowanie identyfikatora rekordu: Odczytaj rekord o danym identyfikatorze.
System, aby przyspieszyć operację przeszukiwania, uruchamia odpowiednią procedurę przeszukiwania w zależności od informacji jakie posiada nt. relacji i pliku dyskowego, w którym jest zapamiętana. Np. gdy system wie, że plik jest uporządkowany, to uruchomi operację S1, a jeśli na relacji założono indeks, to uruchomi operację stosującą odpowiedni indeks.
Złożone warunki zapytania
a) Koniunkcja warunków
Sx. Przeglądanie liniowe: wczytuj kolejne bloki i przeglądając kolejne rekordy sprawdzaj wszystkie warunki zapytania.
S8. Zagnieżdżanie selekcji: Jeżeli dla jednego z atrybutów dostępna jest jedna z metod dostępu: S2 do S7, to zastosuj ją. Następnie odczytując rekordy wyznaczone przez tę metodę sprawdź, które z nich spełniają pozostałe warunki zapytania.
S9. Indeks lub funkcja mieszająca zdefiniowane na atrybucie złożonym: Jeżeli atrybuty występujące w warunku zapytania są powiązane operatorem równości i istnieje złożony indeks lub funkcja mieszająca zdefiniowane na kombinacji tych atrybutów, to wyznacz identyfikatory rekordów spełniających warunek zapytania.
S10. Iloczyn logiczny zbiorów identyfikatorów: Jeżeli dla kilku atrybutów występujących w złożonym warunku zapytania jest dostępna jedna z metod dostępu: S3 do S6, to wyznacz za ich pomocą zbiory identyfikatorów rekordów spełniających poszczególne, proste warunki zapytania. Następnie wyznacz iloczyn logiczny tych zbiorów.
Procedura ta znajduje zastosowanie z systemach implementujących indeksy bitmapowe. Operacje iloczynu logicznego na ciągach bitów są bardzo szybkie.
b) Suma warunków
(OP5) PRACOWNICY
<IdZesp=IdZesp> ZESPOŁY
(OP6) PRACOWNICY
<Szef=IdPrac> PRACOWNICY
Operacje łączenia rekordów pliku
J1. Algorytm „Nested loop”: Wybierz jeden z plików jako zewnętrzny (outer), a drugi jako wewnętrzny (inner). Odczytuj kolejno wszystkie rekordy pliku zewnętrznego. Dla każdego pobranego rekordu z pliku zewnętrznego odczytuj po kolei wszystkie rekordy pliku wewnętrznego i dla każdych dwóch rekordów sprawdź warunek połączenia.
Bloki relacji outer są wczytywane do pamięci tylko raz, a bloki relacji inner są wczytywane w każdej iteracji pętli zewnętrznej. Jeśli mamy do dyspozycji m bloków pamięci, to m-1 przeznaczamy dla relacji outer, a 1 blok dla relacji inner. Należy się więc starać, aby większa relacja stała się outer a mniejsza stała się inner.
J2. Bezpośrednie ścieżki dostępu dla dopasowania rekordów: Jeżeli dla atrybutu połączeniowego jednego z plików jest dostępna jedna z metod dostępu: S2 do S6, to odczytuj kolejno wszystkie rekordy drugiego z nich. Dla każdego odczytanego rekordu, korzystając z bezpośredniej ścieżki dostępu, znajdź wszystkie rekordy pierwszego pliku o danej wartości atrybutu połączeniowego.
Jest to modyfikacja metody nested loop. Jeżeli jeden pliku ma zdefiniowany indeks na atrybucie połączeniowym, to plik ten wybieramy jako inner.
J3. Algorytm „Sort-merge”: Jeżeli łączone pliki są uporządkowane według wartości atrybutu połączeniowego (lub na atrybutach połączeniowych założony jest indeks drugorzędny), to przeglądając liniowo obydwa pliki dopasowuj rekordy na podstawie wartości atrybutu połączeniowego.
Idea: najpierw obie relacje sortujemy a następnie łączymy. Dzięki wstępnemu posortowaniu warunki zakończenia łączenia są ściśle określone i nie trzeba przeglądać całych relacji. Jeśli mamy m bloków pamięci to każdej z relacji przyznajemy po m/2 bloków.
J4. Algorytm „Hash-join”: Zastosuj funkcję mieszającą na atrybucie połączeniowym dla utworzenia jednego pliku haszowego dla rekordów obydwu łączonych plików.
J5. Plik zgrupowany: Korzystając z jednej z metod dostępu odczytaj połączone fizycznie rekordy.
Zakładamy klaster (plik zgrupowany). Idea: definiujemy bloki, do których wpisujemy rekordy o danej wartości atrybutu połączeniowego. Rekordy te nie muszą pochodzić z jednej relacji. Efekt jest taki, że relacje wydają się być już częściowo połączone, gdyż rekordy, które powinny zostać połączone znajdują się w tych samych blokach dyskowych.
Porównanie kosztów metod połączenia
(mierzone liczbą odczytywanych bloków)
Plik A: rA = 50 rekordów, bA = 10 bloków
Plik B: rB = 5000 rekordów, bB = 2000 bloków
Bufor pamięci: n = 6 bloków
J1. Liczba odczytanych bloków pliku outer = bo
Liczba transferów bloków pliku outer = bo/(n-1)
Liczba odczytanych bloków pliku inner = bi × bo/(n-1)
a) Plik B - outer, plik A - inner
bB + (bA × bB/(n-1)) = 2000 + (10 × 2000/5) = 6000
b) Plik A - outer, plik B - inner
bA + (bB × bA/(n-1)) = 10 + (2000 × 10/5) = 4010
J3. bA + bB = 2010
J2. Współczynnik selektywności połączenia - JSF
Wysokość indeksu na atrybucie połączenia pliku A: xA = 2
Wysokość indeksu na atrybucie połączenia pliku B: xB = 4
a) JSF = 1; bB + (rB × (xA + 1)) = 2000 + (5000 × 3) = 17000
b) JSF = 0.01; bA + (rA × (xB + 1)) = 10 + (50 × 5) = 260
Może być projekcja bez usuwania duplikatów lub z usuwaniem duplikatów. Ta ostatnia charakteryzuje się większym kosztem wykonania, gdyż dochodzi koszt sprawdzania warunku, czy dana wartość już się wcześniej nie pojawiła. Operacja ta zawsze jednak wymaga przejrzenia wszystkich rekordów relacji.
Sortowanie jest wykonywane w klauzulach ORDER BY i GROUP BY oraz w metodzie łączenia sort-merge.
W systemach OLAP podstawową operacją operacją jest GROUP BY.
Etapy optymalizacji:
a) zapytanie w języku wysokiego poziomiu
select *
from pracownicy p, zespoły z
where p.płace>5000 and p.IdZesp = z.IdZesp
b) plan wykonania
hierarchia fizycznych operacji na danych realizująca dane zapytanie
σpłace>5000 PRACOWNICY
<IdZesp=IdZesp> ZESPOŁY
c) graf zapytania
hierarchia odpowiadająca wyrażeniu algebry relacji: relacje są reprezentowane przez liście hierarchii, a operacje algebry przez węzły zewnętrzne
W tym przykładzie zakładamy, że mamy indeks na relacji PŁACA.
Optymalizacja napotyka trzy problemy:
a) left-join deep tree
większość generatorów zapytań dopuszcza wygenerowanie tylko takich planów, które mają postać grafu binarnego, w którym liśćmi są relacje a wierzchołki wewnętrzne to operacje połączenia.
b) bushy tree
Ten model jest mniej popularny, gdyż w nim jednocześnie wykonuje się więcej niż jedną operację połączenia co wymaga materializowania wyników pośrednich (wyników tych operacji połączenia).
* * *
Przykład:
Mamy następujące relacje:
Zadajemy zapytanie, w wyniku którego chcemy otrzymać listę pracowników zatrudnionych w instytutach, które przekroczyły swój budżet (tzn. instytutach, w których suma zarobków pracowników jest większa od ich budżetów).
Możliwy plan wykonania przedstawia się następująco:
Jak widać najpierw jest wykonywana operacja łączenia a potem operacja grupowania. Zauważmy jednak, że płaca pracownika może się często zmieniać i chcąc znaleźć odpowiedź na zapytanie system musi za każdym razem dokonywać połączenia obydwu relacji.
Może by więc zmienić kolejność operacji: najpierw dać grupowanie a dopiero potem łączenie:
Dane otrzymane po operacji zgrupowania będzie można zmaterializować. W przypadku modyfikacji płacy któregoś z pracowników nie trzeba będzie przeprowadzać operacji grupowania lecz wystarczy zmodyfikować wynik zmaterializowany - dokonać modyfikacji w wierszu odpowiadającym instytutowi tego pracownika.
1. Algorytmy dokładne
2. Algorytmy przybliżone
3. Metaheurystyki - algorytmy kombinatoryczne
Złożoność optymalizacji bardzo silnie zależy od zapytań. Jeśli zapytania są złożone (np. w magazynach danych), to przestrzeń planów jest olbrzymia i heurystyki się nie sprawdzają. Lepszym podejściem jest optymalizacja kombinatoryczna - zastosowanie metaheurystyk.
Podstawowe pojęcia optymalizacji kombinatorycznej
Ruchem jest jakakolwiek transformacja wygenerowanego dotąd planu. Ruchy mogą być dwojakiego rodzaju: mogą polegać na zmianie kolejności wykonania operacji połączenia (co ma olbrzymi wpływ na koszt) lub mogą polegać na zmianie samych operacji.
Minimum (lokalne czy globalne) to tylko oszacowanie dokonane przez optymalizator - rzeczywiste wartości są nieznane.
W algorytmach kombinatorycznych najczęściej mówi się o pojęciu r-sąsiedztwa, tzn. dla każdego stanu analizuje się nie wszystkie, lecz tylko r stanów sąsiednich.
Algorytmy kombinatoryczne
a) Iterative Improvement
Wadą tej metody jest to, że łatwo można wpaść w minimum lokalne. Na początku zakładany jest jakiś czas optymalizacji. Gdy czas ten minie, to generowany jest nowy stan początkowy i przeszukiwanie przestrzeni stanów jest kontynuowane. Najprawdopodobniej również to nowe poszukiwanie utnie w jakimś minimum lokalnym. Przeprowadza się więc pewną ilość takich restartów i następnie jako minimum globalne wybiera się najlepsze znalezione minimum lokalne.
b) Simulated Annealing
W metodzie tej możliwe jest przesuwanie się do sąsiadów o wyższym koszcie, co w konsekwencji daje lepsze wyniki niż algorytm a). Jednak również tu istnieje możliwość wpadnięcia w minimum lokalne.
c) Tabu Search
W metodzie tej wybiera się sąsiada o najniższym koszcie. Ponieważ istnieje możliwość „chodzenia w kółko”, więc utrzymuje się listę stanów już odwiedzonych (tzw. listę tabu). Metoda ta ma najlepsze własności i bardzo szybko znajduje zadawalające rozwiązanie.
FK = 0.8 × liczba operacji dyskowych + 0.2 × czas procesora
Składniki funkcji kosztu:
Informacje z katalogu (z przechowywanych statystyk) używane w funkcji kosztu:
System Oracle nie pielęgnuje statystyk on-line. Konieczne jest zmuszanie go do wyliczania statystyk przy pomocy odpowiednich zapytań, np.:
ANALYZE TABLE konta COMPUTE STATISTIC;
ANALYZE INDEX konta_indeks ESTIMATE SAMPLE 5 PERCENT;
ANALYZE CLUSTER polisy ESTIMATE SAMPLE 1000 ROWS;
(rozdział w fazie opracowywania, gdyż nie został do końca omówiony na wykładzie)
W celu opisania systemów heterogenicznych posłużmy się przykładem. Mamy system heterogeniczny, w skład którego wchodzą trzy stanowiska (systemy): S1, S2 i S3. Użytkownik pracuje w jednym z nich i zleca transakcję T wymagającą ściągnięcia danych z każdej bazy.
W podejściu sfederowanym, użytkownik musi zlecić szereg transakcji (tu trzy: T1, T2 i T3), z których każda obsłuży inny system. Uzyskane dane użytkownik musi sam zintegrować.
Podejście wielobazowe stwarza iluzję istnienia jednej olbrzymiej bazy danych, a nie zbioru różnych baz danych. Użytkownik kieruje zapytania do warstwy MDBS. Posługuje się on ogólnym językiem zapytań wyszczególniając bazy danych, których zapytanie dotyczy. Transakcja T skierowana do warstwy MDBS sprawia, że warstwa ta sama realizuje transakcje z każdą z baz, następnie integruje dane i przedstawia je użytkownikowi.
Dwa rozwiązania praktyczne:
Relacja r jest sfragmentaryzowana przez podzielenie na minimalny zbiór rozłącznych podrelacji (fragmentów) r1, r2, …, rm. Podrelacje r1, r2, …, rm zawierają dostateczną informację umożliwiającą odtworzenie oryginalnej relacji r.
Fragmentacja pozioma - podział rekordów (krotek) relacji r na podzbiory. Fragment ri jest wynikiem selekcji krotek na relacji r według predykatu P1. Odtworzenie relacji r uzyskujemy sumując wszystkie fragmenty.
Wynika ona z wniosku, że większość referencji ma charakter lokalny, np. dane o pracowniku Wydziału Elektrycznego są najczęściej potrzebne sekretariatowi WE, stąd dane te powinny się znajdować na tymże wydziale.
Fragmentacja pionowa - podział atrybutów relacji r na grupy. Najprostszą formą fragmentacji pionowej jest dekompozycja. Unikalny identyfikator rekordu należy do każdego fragmentu. Odtworzenie relacji r uzyskujemy łącząc (join) wszystkie fragmenty.
Wynika ona ze sposobu przetwarzania. Rozdzielamy atrybuty relacji, przy czym do każdej z wydzielonych grup dokładamy unikalny klucz, by móc potem wykonać operację połączenia.
Fragmentacja mieszana
A1 |
A2 |
A3 |
A4 |
A5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A1 |
A2 |
A3 |
A4 |
A5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Reguły fragmentacji:
where instytut = `Instytut_Informatyki'
and typ = `pracownik_dydaktyczny';
Klasyfikacja SRBD:
Współczynnik koszt/zysk replikacji i rozproszenia danych można ocenić w kategoriach kosztu pamiętania danych, kosztu komunikacji i dostępności danych.
Zakładamy dostępność następującej wiedzy na temat systemu aplikacji i konfiguracji systemu rozproszonego:
Kryteria oceny schematu alokacji:
C = CCOMM + CPROC + CSTOR
CCOMM - koszt komunikacji
CPROC - koszt przetwarzania
CSTOR - koszt przechowywania
Notacja:
i jest indeksem fragmentu
j jest indeksem stanowiska
k jest indeksem aplikacji
fkj jest częstością k-tej aplikacji na j-tym stanowisku
rki jest liczbą referencji odczytu k-tej aplikacji do i-tego fragmentu
uki jest liczbą referencji aktualizacji k-tej aplikacji do i-tego fragmentu
nki = rki + uki
Algorytm określa stanowisko, na którym opłaca się umieścić fragment danych, opierając się na kryterium maksymalnego zysku rozumianego jako suma kosztów odczytu i aktualizacji danych.
Relację Ri pamiętamy na stanowisku Sj, na którym liczba referencji odczytu i zapisu do Ri jest największa:
Przykład:
Mamy trzy fragmenty: R1, R2 i R3. Każdy fragment jest relacją. Podane są średnie czasy I/O dostępu do dysku ze stanowiska lokalnego i zdalnego.
Parametry systemowe (jest to coś jakby opis konfiguracji systemu):
Relacja |
Rozmiar |
Średni lokalny czas zapytania (aktualizacji) [ms] |
Średni zdalny czas zapytania (aktualizacji) [ms] |
R1 |
300 KB |
100 (150) |
500 (600) |
R2 |
500 KB |
150 (200) |
650 (700) |
R3 |
1 MB |
200 (250) |
1000 (1100) |
Transakcja |
Stanowisko |
Częstość |
Liczba dostępów |
T1 |
S1, S4, S5 |
1 |
4 do R1 (3 r, 1 w) 2 do R2 (2 r) |
T2 |
S2, S4 |
2 |
2 do R1 (2 r) 4 do R3 (3 r, 1 w) |
T3 |
S3, S5 |
3 |
4 do R2 (3 r, 1 w) 2 do R3 (2 r) |
Częstość jest podawana w liczbie referencji na np. godzinę lub dzień.
Obliczanie referencji lokalnych (umieszczamy każdą relację na każdym stanowisku i obliczamy koszty):
Relacja |
Stanowisko |
Transakcja T1 |
Transakcja T2 |
Transakcja T3 |
Suma referencji |
R1 |
S1 |
3 r, 1 w (1) |
0 |
0 |
4 |
|
S2 |
0 |
2 r (2) |
0 |
4 |
|
S3 |
0 |
0 |
0 |
0 |
|
S4 |
3 r, 1 w (1) |
2 r (2) |
0 |
8 (max) * |
|
S5 |
3 r, 1 w (1) |
0 |
0 |
4 |
R2 |
S1 |
2 r (1) |
0 |
0 |
2 |
|
S2 |
0 |
0 |
0 |
0 |
|
S3 |
0 |
0 |
3 r, 1 w (3) |
12 |
|
S4 |
2 r (1) |
0 |
0 |
2 |
|
S5 |
2 r (1) |
0 |
3 r, 1 w (3) |
14 (max) |
R3 |
S1 |
0 |
0 |
0 |
0 |
|
S2 |
0 |
3 r, 1 w (2) |
0 |
8 (max) |
|
S3 |
0 |
0 |
2 r (3) |
6 |
|
S4 |
0 |
3 r, 1 w (2) |
0 |
8 (max) |
|
S5 |
0 |
0 |
2 r (3) |
6 |
* Suma referencji, to suma iloczynów „liczba referencji transakcji razy częstość transakcji”. Stąd, w tym przypadku suma wynosi 8, ponieważ transakcja T1 przeprowadza 4 dostępy z częstością 1, transakcja T2 przeprowadza 2 dostępy z częstością 2, a transakcja T3 nie przeprowadza w ogóle dostępu.
Decyzje:
Zaletą metody „Best Fit” jest obliczeniowa prostota. Wadą jest niedokładność i nieuwzględnianie replikacji.
Algorytm określa wszystkie stanowiska, na których opłaca się umieścić fragment danych, tj. te stanowiska, dla których zysk z umieszczenia fragmentu danych na danym stanowisku jest większy niż koszt przechowywania i aktualizowania tego fragmentu.
Relację Ri pamiętamy na stanowiskach Sj, na których koszt referencji odczytu jest większy niż koszt referencji zapisu relacji Ri z dowolnego stanowiska w systemie.
C - stała określająca stosunek kosztu operacji zapisu do kosztu operacji odczytu.
Relację Ri pamiętamy na stanowiskach Sj, dla których wartość Rij jest dodatnia.
Zysk utworzenia dodatkowej kopii danego fragmentu F na stanowisku Sj jest mierzony jako różnica pomiędzy czasem wykonania zapytania zdalnego (bez replikacji) a czasem wykonania zapytania lokalnego pomnożona przez częstość zapytania do fragmentu F ze stanowiska Sj.
Koszt dodatkowej kopii fragmentu F na stanowisku Sj jest mierzony jako sumaryczny czas wszystkich lokalnych aktualizacji fragmentu F przez transakcje inicjowane na stanowisku Sj plus sumaryczny czas wszystkich zdalnych aktualizacji fragmentu F przez transakcje inicjowane na pozostałych stanowiskach systemu.
Dane początkowe identyczne jak w p.7.4.2.1.
Koszt i zysk każdej relacji dla wszystkich możliwych alokacji
Relacja |
Stanowisko |
Zdalne (lokalne) zapisy |
Liczba zapisów · częstość · czas |
Koszt |
R1 |
S1 |
T1 z S4, S5 (T1 z S1) * |
2·1·600+1·1·150 |
1350 |
|
S2 |
T1 z S1, S4, S5 ** |
3·1·600 |
1800 |
|
S3 |
T1 z S1, S4, S5 |
3·1·600 |
1800 |
|
S4 |
T1 z S1, S5 (T1 z S4) |
2·1·600+1·1·150 |
1350 |
|
S5 |
T1 z S1, S4 (T1 z S5) |
2·1·600+1·1·150 |
1350 |
R2 |
S1 |
T3 z S3, S5 |
2·3·700 |
4200 |
|
S2 |
T3 z S3, S5 |
2·3·700 |
4200 |
|
S3 |
T3 z S5 (T3 z S3) |
1·3·700+1·3·200 |
2700 |
|
S4 |
T3 z S3, S5 |
2·3·700 |
4200 |
|
S5 |
T3 z S3 (T3 z S5) |
1·3·700+1·3·200 |
2700 |
R3 |
S1 |
T2 z S2, S4 |
2·2·1100 |
4400 |
|
S2 |
T2 z S4 (T2 z S2) |
1·2·1100+1·2·250 |
2700 |
|
S3 |
T2 z S2, S4 |
2·2·1100 |
4400 |
|
S4 |
T2 z S2 (T2 z S4) |
1·2·1100+1·2·250 |
2700 |
|
S5 |
T2 z S2, S4 |
2·2·1100 |
4400 |
Do obliczenia kosztu dla danej relacji szukamy transakcji, która wykonuje najwięcej operacji zapisu w tej relacji. Stąd, dla relacji R1 weźmiemy transakcję T1, dla R2 weźmiemy T3, a dla R3 T2.
Jako czas bierzemy średni czas aktualizacji.
* Transakcja T1, zgodnie z założeniami, może być wykonywana na stanowisku S1, S4 lub S5. Zakładamy tu, że relacja R1 zostanie umieszczona na stanowisku S1. W tym przypadku transakcja T1 może się do niej dostać zdalnie ze stanowisk S4 lub S5 albo lokalnie ze stanowiska S1.
** Tu zakładamy, że relacja R1 zostanie umieszczona na stanowisku S2. Ponieważ transakcja T1 nie może być wykonywana na tym stanowisku, więc musi się dostać do relacji zdalnie ze stanowiska S1, S4 lub S5.
Relacja |
Stanowisko |
Zapytanie |
Liczba odczytów · częstość · (czas dost. zdalnego. - czas dost. lokalnego) |
Zysk |
R1 |
S1 |
T1 z S1 * |
3·1·(500-100) ** |
1200 |
|
S2 |
T2 z S2 |
2·2·(500-100) |
1600 |
|
S3 |
brak |
0 |
0 |
|
S4 |
T1, T2 z S4 |
(3·1+2·2)·(500-100) |
2800 |
|
S5 |
T1 z S5 |
3·1·(500-100) |
1200 |
R2 |
S1 |
T1 z S1 |
2·1·(650-150) |
2800 |
|
S2 |
brak |
0 |
0 |
|
S3 |
T3 z S3 |
3·3·(650-150) |
4500 |
|
S4 |
T1 z S4 |
2·1·(650-150) |
1000 |
|
S5 |
T1, T3 z S5 |
(2·1+3·3)·(650-150) |
5500 |
R3 |
S1 |
brak |
0 |
0 |
|
S2 |
T2 z S2 |
3·2·(1000-200) |
4800 |
|
S3 |
T3 z S3 |
2·3·(1000-200) |
4800 |
|
S4 |
T2 z S4 |
3·2·(1000-200) |
4800 |
|
S5 |
T3 z S5 |
2·3·(1000-2000) |
4800 |
Do obliczenia zysku z umieszczenia danej relacji R na danym stanowisku S. szukamy takich transakcji, które odczytują dane z tej relacji a ponadto mogą być wykonywane na tymże stanowisku. W przypadku braku takich transakcji zysk nie jest obliczany.
Jako czas dostępu (zdalnego lub lokalnego) bierzemy średni (zdalny lub lokalny) czas zapytania.
* Umieszczamy relację R1 na stanowisku S1. Ponieważ istnieje transakcja, która odwołuje się do R1 i może być wykonywana na S1, więc obliczamy zysk.
** Zapis „(500-100)” należy rozumieć tak: „gdyby referencja była zdalna, to trwała by 500 ms, ale ponieważ jest lokalna, to trwa 100 ms, więc zyskuje się 400 ms”.
Porównanie kosztów i zysków:
Relacja |
Stanowisko |
Koszt |
Zysk |
R1 |
S1 S2 S3 S4 * S5 |
1300 1800 1800 1350 1350 |
1200 1600 0 2800 1200 |
R2 |
S1 S2 S3 S4 S5 |
4200 4200 2700 4200 2700 |
1000 0 4500 1000 5500 |
R3 |
S1 S2 S3 S4 S5 |
4400 2700 4400 2700 4400 |
0 4800 4800 4800 4800 |
* Półgrubą czcionką zaznaczono wszystkie przypadki, gdzie koszt jest mniejszy od zysku, czyli gdzie opłaca się umieścić daną relację na danym stanowisku.
Decyzje:
Algorytm ten nie był omawiany na wykładzie.
Algorytm PFA stanowi praktyczne rozszerzenie algorytmu ABS. Idea: mierzymy zysk z alokacji nowej kopii fragmentu Ri w terminach zwiększonej niezawodności i dostępności danych.
Niech di oznacza stopień redundancji fragmentu Ri i niech Fi oznacza zysk z pełnej replikacji fragmentu Ri na wszystkich stanowiskach.
Następująca funkcja (di) jest miarą zysku:
(di) = (1 - 21-di) · Fi
Zauważmy, że (1) = 0, (2) = Fi / 2, (3) = 3 · Fi / 4
Stąd, zysk z wprowadzenia nowej kopii Ri na stanowisku Sj jest zdefiniowany następująco:
Ideą indeksowania jest przyspieszenie dostępu do krotek relacji. Przyspieszenie to wynika dwóch rzeczy:
Początkowo były stosowane indeksy jednopoziomowe, jednak dużym problemem była tu pielęgnacja indeksu. Szczególnie kłopotliwe było wstawianie nowych wartości do relacji, co wymuszało rozsuwanie bloków. Aby zmiany miały charakter lokalny i nie propagowały zmian na cały indeks, wprowadzono indeksy wielopoziomowe o strukturze B-drzewa i B+-drzewa. Przeszukiwanie takich indeksów było szybsze. Indeks nie był wypełniony do końca i istniała amortyzacja dla operacji jego modyfikacji; cechą charakterystyczną była także mała propagacja zmian. Indeksy o strukturze B+-drzewa są najczęściej wykorzystywane w systemach OLTP (On-Line Transaction Process).
We współczesnych SZBD wyróżnia się dwa sposoby przetwarzania:
Nie można na jednej bazie danych przeprowadzać obydwu rodzajów przetwarzania. Najczęściej OLAP tworzy się jako sąsiadów OLTP i nazywa się je magazynami danych.
|
OLTP |
OLAP |
Dane |
aktualne, niezagregowane, dynamiczne, rzędu dziesiątek GB |
archiwalne, zagregowane, statyczne, rzędu setek, tysięcy GB |
Transakcje |
wyszukiwanie, aktualizacja, niewielka liczba danych |
analityczne, agregacja, duża liczba danych |
Czas odpowiedzi |
ułamki sekund, sekundy |
sekundy, minuty, dziesiątki minut |
Zawartość relacji |
|
Mapy bitowe |
||||
marka |
typ |
|
coupe |
limuzyna |
sedan |
sport |
Ford |
sedan |
|
0 |
0 |
1 |
0 |
Audi |
coupe |
|
1* |
0 |
0 |
0 |
Ford |
sport |
|
0 |
0 |
0 |
1 |
Volvo |
limuzyna |
|
0 |
1 |
0 |
0 |
Volvo |
sport |
|
0 |
0 |
0 |
1 |
Audi |
sport |
|
0 |
0 |
0 |
1 |
BMW |
sport |
|
0 |
0 |
0 |
1 |
Ford |
sport |
|
0 |
0 |
0 |
1 |
Audi |
sport |
|
0 |
0 |
0 |
1 |
Renault |
limuzyna |
|
0 |
1 |
0 |
0 |
Toyota |
limuzyna |
|
0 |
1 |
0 |
0 |
VW |
sport |
|
0 |
0 |
0 |
1 |
Peugeot |
sedan |
|
0 |
0 |
1 |
0 |
BMW |
sport |
|
0 |
0 |
0 |
1 |
*Ponieważ drugi wiersz relacji ma postać [Audi | coupe], więc w mapie bitowej coupe w drugim wierszu mamy 1.
Z każdą wartością mamy związaną mapę bitową
Mając taką strukturę system może realizować pewne typy zapytań, które nie wymagają odwołania do bazy danych (do relacji). Np. zapytanie „w ilu rekordach mamy Audi?” Odpowiedź na takie pytanie jest realizowana operacjami binarnymi na mapach bitowych (operacji bardzo szybkich), czyli na poziomie indeksu.
select marka from sprzedaż
where typ='sport' or typ='sedan';
sedan |
OR |
sport |
|
|
|
marka |
typ |
1 |
|
0 |
|
1 |
|
Ford |
sedan |
0 |
|
0 |
|
0 |
|
Audi |
coupe |
0 |
|
1 |
|
1 |
|
Ford |
sport |
0 |
|
0 |
|
0 |
|
Volvo |
limuzyna |
0 |
|
1 |
|
1 |
|
Volvo |
sport |
0 |
|
1 |
|
1 |
|
Audi |
sport |
0 |
|
1 |
|
1 |
|
BMW |
sport |
0 |
|
1 |
|
1 |
|
Ford |
sport |
0 |
|
1 |
|
1 |
|
Audi |
sport |
0 |
|
0 |
|
0 |
|
Renault |
limuzyna |
0 |
|
0 |
|
0 |
|
Toyota |
limuzyna |
0 |
|
1 |
|
1 |
|
VW |
sport |
1 |
|
0 |
|
1 |
|
Peugeot |
sedan |
0 |
|
1 |
|
1 |
|
BMW |
sport |
założenia: liczba_krotek = 1 000 000, krotnośćA = 4, adres_rekordu = 4B
indeks bitmapowy na atrybucie A 4 mapy bitowe: 4 (1 000 000 / 8) = 4 125kB = 500kB
indeks B+-drzewo na atrybucie A 1 000 000 4B = 4MB
Indeks bitmapowy jest ciągiem zer i jedynek, więc można zastosować jego kompresję.
założenia: liczba_krotek = 1 000 000, krotnośćA = 64, adres_rekordu = 4B
indeks bitmapowy na atrybucie A 64 mapy bitowe: 64 (1 000 000 / 8) = 64 125kB = 8MB
indeks B+-drzewo na atrybucie A 1 000 000 4B = 4MB
a) Wstawianie krotek
b) Uaktualnianie krotek
c) Usuwanie krotek
Można kasować krotkę przez wstawienie 0 w miejsce 1, jednak lepiej jest wstawić tam specjalny znacznik mówiący, że krotkę usunięto.
Poniżej: mapa bitowa MU jest mapą usuniętych krotek (wartość 0 mówi, że krotkę usunięto)
Zawartość relacji |
|
|
NOT |
|
AND |
|
|
marka |
typ |
|
sport |
|
! sport |
|
MU |
Ford |
sedan |
|
0 |
|
1 |
|
1 |
Audi |
coupe |
|
0 |
|
1 |
|
1 |
|
|
|
0 |
|
1 |
|
0 |
Volvo |
limuzyna |
|
0 |
|
1 |
|
1 |
|
|
|
0 |
|
1 |
|
0 |
Audi |
sport |
|
1 |
|
0 |
|
1 |
BMW |
sport |
|
1 |
|
0 |
|
1 |
Ford |
sport |
|
1 |
|
0 |
|
1 |
Audi |
sport |
|
1 |
|
0 |
|
1 |
Renault |
limuzyna |
|
0 |
|
1 |
|
1 |
Toyota |
limuzyna |
|
0 |
|
1 |
|
1 |
VW |
sport |
|
1 |
|
0 |
|
1 |
Peugeot |
sedan |
|
0 |
|
1 |
|
1 |
BMW |
sport |
|
1 |
|
0 |
|
1 |
select marka from sprzedaż where typ!='sport';
W przypadku indeksu bitmapowego wiadomo, która krotka znajduje się w wyniku, jednak nic nie wiadomo o adresie do rekordu, w którym się ona znajduje. Potrzebny jest więc mechanizm transformacji mapy bitowej na adresy rekordów.
Wykorzystano tu mechanizm podobny do haszowania: pozycja i wartość bezpośrednio wyznaczają numer strony i rekord na stronie. Potrzebna jest jeszcze funkcja, która wyznacza numer bloku fizycznego dla danej strony logicznej.
Idea: mamy dwie relacje (np. marki samochodów i sprzedaż). Zakładamy, że często padają zapytania wymagające połączenia tych relacji. Jak wiadomo, operacja łączenia relacji jest operacją najbardziej kosztowną. Aby zmniejszyć koszt wykonywania tych zapytań tworzy się indeks połączeniowy, który jest modyfikacją B+-drzewa. W każdym liściu, poza wskaźnikiem do bloku danych, pojawiają się dodatkowe wskaźniki do relacji, która może być połączona z relacją, której dotyczy indeks. Dzięki tym dodatkowym wskaźnikom operacja połączenia dwóch relacji zostaje znacznie przyspieszona.
Indeks połączeniowy może być implementowany jako:
|
Oracle |
RedBrick |
Sybase |
Informix |
Indeksy połączeniowe |
|
|
|
|
Indeksy bitmapowe |
|
|
|
|
Bitmapowe indeksy połączeniowe |
|
|
|
|
Kompresja indeksów bitmapowych |
|
|
|
|
STAR Index |
|
|
|
|
select count(*) from bench
where n2=1 and n10=1 and n20=1
select sum(n2), sum(n10), sum(n20) from bench
where n2=1 and n10=1 and n20=1
Operacje agregacji nie wspomagane przez indeks bitmapowy.
select sum(n160) from bench where warunek
Gdy mamy warunek nierównościowy to indeks bitmapowy staje się wysoce nieefektywny (patrz pierwsze trzy ciemne kolumny na powyższym wykresie). Indeks bitmapowy staje się praktycznie nieprzydatnym i zbędnym. Dwie ostatnie ciemne kolumny na powyższym wykresie są niskie, gdyż optymalizator przestał korzystać z indeksu bitmapowego (warunek był mało selektywny i system zdecydował się na full scan).
create bitmap index
create index
Indeksy bitmapowe sprawdzają się w systemach OLAP i tam też są głównie stosowane (np. system RedBrick - system zarządzania magazynami danych).
Sieci komputerowe 1/115
Sieci komputerowe 115/115
Wyszukiwarka
Podobne podstrony:
TWORZENIE STRON
Wykład 3 Prawa i obowiązki stron stosunku pracy Wynagrodzenie
, , , , , 5
5
PHP5 Tworzenie stron WWW cwiczenia praktyczne cwphp5
5
biznes plan (31 stron) (2)
Święta z różnych stron świata KLT (2)
5
Nie kaz mi myslec O zyciowym podejsciu do funkcjonalnosci stron internetowych Wydanie II Edycja kolo
5
5
5
PRS UN str 20 21 i 38 43 nr stron nadrukowane
Rozwiązanie umowy o pracę przez pracownika na mocy porozumienia stron, ADWOKAT DOMOWY, WZORY PISM, K
Jak stworzyć prostą wyszukiwarkę dla własnych stron WWW, PHP Skrypty
Adresy stron www na temat zastosowania komputera w terapii pedagogicznej, edukacja, WODN, komputer w
więcej podobnych podstron