Organizzazione fisica dei database

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*log2(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(n2). è 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, {A1, A2, ... Ai}): scansione e ordinamento per attributo/i

Proiezione

  • Project(R, {A1, A2, ... Ai}): proiezione senza eliminazione dei duplicati
  • Distinct(R, {A1, A2, ... Ai}): proiezione con eliminazione dei duplicati

Restrizione

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

Ordinamento

  • Sort(R, {A1, A2, ... Ai})

Raggruppamento

  • GroupBy(O, {A1, A2, ... Ai}, {f1, f2, ... fi}): f indica una funzione di aggregazione contenuta in SELECT e HAVING. L'operatore GroupBy è sempre preceduto da un Sort

Giunzione

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

 

Equivalenze e coperture

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-{Ai})→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

Normalizzazione

Rispetto alla teoria, spesso negli ambienti di lavoro si approccia l'analisi iniziando dalla progettazione relazionale, ma questo introduce delle anomalie, che dovranno essere corrette successivamente. Keep reading →

Algebra relazionale

Operatori primitivi

Gli operatori primitivi sono sei:

  1. Ridenominazione (AS)
  2. Unione (UNION)
  3. Differenza
  4. Proiezione (SELECT)
  5. Restrizione (WHERE)
  6. Prodotto (JOIN)

Ridenominazione

Nell'algebra relazionale il nome di un attributo è molto importante, perché permette di fare NATURAL JOIN e, come nel linguaggio SQL, permette di risolvere ambiguità sulla relazione a cui un nome di attributo si riferisce.
La notazione ρA←B(R) indica che nella relazione R l'attributo B è il nuovo alias con cui si identifica A
(A = vecchio nome, B = nuovo nome) Keep reading →

Modello relazionale

Alcune definizioni

Schema di relazione

Coppia formata da un nome di relazione R e da un tipo relazione definito come segue:

  • int, real, boolean, string... sono tipi primitivi
  • se T1...Tn sono tipi primitivi e A1...An sono etichette distinte, dette attributi, allora (A1:T1...AnTn) è un tipo ennupla di grado n. Due tipi ennupla sono uguali se hanno uguale il grado, gli attributi e il tipo degli attributi con lo stesso nome. (l'ordine non è significativo)
  • se T è un tipo ennupla, allora {T} è un tipo insieme di ennuple o tipo relazione. Due tipi relazione sono uguali se hanno lo stesso tipo ennupla.

Schema relazionale

Uno schema relazionale è costituito da un insieme di schemi di relazione e da un insieme di vincoli di integrità relativi a tali schemi. Keep reading →