Baze de Date Spatiale [PDF]

Zitiervorschau

Sisteme de baze de date evoluate Baze de date spatiale Pe langa datele clasice care domina bazele de date, managerii, analistii s-au lovit de asa numitele date speciale1 care nu puteau fi gestionate cu succes de sistemele clasice de gestiune a bazelor de date. Ca efect al acestei probleme au inceput sa apara tehnologii specializate pe una sau mai multe tipuri de date speciale. Una dintre aceste tehnologii a fost The Geografic Information System (GIS). GIS ofera un mecanism important de analiza si vizualizare a datelor geografice care îi permite utilizatorului sa combine cu usurinta datele pentru obtinerea rezultatelor dorite. Desi gis ofera un set bogat de operatiuni care pot fi executate asupra datelor, s-a constatat ca in cazul unor cantitati mai de informatii rezultatele nu sunt satisfacatoare. Astfel s-a ajuns la concluzia ca un sistem de gestiune al bazelor de date spatiale ar creste eficienta si productivitatea operatiunilor executate asupra datelor. Baza de date spatiala este o colectie de date spatiale si clasice. O astfel de baza de date este optimizată sa tina si sa interogheze date referitoare la obiecte incadrate în spa țiul geografic cum ar fi puncte, linii si poligoane.Altfel spus ea trebuie sa fie capabila sa recunoasca si date SQL cum ar fi int, varchar, dar si date spatiale: punct, linie, poligon. Un exemplu edificator al datelor spatiale sunt imaginile luate din satelit.

Tot mai multi utilizatori se indreapta catre utilizarea bazelor de date spatiale. Dintre acestia se evidentiaza trei clase mari: oameni de stiinta, administratorii si oamenii de afaceri. Pentru a putea prelucra cu succes aceste tipuri de date, bazele de date au fost upgradate cu noi functionlitati, sau au aparut optiuni avansate ca oracle spatial. Aceasta latura a Oracle fost dezvoltata pentru a facilita utilizatorilor gestiunea datelor geografice in forma in care sunt stocate in baza de date. Ea a devenit cu adevarat importanta odata cu Oracle 8i, dupa care a cunoscut o dezvolare continua. Avand in vedere ca datele spatiale sunt bidimensionale sau tridimensionale dezvoltatorii s-au indreptat asupra indecsilor spatiali. Dintre cei mai utilizati putem enumera : Grid index, Quadtree, Octree, UB-tree, R-tree, kd-tree, M-tree 1 In aceasta categorie intra datele spatiale si multimedia.

Importanta acestora este capitala pentru ca determina timpul de executie si uneori rezultatele interogarii. Datele spaţiale sunt stocate în structuri de date spaţiale. Dintre acestea, un loc important îl ocupă cele ierarhice care sunt bazate pe principiul descompunerii recursive. Avantajele acestor tipuri de structuri rezultă din faptul că sunt compacte, depind de natura datelor şi permit realizarea operaţiilor de interogare în mod eficient. O astfel de structură de date este quadtree şi are la bază principiul descompunerii recursive, similar metodei divide-and-conquer. Ea se poate utiliza la descrierea mai multor elemente aparţinînd clasei datelor spaţiale ca de exemplu: puncte, linii, poligoane et

Structura quadtree se bazează pe subdivizarea succesivă a unei imagini în patru cadrane de mărimi egale. Dacă un cadran nu conţine numai valoarea 1 sau numai valoarea 0, el va fi din nou subdivizat în patru cadrane şi aşa mai departe pînă sunt obţinute cadrane ce au fie valoarea 1 fie 0. Valorile 1 respectiv 0 semnifică faptul că zona aparţine sau nu regiunii respective. Cadranele obţinute în urma procesului de divizare a spaţiului se pot reprezenta prin intermediul unui arbore numit quadtree. Structura quadtree este în esenţă un arbore oarecare ce conţine noduri avînd semnificaţiile: - rădăcina corespunde imaginii în ansamblu; - nodurile frunză corespund acelor blocuri pentru care nu mai sunt necesare subdivizări; blocurile fie aparţin regiunii (1) fie sunt în afara ei (0); - celelalte noduri reprezintă cîte un cadran al regiunii care a necesitat o subdivizare. Pentru orice nod ce nu este frunză, fii lui corespund cadranelor în ordinea NE (I), SE (II), SV (III), NV (IV). Structura quadtree poate fi diferită în funcţie de: a) Tipul de dată pe care o reprezintă şi care poate fi: punctul, linia, curba, suprafaţa şi regiunea. b) Principiul care stă la baza procesului de descompunere care se poate face în părţi egale la fiecare nivel (descompunere regulată) sau în m părţi de mărimi diferite în funcţie de data iniţială; c) Rezoluţia descompunerii care poate fi variabilă Această structură poate fi de asemenea utilizată la reprezentarea imaginilor în trei sau mai multe dimensiuni. Varianta cu trei dimensiuni se numeşte octree. Modelul de construire a acestui arbore presupune ca imaginea să fie încadrată într-un cub care va fi recursiv subdivizat în 8 cuburi egale şi aşa mai departe pînă cînd sunt obţinute regiuni uniforme din punct de vedere a culorii ori se ajunge la un anumit nivel predefinit de descompuneri.

Dezvoltarea unei structuri ierarhice este avantajoasă deoarece se poate folosi la procesele de interogare a datelor spaţiale dar şi pentru că se economiseşte spaţiul de memorie necesar reprezentării unor astfel de date. Reprezentarea originală a structurii quadtree a fost aceea de arbore care utiliza pointeri. In acest fel, spaţiul de memorie consumat este destul de mare, de aceea s-au propus, pentru a îmbunătăţi acestă variantă, două modalităţi. Prima tratează imaginea ca pe o colecţie de noduri frunză, unde fiecare nod este reprezentat printr-o pereche de numere. Există un număr în baza 4, numit codul locaţiei, care corespunde secvenţei direcţionale ce localizează frunza şi stabileşte astfel calea de la rădăcină şi un număr ce indică adîncimea la care nodul frunză este regăsit. A doua modalitate reprezintă imaginea în forma unei traversări a structurii quadtree. Ea este foarte compactă dar nu este uşor de folosit cînd se doreşte accesul aleator la un anumit nod. Reprezentarea punctelor se face în funcţie de operaţiile care urmează să se execute cu aceste date. Dintre multiplele moduri de reprezentare a punctelor, adecvată este structura de date PR quadtree (P pentru puncte şi R pentru regiuni), deci o adaptare a structurii quadtree la tipuri bine precizate de date spaţiale. Această structură se bazează pe o descompunere regulată care urmăreşte asocierea unui punct cu un cadran. Procesul de construire este similar cu cel al structurii quadtree, diferenţa este că nodurile frunză fie nu conţin nimic, fie conţin puncte prin valorile coordonatelor lor. In figura 3 se poate observa corespondenţa dintre puncte şi cadrane care stă la baza construirii arborescenţei. Dezavantajul metodei constă în faptul că, dacă punctele sunt foarte apropiate, atunci nivelul maxim de descompunere poate fi foarte mare. Avantajul este că structura devine atractivă în cazul în care prelucrarea datelor spaţiale implică operaţii de căutare. Un exemplu tipic de folosire a arborelui îl constituie determinarea oraşelor din nord-estul ţării. Oraşele vor fi căutate în regiunile care compun cadranul NE al imaginii (Suceava şi Iaşi), lucru uşor de realizat avînd în vedere modul de construire a structurii quadtree.

Pentru manipularea datelor spaţiale este nevoie ca acestea să fie reprezentate în diferite forme. O modalitate constă în a utiliza structuri de date bazate pe ocuparea spaţială a datelor. Acestă metodă presupune descompunerea spaţiului în regiuni numite partiţii. De aceea, metoda este cunoscută sub numele de metoda partiţionării. Partiţionarea datelor spaţiale se bazează pe conceptul minimizării ariei ocupate de partiţie. In acest caz, obiectele spaţiale sunt grupate în ierarhii şi apoi ele sunt stocate în alte structuri de date. Structurile de indexare a datelor spaţiale multidimensionale au la bază două abordări: - prima se bazează pe observaţia că data spaţială ocupă un subspaţiu a spaţiului multidimensional; - cea de-a doua se bazează pe faptul că data fiind multidimensională, un număr mic de dimensiuni stochează majoritatea informaţiei.

Structura arborescentă R (Rectangle tree), face parte din prima categorie şi este similară ca reprezentare şi mod de exploatare cu arborele B. Ea are mai multe variante proiectate în scopul organizării unei colecţii de date spaţiale prin reprezentarea lor în dreptunghiuri n dimensionale Fiecare nod în arbore corespunde celui mai mic dreptunghi n dimensional care include fii lui. Nodurile frunză conţin pointeri ce referă datele spaţiale din baza de date. Obiectele sunt reprezentate prin cele mai mici dreptunghiuri care le conţin. Partiţionarea spaţiului în partiţii disjuncte a dus la crearea unei structuri derivate din arborele R şi anume R+ . Deoarece regiunile sunt disjuncte, înseamnă că pot fi obiecte care nu se încadrează doar într-o singură partiţie. De aceea, ele se vor descompune în subobiecte, fiecare aparţinînd unor regiuni diferite. Devine, astfel, important să se determine partiţiile care conţin o anumită dată spaţială. In literatura de specialitate s-a demonstrat că structurile de indexare bazate pe arbori R nu sunt adecvate pentru date spaţiale reprezentate într-un spaţiu multidimensional. O structură performantă de indexare a datelor spaţiale multidimensionale cu număr mare de dimensiuni este arborele X (eXtended node tree). Structura arborelui X este prezentată în figura 8. Se observă că el conţine trei tipuri de noduri: - noduri de date care sunt la nivelul frunzelor şi fac legăura cu datele spaţiale care se indexează; - noduri directoare normale ce au rol în a dirija căutarea prin arbore şi sunt similare nodurilor interne dintr-un arbore R; şi - supernoduri care sunt în fapt noduri directoare de mărime variabilă. Scopul principal al acestor supernoduri este să evite divizarea nodurilor directoare, care ar avea ca rezultat construirea unei structuri ierarhice ineficiente. Arborele X este diferit de arborele R cu noduri de dimensiuni mari prin faptul că el conţine noduri de dimensiuni mai mari doar dacă este necesar. Supernodurile sunt create în timpul inserării cînd capacitatea unui nod trebuie depăşită şi nu se poate evita acest lucru prin alte procedee. Pentru un arbore X sunt două cazuri extreme: 1. nici un nod director nu este supernod; 2. există doar un singur supernod ce formează rădăcina arborelui, în rest sunt doar noduri de date.

.