Bazy Danych II TOM 2

BAZY DANYCH II TOM II: DWIE ENCJE

opracował Foxer 1

Od autora opracowania W tomie tym znajdziemy współbieżność, indeksy (drzewa) i trochę o optymalizacji zapytań. Dużo bezsensownej teorii.

Spis treści 1

2

3

Indeksy............................................................................................................................................. 3 1.1

Typy indeksów ......................................................................................................................... 3

1.2

Indeks B+ -drzewo ................................................................................................................... 4

Transakcje ........................................................................................................................................ 6 2.1

O transakcjach ......................................................................................................................... 6

2.2

O realizacjach .......................................................................................................................... 7

2.3

Konflikty................................................................................................................................... 7

Algorytmy zarządzania współbieżnym wykonywaniem transakcji.................................................. 8 3.1

Algorytmy blokowania............................................................................................................. 8

3.2

Zakleszczenia ........................................................................................................................... 8

3.3

Poziomy izolacji ....................................................................................................................... 9

4

Recovery ........................................................................................................................................ 10

5

Optymalizacja zapytań .................................................................................................................. 10 5.1

Szacowanie rozmiarów i współczynnik selektywności .......................................................... 10

5.2

Szacowanie rozmiarów selekcji ............................................................................................. 10

5.3

Szacowanie rozmiarów Projection ........................................................................................ 11

5.4

Szacowanie rozmiarów GROUP BY ........................................................................................ 11

5.5

Szacowanie rozmiarów UNION ............................................................................................. 11

5.6

Szacowanie rozmiarów JOIN ................................................................................................. 11

5.7

Histogramy ............................................................................................................................ 12

2

1 Indeksy Indeks zdefiniowany na pliku jest dodatkową strukturą fizyczną, której celem jest przyspieszenie wykonywania operacji, które nie są wystarczająco efektywnie wspierane przez podstawowe organizacje plików i struktury logiczne danych. Indeksy są zakładane na pojedynczych atrybutach lub zbiorach atrybutów relacji. Atrybuty te noszą nazwę atrybutów indeksowych. Rekord indeksu (k*) zawiera dwa pola • klucz reprezentujący jedną z wartości występujących w atrybutach indeksowych relacji • wskaźnik do bloku danych zawierający krotkę, której atrybut indeksowy równy jest kluczowi Typy rekordów indeksu: • Rekord indeksu k* jest rekordem danych (o wartości klucza k) • Rekord indeksu jest parą , gdzie rid jest identyfikatorem rekordu danych o wartości klucza k • Rekord indeksu jest parą , gdzie rid-list jest listą identyfikatorów rekordów danych o wartości klucza k • Rekord indeksu jest parą , gdzie bitmapa jest wektorem 0 i 1 reprezentującym zbiór rekordów danych

1.1 Typy indeksów Typy indeksów: • Charakterystyka atrybutu indeksowego o Indeks podstawowy (primary index) – założony na atrybucie porządkującym unikalnym o Indeks zgrupowany (clustering index) – założony na atrybucie porządkującym nieunikalnym o Indeks wtórny (secondary index) – założony na atrybucie nieporządkującym • Wskazania do plików danych o Indeks gęsty (dense) –posiada rekord indeksu dla każdego rekordu indeksowanego pliku danych o Indeks rzadki (sparse) – posiada rekordy tylko dla wybranych rekordów indeksowanego pliku danych • Liczba poziomów o Indeksy jednopoziomowe – jeden plik indeksu dla jednego pliku danych o Indeksy wielopoziomowe – indeks do indeksu Indeks podstawowy Indeks podstawowy jest indeksem rzadkim ponieważ nie wszystkie rekordy pliku danych posiadają rekordy indeksowe. Rekord indeksowy indeksu podstawowego dla wartości X zawiera adres bloku danych, w którym znajduje się rekord danych z wartością atrybutu indeksowego równą X. Indeks zgrupowany Indeks zgrupowany jest również indeksem rzadkim ponieważ nie wszystkie rekordy pliku danych posiadają rekordy indeksowe. Rekord indeksowy indeksu zgrupowanego dla wartości X zawiera adres bloku danych, w którym znajduje się pierwszy rekord danych z wartością atrybutu indeksowego równą X Indeks zgrupowany z blokami nadmiarowymi Wstawiane rekordy są umieszczane w wolnych szczelinach bloku głównego, a po jego zapełnieniu - w odpowiednim bloku nadmiarowym, do którego prowadzi wskaźnik z bloku głównego.

3

Indeks wtórny Indeks wtórny jest również uporządkowany. Jest on zakładany na atrybucie indeksowym pliku danych, który nie jest atrybutem porządkującym tego pliku. Każdy rekord pliku danych posiada swój odpowiednik w rekordzie indeksu. Stąd, indeks wtórny jest indeksem gęstym. Rekord indeksu wtórnego składa się z dwóch pól: wartości pola indeksowego i wskaźnika albo do rekordu albo do bloku danych zawierającego ten rekord. Indeks o kluczu złożonym Klucz indeksu może zawierać kilka atrybutów – taki klucz nazywamy kluczem złożonym. Indeksy na kluczach złożonych stosuje się do wyszukiwania rekordów spełniających warunki równościowe (tzw. zapytania punktowe) nałożone jednocześnie na pola występujące w kluczu złożonym. Bardziej uniwersalne są indeksy zakładane na pojedynczych atrybutach. Są one jednak mniej efektywne od indeksów złożonych w przypadku warunków poszukiwania jednocześnie nałożonych na indeksowane atrybuty. Indeks wielopoziomowy – ISAM Wyszukanie danych z wykorzystaniem indeksu jednopoziomowego wymaga przeszukania pliku indeksu. Plik indeksu jest przeszukiwany algorytmem połowienia binarnego ponieważ jest to plik uporządkowany. Algorytm ten nie należy do efektywnych. Wprowadzono indeksy wielopoziomowe, których efektywność przeszukiwania jest większa. Struktura ta jest zbudowana z dwóch poziomów. • Poziom pierwszy indeksuje cylindry. Rekordy indeksu na tym poziomie zawierają pary wartości: poszukiwany klucz i adres do indeksu ścieżki dyskowej. • Poziom drugi indeksuje ścieżki. Jego rekordy zawierają pary wartości: poszukiwany klucz i adres ścieżki. PO POLSKU: Indeks na pierwszym poziomie adresuje bloki danych. Każdy rekord tego indeksu zawiera wartość pola indeksowego i adres bloku danych, w którym ta wartość się znajduje. Rekordy tego indeksu są przechowywane w pliku uporządkowanym zgodnie z wartościami klucza indeksu pierwszego poziomu. Rekordy indeksu drugiego poziomu zawierają adresy bloków indeksu pierwszego poziomu. Wady: Indeks na • modyfikowanie zawartości pliku degeneruje indeks - spada efektywność dostępu do danych • powstają puste obszary po usuniętych rekordach • wstawiane rekordy trafiają do bloków nadmiarowych Struktura drzewiasta Wyróżnia się w niej tzw. korzeń, będący wierzchołkiem (punktem wejścia) całej struktury. Z korzenia prowadzą łuki, czyli wskazania albo do węzłów wewnętrznych albo do liści. Węzeł wewnętrzny posiada wskazania do innych węzłów. Liść nie posiada wskazań do innych węzłów. Jest więc elementem końcowym całej struktury.

1.2 Indeks B+ -drzewo Zrównoważona struktura drzewiasta • wierzchołki wewnętrzne służą do wspomagania wyszukiwania • wierzchołki liści zawierają rekordy indeksu ze wskaźnikami do rekordów danych • W celu zapewnienia odpowiedniej efektywności realizacji zapytań przedziałowych wierzchołki liści stanowią listę dwukierunkową 4

Charakterystyka • Operacje wstawiania i usuwania rekordów indeksu pozostawiają indeks zrównoważony • Każdy wierzchołek jest wypełniony w co najmniej 50% (za wyjątkiem korzenia) o usuwanie rekordów może skutkować mniejszym wypełnieniem niż 50% PO POLSKU: W korzeniu mamy wartość graniczną. Od korzenia odchodzą dwie strzałki. Na lewo – mniejsze/równe wartości granicznej, na prawo – większe od wartości granicznej. W wierzchołkach wewnętrznych mamy kolejne wartości graniczne. Odległość wszystkich liści od korzenia musi być taka sama. p – rząd B+ -drzewa WIERZCHOŁKI WEWNĘTRZNE Każdy wierzchołek wewnętrzny posiada co najwyżej p wskaźników do poddrzew. Każdy wierzchołek wewnętrzny, za wyjątkiem korzenia, posiada co najmniej ⎾ (p/2) ⏋ wskaźników do poddrzew. Korzeń posiada co najmniej 2 wskaźniki do poddrzew. LIŚCIE Liść ma postać zbioru par: wartość klucza indeksu, wskaźnik do rekordu (bloku danych) z tą wartością klucza (oznaczone jako Kk, Pk): , ,..., , Pnext>. W indeksach typu B*-drzewo, każdy liść ma dodatkowo wskaźnik do poprzedniego liścia. Wartości klucza indeksowego w liściu są uporządkowane. Każdy liść posiada co najmniej ⎣(p/2)⎦ wartości kluczy. OBLICZANIE RZĘDU INDEKSU Dane: rozmiar klucza V; rozmiar wskaźnika do bloku P; rozmiar bloku B; liczba rekordów w indeksowanym pliku danych r; liczba bloków pliku b Każdy z węzłów musi zmieścić się w pojedynczym bloku dyskowym - rząd B+-drzewa p jest największą liczbą całkowitą, dla której spełniona jest nierówność: (p∗P)+((p-1)∗V)) ≤ B Minimalna wysokość indeksu rzadkiego: h =⎾logpb⏋ Minimalna wysokość indeksu gęstego: h = ⎾logpr⏋ Liczba rekordów w bloku: rbl = B/R Liczba bloków danych: r/rbl OPERACJE NA B+ -drzewie • Koszt wyszukania rekordu bez pomocy indeksu – średnio: liczba bloków danych/2 • Koszt wyszukiwania rekordu za pomocą indeksu typu B+-drzewo: wysokość drzewa + 1 WSTAWIANIE REKORDÓW dla opornych Mamy wstawić element. Szukamy liścia, do którego pasuje. Sortujemy wartości w liściu i sprawdzamy, czy nie jest ich za dużo. Jeśli tak, ⎾n/2⏋elementów wyrzucamy do lewego liścia, pozostałe do prawego (tworzymy nowy liść). Największy element z lewego dodatkowo przekazujemy ‘w górę’ i znowu powtarzamy sprawdzenie, czy w tamtym wierzchołku jest za dużo. Jeśli tak, środkową wartość wyrzucamy wyżej, z tych po lewo tworzymy nowy wierzchołek, z tych po prawo też. Może się zdarzyć, że w ten sposób uzyskamy nowy korzeń.

5

2 Transakcje 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. Typy operacji na bazie danych obejmują: odczyt i zapis danych oraz zakończenie i akceptację (zatwierdzenie), lub wycofanie transakcji. Własności transakcji: • Atomowość - Zbiór operacji wchodzących w skład transakcji jest niepodzielny: albo zostaną wykonane wszystkie operacje transakcji albo żadna. • Spójność - Transakcja przeprowadza bazę danych z jednego stanu spójnego do innego stanu spójnego. W trakcie wykonywania transakcji baza danych może być przejściowo niespójna. Transakcja nie może naruszać ograniczeń integralnościowych • Izolacja - Transakcje są od siebie logicznie odseparowane. Transakcje oddziałują na siebie poprzez dane. Mimo współbieżnego wykonywania, transakcje widzą stan bazy danych tak, jak gdyby były wykonywane w sposób sekwencyjny • Trwałość - Wyniki zatwierdzonych transakcji nie mogą zostać utracone w wyniku wystąpienia awarii systemu. Zatwierdzone dane w bazie danych, w przypadku awarii, muszą być odtwarzalne Z punktu widzenia użytkownika, transakcja jest zbiorem poleceń języka SQL, tj. select, insert, update, delete, commit, rollback. Mówimy tu o tzw. transakcji logicznej. Na poziomie systemu zarządzania bazą danych mówimy o tzw. transakcji fizycznej, która jest zarządzana przez odpowiedni moduł SZBD. Transakcja fizyczna składa się z elementarnych operacji rozpoczęcia transakcji, operacji zaalokowania zasobów systemowych dla transakcji, blokowania danych (przy pewnych rozwiązaniach synchronizacji transakcji), operacji na samych danych, kończenia transakcji i zwalniania zasobów systemowych.

2.1 O transakcjach Transakcję Ti nazywamy uporządkowaną parę: Ti = ( 021 < 04 ) gdzie • Ti = { oj : 1 ≤ j ≤ ni}, oznacza zbiór operacji na bazie danych: { R - odczyt, W - zapis, C zatwierdzenie transakcji, A - wycofanie} 21 • < 04 jest relacją częściowego porządku na zbiorze 0 Przyjmiemy następującą notację: • ri(x) lub ri(x, wartość) • wi(x) lub wi(x, wartość) • ci lub ai Każda transakcja może być reprezentowana przez graf skierowany: G = (V, A), gdzie: V jest zbiorem węzłów odpowiadających operacjom transakcji Ti, A jest zbiorem krawędzi reprezentujących porządek na zbiorze operacji. Klasyfikacja transakcji • Ze względu na porządek operacji: o transakcja sekwencyjna o transakcja współbieżna • Ze względu na zależność operacji: o transakcja zależna od danych o transakcja niezależna od danych • Ze względu na typy operacji: o zapytania lub transakcja odczytu (read only) o transakcja aktualizująca - transakcja (read/write) 6

2.2 O realizacjach Realizacją S zbioru n transakcji T1, T2, ..., Tn nazywamy takie uporządkowanie operacji współbieżnie wykonywanych transakcji, w którym, dla każdej transakcji Ti w realizacji S, porządek wykonania operacji transakcji Ti jest taki sam jak porządek
2.3 Konflikty Jeżeli przynajmniej dwie operacje należące do różnych transakcji realizują dostęp do tej samej danej i przynajmniej jedna z tych operacji jest modyfikacją/zapisem danej, wówczas występuje konflikt w dostępie do tej danej. 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(5), co zapisujemy jako oi(x) oj(y), jeżeli operacje te s. konfliktowe i oi(x) Tj, jeżeli transakcje te zawierają odpowiednio operacje oi(x) i oj(x), między którymi zachodzi relacja poprzedzania. Mówimy, że dwie realizacje r(TAU) = (Tr(5) , oj(y), zachodzi również oi(x) oj(y) w realizacji r'(5). Realizacja r(5) zbioru transakcji 5 jest konfliktowo uszeregowalna wtedy i tylko wtedy, gdy jest ona konfliktowo równoważna dowolnej sekwencyjnej realizacji 5 Relacje uszeregowalne: Wykład 8

7

3 Algorytmy zarządzania współbieżnym wykonywaniem transakcji Klasyfikacja: • algorytmy blokowania - uszeregowanie transakcji wynika z kolejności uzyskiwanych blokad (algorytm blokowania dwufazowego – 2PL) • algorytmy znaczników czasowych – uszeregowanie transakcji wynika z wartości znaczników czasowych związanych z transakcjami • algorytmy optymistyczne - walidacja poprawności uszeregowania

3.1 Algorytmy blokowania Blokada jest zmienną skojarzoną z każdą daną w bazie danych, określającą dostępność danej ze względu na możliwość wykonania na niej określonych operacji Ze względu na proces blokowania, dane w bazie danych mogą występować w jednym z trzech stanów: • dana nie zablokowana (0) • dana zablokowana dla odczytu R (współdzielona S) • dana zablokowana dla zapisu W (wyłączna X) Kompatybilne są blokady do odczytu, natomiast pozostałe kombinacje blokad (RW, WR, WW) są niekompatybilne. Transakcja posiadająca blokadę określonego typu na danej może dokonać jej konwersji w blokadę innego typu. Dopuszczalna jest konwersja blokady typu R na blokadę typu W (nazywamy to operacją eskalacji blokad). Natomiast niedopuszczalna jest konwersja z blokady do zapisu (W) na blokadę do odczytu (R). Algorytm blokowania dwufazowego • Algorytm podstawowy o Każda operacja read(X) danej transakcji T musi być poprzedzona operacją R_lock(X, T) lub W_lock(X, T) o Każda operacja write(X) danej transakcji T musi być poprzedzona operacją W_lock(X, T). o Operacje unlock(x,T) dla danej transakcji T są wykonywane pozakończeniu wszystkich operacji read i write • Algorytm statyczny o Wszystkie blokady muszą być uzyskane przed rozpoczęciem transakcji (przez predeklarowanie zbioru odczytywanych i modyfikowanych danych). • Algorytm restryktywny o Operacje unlock(x,T) dla danej transakcji T są wykonywane po operacji commit lub rollback

3.2 Zakleszczenia Algorytmy zapobiegania zakleszczeniom: • 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 8

• •

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

Algorytmy wykrywania zakleszczeń • Graf WFG (waits-for graph) jest okresowo sprawdzany, czy wystąpił w nim cykl. Zakleszczenie jest rozwiązywane przez wycofanie jednej z transakcji należących do cyklu • Mechanizm timeout-u: jeżeli transakcja czeka zbyt długo na założenie blokady (przekroczyła czas timeput-u), możemy założyć, że wystąpiło zakleszczenie

3.3 Poziomy izolacji Transakcja może występować w dwóch trybach: READ ONLY i READ WRITE Jeżeli transakcja występuje w trybie READ ONLY, oznacza to, że transakcja jest zapytaniem i nie może modyfikować bazy danych. Dla transakcji w trybie READ ONLY, system zakłada wyłącznie blokady dla odczytu - prowadzi to do zwiększenia stopnia współbieżności Domyślnie, trybem wykonywania transakcji jest tryb READ WRITE, który pozwala na wykonywanie wszystkich typów operacji na bazie danych Poziomy ilozacji: • SERIALIZABLE - ten poziom izolacji gwarantuje, że każda transakcja T odczytuje dane utworzone wyłącznie przez zatwierdzone transakcje i że wartość żadnej danej, odczytywanej lub zapisywanej przez T, nie zostanie zmieniona przez inną transakcję do momentu zakończenia transakcji T. Ten poziom izolacji gwarantuje uszeregowalność wszystkich realizacji • REPEATABLE READ - ten poziom izolacji gwarantuje, że każda transakcja T odczytuje dane utworzone wyłącznie przez zatwierdzone transakcje i że wartość żadnej danej, odczytywanej lub zapisywanej przez T, nie zostanie zmieniona przez inną transakcję do momentu zakończenia transakcji T. Niestety, ten poziom izolacji nie gwarantuje rozwiązania problemu „duchów” i, stąd, nie gwarantuje uszeregowalności wszystkich realizacji • READ COMMITTED - ten poziom izolacji gwarantuje, że każda transakcja T odczytuje dane utworzone wyłącznie przez zatwierdzone transakcje i że wartość żadnej danej, zapisywanej przez T, nie zostanie zmieniona przez inną transakcję do momentu zakończenia transakcji T. Jednakże, poziom ten nie gwarantuje, że wartość danej odczytywanej przez transakcję T nie zostanie zmieniona przez inną transakcję do momentu zakończenia transakcji T. Ten poziom izolacji nie gwarantuje również rozwiązania problemu „duchów” i, stąd, nie gwarantuje uszeregowalności wszystkich realizacji • READ UNCOMMITTED - ten poziom izolacji dopuszcza odczyt przez transakcję T zmian dokonywanych przez aktywne jeszcze transakcje. Ten poziom izolacji jest dostępny tylko dla transakcji wykonywanych w trybie READ ONLY

9

4 Recovery Miękki model awarii – awaria nie niszczy danych w pamięci zewnętrznej Twardy model awarii - awaria niszczy dane w pamięci zewnętrznej Efektywność odtwarzania Miara efektywności odtwarzania: MTTF/ (MTTF + MTTR) MTTF – średni czas do awarii MTTR – średni czas odtworzenia po awarii Dostępność (całkowity czas – czas niedostępności)/całkowity czas

Więcej: Wykład 11

5 Optymalizacja zapytań Dla każdego planu wykonania zapytania optymalizator musi oszacować: • Szacunkowy koszt wykonania każdego operatora w planie zapytania (zależny od rozmiarów argumentów wejściowych operatora) • Szacunkowy rozmiar wyniku wykonania każdego operatora w planie zapytania (dane znajdują się w katalogu bazy danych, dla operacji selekcji i projekcji zakładamy niezależność atrybutów) Podstawowym źródłem informacji o relacjach, ich rozmiarach, itp. jest katalog bazy danych. Katalog bazy danych zawiera informacje o: • liczbie krotek każdej relacji R (card(R)) i liczbie stron (Pcard(R)) dla każdej relacji, czasami katalog przechowuje również informacje o liczbie różnych wartości każdego atrybutu relacji (val(A[R]), • liczbie różnych wartości atrybutu (NKeys) i liczbie stron dla każdego indeksu, • wysokości indeksu, minimalnej i maksymalnej wartości klucza indeksu (Low/High).

Współczynnik selektywności (sf) związany z każdym predykatem term odzwierciedla wpływ predykatu term na redukcję rozmiaru wyniku

5.1 Szacowanie rozmiarów i współczynnik selektywności • • • • •

Rozmiar wyniku = max liczba krotek * iloczyn wszystkich sf Założenie: predykaty niezależne Predykat atrybut=wartość, wsp. selektywności sf = 1/val(atr), gdzie atr oznacza atrybut (patrz selekcja) Predykat atrybut=wartość , wsp. selektywności sf = 1/NKeys(I), jeżeli dany jest indeks I na atrybucie Predykat atr1=atr2, wsp. selektywności sf = 1/MAX(NKeys(I1), NKeys(I2)), dane indeksy I1 i I2 Predykat atr > wartość wsp. Selektywności sf = (High(I)-value)/(High(I)-Low(I))

5.2 Szacowanie rozmiarów selekcji Niech S oznacza wynik wykonania operacji selekcji na relacji R . Rozmiar relacji (card) – z każdą selekcją związany jest współczynnik selektywności określający procent krotek spełniających predykat selekcji, dla prostego predykatu selekcji (Atrybut = wartość), sf definiujemy następująco: sf = 1/val(A[R]) 10

przy założeniu równomiernego rozkładu wartości krotek. Stąd: card(S) = sf * card(R) Szerokość (size): selekcja nie wpływa na szerokośćwynikowej relacji: size(S) = size(R) Liczba różnych wartości (val) : zależy od predykatu selekcji.

5.3 Szacowanie rozmiarów Projection Rozmiar relacji (card) – projekcja wpływa na rozmiar relacji w przypadku usuwania duplikatów. Efekt trudny do oszacowania. Stosuje się trzy reguły do oszacowania • Projekcja na pojedynczym atrybucie A: card(S) = val(A[R]) • Jeżeli iloczyn Π Ai∈Attr(S) val(Ai[R]) mniejszy niż card(R), gdzie Attr(S) to zbiór atrybutów należący do wyniku projekcji, wówczas card(S) = Π Ai∈Attr(S) val(Ai[R]) • Jeżeli projekcja zawiera klucz relacji R, wówczas card(S) = card(R) • Jeżeli projekcja nie eliminuje duplikatów, wówczas card(S) = card(R) Szerokość (Size): szerokość wyniku projekcji jest równa sumie rozmiarów atrybutów wyspecyfikowanych w projekcji Liczba różnych wartości: liczba różnych wartości atrybutów należących do wyniku projekcji S identyczna z liczbą różnych wartości tych samych atrybutów w relacji R

5.4 Szacowanie rozmiarów GROUP BY Niech G oznacza zbiór atrybutów, na którym wykonywana jest operacja grupowania Rozmiar relacji – górne ograniczenie rozmiaru S: card(S) < Π Ai∈G val(Ai[R]) Szerokość: dla wszystkich atrybutów A należących do G: size(R.A) = size (S.A) Liczba różnych wartości: dla wszystkich atrybutów A należących do G val(A[S]) = val(A[R])

5.5 Szacowanie rozmiarów UNION Niech T oznacza wynik wykonania operacji sumy na relacjach R i S Rozmiar relacji: card(T) < card(R) + card(S) Równość zachodzi w przypadku, gdy nie eliminujemy duplikatów Szerokość: size(T) = size(R) = size(S) Liczba różnych wartości : górna granica wynosi: val(A[T]) < val(A[R]) + val(A[S])

5.6 Szacowanie rozmiarów JOIN Rozmiar relacji: oszacowanie rozmiaru relacji T będącej wynikiem połączenia relacji R i S jest bardzo trudne, górne ograniczenie rozmiaru: card(T) < card(R) x card(S) ale jest to bardzo duże przybliżenie. Najczęściej podaje się następujące przybliżenie rozmiaru relacji T: card(T) = (card(R) x card(S))/max{val(A[R]), val(A[S])} gdzie A oznacza atrybut połączeniowy relacji R i S

11

Szerokość: size(T) = size(R) = size(S) W przypadku połączenia naturalnego od szerokości wyniku odejmujemy szerokość atrybutu połączeniowego Liczba różnych wartości : jeżeli A jest atrybutempołączeniowym, górne ograniczenie wynosi: val(A[T]) < min(val(A[R]), val(B[S])) jeżeli A nie jest atrybutem połączeniowym, górne ograniczenie wynosi: val(A[T]) < val(A[R]) + val(B[S]))

5.7 Histogramy Umożliwiają uzyskanie znacznie dokładniejszych oszacowań rozmiarów wyników wykonania operacji. Różne wersje: • Equi-depth (równa liczba wartości dla pojedynczego interwału) • Equi-width (równa szerokość każdego interwału) Przykład: Oszacowanie wyniku operacji połączenia zwykłą metodą (card(R)* card(S)) / max{val(A[R]), val(A[S]) Oszacowanie z histogramem: Σicardi(R)* cardi(S) gdzie i – kolejne przedziały w histogramie

Więcej: Wykład 13

12