Riassunto esame Basi di dati, Prof. Persia, libro consigliato Sistemi di basi di dati e applicazioni, Angelo Chianese, Vincenzo Moscato, Antonio Picariello, Lucio Sansone

X X

1 2

dove r è una qualsiasi relazione sullo schema R(X)

7.5.2 Decomposizione legale

Una decomposizione si dice legale se:

1. è senza perdita

2. mantiene le dipendenze funzionali dello schema originale.

7.6 Terza forma normale

Uno schema R(X) è in terza forma normale se:

1. è in 2NF

2. ogni attributo non primo dipende da tutta e sola la superchiave in R(X).

Una definizione alternativa utilizza la dipendenza transitiva, ovvero R(X) è in 3NF se:

1. è in 2NF

2. ogni attributo non primo dipende non transitivamente da ogni chiave di R.

7.7 Decomposizione

Uno schema non in 3NF si normalizza decomponendo la relazione di partenza in relazioni che soddisfino le

proprietà della 3NF, facendo in modo che non venga alterato il contenuto informativo del database.

17 Esempio

MAGAZZINI

Articolo Magazzino Quantità Città

scarpe NA 2500 Napoli

scarpe RM 1000 Roma {Articolo, →

In questo caso vediamo che esiste la dipendenza funzionale Magazzino} Città, ma anche Magazzino

→ Città (ovvero solo parte della chiave). Si può in questo caso decomporre sulla base di un attributo comune

agli attributi che si vogliono dividere, come ad esempio Magazzino. Il risultato sarà:

ART MAG CIT MAG

Articolo Magazzino Quantità Magazzino Città

scarpe NA 2500 NA Napoli

scarpe RM 1000 RM Roma

Per capire se la decomposizione effettuata è senza perdita (lossless) e quindi è stata fatta correttamente, sia

R(X) la relazione originaria e siano R (X ), R (X ) le relazioni ottenute dopo la scomposizione, allora deve

1 1 2 2

valere che π (r) ▷◁ π (r) = r.

X X

1 2

Si dice che una decomposizione conserva le dipendenze se ciascuna delle dipendenze funzionali della relazione

originaria coinvolge attributi che compaiono tutti insieme in uno degli schemi risultanti. Tale proprietà non

deve necessariamente essere rispettata, ma sarebbe meglio farlo. Si parla di decomposizione legale quando:

1. è lossless

2. conserva le dipendenze

7.8 Forma normale Boyce e Codd →

Si dice che R(X) è in forma normale di Boyce e Codd se per ogni dipendenza funzionale non banale Y Z

deifnita su R(X), Y è superchiave di R(X). Anche in questo caso può essere applicata la decomposizione in modo

che le relazioni risultanti siano ancora in BCNF. In generale, ogni relazione con esattamente due attributi è in

BCNF. 18

8 Struttura di un DBMS

8.1 Introduzione

8.1.1 File di record

I file all’interno di una base di dati vengono visti come insiemi di record, ovvero dati strutturati in campi

atomici. Più record vengono memorizzati in pagine (di 4 o 8 KB) ed ognuno di essi ha un identificatore che

permette di risalire all’indirizzo fisico della pagina che lo contiene. Le operazioni di i/o sono generalmente le

più costose in un DB ed è quindi importante gestirle correttamente.

8.1.2 Fattore di blocco

Assumiamo che ogni tupla di una relazione sia mappata in un record: quando l’utente richiede una tupla, il

DBMS mappa un record logico in un record fisico associato ad una pagina in memoria principale. Il fattore di

blocco è il numero di record logici contenuti in un record fisico.

8.2 Orgnizzazione dei file

I record possono essere memorizzati sui file in diversi modi, ognuno dei quali rende più efficienti delle operazioni

e meno efficienti delle altre. Si dice metodo di accesso l’insieme di tecniche per memorizzare e recuperare i

record da un file, ed il metodo di accesso è strettamente legato al modo in cui i file sono organizzati.

8.2.1 File heap

Nel caso del file heap, o file non ordinati, i record vengono inseriti in coda al file senza rispettare un ordinamento.

Ciò permette di rendere il costo dell’inserimento costante, mentre quelli della ricerca e della cancellazione saranno

lineari. 19

8.2.2 File sequenziali

Nel caso dei file sequenziali, o file ordinati, i record vengono inseriti rispettando l’ordinamento su uno o più

attributi chiamati chiavi di ordinamento (non necessariamente coincidenti alle chiavi primarie). Ciò permette

di rendere la ricerca logaritmica (ricerca binaria) e di velocizzare anche la cancellazione sfruttando lo stesso

principio, ma il costo dell’inserimento sarà lineare.

8.2.3 File hashing

Nel caso del file hashing, viene definita una funzione hash su uno o più attributi chiamati chiavi di hashing. Il

problema delle funzioni hash sono le collisioni, ma possono essere risolte, ad esempio, tramite i bucket, ovvero

delle liste di trabocco che conterranno i record in collisione. Un metodo per accedere a tali record è quello di

attendere l’eliminazione del primo record nella posizione, oppure di scorrere il bucket.

8.3 Indice di accesso

Ad ogni file di record può essere associato un indice di accesso per ogni campo dei record del file. Ciò servirà a

rendere più efficiente l’accesso per valore di quel campo ad un certo record. Gli indici non sono necessari per il

funzionamento di un DBMS ma ne migliorano notevolmente le prestazioni. L’indice viene memorizzato a sua

volta in un file, in cui si ha un ordinamento sul campo relativo a quell’indice. Anche gli indici possono essere

organizzati in modi diversi a seconda di quale operazione si vuole velocizzare. Si dice data entry la ”singola

riga” dell’indice, ovvero una coppia formata da chiave (ID nell’indice) e valore (ID del record ”puntato” dal

data entry nel file di record).

8.3.1 Classificazione in base al tipo di attributi

Gli indici possono essere classificati in tre categorie a seconda del tipo di attributi che vengono scelti per

l’ordinamento, ovvero:

• indice primario se nell’insieme di attributi scelti compare la chiave primaria.

• indice secondario se nell’insieme di attributi scelti compare una chiave non primaria.

• indice clustering se nell’insieme di attributi non sono presenti chiavi e quindi la chiave di un data entry

può corrispondere a più valori.

8.3.2 Classificazione in base ai record

Gli indici possono essere classificati inoltre in due categorie, ovvero:

• indice sparso se non sono rappresentati tutti i record all’interno dell’indice.

• indice denso se sono rappresentati tutti i record all’interno dell’indice.

8.3.3 Organizzazione dell’indice

Un indice può essere organizzato in diverse strutture, a seconda di quale tipo di operazione si vuole privilegiare.

8.3.4 Indexed sequential files

Un file sequenziale indicizzato è un file ordinato con un indice primario. Essendo il file di record organizzato in

pagine ed ordinato, ogni pagina avrà un valore di inizio (o di fine). Nell’indice viene proprio messo tale valore,

quindi una volta capito tra le chiavi di quali data entry si trova il valore cercato, basterà poi accedere alla pagina

corrispondente ed effettuare li una nuova ricerca binaria.

20

8.3.5 Indice multilivello

L’indice di un file sequenziale indicizzato, essendo anch’esso un file di record, può essere a sua volta indicizzato

in un altro indice. Tale operazione si dice indicizzazione multilivello.

8.3.6 Btree

I data entry vengono organizzati in un albero bilanciato 2-3-...-k, dove k è il numero massimo di data entry

che può contenere un nodo. Quando viene inserito un nuovo data entry, esso verrà inserito nel nodo più in

basso mantenendo l’ordinamento e, se tale nodo dovesse essere pieno, allora verrà diviso in due nodi e il valore

centrale sarà trasferito nel nodo padre. Quando invece si effettua una cancellazione, se il nodo rimane con un

k

numero di nodi minore di , allora il nodo viene fuso con uno dei suoi vicini. Entrambe le operazioni possono

2

propagarsi fino alla radice.

+

8.3.7 B tree

È un’evoluzione del Btree in cui i data entry si trovano solo nei nodi foglia dell’albero, mente in quelli intermedi

sono comunque presenti alcuni data entry ma servono solo per orientarsi durante la ricerca binaria. Un’altra

+

caratteristica dei B tree è che le foglie sono collegate tra loro in una linked list, rendendo più efficienti le query

+

ad intervalli. I B tree sono le strutture più utilizzate negli indici dei DBMS.

∗

8.3.8 B tree 23

+

È un’evoluzione del B tree in cui ogni nodo deve contenere almeno k data entry.

8.3.9 Indice di Bitmap

Viene usato su Attributi enumerativi e viene creata una matrice di bit in cui il bit assume valore 1 se il record

associato a quel data entry ha il valore della colonna come valore di quell’attributo.

Impiegati Bitmap sul ruolo

ID Nome Ruolo rid manager analista segretario

1 Giulia manager 001 1 0 0

2 Franco analista 002 0 1 0

3 Daniele segretario 003 0 0 1

4 Davide analista 004 0 1 0

8.3.10 Indice di join

Crea un’indice su un pre-calcolo di un join. Ciò rende più efficienti le query in cui viene richiesta la join, in

quanto non serve ricalcolarla ogni volta. 21

8.4 Buffer Manager

Il buffer manager si occupa di ottimizzare l’utilizzo dei buffer usati per trasferire pagine da e verso la memoria

secondaria. In generale i suoi compiti sono di caricare le pagine nel buffer finché questo non sarà pieno, quindi

applicare una serie di politiche di gestione per il rimpiazzo che possono essere FIFO oppure LRU.

8.4.1 Funzionamento del buffer manager

Il buffer manager fa uso di variabili di stato, ovvero dei valori associati ad ogni pagina che danno informazioni

in più sul loro stato, ovvero:

1. dirty bit, che è attivo se la pagina ha subito una modifica ed ha quindi bisogno di essere salvata.

2. count, che viene incrementata (o decrementata) quando una transazione fa uso (o rilascia) quella pagina.

In altre parole, se count è 0 allora la pagina non è usata da nessuno e quindi può essere scelta come vittima,

altrimenti qualche transazione che sta usando quella pagina non avrà ancora fatto commit (o abort).

8.4.2 Steal e force

Quando nel buffer sono presenti pagine con count = 0, allora non ci soni problemi nel scegliere una di esse

come vittima. Quando ciò non si verifica, e quindi tutte le pagine nel buffer sono utilizzate, si possono adottare

diverse politiche per scegliere la vittima.

• steal, che permette di sostituire una pagina anche prima che il commit sia avvenuto.

• no steal, che non permettetale operazione e quindi la nuova pagina viene messa in attesa.

Un altro set di politiche per la gestione delle pagine riguarda invece la memorizzazione in seguito al commit,

che può avvenire in due modi:

• force, che obbliga a scrivere su memoria secondaria le modifiche effettuate sulla pagina subito dopo il

commit.

• no force, altrimenti.

8.5 Query Processor

Il gestore delle query ha il compito di ottimizzare le query, ovvero di scegliere la strategia esecutiva migliore per

ottimizzare i tempi di risposta. L’ottimizzazione delle query si svolge in tre fasi.

8.5.1 Analisi lessicale, sintattica e semantica

Viene verificata la correttezza della query