DAM - DAW - MP 0484 Bases de Dades
Normalització
El principi bàsic de la Normalització diu: tota relació (taula) ha de descriure un concepte semàntic únic.
Per a reconèixer els casos en què això no es compleix, s'utilitza l'aplicació de les Formes Normals (FN).
Una relació (taula) està en una forma normal determinada, si satisfà un conjunt de restriccions determinades que són pròpies d'aquesta forma normal. La violació d'aquestes restriccions origina que la relació tingui anomalies i/o redundàncies.
Hi ha diverses Formes Normals, però, les més importants son: FN1, FN2, FN3, FNBC, FN4 i FN5. De manera que si es compleix una d'aquestes FN, també es compleixen les anteriors. Per tant, és important l'ordre en què les comprovem i resolem.
La primera forma normal (1FN) es basa en el concepte de valor atòmic, mentre que la resta de formes normals es basen en el concepte de dependència. La segona forma normal (2FN), la tercera forma normal (3FN) i la forma normal de Boyce-Codd (FNBC) es basen en el concepte de dependència funcional. Per acabar, la quarta forma normal (4FN) i la cinquena forma normal (5FN) es basen en els conceptes de dependència multivaluada i dependència de projecció-combinació, respectivament.
Primera Forma Normal - 1FN
Una relació està en primera forma normal (1FN) si, i només si, cap atribut de la relació és en si mateix una relació, és a dir, si tot atribut de la relació és atòmic, no descomponible, no grup repetitiu.
Per a aconseguir de normalitzar una relació a 1FN, caldrà aplicar una operació que es coneix amb el nom d'aplanar.
Quan s'aplana la relació, la clau primària pot canviar i esdevenir composta.
Exemple
Si tenim la següent relació:
| Subministraments | |||
| CodiProveidor | CodiArticle | Quantitat | CiutatProv |
| 1 | a1 a2 | 100 150 | Reus |
| 2 | a1 a2 | 200 250 | Vic |
| 3 | a2 | 100 | Vic |
Aplanem la relació i aconseguim:
| Subministraments | |||
| CodiProveidor | CodiArticle | Quantitat | CiutatProv |
| 1 | a1 | 100 | Reus |
| 1 | a2 | 150 | Reus |
| 2 | a1 | 200 | Vic |
| 2 | a2 | 250 | Vic |
| 3 | a2 | 100 | Vic |
De manera que la Clau de la relació ha passat a ser composta.
Segona Forma Normal - 2FN
Una relació està en segona forma normal (2FN) si, i només si, està en 1FN i tot atribut no clau depèn funcionalment en forma completa de la clau primària.
Hi ha una excepció: un atribut pot dependre funcionalment de part de la clau primària, si aquest atribut és part d'una clau alternativa.
Aquesta forma normal només es pot violar quan la clau primària d'una relació és composta.
Per a aconseguir tenir una relació a 2FN, cal evitar que hi hagi dependències funcionals no completes respecte de la clau. Per tant, tots els atributs que participen en la dependència funcional no completa s'han de projectar en una nova relació que correspon al concepte semàntic que representen.
Exemple
- Subministraments(CodiProvedior, CodiArticle, Quantitat, CiutatProveidor)
on hi ha un atribut no clau, CiutatProveidor que depèn d'un subconjunt de la clau, CodiProveidor.
La solució que apliquem és crear una nova relació:
-
Subministraments(CodiProvedior, CodiArticle, Quantitat)
-
Proveidors (CodiProveidor, , CiutatProveidor)
Tercera forma normal - 3FN
Una relació està en tercera forma normal (3FN) si, i només si, està en 2FN i cap atribut no clau depèn funcionalment de cap altre conjunt d'atributs no clau.
Per a normalitzar una relació que viola la 3FN, cal evitar la dependència funcional entre atributs no clau. Per tant, els atributs que participen en la dependència funcional, s'han de projectar en una nova relació que correspon al concepte semàntic que representen.
Exemple
- Clients(CodiClient, Carrer, Numero, Ciutat, Provincia)
on hi ha una dependència funcional entre dos atributs no clau: Ciutat i Provincia
La solució que apliquem és crear una nova relació:
-
Clients(CodiClient, Carrer, Numero, Ciutat)
-
Ciutats (Ciutat, Provincia)
Forma normal de Boyde-Codd - FNBC
Quan Codd va enunciar la 2FN i la 3FN l'any 1970, no va considerar la possibilitat que en una relació hi pogués haver diverses claus candidates que fossin compostes, ni tampoc va considerar la possibilitat que entre aquestes hi pogués haver encavalcaments. Per això, l'any 1974, Boyce i Codd van proposar la forma normal de Boyce-Codd que soluciona les limitacions de la 2FN i la 3FN. De fet, sovint es normalitza una relació directament a la forma normal de Boyce-Codd sense passar prèviament per la 2FN i la 3FN.
Una relació està en forma normal de Boyce-Codd (FNBC) si, i només si, està en 1FN, i si tots els determinants són clau candidata de la relació.
Determinant...
Donada una dependència funcional { X } --> { Y }, un determinant és el conjunt { X }.
Un determinant és l'atribut del qual depèn funcionalment algun altre atribut.
Exemple
Considerem una empresa on els treballadors treballen en un Departament. Aquest Departament pot tenir varis responsables, però el treballador només en té un d'assignat. Tindriem la següent taula vàlida:
- Treballador(CodiTreballador, CodiDepartament, CodiResponsable)
Si ara ens diuen que un treballador només pot ser responsable en un sol departament, ens trobem que es produeix una dependència funcional ja que
CodiResponsable --> CodiDepartament
Per tant, ens trobem un determinant, CodiResponsable, sense ser clau candidata. Caldria, doncs, crear una nova relació:
-
Treballador(CodiTreballador, CodiResponsable)
-
Responsable(CodiResponsable, CodiDepartament)
Conlusions
-
Sempre és possible normalitzar fins a la forma normal de Boyce-Codd.
-
Donat un model lògic inicial d'una base de dades, si hi apliquem un procés de normalització, el model lògic final obtingut equival sempre al model lògic inicial. És a dir, el procés de normalització preserva la semàntica (o significat) del model lògic inicial.
-
Com a conseqüència de la normalització, el model lògic final és millor que el model lògic inicial pels motius següents:
-
Elimina redundàncies i anomalies.
-
Separa fets semànticament diferents.
-
Mentre que les formes normals que acabem de veure es relacionen amb fets monovaluats, la quarta i la cinquena forma normal estan relacionades amb fets multivaluats.
Quarta forma normal - 4FN
Sigui R una relació amb esquema R(A1,A2,...,An) i siguin { X }, { Y }, { Z } atributs de R. Aleshores, la dependència multivaluada independent { X } { Y } existeix si, i només si, el conjunt de valors possibles de { Y } per a un parell { X, Z } depèn únicament del valor de { X } i és independent del valor de { Z }. Si existeix { X } { Y }, llavors també existirà la dependència multivaluada independent { X } { Z }.
Una relació està en quarta forma normal (4FN) si, i només si, està en FNBC i no té dependències multivaluades independents.
Exemple
Donada la relació:
Alumne(CodiAlumne, idiomaQueConeix, llenguatgeDeProgramacióQueConeix)
amb les possibles dades (i veiem-ne la redundància)
| CodiAlumne | idiomaQueConeix | llenguatgeDeProgramacióQueConeix |
|---|---|---|
| 1 | català | C# |
| 1 | castellà | C# |
| 1 | anglès | C# |
| 1 | català | Javascript |
| 1 | castellà | Javascript |
| 1 | anglès | Javascript |
Com veiem, hi ha dos camps que no tenen res a veure l'un amb l'altre i són multivaluats. Això implica que l'alumne apren un alte llenguatge o idioma, cal afegir més d'una fila, 3 per un llenguatge nou o 2 per un nou idioma.
La solució passa per separar aquests dos camps i posar-los en relacions diferents:
-
Alumne(CodiAlumne, idiomaQueConeix)
-
Alumne(CodiAlumne, llenguatgeDeProgramacióQueConeix)
| CodiAlumne | idiomaQueConeix |
|---|---|
| 1 | català |
| 1 | castellà |
| 1 | anglès |
i
| CodiAlumne | llenguatgeDeProgramacióQueConeix |
|---|---|
| 1 | C# |
| 1 | Javascipt |
Cinquena forma normal - 5FN
La 5FN també és coneguda com a Forma Normal de Projecció/Unió (PJ/NF).
Una relació està en cinquena forma normal (5FN) si, i només si, està en 4FN i no té dependències de projecció-combinació sense variació d’informació.
Proposada per Ronald Fagin el 1979
Exemple
Suposem que volem guardar la infromació dels professors que donen cada assignatura a cada grup del centre. Per exemple:
| Professor | CodiModul | Cicle |
|---|---|---|
| Pere | Bases de Dades | DAM |
| Pere | Programació | DAM |
| Joan | Bases de Dades | ASIX |
| Joan | Bases de Dades | DAW |
| Maria | Programació | DAW |
| Maria | Programació | DAM |
Sembla que hi ha duplicitats ja que tenim tuples repetides, però, en aquest cas, no existeixen totes les combinacions de Professor, Mòdul i Cicle.
La forma de separar-ho seria amb 3 relacions:
| Professor | CodiModul |
|---|---|
| Pere | Bases de Dades |
| Pere | Programació |
| Joan | Bases de Dades |
| Maria | Programació |
| CodiModul | Cicle |
|---|---|
| Bases de Dades | DAM |
| Bases de Dades | ASIX |
| Bases de Dades | DAW |
| Programació | DAM |
| Programació | DAW |
| Professor | Cicle |
|---|---|
| Pere | DAM |
| Joan | ASIX |
| Joan | DAW |
| Maria | DAW |
| Maria | DAM |