Rozproszone (distributed) systemy baz danych.

Rozproszone b.d. to takie b.d., które są przechowywane w wielu oddalonych od siebie miejscach. Rozmaite komputery sterują dostępem do różnych porcyj danych oraz służą do pośredniczenia pomiędzy b.d. a użytkownikami w wielu miejscach. Czasami te funkcje:

-sterowanie dostępem

-pośredniczenie pomiędzy b.d. a użytkownikiem

są wykonywane przez ten sam komputer.

Komputery w środowisku rozproszonym współpracują w obsłudze b.d. przy pomocy łączy komunikacyjnych. Szybkość transmisji tymi łączami jest znacznie mniejsza niż prędkość odczytu plików z dysku. Zatem transmisja przez łącza komunikacyjne jest „wąskim gardłem” i większość zagadnień dla tych systemów dotyczy sposobów uporania się z tym problemem.

Dla rozpr. b.d. istnieją szczególne metody optymalizacyjne, ponieważ często o czasie odpowiedzi decyduje nie liczba wykonanych obliczeń, lecz ilość przesyłanych danych (pomiędzy komputerami.

Innymi problemami rozpr. b.d są:

-współbieżność transakcyj

-ograniczone połączenie pomiędzy komputerami: wysłanie komunikatu typu „zablokuj jednostkę X dla transakcji T” pochłania dużo czasu (na zestawienie połączenia), a gdy komunikaty są dłuższe (przesyłanie danych) to czasu trzeba jeszcze więcej.

Rozpatrzymy przypadek podziału relacji na fragmenty, które są następnie lokowane w różnych miejscach w rozproszonej b.d. Zakładamy, że:

1. rozproszona b.d. składa się z relacyj logicznych, które faktycznie nie istnieją

2. fragmenty b.d. tworzy się najczęściej za pomocą operatorów sumy lub złączenia naturalnego

3. zapytania do b.d. oraz aktualizacja b.d. realizowane są i odnoszą się do bazy logicznej

4. mówimy także o relacjach fizycznych, które faktycznie istnieją i są fragmentami relacyj logicznych

W dalszych rozważaniach będziemy zakładać, że b.d. rozproszona składa się z pewnej liczby węzłów. Każdy węzeł to komputer ze środkami do przechowywania danych. Każdy węzeł zawiera zazwyczaj system obsługi transakcyj do aktualizacji i przetwarzania zapytań wprowadzonych przez użytkownika oraz system obsługi plików sterujący dostyępem do danych. Możliwe, że jedna z funkcyj jest pominięta (obie funkcje realizuje jeden system). Zakładamy również, że b.d. skłąda się z jednostek - porcyj danych nadających się do indywidualnego blokowania. Pewne jednostki mogą być powielane (pojawiają się w dwóch lub więcej różnych węzłąch). Takie powielenie stosuje się najczęściej, gdy z określonych fragmentów b.d. użytkownicy tylko czytają dane (po to, aby przyspieszyć działania na tych jednostkach). Wówczas jednostka jest dostępna w tym węźle, który czyta. Ponadto nadmiarowe zapamiętywanie danych zmniejsza prawdopodobieństwo ich utraty na skutek awarii. Ceną płaconą za powielanie jest konieczność przesyłania większej liczby komunikatów podczas aktualizacji lub blokowanie jednostki powielonej w więcej niż jednym węźle.

Zakładamy, że między pewnymi lub wszystkimi węzłami są łącza, po których przesyłane są komunikaty i dane. Szybkość przesyłania danych ograniczona jest szybkością ich wysyłania i odbioru oraz szybkością przesyłu. Dalej będziemy rozważać zapytania do b.d. w relacyjnych b.d. rozproszonych. W pewnym sensie zapytania do rozproszonych b.d. w modelu relacyjnym będą dotyczyć relacji a raczej jej fragmentów. Każda relacja wynikowa składa się z fragmentów.

Dalej będziemy rozważać dwie metody składania relacji z fragmentów:

1.Relacja jest złączeniem naturalnym kilku fragmentów (fragmentacja pionowa):

R= R1|x| R2|x| R3|x|...|x|Rn

Jeżeli R to tablica, to Rk reprezentuje pewne jej kolumny -stąd są to fragmenty pionowe

2.Relacja R set sumą kilku fragmentów (fragmentacja pozioma):

R=R1∪ R2∪...∪Rn

Tabela R składa się z fragmentów poziomych. Założenie o rozłączności Ri nie jest konieczne.

Dalej będziemy zakładać, że każda relacja R logiczna w rozproszonej b.d. składa się z z fragmentów (być może z 1 fragmentu), a każdy fragment znajduje się w innym węźle. Fragmenty mogą same być relacjami logicznymi składającymi się z fragmentów itd.

Przykład: Bankowa baza danych:

Naturalne jest, że każdy oddział banku utrzymuje dane o swoich rachunkach i kredytach; korzyść polega na tym, że klienci dokonujący operacji w swoich oddziałach mogą dokonywać transakcyj bez potrzeby wykorzystania łączy.

Mamy relacje logiczne:

-Rachunki(O,R,S) O-oddział, R-rachunek (nr), S-saldo

-Kredyty(O,P,W) P-pożyczka (nr), W-wartość

-Właściciele(R,K) K-ident.klienta

-Dłużnicy(P,K)

-Klienci(K,A) A-Adres klienta

Wydaje się więc, e we wszystkich oddziałach przechowywane są poziome fragmenty powyższych relacyj. Dla pewnych zapytań dobrze byłoby przechowywać relację Klienci w oddziale głównym. Tu klienci są skojarzeni ze swoimi adresami. Załóżmy, ze użytkownik widzi relacje logiczne. Przez zapytanie konstruuje się wyrażenie, którego argumentami są relacje fizyczne.

Rozważmy dalej, ze istnieją 3 oddziały, które oznaczymi 1,2,3. Fragment poziomy danych umieszczonych w oddziale 1 musi spełniać warunek O=1.

Warunek skojarzony z fragmentem poziomym nazywa się dozorem. Taki dozór obowiązuje dla fragmentów Rachunki. Ogólnie: jeśli g jest dozorem fragmentu relacji R, to każde użycie relacji R można zastąpić selekcją σg(R) (selekcja z R pod warunkiem, że g) nie zmieniając wyników wyrażenia. Jeżeli dla zapytania zbudujemy graf wyrażenia, to selekcję taką dla optymalizacji zapytań należałoby przesunąć w dół drzewa. Również inne selekcje można przesunąć w dół drzewa. Wtedy można stwierdzić, czy selekcja zastosowana do R jest sprzeczna z dozorem g. Jeśli selekcje w wyrażeniu i dozór będą sprzeczne, to relację R da się wyeliminować z wyrażenia.

W przykładowej b.d. można np. narzucić dozór: każdy klient oddziału 1 ma rachunek>1000zł. Taki dozór nie pozwala wyrazić faktu, iż fragmenty relacji właściciele w oddziałach 2 i 3 nie zawierają żadnej krotki dla rachunków z oddziału 1. Jest tak, ponieważ O nie jest atrybutem Właściciele; dlatego warunek O=1,2,3 odpowiednie do oddziału nie może być warunkiem dozoru. Aby taki dozór opracować, posłużymy się inną metodą fragmentacji. W nowej metodzie posłużymy się relacją R o schemacie R=ORSK. Tę relację rozłożymy na fragmenty poziome:

R=R1∪R2∪R3, gdzie R1=σO=1(R) ...

Ponadto każda relacja R1, R2, R3 jest podzielona na fragmenty pionowe A1 A2 A3

A1=σO=1(Rachunki) ...

H1=σO=1(Właściciele) ...

Dlatego σO=1(R)= σO=1(A1|x|H1|)

Można zbudować drzewo:

σO=1

σS>1000

∪

σO=1 σO=2 σO=3

|x| |x| |x|

A1 H1 A2 H2 A3 H3

Górną selekcję można przesunąć poniżej ∪, otrzymamy 2 bezsensowne warunki selekcji: (O=2 AND O=1) oraz (O=3 AND O=1). Dlatego drugie i trzecie poddrzewo można usunąć. Należy również usunąć ∪ ponieważ dotyczy ona tylko jednego argumentu. Ponieważ σO=1 jest dozorem A1|x|H1 to można pominąć dozór, gdy skończył oddziaływać na wszystkie inne selekcje. Selekcja σS>1000 przesuwa się w dół do A1, bo H1 nie zależy od S. Drzewo końcowe jest postaci:

|x|

σS>1000 H1

A1

Dlatego otpymalizacja zapytań dla rozproszonych b.d. może być w tym przypadku ograniczona do optymalizacji dla normalnych b.d. o ile zostaną określone warunki dozoru.

Innym problemem rozproszonych b.d. jest aktualizacja relacji (logicznej) R. Aby zaktualizować tę relację np. wstawiając krotkę t, należy dokonać wstawień do pewnych fragmentów R. Algorytm postępowania jest rekurencyjny. Załóżmy, że R=R1|x|R2|x|...|x|Rn

(R składa się z fragmentów pionowych). Żeby zaktualizować R trzeba wstawić t[R1] dla każdego i=1..n. Jeżeli R jest złożona z fragmentów poziomych (R= R1∪R2∪...∪Rn), znajdujemy takie i, że krotka t spełnia dozór relacji Ri, i t wstawiamy do fragmentu Ri. Gdy taki fragment nie istnieje to wstawienie jest niemożliwe. Gdy istnieje, to zaleca się wstawienie krotki do lokalnego fragmentu (w najbliższym węźle) aby oszczędzić na transmisji.Większym problemem jest usuwanie krotki t z relacji R. W przypadku fragmentacji poziomej usuwanie sprowadza się do usunięcia krotki z każdej relacji Ri, w której ona występuje. Jeżeli relacja składa się z fragmentów pionowych. To trudno określić poprawny sposób usuwania krotki. Istnieje rozwiązanie zadowalające, chociaż nie najefektywniejsze. Do każdej krotki wstawianej do R tworzy się jednoznaczny identyfikator krotki (IK), który dopisywany jest do schematu relacji w postaci nowego atrybutu IK, funkcyjnie wyznaczający krotki t, czyli pozostałe atrybuty. Wstawiając krotkę do relacji R system tworzy rzyty t z wartością IK dla wszystkich fragmentów relacji. Przy usuwaniu dla każdej relacji Ri znajdujemy zbiór Si krotek ab1,...bk należących do Ri, takich że a jest składową IK, a b1,...bk będą wartościami składowymi różnych od IK, tworzą nowy rzut krotki t na Ri. Znajdując Si dla każdego Ri dokonujemy złączenia: at=S1|x|S2|x|...|Sn|. Wynikiem będzie zero lub więcej krotek postaci at, gdzie a jest identyfikatorem IK, t-usuwaną krotką. Znając identyfikator krotki z relacji Ri można usunąć at[Ri] dla każdego takiego a oraz i=1..n.

Ważnym problemem jest realizacja łączenia relacyj R i S znajdujących się w w różnych węzłach. Oczywistą metodą jest przesłanie kopii R do węzła zawierającego S lub odwrotnie. Koszt jest równy wówczas sumie kosztu zapoczątkowania komunikacji i kosztu przesłania jednej relacji. Dalej załóżmy, że koszt przesyłania krotki jest stały i ten czas przyjmijmy za naszą jednostkę. Niech c0-czas zapoczątkowania komunikatu, R ma „r” krotek, a S -„s” krotek. Wówczas koszt złączenia oblicza się wg wzoru c0+min(r,s). Nie zawiera on członu odpowiadającego kosztowi uzyskania wyniku w konkretnym węźle. Załóżmy, że wynik może byc uzyskany w dowolnym węźle. Inną metodą jest półzłączenie R i S: R|xS=ΠR(R|X|S) (operacja niesymetryczna).

W środowisku rozproszonym półzłączenie realizujemy następująco:

1.rzutujemy S na R∩S i rzut przesyłamy do R

2.w węźle R usuwamy z R tzw. Krotki zwisające: wykonujemy właściwie złączenie naturalne R|x|ΠR∩S(S)

Przypuśćmy dalej, że r'-rozmiar rzutów R na R∩S, s'-rozmiar rzutów S na R∩S, r''-rozmiar R|xS, s''-rozmiar S|xR

Aby dokonać pełnego złączenia naturalnego należy:

1.przesłać ΠR∩S(S) do węzła z R

2.w węźle z R obliczyć R|xS

3.R|xS przesłać do węzła z S

4.w węźle z S obliczyć (R|xS)|x|S

Można udowodnić, że (R|xS)|x|S=R|x|S

Istnieje symetryczna metoda (role R i S są odwrócone). Koszt (1) wynosi c0+s', (3): c0+r''

Zatem koszt jest mniejszy od prostej metody złączenia, jeżeli:

c0+min(s'+r'',r'+s'')<min(r,s).

Metoda półzłączeń jest zatem efektywna szczególnie dla małych c0 i interesuje nas minimalizacja kosztu przesyłania, a nie minimalizacja obliczeń w węźle.

Gdy należy dokonać złączenia większej ilości relacyj, to liczba sposobów wykonywania półzłączeń gwałtownie się zwiększa. Zazwyczaj korzystne jest wykonywanie wielu półzłączeń. W ich wyniku zmniejsza się w miarę możliwości jedną lub wiele relacyj.

Relację postaci ΠRi(R1|x|R2...|x|Rn) nazywa się redukcją Ri względem R1,...Rn. Bywa, że zapytanie polagające na złączeniu sprowadza się do redukcji jednej relacji względem pozostałych.

Architektura klient-serwer

Istnieją dwa sposoby realizacji dostępu do bazy danych w architekturze klinet-serwer:

Rozwiązanie oparte na serwerze plików oraz na serwerze SQL. Pierwsze ma wiele wad (brak gwarancji jednolitego systemu zarządzania np. współbieżnością, szybkością dostępu), natomiast drugie wspiera optymalizację zapytań, współbieżność oraz standardowe odwołania do systemu zarządzania (SQL).

Koncepcja klient serwer, wykorzystująca serwery bazodanowe (SQL) zaczęła się rozwijać wraz z rozwojem sieci komputerowych. Wówczas wymyślono, aby system posiadał dwa rodzaje aplikacyj: jedną na komputerze (komputerach) klienta, drugą na serwerze (serwerach). Oprócz tego na rozwój architektury klient-serwer ma wpływ Internet w tym WWW (dostęp do serwerów poprzez adresy URL, środowisko graficzne).

W tej architekturze aplikacje mogą być dzielone na moduły i odpowiednie moduły (np. formularz) są przesyłane do odpowiednich klientów. Dodatkowo mechanizmy internetu wykorzystuje się w sieciach wewnętrznych firm (intranety).

Do tych celów opracowano trójwarstwowy model zarządzania, gdzie poszczególne warstwy odbierają dane i dokonują na nich ściśle określonych działań, a w przypadku błędu komunikat o nim przesyłają do źródła danych. Żadna z warstw nie powiela pracy innych.

Wyróżnia się 3 warstwy:

1.Dolną -odpowiedzialną za dostęp do bazy danych. Realizuje ona bezpoścredni dostęp do bazy poprze sterowniki oraz aplikacje sieciowe. Warstwa ta odbiera instrukcje-zapytania SQL z warstwy średniej i je wykonuje. Odpowiedź z bazy danych przekazuje warstwie środkowej.

2.Środkową -warstwę reguł dziedziny danych. Tworzy ona kod odpowiedzialny za implementację reguł spójności danych, zgodności formatu. Te reguły wymuszają na aplikacji odpowiednią modyfikację bazy danych. Pobiera z warstwy górnej zadania -instrukcje do wykonania. Porównuje je z regułami i przesyła do dolnej warstwy, a wyniki otrzymane od niej i potwierdzenie wykonania przekazuje do warstwy górnej

3.Górną -interface użytkownika. Zajmuje się ona prezentacją danych i instrukcyj w komputerze użytkownika. Odbiera od niego dane i przekazyuje warstwie środkowej i wyświetla otrzymane od niej dane lub komunikaty o błędzie. Projekt interface'u nazywa się kodem prezentacji. Zawiera on: sposób podiału na ekrany, przepływ informacji pomiędzy ekranami, ułożenie pól na ekranie, sposób prezentacji komunikatów, rodzaje symulacji graficznej, użycie kolorów, grafiki etc.

Warstwy to logiczne części aplikacji rozdzielone funkcjami. Warstwy górna i dolna nie zależą od sposobu przechowywania bazy danych, której struktura jest znana jedynie warstwie środkowej, która może być scalona z górną. Gdy warstwom odpowiadają rożne programy to pełnią rolę klienta albo serwera, przy czym warstwa górna jest zawsze klientem, dolna serwerem. Można mówić o klientach jedno- i wielowarstwowych.

Do dostępu do baz danych stosuje się standardowe sterowniki. Najpopularniejszym jest standard ODBC (Open DataBase Connectivity) by Microsoft. Inne to Java DBC (JDBC) by Sun, DataBase Engine (DBE) by Borland.

W standardzie ODBC stewrownik ODBC umieszcza się pomiędzy bazą danych a aplikacją. Dla różnych systemów baz danych są różne sterowniki ODBC, przy czym można wyróżnić 2 architektury:

1. zorientowana na klienta (najpopularniejsza): sterownik ODBC jest umieszczany na komputerze klienta (PC+Windows); kżdy sterownik używa specjalnego oprogramowania sieciowego do połączenia się z serwerem; aplikacja korzysta z menedżera sterowników ODBC, wybierającego odpowiedni sterownik dla odpowiedniego systemu b.d.

2. zorientowana na klienta: tu do komunikacji wystarczy standardowy sterownik komunikacji sieciowej, zaś sterowniki ODBC znajdują się na serwerze ODBC (który może lecz nie musi być związany bezpośrednio z jednym serwerem b.d.); maszyna klienta potrzebuje tylko „ogólnego” sterownika ODBC; serwer wymaga jednego sterownika dla każdego systemu b.d.

Z kolei Interface JDBC może pracować w dwóch trybach: z lub bez pośrednictwa sterowników ODBC.

Przy wykorzystywaniu Internetu (intranetu) jako medium łączącego klienta z serwerem można skorzystać z języków programowania wykorzystywanych w Internecie:

-HTML -formularze HTML są przesyłane na serwer i wykonywane przez skrypty CGI lub PHP

-Applety Javy®- wykorzystujące formularze HTML lub sterowniki JDBC lub ODBC.

W realizacji dostępu z wykorzystaniem Internetu (intranetu) warstwę środkoa często umieszcza się na oddzielnym serwerze warstwy środkowej (jek w ODBC, JDBC i CGI), który dopiero komunikuje się z serwerem bazy danych. Ponadto za efektywniejszą uważa się realizację klienta jednowarstwowego.

---