Cap.1 Dipendenze funzionali e normalizzazioni Flashcards
Dipendenze funzionali e normalizzazioni
Quali sono le misure informali di qualità per la progettazione di uno schema di relazione?
Si ha il bisogno di misurare formalmente il perché un raggruppamento di attributi in uno schema di relazione possa essere meglio di un altro,
misurando la “bontà” (qualità) del progetto. Esistono 4 misure informali:
- Semantica degli attributi, ogni volta che si raggruppano degli attributi per formare uno schema di relazione, si suppone che ad essi sia associato un
certo significato. Ogni relazione può essere interpretata come un insieme di fatti o asserzioni.
LINEA GUIDA 1: Si progetti ogni schema di relazione in modo tale che sia semplice spiegarne il significato. Non si uniscano attributi provenienti da
più tipi di entità e tipi di associazione in un’unica relazione. Se uno schema di relazione corrisponde a un solo tipo di entità o a un solo tipo di
associazione, il suo significato tende ad essere chiaro. - Riduzione dei valori ridondanti nelle tuple, uno scopo della progettazione di schemi è quello di ridurre al minimo lo spazio di memoria occupato
dalle relazioni di base. Il raggruppamento di attributi in schemi di relazione ha un effetto significativo sullo spazio di memoria. Un altro problema
che si presenta sono le anomalie di aggiornamento, che possono essere classificate in:
▪ Anomalia di inserimento, per inserire una nuova tupla occorre inserire i valori degli attributi in tutti i campi della relazione, altrimenti valori nulli.
▪ Anomalia di cancellazione, se si cancella l’ultima tupla in una relazione, l’informazione che si riverisce ad un’altra relazione non sarà più presente.
▪ Anomalia di modifica, se si cambia un attributo in una relazione occorre aggiornare le tuple di tutte le relazioni collegate ad esso.
LINEA GUIDA 2: Si progettino gli schemi di relazione di base in modo che nelle relazioni non siano presenti anomalie. Se sono presenti delle
anomalie, le si rilevi chiaramente e ci si assicuri che i programmi che aggiornano la base di dati operino correttamente. - Riduzione del numero di valori nulli nelle tuple, è possibile che vengano raggruppati numerosi attributi a formare una grossa relazione, se molti
attributi non riguardano tutte le tuple della relazione, quelle tuple saranno nulle. Ciò può dar luogo ad uno spreco di memoria e problemi di
comprensione del significato. Inoltre, i valori nulli possono avere più interpretazioni.
LINEA GUIDA 3: Per quanto possibile, si eviti di porre in una relazione di base attributi i cui valori possono essere frequentemente null. Se i valori
null sono inevitabili, ci si assicuri che essi si presentino solo in casi eccezionali e che non riguardino una maggioranza di tuple nella relazione. - Impossibilità di generare tuple spurie, se viene separata una relazione in relazioni più piccole, e si tenta un’operazione di JOIN NATURALE sulle due
relazioni, il risultato del join può produrre molte più tuple rispetto all’originaria popolazione. Tuple aggiuntive sono dette tuple spurie perché
rappresentano un’informazione spuria o sbagliata che non è valida.
LINEA GUIDA 4: Si progettino schemi di relazione in modo tale che essi possano essere riuniti, tramite JOIN, con condizioni di uguaglianza su
attributi che sono o chiavi primarie o chiavi esterne in modo da garantire che non vengano generate tuple spurie. Non si abbiano relazioni che
contengono attributi di accoppiamento diversi dalle combinazioni chiave esterna – chiave primaria. Se relazioni di questo tipo sono inevitabili, non
si effettui su di esse un’operazione di join sulla base di questi attributi, perché il join può produrre tuple spurie.
Quali sono le regole di inferenza di Armstrong?
Sono 6: (Le dimostrazioni non sono scritte, vedi slide 3)
-Regola riflessiva
Se Y è sottoinsieme di X, allora X->Y
-Regola di arricchimento
{X->Y} |= XZ->YZ
-Regola transitiva
{X->Y, Y->Z} |= X->Z
-Regola di decomposizione
{X->YZ} |= X->Y
-Regola di unione
{X->Y, X->Z} |= X->YZ
-Regola pseudo transitiva
{X->Y, WY->Z} |= WX->Z
Perchè le prime 3 regole di inferenza sono dette corrette e complete?
Per corrette si intende che, dato un insieme di dipendenze funzionali F specificate su uno schema di relazione R, tutte le dipendenze che è possibile inferire da F usando le regole da RI1 a RI3 sussistono in ogni stato di relazione r di R che soddisfa le dipendenze in F.
Per complete si intende che, usando ripetutamente le regole da RI1 a RI3 per inferire dipendenze finché non se ne possono dedurre più, si ottiene come risultato l’insieme completo di tutte le possibili dipendenze che possono essere dedotte da F
Algoritmo per calcolare X+
X+ := X;
repeat
oldX+ := X+;
for each functional dependency Y -> Z in F do
if Y (sottoinsieme X+ then X+ := X+ (unione) Z;
until (oldX+ = X+);
Quando un insieme di dipendenze funzionali copre un altro insieme di dipendenze funzionali? E quando due insiemi di df si dicono equivalenti?
Un insieme di dipendenze funzionali E è coperto da un insieme di dipendenze funzionali F, alternativamente si dice che F copre E, se ogni DF in E è presente anche in F+, cioè se ogni dipendenza in E può essere inferita da F.
Due insiemi E e F di dipendenze funzionali sono equivalenti se E+=F+
Perciò l’equivalenza implica che ogni DF in E possa essere inferita da F, e ogni DF in F possa essere inferita da E, ossia E è equivalente a F se sussistono entrambe Ie condizioni E copre F e F copre E.
Quando un insieme F di dipendenze funzionali è detto minimale?
Un insieme F di dipendenze funzionali è minimale se soddisfa le seguenti condizioni:
1.Ogni dipendenza presente in F ha come parte destra un solo attributo
2.Non è mai possibile sostituire una dipendenza X->A di F con una dipendenza Y->A dove Y è un sottoinsieme di X, e avere ancora un insieme di dipendenze equivalente a F
3.Non è mai possibile rimuovere una dipendenza da F e avere ancora un insieme di dipendenze equivalente a F
algoritmo
1. Porre G:=F;
2. Rimpiazzare ogni dipendenza funzionale X→ {A1, A2, …, An} in G, con n dipendenze funzionali X→A1, X→A2, …, X→An;
3. Per ogni dipendenza funzionale X→A in G
per ogni attributo B che è un elemento di X
se { {G - {X → A} } ∪ { (X – {B}) → A} } è equivalente a G allora sostituire X → A con (X – {B}) → A in G;
4. Per ogni dipendenza funzionale rimanente X → A in G
se { G – {X → A} } è equivalente a G allora rimuovere X → A da G
Cos’è una superchiave? Cos’è una chiave? Cos’è un attributo primo?
Una superchiave di uno schema di relazione R = {A1, A2, …, An} è un insieme di attributi S⊆R con la proprietà che nessuna coppia di tuple t1 e t2 in un generico stato valido di relazione r di R avrà t1[S]=t2[S].
Una chiave K è una superchiave con la proprietà aggiuntiva che la rimozione di qualsiasi attributo da K fa sì che K cessi di essere una superchiave.
La differenza tra una chiave e superchiave sta nel fatto che la chiave deve essere minimale.
Se uno schema di relazione ha più chiavi, esse sono tutte chiavi candidate e solo una di queste sarà chiave primaria.
Un attributo di uno schema relazionale R è detto attributo primo di R se è membro di qualche chiave candidata di R, altrimenti è detto non-primo.
Prima forma normale
La prima forma normale (1NF) è stata definita per non permettere l’uso di attributi multivalore, composti o loro combinazioni.
Essa richiede che il dominio di un attributo comprenda solo valori atomici e che il valore di qualsiasi attributo in una tupla sia un valore singolo del suo dominio.
Le principali caratteristiche della prima forma normale includono:
Dati atomici: Ogni valore in una tabella deve essere atomico, ovvero indivisibile. Non dovrebbero esserci valori multipli o elenchi separati da virgole all'interno di una singola cella di una tabella. Tabelle organizzate: I dati devono essere organizzati in tabelle, in modo che ogni riga rappresenti una singola istanza di un'entità e ogni colonna rappresenti un attributo separato. Ad esempio, invece di avere una singola tabella con una colonna "Nome dei clienti" contenente una lista separata da virgole di nomi, è necessario avere una tabella separata con una colonna "Nome cliente" per ogni nome unico. Identificatore univoco: Ogni tabella deve avere una chiave primaria che identifichi univocamente ogni riga. Questo consente di distinguere e accedere a ogni record in modo inequivocabile. Ordine degli elementi: Nella prima forma normale, l'ordine delle righe e delle colonne non ha importanza. I dati devono essere accessibili e manipolabili indipendentemente dall'ordine in cui sono memorizzati.
Quando una DF si dice completa?E parziale?
Una DF X->Y è una DF completa se la rimozione di qualsiasi attributo A da X comporta che la dipendenza non sussista più, cioè, per ogni attributo A∈X, (X-{A}) non determina funzionalmente Y.
È parziale, invece, se si possono rimuovere certi attributi e la dipendenza continua a sussistere, cioè, per qualche A∈X, (X-{A})→Y.
Seconda forma normale
Uno schema di relazione R è in 2NF se ogni attributo non-primo A di R dipende funzionalmente in modo completo dalla PK di R.
Per rispettare la 2NF la relazione la si scompone in un certo numero di relazioni in 2NF, nelle quali gli attributi non-primi sono associati solo alla parte della PK da cui sono funzionalmente dipendenti in modo completo.
Quando una DF è detta dipendenza transitiva?
Una DF X→Y in uno schema di relazione R è una dipendenza
transitiva se esiste un insieme di attributi Z, che non è né una chiave
candidata né un sottoinsieme di chiavi di R, per cui valgono
contemporaneamente X→Z e Z→Y.
Forma Normale Di Boyce e Codd (BCNF)
La Forma Normale di Boyce-Codd (BCNF) è una forma normale utilizzata nel campo della progettazione dei database relazionali per garantire la ridondanza dei dati e la corretta gestione delle dipendenze funzionali.
La BCNF viene applicata a una relazione (tabella) all’interno di un database relazionale. Una relazione si dice essere in BCNF se soddisfa due requisiti:
Ogni dipendenza funzionale all'interno della relazione deve essere una dipendenza funzionale completa. Ciò significa che l'attributo a sinistra della freccia (il determinante) deve essere una chiave candidata (SUPERCHIAVE) (insieme di attributi che possono univocamente identificare una tupla) della relazione. Non ci devono essere dipendenze funzionali parziali. Ciò significa che non ci devono essere attributi non chiave che dipendono funzionalmente da parte di una chiave candidata. In altre parole, ogni attributo non chiave deve dipendere completamente da tutta la chiave candidata e non solo da una parte di essa.
la 3NF richiede solo di rimuovere le dipendenze transitive, la BCNF richiede anche che ogni dipendenza funzionale sia completa rispetto alla chiave primaria. Pertanto, la BCNF è una forma normale più stringente rispetto alla 3NF e impone restrizioni aggiuntive sulla progettazione del database.
Terza Forma Normale
La terza forma normale (3NF) è basata sul concetto di dipendenza transitiva.
Uno schema di relazione è in 3NF se è in 2NF e nessun attributo non-primo di R dipende in modo transitivo dalla chiave primaria
Cos’è una dipendenza funzionale?
Una dipendenza funzionale è un vincolo tra due insiemi di attributi della base di dati. Formalmente, una dipendenza funzionale (DF), indicata con X→Y,
tra due insiemi di attributi X e Y che siano sottoinsiemi di R specifica un vincolo sulle tuple che possono formare uno stato di relazione r di R. Il vincolo
è che per ogni coppia di tuple t1 e t2 in r per le quali è t1[X]=t2[X], si deve avere anche t1[Y]=t2[Y]. Ciò significa che i valori della componente Y di una
tupla in r dipendono da, o sono determinati da, i valori della componente X.
