4 settembre 2023 - esercizio 2

[CuriousCI]

[Warcophyr]

[CuriousCI]

Si prendono gli elementi che non sono mai determinati, perché l'unico modo per determinarli in un'eventuale chiave è se sono nella chiave (non li determina nessun'altro se non se stessi per riflessività). Però non basta, questa è solo un'euristica, devi vedere la definizione di chiave.

Sia $R$ uno schema relazionale, e sia $F$ un insieme di dipendenze funzionali su $R$. Sia $K \subseteq R$, $K$ si dice chiave se

• $K \to R \in F^+$
• $\forall K' \subset K, K' \to R \notin F^+$

Un sottoinsieme di attributi $K$ si dice chiave se determina tutto lo schema $\iff R \subseteq (K)^+_F$ (Lemma visto a lezione). Inoltre, se prendi $K' \subset K$, quindi $K'$ sottoinsieme proprio (vuol dire che non deve essere uguale a $K$), $K'$ non deve essere chiave. Vuol dire che $K$ è una chiave miniamle.

Prendiamo un esempio $(BD)^+_F = R \implies BD$ è superchiave (determina tutti gli attributi dello schema). Ora dobbiamo verificare che $B$ e $D$ non siano chiavi. Infatti $(B)^+_F = B \neq R$ e $(D)^+_F = D \neq R$, quindi $BD$ è chiave.

[CuriousCI]

Oltretutto, questo esercizio è particolare perché non specifica quante sono le chiavi, potrebbe essere 1 (si vede con il criterio dell'intersezione) o potrebbero essere 3, 4, 5 etc... infatti lui si è perso la chiave $AC$. Per vedersi tutte le chiavi, la soluzione più comoda è scriversi tutti i sottoinsiemi, ed eliminare quelli che non sono chiave man mano che si trovano chiavi / si calcolano le chiusure usando certe euristiche (ad esempio, se ABCD non è chiave, neanche tutti i sottoinsiemi di ABCD sono chiave)

[FrascaHoryzont]

Quindi per vederlo posso prendere l'insieme e considerare tutte le coppie possibili (AB,BC,CD, ecc...) e vedo tramite i loro sottoinsiemi (se già di per se sono chiavi) se sono chiavi oppure no giusto?

[CuriousCI]

Caution

Nel messaggio originale avevo scritto $K' \to K \notin F^+$, è un errore, dovevo scrivere $K' \to R \notin F^+$

Comunque sì, devo verificare che i sottoinsiemi non sono chiavi. Peccato che considerare tutte le coppie possibili non basta. Una terna $ABE$ potrebbe essere benissimo chiave se $AB$, $BE$ e $AE$ non sono chiavi e $ABE$ determina $R$.

In questo esercizio $R = ABCDEH$. Sai che $E$ non può essere in una chiave perché non compare mai a sinistra, quindi ti rimangono da considerare le combinazioni degli attributi $ABCDH$, che sono $2^5 = 32$. Non devi verificare la chiusura per tutte, puoi usare qualche euristica per tagliarti un sacco di combinazioni una volta che hai calcolato una chiusura, ma è comunque laborioso se non sai di preciso quante sono le chiavi.

Se vuoi qui #24 ho una soluzione completa in cui calcolo tutte le chiavi di uno schema non sapendo quante sono in anticipo.

[FrascaHoryzont]

grazie mille vedo subito.

[niccolo-fato]

[UnoCasuale]

Mi sembra corretto, ma credo tu ti sia perso la chiave AC

[niccolo-fato]

sì, hai ragione

[Frisbon]

Controllando i determinanti, vedo che E non determina nulla ⇒ non é / non fa parte di una chiave. Quindi le calcolo per ABCDH

Controllo le combinazioni:

$(A,B,C,D,H) ^+ \not= R$

Ora quelle a due…

$AB^+ = R ⇒ K$ ⇒ Non devo calcolare combinazioni con AB dentro.
$AC^+ = R ⇒ K$ ⇒ Same
$AD^+ ≠ R$
$AH^+ = R ⇒ K$ ⇒ Same
$BC^+ ≠ R$
$BD^+ = R ⇒ K$ ⇒ Same
$BH^+ ≠ R$
$CD^+ ≠ R$
$CH^+ ≠ R$
$DH^+ ≠ R$

Ora quelle a tre… (cancello quelle che contengono chiave)

ABC,ABD,ABH,ACD,ACH,ADH
BCD,BCH,BDH,CDH
$(BCH,CDH)^+ \not= R$

Ora quelle a quattro sono solo queste e non posso usarle ABCD ACDH BCDH

Quindi le uniche chiavi sono:
AB,AC,AH,BD

---

3NF sse per ogni dip fun X→Y ho che X é chiave or Y in a chiave

C→E viola la 3NF. (dimostrazione lasciata per casa)

---

Cerco cop minima. Decompongo F
diventa {BCD→A,BCD→H,BD→C,BD→H,A→D,C→E,CD→H,H→E,AH→B}

Ora controllo le ridondanze nei determinanti a coppia.
Se ho XYZ→A Calcolo XY,YZ,AX e vedo se (xes) A$\in$XY e se succede, levo Z.

BCD→A ⇒ $BC^+ = BCE,\ BD^+ =R, \ CD^+ = DEH$, A apparteiene a BD quindi C é ridondante. Elimino
BCD→H ⇒ H appartiene a BD e CD quindi lascio (per ora)
BD→C ⇒ $B^+ = B,\ D^+= D$, C non appartiene a loro, lascio.
BD→H ⇒ Same
CD→H ⇒ $C^+=CE,\ D^+ = D$, H non appartiene a loro, lascio.
AH→B ⇒ $A^+ = AD,\ H^+=EH$, same, lascio.

Mi rimane:
{BD→A,BCD→H,BD→C,BD→H,A→D,C→E,CD→H,H→E,AH→B}

Ora, per ogni dipendenza, calcolo le chiusure senza quella stessa presa in considerazione.

$BD^+ = BCDEH$, A non ne fa parte, lascio…
$BCD^+ = R$, H ne fa parte, Elimino…
$BD^+ = BDHE$, C not in, lascio.
$BD^+= BDCEH$, H dentro, elimino…
$A^+ = A$, lascio
$C^+ = C$, same
$CD^+ = CDE$, H not in, lascio.
$H^+= H$,same
$AH^+= ADHE$, b not in, lascio

Quindi la copertura minima che rimane é…
{BD→A,BD→C,A→D,C→E,CD→H,H→E,AH→B}

Applico l’algoritmo di decomposizione…
Il primo for mi cerca attributi che non sono in F, ci sono tutti quindi $S=$ é vuoto ⇒ salto il primo if e diventa $\rho = {\text{BDA, BDC, AD, CE, CDH, HE, AHB}}$

[CarloDaRomadev]

[sprigatita]