Basi di dati, Page 2 Categoria

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

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 →

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 →

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 T₁...T_n sono tipi primitivi e A₁...A_n sono etichette distinte, dette attributi, allora (A₁:T₁...A_nT_n) è 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 →