Dependències funcionals

Ampliar coneixements

Per aprofundir en la teoria de dependències funcionals i les seves propietats matemàtiques, consulta l'article de la Wikipedia:

Dependencia funcional — Wikipedia (es)

Les dependències funcionals constitueixen el fonament matemàtic de la normalització. Permeten expressar de forma precisa les restriccions que existeixen entre els atributs d'una relació i determinar si un disseny conté redundàncies o anomalies.

Igual que en una funció matemàtica un valor d'entrada determina un valor de sortida, en les bases de dades un conjunt d'atributs pot determinar de manera única un altre conjunt d'atributs.

---

Definició formal

Donat un esquema de relació R amb atributs A₁, A₂, ..., Aₙ, i dos subconjunts X i Y d'aquests atributs:

Es diu que Y depèn funcionalment de X (s'escriu X → Y) si per qualsevols dues tuples t₁ i t₂ de r tals que t₁[X] = t₂[X], llavors necessàriament t₁[Y] = t₂[Y].

Dit d'una altra manera: si dues tuples coincideixen en els valors dels atributs de X, han de coincidir també en els valors dels atributs de Y. X s'anomena determinant i Y s'anomena dependent.

Lectures equivalents de X → Y:

• "X determina Y"
• "Y ve determinat per X"
• "X → Y és una dependència funcional"

Tipus de dependències funcionals

Tipus	Descripció
Bàsica	La clau primària determina tots els altres atributs: és la dependència mínima que sempre existeix
Parcial	Un subconjunt propi de la clau ja determina alguns atributs no clau
Transitiva	Un atribut no clau determina un altre atribut no clau: X → Z → Y, amb Z no clau
Trivial	Y és subconjunt de X; sempre es compleix (p. ex. {Dni, Nom} → {Dni})

---

Exemple amb la taula EMPLEAT

Donada la taula EMPLEAT(Dni, Nom, Cog1, Població, Província, Comunitat Autònoma), on Dni és la clau primària:

Dependència	Tipus
{Dni} →	Bàsica
{Dni, Cog1} →	Ampliada (no bàsica)
{Dni, Nom} →	Ampliada (no bàsica)
{Província} →	Derivada (no bàsica)
{Població, Província} →	Derivada (no bàsica)

Les dependències funcionals bàsiques són les que s'obtenen a partir de les claus: el camp clau determina tots els altres atributs. Les demés es poden inferir a partir de les bàsiques.

---

Exemple amb dades reals: taula CLIENTS

Dni	Cog1E	NomE	Sexe	Població	Província	Comunitat Autònoma
011	Pagés	Nito	M	Girona	Girona	Catalunya
022	Serra	Albert	M	Girona	Girona	Catalunya
111	Pi	Maria	F	Mieres	Girona	Catalunya
222	Sau	Josep	M	Mieres	Astúries	Astúries
555	Puig	Anna	F	Olot	Girona	Catalunya

Dependències funcionals identificables:

• {Dni} → {Cog1E, NomE, Sexe, Població, Província, Comunitat Autònoma} — dependència bàsica
• {Província} → {Comunitat Autònoma} — cada província pertany a una única comunitat
• {Població, Província} → {Comunitat Autònoma} — la combinació determina la comunitat

{Població} → {Comunitat Autònoma} és vàlida?

A primer cop d'ull podria semblar-ho, però no és una dependència funcional vàlida: una mateixa població pot existir a dues comunitats autònomes (com Mieres, que apareix a Girona/Catalunya però també a Astúries). Les dependències funcionals s'han de verificar per a tots els valors possibles, no només per als que hi ha a la taula en un moment concret.

Com identificar una dependència funcional

Pregunta't: «Si sé el valor de X, queda determinat de manera única el valor de Y, en qualsevol instància possible de la relació?» Si la resposta és sí, existeix la dependència X → Y.

---

Clausura de dependències funcionals (F⁺)

El conjunt F de dependències funcionals d'un esquema és molt més ampli que el conjunt inicial que s'observa. Moltes dependències es poden inferir (deduir) aplicant regles lògiques.

Al conjunt de totes les dependències funcionals —incloses les deduïdes— se l'anomena F⁺ (tancament o clausura de F).

Exemple de deducció:

Si sabem: - {Dni} → {Província} (el Dni determina la província) - {Província} → {Comunitat Autònoma} (la província determina la comunitat)

Podem deduir sense consultar les dades: - {Dni} → {Comunitat Autònoma}

---

Regles d'inferència

Les regles d'inferència permeten construir F⁺ a partir d'un conjunt inicial F de dependències. S'usa la notació DF |= X → Y per indicar que la dependència X → Y ha estat inferida a partir del conjunt DF.

Per representar la unió de dos subconjunts d'atributs X i Y s'usa l'expressió XY (notació concatenada).

Les sis regles

Regla	Nom	Formulació formal
R1	Reflexiva	Si Y ⊆ X, llavors X → Y
R2	Augment	{X → Y} |= XZ → YZ
R3	Transitiva	{X → Y, Y → Z} |= X → Z
R4	Descomposició	{X → YZ} |= X → Y i X → Z
R5	Unió	{X → Y, X → Z} |= X → YZ
R6	Pseudotransitiva	{X → Y, WY → Z} |= WX → Z

Axiomes d'Armstrong

Armstrong va demostrar que les regles R1, R2 i R3 són completes: donats qualsevol conjunt F de dependències funcionals, aplicant repetidament R1, R2 i R3 es pot obtenir F⁺. Per aquest motiu, R1, R2 i R3 s'anomenen regles d'inferència d'Armstrong.

Les regles R4, R5 i R6 es poden deduir a partir de R1–R3, però resulten pràctiques com a dreceres. Les més importants a la pràctica (destacades en negre) són R3, R4 i R5.

Exemples de cada regla

R1 — Reflexiva: Si X conté Y, llavors X determina Y (resultat trivial).

{dni, nom} |= {dni, nom} → {dni}
{dni, nom} |= {dni, nom} → {nom}

R2 — Augment: Si X determina Y, podem afegir el mateix conjunt Z als dos costats.

{dni} → {nom}  |=  {dni, cog1} → {nom, cog1}

R3 — Transitiva: Si X determina Y i Y determina Z, llavors X determina Z.

{dni} → {província}
{província} → {comunitat}
─────────────────────────────────
|= {dni} → {comunitat}

R4 — Descomposició: Si X determina YZ, llavors determina cadascun per separat.

{dni} → {nom, cog1}
─────────────────────────────────
|= {dni} → {nom}
|= {dni} → {cog1}

R5 — Unió: Si X determina Y i X determina Z per separat, determina YZ conjuntament.

{dni} → {nom}
{dni} → {cog1}
─────────────────────────────────
|= {dni} → {nom, cog1}

R6 — Pseudotransitiva: Si X determina Y i WY determina Z, llavors WX determina Z.

{dni} → {municipi}
{província, municipi} → {comunitat}
─────────────────────────────────
|= {dni, província} → {comunitat}

---

Trobar claus candidates amb les regles d'inferència

Una de les aplicacions pràctiques de les regles d'inferència és identificar les claus candidates d'una relació. Una clau candidata és un conjunt mínim d'atributs que determina tots els atributs de la relació.

Procediment

1. Escollir una dependència funcional qualsevol com a punt de partida.
2. Aplicar les regles d'inferència per ampliar progressivament el conjunt d'atributs determinats.
3. Quan el determinant determina tots els atributs de R, és una clau candidata (si no es pot reduir).

Exemple

Donada la relació R(A, B, C, D, E, F, G, H, I, J) i les dependències funcionals:

ABC → E       C → J       AB → G       CJ → I       B → F       G → H

Partim de AB → G i apliquem les regles per inferir tantes dependències com sigui possible:

Inferència	Regla aplicada
AB → G	Donada
AB → AB	R1 (reflexiva)
AB → A, AB → B	R4 (descomposició)
AB → H	R3 (transitiva: AB→G i G→H)
ABC → HC	R2 (augment de AB→H amb C)
ABC → H, ABC → C	R4 (descomposició)
ABC → F	R3 (transitiva: ABC→B i B→F)
ABC → J	R3 (transitiva: ABC→C i C→J)
ABC → CJ	R5 (unió: ABC→C i ABC→J)
ABC → I	R3 (transitiva: ABC→CJ i CJ→I)
ABC → E	Donada
ABCD → ED	R2 (augment de ABC→E amb D)
ABCD → E, ABCD → D	R4 (descomposició)

ABCD determina tots els atributs A, B, C, D, E, F, G, H, I, J. Per tant, ABCD és una clau candidata de R.

flowchart TD
    DF["Dep. donades:\nABC→E, C→J, AB→G\nCJ→I, B→F, G→H"]

    subgraph "Inferències des de AB"
        AB["AB → G\n(donada)"]
        ABH["AB → H\n(R3: G→H)"]
        AB --> ABH
    end

    subgraph "Ampliem a ABC"
        ABC["ABC → C, F, J, H, E, I\n(R3 + R4 + R5)"]
    end

    subgraph "Ampliem a ABCD"
        ABCD["ABCD → D, E, F, G, H, I, J\nClau candidata!"]
    end

    DF --> AB
    AB --> ABC
    ABH --> ABC
    ABC --> ABCD

    style ABCD fill:#1b5e20,stroke:#2e7d32,color:#fff
    style DF fill:#1a237e,stroke:#283593,color:#fff

AC0372/02/02 — Miniactivitat

RA2 · CA2.8

Donada la relació R(A, B, C, D, E, F) i les dependències funcionals:

A → BC
B → E
CD → F
E → A

1. Identifiqueu les dependències funcionals bàsiques (les que determinen tots els atributs).
2. Apliqueu les regles d'inferència per demostrar que {CD} no és una clau candidata de R.
3. Trobeu almenys dues claus candidates de R justificant les inferències aplicades.