DATABASE MULTIMEDIALI

DATABASE MULTIMEDIALI

SEMINARIO MAGGIO 2009DANIELA SCARCELLA E MATTEO BUFFA

1La rappresentazione dei dati nello spazio, ha diverse applicazioni. Questo trova riscontro nei seguenti applicativi: DBMS commerciali G.I.S. (sistemi informatici geografici) Gestione di progetti nel settore architettonico, industriale;Etc.

2STRUTTURE DATI MULTIDIMENSIONALILaumento del numero di dimensioni nello spazio porta ad una complessit maggiore, ed per questo che si cerca di ottimizzare la rappresentazione di informazioni multidimensionali studiando nuove strutture dati. La rappresentazione di oggetti n-dimensioni strettamente legata al concetto di indicizzazione di relazioni di database.

3Esistono molte strutture dati che rappresentano metodi di decomposizione dello spazio, tali per cui la rappresentazione dei punti comporta , un risparmio di spazio di memorizzazione, e tempo di esecuzione delle operazioni (aggiornamento, creazione, modifica, ecc).4STRUTTURE DATI MULTIDIMENSIONALIRappresentazioni di dati nello spazioK-d tree Quadtree PointQuadtree-MX R-tree5Sistemi Informatici geograficiConsideriamo un sistema di informazioni geografiche il quale immagazzina i dati di una determinata zona.

Prendiamo in esame una mappa come unimmagine Bi-dimensionale.

6

7K-d treeUn albero a due dimensioni (es. k=2) immagazzina informazioni bi-dimensionali,.Un albero a tre dimensioni (es.k=3) immagazzina informazioni tri-dimensionaliEtc.8Struttura di un albero 2-dIn un albero, il nodo ha una certa struttura di record.nodetype = recordINFO : infotypeXVAL : realYVAL : realLLINK : nodetypeRLINK : nodetype

9Condizioni da soddisfareSe N un nodo di livello pari:Nel ramo di sinistra i nodi M hanno la propriet M.XVAL < N.XVAL.Nel ramo di destra i nodi P hanno la propriet P.XVAL >= N.XVAL.Il nodo N divide la regione in due parti, disegnando una linea verticale.10Condizioni da soddisfareSe N un nodo di livello dispari:Nel ramo di sinistra i nodi M (figlio di N) ha la propriet M.YVAL =N.YVAL

Il nodo N divide la regione in due parti, disegnando una linea orizzontale.11 CITTAXYTORINO6683BIELLA74115ALESSANDRIA9865CUNEO4215

12Supponiamo di voler inserire questi elementi cos come messi nella tabella.Inserimento primo elemento: se la tabella vuota, questo record sar la radice dellalbero di dati.LIV 0INSERIMENTO ALBERO 2-D 13

INSERIMENTO ALBERO 2-DInserimento secondo elemento: siccome siamo in un livello pari dellalbero dobbiamo confrontare i campi XVAL; ovvero BIELLA.XVAL >= TORINO.XVAL; quindi collegheremo il figlio al campo Rlink(destro).14

LIV 0 LIV 115

INSERIMENTO ALBERO 2-DInserimento terzo elemento: inizio con il confrontare Torino.XVAL con Alessandria.XVAL, dal confronto mi accorgo che Alessandria.XVAL > TORINO.XVAL per il campo destro gi occupato, quindi confronto (mi trovo al LIV 1) Alessandria.YVAL con Biella.YVAL , e quindi Alessandria.YVAL < Biella.YVAL; allora collego questo nuovo elemento al campo sinistro.16

LIV 0LIV 1LIV 217

668374115

9865Inserimento quarto elemento: lultimo elemento da inserire la citt di Cuneo. CUNEO.XVAL con TORINO.XVAL confronto i campi XVAL perch ci troviamo al livello pari. Questo nuovo e ultimo elemento lo colleghiamo al figlio sinistro della radice, poich CUNEO.XVAL < TORINO.XVAL18Quindi il nostro schema finale sar:

LIV 0LIV 1LIV 219

6683741159865

CANCELLAZIONE ALBERI 2-DLa parte pi complessa nella gestione degli alberi K-D la cancellazione di un nodo.Il primo passo consiste nell individuare il nodo da cancellare. Supponiamo di voler cancellare un elemento nella posizione (x,y). Se il nodo da cancellare una foglia (questo il caso piu semplice) si elimina il nodo selezionato, ponendo a NULL il puntatore al nodo padre che ne memorizza il riferimento.20

NULL21CANCELLAZIONE ALBERI 2-DSe invece il nodo da cancellare interno, la cancellazione sar pi complessa.Supponiamo infatti di voler cancellare un nodo N, non vuoto cio che ha almeno un figlio. Il primo passo da fare trovare un candidato(nodo R) che pu sostituire il nodo che vogliamo cancellare (N).22CANCELLAZIONE ALBERI 2-DPassi da fare per cancellare un nodo internoPasso 1: trovare un sostituto R per rimpiazzare il nodo figlio di Ti(Tr o Tl). Passo 2: sostituire i campi Info, XVAL e YVAL di N con quelli di R (ovvero il sostituto).Passo 3: Cancellare ricorsivamente R da Ti.23Il nodo candidato deve soddisfare le seguenti propriet: 1: Ogni nodo M in Tl deve verificare M.XVAL < R.XVAL se il livello pari, mentre deve verificare che M.YVAL < R.YVAL se il livello dispari .2: Ogni nodo M in Tr deve verificare che M.XVAL >= R.XVAL se il livello pari, mentre deve verificare che M.YVAL >= R.YVAL se il livello dispari.

2425TrTlLIV 0LIV 1LIV 2LIV 3CONSIDERAZIONI (sotto-albero destro)In generale,se il livello di N pari, ogni nodo Tr che ha il campo XVAL pi piccolo possibile in Tr il nodo candidato per la sostituzione. In modo analogo se il livello di N dispari, ogni nodo in Tr che ha il campo YVAL pi piccolo possibile in Tr il nodo candidato per la sostituzione.Nel nostro caso, se volessi cancellare TORINO, il nodo che dovrebbe rimpiazzare associato ad ALESSANDRIA, poich questo nodo ha coordinata Y pi piccola di tutte le altre citt nel sottoalbero destro di TORINO.26ALESSANDRIA la citt con campo YVAL pi piccolaNodo NLIV 1 LIV 0LIV 227

R(candidato)M (di livello dispari)M verifica la condizione 2(ovvero M.YVAL >= R.YVAL)

ALESSANDRIA la citt con campo YVAL pi piccolaNodo NLIV 1 LIV 0LIV 228

ALESSANDRIA la citt con campo YVAL pi piccolaNodo NLIV 1 LIV 0LIV 229

CONSIDERAZIONI (sotto-albero sinistro)Se il livello N pari, un nodo di rimpiazzo in Tl sar il nodo in cui il campo XVAL ha valore pi grande. In modo analogo, se il livello N dispari, consideriamo il nodo di rimpiazzo Tl che ha campo YVAL maggiore.30RANGE QUERY IN ALBERI 2-DUna query su un intervallo in un albero a 2-d una ricerca che permette di recuperare tutti i punti situati allinterno di una circonferenza con centro nel punto (xc, yc) e raggio r.La risposta alla query recupera tutti i punti inseriti nellalbero che hanno una distanza dal centro minore del raggio. In altre parole si presuppone di trovare tutti quei punti dellalbero 2-d che stanno nellintorno.Nellelaborazione di una query su un intervallo necessario ricordare che ogni nodo N inserito allinterno dellalbero definisce una regione Rn.

31Se il cerchio in una query non ha intersezione Rn, allora non esistono punti da cercare nel sottoalbero con radice N.Se consideriamo la mappa precedente: 1) Il nodo con etichetta TORINO rappresenta tutti i punti del dominio applicato2) Il nodo etichettato BIELLArappresenta la regione di tutti i punti (x,y) tali che x>663)Il nodo etichettato ALESSANDRIA rappresenta tutti i punti(x,y) tali che x>=19 e yrnodetype;End

65R Tree (Struttura)G1 G2 G3 G4R4 R5 R6 R7R8 R9R1 R2 R3Ogni R-Tree ha associato un ordine che un intero k.Ogni nodo che non una foglia, contiene un insieme di k rettangoli (al massimo) o [k/2] rettangoli (almeno).Root lunica eccezione a queste regole.Ogni rettangolo sia un rettangolo reale che un gruppo di rettangoli.

66R Tree (Struttura)67R Tree (Inserimento)

R2R1R3R4R5R6R7R8R9Supponiamo di voler inserire il rettangolo R10 dentro la struttura ad albero vista in precedenza e rappresentata dalla mappa a destraR1068R Tree (Inserimento)

R2R1R3R4R5R6R7R8R9Il metodo migliore che ci viene suggerito anche dalla figura quello di inserire il rettangolo R 10 espandendo larea del gruppo 1 di rettangoli. Infatti, se si cercasse di inserire R 10 dentro il gruppo 3 si averebbe un incremento sostanziale dellarea coperta .R1069R Tree (Inserimento)

R2R1R3R4R5R6R7R8R9Ora vogliamo inserire il rettangolo R11Abbiamo 2 opzioni:Inserire il rettangolo nel gruppo che ha ancora spazio (in questo caso il gruppo 3).R10R11

70R Tree (Inserimento)R2R1R3R4R5R6R7R8R9Ora vogliamo inserire il rettangolo R11Abbiamo 2 opzioni:Inserire il rettangolo nel gruppo che ha ancora spazio (in questo caso il gruppo 3).Creare un sotto-gruppo con le regioni R4 ed R11R10R11

71R Tree (Cancellazione)R2R1R3R4R5R6R7R8R9La cancellazione negli R-Tree pu violare il vincolo i integrit (ovvero che ci siano sempre almeno [k/2] rettangoli (reali o gruppi).Quindi, quando si elimina un rettangolo dallalbero, bisogna assicurare il vincolo.R10R1172R Tree (Cancellazione)G1 G2 G3 G4R4 R5 R6 R7R8 R9R1 R2 R373R Tree (Cancellazione)G1 G2 G3 G4R4 R5 R6 R7R8R1 R2 R3Condizione di Underflow74R Tree (Cancellazione)G1 G2 G3 G4R4 R6 R7R8 R5R1 R2 R3Soluzione!!!75Per concluderePoint Quadtree:Pro: di facile implementazioneContro: un albero con k nodi pu avere laltezza = k e la complessit pu arrivare a O(k).Inoltre richiesta sempre la comparazione di due campi,non solo uno.La cancellazione spesso difficile.K-d tree: Pro: di facile implementazioneContro: un albero con k nodi pu avere laltezza = k e la complessit peggiore dei point-Quadtree.La complessit nel caso peggiore della ricerca arriva a

76Per concludereQuadtree-MX:Pro: garantiscono laltezza O(n). Inserimento, cancellazione e ricerca hanno un tempo proporzionale O(n). Il range di ricerca molto efficiente dove N = numero di punti in risposta alla ricerca e h laltezza dellalbero.R-tree: Pro: Ottimi per lottimizzazione degli accessi al disco, riducendo notevolmente laltezza dellalbero. Questo li rende molto popolari.Contro: I rettangoli si possono sovrapporre tra di loro, dando vita a percorsi differenti che portano allo stesso rettangolo. Questo pu provocareun accesso multiplo al disco, vanificando lottimizzazione.