Marzo 2015 Archive

Troviamo le chiavi nella relazione
R(A, B, C)
F={A→B, B→C}

A è prima, perché si trova solo a sinistra di una relazione, B e C sono non prime.

Facciamo uno schemino con tre colonne: nella prima ci sono gli attributi che compaiono solo a sinistra, nella terza gli attributi che sono presenti sia a sinistra sia a destra di una DF, in mezzo gli attributi presenti sia a destra sia a sinistra di qualche DF.

 S | E | D
---+---+---
 A | B | C
---+---+---

Altro esempio:
R(ABCD)
F={AB→C, C→B, C→D}

 S | E | D
---+---+---
 A | B | D
   | C | 
---+---+---

A⁺ è dato da A, ma ora dobbiamo trovare la chiusura di AB^{+, che è ABCD e la chiusura di AC+, che è ACBD.}

La chiave primaria è data da ABC.

Altro esempio:
R(ABC)
F={A→B, B→C, C→A}

 S | E | D
---+---+---
   | A | 
   | B | 
   | C | 
---+---+---

"Really sticky situation".

La chiave è (ABC) e la superchiave è - ovviamente - ABC

https://www.youtube.com/watch?v=hTFyG5o8-EA

Una relazione R(A₁, A₂, ... A_n)può essere scomposta in due relazioni:
R₁(B₁, B₂, ... B_k)
R₂(C₁, C₂, ... C_k)

e le relazioni risultanti sono di Boyce Codd se:

1. Gli attributi di R₁ ⋃ gli attributi di R₂ = gli attributi di R
2. La join naturale R₁ ⨝ R₂ è la proiezione di R
3. Ogni attributo in comune tra R₁ e R₂ è una chiave

Per esempio:

Studenti(CodiceFiscale, Nome, Indirizzo, CodiceScuola, NomeScuola, NomeCittà, Punteggio, Priorità)

ha le seguenti DF:

CodiceFiscale → Nome, Indirizzo, Punteggio
Punteggio → Priorità
CodiceScuola → NomeScuola, NomeCittà

è in forma Boyce-Codd?

Le chiavi sono: CodiceFiscale, CodiceScuola.

Ogni DF ha una chiave contenente CodiceFiscale e Scuola? NO! Quindi la relazione non è in BCFN.

Altro esempio:

Iscritto(CodiceFiscale, Nome, Stato, Data, Maggiorenne

La DF è: CodiceFiscale, Nome, Stato → Data, Maggiorenne

è quindi in BCNF.

Algoritmo per decomporre una relazione in BCNF

Input: relazione + dipendenze funzionali

Output: decomposizione di R in relazioni che rispettano la BCNF senza perdita di join

1. Calcolare le chiavi di R
2. Ripetere finché tutte le relazioni non sono in BCNF:
   1. Prendere ogni R' con A→B che viola la BCNF
   2. Decomporre R' in R₁(A, B), R₂(A, resto). La join tra le relazioni deve restituire R
   3. Calcolare le dipendenze funzionali di R₁ e R₂
   4. Calcolare le chiavi di R₁ e R₂

Esempio:

Studenti(CodiceFiscale, Nome, Indirizzo, CodiceScuola, NomeScuola, NomeCittà, Punteggio, Priorità)

ha le seguenti DF:

CodiceFiscale → Nome, Indirizzo, Punteggio
Punteggio → Priorità
CodiceScuola → NomeScuola, NomeCittà

Come sopra, la chiave è CodiceFiscale, CodiceScuola

Creiamo due relazioni

S₁(CodiceScuola, NomeScuola, NomeCittà)

S₂(CodiceFiscale, Nome, Indirizzo, CodiceScuola, Punteggio, Priorità)

Ora S₁ è in BCNF

Invece S₂ non è in BCNF, quindi la decomponiamo in:

S₃(Punteggio, Priorità)

S₄(CodiceFiscale, Nome, Indirizzo, CodiceScuola, Punteggio)

Ora S₃ è in BCNF.

Invece S₄ non è in BCNF, quindi la decomponiamo in:

S₅(CodiceFiscale, Nome, Indirizzo, Punteggio)

S₆(CodiceFiscale, CodiceScuola)

Finalmente abbiamo S₁, S₃, S₅, S₆ che rappresentano la BCNF della relazione senza perdita di join.

 

Alcuni esempi, redatti con l'aiuto di http://dblab.dsi.unive.it:8080/

Attributi	Dipendenze funzionali	Chiavi	Attributi primi	Boyce-Codd	3NF	Commento
a	-	{(a)}	(a)	R<(a){}>	R<(a){}>	Nessuna d.f.
a	a→a	{(a)}	(a)	R<(a){}>	R<(a){}>	D.f. banale, non si riporta
a, b	a→b	{(a)}	(a)	R<(a,b){a→b}>	R<(a,b){a→b}>
a, b	a→b, b→a	{(a), (b)}	(a b)	R<(a,b){a→b,b→a}>	R<(a,b){b→a}>	Differenza tra BC e 3NF: nel primo caso sono esplicite entrambe le d.f., nella 3NF solo una
a, b, c	a→b, b→c	{(a)}	(a)	R1<(a,b){a→b}>, R2<(b,c){b→c}>	R1<(a,b){a→b}>, R2<(b,c){b→c}>	In entrambi i casi, si "estrae" una relazione. Dipendenze preservate.

Nota bene: b non è una chiave, ma diventa la chiave di una nuova relazione sia secondo BC sia secondo 3NF

a, b, c	a→b, ab→c	{(a)}	(a)	R<(a,b,c){a→b,a→c}>	R<(a,b,c){a→bc}>	b è determinato da a, quindi c è determinato dalla sola a (secondo Boyce-Codd) oppure in ogni caso da ab (secondo 3NF)
a, b, c	a→b, ab→c, bc→a	{(a),(bc)}	(abc)	R<(a,b,c) {a→b, a→c, bc→a}>	R<(a,b,c) {bc→a}>
a, b, c, d, e, g, h, i	adg→gi ach→adg bc→ad ce→ach	{(bce)}	(bce)	R<(a,b,c) {a→b, a→c, bc→a}>	R<(a,b,c) {bc→a}>

Transazione

Atomicità: un'operazione può essere o completata o annullata, non può essere completata parzialmente

Persistenza: se una transazione termina con successo, le modifiche devono essere mantenute sui dati

Serializzabilità: non possono essere eseguite due transazioni che interferiscono tra loro (ved. esempio due prelievi bancomat contemporanei)

Problemi / giornale

• La transazione fallisce
• C'è un problema esterno temporaneo (es. caduta della corrente elettrica)
• C'è un disastro (rottura di un disco)

La garanzia per tutti e tre i tipi di problema è il giornale, cioè un log delle transazioni.

Il giornale è compilato con il contenuto delle transazioni e ogni tanto avviene un allineamento con la base dati. L'allineamento può avvenire tramite una sospensione di tutte le transazioni, ma esistono anche tecniche che riducono i tempi di attesa.

Disfare le transazioni

Se un'operazione fallisce la transazione si deve DISFARE.

Se un'operazione riesce ma non siamo sicuri che il dato sia scritto nel disco, occorre RIFARE.

Il giornale NON è soggetto a buffering, quindi le informazioni sono sempre scritte direttamente sul disco.

 

Organizzazione fisica dei file

Heap: inserisco i dati a caso. È il metodo utilizzato di default nel filesystem. Può andare bene per pochi dati o accessi sempre su tutti i dati.

Sequenziale: inserisco i dati in ordine, con un ordine scelto a priori. Con un ordinamento sequenziale il costo dell'accesso a un dato è di N*log₂(N).

L'ordinamento tipico di ordinamento nei database che memorizzano i dati in modo sequenziale è merge sort. MS si presta bene al calcolo in parallelo su più processori.

L'ordinamento può essere effettuato tramite hash o tramite albero, e può essere statico (le informazioni, una volta inserite, non cambiano) o dinamico.

Nell'hash si trasforma una hash in un indirizzo di pagina. Bisogna gestire le eccezioni (collisioni) e la possibilità che i dati aumentino o diminuiscano molto. L'hash è estremamente efficiente. L'hash si presta molto poco alla ricerca su intervallo.

La struttura ad albero permette sia un accesso diretto a un dato sia a un intervallo con un tempo di esecuzione molto soddisfacente. L'organizzazione ad albero B⁺ può essere applicato sia al dato sia a un indice.

Inoltre la struttura ad albero restituisce insiemi di dati già ordinati.

Gli indici devono essere usati con parsimonia e buon senso, perché la loro aggiunta selvaggia compromette i tempi delle operazioni di inserimento e la concorrenza nell'accesso ai dati.

La chiave primaria è corredata automaticamente di un indice, perché permette di verificare velocemente se esiste già una chiave uguale o meno.

Operazioni

Proiezione

π e π⁺ sono le due operazioni algebriche che rappresentano rispettivamente SELECT DISTINCT e SELECT.
π⁺ ha un'esecuzione banale: si eliminano i campi non interessanti e si scrive il risultato.
π invece esclude i duplicati, e funziona:

1. riscrive una copia della tabella con i soli campi che interessano
2. ordina per tutti gli attributi
3. elimina duplicati
4. scrive il risultato

L'operazione di π si indica con due operazioni (SORT + DISTINCT), a indicare che l'operazione di eliminazione dei duplicati agisce in due fasi diverse.

Restrizione

σ è l'operazione algebrica corrispondente alla clausola WHERE (HAVING).

L'operazione funziona in modi diversi se esiste un indice sugli attributi ricercati o se non esiste.

Se non esiste, occorre leggere tutta la tabella e scartare i record non corrispondenti.

Se  esiste, il costo è dato dalla somma del costo per l'accesso all'indice e per l'accesso al dato. Il motore decide quale alternativa è migliore; in generale l'indice conviene quando la restrizione è molto selettiva (estrae pochi record).

Aggregazione

L'aggregazione senza GROUP BY legge i record e applica la funzione di aggregazione.

Con GROUP BY bisogna prima raggruppare i dati e successivamente calcolare l'aggregazione.

In particolare, si ordinano i record sull'attributo di ordinamento e poi si calcolano le funzioni di aggregazione.

Anche in questo caso le operazioni sono SORT + GROUP BY.

Giunzione

Gli algoritmi possibili sono:

• Nested loop: leggo un record alla volta della prima relazione (i), leggo un record della seconda relazione (j) e restituisco il record se gli attributi sono uguali. Il tempo di esecuzione è O(n²). è comodo se la seconda relazione è molto piccola e la prima grande.
• Nested loop a pagine
• Indexed nested loop: usa un indice per fare il confronto (necessita di un indice sul campo di join)
• Merge join: quando entrambe le tabelle sono ordinate sull'attributo di join, l'algoritmo confronta solo i record finché l'attributo non cambia in entrambe le tabelle

Operatori

Lettura dei dati

• TableScan(R): scansione su una tabella
• IndexScan(R, Idx): scansione sull'indice di una tabella
• SortScan(R, {A₁, A₂, ... A_i}): scansione e ordinamento per attributo/i

Proiezione

• Project(R, {A₁, A₂, ... A_i}): proiezione senza eliminazione dei duplicati
• Distinct(R, {A₁, A₂, ... A_i}): proiezione con eliminazione dei duplicati

Restrizione

• Filter(O, ψ)
• IndexFilter(R, Idx, ψ)

Ordinamento

• Sort(R, {A₁, A₂, ... A_i})

Raggruppamento

• GroupBy(O, {A₁, A₂, ... A_i}, {f₁, f₂, ... f_i}): f indica una funzione di aggregazione contenuta in SELECT e HAVING. L'operatore GroupBy è sempre preceduto da un Sort

Giunzione

• NestedLoop(O_E, O_I, ψ_J)
• PageNestedLoop(O_E, O_I, ψ_J)
• IndexNestedLoop(O_E, O_I, ψ_J): O_E rappresenta il risultato di un'operazione di IndexFilter
• MergeJoin(O_E, O_I, ψ_J): O_E e O_I rappresentano due relazioni già ordinate per gli attributi di join

 

Due insiemi di DF, F e G, sullo schema R sono equivalenti F ≡ G sse F⁺ = G⁺

F è una copertura di G e G è una copertura di F.

Copertura canonica

o canonica minima, ci permette di definire un insieme di equivalenze in maniera semplice e compatta.

Sia un insieme di dipendenze funzionali F, un attributo è estraneo sse (X-{A_i})→Y∈F⁺
Per esempio, data una relazione R({Nome, Telefono, Indirizzo, Città, Voto, Materia}, {(Nome, Telefono)→Indirizzo, (Nome, Indirizzo)→Telefono, (Nome, Materia)→Voto, Indirizzo→Città)})

si può scrivere A = Nome, B = Telefono, C = Indirizzo, D = Città, E = Voto, G = Materia

R({A, B, C, D, E, G}, {AB→C, AC→B, AG→E, C→D})

AB→C contiene l'attributo estraneo B, poiché AB-{B}→C è vero, cioè A→C

AC→B contiene l'attributo estraneo C, per lo stesso motivo.

ABGE è una superchiave di R, perché non esistono due elementi con lo stesso valore per gli attributi ABGE.

Però la chiave ABGE contiene un sottoinsieme AG che è superchiave ma è più "ristretta" della superchiave ABGE. Quando una superchiave (come AG) non contiene altre superchiavi più strette, si dice che è chiave.

Gli attributi che non compaiono mai a destra delle DF (come A e G nell'esempio) sono sicuramente contenute in ogni chiave di R.

Gli attributi che compaiono solo a destra delle DF (come D e E nell'esempio) non appartengono a nessuna chiave.

Appartiene a tutte le chiavi	Da determinare	Non appartiene sicuramente ad alcuna chiave
A, G	B, C	D, E

Agli attributi B, C occorre applicare l'algoritmo di chiusura lenta per capire se fanno parte o meno di una chiave.

1. AGB⁺ = AGB
2. AGC⁺ = AGC