• 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).