DatabázeLogický model DB

David Hoksza

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ě(1)• 1974 - E. F. Codd

• reprezentace objektů konceptuálního schématu pomocí (matematických) relací (lze reprezentovat tabulkou) + dotazovací jazyk (relační kalkul, relační algebra)• entitní (vztahový) typ → relace (tabulka)• atribut → atribut relace definované domény (sloupec)• entita (vztah) → n-tice (řádek tabulky)

• schéma relace (tabulky)• T(S1:T1, …, Sn:Tn) – T = tabulka, Si = sloupec i, Ti = datový typ sloupce i

• schéma DB• schémata všech tabulek v DB + případná integritní omezení

Relační logický model (neformálně) - příklad

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

automobil(spz:string, majitel:string, rok_vyroby:integer, znacka:string)

Relační logický model -neformálně (2)

• Narozdíl od tabulky, relace neobsahují duplicitní entice, tj. přesné mapování by vyžadovalo, aby každá tabulka měla jednoznačný identifikátor

• Množina sloupců jednoznačně identifikující řádky tabulky se nazývá nadklíč

• Nadklíč s nejmenším počtem sloupců se nazývá klíč• klíčů může být více

• Množinu sloupců, které jsou klíčem v jiné tabulce nazýváme cizí klíč• realizace vztahů mezi entitami

• Relační model nezná pojem NULL (neznámé/nevyplněné) hodnoty• lze zavést metahodnotu NULL

Cizí klíč - princip

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

automobil(spz:string, majitel:string, rok_vyroby:integer, znacka:string)

vyrobce(znacka:string, zeme:string)

klíč

cizí klíč

automobil(znacka) ⊆ vyrobce(znacka)

Relační model (formálně)• relace

• 𝑹 ⊆ 𝑫𝟏 ×⋯×𝑫𝒏 𝐷𝑖 … doména (datový typ) 𝑖

• databázové rozšíření pojmu relace• 𝑹(𝑨𝟏: 𝑫𝟏, … . , 𝑨𝒏: 𝑫𝒏)

• Relace 𝑅 nad množinou atributů 𝐴1, … , 𝐴𝑛 z domén 𝐷1, … , 𝐷𝑛• zjednodušeně 𝑹 𝑨𝟏, … . , 𝑨𝒏

• dále budeme používat zjednodušený relační model k popisu principů převodu konceptuálního schématu do relačního

• formální vs. neformální• schéma relace – schéma (struktura/záhlaví) tabulky• relace – tabulka (data)• doména – datový typ sloupce• prvek relace – řádek tabulky

Realizace vazeb – kardinalita 1:1

linkaridic(cislo, start, cil, …, id, jmeno, rok_narozeni, …)

• V 1:1 kardinalitě může libovloný z klíčů účastnících se entit být klíčem výsledného relačního schématu

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í

Realizace vazeb – kardinalita 1:1

linka(cislo, start, cil, …)

linkaridic(cislo, id)

ridic(id, jmeno, rok_narozeni, …)

• 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é

• protože jsou kardinality na obou stranách 1, tvoří každý z cizích klíčů ve spojovací relaci klíč v této relaci

Realizace vazeb– kardinalita 1:N

linka(cislo, start, cil, …)

ridic(id, jmeno, rok_narozeni, cislo)

• 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ě 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

Realizace vazeb– 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 idjako 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

Realizace vazeb– kardinalita M:N

• Ve vztahu M:N nejsmeschopni 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

linka(cislo, start, cil, …)

linkaridic(cislo, id)

ridic(id, jmeno, rok_narozeni)

Funkční závislost – př. (1)

značení

• RC → JMENO

čtení

• rodné číslo funkčně určuje jméno

• 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

význam

RČ … JMENO …

870226/5385 … Karel Vomáčka …

890610/1182 … David Mikeš …

880906/5595 … Jan Novák …

870226/5385 … Patrik Nový …

• funkční závislost určuje sémantické vztahy mezi atributy

Funkční závislost – př. (2)

značení

• {START, CIL} →CISLO

čtení

• Start a cílfunkčně určuje číslo

• 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

význam

CISLO … START CIL …

106 … Kavkazská Nádraží Braník …

203 … Kačerov Vavřenova …

308 … Kavkazská Nádraží Braník …

205 … Zemanka Komořany …

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á datamohou být v DB uložena, případně vymezuje vztahy mezi nimi

Funkční závislost (FZ) 𝑋 → 𝑌 nad schématem 𝑅(𝐴) je parciální zobrazení 𝑓𝑖: 𝑋𝑖 → 𝑌𝑖, 𝑋𝑖 , 𝑌𝑖 ⊆ 𝑨 (kde 𝑖 =1..počet závislostí pro R(A)). Říkáme že n-tice z Xi funkčně určuje m-tici z 𝑌𝑖 a že m-tice z 𝑌𝑖 funkčně závisí na n-tici z 𝑋𝑖.

• Definice:

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ávislostimezi nimi• R(A, F), kde F = ∪i{fi}

• nadklíč relace NK• NK → A

• klíč relace K• K → A ∧ ∄ K1(K1 → A) : K1⊇ K

• klíčový atribut• atribut z A, který je součástí nějakého klíče (klíčů může být více)

• neklíčový atribut• 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_KM_ZA_MESIC

ODPRACOVANO_LET

PLAT VEK

1 Petr Malý 412 20 18000 48

2 Jan Vostrý 654 10 19000 35

3 Aleš Nový 412 20 18000 44

4 Petr Berka 128 15 17000 50

• ID → ALL

• JMENO → ALL

• NJKZM → OL

• OL → NJKZM

• {NJKZM, OL} → PLAT

• VEK → VSE

ne vše, co vidíme, v datech obecně platí

Aktualizační anomálie

• mějme relaci

• AUTOBUS(SPZ, NAJETO, …, SOUCASTKA, VYROBCE_SOUCASTKY, …)• součástky uchováváme v relaci s autobusy, tj. má-li autobus 20

součástek, máme 20 řádků pro 1

• příklady aktualizačních anomálií

• změna informace o konkrétním autobusu vyžaduje vícenásobné provedení této změny

• chceme-li odstranit jeden autobus z DB, je třeba to učinit na více místech

• není-li součástka použita v žádném autobusu, informaci o ní ztrácíme• nelze přidat součástku do DB, aniž by nebyla použita v nějakém

autobuse

Normalizace schématu• Normalizace relace

minimalizuje redundanci v datech a tak předchází vzniku aktualizačních anomálií

• Normalizaci lze zajisti dekompozicí (rozdělení jedné relace do více tabulek) tak, aby výsledné schéma splňovalo požadavky dané normální formy (NF)

• 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• BCNF• 4NF• 5NF

• Výhody• Snížení redundance dat → menší

prostorové nároky• Jednodušší aktualizace dat• Zabránění aktualizačním

anomáliím

• Nevýhody• Zpomalení komplexních dotazů

1NF1. tabulka musí reprezentovat relaci v algebraickém smyslu

• 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)• 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• ∄𝐾𝐾 ⊂ 𝐾:𝐾𝐾 → 𝑁𝐾

• {C_ZIDLE,BUDOVA} → ALL, BUDOVA → ADRESA

• redundance adresy (nebo obecně jakékoli informace závislé na budově)

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

není v 2NF

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

BUDOVA ADRESA

A Technická 5, Praha

B Technická 3, Praha

C Studentská 1, Praha

{C_ZIDLE,BUDOVA} → ALL … 2NF

BUDOVA → ADRESA … 2NF

3NF• v DB se nesmí vystkytnout tranzitivní závislost na klíči K

• ∄𝐴, 𝐵:𝐾 → 𝐴 → 𝐵

• JMENO → VSE, PSC → MESTO ⇒ JMENO → PSC → MESTO

• reundance města• může být problematické, když se rozhodneme uchovávat další informace

o městě, např. počet obyvatel

JMENO PSC MESTO PLAT

Jan Vodnář 14200 Praha 24000

Petr Novotný 14200 Praha 20000

Karel Kolář 60200 Brno 18000

Patrik Nový 66434 Kuřim 35000

Aleš Výmola 63900 Brno 28000

není v 3NF

3NF – dekompoziceJMENO PSC PLAT

Jan Vodnář 14200 24000

Petr Novotný 14200 20000

Karel Kolář 60200 18000

Patrik Nový 66434 35000

Aleš Výmola 63900 28000

PSC MESTO

14200 Praha

60200 Brno

66434 Kuřim

63900 Brno

JMENO → ALL … 3NF

PSC→ MESTO … 3NF