Decomposition

La decomposizione di uno schema di relazione è un processo fondamentale nella progettazione di basi di dati. L’obiettivo principale è ottenere schemi più semplici e coerenti, spesso in Terza Forma Normale (3NF), garantendo al tempo stesso due requisiti essenziali:

• Preservare le dipendenze funzionali: tutte le regole di integrità che valevano sullo schema originario devono continuare a valere.
• Assicurare il join senza perdita: ogni istanza legale dello schema originario deve poter essere ricostruita mediante join naturale, senza introdurre tuple spurie o informazioni estranee.

La decomposizione viene tipicamente applicata quando lo schema non è già in 3NF, oppure per motivi di efficienza degli accessi (ridurre la dimensione delle tuple permette di caricarne di più in memoria e separare informazioni usate in contesti diversi migliora le prestazioni).

---

DEFINIZIONE

Sia R uno schema di relazione. Una decomposizione di R è una famiglia ρ = {R₁, R₂, …, R_k} di sottoinsiemi di R che ricopre R, ovvero:

${\bigcup }_{i=1}^k{R}_i=R$

Se lo schema R è composto da un certo insieme di attributi, decomporlo significa definire dei sottoschemi che contengono ognuno un sottoinsieme degli attributi di R. I sottoschemi possono avere attributi in comune, e la loro unione deve necessariamente contenere tutti gli attributi di R.

---

DECOMPOSIZIONI CHE PRESERVANO LE DIPENDENZE

Sia R uno schema di relazione. F un insieme di dipendenze funzionali su R e ρ = {R₁, R₂, …, R_k} decomposizione di R, diciamo che ρ preserva F se:

$F\equiv {\bigcup }_{i=1}^k{\pi }_{R_i}(F)$

dove:

${\pi }_{R_i}(F)=\{X\to Y|X\to Y\in F^{+}\wedge XY\subseteq R_i\}$

Ogni π_Ri(F) è un insieme di dipendenze funzionali dato dalla proiezione dell’insieme di dipendenze funzionali F sul sottoschema R_i. Contiene solo le dipendenze di F⁺ che hanno tutti gli attributi (determinati e determinanti) in R_i.

---

Verifica:

Verificare se una decomposizione preserva un insieme di dipendenze funzionali F richiede che venga verificata l’equivalenza dei due insiemi di dipendenze funzionali F e G=∪_i=1^k π_Ri(F) e quindi che valga la doppia inclusione F⁺⊆ G⁺ e G⁺⊆ F⁺.

---

Prima inclusione:

Dimostriamo che G⁺⊆ F⁺:

Per come è stato definito G in questo caso sarà sicuramente G ⊆ F⁺, infatti: G=∪_i=1^k π_Ri(F), dove π_Ri(F) = { X → Y | X → Y ∈ F⁺ ∧ XY ⊆ R_i } quindi ogni π_Ri(F) che viene inclusa in G è per definizione una porzione di F⁺. Inoltre, per il lemma: G ⊆ F⁺ ⟹ G⁺⊆ F⁺, inclusione verificata.

---

Seconda inclusione:

Dimostriamo che F⁺⊆ G⁺:

Dimostrare che F ⊆ G⁺ significa verificare che per ogni X → Y ∈ F, vale Y ⊆ X⁺_G, infatti: Se Y ⊄ X⁺_G allora X → Y ∉ G^A per il lemma e quindi X → Y ∉ G⁺ per il teorema. Quindi basta verificare che anche una sola dipendenza in F non appartiene alla chiusura di G per poter affermare che l’equivalenza non sussiste. Per farlo si utilizza un semplice algoritmo iterativo:

Algoritmo verifica F ⊆ G⁺:

begin
	success := true
	for every X → Y ∈ F do:
	begin
		calculate Z    # Z = chiusura di X rispetto a G
		if Y ⊄ Z then: success := false
	end
end

• Input: due insiemi F e G di dipendenze funzionali su uno schema R e la chiusura X⁺_G dell’insieme di attributi X rispetto a G (Z = X⁺_G).
• Output: la variabile booleana success (se success = true allora F ⊆ G⁺).

---

Per il calcolo di X⁺_G si potrebbe ricorrere all’algoritmo del calcolo della chiusura di un insieme di attributi, ma per farlo dovremmo prima calcolare G. Sappiamo però che per definizione: G=∪_i=1^k π_Ri(F), dove π_Ri(F) = { X → Y | X → Y ∈ F⁺ ∧ XY ⊆ R_i } Dunque per costruire G in modo diretto, dovremmo prima avere F⁺. Ma il calcolo di F⁺ è noto per essere esponenziale nel numero di attributi, perché può generare un numero enorme di dipendenze funzionali implicate. Ricorriamo quindi a un algoritmo che ci permette di calcolare X⁺_G a partire da F:

Algoritmo calcolo X⁺_G:

begin
	Z := X
	S := Ø
	for i := 1 to k do: S := S ∪ [(Z ∩ Rᵢ)⁺ ∩ Rᵢ]
	while S ⊄ Z do:
	begin
		Z := Z ∪ S
		for i := 1 to k do: S := S ∪ [(Z ∩ Rᵢ)⁺ ∩ Rᵢ]
	end
end

• Input: uno schema R, un insieme F di dipendenze funzionali su R, una decomposizione ρ = {R₁, R₂, …, R_k} di R, un sottoinsieme X di R;
• Output: la chiusura X⁺_G di X rispetto a G=∪_i=1^k π_Ri(F) (nella variabile Z).

---

Idea di base:

Invece di calcolare prima F⁺ e poi costruire G (operazione esponenziale), l’algoritmo simula direttamente la proiezione e l’applicazione delle dipendenze di G usando solo F. Il meccanismo è semplice: per ogni sottoschema R_i, si prende Z ∩ R_i (gli attributi di Z che stanno in R_i), si calcola la loro chiusura rispetto a F, e si aggiungono a Z solo gli attributi risultanti nella chiusura che appartengono a R_i.

---

Inizializzazione:

Z sarà la variabile che contiene X⁺_G.

Z := X

All’inizio conosciamo solo che X determina se stesso (per riflessività), quindi X ⊆ X⁺_G.

S := Ø

S è l’insieme temporaneo di attributi che si possono aggiungere a Z ad ogni ciclo (inizialmente vuoto).

---

Ciclo di scelta iniziale degli attributi:

for i := 1 to k do: S := S ∪ [(Z ∩ Rᵢ)⁺ ∩ Rᵢ]

Per ogni sottoschema R_i:

• Prendi gli attributi già presenti in Z che appartengono a R_i : Z ∩ R_i
• Calcola la loro chiusura rispetto a F : (Z ∩ R_i)⁺_F
• Mantieni solo gli attributi della chiusura che stanno in R_i : (Z ∩ R_i)⁺_F ∩ R_i
• Aggiungi a S gli attributi risultanti : S ∪ [(Z ∩ R_i)⁺_F ∩ R_i]

---

Ciclo di espansione:

while S ⊄ Z do:

Se S contiene attributi non ancora in Z, allora possiamo espandere Z.

Z := Z ∪ S

Aggiungiamo S a Z.

for i := 1 to k do: S := S ∪ [(Z ∩ Rᵢ)⁺ ∩ Rᵢ]

Ripetiamo il calcolo di S con il nuovo Z. Questo può produrre ulteriori attributi deducibili, che verranno aggiunti al prossimo ciclo.

Continuiamo finché S non aggiunge più nulla (cioè S ⊆ Z).

---

Teorema sulla validità dell’algoritmo calcolo X⁺_G:

L’algoritmo calcola correttamente X⁺_G con G=∪_i=1^k π_Ri(F).

---

Dimostrazione:

Indichiamo con Z₀ il valore iniziale di Z (Z₀ = X) e con Z_j ed S_j, con j ≥ 1, i valori di Z ed S dopo la j-esima esecuzione del corpo del ciclo. Facile vedere che, per ogni j:

$Z_j\subseteq Z_{j+1}$

Ricorda: In Z_j ci sono gli attributi aggiunti a Z fino alla j-esima iterazione. Alla fine di ogni iterazione aggiungiamo qualcosa a Z da S, ma non eliminiamo mai nessun attributo in Z.

Sia f tale che S_f ⊆ Z_f (cioè Z_f = valore di Z al termine dell’algoritmo = X⁺_G), dimostriamo che:

$Z_f=X_G^{+}$

---

Prima inclusione:

Dimostriamo che Z_f ⊆ X⁺_G:

---

Caso base (j = 0):

$Z_0=X\subseteq X_G^{+}⟹Z_0\subseteq X_G^{+}$

Per riflessività, tutti gli attributi in X appartengono a X⁺_G, perché X⁺_G è l’insieme di tutti gli attributi determinati in G a partire da X. Caso base verificato.

---

Ipotesi induttiva:

$Z_j\subseteq X_G^{+}$

Si assume che tutti gli attributi ottenuti con al più j iterazioni dell’algoritmo siano già in X⁺_G.

---

Passo induttivo (j > 0):

$Z_{j+1}\subseteq X_G^{+}$

Bisogna mostrare che anche ogni attributo in Z_j+1 è contenuto in X⁺_G, dunque che ogni attributo in Z_j ∪ S_j è contenuto in X⁺_G (dato che per l’algoritmo: Z_j+1 = Z_j ∪ S_j).

Se A ∈ Z_j allora per ipotesi induttiva A ⊆ X⁺_G, dunque in questo caso il passo è dimostrato.

Se A ∈ S_j allora per definizione di S_j esiste un indice i ≤ k tale che A ∈ [(Z_j ∩ R_i)⁺_F ∩ R_i]. Dunque, per definizione di chiusura, se A ∈ S_j allora (Z_j ∩ R_i) → A ∈ F⁺, con (Z_j ∩ R_i) ∪ A ⊆ R_i. Ciò significa che A è derivabile da (Z_j ∩ R_i)​ usando dipendenze che coinvolgono solo attributi di R_i​. Tali dipendenze appartengono sicuramente alla proiezione π_Ri(F) = { X → Y | X → Y ∈ F⁺∧ XY ⊆ R_i }, (in questo caso X = (Z_j ∩ R_i)​ e Y = A) quindi, per definizione, appartengono a G (ricordiamo che G=∪_i=1^k π_Ri(F)). Dunque, se (Z_j ∩ R_i) → A ∈ G e (Z_j ∩ R_i) ⊆ Z_j ⊆ X⁺_G allora A ⊆ X⁺_G. Anche in questo caso il passo è dimostrato.

Abbiamo dimostrato che l’algoritmo non introduce attributi “a caso”. Ogni attributo che aggiunge è davvero derivabile da X usando le dipendenze in G, quindi Z_f ⊆ X⁺_G.

---

Seconda inclusione:

Dimostriamo che X⁺_G ⊆ Z_f:

---

L’algoritmo parte da (Z₀ = X) e poi aggiunge attributi senza mai rimuoverne. Quindi alla fine sarà sempre valida la condizione:

$X\subseteq Z_f$ L’algoritmo si ferma solo quando non riesce più ad aggiungere attributi applicando le dipendenze funzionali in G. Questo significa che, se esistesse una dipendenza Y → A ∈ G con Y ⊆ Z_f ma A ∉ Z_f, l’algoritmo potrebbe ancora aggiungere A a Z_f e quindi non sarebbe terminato. Poiché è terminato (abbiamo raggiunto Z_f), una situazione del genere non può esistere e quindi possiamo dire che Z_f è già chiuso, cioè:

$(Z_f{)}_G^{+}=Z_f$

Una proprietà generale della chiusura di X che nasce dalla monotonia delle chiusure è: se X ⊆ Y allora X⁺_G ⊆ Y⁺_G. Qui sappiamo che X ⊆ Z_f, quindi: X⁺_G ⊆ (Z_f)⁺_G. Ma dato che (Z_f)⁺_G = Z_f, allora X⁺_G ⊆ Z_f. L’inclusione è dimostrata, infatti, al termine dell’algoritmo, Z_f deve contenere tutto ciò che è derivabile da X in G.

---

DECOMPOSIZIONI CON JOIN SENZA PERDITA

Sia R uno schema di relazione. Una decomposizione ρ = {R₁, R₂, …, R_k} di R ha un join senza perdita se per ogni istanza legale r di R si ha:

$r={\pi }_{R_1}(r)⨝{\pi }_{R_2}(r)⨝...⨝{\pi }_{R_k}(r)=m_{\rho }(r)$

Ogni π_Ri(r) è un insieme di tuple dato dalla proiezione dell’istanza r sul sottoschema R_i. Contiene solo le tuple di r che hanno tutti gli attributi in R_i.

---

Teorema sulle decomposizioni con join senza perdita

Sia R uno schema di relazione e ρ = {R₁, R₂, …, R_k} una decomposizione di R. Per ogni istanza legale r di R, indicato con m_ρ(r) = π_R1(r) ⨝ π_R2(r) ⨝ … ⨝ π_Rk(r) si ha:

• r ⊆ m_ρ(r)
• π_Ri(m_ρ(r)) = π_Ri(r)
• m_ρ(m_ρ(r)) = m_ρ(r)

m_ρ(r) è il join delle proiezioni di r sui sottoschemi R_i, cioè l’istanza di R ricostruita a partire dalla decomposizione ρ.

---

Dimostrazione r ⊆ m_ρ(r):

Dimostriamo che ogni tupla di r compare anche in m_ρ(r). Il join delle proiezioni infatti non perde mai tuple originali (può solo aggiungerne di altre).

Sia t una tupla ∈ r. Proiettando r su R_i, la parte di t sugli attributi di R_i compare in π_Ri(r) (ovvero t[R_i] ∈ π_Ri(r) per ogni i ∈ {1, …, k}). Nel join naturale m_ρ(r) delle proiezioni, tutte queste parti compatibili si ricombinano, quindi la tupla t viene ricostruita, ovvero t ∈ m_ρ(r) (ogni tupla di r è anche in m_ρ(r)).

---

Dimostrazione π_Ri(m_ρ(r)) = π_Ri(r):

Dimostriamo che se si prende il join m_ρ(r) e lo si proietta su R_i, si ottiene esattamente la stessa proiezione che si aveva da r. Bisogna dimostrare due inclusioni.

1. Per il punto 1 si ha r ⊆ m_ρ(r) e, quindi π_Ri(r) ⊆ π_Ri(m_ρ(r)) è dimostrata (proiettando entrambi sui campi R_i​, l’inclusione resta valida).
2. Dimostriamo ora che anche π_Ri(m_ρ(r)) ⊆ π_Ri(r). Sia t ∈ m_ρ(r). Per definizione di join naturale, la tupla t è stata ottenuta combinando tuple provenienti dalle proiezioni di r, cioè: t = t₁ ∪ t₂ ∪ … ∪ t_k con t₁ ∈ π_R1(r), t₂ ∈ π_R2(r), …, t_k ∈ π_Rk(r) e tutte compatibili sugli attributi in comune. In particolare, la parte della tupla t sugli attributi R_i coincide con la tupla t_i, quindi t[R_i] = t_i. Poiché t_i ∈ π_Ri(r), segue che: t[R_i] ∈ π_Ri(r). Questo vale per ogni t ∈ m_ρ(r), quindi π_Ri(m_ρ(r)) ⊆ π_Ri(r).

---

Dimostrazione m_ρ(m_ρ(r)) = m_ρ(r):

Dimostriamo che se si prende l’istanza ricostruita m_ρ(r) e si applica di nuovo la stessa operazione di decomposizione e join, si ottiene lo stesso risultato (idempotenza). Questo è importante perché assicura che la ricostruzione è stabile e non dipende da quante volte si applica l’operazione.

Per definizione m_ρ(m_ρ(r)) = π_R1(m_ρ(r)) ⨝ π_R2(m_ρ(r)) ⨝ … ⨝ π_Rk(m_ρ(r)). Dal punto 2 già dimostrato sappiamo che π_Ri(m_ρ(r)) = π_Ri(r) per ogni i. Sostituendo: m_ρ(m_ρ(r)) = π_R1(r) ⨝ π_R2(r) ⨝ … ⨝ π_Rk(r) = m_ρ(r).

---

Algoritmo verifica join senza perdita:

begin
	build r
	repeat
	begin
		for every X → Y ∈ F do:
		begin
			if ∃ t₁,t₂ ∈ r tali che t₁[X] = t₂[X] e t₁[Y] ≠ t₂[Y] then:
			begin
				for every Aⱼ in Y do:
				begin 
					if t₁[Aⱼ] = "aⱼ" then: t₂[Aⱼ] := t₁[Aⱼ]
					else: t₁[Aⱼ] := t₂[Aⱼ]
				end
			end
		end
	end
	until: r ha almeno una riga con tutte "aⱼ" || r non è cambiato
	
	if r ha almeno una riga con tutte "aⱼ" then: ρ ha un lossless join
	else: ρ non ha un lossless join
end

• Input: uno schema di relazione R, un insieme F di dipendenze funzionali su R, una decomposizione ρ = {R₁, R₂, …, R_k} di R.
• Output: decide se ρ ha un join senza perdita.

---

Costruzione di r :

build r

La tabella r ha:

• |R| colonne j (una per ogni attributo di R)
• |ρ| righe i (una per ogni sottoschema R_i)

In ogni cella di r :

• Se l’attributo A_j ∈ R_i, mette il simbolo a_j.
• Se l’attributo A_j ∉ R_i, mette un simbolo distinto b_ij.

N.B. Ogni riga di r rappresenta una proiezione π_Ri(r) del join, definendo gli attributi di R_i con a_j, e gli attributi non in R_i con simboli diversi.

---

Ciclo di propagazione:

repeat
	...
until: r ha almeno una riga con tutte "aⱼ" || r non è cambiato

Ciclo che termina se:

• r contiene almeno una riga con tutte a_j nei campi, oppure
• r non è nell’ultima iterazione del ciclo (cioè si propagano nuove uguaglianze).

for every X → Y ∈ F do:
begin
	if ∃ t₁,t₂ ∈ r tali che t₁[X] = t₂[X] e t₁[Y] ≠ t₂[Y] then:
	begin
		for every Aⱼ in Y do:
		begin 
			if t₁[Aⱼ] = "aⱼ" then: t₂[Aⱼ] := t₁[Aⱼ]
			else: t₁[Aⱼ] := t₂[Aⱼ]
		end
	end
end

Per ogni X → Y ∈ F :

• Se ∃ t₁, t₂ ∈ r tali che t₁[X] = t₂[X] e t₁[Y] ≠ t₂[Y] (definizione di dipendenza funzionale), allora:
  • Per ogni attributo A_j nell’insieme Y (determinato):
    • Se t₁[A_j] = a_j allora : t₂[A_j] acquisisce il valore di t₁[A_j] (ovvero a_j)
    • Se t₁[A_j] ≠ a_j (quindi t₁[A_j] = b_ij) allora : t₁[A_j] acquisisce il valore di t₂[A_j] (che potrebbe essere a_j o b_ij)

N.B. In questo modo stiamo anche rendendo l’istanza r un’istanza legale. Infatti alla fine del ciclo avremo che per ogni t₁[X] = t₂[X] allora t₁[Y] = t₂[Y].

---

Verifica finale:

if r ha almeno una riga con tutte "aⱼ" then: ρ ha un lossless join
else: ρ non ha un lossless join

• Se esiste una riga in r con tutti a_j : significa che la decomposizione è senza perdita di join, perché quella riga rappresenta la tupla originale ricostruita senza ambiguità.
• Se non esiste una riga in r con tutti a_j : la decomposizione è con perdita, perché non si riesce a ricostruire le tuple originali senza generare simboli spuri.

---

Esempio:

R = ABCD F = { A → B, C → D, B → C } ρ = { R₁ = AB, R₂ = BC, R₃ = CD }

Verificare se ρ è una decomposizione con join senza perdita.

---

Costruzione della tabella r :

Colonne: A, B, C, D Righe: una per ciascun sottoschema R₁, R₂, R₃

Regola di riempimento:

• Se l’attributo A_j ∈ R_i, metto a_j
• Altrimenti metto un simbolo distinto b_ij

Tabella iniziale:

Ri	A	B	C	D
R1 (AB)	aA	aB	b1C	b1D
R2 (BC)	b2A	aB	aC	b2D
R3 (CD)	b3A	b3B	aC	aD

---

Ciclo di propagazione con le FD di F:

Applichiamo ripetutamente: per ogni X → Y ∈ F: Se esistono due righe t₁, t₂ tali che t₁[X] = t₂[X] e t₁[Y] ≠ t₂[Y], allora si uniformano i simboli in Y (preferendo gli a_j quando presenti):

---

A → B :

Confronto tra R₁ e R₂:

• Su A: a_A ≠ b_2A quindi A → B qui non si applica (R₁[A] ≠ R₂[A]).

Ri	A	B	C	D
R1 (AB)	aA	aB	b1C	b1D
R2 (BC)	b2A	aB	aC	b2D
R3 (CD)	b3A	b3B	aC	aD

Confronto tra R₂ e R₃:

• Su A: b_2A ≠ b_3A quindi A → B qui non si applica (R₂[A] ≠ R₃[A]).

Ri	A	B	C	D
R1 (AB)	aA	aB	b1C	b1D
R2 (BC)	b2A	aB	aC	b2D
R3 (CD)	b3A	b3B	aC	aD

Confronto tra R₁ e R₃:

• Su A: a_A ≠ b_3A quindi A → B qui non si applica (R₁[A] ≠ R₃[A]).

Ri	A	B	C	D
R1 (AB)	aA	aB	b1C	b1D
R2 (BC)	b2A	aB	aC	b2D
R3 (CD)	b3A	b3B	aC	aD

---

B → C :

Confronto tra R₁ e R₂:

• Su B: a_B = a_B.
• Su C: b_1C ≠ a_C quindi uniformo C mettendo a_C in R₁.

Ri	A	B	C	D
R1 (AB)	aA	aB	aC	b1D
R2 (BC)	b2A	aB	aC	b2D
R3 (CD)	b3A	b3B	aC	aD

Confronto tra R₂ e R₃:

• Su B: a_B ≠ b_3B quindi B → C qui non si applica (R₂[B] ≠ R₃[B]).

Ri	A	B	C	D
R1 (AB)	aA	aB	aC	b1D
R2 (BC)	b2A	aB	aC	b2D
R3 (CD)	b3A	b3B	aC	aD

Confronto tra R₁ e R₃:

• Su B: a_B ≠ b_3B quindi B → C qui non si applica (R₁[B] ≠ R₃[B]).

Ri	A	B	C	D
R1 (AB)	aA	aB	aC	b1D
R2 (BC)	b2A	aB	aC	b2D
R3 (CD)	b3A	b3B	aC	aD

---

C → D :

Confronto tra R₁ e R₂:

• Su C: a_C = a_C.
• Su D: b_1D ≠ b_2D quindi uniformo C mettendo b_2D in R₁.

Ri	A	B	C	D
R1 (AB)	aA	aB	aC	b2D
R2 (BC)	b2A	aB	aC	b2D
R3 (CD)	b3A	b3B	aC	aD

Confronto tra R₂ e R₃:

• Su C: a_C = a_C.
• Su D: b_1D ≠ a_D quindi uniformo C mettendo a_C in R₂.

Ri	A	B	C	D
R1 (AB)	aA	aB	aC	b1D
R2 (BC)	b2A	aB	aC	aD
R3 (CD)	b3A	b3B	aC	aD

Confronto tra R₁ e R₃:

• Su C: a_C = a_C.
• Su D: b_1D ≠ a_D quindi uniformo C mettendo a_C in R₁.

Ri	A	B	C	D
R1 (AB)	aA	aB	aC	aD
R2 (BC)	b2A	aB	aC	aD
R3 (CD)	b3A	b3B	aC	aD

---

Condizione di terminazione e controllo:

Il ciclo si ferma quando:

• La tabella non cambia più, oppure
• Appare una riga con tutti simboli a_j.

A questo punto, la riga R₁ è già tutta in a_j, condizione sufficiente per concludere che la decomposizione ρ = { R₁ = AB, R₂ = BC, R₃ = CD } è senza perdita.

---

Teorema sulla validità dell’algoritmo verifica join senza perdita:

L’algoritmo verifica correttamente se una decomposizione ρ di R ha un join senza perdita.

---

Dimostrazione:

Occorre dimostrare che: se ρ ha un join senza perdita (m_ρ(r) = r per ogni r legale), allora, quando l’algoritmo termina, la tabella r ha una tupla con tutte a_j.

Costruiamo r₀, ovvero l’stanza r nella fase iniziale dell’algoritmo:

• creiamo una tupla t_i0 per ogni R_i
• inseriamo a_j nelle colonne degli attributi di R_i
• inseriamo simboli distinti b_ij nelle altre colonne.

Applichiamo il ciclo di propagazione fino ad ottenere r_f, ovvero l’stanza r nella fase finale dell’algoritmo.

Per ogni tupla t_if nelle colonne di R_i restano sicuramente tutti a_j (per la costruzione di r), quindi t_if[R_i] = (a_j1, a_j2, …) . Cioè la proiezione della tupla t_i sugli attributi del suo schema R_i contiene solo a_j.

Definiamo ora la tupla t^a tale che t^a[R]= (a_j1, a_j2, …, a_jn) cioè la tupla su tutto R che ha solo a_j. Consideriamo poi il join naturale delle proiezioni delle tuple. Il join combina tuple che coincidono sugli attributi in comune:

$t_{1_f}[R_1]\bowtie t_{2_f}[R_2]\bowtie \cdots \bowtie t_{k_f}[R_k]$

Osserviamo che, dato che ogni tupla t_if ha sicuramente a_j nelle colonne del sottoschema R_i corrispondente, sugli attributi comuni tra due sottoschemi R_i1 e R_i2, con R_i1 ∩ R_i2 ≠ Ø (con almeno un attributo in comune su cui fare il join) il valore è sempre a_j. Dunque le tuple sono compatibili e il join produce sicuramente la tupla che ha a_j ovunque. Quindi:

$t^a\in t_{1_f}[R_1]\bowtie \cdots \bowtie t_{k_f}[R_k]$

Inoltre, per definizione, sappiamo che:

$m_{\rho }(r_f)={\pi }_{R_1}(r_f)\bowtie \cdots \bowtie {\pi }_{R_k}(r_f)$

Ora t_if[R_i] è una delle tuple contenute nella corrispondente proiezione π_Ri(r_f), di conseguenza il join delle sole t_if[R_i] produce un sottoinsieme del join di tutte le proiezioni. Quindi:

$t_{1_f}[R_1]\bowtie \cdots \bowtie t_{k_f}[R_k]\subseteq {\pi }_{R_1}(r_f)\bowtie \cdots \bowtie {\pi }_{R_k}(r_f)$

Cioè t^a ∈ m_ρ(r_f).

Abbiamo infine che r_f è legale (soddisfa F, perché l’algoritmo ha applicato e soddisfatto tutte le dipendenze) e ρ è lossless. Per definizione di lossless: r_f = m_ρ(r_f). Dunque se t^a ∈ m_ρ(r_f) e r_f = m_ρ(r_f) allora possiamo concludere che t^a ∈ r_f, cioè in r_f esiste una riga con tutti a_j (l’algoritmo è corretto).

---

CALCOLO DELLA DECOMPOSIZIONE

Dato uno schema di relazione R e una copertura minimale F su R è sempre possibile calcolare in tempo polinomiale una decomposizione ρ = {R₁, R₂, …, R_k} di R tale che:

• per ogni i, i=1, …, k : R_i è in 3NF.
• ρ preserva F.

Per il calcolo ci serviamo di un algoritmo:

---

Algoritmo calcolo ρ:

begin
	S := Ø
	for every A ∈ R such that ∄ X → Y ∈ F | A ∈ X ∪ Y do: S := S ∪ A
	if S ≠ Ø then:
	begin
        R := R - S
        ρ := ρ ∪ S
    end
    if ∃ X → Y ∈ F | (X ∪ Y = R) then: ρ := ρ ∪ R
    else
    begin
        for every X → A ∈ F do: ρ := ρ ∪ (X ∪ A)
    end
end

• Input: uno schema R, una copertura minimale F su R.
• Output: una decomposizione ρ di R che preserva F e che per ogni i, i=1, …, k : R_i è in 3NF.

N.B. La copertura minimale non garantisce che una chiave candidata compaia ancora in qualche dipendenza funzionale. Per questo motivo, se si desidera garantire anche la proprietà di join senza perdita, è necessario verificare che la decomposizione finale ρ contenga almeno un sottoschema che includa una chiave candidata di R. Se ciò non accade, allora si aggiunge esplicitamente una relazione contenente una chiave candidata: ρ := ρ ∪ {K} dove K è una chiave candidata di R. Questo passo non è obbligatorio per la sola preservazione delle dipendenze e per la 3NF, ma diventa necessario se si vuole assicurare che la decomposizione sia anche lossless.

---

Inizializzazione:

S := Ø

S è l’insieme temporaneo di attributi orfani, cioè che non sono coinvolti in nessuna DF di F (inizialmente vuoto).

---

Raccolta degli attributi orfani:

for every A ∈ R such that ∄ X → Y ∈ F | A ∈ X ∪ Y do: S := S ∪ A

Scansiona ogni attributo A di R e verifica se non appare in nessuna dipendenza di F (né nel determinante X né nel determinato Y). Se l’attributo soddisfa tale condizione (è orfano) lo aggiunge a S.

---

Separazione degli attributi orfani:

if S ≠ Ø then:

Se almeno un attributo di R è orfano:

R := R - S

Rimuove gli attributi orfani da R.

ρ := ρ ∪ S

Aggiunge S come nuova relazione (sottoschema di R) nella decomposizione. È una relazione contenente solo attributi orfani.

---

Controllo di una dipendenza totale su R:

if ∃ X → Y ∈ F | (X ∪ Y = R) then: ρ := ρ ∪ R

Se esiste una DF in F il cui insieme di attributi (determinante ∪ determinato) copre esattamente tutti gli attributi attuali di R. Allora aggiunge lo schema R alla decomposizione. Questo copre tutte le DF e rispetta la 3NF perché con copertura minimale e con determinanti appropriati, le violazioni sono evitate o rese ammissibili (attributi primi o dipendenze da chiave).

---

Calcolo della decomposizione per DF minimali:

else

Se non esiste una DF totale su R:

for every X → A ∈ F do: ρ := ρ ∪ (X ∪ A)

Per ogni dipendenza minimale con lato destro singolo A (come richiesto dalla copertura minimale) aggiunge una relazione (sottoschema di R) contenente gli attributi di X insieme all’attributo A (attributi della DF). (N.B.)

---

Perché funziona:

Preservazione delle DF: ogni dipendenza minimale X → A ha una relazione R_i = XA dove la dipendenza è naturalmente valida, quindi l’insieme F è preservato (o ricostruibile via chiusura).

3NF assicurata: con copertura minimale e relazioni R_i costruite come XA, gli attributi determinati sono o primi nelle rispettive relazioni o dipendono da chiavi candidate del loro schema, rispettando la definizione di 3NF. Gli attributi orfani non creano violazioni perché non ci sono DF che li coinvolgono.

Pulizia semantica: separare gli orfani evita di introdurre attributi che non partecipano a vincoli nel mezzo di relazioni R_i governate da DF, riducendo ambiguità e facilitando la manutenzione.

---

Teorema sulla validità dell’algoritmo calcolo ρ:

L’algoritmo calcola correttamente ρ = {R₁, R₂, …, R_k} tale che:

• per ogni i, i=1, …, k : R_i è in 3NF.
• ρ preserva F.

---

Dimostrazione:

Dimostriamo separatamente le due proprietà:

---

1. ρ preserva F:

Sia G = ∪_i=1^k π_Ri(F), per verificare che ρ preserva F dobbiamo dimostrare che F e G siano due insiemi equivalenti.

---

Prima inclusione:

Dimostriamo che F⁺⊆ G⁺:

Sappiamo che per ogni X → A ∈ F si ha XA ∈ ρ, infatti dall’algoritmo notiamo che XA è uno dei sottoschemi di R:

for every X → A ∈ F do: ρ := ρ ∪ (X ∪ A)

Dunque per definizione di proiezione, se XA ⊆ R_i, allora X → A ∈ G, quindi F ⊆ G, e quindi F⁺ ⊆ G⁺.

N.B. La chiusura è monotona (può solo crescere o restare uguale all’insieme di partenza): quindi se G contiene tutte le DF di F allora la sua chiusura G⁺ conterrà sicuramente tutte le DF in F⁺.

---

Seconda inclusione:

Dimostriamo che G⁺⊆ F⁺:

Sempre per definizione, G è ottenuto proiettando F sui vari sottoschemi, quindi ogni DF in G proviene da F⁺, dunque G ⊆ F⁺ e, per il lemma: G⁺⊆ F⁺

---

Conclusione:

Abbiamo dimostrato entrambe le inclusioni, dunque F⁺ = G⁺, ρ preserva F.

---

2. Ogni R_i in ρ è in 3NF:

Analizziamo i diversi casi che si possono presentare:

---

Caso 1 (S ∈ ρ):

if S ≠ Ø then:
begin
    R := R - S
    ρ := ρ ∪ S 
end

S è l’insieme degli attributi orfani. Per definizione, se un attributo non è determinato da nessuno, l’unico modo per “coprirlo” è che faccia parte della chiave. Quindi in ogni relazione S, tutti gli attributi sono primi (appartengono alla chiave). Dunque se S ∈ ρ, ogni attributo in S fa parte della chiave e quindi, banalmente, S è in 3NF.

---

Caso 2 (R ∈ ρ):

if ∃ X → Y ∈ F | (X ∪ Y = R) then: ρ := ρ ∪ R

Esiste una dipendenza funzionale X → A ∈ F che coinvolge tutti gli attributi di R. Poiché F è una copertura minimale (condizione necessaria affinché l’algoritmo funzioni) la dipendenza X → A è sicuramente della forma: (R - A) → A e quindi R - A è chiave nello schema R. Prendendo una qualsiasi Y → B ∈ F⁺ con YB ⊆ R:

• Se B = A, allora per minimalità Y = R - A in quanto non può esistere un sottoinsieme proprio della chiave candidata che determina A. Dunque Y è chiave candidata e la DF rispetta la 3NF.
• Se B ≠ A, allora B ∈ R - A, ovvero B appartiene a una chiave candidata, dunque B è un attributo primo e per questo la DF rispetta la 3NF.

Dunque anche in questo caso ρ è in 3NF.

---

Caso 3 (XA ∈ ρ):

else
begin
	for every X → A ∈ F do: ρ := ρ ∪ (X ∪ A)
end

Per ogni DF minimale X → A ∈ F, l’algoritmo costruisce il sottoschema X ∪ A. Poiché F è una copertura minimale, non può esistere un sottoinsieme X^’⊆ X tale che X^’→ A dunque X è chiave nello schema XA. Prendendo una qualsiasi Y → B ∈ F⁺ con YB ⊆ XA:

• Se B = A, allora per minimalità Y = X in quanto non può esistere un sottoinsieme proprio della chiave candidata che determina A. Dunque Y è chiave candidata e la DF rispetta la 3NF.
• Se B ≠ A, allora B ∈ X, ovvero B appartiene a una chiave candidata, dunque B è un attributo primo e per questo la DF rispetta la 3NF.

Dunque anche in questo caso ρ è in 3NF.

---

Teorema sul calcolo di ρ con lossless join:

Dato uno schema di relazione R, una copertura minimale F su R e una decomposizione ρ di R prodotta dall’algoritmo di decomposizione: La decomposizione σ = ρ ∪ W, dove W è una chiave per R, è tale che:

• per ogni i, i=1, …, k : R_i è in 3NF.
• σ preserva F.
• σ ha un join senza perdita.

---

Dimostrazione:

Dimostriamo separatamente le tre proprietà:

---

1. σ preserva F:

Sia G^’= ∪_i=1^k π_Ri(F), per verificare che σ preserva F dobbiamo dimostrare che F e G^’ siano due insiemi equivalenti.

Poiché ρ preserva F (per il teorema) anche σ preserva F. Infatti σ = ρ ∪ W quindi stiamo aggiungendo una nuova proiezione π_Z(F) all’insieme G : G^’= G ∪ π_Z(F). Dunque F ⊆ G ⊆ G^’e quindi per la monotonia della chiusura vale: F⁺ ⊆ G⁺ ⊆ G^’+ .

Inoltre, per definizione, G^’ è ottenuto proiettando F sui vari sottoschemi, quindi ogni DF in G^’ proviene da F⁺, dunque G^’⊆ F⁺ e, per il lemma: G^’+⊆ F⁺

Abbiamo dimostrato entrambe le inclusioni, dunque F⁺ = G^’+, σ preserva F.

---

2. Ogni R_i in σ è in 3NF:

Poiché ogni schema di relazione in ρ è in 3NF (per il teorema) e σ = ρ ∪ W, è sufficiente verificare che anche lo schema di relazione Z sia in 3NF per poter affermare che ogni schema di relazione in σ sia in è in 3NF.

Supponiamo per assurdo che W non sia una chiave per lo schema Z (sappiamo che è impossibile in quanto, per riflessività, W → W vale sempre). Allora esiste un sottoinsieme W^’ di W che determina tutto lo schema W, ovvero tale che W^’→ W ∈ F⁺. Poiché W è chiave per lo schema R, ovvero W → R ∈ F⁺, pertanto, per transitività abbiamo W^’→ R ∈ F⁺, ma questo contraddice il fatto che W è chiave per lo schema R (verrebbe violato il principio di minimalità). Pertanto W è chiave per lo schema Z e quindi per ogni dipendenza funzionale X → A ∈ F⁺ con XA ⊆ W: A è attributo primo (appartiene alla chiave W).

---

3. σ ha un join senza perdita:

Sappiamo che W è una chiave per R, quindi W⁺= R. Utilizzando quindi l’algoritmo per il calcolo della chiusura su W possiamo determinare tutti gli attributi di R - W grazie alle dipendenze funzionali minime sullo schema R. L’algoritmo produce una lista ordinata di attributi determinati A₁, A₂, …, A_n e, per ciascuno di essi, un determinante Y_i ⊆ Z_i-1 tale che Y_i → A_i ∈ F. Quindi l’algoritmo produrrà Z₀ = W e Z_i = Z_i-1 ∪ A_i.

Poiché F è una copertura minimale, per ogni dipendenza Y_i → A_i lo schema Y_iA_i appartiene alla decomposizione ρ, e quindi anche a σ.

Applicando alla decomposizione σ l’algoritmo di verifica del join senza perdita, e utilizzando come insieme di dipendenze funzionali su R, l’insieme F di dipendenze Y_i → A_i con cui abbiamo calcolato la chiusura W⁺, possiamo dimostrare per induzione che σ ha un join senza perdita.

Costruiamo la tabella r con una riga per ogni sottoschema di σ. In particolare:

• La riga di W ha inizialmente a_j su tutti gli attributi di W.
• La riga di ciascun sottoschema Y_iA_i ha a_j su Y_i e, per propagazione, anche su A_i.

Consideriamo le dipendenze Y₁ → A₁, Y₂ → A₂, …, Y_n → A_n nell’ordine in cui gli attributi entrano nella chiusura di W. Dimostriamo per induzione che, dopo aver applicato la dipendenza Y_i → A_i, la riga di W contiene a_j su tutti gli attributi Z_i.

N.B. L’ordine delle dipendenze dato dal calcolo di W⁺ ci garantisce che nella tabella r, al passo i, la riga di W ha già a_j su Y_i, quindi la DF Y_i → A_i è applicabile e possiamo propagare la a_j su A_i.

---

Caso base (i = 1):

$Y_1\subseteq Z_0=W$

Quindi :

• La riga W ha già a_j su tutti i suoi attributi e quindi anche su Y₁.
• La riga Y₁A₁ ha a_j su Y₁ e su A₁.

Applicando la regola dell’algoritmo alla DF Y₁ → A₁ propaghiamo la a_j di A₁ (sulla riga di Y₁) pure sulla riga di W. Risultato: la riga di W ha a_j su tutti gli attributi di Z₁ = W ∪ A₁.

---

Ipotesi induttiva:

$Y_{i+1}\subseteq Z_i=Z_{i-1}\cup A_i$

Si assume che per ogni i > 1, nella riga corrispondente a W nella tabella r, ci sia una a_j in corrispondenza di ogni attributi A_j con j ≤ i - 1 (lossless join sempre verificato).

---

Passo induttivo (i > 1):

Supponiamo valida l’ipotesi induttiva. Nella riga corrispondente a W nella tabella r ci sono già tutte le a_j sugli attributi di Z_i-1. Ora consideriamo l’attributo A_i che entra in chiusura grazie alla dipendenza funzionale minimale Y_i → A_i con Y_i ⊆ Z_i-1:

• La riga W, per ipotesi, ha già a_j su tutti gli attributi di Z_i-1, e quindi anche su Y_i.
• La riga Y₁A₁ ha a_j su Y₁ e su A₁.

Poiché le due righe concordano con a_j su Y_i, l’algoritmo di verifica del join senza perdita applica la DF Y_i → A_i e propaga la a_j su A_i anche nella riga di W.

Dunque La riga di W contiene ora a_j su tutti gli attributi di Z_i = Z_i-1 ∪ A₁:

Ripetendo questo ragionamento per ogni i=1, …, n, otteniamo che la riga di W si arricchisce progressivamente di tutte le a_j fino a coprire l’intero schema:

$Z_n=R$

Quindi, al termine, la tabella r contiene una riga tutta a_j, e per definizione dell’algoritmo la decomposizione σ ha un join senza perdita.

---