DB Spaziali

Visite: 2119

Gradito:

[ Medio appunti ]

Leggi anche appunti: I Database Relazionali I Database Relazionali allora cosa sono questi famigerati Database relazionali? Documento delle Specifiche relativo alla progettazione di una base di dati per la gestione dei dipartimenti del Polo Didattico delle Scienze (v. 1.0) Documento delle Specifiche relativo alla progettazione di una base di dati per la I Semafori , ovvero la gestione della multiutenza I Semafori , ovvero la gestione della multiutenza Chiariamo subito una cosa: già

PostGIS non ha di per sé un visualizzatore grafico.

E' difficile però l'analisi senza visualizzare i dati. È possibile utilizzare il visualizzatore QGIS- Quantum GIS

Perché il funzionamento delle query spaziali sia veloce è fondamentale creare un indice sulla colonna "geometrica" (nell' esempio shape-forma).

Un indice su dati spaziali deve essere un ordinamento (indicizzazione) basato su una "vicinanza" spaziale.

L'indicizzazione permette l'utilizzo di un database spaziale di grandi dimensioni.

Il database organizza i dati in un albero di ricerca che può essere velocemente attraversato. Senza indicizzazione ogni ricerca richiederebbe una «scansione sequenziale» di ciascun record nel database.

Gli indici spaziali utilizzabili:

R-TREE suddivide i dati in rectangles, sub-rectangles, sub-sub-rectangles ecc.. è una struttura di indice dinamico per la ricerca spaziale;

GiST (Generalized Search Trees-Alberi di ricerca generalizzati): suddivide i dati in 'things to one side', 'things which overlap', 'things which are inside ('oggetti in una posizione', 'oggetti che si sovrappongono', ' oggetti che sono dentro'.).

Facciamo un esempio sull R-Tree:

Voglio trovare tutti gli edifici della tabella edificio che interseacano una certa area.

Se ho 1.000.000 di edifici voglio evitare di andare a controllarli tutti

La Soluzione sta nell'utilizzo dell'MBR (minimum bounding rectangles - minimo rettangoli di delimitazione ).

A ciascuna geometria è associato un MBR (ATTENZIONE! L'intersezione tra MBR non corrisponde all'intersezione tra le geometrie!)

-------- ----- ------ -------approfondimento da integrare----- ----- --------- ----- --------

Gli R-tree o R-alberi sono un tipo di albero (grafo) simile al B-Albero, ma sono usati per indicizzare spazi multidimensionali, ad esempio le coordinate spaziali (X, Y) per dati geografici. Una richiesta di esempio che usi un R-tree potrebbe essere 'Trova tutti i musei entro 2 km dalla mia posizione attuale'.

La struttura dati divide lo spazio in MBR (minimum bounding rectangles, infatti R-tree deriva proprio da Rectangle) innestati gerarchicamente e quando possibile sovrapposti.

Ogni nodo dell'R-tree ha un numero variabile di entry (fino ad un massimo predeterminato). Ogni entry che non sia un nodo foglia contiene due entità: una identifica il nodo figlio, l'altra l'MBR che contiene tutte le entry del nodo figlio.

L'algoritmo di inserimento e cancellazione di entry dagli MBR assicura che elementi 'vicini' siano posizionati nello stesso posto (nodo foglia): un nuovo elemento andrà nel nodo foglia che richiede il minor numero di estensioni delle dimensioni dell'MBR).

Gli algoritmi di ricerca usano gli MBR per decidere se cercare o meno nel nodo figlio del nodo corrente. In questo modo la maggior parte dei nodi non viene esplorata dagli algoritmi. Per questo motivo, come per i B-tree, ciò rende gli R-tree adatti ai database, dove i nodi possono essere copiati in memoria solo quando necessario.

Diversi algoritmi possono essere usati per dividere i nodi quando diventano troppo estesi, ovvero quando vengono aggiunti in un nodo un numero di elementi che supera il limite prestabiito.

Gli R-tree non garantiscono una performance ottima di caso peggiore, ma in generale si comportano molto bene con dati reali. Per questo nel 2004 è stato sviluppato un nuovo algoritmo (Priority R-tree), che cerca di essere efficiente ed allo stesso tempo ottimo rispetto al caso peggiore

Ricerca

L'input è un rettangolo MBR. La ricerca è simile a quella dei B-tree. Essa parte dal nodo radice e si estende ad ogni nodo figlio (contenente sia rettangoli MBR che puntatori ai nodi figli). Giunti al nodo foglia si hanno i veri e propri oggetti multidimensionali. Per ogni MBR incontrato si verifica se esso è sovrapposto con il rettangolo di ricerca (di input) o meno. Se esso è sovrapposto si cerca anche in quel nodo corrispondente, altrimenti no. La ricerca procede quindi in un modo ricorsivo, fermandosi quando tutti gli MBR sovrapposti sono stati esplorati. Un oggetto viene aggiunto all'insieme di ricerca (l'output dell'algoritmo) quando si trova in un MBR che si sovrappone all'MBR query.

Aggiunta di nodi [modifica]

Per inserire un oggetto l'albero è visitato ricorsivamente dal nodo radice. Un elemento è inserito in un MBR che necessita il minor numero di estensione delle dimensioni che l'aggiunta comporterebbe. A parità di numero di estensioni, viene scelto il nodo con MBR di area minima. Trovato il nodo foglia corretto, viene aggiunto l'oggetto vero e proprio. Se viene aggiunto un nodo ad un MBR che contiene già un numero-limite di elementi (di solito chiamato 'C', capacity), la regione (MBR) viene divisa in due regioni con un algoritmo di split. Tale algoritmo realizza le due nuove regioni tendendo a creare MBR con area minima (tra tutti quelli possibili).

Uso degli indici spaziali.

L' operatore "&&" calcola l'intersezione tra Bounding(limite) Boxes.

A ciascuna geometria è associato un MBR (ATTENZIONE! L'intersezione tra MBR non corrisponde all'intersezione tra le geometrie!)

Esempio SQL

Select id

from edificio

where ST_Intersect (shape, 'POLYGON((6 42, 8 42, 8 43, 6 43, 6 42))'::GEOMETRY)

AND id in (select id

from edicio

where shape && 'SRID=POLYGON((6 42, 8 42, 8 43, 6 43, 6 42))'::GEOMETRY

)

Seleziona l'id degli oggetti presenti in edificio che intersecano il poligono e che risultano avere id nella tabella costituita da tutti gli oggetti che intersecano (&&) il sistema di riferimento del poligono stesso (modificare)

Un esempio più complesso

Realizzazione di un Moving Object Database (MOD) per lo storing ed il retrieval (conservazione ed il recupero) delle informazioni collegate al movimento degli oggetti: le traiettorie.

Si ricorda che una traiettoria è un insieme di punti spaziotemporali:

< (x1; y1; t1); (x2; y2; t2); . ; (xN; yN; tN) >

Determina se un segmento, o parte di esso, si trova all'interno dell'area considerata.

Time interval queries

- Trovare le persone che hanno attraversato una certa area in un certo intervallo di tempo.

- Dobbiamo verificare l'intersezione tra un box 3D e tutti i segmenti di ciascuna traiettoria.

Gli indici non supportano il 3D

Se una traiettoria interseca il box, allora ciascuna proiezione della traiettoria intersecherà la corrispondente proiezione del box sui piani bidimensionali.

Questa è una condizione NECESSARIA ma NON SUFFICIENTE.

La proposta avanzata prevede

1) Proiezione della traiettoria e del box sui tre piani bidimensionali XY, XT, YT;

2) Ricerca delle traiettorie candidate al clipping grazie all'intersezione tra il Minimum Bounding Rectangle della traiettoria (MBR) e la corrispondente proiezione del box;

3) algoritmo di Clipping 3D Cohen-Sutherland tra le traiettorie rimanenti e il box.

-Proiezione

-intersezione

-clipping (gangio, taglio,fermaglio) 3d

-------- ----- ------ -----Altro gis-------- ----- ------ ----- ----- ---------------

Un GIS è invece un sistema informativo computerizzato che permette l'acquisizione, la registrazione, l'analisi, la visualizzazione e la restituzione di informazioniderivanti da dati geografici (geo-riferiti). Secondo la definizione di Burrough (1986) 'il GIS è composto da una serie di strumenti software per acquisire, memorizzare, estrarre, trasformare e visualizzare dati spaziali dal mondo reale'. Trattasi quindi di un sistema informatico in grado di produrre, gestire e analizzare dati spaziali associando a ciascun elemento geografico una o più descrizioni alfanumeriche.

Il GIS differisce dal DBMS (o Database Management System), in quanto si occupa essenzialmente dell'elaborazione e manipolazione dei dati georeferenziati, anche se questi possono essere memorizzati in un DBMS o in singoli file.

Per la rappresentazione dei dati in un sistema informatico occorre formalizzare un modello rappresentativo flessibile che si adatti ai fenomeni reali. Nel GIS abbiamo tre tipologie di informazioni:

Geometriche: relative alla rappresentazione cartografica degli oggetti rappresentati; quali la forma (punto, linea, poligono), la dimensione e la posizione geografica;

Topologiche: riferite alle relazioni reciproche tra gli oggetti (connessione, adiacenza, inclusione ecc.);

Informative: riguardanti i dati (numerici, testuali ecc.) associati ad ogni oggetto.

Il GIS prevede la gestione di queste informazioni in un database relazionale.

L'aspetto che caratterizza il GIS è quello geometrico: esso memorizza la posizione del dato impiegando un sistema di proiezione reale che definisce la posizione geografica dell'oggetto. Il GIS gestisce contemporaneamente i dati provenienti da diversi sistemi di proiezione e riferimento (es. UTM o Gauss Boaga)

A differenza della cartografia su carta, la scala in un GIS è un parametro di qualità del dato e non di visualizzazione. Il valore della scala esprime le cifre significative che devono essere considerate valide delle coordinate di georeferimento.

L'informazione territoriale può essere codificata in un sistema informativo geografico attraverso due tipologie principali di dato: il dato vettoriale e il dato raster.

I dati vettoriali sono costituiti da elementi semplici quali punti, linee e poligoni, codificati e memorizzati sulla base delle loro coordinate. Un punto viene individuato in un sistema informativo geografico attraverso le sue coordinate reali (x1, y1); una linea o un poligono attraverso la posizione dei suoi nodi (x1, y1; x2, y2; ). A ciascun elemento è associato un record del database informativo che contiene tutti gli attributi dell'oggetto rappresentato.

Il dato raster permette di rappresentare il mondo reale attraverso una matrice di celle, generalmente di forma quadrata o rettangolare, dette pixel. A ciascun pixel sono associate le informazione relative a ciò che esso rappresenta sul territorio. La dimensione del pixel (detta anche pixel size), generalmente espressa nell'unità di misura della carta (metri, chilometri etc.), è strettamente relazionata alla precisione del dato.

I dati vettoriali e i dati raster si adattano ad usi diversi. La cartografia vettoriale è particolarmente adatta alla rappresentazione di dati che variano in modo discreto (ad esempio l'ubicazione dei cassonetti dei rifiuti di una città o la rappresentazione delle strade o una carta dell'uso del suolo), la cartografia raster è più adatta alla rappresentazione di dati con variabilità continua (ad esempio un modello digitale di elevazione o una carta di acclività del versante).