• Proces identyfikowania logicznych związków
między elementami danych
• Proces projektowania baz danych, który będzie
identyfikować takie związki - bez anomalii
Anomalia baz danych nienormalizowanych:
•anomalia dołączania
•anomalia aktualizacji
•anomalia usuwania
Normalizacja
Normalizacja
W celu wykonania normalizacji danych
potrzebujemy:
• zrozumienia zależności funkcyjnej – w
przypadku baz danych często jesteśmy
zainteresowani zależnościami funkcyjnymi
pomiędzy kolumnami
• zdrowego rozsądku
• zrozumienia znaczenia danych – nazywamy to
definicją wymagań
• zrozumienia oczekiwań zleceniodawcy w
stosunku do bazy danych
• znajomości procesu normalizacji
Proces normalizacji można traktować jako proces,
podczas którego schematy relacji posiadające
niepożądane cechy są dekomponowane na
mniejsze schematy o pożądanych własnościach.
• Dekompozycja - podział atrybutów tabeli R między
dwa schematy nowych tabel
• Reguła dekompozycji obejmuje również podział
wierszy tabeli R między nowe tabele
• Tabelę R o schemacie {A1, A2,…An} dekomponujemy
na dwie tabele: S - {B1, B2,…Bm} oraz T - {C1,C2,…
Ck} wg zasad:
– {A1, A2,…An} = {B1, B2,…Bm} {C1,C2,…Ck}
– Wiersze relacji S i T powstają przez projekcję
wszystkich wierszy relacji R na zbiór atrybutów
odpowiednio {B1, B2,…Bm} i {C1,C2,…Ck}
Normalizacja
• Celem normalizacji jest minimalizacja
fizycznego rozmiaru bazy danych oraz
uniknięcie anomalii związanych z
wstawianiem, aktualizacją i usuwaniem
wierszy.
• Proces normalizacji musi posiadać trzy
własności:
1. Żaden atrybut nie może zostać zagubiony
w trakcie procesu normalizacji
2. Dekompozycja tabeli nie może prowadzić
do utraty informacji
3. Wszystkie zależności funkcyjne muszą
być reprezentowane w pojedynczych
schematach tabel
Normalizacja
• Tabela jest w pierwszej postaci normalnej, jeśli
każda wartość atrybutu w każdym wierszu tej
tabeli jest wartością elementarną, czyli
nierozkładalną (atomową).
• 1NF zabrania definiowania złożonych
atrybutów, które są wielowartościowe.
• Tabele, które dopuszczają definiowanie
złożonych atrybutów to tabele zagnieżdżone
(koncepcja ta nie mieści się w ramach
klasycznego relacyjnego modelu)
Pierwsza postać normalna 1PN (1NF)
Zamówienia
Numer id Nazwa Adres Id Nazwa
części ilość
zamówienia dostawcy dostawcy dostawcy części
1
010
Seagate
Szlak 24
33
Dysk twardy
5
34
Sterownik
I/O
30
2
020
Toshiba
Długa 5
70
Napęd CD
10
3
010
Seagate
Szlak 24
33
Dysk twardy
50
70
Napęd CD
20
Zamówienia
Numer id Nazwa Adres Id Nazwa
części ilość
zamówienia dostawcy dostawcy dostawcy części
1
010
Seagate
Szlak 24
33
Dysk twardy
5
1
010
Seagate
Szlak 24
34
Sterownik
I/O
30
2
020
Toshiba
Długa 5
70
Napęd CD
10
3
3
010
010
Seagate
Seagate
Szlak 24
Szlak 24
33
Dysk twardy
50
70
Napęd CD
20
Definicja zależności funkcyjnej
Atrybut B tabeli R jest funkcyjnie zależny od
atrybutu A tej tabeli, jeżeli zawsze każdej
wartości a trybutu A odpowiada nie więcej
niż jedna wartość b atrybutu B
Numer zamówienia
Id dostawcy
Nazwa dostawcy
Adres dostawcy
Id części
Nazwa części
Ilość
Zależności funkcyjne między atrybutami tabeli zamówienia
Wszystkie zależności funkcyjne w tabeli ZAMÓWIENIA
są pełnymi zależnościami funkcyjnymi
Definicja pełnej zależności funkcyjnej
Atrybut A jest w pełni zależny funkcjonalnie
od
zbioru atrybutów X, gdy jest zależny
funkcjonalnie
od całego zbioru, a nie od podzbioru
atrybutów z X
Tabela R jest w drugiej postaci
normalnej, jeśli jest w pierwszej postaci
normalnej i każdy atrybut tej tabeli nie
wchodzący w skład klucza jest w pełni
funkcyjnie zależny od wszystkich kluczy
potencjalnych tej tabeli (jest w pełni
zależny od klucza )
Druga postać normalna 2PN (2NF)
Dostawca (na zamówieniu)
Numer id Nazwa Adres
zamówienia dostawcy
dostawcy dostawcy
1
010
Seagate
Szlak 24
2
020
Toshiba
Długa 5
3
010
Seagate
Szlak 24
Zamówienie dostawy
Numer id
zamówienia Części
ilość
1
33
5
1
34
30
2
70
10
3
33
50
3
70
20
Części
33
Dysk twardy
34
Sterownik
I/O
35
Napęd CD
id Nazwa
części części
Numer zamówienia
Id dostawcy
Nazwa dostawcy
Adres dostawcy
Id części
Nazwa części
Ilość
Numer zamówienia
Id części
Zamówienie dostawy
Części
Dostawcy
W tabeli DOSTAWCA (na zamówieniu)
atrybuty nazwa i adres dostawcy są
przechodnio funkcyjnie zależne od
atrybutu nr_zamówienia, gdyż atrybuty
nazwa i adres są funkcyjnie zależne od
id_dostawcy, a ten atrybut jest
funkcyjnie zależny od nr_zamówienia
A
B
C
Przechodnie zależności funkcyjnych
Schemat usuwania przechodnich zależności
funkcyjnych
A
B
C
A
B
B
C
Numer zamówienia
Id dostawcy
Nazwa dostawcy
Adres dostawcy
Id części
Nazwa części
Ilość
Numer zamówienia
Id części
Zamówienie dostawy
Części
Dostawcy
Zależności funkcyjne i przechodnie zależności funkcyjne
Tabela R o danym schemacie jest w trzeciej
postaci normalnej, jeżeli jest w drugiej postaci
normalnej i żaden atrybut nie wchodzący w
skład klucza potencjalnego tej tabeli nie jest
przechodnio zależny od żadnego klucza
potencjalnego tej tabeli
Trzecia postać normalna 3PN (3NF)
każdy atrybut musi być w pełni zależny od
klucza głównego
i niezależny od pozostałych atrybutów
Zamówienia
Dostawcy
Numer Numer
zamówienia dostawcy
1
010
2
020
3
010
Id Nazwa Adres
dostawcy dostawcy dostawcy
010
Seagate
Szlak 24
020
Toshiba
Długa 5
030
Sony
Warszawska
5
Numer id Nazwa Adres
zamówienia dostawcy
dostawcy dostawcy
1
010
Seagate
Szlak 24
2
020
Toshiba
Długa 5
3
010
Seagate
Szlak 24
Dostawca (na zamówieniu)
Diagramy zależności funkcyjnych w 3NF
Numer zamówienia
Id dostawcy
Id części
Nazwa części
Id dostawcy
Nazwa dostawcy
Adres dostawcy
Dostawcy
Zamówienie
Części
Normalizacja
Normalizacja
• Relacja jest w 1 PN jeśli każdy jej atrybut ma
wartości atomowe i każdy atrybut niekluczowy
jest funkcyjnie zależny od klucza głównego
• Relacja jest w 2 PN jeśli jest w 1 PN i każdy
atrybut niekluczowy jest w pełni funkcyjnie
zależny od klucza głównego
• Relacja jest w 3 PN jeśli jest w 2 PN i każdy
atrybut niekluczowy jest bezpośrednio (a nie
pośrednio) zależny od klucza głównego
Poziomy normalizacji
Tabela ma postać BCNF, gdy każdy
atrybut tabeli zależy funkcjonalnie tylko
od klucza podstawowego
Postać normalna BCNF
(Boyce-Codd normal form)
Postacią normalną, która rzeczywiście
usuwa wszystkie zależności przechodnie
jest postać BCNF
Tabela nieznormalizowana
Tabela znormalizowana
Przykładowo w relacji PRACOWNICY podzbiór
X={Nazwisko_pracownika}, Y={język_programowania},
R-X-Y = {Język_obcy}
Parze wierszy (krotek)
Dana tabela jest w czwartej postaci
normalnej, wtedy i tylko wtedy, gdy jest
w trzeciej postaci normalnej i
wielowartościowa zależność podzbioru Y
od X pociąga za sobą funkcjonalną
zależność wszystkich atrybutów tej tabeli
od X
Czwarta postać normalna 4PN (4NF)
Tabela jest w piątej postaci normalnej
gdy jest w czwartej postaci normalnej i
gdy zależność połączeniowa (w
przypadku jej występowania ) wynika z
zależności od klucza
Piąta postać normalna 4PN (4NF)
PRZETWARZANIE ZAPYTAŃ TO:
PRZETWARZANIE ZAPYTAŃ TO:
przekształcenie zapytania zapisanego w
języku wysokiego poziomu, zazwyczaj SQL,
w poprawną efektywną sekwencję operacji
niskiego poziomu (operacje algebry relacji)
oraz wykonanie tej sekwencji operacji w
celu uzyskania poszukiwanych danych
Zapytanie jest poddawane
przetwarzaniu w następujących
etapach:
1. Analiza składniowa
2. Poprawność zapytania względem informacji
przechowywanej w słowniku bazy danych
3. Optymalizacja zapytania
4. Wykonanie zapytania
5. Zwrot do użytkownika wyników zapytania lub
komunikatów o błędach
Fazy procesu przetwarzania zapytania
Fazy procesu przetwarzania zapytania
Rozkład
Rozkład
zapytania
zapytania
Optymaliza
Optymaliza
cja
cja
zapytania
zapytania
Generowani
Generowani
e kodu
e kodu
Wykonanie
Wykonanie
zapytania
zapytania
Kompilacja
Kompilacja
Wykonanie
Wykonanie
Wynik
Wynik
zapytani
zapytani
a
a
Katalog
Katalog
systemowy
systemowy
Statystyki bazy
Statystyki bazy
danych
danych
Główna baza
Główna baza
danych
danych
Wygenerowany
Wygenerowany
kod
kod
Plan
Plan
wykonania
wykonania
Wyrażenie algebry relacji
Wyrażenie algebry relacji
Zapytanie w języku
Zapytanie w języku
wysokiego
wysokiego
poziomu (SQL)
poziomu (SQL)
OPTYMALIZACJA ZAPYTAŃ
OPTYMALIZACJA ZAPYTAŃ
• Optymalizacja dynamiczna – powtarzanie rozkładu
i optymalizacji za każdym razem, gdy zapytanie
jest wykonywane.
• Optymalizacja statyczna – analiza składni,
kontrola poprawności i optymalizacja jest
wykonywana tylko raz (podejście podobne do
stosowanego w kompilatorach języków
programowania).
• Można stosować połączenie tych strategii,
wówczas ponowna optymalizacja ma miejsce
wówczas, gdy system wykryje, że w statystykach
zaszły poważne zmiany od ostatniej kompilacji.
Rozkład zapytania - przykład drzewa algebry
Rozkład zapytania - przykład drzewa algebry
relacji
relacji
Persone
l
Biuro
liście
Operacje
pośredni
e
Stanowisko=’dyrekto
r’
miasto=’Londy
n’
nrbiura=biuronr
Korzeń
SELECT *
SELECT *
FROM Personel, Biuro
FROM Personel, Biuro
WHERE nrbiura=biuronr AND
WHERE nrbiura=biuronr AND
(stanowisko=’dyrektor’ AND miasto=’Londyn’)
(stanowisko=’dyrektor’ AND miasto=’Londyn’)
Etap normalizacji
Etap normalizacji
• Koniunktywna postać normalna – składa
się z ciągu czynników połączonych
operatorem koniunkcji. Każdy czynnik składa
się z kilku członów połączonych operatorami
alternatywy.
• Dysjunktywna postać normalna – składa się
z ciągu składników połączonych operatorem
alternatywy. Każdy składnik składa się z kilku
członów połączonych operatorem koniunkcji.
Analiza semantyczna
Analiza semantyczna
• Analiza semantyczna ma na celu odrzucenie
tych spośród znormalizowanych zapytań,
które są źle sformułowane lub sprzeczne.
• Zapytanie jest źle sformułowane, jeżeli jego
elementy nie prowadzą do wygenerowania
wyniku, co może się zdarzyć na skutek
pominięcia specyfiki złączenia.
• Zapytanie jest sprzeczne – jeżeli jego
warunek nie może być spełniony przez żaden
wiersz.
Istnieją dwie klasy optymalizatorów
Istnieją dwie klasy optymalizatorów
używanych we współczesnych
używanych we współczesnych
relacyjnych SZBD
relacyjnych SZBD
• optymalizatory
oparte
na
składni
(nazywane też opartymi na heurystyce) -
wybierają plan wykonania na podstawie
składni instrukcji SQL. Decyzja jest
podejmowana
na
podstawie
takich
wielkości
jak:
postać
i
kolejność
warunków w klauzuli WHERE.
.
• optymalizatory oparte na statystyce
(oparte na koszcie)
OPTYMALIZACJA ZAPYTAŃ
OPTYMALIZACJA ZAPYTAŃ
• Zapytania są kompilowane - plany wykonań są
tworzone na etapie kompilacji i składowane do
późniejszego użycia.
• Zapytania interpretowane – wszystkie zapytania są
interpretowane w czasie wykonania.
• Zapytania kompilowane są wykonywane szybciej niż
interpretowane - ponieważ w przypadku powtórnego
zapytania kompilacja nie musi być wykonana
ponownie.
• Jeśli jednak baza danych jest przedmiotem wielu
zapytań kierowanych do niej ad hoc, to zapytania
interpretowane są bardziej elastyczne, ponieważ nie
są przedmiotem wcześniejszego etapu kompilacji.
OPTYMALIZACJA ZAPYTAŃ
OPTYMALIZACJA ZAPYTAŃ
W SYSTEMIE ORACLE
W SYSTEMIE ORACLE
•
Optymalizacja oparta na regułach - wykorzystuje
15 reguł, które zostały przedstawione w kolejności
spodziewanego wpływu na efektywność.
Optymalizator może wybrać konkretną ścieżkę
dostępu do tabeli tylko wówczas, gdy zapytanie
zawiera odpowiedni warunek lub istnieje struktura
umożliwiająca określony sposób dostępu
•
Optymalizator oparty na analizie kosztów –
wybiera strategię wykonania zapytania wymagającą
najmniejszych zasobów do przetworzenia wszystkich
wierszy, do których odwołuje się zapytanie.
Użytkownik może wybrać, czy optymalizowanym
zasobem ma być przepustowość, czy czas odpowiedzi.
OPTYMALIZACJA ZAPYTAŃ SYSTEMIE
OPTYMALIZACJA ZAPYTAŃ SYSTEMIE
ORACLE
ORACLE
1
Jeden wiersz wg identyfikatora wiersza
2
Jeden wiersz wg indeksu grupującego
3
Jeden wiersz wg indeksu haszującego dla klucza
unikalnego lub głównego
4
Jeden wiersz wg klucza unikalnego lub głównego
5
Wykorzystanie klastra
6
Grupujący klucz haszujący
7
Klucz indeksu grupującego
8
Klucz złożony
9
Indeks wg pierwszej kolumny
10 Poszukiwanie zakresu dla kolumny z indeksem
11 Poszukiwanie bez ograniczeń dla kolumny z indeksami
12 Złączenie przez scalanie posortowanych relacji
13 MAX lub MIN dla kolumny z indeksem
14 ORDER BY dla kolumny z indeksem
15 Przeszukiwanie całej tablicy
OPTYMALIZACJA ZAPYTAŃ
OPTYMALIZACJA ZAPYTAŃ
W SYSTEMIE ORACLE
W SYSTEMIE ORACLE
• Działanie optymalizatora opartego na analizie kosztów
zależy od zgromadzonych statystyk dla tabel, klastrów oraz
indeksów.
• Sam Oracle nie zbiera tych statystyk automatycznie –
generuje je i uaktualnia tylko na polecenie użytkownika.
• Proces gromadzenia statystyk jest regulowany przez liczne
opcje, gdy tylko jest to możliwe.
• Gdy zostanie wyznaczony optymalny plan wykonania
zapytania, można go zapisać poleceniem CREATE OUTLINE,
które pozwala przechować atrybuty wykorzystane przez
optymalizator do stworzenia planu wykonania.
• W trakcie późniejszych wykonań zapytania, optymalizator
korzysta z zapisanych atrybutów i wykonuje gotowy plan
zapytania, zamiast generować go od nowa.
• System Oracle pozwala obejrzeć plan wykonania wybrany
przez optymalizator poleceniem EXPLAIN PLAN. Przydaje
się to szczególnie wtedy, gdy efektywność wykonania
zapytania nie spełnia naszych oczekiwań. Wynik polecenia
EXPLAIN PLAN jest zapisywany w tabeli bazy danych
(domyślnie PLAN_TABLE).