Databáze
2011/2012
Logický model DB
RNDr.David Hoksza, Ph.D.
http://siret.cz/hoksza
Osnova
• Relační model dat
• Převod konceptuálního schématu do logického
• Funkční závislosti
• Normalizace schématu
• Cvičení – převod do relačního modelu
Relační logický model
(neformálně)
• 1974 - E. F. Codd
• reprezentace objektů konceptuálního schématu
pomocí tabulek (relací)
o entitní (vztahový) typ → tabulka
o atribut → sloupec
o entita (vztah) → řádek tabulky
• schéma tabulky
o T(S1:T1, …, Sn:Tn) – T = tabulka, Si = sloupec i, Ti = datový typ sloupce i
• schéma DB
o schémata všech tabulek v DB + případná integritní omezení
Relační model
(neformálně)
• Neexistují 2 stejné řádky, tj. každá tabulka má
jednoznačný identifikátor
• Relační model nezná pojem NULL hodnoty
o lze zavést metadhonotu NULL
• Množina sloupců jednoznačně identifikující řádky tabulky
se nazývá nadklíč
• Nadklíč s nejmenším počtem sloupců se nazývá klíč
o klíčů může být více
• Množinu sloupců, které jsou klíčem v jiné tabulce
nazýváme cizí klíč
o realizace vatahů mezi entitami
Relační model (formálně)
• relace v algebře
o R ⊆ D1 x D2 x … x Dn
• databázové rozšíření pojmu relace
o R(A1:D1, …, An:Dn)
o zjednodušeně R(A1, …, An)
• formální vs. neformální
o
o
o
o
schéma relace – schéma tabulky
relace – tabulka (data)
doména – datový typ sloupce
prvek relace – řádek tabulky
• dále budeme používat zjednodušený relační model
k popisu principů převodu konceptuálního
schématu do relačního
Cizí klíč - princip
automobil(spz:string, majitel:string, rok_vyroby:integer, znacka:string)
spz
majitel
rok_vyroby
znacka
1A3 3040
Petr Novák
1980
Ford
ANE 0689
Aleš Vomáčka
2005
Honda
1T8 1230
Josef Novotný
2000
Honda
2B1 3491
Karel Vodrážka
2005
Škoda
znacka
zeme
Ford
USA
Honda
JP
Škoda
CZ
vyrobce(znacka:string, zeme:string)
klíč
cizí klíč
Převod – kardinalita 1:1
• V 1:1 kardinalitě může
libovlný z klíčů
účastnících se entit být
klíčem výsledného
relačního schématu
linkaridic(cislo, start, cil, …, id, jmeno, rok_narozeni, …)
linka(cislo, start, cil, …, id),
ridic(id, jmeno, rok_narozeni, …)
• Při nepovinné účasti
je třeba zvláštní relaci
pro řidiče, který ve
vztahu být nemusí
Převod – kardinalita 1:1
linka(cislo, start, cil, …)
• Při nepovinné účasti
obou entit je třeba
vytvořit novou relaci,
protože každý objekt v
jedné entitě může
existovat nezávisle na
objektu v entitě druhé
linkaridic(cislo, id)
ridic(id, jmeno, rok_narozeni, …)
• Protože jsou kardinality
na obou stranách 1,
tvoří každý z cizích klíčů
ve spojovací relaci klíč
v této relaci
Převod – kardinalita 1:N
linka(cislo, start, cil, …)
• Kardinalitu N zajišťuje
cizí klíč cislo v relaci
ridic, kde nehraje roli
klíče (atribut není
podtržen), na rozdíl
od (0,1):(1,1) situace
• Parcialitu na N straně
ridic(id, jmeno, rok_narozeni, cislo) nejsme schopni v
základním relačním
modelu zajistit, proto
ke 2 ER schématům
máme 1 relační
schéma
Převod – kardinalita 1:N
linka(cislo, start, cil, …)
linkaridic(cislo, id)
ridic(id, jmeno, rok_narozeni)
• Parcialitu na 1 straně
zajistíme vložením
spojovací relace, která
bude mít id jako klíč.
Výsledek je podobný
jako (0:1):(0:1) až na
nejednoznačnost
atributu cislo ve
spojovací relaci
• Parcialitu na N straně
nejsme schopni v
základním relačním
modelu zajistit, proto ke
2 ER schématům
máme 1 relační
schéma
Převod – kardinalita M:N
linka(cislo, start, cil, …)
linkaridic(cislo, id)
ridic(id, jmeno, rok_narozeni)
• Ve vztahu M:N nejsme
schopni v relačním
modelu zajistit
parcialitu, neboť
každý objekt jedné
entity muže být ve
vztahu s více objekty
druhé entity → nutnost
spojovací relace
• Klíčem ve spojovací
relaci nemůže být ani
jeden z cizích klíčů,
nýbrž klíč musí tvořit
oba cizí klíče
najednou
Funkční závislost – př.
• funkční závislost určuje sémantické vztahy mezi
atributy
značení
• RC → JMENO
čtení
význam
• Rodné číslo
funkčně
určuje jméno
RČ
…
JMENO
…
870226/5385
…
Karel Vomáčka
…
890610/1182
…
David Mikeš
…
880906/5595
…
Jan Novák
…
870226/5385
…
Patrik Nový
…
• Ke každému RČ
existuje nejvýše
jedno jméno
=
• Neexistují 2
záznamy v
tabulce řidič se
stejným RČ, ale
různým jménem
Funkční závislost – př.
čtení
značení
• {START, CIL} →
CISLO
význam
• Start a cíl
funkčně
určuje číslo
CISLO
…
START
CIL
…
106
…
Kavkazská
Nádraží
Braník
…
203
…
Kačerov
Vavřenova
…
308
…
Kavkazská
Nádraží
Braník
…
205
…
Zemanka
Komořany
…
• Ke každému
startu a cíli
existuje nejvýše
jedno číslo
=
• Neexistují 2
záznamy v
tabulce linka se
stejným startem
a cílem, ale
různým číslem
Funkční závislost – formálně
• Funkční závislost (FZ) je funkce mezi doménami
atributů
• FZ je typem integritního omezení, tj. vymezuje jaká
data mohou být v DB uložena, případně vymezuje
vztahy mezi nimi
• Definice:
Funkční závislost (FZ) X → Y nad schématem
R(A) je parciální zobrazení fi: Xi → Yi, kde Xi,Yi⊆A
(kde i = 1..počet závislostí pro R(A)). Říkáme že ntice z Xi funkčně určuje m-tici z Yi a že m-tice z Yi
funkčně závisí na n-tici z Xi
Funkční závislost a relační
model
• relační model lze rozšířit tak, aby bylo možné v něm
uchovávat informace o závislostech, tj. u relace
nebudeme uchovávat pouze seznam atributů, ale i
funkční závislosti mezi nimi
o R(A, F), kde F = ∪i{fi}
• nadklíč relace NK
o NK → A
• klíč relace K
o K → A ∧ ∄ K1: K1 ⊇ K
• klíčový atribut
o atribut z A, který je součástí nějakého klíče (klíčů může být více)
• neklíčový atribut
o atribut z A, který není součástí žádného klíče
Návrh funkčních
závislostí
• modelování funkčních závislostí spadá do procesu funkční
analýzy, tj. je třeba jej učinit ještě před vkládáním dat. To
plyne i z faktu, že se jedná o IO, tedy omezuje možné vstupy
• není možné FZ odvozovat ze stávajících dat, nýbrž z
přirozených vztahů mezi atributy
ID JMENO
NAJETE_K
M_ZA_ME
SIC
ODPRAC PLAT
OVANO_
LET
VEK
1
Petr
Malý
412
20
18000
48
2
Jan
Vostrý
654
10
19000
35
3
Aleš
Nový
412
20
18000
44
• ID → ALL
• JMENO →
ALL
• NJKZM → OL
• OL → NJKZM
• {NJKZM, OL}
→ PLAT
• VEK → VSE
4
Petr
Berka
128
15
17000
50
ne vše, co vidíme v
datech obecně platí
Aktualizační anomálie
• mějme relaci
o AUTOBUS(SPZ, NAJETO, …, SOUCASTKA, VYROBCE_SOUCASTKY, …)
o součástky uchováváme v relaci s autobusy, tj. má-li autobus 20
součástek, máme 20 prvků relace v tabulce autobus pro jeden autobus
• příklady aktualizačních anomálií
o změna informace o konkrétním autobusu vyžaduje vícenásobné
provedení této změny
o chceme-li odstranit jeden autobus z DB, je třeba to učinit na více místech
o není-li součástka použita v žádném autobusu, informaci o ní ztrácíme
o nelze přidat součástku do DB, aniž by nebyla použita v nějakém autobuse
Normalizace schématu
• Normalizaci lze zajisti dekompozicí tak, aby výsledné
schéma splňovalo požadavky dané normální formy
• 1NF zajišťuje nestrukturovanost dat
• 2NF a 3NF omezují redundanci dat, tj. nutí uživatele
dekomponovat schéma
• Další NF, které nejsou v praxi často využívány
o BCNF
o 4NF
o 5NF
• Výhody
o Snížení redundance dat → menší prostorové nároky
o Jednodušší aktualizace dat
o Zabránění aktualizačním anomáliím
• Nevýhody
o Zpomalení komplexních dotazů
1NF
1. tabulka musí reprezentovat relaci v algebraickém smyslu
o
atributy vnitřně nestrukturované (žádné vnořené tabulky, nebo složené datové typy,
tj. jako domény je třeba užít základní datové typy)
2. neexistence opakujících se skupin
• osoba(id:integer, jmeno:string, datum_narozeni:date,
podrizeni:osoba[])
• osoba(id:integer, jmeno:string, datum_narozeni:date)
• osobaosoba(id_pod:integer, id_nad:integer)
• osoba(id:integer, jmeno:string, datum_narozeni:date,
tel1:string, tel2:string, tel3:string)
• osoba(id:integer, jmeno:string, datum_narozeni:date)
• osobatelefon(cislo:string, id_osoba:integer)
o
1NF odporuje i situace, kdy je pro telefon použit jeden sloupec typu string, kde jsou
telefony odděleny delimitorem
2NF
• v DB se nesmí vyskytovat závislost neklíčového
atributu NK na vlastní podmnožině některého klíče K
o ∄ ⊂ :  → 
není v 2NF
JMENO
C_ZIDLE
BUDOVA ADRESA
PLAT
Jan Vodnář
58
A
Technická 5, Praha
24000
Petr Novotný 58
B
Technická 3, Praha
20000
Karel Kolář
2
A
Technická 5, Praha
18000
Patrik Nový
23
C
Studentská 1, Praha
35000
Aleš Výmola
45
B
Technická 3, Praha
28000
• {C_ZIDLE,BUDOVA} → ALL, BUDOVA → ADRESA
• redundance adresy
2NF - dekompozice
JMENO
C_ZIDLE
BUDOVA PLAT
Jan Vodnář
58
A
24000
Petr Novotný 58
B
20000
Karel Kolář
2
A
18000
Patrik Nový
23
C
35000
Aleš Výmola
45
B
28000
{C_ZIDLE,BUDOVA} → ALL … 2NF
BUDOVA ADRESA
A
Technická 5, Praha
B
Technická 3, Praha
C
Studentská 1, Praha
BUDOVA → ADRESA … 2NF
3NF
• v DB se nesmí vystkytnout tranzitivní závislost na klíči K
o ∄, :  →  → 
není v 3NF
JMENO
PSC
MESTO
PLAT
Jan Vodnář
14200
Praha
24000
Petr Novotný
10100
Praha
20000
Karel Kolář
60200
Brno
18000
Patrik Nový
66434
Kuřim
35000
Aleš Výmola
63900
Brno
28000
• JMENO → VSE, PSC → MESTO ⇒ JMENO → PSC →
MESTO
• reundance města
o může být problematické, když k se rozhodneme uchovávat další informace
o městě, např. počet obyvatel
3NF – dekompozice
JMENO
PSC
PLAT
Jan Vodnář
14200
24000
Petr Novotný
10100
20000
Karel Kolář
60200
18000
Patrik Nový
66434
35000
Aleš Výmola
63900
28000
JMENO → ALL … 3NF
PSC
MESTO
14200
Praha
10100
Praha
60200
Brno
66434
Kuřim
63900
Brno
PSC→ MESTO … 3NF
Download

2 nd round