proiezione

L’operatore di proiezione consente di eliminare attributi dal risultato di una query, data una query del tipo:

SELECT DISTINCT R.sid, R.vid
FROM Recensioni R

E necessario eliminare gli attributi non richiesti e eliminare i record duplicati, ci sono 3 approcci principali

Proiettare ordinando

Una possibile soluzione e quella di sfruttare l’ordinamento, si procede come segue

• si legge il file rimuovendo gli attributi non richiesti
• si ordina per mezzo del merge sort
• si eliminano i duplicati

costo complessivo dato da $P(R)+P(T)+2P(T)\lceil {\log }_{Z}P(T)\rceil +P(T)$

si possono squashare la rimozione degli attributi con la fase di sorting e l'eliminazione dei duplicati nella fase di merging del merge sort

Proiettare usando hashing

Fattibile solo se si hanno un alto numero di pagine, il processo si divide in due fasi

Fase di partizionamento

• si leggono le pagine del buffer e si eliminano gli attributi
• si applica una funzione di hash (a $B-1$ valori) per suddividere le tuple in base agli attributi rimasti
• se una pagina e piena la si scrive nel disco

flowchart LR
A[(input file)]
subgraph central memory
B[pagina input]
C[1]
D[2]
E[...]
F[B-1]
end
G[(partizioni)]
A --> B --> C & D & E & F --> G

Fase di eliminazione dei duplicati

si leggono in sequenza i file generati e si applica una nuova funzione hash (diversa dalla prima ) e si redistribuiscono i record nelle pagine e si eliminano i duplicati

l'ipotesi è che nella seconda fase non si debbano salvare le pagine su disco, di conseguenza il numero di pagine del file di input deve essere minore di $(B-1{)}^2$

in caso sia necessario scrivere su disco si può ripetere il processo con una terza funzione di hash

Sorting vs hashing

La tecnica basata su sorting risulta migliore nel caso in cui i valori risultino sbilanciati o ci siano molte tuple da eliminare

con il sorting il risultato e anche ordinato :)

Proiettare con un indice

Questa modalità necessita che tutte le chiavi da restituire in output siano contenuti nell’indice, le tecniche sono le precedenti ma si attuano sull’indice e non sul file dati

in caso di indice b+tree se gli attributi sono un prefisso della chiave basta scandire le foglie eliminando i duplicati con costo $L$

PREVIOUS NEXT