I6E1S1
Architektura
Obiektowej
Bazy Danych
Projekt zespołowy
Autorzy:
Paulina Brzozowska,
Miłosz Góralczyk,
Michał Jasiorowski,
A
ukasz Jesionek,
Marcin Karpioski,
Grzegorz Kędzierski
Wojskowa Akademia Techniczna
Spis treści
1. Ogólna koncepcja architektury OBD ............................................................................................... 4
2. Ogólne założenia ............................................................................................................................. 5
3. Ogólny schemat komunikacji .......................................................................................................... 5
4. Ogólny schemat struktury projektu ................................................................................................ 8
5. 5. Projekt systemu zarzÄ…dzania obiektowÄ… bazÄ… danych .............................................................. 10
5.1 DIAGRAM PAKIETÓW ................................................................................................................. 10
5.2 DIAGRAM KLAS ......................................................................................................................... 11
6. Projekt analizatora syntaktycznego i semantycznego obiektowego języka zapytao .................... 13
6.1 DIAGRAM PAKIETÓW ................................................................................................................. 13
6.2 ORGANIZACJA PLIKU y
RÓDA
OWEGO ............................................................................................ 13
6.3 SEKCJA KODU UŻYTKOWNIKA...................................................................................................... 13
6.4 SEKCJA DYREKTYW .................................................................................................................... 13
6.5 SEKCJA REGUA
WYRAŻEO REGULARNYCH ...................................................................................... 14
7. Projekt składu obiektów w obiektowej bazie danych ................................................................... 16
7.1 DIAGRAM PAKIETÓW ................................................................................................................. 16
7.2 DIAGRAM KLAS ......................................................................................................................... 16
7.3 ZAA
OŻENIA OGÓLNE .................................................................................................................. 17
7.4 OSFF  OBJECT STORAGE FILE FORMAT ..................................................................................... 17
7.4.1 SCHEMAT PLIKU ................................................................................................................. 17
7.4.2 BOOT SEKTOR .................................................................................................................. 18
7.4.3 OAT  OBJECT ALLOCATION TABLE ....................................................................................... 18
7.4.4 DANE ............................................................................................................................... 18
7.5 META DANE ............................................................................................................................. 18
8. Projekt indeksów w obiektowej bazie danych .............................................................................. 20
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
2
8.1 DIAGRAM PAKIETÓW ................................................................................................................. 20
8.2 DIAGRAM KLAS ......................................................................................................................... 20
9. Projekt generatora planów wykonania zapytania ......................................................................... 23
9.1 DIAGRAM PAKIETÓW ................................................................................................................. 23
9.2 ZADANIA QUERY PLANNERA ........................................................................................................ 23
9.3 MODEL KOSZTÓW ...................................................................................................................... 24
9.4 WARUNEK STOPU GENERACJI PLANÓW WYKONANIA ZAPYTANIA .................................................... 24
10. Projekt mechanizmów organizujących rozproszenie obiektowej bazy danych ........................ 26
10.1 DIAGRAM PAKIETÓW ................................................................................................................. 26
10.2 CELE ........................................................................................................................................ 26
10.3 OGÓLNE ZAA
OŻENIA .................................................................................................................. 26
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
3
Architektura OBD
1. Ogólna koncepcja architektury OBD
Klient
Serwer centralny
Serwer danych 1 Serwer danych 2 Serwer danych 3
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
4
2. Ogólne założenia
·ð DoÅ‚Ä…czony serwer automatycznie replikuje dane z serwerami już należącymi do systemu
·ð System automatycznie zapewnia redundancjÄ™ na zadanym poziomie
o W razie awarii mniejszej niż zadana liczby serwerów system ma pozostad w stanie
sprawności z dostępem do jak największej części danych
·ð (W ramach możliwoÅ›ci) brak serwera głównego
·ð System musi równoważyd obciążenie poszczególnych serwerów
·ð W przypadku równoczesnego dostÄ™pu do tych samych danych (zapis) rozwiÄ…zywanie
konfliktów związanych z aktualnością danych.
·ð MożliwoÅ›d wprowadzenie przez użytkownika poziomu redundancji
o (szczególny przypadek  pełne mirrory)
·ð System musi zapewnid mechanizmy przesyÅ‚anie danych poprzez różne kanaÅ‚y np. tcp/ip,
named Pipes itp.
·ð System musi dysponowad mechanizmami przesyÅ‚ania komunikatów pomiÄ™dzy serwerami
·ð System powinien umożliwid zastosowanie priorytetów aktualnoÅ›ci danych (jeÅ›li aktualnoÅ›d
danych nie jest rzeczÄ… priorytetowÄ… pobieranie danych tylko z kopii)
·ð System musi dysponowad mechanizmami replikacji i synchronizacji serwerów co okreÅ›lony
kwant czasu
·ð System musi dysponowad informacjami o tym gdzie przechowywane sÄ… kopie (i oryginaÅ‚y)
obiektów
3. Ogólny schemat komunikacji
ODCZYT OBIEKTU O ZNANYM OID:
1. Klient odpytuje serwer centralny o obiekt o danym OID
2. Serwer centralny podaje klientowi adres serwera z danym obiektem
3. Klient wysyła żądanie przesłania obiektu o danym OID do serwera wskazanego przez SC
4. Serwer danych przesyła obiekt bezpośrednio do Klienta
ZAPIS OBIEKTU DO BAZY:
1. Klient wysyła żądanie chęci zapisu obiektu do SC
2. SC odsyła adres serwera danych do którego klient może zapisad dany obiekt
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
5
3. Klient wysyła żądanie zapisu obiektu do serwera danych wskazanego przez SC
4. Serwer danych zapisuje obiekt i zwraca wynik operacji do Klienta
5. Serwer danych wysyła wiadomośd do SC, że został dodany nowy obiekt, obiekt ten przesyłany
jest do SC, ten rozsyła go do odpowiedniej liczby serwerów danych (dla zachowania
redundancji danych)
6. SC odsyła zmodyfikowane meta dane do Serwera danych który wysłał żądanie
AKTUALIZACJA OBIEKTU:
1. Klient wysyła zaktualizowany obiekt bezpośrednio do Serwera danych z którego pochodził
ten obiekt
2. Serwer danych po zapisie potwierdza klientowi udany zapis
3. Serwer danych przesyła do SC informację o aktualizacji obiektu
4. SC rozsyła nową kopię obiektu do pozostałych serwerów danych
WYKONANIE ZAPYTANIA:
1. W oknie konsoli aplikacji OBD lub innej aplikacji połączonej przez interfejs sieciowy zostaje
wygenerowane zapytanie
2. Zapytanie to przesyłane jest do SC
3. Analizator znajdujÄ…cy siÄ™ na SC w oparciu o zapytanie oraz o metadane SC przeprowadza
analizę syntaktyczną, która sprawdza poprawnośd składni zapytania, a następnie
przeprowadza analizę semantyczną, co umożliwia określenie, czy obiekty do którego odnosi
się zapytanie istnieją i czy zapytanie może się wykonad. Efektem działania analizatora jest
wytwarza drzewo tokenów
4. Drzewo to trafia do Query Plannera który również znajduje się na SC. QP tworzy możliwe
plany wykonania zapytania. Możliwe ograniczenie liczbowe lub czasowe generowanych
planów. QP musi podjąd decyzję czy jego działanie przy każdym zapytaniu ma sens  niekiedy
wykonanie prostego zapytania zostanie zrealizowane szybciej niż czas potrzebny na działanie
QP. Działalnośd QP ściśle związane jest z mechanizmem indeksów serwera centralnego i
statystykami zapisanymi w metadanych SC.
5. Po ułożeniu optymalnego zapytania, przesyłane jest żądanie wykonania tego zapytania do SD
który posiada największą ilośd obiektów potrzebnych do wykonania danego zapytania
6. SD odczytuje jakie obiekty potrzebne będą do wykonania tego zapytania, następnie dzieli
zapytania na niezależne części (np. Osoba where Imie =  Jan ), taka częśd wysyłana jest do
SC ten z kolei rozsyła to zapytanie do serwerów danych które posiadają obiekty tego typu
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
6
7. Obiekty spełniające to kryterium przesyłane są bezpośrednio do SD które obsługuje całe
zapytanie
8. Po wykonaniu całego zapytania, do Klienta zwracane są referencje do obiektów które
spełniają to zapytanie (zwracane są ich OID)
9. Klient otrzymując bezpośrednio od SD listę OID, prosi SC o dereferencje obiektów(jeśli jest
potrzebna) (dereferencja przebiega jak odczyt obiektów)
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
7
4. Ogólny schemat struktury projektu
Struktura projektu została podzielona na 7 głównych pakietów:
·ð Storage Package
·ð Engine Package
·ð SBQL Syntatic Analyzer Package
·ð Query Planner Package
·ð Indicies Package
·ð Managment System Package
·ð Data Distribution Package
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
8
5.
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
9
5. Projekt systemu zarzÄ…dzania obiektowÄ… bazÄ… danych
System zarzÄ…dzania bazÄ… danych (ang. DBMS  database management system), jest
oprogramowaniem będącym swoistym interfejsem z którego mogą korzystad użytkownicy baz
danych w celach administracyjnych czy wywoławczych (np. wykonywanie zapytao). DBMS w
architekturze klient-serwer składa się z mechanizmów znajdujących się po stronie serwera
bazodanowego oraz aplikacji, która pozwala zarządzad danym serwerem w sposób przystępny dla
użytkownika.
5.1 DIAGRAM PAKIETÓW
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
10
5.2 DIAGRAM KLAS
MECHANIZMY DBMS, KTÓRE S
NIEZB
DNE DO DZIAA
ANIA SERWERA BAZ DANYCH TO:
·ð interfejsy, które umożliwiajÄ… i kontrolujÄ… przebieg wykonywania zapytao do bazy, tj.
komunikacji z mechanizmami takim jak:
üð parser,
üð query planer,
üð podsystem skÅ‚adu obiektów,
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
11
üð komunikacja sieciowa;
·ð modyfikowanie (dodawanie/usuwanie/modyfikowanie) elementów wykonawczych bazy,
takich jak:
üð indeksy,
üð procedury,
üð funkcje;
·ð zarzÄ…dzanie bazami danych  tzn. modyfikowanie konkretnych instancji, tworzenie nowych,
usuwanie istniejÄ…cych baz;
·ð zarzÄ…dzanie bezpieczeostwem  w tym weryfikacja i autoryzacja dostÄ™pu do danych;
·ð wspieranie replikowania danych oraz tworzenia kopi zapasowych;
·ð modyfikacja parametrów uruchomieniowych serwera lub baz.
FUNKCJONALNOŚD, KTÓR
POWINNA POSIADAD APLIKACJA DBMS:
·ð modyfikowanie (jw. + przeglÄ…danie) struktury serwera  rodzaje i typy baz danych
udostępnianych przez serwer;
·ð modyfikowanie konkretnych baz danych, w tym edycja danych przechowywanych obiektów
oraz podglÄ…d schematu bazy;
·ð możliwoÅ›d definiowania wÅ‚asnych zapytao, umożliwienie sprawdzenia ich poprawnoÅ›ci;
·ð prezentacja oraz zapis wyników wykonania zapytao;
·ð query builder  narzÄ™dzie do tworzenia zapytao w sposób graficzny.
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
12
6. Projekt analizatora syntaktycznego i semantycznego
obiektowego języka zapytań
6.1 DIAGRAM PAKIETÓW
6.2 ORGANIZACJA PLIKU y
RÓDA
OWEGO
Kod użytkownika (implementacja klas i zwracanych typów)
%%
Dyrektywy C# Lex (definicje makr, deklaracje nazw stanów)
%%
Reguły wyrażeń regularnych (reguły analizy leksykalnej)
6.3 SEKCJA KODU UŻYTKOWNIKA
Kod użytkownika jest kopiowany do pliku z
ródłowego analizatora leksykalnego. Znajdują się tu
deklaracje importowanych modułów, definicje przestrzeni nazw.
6.4 SEKCJA DYREKTYW
Zaczyna się po wystąpieniu pierwszego separatora %% i trwa do wystąpienia drugiego. Każda
dyrektywa powinna być zawarta w pojedynczej linii.
1. Kod klasy analizatora leksykalnego:
%{

%}
2. Kod konstruktora klasy analizatora leksykalnego:
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
13
%init{

%init}
3. Kod zakończenia pliku klasy analizatora leksykalnego
%eof{

%eof}
4. Definicje makr
Nazwa makra może się składać z liter, cyfr, znaków podkreślenia; nazwa rozpoczyna się od litery
lub znaku podkreślenia. Ponadto definicja makra powinna być wyrażeniem regularnym.
=
5. Deklaracje stanów
Stany leksykalne są wykorzystywane do sterowania w sytuacji dopasowania wyrażeń regularnych.
Deklaracja stanów powinna być zawarta w jednej linii pliku z
ródłowego.
%state state[0][, state[1], state[2], & ]
6. Nazwy komponentów analizatora leksykalnego
·ð Zmiana nazwy klasy analizatora leksykalnego z Yylex:
%class
·ð Zmiana nazwy funkcji zwracajÄ…cej kolejne leksemy z yylex:
%function
·ð Zmiana typu zwracanego w wyniku wykonania funkcji podajÄ…cej kolejne leksemy:
%type
7. Alfabet analizatora leksykalnego
Domyślnym alfabetem dla analizatora leksykalnego są znaki z zakresu 0 do 127.
6.5 SEKCJA REGUA
WYRAŻEC
REGULARNYCH
Sekcja ta dotyczy reguł dzielenia strumienia wejściowego analizowanego programu na symbole
leksykalne. Każda reguła składa się z trzech części:
] {}
1. Stany leksykalne
Każda reguła poprzedzona jest opcjonalną listą stanów leksykalnych o następującej budowie:

Lista stanów zdefiniowana w ten sposób określa, w jakich stanach początkowych reguła może
zostać dopasowana.
2. Wyrażenia regularne
Wyrażenia regularne nie powinny zawierać pustych spacji, ponieważ są one interpretowane
jako koniec wyrażenia regularnego. Wyjątek:   jest interpretowany jako pusta spacja.
Zbiór znaków specjalnych: ? * + | ( ) ^ $ . [ ] { }  \
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
14
Oznaczmy literami e i f dwa wyrażenia regularne. Wyrażenia regularne ef występujące po sobie są
złączeniem tych wyrażeń regularnych.
W przypadku zapisu e | f znak  | oznacza opcjonalność wyrażeń regularnych
występujących po obu stronach tego znaku.
Niżej zostały wymienione rozpoznawane sekwencje escape owe i ich znaczenia:
\b  backspace
\n  nowa linia
\t  znak tabulacji
\f  formfeed
\r  znak powrotu karetki
\ddd  kod znaku zapisany na trzech pozycjach w kodzie ósemkowym
\xdd  kod znaku zapisany na dwóch pozycjach w kodzie szesnastkowym
\udddd  znak alfabetu Unicode zapisany na czterech pozycjach w kodzie szesnastkowym
\^C  znak CTRL
\c  znak c poprzedzony znakiem backslash powoduje rozpoznanie znaku c
$ - znak końca linii
.  kropka oznacza dowolny znak z wyjÄ…tkiem znaku nowej linii
 &   znaki specjalne umieszczone w cudzysłowie są rozpoznawane jako one same. Wyjątkiem
jest znak  , który powinien być zapisany jako \ .
{nazwa makra}  nawiasy klamrowe określają rozszerzenia makra
* - znak * oznacza domknięcie Kleene a i oznacza dopasowanie zero lub więcej wystąpień
wyrażenia regularnego poprzedzającego znak *
+ - znak + powoduje dopasowanie jednego lub więcej wystąpienia wyrażenia regularnego
występującego bezpośrednio przed znakiem +
?  znak zapytania pozwala dopasować zero lub jedno wystąpienie poprzedzającej ten znak
wyrażenia regularnego
(& )  nawiasy okrągłe są wykorzystywane do grupowania w nich wyrażeń regularnych
[& ]  nawiasy kwadratowe oznaczają klasę znaków i pozwalają dopasować dowolny znak
zawarty między nawiasami. Jeżeli po pierwszym nawiasie zostanie wprowadzony znak ^,
wtedy oznacza to negację zbioru znaków zawartych w nawiasach, a więc będą
dopasowywane wszystkie znaki z wyjątkiem tych znajdujących się między nawiasami.
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
15
7. Projekt składu obiektów w obiektowej bazie danych
7.1 DIAGRAM PAKIETÓW
7.2 DIAGRAM KLAS
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
16
7.3 ZAA
OŻENIA OGÓLNE
·ð SkÅ‚ad obiektów może korzystad zarówno z pamiÄ™ci masowej jak i pamiÄ™ci podrÄ™cznej
·ð Wszystko co jest zapisywane w skÅ‚adzie obiektów jest obiektem
·ð Atrybuty obiektów sÄ… obiektami
·ð Nie istniejÄ… typy proste
·ð Każdy obiekt ma dowolnÄ… wielkoÅ›d
·ð Obiekty w bazie zapisywane sÄ… zgodnie ze schematem bazy
·ð Schemat bazy danych zapisany jest jako drzewo powiÄ…zao miedzy obiektami
·ð Schemat bazy danych zapisywany jest w metabazie
·ð Metabaza przetrzymuje informacjÄ™ dot. Odwzorowywania OID na fizyczne adresy obiektów
·ð Każdy obiekt posiada swój identyfikator OID
·ð OID jest niezmiennÄ… strukturÄ… jednoznacznie reprezentujÄ…cÄ… dany obiekt
·ð OID powinien pozwalad na okreÅ›lenie poÅ‚ożenia obiektu w rozproszonej bazie danych
·ð Obiekty zapisywane sÄ… w pliku bazy danych zgodnie z algorytmem zapisywania
·ð Dopuszczalna jest fragmentacja (jak najmniejsza) pliku bazy danych
·ð SkÅ‚ad obiektów powinien posiadad metody wspomagajÄ…ce efektywne zarzÄ…dzanie
położeniem obiektów w pliku bazy danych
·ð SkÅ‚ad obiektów powinien posiadad metody umożliwiajÄ…ce wyszukiwanie obiektów o
określonym typie w celu przyśpieszenia wyszukiwania.
·ð SkÅ‚ad obiektów powinien wspierad sprawdzanie istnienia typu obiektów przez parser
synaktyczny
·ð SkÅ‚ad obiektów powinien wspierad asynchroniczne odczytywanie jak i zapisywanie do pliku
bazy danych w celu przyśpieszenia wykonywania zapytao
·ð SkÅ‚ad obiektów powinien udostÄ™pniad mechanizm cache w celu optymalizacji czasu dostÄ™pu
do odpowiednich danych lub ich zapisywania
·ð SkÅ‚ad obiektów musi mied możliwoÅ›d współpracy z mechanizmem indeksowania w celu
przyśpieszenia działania operacji wyszukania
·ð SkÅ‚ad obiektów powinien udostÄ™pniad metody pozwalajÄ…ce na dereferencje obiektów
7.4 OSFF  OBJECT STORAGE FILE FORMAT
7.4.1 SCHEMAT PLIKU
0B  1024B BOOT Sektor
1025B - & B OAT (Object Allocation Table)
& B - 2^64B Dane
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
17
7.4.2 BOOT SEKTOR
Obszar ten zawiera następujące dane w postaci zserializowanego obiektu:
Segment Size Rozmiar segmentu danych
Data Start Segment PoczÄ…tkowy segment danych
7.4.3 OAT  OBJECT ALLOCATION TABLE
Obszar ten zawiera obiekt zawierajÄ…cy informacjÄ™ o tym gdzie znajdujÄ… siÄ™ poczÄ…tkowe segmenty
meta danych.
Zawartośd obiektu:
SegmentID Identyfikator segmentu (niezmienny)
Segment Adres segmentu danych (zmienny w zależności od położenia)
Type Typ segmentu danych (0  wolny, 1  zajęty, 2  zarezerwowany)
Next GUID wskazujący następny segment (Guid.Empty jeśli jest to ostatni)
7.4.4 DANE
Obszar zawiera faktyczne segmenty z danymi na nich zapisanymi
Dane dotyczące każdego dostępnego segmentu zapisywane są w tablicy OAT. Gdy ilośd segmentów
zwiększa się i zbliża do maksymalnej dostępnej w tej chwili objętości OAT, automatycznie następuje
powiększenie obszaru dostępnego dla OAT poprzez przepisanie początkowych segmentów na koniec
tablicy oraz podanie nowego Data Start Segment do obiektu BOOT. Następuje również
przebudowanie indexów.
7.5 META DANE
Meta dane występują w dwóch wersjach (dla serwera centralnego dane logiczne, oraz dla serwerów
danych dane fizyczne)
Dane fizyczne:
Zawierają informację dotyczące przechowywanych obiektów.
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
18
Dane obiektów:
OID Identyfikator obiektu
Type Identyfikator typu
SegmentID Identyfikator segmentu na którym obiekt jest
zapisany
CreationTime Czas zapisania obiektu
ModificationTime Czas modyfikacji obiektu
Copies Lista kopii obiektu na innych serwerach
Meta dane te przechowują również strukturę bazy danych. Przechowują również informacje o ilości
obiektów poszczególnych typów na tym serwerze, dane dotyczące indeksów na poszczególnych
obiektach danego typu.
Dane logiczne:
Przechowują informacje dotyczące aktualności danych, ilości obiektów danego typu, o tym gdzie
obiekty o danym OID się znajdują, o kopiach poszczególnych obiektów.
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
19
8. Projekt indeksów w obiektowej bazie danych
Indeksy są strukturami danych umożliwiającymi szybszy dostęp do określonych rekordów w pliku
danych, a co za tym idzie szybsze wykonywanie zapytao. Struktury te umożliwiają wydajny dostęp do
rekordów w oparciu o pola indeksujące, które są wykorzystywane do budowy indeksów. W celu
zlokalizowania rekordu w pliku danych z wykorzystaniem indeksu najpierw odwołujemy się do
indeksu, który wskazuje nam adres rekordu w pliku danych.
W najbardziej popularnym ujęciu indeks należy rozumied jako dwu-kolumnową tablicę, gdzie
pierwsza kolumna zawiera wartości kluczowe, zaś druga  wartości niekluczowe, najczęściej
referencje do obiektów.
8.1 DIAGRAM PAKIETÓW
8.2 DIAGRAM KLAS
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
20
NAJBARDZIEJ POPULARNYMI STRUKTURAMI DANYCH UŻYWANYMI DO ORGANIZACJI INDEKSÓW S

·ð indeksy z kodowaniem haszujÄ…cym (hash coding)
Kodowanie haszujące, oparte na funkcji haszującej (hash function) działającej na
wartości kluczowej, dostarcza praktycznie jednakowego czasu wyszukiwania dla
dowolnego rozmiaru indeksu.
Wadą tej metody jest koniecznośd określenia z góry rozmiaru tablicy indeksu. Wada
ta jest wyeliminowana przez tzw. dynamiczne haszowanie (dynamic hashing) lub
haszowanie liniowe (linear hashing).
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
21
Druga wada polega na konieczności rozstrzygania konfliktów (ten sam wynik funkcji
haszującej dla różnych wartości kluczowych).
·ð B-drzewo (B-tree, balanced tree)
Metoda oparta na B-drzewie jest nieco gorsza jeżeli chodzi o czas wyszukiwania i jest
wrażliwa na częste aktualizacje indeksu. Jej zaletą jest prostota algorytmu
i oszczędnośd miejsca.
Same indeksy są zapamiętane w bazie danych. Informacja o nich jest zapamiętana w specjalnym
rejestrze indeksów znajdującym się na serwerze.
OGÓLNIE INDEKSY MOŻNA PODZIELID NA NAST
PUJ
CE
Indeks główny jest obliczony na unikalny klucz kolekcji: dla danego argumentu zwraca dokładnie
jednÄ… referencjÄ™ do obiektu.
" Np. indeks, którego argumentem (wartością kluczową) jest numer PESEL.
Indeks wtórny jest obliczony na atrybut, którego wartośd nie jest unikalna dla danej kolekcji
obiektów.
" Np. indeks, którego argumentem (wartością kluczową) jest stanowisko pracownika.
Indeks gęsty oznacza, że dla każdej wartości atrybutu występującej w bazie danych tworzona jest
pozycja indeksu.
" Np. dla obiektów Osoba indeks, którego argumentem jest dowolne nazwisko
występujące w bazie danych.
Indeks zakresowy dotyczy wartości z pewnego zakresu.
" Np. dla atrybutu zarobek indeks zawiera pozycje z przedziałów 0-99, 100-199, 200-
299, ...
" Dla nazwisk pozycje mogÄ… mied postad:  nazwiska zaczynajÄ…ce siÄ™ na A ,  nazwiska
zaczynajÄ…ce siÄ™ na B , ....,  nazwiska zaczynajÄ…ce siÄ™ na Å» .
Celem zastosowania mechanizmu indeksowania jest chęd zwiększenia szybkości działania aplikacji.
Wstępnie przewiduję zastosowanie struktury B+ drzewa (wariancji B-drzewa).
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
22
9. Projekt generatora planów wykonania zapytania
9.1 DIAGRAM PAKIETÓW
DANE WEJÅšCIOWE
Query Planner na wejściu otrzymuje drzewo tokenów (parse tree, query tree & ) które jest wynikiem
działania parsera. Parse tree reprezentuje logiczne kroki niezbędne dla wykonania zapytania
9.2 ZADANIA QUERY PLANNERA
üð PodjÄ™cie decyzji czy generowad możliwe plany wykonania zapytania ( tworzenie query palnu
dla zapytao bardzo prostych, na przykład do jednej tabeli bez indeksów, może niekiedy zająd
więcej czasu niż bezpośrednie wykonanie zapytania)
üð Tworzenie i ewaluacja istniejÄ…cych query planów
üð Estymacja wartoÅ›ci funkcji kosztu  wyrażenia w którym wystÄ™pujÄ… wszystkie skÅ‚adniki
uważane za mające istotny wpływ na koszt realizacji zapytania. (liczba dostępów do dysku,
czas zajętości procesora, czas komunikacji)
üð Wybór najmniej kosztownego planu, który wykona zapytanie najszybciej jak to możliwe, przy
jednoczesnym minimalnym wykorzystaniu zasobów komputera
üð PodjÄ™cie decyzji kiedy zaprzestad generowanie kolejnych planów
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
23
9.3 MODEL KOSZTÓW
Zadaniem modelu kosztów jest oszacowanie czasu/kosztu różnych planów ewaluacji zapytania.
Wyrażenie, w którym występują wszystkie składniki uważane za mające istotny wpływ na koszt
realizacji zapytania.
Podstawową miarą kosztu w systemie scentralizowanym jest na ogół liczba dostępów do dysku, ale
istotny może okazad się również czas zajętości procesora lub czas komunikacji(jeśli zapytanie jest
wykonywane w środowisku wieloprocesorowym lub rozproszonym).
Wartośd funkcji kosztu realizacji zapytania wyrażana jest w jednostkach czasu, jednostkach
bezwymiarowych lub  sztucznych
MODEL KOSZTÓW POWINIEN OBEJMOWAD
üð SzczegółowÄ… budowÄ™ zapytania (semantyka)
üð Sposób jego ewaluacji;
üð Meta-informacje dotyczÄ…ce struktur danych (np. rozmiary kolekcji obiektów);
üð Meta-informacje retrospektywne (np. dotyczÄ…ce rzeczywistych kosztów ewaluacji podobnych
zapytań);
üð Informacje odnoÅ›nie pomocniczych struktur danych uczestniczÄ…cych w ewaluacji zapytaÅ„ (np.
rozmiar buforów);
üð Informacje odnoÅ›nie Å›rodowiska komputerowego (np. ilość wolnej przestrzeni dyskowej);
üð Dowolne inne informacje relewantne dla optymalizacji (np.czas transferu dyskowego,
szybkość sieci)
9.4 WARUNEK STOPU GENERACJI PLANÓW WYKONANIA ZAPYTANIA
Ważnym elementem podczas generacji planów wykonania jest określenie, kiedy generator powinien
zakooczyd swoje działanie, tak, by czas generacji nie przewyższył czasu wykonania nawet najgorszego
planu.
Generator powinien zakooczyd działanie, gdy:
" koszt aktualnego planu jest wysoki, generator szuka lepszego planu bardziej intensywnie
(rozpatruje więcej alternatywnych planów)
" koszt aktualnego planu jest niski, generator kooczy poszukiwania z uwagi na małe
prawdopodobieostwo poprawy
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
24
WA
AÅšCIWOÅšCI
üð Plany powinny byd przechowywane  dla ponownego użycia  przy kolejnym wykonywaniu
tego samego zapytania zyskujemy czas który musielibyśmy poświęcid na stworzenie query
planu dla tego zapytania
üð W zwiÄ…zku z przechowywaniem  potrzeba istnienia  czegos do przechowywania planów 
może coś w stylu cache
üð Potrzeba wystÄ™powania kryteriów okreÅ›lajÄ…cych  jak dÅ‚ugo przechowywad plany
üð Plany wykonania mogÄ™ byd statyczne i dynamiczne  dynamiczne to takie które mogÄ… byd
modyfikowane podczas wykonywania zapytania, statyczne generowane przed wykonaniem
zapytania  w związku z planami dynamicznymi możemy wyróżnid Szacowany plan
wykonania (Estimated execution plan) i rzeczywisty plan wykonania (Actual execution plan)
üð Każdy plan powinien speÅ‚niad zasadÄ™ zachowania semantyki zapytania  tzn. każda Å›cieżka
wykonania zapytania powinna dad jednakowy wynik
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
25
10. Projekt mechanizmów organizujących rozproszenie
obiektowej bazy danych
10.1 DIAGRAM PAKIETÓW
10.2 CELE
·ð ZwiÄ™kszenie niezawodnoÅ›ci systemu
·ð ZwiÄ™kszenie wydajnoÅ›ci systemu
·ð Zrównoważenie obciążenia serwerów
·ð Organizacja kanałów replikacji i synchronizacji serwerów
10.3 OGÓLNE ZAA
OŻENIA
·ð DoÅ‚Ä…czony serwer automatycznie replikuje dane z serwerami już należącymi do systemu
·ð System automatycznie zapewnia redundancjÄ™ na zadanym poziomie
o W razie awarii mniejszej niż zadana liczby serwerów system ma pozostad w stanie
sprawności z dostępem do jak największej części danych
·ð (W ramach możliwoÅ›ci) brak serwera głównego
·ð System musi równoważyd obciążenie poszczególnych serwerów
·ð W przypadku równoczesnego dostÄ™pu do tych samych danych (zapis) rozwiÄ…zywanie
konfliktów związanych z aktualnością danych.
·ð MożliwoÅ›d wprowadzenie przez użytkownika poziomu redundancji
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
26
o (szczególny przypadek  pełne mirrory)
·ð System musi zapewnid mechanizmy przesyÅ‚anie danych poprzez różne kanaÅ‚y np. tcp/ip,
named Pipes itp.
·ð System musi dysponowad mechanizmami przesyÅ‚ania komunikatów pomiÄ™dzy serwerami
·ð System powinien umożliwid zastosowanie priorytetów aktualnoÅ›ci danych (jeÅ›li aktualnoÅ›d
danych nie jest rzeczÄ… priorytetowÄ… pobieranie danych tylko z kopii)
·ð System musi dysponowad mechanizmami replikacji i synchronizacji serwerów co okreÅ›lony
kwant czasu
·ð System musi dysponowad informacjami o tym gdzie przechowywane sÄ… kopie (i oryginaÅ‚y)
obiektów
Projekt Obiektowej Bazy Danych | Wojskowa Akademia Techniczna
27