Boyce Codd Normal Form (BCNF)
Buongiorno! Come da titolo mi sto cimentando allo studio del BCNF. Non mi è ancora chiarissimo l'algoritmo, su internet e sul libro di testo non trovo nulla di veramente esaustivo. Ho provato anche a risolvere un esercizio:
Si consideri il seguente schema relazionale ABCDEF e le DF:
$A -> F$
$BC -> F$
$AE -> D$
$F -> E$
Convertire lo schema in BCNF.
Io ho provato a risolverlo nel seguente modo:
per prima cosa ho unito quel che potevo nelle DF, ottenendo
$ABC -> E$ (infatti $ABC -> F$, e visto che $F -> E$ allora ho pensato di fare $ABC -> E$)
$AE -> D$
e quindi ho le seguenti relazioni
$R_1 (ABCE)$
$R_2 (ADE) $
Dove $R_1 nn R_2 = AE$. Visto che $AE$ è chiave di $R_2$, allora l'ultima relazione trovata è in BCNF!
E' giusto il procedimento? Grazie
Si consideri il seguente schema relazionale ABCDEF e le DF:
$A -> F$
$BC -> F$
$AE -> D$
$F -> E$
Convertire lo schema in BCNF.
Io ho provato a risolverlo nel seguente modo:
per prima cosa ho unito quel che potevo nelle DF, ottenendo
$ABC -> E$ (infatti $ABC -> F$, e visto che $F -> E$ allora ho pensato di fare $ABC -> E$)
$AE -> D$
e quindi ho le seguenti relazioni
$R_1 (ABCE)$
$R_2 (ADE) $
Dove $R_1 nn R_2 = AE$. Visto che $AE$ è chiave di $R_2$, allora l'ultima relazione trovata è in BCNF!
E' giusto il procedimento? Grazie
Risposte
La prima relazione trovata non è in BCNF perché \( A \) non è una chiave, ma hai che \( A \to E \). Inoltre, che fine ha fatto \( F \) nelle relazioni che hai trovato? Piuttosto avrei considerato la DF \( A \to DEF \) che si ottiene a partire da \( A \to F, F \to E\) e \( AE \to D \) costruendo la relazione \( ADEF \) in cui \( A \) è una chiave e la relazione \( ABC \) in cui non ci sono dipendenze funzionali (e quindi \( ABC \) è una chiave).
P.S. Credo sia abbastanza improbabile che un computer generi le relazioni da me trovate, ma l'algoritmo che conosco io non segue il procedimento da te seguito. Che libro o dispense stai seguendo?
P.S. Credo sia abbastanza improbabile che un computer generi le relazioni da me trovate, ma l'algoritmo che conosco io non segue il procedimento da te seguito. Che libro o dispense stai seguendo?
"Black27":
sul libro di testo non trovo nulla di veramente esaustivo.
io dovetti cercare un po' per trovare materiale decente, oltre il libro di Ullman (per la teoria, ma che non ha esercizi svolti) cercai delle slide, che ho raccolto qui, se ti son utili
"apatriarca":
La prima relazione trovata non è in BCNF perché \( A \) non è una chiave, ma hai che \( A \to E \). Inoltre, che fine ha fatto \( F \) nelle relazioni che hai trovato? Piuttosto avrei considerato la DF \( A \to DEF \) che si ottiene a partire da \( A \to F, F \to E\) e \( AE \to D \) costruendo la relazione \( ADEF \) in cui \( A \) è una chiave e la relazione \( ABC \) in cui non ci sono dipendenze funzionali (e quindi \( ABC \) è una chiave).
P.S. Credo sia abbastanza improbabile che un computer generi le relazioni da me trovate, ma l'algoritmo che conosco io non segue il procedimento da te seguito. Che libro o dispense stai seguendo?
Come si diceva qui sopra, il libro è Ullman - Database Systems: the complete book ma ho avuto qualche problema nell'applicarlo alla pratica...Sto studiando solo da oggi questo argomento, magari devo ancora assimilarlo un po', ma su internet avevo trovato qualche slide che pensavo spiegasse con chiarezza l'argomento ma ahimè non penso abbia raggiunto il suo scopo! Purtroppo non so dirti dove l'avevo trovata. Ora guardo le slide che mi ha linkato hamming_burst e poi ritorno
Ho provato a studiare le slide ai link e il capitolo sull'Ullman, ma faccio ancora confusione e non riesco a risolvere l'esercizio che ho postato. 
Ricapitolando: Praticamente una relazione è in BCNF se una relazione R ha delle dipendenze funzionali F tali che nella parte a sinistra di ogni DF c'è una superchiave, e nessuna DF banale. E' giusto?
Allora per risolvere gli esercizi come faccio?
- Prima trovo la chiave
- Trovo delle DF tali che non sono presenti DF banali
- Le relazioni create che contengono queste ultime DF sono in BCNF
E' così?
Prendo un esercizio dell'Ullman:
$R = (ABCDE) $
$AB -> C$
$C -> D$
$D -> E$
Identifico la chiave, che è $AB$ perché la sua chiusura comprende tutti gli elementi di $R$.
La relazione però viola la BCNF perché gli elementi $C$ e $D$ non sono chiavi. Quindi divido il risultato in tre relazioni:
$R_1 = (ABC)$
$R_2 = (CD)$
$R_3 = (DE)$
E quindi queste tre relazioni sono in BCNF.
La mia domanda è: Come mai non può essere in BCNF la relazione $R_4 = (CE)$, visto che:
$C -> D$
$D -> E$
sono per la transitività equivalenti a $C -> E$?
Inoltre quale sarebbe la possibile soluzione del primo esercizio che ho postato?
Grazie
Ricapitolando: Praticamente una relazione è in BCNF se una relazione R ha delle dipendenze funzionali F tali che nella parte a sinistra di ogni DF c'è una superchiave, e nessuna DF banale. E' giusto?
Allora per risolvere gli esercizi come faccio?
- Prima trovo la chiave
- Trovo delle DF tali che non sono presenti DF banali
- Le relazioni create che contengono queste ultime DF sono in BCNF
E' così?
Prendo un esercizio dell'Ullman:
$R = (ABCDE) $
$AB -> C$
$C -> D$
$D -> E$
Identifico la chiave, che è $AB$ perché la sua chiusura comprende tutti gli elementi di $R$.
La relazione però viola la BCNF perché gli elementi $C$ e $D$ non sono chiavi. Quindi divido il risultato in tre relazioni:
$R_1 = (ABC)$
$R_2 = (CD)$
$R_3 = (DE)$
E quindi queste tre relazioni sono in BCNF.
La mia domanda è: Come mai non può essere in BCNF la relazione $R_4 = (CE)$, visto che:
$C -> D$
$D -> E$
sono per la transitività equivalenti a $C -> E$?
Inoltre quale sarebbe la possibile soluzione del primo esercizio che ho postato?
Grazie
Ma \( CE \) è in BCNF nel tuo esempio. Semplicemente sono state scelte dipendenze funzionali diverse per la decomposizione. A partire da una singola relazione sono possibili diverse decomposizioni. Nell'esempio del libro avresti per esempio potuto decomporre la relazione iniziale usando \( C \to D \) e quindi arrivare alle relazioni \( ABCE \) e \( CD \). A questo punto \( ABCE \) non sarebbe in BCNF essendoci ancora le DF \( AB \to C, C \to E \) in cui \( C \) non è una chiave. Decomponendo ulteriormente la relazione si otterrebbero alla fine le relazioni in BCNF \(ABC, CD, CE \) diverse da quelle calcolate nell'esercizio.
Nel tuo esempio iniziale \(ABCDEF\) con DF \( A \to F, BC \to F, AE \to D, F \to E\) e seguendo l'algoritmo che conosco si otterrebbe ad esempio che (la scelta delle DF da usare per la decomposizione è casuale):
1. \( F \to E \), si creano le relazioni \( FE \) e \( ABCDF \). La prima è in BCNF, mentre la prima no perché ci sono le DF \( A \to F, BC \to F, AF \to D \).
2. \(A \to F\), si decompone \( ABCDF \) nelle relazioni \( AF \) e \( ABCD \) in cui la prima delle due è in BCNF. Nella seconda c'è ancora la dipendenza funzionale \( A \to D \).
3. \(A \to D\), si decompone \( ABCD \) in \( AD \) e \( ABC \) entrambi in BCNF.
In conclusione, una possibile soluzione dell'esercizio potrebbero essere le relazioni \( FE, AF, AD, ABC \).
Ritengo comunque che tutta questa teoria sia generalmente poco utile. Non sempre le relazioni trovate seguendo queste regole sono infatti "ottimali" (nel senso che è il miglior design possibile per il database considerando la particolare applicazione) ed è abbastanza facile progettare relazioni con buone proprietà senza far ricorso a nessuna teoria o algoritmo particolare semplicemente ragionando sul problema. Nel tuo esercizio ad esempio, se fosse necessario accedere spesso a \(B, C\) ed \(F\) nella stessa query, sarebbe comodo avere questi attributi nella stessa relazione invece di dover fare il join tra diverse relazioni come è necessario nella mia soluzione.
Nel tuo esempio iniziale \(ABCDEF\) con DF \( A \to F, BC \to F, AE \to D, F \to E\) e seguendo l'algoritmo che conosco si otterrebbe ad esempio che (la scelta delle DF da usare per la decomposizione è casuale):
1. \( F \to E \), si creano le relazioni \( FE \) e \( ABCDF \). La prima è in BCNF, mentre la prima no perché ci sono le DF \( A \to F, BC \to F, AF \to D \).
2. \(A \to F\), si decompone \( ABCDF \) nelle relazioni \( AF \) e \( ABCD \) in cui la prima delle due è in BCNF. Nella seconda c'è ancora la dipendenza funzionale \( A \to D \).
3. \(A \to D\), si decompone \( ABCD \) in \( AD \) e \( ABC \) entrambi in BCNF.
In conclusione, una possibile soluzione dell'esercizio potrebbero essere le relazioni \( FE, AF, AD, ABC \).
Ritengo comunque che tutta questa teoria sia generalmente poco utile. Non sempre le relazioni trovate seguendo queste regole sono infatti "ottimali" (nel senso che è il miglior design possibile per il database considerando la particolare applicazione) ed è abbastanza facile progettare relazioni con buone proprietà senza far ricorso a nessuna teoria o algoritmo particolare semplicemente ragionando sul problema. Nel tuo esercizio ad esempio, se fosse necessario accedere spesso a \(B, C\) ed \(F\) nella stessa query, sarebbe comodo avere questi attributi nella stessa relazione invece di dover fare il join tra diverse relazioni come è necessario nella mia soluzione.
"apatriarca":
Ritengo comunque che tutta questa teoria sia generalmente poco utile. Non sempre le relazioni trovate seguendo queste regole sono infatti "ottimali" (nel senso che è il miglior design possibile per il database considerando la particolare applicazione) ed è abbastanza facile progettare relazioni con buone proprietà senza far ricorso a nessuna teoria o algoritmo particolare semplicemente ragionando sul problema.
se ricordo bene se si lavoro solo su schemi E-R o qualche altro tipo di astrazione, si riesce a ridurre in forma normale già a questo punto della progettazione (e poi tradurlo nei vari schemi relazionali) rispettando le varie formulazioni *NF. Perciò queste teorie sono più una formulazione matematica di questa modellizzazione. Mi sembra che solo pochissimi prodotti commerciali danno la possibilità che, date le FD e gli schemi, li riduca in BCNF e compagnia, anche perchè sono algoritmi costosi (con qualche eccezione).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo