Cap.2 Algoritmi per la progettazione di base di dati relazionali Flashcards
Cos’è una decomposizione di R(schema di relazione universale)?
D={R1,R2,…,Rn}, detto decomposizione di R, è un insieme di schemi ottenuti decomponendo R attraverso vari algoritmi e basandosi sulle dipendenze funzionali.
è necessario assicurarsi che ogni attributo presente in R sia anche presente in almeno uno schema di relazione Ri, nella decomposizione, così che non ci siano attributi “persi”
Unione che va da i=1 ad m di Ri = R
Questa condizione è detta condizione di conservazione degli attributi.
Un altro obiettivo è quello che ogni relazione Ri nella decomposizione D sia in BCNF
Cos’è la condizione di conservazione delle dipendenze?
Indica che una forma normale o una trasformazione di una relazione (tabella) deve preservare tutte le dipendenze funzionali esistenti nella relazione originale.
In altre parole, se una dipendenza funzionale esiste tra gli attributi di una relazione, quando applichiamo una forma normale o una trasformazione a quella relazione, dobbiamo assicurarci che la dipendenza funzionale sia ancora valida nella nuova relazione risultante.
La condizione di conservazione delle dipendenze è fondamentale perché assicura l’integrità dei dati e la corretta rappresentazione delle informazioni all’interno del database. Se una trasformazione viola questa condizione, potrebbe alterare le dipendenze funzionali esistenti e portare a risultati errati o inconsistenti.
è una condizione dove ogni dipendenza funzionale X→Y specificata in F appare direttamente in uno degli schemi di relazione Ri della decomposizione D, oppure può essere inferita dalle dipendenze presenti in qualche Ri
Dato un insieme di dipendenze F su R, cos’è la proiezione di F su Ri dove Ri è un sottoinsieme di R?
Una proiezione di F su Ri, denotata con πRi(F), è l’insieme delle dipendenze X->Y di F+ tali che gli attributi di XUY siano tutti contenuti in Ri.
Perciò la proiezione di F su ogni schema di relazione Ri della decomposizione D è l’insieme delle dipendenze funzionali in F+, chiusura di F, tali che tutti i loro attributi di parte sinistra e di parte destra siano in Ri.
Si dirà che una decomposizione D={R1, R2, …, Rm} di R conserva le dipendenze rispetto a F se l’unione delle proiezioni di F su ogni Ri in D è equivalente a F, cioè:
((𝜋𝑅1(𝐹)) ∪ … ∪ (𝜋𝑅𝑚(𝐹)))+=F+
.
Algoritmo di sintesi relazionale
L’algoritmo di sintesi relazionale, a partire da un insieme di DF crea una decomposizione D={R1,R2,…,Rn} di una relazione universale che conserva le dipendenze e tale che ogni Ri di D sia in 3NF.
L’algoritmo conserva tutte le dipendenze presenti in G, perché ogni dipendenza compare in una delle relazioni Ri della decomposizione D
Input: Una relazione universale R e un insieme di dipendenze funzionali F sugli attributi di R.
1.Trovare una copertura minimale G di F
2.Per ogni parte sinistra X di una DF che appare in G, creare uno schema di relazione {X ∪ A1 ∪ A2 ∪ … ∪ Am} in D dove X→A1, X→A2, …,X→Am sono le sole dipendenze in G aventi X come parte sinistra
- Mettere in uno schema di relazione singolo tutti gli attributi rimanenti, per garantire la proprietà di conservazione delle dipendenze.
L’Algoritmo è detto algoritmo di sintesi relazionale, perché ogni schema di relazione Ri nella decomposizione è sintetizzato (costruito) a partire dall’insieme di dipendenze funzionale in G con la stessa parte sinistra X
Cos’è il LossLess Join?
è una proprietà che una decomposizione D deve soddisfare e assicura che non vengano generate tuple spurie quando alle relazioni della decomposizione viene applicata un’operazione di NATURAL JOIN
Formalmente, una decomposizione D={R1, R2, …, Rm} di R soddisfa la proprietà di join senza perdita (non-additivo) rispetto all’insieme di dipendenze F di R se, per ogni stato di relazione r di R che soddisfa F, sussiste quanto segue, dove * è il JOIN NATURALE di tutte le relazioni in D:
∗ (𝜋_𝑅1(𝑟), … , 𝜋_𝑅𝑚(𝑟)) = r
ALGORITMO
Input: Una relazione universale R e un insieme di dipendenze funzionali F sugli attributi di R.
1. Trovare una copertura minimale G per F;
2. Per ogni parte sinistra X di una FD in G, creare uno schema di relazione in D con attributi {X∪A1∪A2∪…∪Am} dove X→A1, X→A2, …, X→Am sono
le sole dipendenze in G aventi X come parte sinistra.
3. Se nessuno degli schemi di relazione in D contiene una chiave di R, creare un altro schema di relazione che contiene attributi che formano una
chiave per R
Quali sono le proprietà della LOSSLESS JOIN?
La prima proprietà riguarda le decomposizioni binarie, decomposizioni di una relazione R in due relazioni:
Una decomposizione D={R1, R2} di R soddisfa la proprietà di join senza perdita rispetto a un insieme di dipendenze funzionali F di R se e solo se:
▪ La DF ((R1∩R2))→(R1-R2) è in F+
oppure
▪ La DF ((R1∩R2))→(R2-R1) è in F+
La seconda proprietà tratta l’esecuzione di decomposizioni successive e può essere applicata solo se si hanno due relazioni, R1 e R2:
Una decomposizione D={R1, R2, …, Rm} di R gode della proprietà di join senza perdita rispetto a un insieme di dipendenze funzionali F su R, e se una decomposizione D1={Q1, Q2, …, Qk} di Ri gode della proprietà di join senza perdita rispetto alla proiezione di F su Ri, allora la decomposizione D2={R1, R2, …, Ri-1, Q1, Q2, …, Qk, Ri+1, …, Rm} di R gode della proprietà di join senza perdita rispetto a F.
Cos’è una tupla dangling?
è un record incompleto o impreciso in una tabledi database che non dispone di una valore corrispondente in una tabella correlata.
Cos’è una dipendenza multivalore?
Le dipendenze multivalore sono una conseguenza della prima forma normale (1NF), che impedisce a un attributo in una tupla di conoscere un insieme di valori.
Se vi sono due o più attributi multivalore indipendenti nello stesso schema di relazione, si ha il problema di dover ripetere ogni valore di uno degli attributi per ciascun valore dell’altro attributo.
Questo vincolo viene espresso mediante una dipendenza multivalore.
Quindi, dato un particolare valore di X, l’insieme di valori di Y è determinato completamente solo da X e non dipende dai valori dei restanti attributi in Z di R.
Una MVD X ↠ Y in R è detta MVD banale (trivial) se: Y è un sottoinsieme di X,
oppure X U Y = R.
Quali sono le regole di inferenza per MVD?
Si supponga che tutti gli attributi siano inclusi in uno schema di relazione “universale” R = {A1, A2, …, An} e che X, Y, Z e W siano sottoinsiemi di R.
▪ RI1 (regola riflessiva per le DF): se X ⊇ Y, allora X → Y
▪ RI2 (regola di arricchimento per le DF): {X → Y} |= XZ → YZ
▪ RI3 (regola transitiva per le DF): {X → Y, Y → Z} |= X → Z
▪ RI4 (regola di completamento per le MVD): {X↠Y}|=X↠ (R-(X∪Y))
▪ RI5 (regola di arricchimento per le MVD): Se X↠Y e W⊇Z, allora WX↠YZ
▪ RI6 (regola transitiva per le MVD): {X ↠Y, Y ↠ Z} |= X ↠ (Z-Y)
▪ RI7 (regola di replicazione per DF in MVD): {X→Y}|=X↠Y
▪ RI8 (regola di unione per le DF e le MVD): Se X↠Y ed esiste W con le proprietà che (a) W∩Y è vuota, (b) W→Z e (c) Y⊇Z, allora X→Z
Quarta forma normale
La quarta forma normale 4NF viene violata quando una relazione ha dipendenze multivalore non volute, e quindi può essere usata per identificare e decomporre tali relazioni.
Uno schema di relazione R è in 4NF rispetto a un insieme di dipendenze F (che include le dipendenze funzionali e multivalore) se, per ogni dipendenza multivalore non banale X↠Y in F+ , X è una superchiave di R.
NOTA sulle MVD non-banali: Relazioni contenenti MVD non-banali tendono ad essere relazioni “tutta chiave” (la chiave è formata da tutti gli attributi).
perché quando progettiamo uno schema ci fermiamo a 3nf o bcnf?
Perché si potrebbe perdere efficienza in quanto abbiamo sempre più relazioni e di conseguenza quando dobbiamo fare le query ci saranno sempre più operazioni di join da fare (molto dispendiose).
Inoltre, non sempre è possibile conservare tutte le dipendenze, quindi la 4nf porta a perdita dei dati.
La 4NF è poco usata nelle applicazioni odierne, in quanto la 3NF e la BCNF già forniscono il giusto compromesso tra semplicità e qualità dei risultati
Problema 1nf che non è 4nf (DOMANDA ORALE NON HO CAPITO)
Perché la 1NF non permette attributi multivalore che siano essi stessi composti. Queste relazioni sono dette relazioni nidificate perché ogni tupla può avere al suo interno una relazione.
