67 MODELIRANJE PODATAKA: INFORMATICA 1/89 ER JEZIK I NORMALNE FORME Descriptors: PROGRAMMING LANGUAGE, DATA MODELING, DATA BASES RERLATIONAL Modeliranje podataka temelji na dva osnovna sredstva: ER Jeziku i normalizaciji. Dok Je prvo relativno Jednostavno 1 Široko poznato, prema drugom vlada izvjestan "animozitet" , i to zbog njegove "sofist1cirane" 1 strogo formalne prirode. U ovom členku analiziramo neke tipične prlmjere "nenormalnosti" formi relacija, te pokazujemo da te "nenormalnosti" slijede iz grešaka u ER modelu podataka. Drugim riječlma, ovdje pokazujemo da ako Je ER model podataka korektno izraden, sheme relacija koje iz nJega slijede redovlto več Jesu u "optimalnoj (normalnoj) formi". Mario Radovan Sveučilište Rijeka, SET Pula Univerza v Ljubljani, IJS Ljubljana DATA MODELING: ER LANGUAGE AND NORMAL FORMS Data modeling Is based on two principal means: ER language and normal 1zation. While the first one is relatively simple and wide known, the second one undergoes certain "animosity" due to its "sophisticated" and strictly formal nature. In this paper we analyse typical examples of "non-normal" forms of relations, and shov that such "non-norma11ties" derive from errors In the ER data model. In other words, it is shown that if the ER data model is correctly drawn out, the relational schemes deriving from It are already in "an optimal (normal) form". 1. Uvod ER jezik Model objekti-veze-svoJstva, kao graflčkl Jezik za predstavljanje "strukture svijeta" (111: forme znanja o njemul) predložen Je u . TaJ Jezik obično se naziva ER modelom/Jez 1 kom (Entity-Relationship), pa ¿eno ga ovdje tako i nazivati. Polaznu osnovu ER modela/Jezika moie-mo izreči slijedečim riječima: Podaci su znanja o objektima, vezama (medu tlm objektima) i svojstvlma (objekata odnosno veza). Stoga, Je cilj Jezika za modeliranje podataka da omo-guči precizno 1 Jednostavno predstavljanje forme tih triju temeljnih kategorija znanja. Na Chenov prijedlog ER modela podataka uslije-dilo je vlie terminoloških i notacijskih nado-puna, kao i proiirenja samoga modela. Zbog ograničenostl prostora, ovdje ne iznosimo eksplicitno sam ER model podataka. Dobar prikaz toga modela/Jezika te načina njegova prevodenja na relacijski jezik dat je npr. u . Relacijski Jezik Relacija, kao temeljni element relacijsko? jezika/modela, ima dva aspekta: značenje 1 sadrfaj. Značenje relacije naziva se lntenzl-Jom, a formalno se iskazuje shemom relacije. Sadržaj relacije naziva se ekstenzijom, a Iskazuje se naslovi Jenom tabeloa podataka. Tabelu tvore n-torke atomar.nlh vrijednostl. Pored "tabelarnog izgleda", relacijski model karakter i zlra 1 skup operatora definiranih na skupu tabela-relacija. Ti operatorl omogučavaju da se, pored znanja (podataka) ekspllcltno datlh pojedinim relacijama, deduclraju (Izračuna ju) i ona znanja koja iz toga skupa relacija 68 loglčkl slljede. O kontekstu modeliranja podataka bitni su operatori projekcije i spajanja. Prikaz relacijskog modela dat Je npr. u , , , , ... . Normal1zacija Neformalno rečeno, (standardnim) procesom normalizacije nastojl se razviti dobar model podataka na taj način da se lz datog modela podataka otklanjaju slabosti. Stoga, prikaz problematike normalizacije otpočnlmo analizom slabosti ko Je mogu karakteri z irati neki dati model podataka. Na slici 1 dat Je ilustrativni primjer skupa relacija KUPAC, ARTIKAL i NARUD2BA. KUPAC Mflff IHE SJEDISTE Ki Siltb Zigrib K2 Arini Puli H Mirni Rovlnj K4 Bidil Zagrafa ARTIKAL i-ART NAZIV BOJA CIJENA Al slovki crvint 3 A2 guilci bljili 7 A3 pinkili plivi » M pinkili crvtni 9 MRU02BA HUP i-ART KOLIČINA U Al 100 KI A2 200 K2 Al 200 K2 M 200 K3 AJ 100 Sliki 1. Postavlja se pitanje zaito Je dati skup podataka (o fragmentu realnog svijeta) razdijeljen upravo u tri zasebne relacije. Eventualni odgo- vor da to "očito treba biti tako" nije neumje-san. Medutlm, kod opsežnijih (kompleksn1 j i h) modela stvari oblino nisu toliko očlte. S druge strane, mogli bismo isto tako reči da data podjela podataka slijedi iz ER modela sa slike 2. MARUDIBA Sliki 2. Naime, prijevod tog ER modela podataka na relacijski Jezik daje sheme relacija: KUPAC(fl-KUP, IME, SJEDI STE), ARTIKAL(fi-ART, NAZIV, BOJA, CIJENA), NARUD2BA(S-KUP, 6-ART, KOLIČINA), tj. točno sheme relacija sa slike 1. Medutim, to Je prije odgovor na pitanje odafcJe nego na pitanje zaito tri relacije. Da bi odgovorili na pitanje zašto, pokuiajmo isti fragment realnog svijeta opisati nekorektnim ER modelom .podataka datlm na slici 3. Sliki 3. Relacijski zapis ER modela podataka sa slike 3 glasi : NARUD2BA1(6-KUP, IME, SJEDI6TE, 6-ART, NAZIV, CIJENA, KOLIČINA) Primjer ekstenzija relacije NARUDžBAl dat Je na slici 4. Prva slabost relacije NARUD2BA1, Jeste prlsu-stvo redundance. Na primjer, ime i sjediite kupca JavljaJu se toliko puta koliko artikala Je naruiio pojedini kupac. Zbog prisustva redundance Javljaju se problemi i kod mijenja-nja ekstenzije (tj. sadriaja) relacije. Te probleme zajedničklm imenom nazlvamo anomalijama odrtavanja. 69 NARUtlBAl i-KUf KI IKE SJEDHTE 1-ART NAZIV BOJA CIJENA KOLIČINA Bilib Zijrtb Al olovk* crvini 3 100 KI Btl tb Zigrtb A2 guilci bljili 7 200 K2 Arini Puli Al ol oviti crvtni 3 200 KJ Ar «ni Puli A2 gutici . bljtli 7 200 K3 Hlrm Rovinj A3 pinkili plava 5 100 Sliki 4. Upi s ° Podatke o pojedino» kupcu ni Je mogrucie upi sati u relaclju NARUDŽBA1 sve dok taj kupac neSto ne naručl. Analogno vrijedl i za artikle. Brisanje 'i Brisanjem pojedine narudžbe mogu biti izgubljeni 1 svl podacl o kupcu odnosno artiklu. HljenjanJe Ako kupac promjenl ime 1 /i 11 sjedlite, onda se ta promjena mora provesti na toliko mjesta koliko narudžbi ima za toga kupca. Analogno vrijedl i za artikle. Primjetimo da se nijedna od iznad navedenih slabosti relacije NARUDžBAl ne javlja u skupu relacija sa slike 1, gdje su podaci razdjeljeni u tri zasebne relacije. Stoga, iznijeti primjer navodi na zaključak da je relaciju sa "mnogo atributa" poželjno dekomponirati (razdijeliti) na "viie relacija sa manje atributa". Cilj teorije normalizacije jeste da definira kriterije kada i proces kako se dekompoziciJ a date sheme relacije treba izvesti. Kaiemo da se normalizacija date sheme relacije izvodi na temelju dodatnih znanja o odnoslma medu entitetlma realnog svljeta. Siji model podataka oblikujemo. Ta znanja nazlvamo zavisnostima. Govorimo o tri vrste zavisnosti, i to: funkcljskoj zaviusnost (FZ), viSeznainoj zavisnost (VZ) i zavisnosti spajanja (ZS). 2. Funkcijska zavisnost Neka bude data shema relacije R sa skupom atributa A (R ) . Nadalje, neka V 1 H budu podskupovi od A(R). Na shemi relacije R vrijedl funkcijska zavisnost V --> W ako i samo ako svakoj instanci od V može biti pridružena točno jedna Instanca od W• Tada kaiemo da V funkcljskl determinira W, odnosno da W funkcijski zavisi od V. Za FZ oblika X --> Y kaiemo da je tri-vijalna ako je Y podskup od X. Zavisnosti ne lskazuju odnose unutar neke date ekstenzlje relacije (tj. nekog trenutnog sadr-iaja relacije), več odnose koji - u datom fragmentu realnog svljeta - uvljek vrljede medu promatraniro entitetlma. Na temelju zavisnosti, definiran Je 1 pojam legalne ekstenzlJe relacije. Neka bude data shema relacije R, sa prlpadnim skupom funkcijskih zavisnosti F. Ekstenzija relacije R legalna je ako 1 samo ako su na njoj zadovoljeni svl uvjeti iskazani sa FZ lz skupa F. Legalnost ekstenzije relacije ne garantira točnost podataka. Medutim nelegalnost garantira da su netočne barem neke od tvrdnji iz date ekstenzije relacije. Iz datog skupa funkcijskih zavisnosti F mogu loglčkl slljedltl 1 FZ koje u F nisu eksplicitno sadriane. Na primjer, iz skupa FZ koji sadrži zavisnosti A --> B i B -->.C loglčkl sli jedi zavisnost A --> C. Skup svlh FZ koje loglčkl sli jede iz F naziva se zatvorenjem od F, a označava se sa F+. Niz pravila koja omogu-čavaju da se iz datog skupa F izvedu sve 1 samo FZ koje spadaju u F+ naziva se Armstrongov i m akslorni ma. Formalna definicija postupka norma 11zaci je temelji na skupu zavisnosti F+. No, radi poje-dnostavljenja prikaza, ovdje proces normalizacije temeljimo na skupu eksplicitno datlh zavisnosti, tj. na skupu F. 0 praktičklm terminlma, to ne umanjuje valjanost lznljetih postupaka. Naime, projektant je taj koji - promatranjem odnosa u realnom svljetu - utvrduje skup eksplicitnih zavisnosti F. Stoga, nema razloga da u taj skup ne uključi sve relevantne FZ, čime skup F+ postaje praktički beznačajan. 70 3. Dekompozicija baz gubitka informacija Neka bude data shema relacije R. Relacijske sheme R1 i R2 su dekompoziciJ a od R ako i samo ako vri jedi: A(R i) uni ja A(R2) = A(R). Dakle, sheme relacija R1 i R2 tvore dekompozi-ciju sheme relacije R ako i samo ako se svaki atribut iz A(R) javlja u barem jednoj od shema relacija R1 odnosno R2. DekompoztciJa (Rl, R2) sheme relacije R je bez gubitaka informacija ako i samo ako se svaku legalnu ekstenziju relacije R dade rekonstruirati spajanjem njenih projekcija na skupove atributa A(R1) i A(R2 ) . Ta definicija ne daje prikladan kriterij za utvrdivanje da li dekompozicija jeste ili nije bez gubitaka informacija. Pogledajmo, stoga, slljedeču definiciju. Neka bude data shema relacije R i pri-padni skup funkcijskih zavisnosti F. DekompoziciJa (Rl, R2) sheme relacije R Je bez gubitaka informacija ako i samo ako na R vrijedi barem jedna od sllje-dečih FZ: A(R1 ) presjek A(R2) --> A(R1) A(R1) presjek A(R2) --> A(R2). Drugim riječlma, presjek skupova atributa shema relacija Rl i R2 mora bit kandidat ključa u barem jednoj od tih relacija. Shema relacije R na kojoj vrijedi FZ oblika X --> Y dekomponlra se na sheme relacija Rl i R2 tako da vrijedi: A(Rl) = X unija Y A(R2) = A(R) minus Y. 4. Prva, druga i tre Y nazlvamo potpunon FZ ako na postoji skup V, V pravi podskup od X, za koji vrijedi V --> Y. Tada kažemo da Y potpuno zavisi od X. Funkcijsku zavisnost (od X) koja nije potpuna nazlvamo parcijalnom FZ (od X). Shema relacije R nalazi se u 2NF ako je svaki neključni atribut od R potpuno zavisan od kandidata ključa. 2NF nema večeg praktičkog značaja jer se prevo-denjem sheme relacije samo u 2NF slabosti modela (tj. redundanca i anomalije) opčenito ne otklanjaju. Stoga 2NF moiemo smatrati samo "prirodnim prethodnikom" treče normalne forme. Takva dekompoziciJa očito jeste bez gubitaka informacija Jer Je A(R1 ) presjek A(R2) = X, a zbog X --> Y, skup atributa X Je kandidat ključa u Rl, tako da vrijedi X --> A(R1). Datu shemu relacije R opdenlto se dekomponlra na prolzvoljan broj shema relacija Rl, Rn. No, radi pojednostavlJenJa, ovdje se ograniča-vamo na dekompoziciju na dvije sheme relacija. Proces dekomponlranja mole se dalje sukcesivno izvoditi na shemama relacija generiranlm u prvom koraku dekompozicije. Treča normalna forma Naka bude data relacija R, 1 neka X, Y i Z budu podskupovi od A(R). Funkcijska zavisnost X --> Y Je tranzitivna FZ na R ako na R vrijede zavisnosti X --> Z 1 Z --> Y. Shema relacije R nalazi se u treefoj norjnalnoJ formi (3NF) ako neključni atributi nisu tranzitivno zavlsni od kandidata ključa. 71 Na sllci 5 dat je grafiSki prikaz FZ koje vrijede na shemi relacije NARUD2BA1. Ta shema relacije nije u 2NF - a tirne ni u 3NF - Jer Je parcijalna zavisnost oblik tranzltivne zavisnosti . KOLIČINA j Sheme relacija R3 1 R4 jesu u 3NF, Jer ne sadrže tranzitivnih zavisnosti. , DekompoziciJom sheme relacije NARUDi BA1 na relacije Rl, R3 i R4 generirane su shema relacija sa slike 1 (ovdje sa drukčijim imenitna, naravno). To ujedno pokazuje da proces normalizacije sheme relacije NARUDiBAl (koja slijedi iz nekorektnost ER modela podataka sa slike 2) daje one sheme relacija koje daje i sam korek-tan ER mode podataka sa slike 11 Dakle, normalizacija se ovdje svela na otklanjanje nekorektnosti ER modela podataka. A to sugerira da korektna izrada ER modela podataka dovodi do shema relacija koje več Jesu "u optimalnoj (normalnoj) formi", 5ime se ukida i sama potreba po normalizaciji. Sliki S. Polazeči od FZ S-KUP --> IME, SJEDISTE, shemu relacije NARUDŽBA1 dekomponirajmo na sheme relacija: R1 (S-KUP, IME, SJEDISTE) R2(5-KUP, 6-ART, NAZIV, BOJA, CIJENA, KOLIČINA). Shema relacije Rl jeste u 3NF, Jer IME ne determinira SJEDISTE tako da nema tranzitivnih zavisnosti. Medutlm, dijagram FZ za shemu relacije R2, dat na sllci 6 pokazuje da ta shema relacije nije u 2NF (a time ni u 3NF). 5. DekompoziciJa bez gubitka zavisnosti Funkcijske zavisnosti iskazuju odnose kojl vrijede u realnom svijetu. Stoga, ako želimo da ti odnosi vrijede i u modelu podataka (a to Je globalni kriterij dobrog modeliranja1), onda prilikom dekomponiranJa sheme relacije nljedna FZ ne smije biti ukinuta. Dekompozlcija (Rl, R2) sheme relacije R je bez gubltaka funkcijskih zavisnosti ako sve FZ definirane na R logičkl sll-Jede iz unije skupova FZ definiranih na Rl odnosno R2. KOLIČINA 4 t Sliki 6. Polazedi od FZ e-ART --> NAZIV, BOJA, CIJENA, shemu relacije R2 dekomponirajmo - prema iznad datom principu - na sheme relacija R3 i R4: R3(6-ART, NAZIV, BOJA, CIJENA) R4(S-K0P, 6-ART, KOLIČINA). Slijedeča definicija daje operativno pravilo za dekomponiranJe bez gubitaka FZ: Shema relacije R dekomponira se (bez gubitka FZ) ako se dekomponira prema FZ koja nije od kandidata ključa. Dosadažnji prikaz procesa modeliranja podataka zaključimo slijedečom tvrdnjom: Svaka shema relacije R koja nije u 3NF dade se - sukcesivnom primjenom ovdje opisanog postupka - dekomponirati na skup shema relacija Rl, ..., Rn, tako da vri Jedi: - Svaka Rl, 1 =< i =< n, jeste u 3HF; - Dekompozicija Je bez gubitka informacija; - DekompoziciJa Je bez gubitka funkcijskih zavisnosti. 72 Moiemo redi da Je 3NF (za praksu) najvainlJa normalna forma. Naime, shema relacije koje nije u 3NF redovito dovodi do ranije iznijetih slabosti (redundanca, anomalije održavanja). S druge strane, shemu relacije koja jaste u 3NF ponekad ni Je moguče dekomponirati bez gubltka FZ. Iznijetlm prlmjerom ilustrirano je da sam kore-ktan ER model podataka daje sheme relacija koje Jesu (barem) u 3NF. Utollko se i normalne forme mogu ovdje smatrati formalnim kriterijima za kontrolu lspravnosti ER modela podataka. 6. Boyce/Coddova normalna forma Za Boyce/Coddovu normalnu formu (BCNF) moiemo reči da predstavlja stroii oblik 3NF. BCNF je relevantna za one sheme relacija koje iroaju više zastavljenih kandidata ključa koji se medusobno djelomlčno prekrivaju. Shema relacije je u BCNF ako i samo ako su sve njene netrivljalne FZ ujedno FZ od kandidata ključa. Problematiku vezanu za BCNF iznijeti demo na primjeru trojne veze. Najpcije Je data trojna veza koja - prevedena na relacijski Jezik daje shemu relacije koja Je u 3NF, ali i u BCNF. Zatim Je taj primjer modificiran tako da shema relacije jeste u 3NF, ali ne i u BCNF. Na slici 7 dat je ER model podataka koji predstavlja sl,ljedede tvrdnje: 1. Jedan nastavnlk za jedan predmet koristi Jedan udibenlk. 2. Jedan predmet prema Jednom udibeniku predaje viže nastavnika. 3. Jedan udibenlk jedan nastavnik koristi za Jedan predmet. Vezu KOLEGIJ zapisujemo na relacljskom slljededom shemom relacije: KOLEGIJ(6-PRED, fi-NAST, S-UD2) Jez iku Da su <8-PRED, 6-NAST> i kandl-da- ti ključa slijedi iz tvrdnje (1) odnosno (3). Odatle slijede i FZ : FZ1: S-PRED, 6-NAST --> S-UD2, FZ2: S-NAST, S-UD2 --> S-PRED. Obzirom da shema relacije KOLEGIJ nema neklju-čnih atributa, ne može imati ni tranzltlvnih zavisnosti takvlh atributa te se stoga nalazi u 3NF. Nadalje, obzirom da su obje iznad date netrivljalne FZ od kandidata ključa, shema relacije KOLEGIJ nalazi se i u BCNF. Izmijenimo sada treču od iznad datih tvrdnji, koja neka glasi: 3'. Jedan udSbenik koristi se samo za jedan predmet. Tvrdnja (3') Implicira tvrdnju (3). Naime, ako se Jedan udibenlk koristi samo za jedan predmet (tvrdnja 3'), onda to mora poStivatl svaki nastavnik (tvrdnja 3). Tvrdnju (3') - samu za sebel - predstavili bi u ER modelu podataka blnarnom vezom. Medutlm, u kontekstu tvrdnji (1) i (2) predstavljamo Ju u okviru trojne veze, točno kako Je to učinjeno ER modelom podataka na slici 7. Odatle slljedl da Je 1 shema relacije - nazovimo Ju KOLEGIJI -za vezu datu tvrdnjama (1), (2) 1 (3') jednaka predainjoj shemi relacije KOLEGIJ. Dakle, KOLEGIJ 1(6-PRED, S-NAST, 6-UD2) Medutlm, na tim shemama ne vrljede isti skupovi FZ. Obzirom da Je tvrdnja (1) ostala nelzmje-njena, očito ovdje vrijedi FZ1. Nadalje, obzirom da (3') implicira (3) vrijedi i FZ2. No, lz tvrdnje (3 * > slljedl 1 FZ 3: 6-UD2 --> S-PRED koja ne vrijedi na shemi relacije KOLEGIJ. Sliki 7. Na slici 8 dat je primjer legalne ekstenzije relacije KOLEGIJI. Ekstenzlja Je legalna Jer su njome zadovoljene sve tri iznad date FZ. Nadalje, obzirom da vrijednost atributa S-UD2 ne "adreslra" samo jednu n-torku iz relacije KOLEGIJI, taj atribut očito ni Je kandidat ključa. A to, nadalje, značl da FZ3 nlje funkcijska zavisnost od kandidata ključa, tako da ni shema relacije KOLEGIJI ni je u BCNF. 73 KOLESIJ 1 S-PRED S-NftST S-UDJ P1 m III P1 - N2 U1 P2 NI U2 P2 K2 U2 Jer sadrži FZ koje nlsu od kandidata ključa. BCNF modela podataka moiemo doseči dekompozici-J.om sheme relacije NARUDžBAl prema S-KUP --> IME-KUP koja nlje od kandidata ključa) na: R1(6-KUP, IME-KUP) Bilki S. S druge strane, ta shema relacije jeste u 3NF, Jer nema neključnlh atributa. Medutim, prlmje-timo da se u relaciji KOLEGIJI - uprkos 3NF -Javlja redundanca (a sa njom i anomalije odria-vanja). Ta redundanca Je posljedica od FZ3. Naime, ako sam udibenik determinira predmet, onda se podatak o udžbeniku ne bi trebao zapi-sivatl toliko puta koliko nastavnika predaje taj predmet (kako Je to slučaj u relaciji KOLEGIJI). Postavlja se, stoga, pitanje Sto učlniti sa shemom relacije KOLEGIJI. U datom primjeru, preporučljiv odgovor glasi nlita. Dakle, zadržati ju u modelu podataka takvu kakva jeste. Naime, shemu relacije KOLEGIJI nije moguče dekomponirati bez gubitka FZ. Pogledajmo.to. R2(8-KUP, S-ART, KOLIČINA). Ta dekompoziciJa Je bez gubltaka Informacija i bez gubltaka funkcijskih zavisnosti. Naime: - treda i četvrta FZ iz F definirane su na Rl, - prva FZ iz F definirana Je na R2, - druga FZ iz F logički slijedi iz treče i prve FZ. Medutim, shema relacije NARUDž BA1 slijedi lz grube gre£ke u ER modela podataka. Naime, svoj-stvo IME-KUP očito pripada entltetu KUPAC a ne entitetu NARUDž BA. Dakle, sam korektan ER model podataka doveo bi do shema relacija Rl i R2, a ne do sheme relacije NARUD2BA1. Dakle, sheme relacija Rl i R2 - formirane iz sheme relacije NARUDžBAl - pokazuju da lz korektno lzradenog ER modela podataka slijede sheme relacija koje nisu samo u 3NF več 1 u BCNF. Polazečl od "kritične" FZ3, shemu relacije KOLEGIJI moiemo - bez gubitka informacija! dekomponirati na: Rl(6-UDž, 8-PRED) R2(6-NAST, 6-UD2). Medutim, ton dekompoziciJom izgubljene sz FZ1 i FZ2. Naime, od FZ sa sheme relacije KOLEGIJI, ovdje vrijedl samo FZ3 (na Rl), iz koje zacjelo ne slijede FZ1 1 FZ2. Dakle, takvu dekompozicl-Ju ne valja izvoditi, tako da prikaz veze KOLEGIJI ER modelom sa slike 7 Jeste korektan. Postoje sheme relacija koje Jesu u 3NF a nlsu u BCNF, i koje se dadu prevesti u BCNF bez gubltaka PZ. Pogledajmo primjer. Neka bude data shema relacije NARUDžBAl(S-KUP, IME-KUP, S-ART, KOLIČINA) i neka skup F sadrži slijedeče FZ: S-KUP, S-ART --> KOLIČINA, IME-KUP, 8-ART --> KOLIČINA, IME-KUP --> 8-KUP, S-KUP --> IME-KUP Shema relacije NARUDžBAl Jeste u 3NF jer (jedi-ni) nekiJučnl atribut KOLIČINA ne zavisi tran-zitivno. Medutim, ta shema relacije nije u BCNF Ako pak ER model podataka ne daje shemu relacije u BCNF (slučaj sheme KOLEGIJI), onda valja provjeriti da 11 se takva shema uopče dade dekompnirati (bez gubitakal) na sheme relacija koje Jesu u BCNF. Ovdje nemarno formalnog dokaza da takva dekompozicija nlje moguda. No, nije nam po&lo za rukom načl primjer u kojem bi takva dekompoziciJa bila moguča. 7. Višeznačna zavisnost Neka bude data shema relacije R 1 neka X, Y 1 Z budu podskupovi od A(R). Na shemi relacije R vrijedi VZ X -->> Y ako 1 samo ako skup vrljednosti atributa iz Y za dati par vrijednosti atributa lz X i Z zavisi lsključivo od vrljednosti atributa iz X, a nezavisan je od vrijednosti atributa iz Z. Kažemo da X vlSeznačno determinira Y, odnosno da Y vlšeznaino zav.lsl od X. Grafičkl prikaz VZ dat na slici 9, deflniciju razumi j iviJom. čini gornJu 74 PREDHET Sliki 9. Na slici 9 date eu dvije VZ, 1 to: PREDMET -->> NASTAVNIK PREDMET -->> UDŽBENIK. VZ se javljaju u "parovima". Vrijedi slljedeče pravilo : Ako na shemi relacije R vrijedi VZ X -->> Y onda vrijedi i VZ X -->> R minus (X unija Y). Dakle, ako skup atributa vlžeznačno determinira skup atributa Y, onda X viieznačno determinira i skup preostalih atributa sheme relacije R. To oblčno zapisujemo na slijedeoi način: x -->> Y I R minus (X unija Y) I VZ koje su zadovoljene u svakoj eksten-ziji relacije nazlvamo trivijalnima. Na primjer, u svakoj ekstenzij binarne relacije R(X, Y) zadovoljene su trivijalne VZ X -->> Y 1 Y -->> X. Naime, svakoj vrijednostl atributa X pripada skup (od jedne ili viie) vrijednosti atributa Y, i obrnuto. VZ predstavijaJu general izaciJu FZ. Pod time podrazumiJevamo da svaka FZ - po definiciji I jeste ujedno i VZ. Naime, FZ oblika X --> Y je ujedno VZ kod koje skup vrijednosti atributa Y za Jednu vrijednost atributa X sadrii samo jedan element. 8. Cetvrta normalna forma Shema relacije koja se nalazi u BCNF i/lli 3NF može svejedno dovesti do Javljanja redundance (u bazi), a time i do anomalija odriavanja. Pogledajmo primjer. Na sllcl 10 dat je primjer ekstenzije relacije KOLEGI J 2, čija shema glasi KOLEGIJ2(6-PRED, S-NAST, S-UDŽ) i-PRED S-MAST i-UM Fizika Duokrlt Oinovt Fizika Dtiokrlt Principi Ftiiki Km t on Otnovt Fizika »i»ton Principi Siliti 10. Shema relacije KOLEGIJ2 jeste u BCNF jer na njoj nije definirana nlkakva netrlvijalna fz. Medutlm, relacija KOLEGIJ2 sa slike 10 očito sadrii redundancu: zapis o tome da pojedini nastavnlk predaje pojedini predmet javlja se toliko puta koliko udibenlka ima za taj predmet. Analogno vrijedi i za udibenike. Kao i FZ, VZ daju osnovu za definiranje (nove) normalne forme, odnosno dekouponiranje shema relacija, u cilju otklanjanja redundance 1 anomalija odriavanja. Shema relacije je u četvrtoj normalnoj formi (4NF) ako i samo ako su sve njene netrivljalne VZ ujedno FZ od kandidata ključa. Jednostavnlje rečeno, shema relacije je u 4NF ako Je u BCNF i ako nema "pravih VZ". (Dakle, ako nema VZ koje nlsu FZ.) Naime, ako shema relacije nema "pravih VZ", onda se zahtjev lskazan samom deflnlclJom 4NF svodi na zahtjev iskazan definlcljom BCNF. (Dakle, da sve fz budu od kandidata ključa.) Shema relacije KOLEGI J 2 ntje u 4NF. Naime, ona očito sadrii VZ S-PRED -->> e-NAST j 6-UD2, koje, nisu FZ (pa ni FZ od kandidata ključa). U cilju otklanjanja redundance 1 anomalija odriavanja, shemu relacije koja sadrii VZ valja dekomponirati. Shema relacije na kojoj vrijedi netrlvijalna VZ oblika X -->> Y dekomponira se bez gubitaka Informacija 75 na sheme relacija R1 i R2, pri čemu vri Jedi : A(R1) = X unija Y A(R2) = A(R) minus Y. Po 1 a zeč1 od datlh VZ, shema relacije KOLEGI J 2 dekomponira se na sheme relacija R1(fl-PRED, 6-NAST) R2(ž-PRED, a-UDž). Na slicl 11 date su ekstenzije relacija R1 i R2, dobivene projekcijom ekstenzije relacije KOLEGIJ2 na skupove utrl buta A (R1) odnosno A(R2). S-PRED Í-NAST R2 Í-PRE0 1-UDi Fizika Dtiokrit Fiziki Omovi riiiki Niaton Fiziki Principi Sliki 11. Sheme relacija R1 i R2 jesu u 4NF. Naime, na tim shemama vrljede samo trivijalne VZ . Ranije isticana nuinost oiuvanja zavisnosti kod dekompozici Je, odnosi se i na vlieznačne zavisnosti. Formalni prikaz toga problema prelazi potrebe ovoga prikaza. Stoga, navodimo samo slijedeče (praktlčko) načelo: Sliki 12. vezani u Jednu vezu, ne opisuje stvarno stanje stvari u fragmentu realnog svijeta Siju stru-kturu modeliramo. Drugim riječima, javljanje VZ na shemi relacije Je posljedlca nekorektnosti ER modela podataka sa slike 12. Naiine, ako vrljede iznad date VZ, onda stvarno stanje stvari ne opisuje taj model, ved ER model podataka sa slike 13. PREDAJE PREDHET NASTAVNIK O LITERATURA UD2BEN1K Ako se dekompoziciJa izvodi polazeči od netrlvljalne VZ definirane na polaznoj shemi relacije (kako je iznad učlnje-no], onda dekompoz1ci J a nede dovesti do gubltka VZ. činjenica da neka shema relacije jeste u BCNF a nije u 4NF ukazuje na evldentnu grešku u ER modelu podataka, iz kojeg takva shema relacije sli jedi. Na prlmjer, shema relacije KOLEGIJ2 očito slijedi iz ER modela podataka datog na sllci 12. Napomenimo da tip povezanosti mnogo svlh triju tipova objekata koji tvore vezu slijedi iz toga ito Je ključ sheme relacije KOLEGIJ2 sastavljen iz identifikatora svlh trJJu tipova objekata. "Otkriče" VZ 6-PRED -->> S-NAST j S-UD2 v na shemi relacije KOLEGIJ2 ukazuje na to da su 11 pov i objekata NASTAVNIK i UD2BENIK medusobno potpuno nezavlsnl. A to onda znači da trojna veza KOLEGIJ2, kojom su ti tipovl objekata po- Sllki 13. Iz potonjeg ER modela očito direktno slljede sheme relacija R1 1 R2 (tj. PREDAJE 1 LITERATURA), koje su ranije bile generirane dekompoziciJom sheme relacije KOLEGIJ2 doblvene iz nekorektnog ER modela podataka. Dakle, normalizacija Ima i u ovom slučaju samo ulogu otkrivanja (1/ili otklanjanja) greiaka učinje-nih u procesu izrade ER modela podataka. Naravno, veza KOLEGIJ2 mogla bi biti 1 trojna. Medutim, u to» slučaju na prlpadnoj shemi relacije KOLEGIJ2 ne bi vrijedile iznad date VZ. Dakle, tada bi shema relacije KOLEGIJ2 bila ne samo u BCNF več 1 u 4NF. A to znači da bi i ER model podataka sa slike 12 tada dao shemu relacije koja jeste "u optlmalnoj normalnoj formi". 76 9. Zavisnost spajanja Postoje relacije koje se ne mogu dekomponlratl bez gubitka informacija na dvlje relacije, ali se mogu bez gubitka informacija dekomponlrat1 na tri 111 viie relacija. Pogledajmo primjer. Neka bude data shema relacije KOLEGIJ3(6-PRED, 6-NAST, S-UDž) na kojoj nlsu definirane nikakve netrivijalne VZ. Dakle, ta shema relacije Je u 4NF. Medutim, ekstenzija relacije KOLEGIJ3 data na slici 14 sadrži redundancu. KOLESIH S-PRED S-NAST S-UD2 P1 NI U1 P1 NI U2 P1 N2 U1 P2 NI Ul Sliki 14. Na primjer, podatak da nastavnik Ni predaje predmet P1 zapisan je toliko puta koliko udžbe-nika taj nastavnik koristi za taj predmet. Medutim, obzirom da nastavnik N2 za isti predmet ne koristi isti skup udžbenlka kao 1 nastavnik NI, na shemi relacije KOLEGIJ3 ne vrijedi VZ fi-PRED -->> S-NAST | S-UD2. Odatle slljedi da tu shemu relacije nije mogude dekomponlrati na dvije sheme relacija (na temelju VZ) , kako Je to užinjeno sa shemom relacije KOLEGIJ2. Medutim, na slici 15 pokazano Je da se ta relacija dade dekomponlratl na tri relacije, i to bez gubitka informacija. Relacija PNU, doblvena spajanjem relacija PN i NO sadril Jednu suvižnu n-torku. Drugim rljeii-ma, rezultat tog spajanja sadrži i tvrdnju da za predmet P2 nastavnik Ni koristi i udžbenik 02, Sto - prema relaciji KOLEGIJ3 - nije istina. Dakle, dekompozicija relacije KOLEGIJ3 samo na relacije PN i NU dovela bi do gubitka lnforma- cijskog sadržaja relacije K0LEGIJ3. Medutim, spajanje relacije PNU sa relacljom PU daje točno polaznu relaclju K0LEGIJ3. Obzirom da na shemi relacije KOLEGIJ3 nisu definirane nikakve netrivijalne VZ, tro- j-pred S-nast pl ni p1 n2 p2 ni NU S-NAST S-UDJ NI Ul NI U2 N2 Ul pu »-PRED S-ODi Pl 111 Pl U2 P2 Ul pnu • pn spoji nu PNU prldodin! S-PRED S-NAST S-I/Dl Pl NI Ul Pl NI U2 Pl N2 Ul P2 NI Ul P2 N1 U2 kolesij] • pnu spoji pu \ kolesij: S-PREt S-NAS S-UD2 Pl NI Ul Pl m U2 Pl N2 Ul P2 NI Ul Sliki 13. dekomponibllnost te relacije ne može biti formalno utemeljena (obrazložena) na osnovu takvih zavisnosti. Stoga je uvedena (definirana) nova vrsta zavisnosti: zavisnost spajanja. Na shemi relacije R vrijedi zavisnost spajanja (ZS) *(R1, .. . , Rn) ako i samo ako je Rl, ..., Rn dekoropo-zlcija od R bez gubitka informacija. Zavisnost spajanja *(R1, ..., Rn) nazl-vamo trlvlJalnom ako je R Jednaka nekoj od Ri, 1 =< i =< n. Zavisnost spajanja omogučava da se iznad dato svojstvo tro-dekomponlbllnostl (odnosno, opdenlto n-dekomponibllnosti) definira na razini sheme relacije. Za promatrani primjer to fiinimo pomoču slijedeie zavisnosti spajanja: *(PN, NU, PU). 77 Naravno, tirne smo ujedno definirali klasu legalnih ekstenzlja relacije KOLEGIJ3. Stoga, takvu ZS ne valja definirati samo na temelju Jedne ekstenzije relacije, ved to smijemo učiniti samo ako ta ZS iskazuje stvarne odnose u realno» svijetu. 0 tom (problemul) biti če viSe riječi u slljedečem odjeljku. Iz definicije ZS slijedi da su FZ i VZ samo posebni slučajev1 ZS. Več je ranije pokazano da je FZ samo poseban slučaj VZ. Nadalje, pokazano je da se shema relacije oblika R(X, Y, Z) može dekomponirati (bez gubitka informacija) na sheme relacija R1(X, Y) i R2(X, Z) ako na shemi relacije R vrijedi VZ X -->> Y | Z. Prema definiciji ZS, to ujedno znaSi da na shemi relacije R vrijedi ZS * (X Y, XZ). Dakle, gornja VZ dade se na ekvivalentan način izraziti kao ZS. S druge strane, očito postoje ZS koje nisu VZ. Takva Je, na primjer, ZS *(PN, NU, PO), definirana na shemi relacije K0LEGIJ3, na kojoj nije definirana nikakva VZ. Iz definicije ZS slijedi da Je to najopčenltljl mogučl oblik zavisnosti, sve dok se sheme relacija dekomponiraju prlmjenom operacije projekcije 1 regenerlraju primjenom operacije spajanja. Kao i prethodne zavisnosti, ZS daje osnovu za definiranje nove (a u kontekstu projekcije-spajanja i najvlie moguče) normalne forme. 10. Peta normalna forma Shema relacije na kojoj su definirane netrivi-jalne ZS moie se dalje dekomponiratl, i to upravo na one sheme relacija koje su date samim zapisom ZS. Cilj takve dekompozici Je jeste doseči petu nocmalnu formu shema relacija, kao najvliu moguču normalnu formu, koja definitivno ne dovodi do nikakvih redundanci ni anomalija odriavanja. Shema relacije R nalazl se u petoj normalnoj formi (5NF) ako i samo ako za svaku netrivijalnu ZS oblika *(R1, ..., Rn) definlranu na R vrijedi da je svaki A(Ri), 1 =< i =< n, suporključ od H. Jednostavnije rečeno, shema relacije Je u 5NF ako se ne da "suvislo dekomponiratl". Pokušajmo to ilustrirati na prlmjeru sheme relacije OSOBA(MAT-BROJ, IME, GOD-ROD). Takvom shemom relacije može u relacljskom Jeziku biti predstavljen objekt OSOBA iz ER modela podataka. Obzirom da je HAT-BROJ ključ sheme relacije OSOBA, na toj shemi relacije zacljelo vrijedi FZ HAT-BROJ --> IME. Polazeči od te FZ, shemu relacije OSOBA može se dekomponiratl (prema ranije iznljetom principu) na sheme relacija 0S0BA1(MAT-BROJ, IME), 0S0BA2(MAT-BROJ, DAT-ROD). Prema definiciji ZS, to ujedno znači da na shemi relacije OSOBA vrijedi ZS *((MAT-BROJ, IME), (MAT-BROJ, DAT-ROD)). Medutlm, primjetimo da Je ključ sheme relacije OSOBA (tj. MAT-BROJ) sadržan u obje sheme relacija generirane dekompozicijom. Dakle, A(OSOBA1) 1 A(OSOBA2) Jesu superkl Jučevi. sheme relacije OSOBA. A, prema definiciji 5NF, to znači da relacija OSOBA Jeste u 5NF. Dakle, kao sto je objekt OSOBA Jedan entitet ER modela podataka, tako je 1 shema relacije OSOBA u 5NF, te ne postoje formalni razlozl za njeno dalnje dekomponiranJe. S druge strane, .shema relacije K0LEGIJ3, uz pretpostavku da na njoj vrijedi ZS *(PN, NU, PU), nije u 5NF. Nalme, ključ sheme relacije KOLEGIJ3 je trojka atributa , tako da A(PN), A(NU) 1 A(PU) nisu superklJuievl sheme relacije KOLEG IJ 3. Stoga je ta shema relacije mogla biti "suvislo dekompon1 rana" na sheme relacija PN, NU 1 PU. ^Sheme relacija PN, NU 1 PU jesu u 5NF Jer se binarne relacije ne da netrivijalno dekomponiratl, tako da na njima nema netrlvlJalnih ZS. Stoga, svaka binarna relacija Jeste u 5NF. Postavlja se pitanje da 11 bi (i na temelju čega) 1 iz ER modela podataka slijedile sheme relacija P-N NU i PU, a ne shema relacije KOLEGIJ3. Prije odgovora, izneslmo slljedeča činjenice o 5NF. Obzirom da Je ZS najopčenltij i oblik zavisnosti, i 5NF najviia normalna forma, mogli bismo zaključiti da ZS i 5NF imaju dominantnu ulogu u 78 oblikovanju modela podataka. No, tome nlje baš tako. Na primjer, u nalazlmo tvrdnju da se 5NF (a tirne ni ZS) u praksi "opčenito ne korlste". Razlog za to Iznosi Date: "___ dok je otkrivanje FZ 1 VZ relativno jednostavno, ..., isto se ne bi moglo reči za ZS (koje nisu VZ), jer je intuitivno značenje ZS daleko od Jedno-stavnog. Stoga je i postupak utvrdiva-nja kada data relacija Jeste u 4NF ali ni Je u 5NF (te bi mogla biti dalje de-komponirana) JoS uvijek nejasan." (Podcrtao M.R.) Odatle direktno slijede 1 sheme relacija PN, NU i PU. Medutim, problem 5NF je u njenom otkriva-nju. Točnlje: u otkrivanju ZS koje nisu VZ. A taj problem je jednako prlsutan u formalizmu normalnih formi kao 1 u (bitno) jednostavni jem ER jeziku. Dakle, 1 s tog aspekta, ER jezik nudi mogučnost lzrade jednako kvalltetnog modela podataka kao i "sof1sttciran1" proces normal1zaci Je . Napomenimo da Je u gornja tvrdnja (lz prethodnog lzdanja iste knjige) nešto ublažena: umjesto "daleko od Jednostavnog" nalazimo "može ne biti očlto". Medutim, zaključak o nejasnoči postupka otkrlvanja ZS ostaje nelzmjenjen. Date, nadalje, sugerira mogučnost da su relacije koje Jesu u 4NF a nisu u 5NF "patološki slučajevi" koji se, izgleda, rijetko Javljaju u praksi. Taj stav, zajedno sa ranije rečenim o BCNF i 4NF, potkrepljuje ocjenu da je sa praktlčkog aspekta 3NF najvažnlja. Nalme, ako je ER model podataka korektno izraden (i ako relacija ni Je "patološka"), onda če sheme relacija generlrane iz tog ER modela koje jesu u 3NF biti ujedno i u BCNF, 4NF i 5NF. Stoga, ne izgleda primjerenim reči da se 5NF "u praksi opčenito ne koristi", več da se (u praksi) ne pokušava eksplicltno doseči. Medutim, to ne znafil da sheme relacije generlrane lz dobro oblikovanih ER modela podataka nisu 1 u 5NF. Iznad rečeno ujedno ukazuje na odnos ER modela 1 5NF. Nalme, ako se uspije otkrltl zavisnost spajanja poput *(PN, NU, PU) onda ista može biti iskazana tako da se umjesto trojne veze K0LEGIJ3 (koja Je po formi Jednaka vezi KOLEGIJ2 sa slike 12), ER modelom iskažu tri binarne veze, kako je to užinjeno na sllci 16. P* REFERENCE