Oggi ho letto dellalgoritmo di decomposizione 3NF. Diceva:
- Trova una base minima di F, ad esempio G
- Per ogni FD X → A in G, usa {X, A} come schema di una delle relazioni nella scomposizione
- Se nessuno degli insiemi di relazioni di Step2 è una superchiave per R, aggiungi unaltra relazione il cui schema è una chiave per R
Voglio scomporre questa relazione in 3NF.
R(A,B,C) S={A→B, A→C, B→A, B→C, C→A, C→ B, AB→ C, BC→A, AC→B, A→BC, B→AC, C→AB} Come possiamo vedere, la chiave di R è: {A},{B},{C}
S ha diverse basi minime, come:
-
{A→B, B→A, B→C, C→B}; e -
{A→B, B→C, C→A}
Il problema è che se usiamo la prima base minima, scomponiamo R in 2 relazioni : (A, B), (B, C).
Se usiamo la seconda base minima, R si trasforma in: (A, B), (B, C), (C, A).
La mia domanda è: qual è quella corretta?
Risposta
Prima di tutto, nota che la la relazione originale è già in Terza forma normale, poiché ogni attributo è primo (ogni attributo è una chiave, in realtà), in modo che la definizione di 3NF venga rispettata.
Quindi, nota che lalgoritmo è incompleto. I passaggi sono:
- Trova una base minima di F, ad esempio G
- Per ogni gruppo di FD con lo stesso parte sinistra, X → A 1 , X → A 2 , …, X → A n in G, usa {X, A 1 , A 2 , …, A n } come schema di una delle relazioni nella scomposizione
- Elimina tutte le relazioni i cui attributi sono contenuti in unaltra relazione.
- Se nessuno degli insiemi di relazioni del passaggio 2 è un superkey per R, aggiungi unaltra relazione il cui schema è una chiave per R.
Quindi, nel primo caso, ottieni tre gruppi di dipendenze:
A → B B → A B → C C → B che producono tre relazioni, R 1 (A, B), R 2 (A, B, C), R 3 (B, C) e, seguendo lalgoritmo, si ottiene come risultato solo R 2 , poiché gli altri due hanno attributi in essi contenuti.
Quindi si hanno due output diversi dallalgoritmo, a seconda della base minima utilizzata (che a sua volta dipende lordine in cui si considerano le dipendenze quando si calcola la copertura minima).
Quindi, la risposta alla tua domanda:
che uno è corretto?
è: entrambi sono corretti , poiché entrambi soddisfano la definizione di 3NF. Hai semplicemente scoperto che lalgoritmo di sintesi per scomporre una relazione in 3NF può produrre diverse soluzioni.
Una domanda diversa è: quale è “migliore”, e ovviamente la soluzione con una singola relazione è “migliore” , dal momento che non è necessario unire le tabelle quando si effettuano le query.
Naturalmente, se si potesse controllare allinizio se la relazione è già in 3NF, si può evitare di applicare lalgoritmo. Ma questo in generale non può essere fatto, poiché il controllo richiede il calcolo esponenziale di tutte le chiavi, per trovare i primi attributi della relazione.
A First Course in Database System - 3rd edition. Quale dovrei seguire adesso?