Wstęp w „przestrzenne bazy danych”

Wiktor Miszuris

Wstęp

W dzisiejszych czasach do zadań baz danych należy nie tylko przechowywanie informacji czysto biznesowych, lecz także struktur i obiektów o znacznie bardziej skomplikowanej budowie. Bazy danych znajdują zastosowanie także w takich dziedzinach jak elektronika (przechowywanie planów układów scalonych o bardzo dużej skali złożoności), biologia (przechowywanie struktur białek i innych substancji), kartografii (przechowywanie informacji kartograficznych). Oczywiście funkcje baz danych pozostają niezmienne: bezpieczne i dokładne przechowywanie danych oraz efektywne wyszukiwanie interesujących informacji. Wymaga to jednak, ze względu na bardziej skomplikowane zastosowania inne podejścia do przechowywania i wykonywanie zapytań.

Nas interesować będą bazy danych przechowujące różnego rodzaju obiekty w przestrzeni (spatial databases). Tego typu bazy danych znajdują zastosowania w elektronice, budownictwie, CAD, robotyce oraz systemy informacji geograficznej (Geographic Information Systems – GISs). W dość szybkim tempie bazy danych przestrzennych przeistoczyły się z projektów teoretycznych i doświadczalnych w realnie działające produkty (komercyjne i darmowe), bez których ciężko byłoby się już obejść.

GIS

Skupimy się tu głównie na systemach typu GIS, każdy inny system przestrzennych baz danych jest w pewnym sensie pochodną GIS’u.

Zbieranie informacji do przestrzennej bazy danych jest zadaniem mało trywialnym, najlepiej do tego nadaje się system GPS (Global Positioning System). Możliwe jest również zbieranie informacji na podstawie zdjęć satelitarnych bądź istniejących map – to niestety jest związane zazwyczaj z błędami.
System GIS powinien zapewniać wykonywać czynności:

• Wprowadzanie i weryfikacja danych
• Przechowywanie i zarządzanie danymi
• Wyświetlanie i prezentacja danych
• Transformacje na danych
• Interakcję z użytkownikiem

Jądrem systemu GIS jest baza danych (DBMS), która zajmuje się przechowywaniem i zarządzaniem danymi.

System może być zastosowany po uprzednim uproszczeniu świata rzeczywistego, który chcemy reprezentować w bazie danych przestrzennej, proces ten prowadzi do utworzenia modelu świata. Następnym krokiem jest znalezienie odpowiednich struktur danych dla tego modelu.

Słowniczek pojęć geo-przestrzennych aplikacji bazodanowych

Theme (nie wiem, jak po Polsku)

W systemach GIS informacja związana z jakiś konkretnym tematem jest nazywana „theme”, theme jest do relacji w relacyjnym modelu bazodanowym. Theme ma schemat i instancje. Rzeki, Miasta, Państwa – to są przykłady theme’ów.

Obiekt geograficzny

Jest to podajże najważniejszy element całego systemu. Theme, to kolekcja obiektów geograficznych. Obiekt geograficzny odpowiada bytowi ze świata rzeczywistego ma dwie składowe:

1. Opis – dowolny opis, który uznamy, że będzie nam potrzebny
2. Komponent przestrzenny, który może przechowywać zarówno kształt, położenie geograficzne a także topologię (zależności przestrzenne w stosunku do innych obiektów, np. przystawanie)

Zważając na dość skomplikowaną budowę większości obiektów, które występują w świecie rzeczywistym, trzeba wprowadzić pojęcie atomowego obiektu geograficznego i złożonego obiektu geograficznego. Złożony obiekt geograficzny składa się z innych obiektów geograficznych, które mogą być złożone bądź atomowe.

Theme, jest to zbiór jednorodnych obiektów geograficznych (obiektów mających tę samą strukturę/typ). Rozważmy przykład theme „miasto”. Każde miasto opisywane jest poprzez ten sam zbiór atrybutów, które tworzą schemat: nazwa, populacja oraz geometria. Sposób reprezentacji geometrii jest zależny geograficznego modelu konkretnego systemu GIS. Atrybut przestrzenny nie odnosi się w żaden sposób do już istniejących typów w relacyjnych bazach danych. Wymaga to użycia owego modelu danych: przestrzennego modelu danych. Zazwyczaj, następujące podstawowe typy danych są używane w przestrzennym modelu: punkt, linia/odcinek, rejon.

Operacje na theme’atach

Rozważmy następujące dwa theme:

Państwa (nazwa, stolica, zaludnienie, geo:region)

Języki (język, geo:region)

Projekcja (Theme projection)

Polega na uzyskaniu nowego theme poprzez obcięcie innego do pewnego podzbioru atrybutów.

Np., gdy nie interesuje nas informacja o stolicach i zaludnieniu możemy dokonać projekcji:

Państwa x [nazwa, geo:region]

Selekcja (Theme selection)

Polega na wybraniu z tematu encji, które odpowiadają podanemu predykatowi na atrybutach. Jest to odpowiednik selekcji z relacyjnego modelu.

Unia (Theme union)

Polega na unii dwóch theme’ów o tym samym schemacie. Jest to odpowiednik unii z relacyjnego modelu.

Nałożenie (Theme overlay)

Nowy theme jest tworzony z nałożenia jednego theme na drugi. W wynikowym theme tworzone są nowe obiekty geograficzne poprzez zastosowanie przecięcia obiektów z theme przykrywanego i nałożonego, ich opis jest kombinacją pozostałych atrybutów z dwóch theme’ów.

Jest to tzw. spatial join – obiekt z jednego theme jest łączony z drugim, jeśli ich kształty się przecinają, wynikowy obiekt dostaje atrybuty z obydwu theme’ów.

Selekcja geometryczna

Okienkowanie/zapytanie okienkowe (Windowing/Window query)

Poprzez okienkowanie otrzymujemy theme zawierający obiekty, które przecinają się z obszarem okienkowania, (który jest zazwyczaj prostokątny).

Zapytanie punktowe (Point query)

Zwracany jest theme, zawierający obiekty, który kształty zawierają podany punkt.

Zapytanie obcinające (Clipping)

Podobne do okienkowania, tyle, że kształty zwracanych obiektów są dodatkowo obcinane do kształtu okienka.

Merger

Operacja, która złącza obiekty na podstawie podanego warunku (np. złącza wszystkie stany, województwa i inne działy administracyjne otrzymując w wyniku tylko państwa).

Dalsze operacje

Operacje metryczne

Typu, jaka odległość jest między obiektem A i B.

Operacje topologiczne

Typu, zwróć wszystkie obiekty przyległe do obiektu A.

Rozwiązania do przechowywania danych przestrzennych

Użycie baz relacyjnych

Główne cechy tego podejścia:

• Obiekty geometryczne są reprezentowane poprzez kilka rekordów z kilku relacji
• Składnia zapytań – czysty SQL

Tego typu podejście nadaje się do prostszych rozwiązań, niestety jest trudny do utrzymania w stanie kompletnego porządku, jest wyjątkowo nieprzystosowany do bardziej skomplikowanych zapytań. Zapytania, nawet najprostsze wymagają wpisania kilku linijek kodu SQL złączającego kilka tabel w logiczną całość.

Przykład:

Państwa (nazwa, stolica, zaludnienie, id-granicy)

Granice (id-granicy, id-kształt)

Kształt (id-kształt, point-num, id-point)

Point (id-point, x, y)

Luźno związane podejście

Bazuje na użyciu silnika zwykłej bazy relacyjnej oraz odrębnego silnika bazy przestrzennej.

Jednakże powstają problemy w powiązaniu struktur oraz efektywnym zapytaniach.

Zintegrowane podejście (dwa w jednym)

Bazuje na wprowadzeniu nowego typu danych – geometria oraz operatorów i funkcji na tych typach, które można używać w zwykłych zapytaniach SQL. Tego typu baza danych powinna starać się zoptymalizować przechowywane struktury danych ze względu na możliwe do wykonania przez użytkownika zapytania.

Modelowanie światów

Sposoby traktowania i reprezentacji obiektów świata rzeczywistego.

Model encyjny

W tym modelu obiekty są zawieszone w przestrzeni.

Ten model wprowadza następujące typy:

Punkt, linia, odcinek, łamana (zbiór powiązanych odcinków), wielokąt (zamknięta łamana), wielokąt wypukły, wielokąt prosty.

Field-based model

W tym modelu dla każdego punktu przestrzeni określone są jeden lub więcej atrybutów/charakterystyk. Np. Mapa temperatur.

Reprezentacja światów

Podział (Tesselation)

Dyskretny podział przestrzeni na przylegające komórki.

Podziały dzielą się na:

Regularne (podział na identyczne części)

Nieregularny

è rysunki, przykład reprezentacji figury

Wektorowa reprezentacja

Zostają wprowadzone następujące prymitywy:

• punkt [x, y]
• łamana <punkt>
• wielokąt <punkt>
• obszar {wielokąt}

gdzie [] – krotki, <> – listy, {} – zbiory.

Uwagi:

Wielokąt n-kątny ma 2n reprezentacji, co może utrudniać proces zapytań.

Do zadań programu należy rozróżniać logicznie różnicę pomiędzy łamaną a wielokątem.

Do zadań użytkownika należy także zapewnienie, aby wielokąt był prosty – struktura nie jest wystarczająco mocna, aby nam to zagwarantować.

Field-based model in Vector Mode

Mamy zbiór punktów na płaszczyźnie, w których znamy wartość funkcji (wysokość/temperatura), dokonujemy triangulacji i dla każdego trójkąta możemy dokonać interpolacji – a więc otrzymać przybliżoną wartość funkcji dla każdego punktu wewnątrz trójkąta.

Pół-przestrzenna reprezentacja (Half-plane Representation)

Musimy zdefiniować d-wymiarową pół-przestrzeń jako nierówność:

Wypukły d-wymiarowy wielokąt (Polytope) jest definiowany jako przecięcie pewnej skończonej liczby półprzestrzeni.

Unia skończonej liczby Polytope tworzy Polyhedron. Polytope niekoniecznie muszą przystawać, mogą na siebie nachodzić albo być w ogóle niepowiązane.

Dla każdego Polyhedrone’a rozróżniamy wnętrze, granicę oraz obszar nienależący do polyhedrone’a.

è pokazać, jak się robi trójkąt, czworokąt i wielokąt

Reprezentacja zbioru obiektów

Rozpatrzyliśmy wektorowe reprezentacje obiektów geometrycznych. Teraz zajmiemy się możliwymi reprezentacjami kolekcji obiektów. Różnią się one między sobą ilością szczegółów topologicznych.

Spaghetti

W tym podejściu każdy obiekt geometryczny jest reprezentowany niezależnie od innych już istniejących w bazie. Żadne zależności topologiczne nie są dodatkowo trzymane w bazie.

Plusy:

Prostota wprowadzania danych oraz ich utrzymanie.

Minusy:

Brak topologii

Brak zdefiniowanej możliwości ustalenia punktów wspólnych dla dwóch wielokątów (możliwe pojawienia się „niczyjej” przestrzeni pomiędzy wielokątami, które logicznie powinny być przystające.

Model sieciowy

Początkowo zaprojektowany do reprezentacji sieci i grafów (połączenia transportowe, telefoniczne etc.). W tym modelu topologiczne relacje pomiędzy punktami oraz łamanymi są trzymane dodatkowo w bazie danych.

Zbiór typów geometrycznych jest rozszerzony o następujące koncepcje:

Nodes, arc. Node – jest to punkt, który łączy listę łuków. Łuk, to łamana, która zaczyna się w Node i kończy się w Node.

è z książki

Mamy więc dwa typu punktów – zwykłe punkty i Node.

Obiekty w tym modelu są definiowane więc jako:

• Punkt: [x, y]
• Node: [point, <arc>]
• Arc: [node-start, node-end, <point>]
• Polygon: <point>
• Region: {polygon}

Mamy tu dużą zaletę – operację związane z nawigacją po reprezentacji sieci są szybsze.

Model topologiczny

Model topologiczny jest podobny do sieciowego, z tym wyjątkiem, że narzucony zostaje warunek planarności na powstającą sieć. Definicja wielokątu zostaje zmieniona – może on zostać utworzony tylko z łuków. Łuk dodatkowo trzyma informację o przystających do niego wielokątów, (które mogą nie mieć rzeczywistych odpowiedników w realnym świecie).

Obiekty w tym modelu są definiowane więc jako:

• Punkt: [x, y]
• Node: [point, <arc>]
• Arc: [node-start, node-end, left-poly, right-poly, <point>]
• Polygon: <arc>
• Region: {polygon}

Została całkowicie wyeliminowana redundancja danych – wielokąty przystające nie będą już miały duplikowanych punktów w bazie danych, bo są one utworzone z tego samego łuku.

è przykład

Dodatkową zaletą w stosunku do modelu sieciowego jest jeszcze większe wzbogacenie informacji topologicznej przechowywanej w bazie. Pewne zapytania będą wykonywane natychmiast. Brak redundancji. Łatwość zmiany granicy między wielokątami vs. Spaghetti.

Niestety są też minusy tego rozwiązania:

Niektóre obiekty trzymane w bazie nie mają żadnego fizycznego uzasadnienia w świecie rzeczywistym. Złożoność powstających struktur jednak może zwalniać niektóre operacje bazodanowe. Przy dodawaniu nowego obiektu niezbędne jest przeliczenie części grafu, aby był nadal poprawny z naszego punktu widzenia.

Wyciąg z dokumentacji Postgres’a:

Geometric Functions and Operators

The geometric types point, box, lseg, line, path, polygon, and circle have a large set of native support functions and operators.

Table 6-19. Geometric Operators

Operator	Description	Usage
+	Translation	box '((0,0),(1,1))' + point '(2.0,0)'
-	Translation	box '((0,0),(1,1))' - point '(2.0,0)'
*	Scaling/rotation	box '((0,0),(1,1))' * point '(2.0,0)'
/	Scaling/rotation	box '((0,0),(2,2))' / point '(2.0,0)'
#	Intersection	'((1,-1),(-1,1))' # '((1,1),(-1,-1))'
#	Number of points in path or polygon	# '((1,0),(0,1),(-1,0))'
##	Point of closest proximity	point '(0,0)' ## lseg '((2,0),(0,2))'
&&	Overlaps?	box '((0,0),(1,1))' && box '((0,0),(2,2))'
&<	Overlaps to left?	box '((0,0),(1,1))' &< box '((0,0),(2,2))'
&>	Overlaps to right?	box '((0,0),(3,3))' &> box '((0,0),(2,2))'
<->	Distance between	circle '((0,0),1)' <-> circle '((5,0),1)'
<<	Left of?	circle '((0,0),1)' << circle '((5,0),1)'
<^	Is below?	circle '((0,0),1)' <^ circle '((0,5),1)'
>>	Is right of?	circle '((5,0),1)' >> circle '((0,0),1)'
>^	Is above?	circle '((0,5),1)' >^ circle '((0,0),1)'
?#	Intersects or overlaps	lseg '((-1,0),(1,0))' ?# box '((-2,-2),(2,2))'
?-	Is horizontal?	point '(1,0)' ?- point '(0,0)'
?-|	Is perpendicular?	lseg '((0,0),(0,1))' ?-| lseg '((0,0),(1,0))'
@-@	Length or circumference	@-@ path '((0,0),(1,0))'
?|	Is vertical?	point '(0,1)' ?| point '(0,0)'
?||	Is parallel?	lseg '((-1,0),(1,0))' ?|| lseg '((-1,2),(1,2))'
@	Contained or on	point '(1,1)' @ circle '((0,0),2)'
@@	Center of	@@ circle '((0,0),10)'
~=	Same as	polygon '((0,0),(1,1))' ~= polygon '((1,1),(0,0))'

Table 6-20. Geometric Functions

Function	Returns	Description	Example
area(object)	double precision	area of item	area(box '((0,0),(1,1))')
box(box, box)	box	intersection box	box(box '((0,0),(1,1))',box '((0.5,0.5),(2,2))')
center(object)	point	center of item	center(box '((0,0),(1,2))')
diameter(circle)	double precision	diameter of circle	diameter(circle '((0,0),2.0)')
height(box)	double precision	vertical size of box	height(box '((0,0),(1,1))')
isclosed(path)	boolean	a closed path?	isclosed(path '((0,0),(1,1),(2,0))')
isopen(path)	boolean	an open path?	isopen(path '[(0,0),(1,1),(2,0)]')
length(object)	double precision	length of item	length(path '((-1,0),(1,0))')
npoints(path)	integer	number of points	npoints(path '[(0,0),(1,1),(2,0)]')
npoints(polygon)	integer	number of points	npoints(polygon '((1,1),(0,0))')
pclose(path)	path	convert path to closed	popen(path '[(0,0),(1,1),(2,0)]')
popen(path)	path	convert path to open path	popen(path '((0,0),(1,1),(2,0))')
radius(circle)	double precision	radius of circle	radius(circle '((0,0),2.0)')
width(box)	double precision	horizontal size	width(box '((0,0),(1,1))')

Table 6-21. Geometric Type Conversion Functions

Function	Returns	Description	Example
box(circle)	box	circle to box	box(circle '((0,0),2.0)')
box(point, point)	box	points to box	box(point '(0,0)', point '(1,1)')
box(polygon)	box	polygon to box	box(polygon '((0,0),(1,1),(2,0))')
circle(box)	circle	to circle	circle(box '((0,0),(1,1))')
circle(point, double precision)	circle	point to circle	circle(point '(0,0)', 2.0)
lseg(box)	lseg	box diagonal to lseg	lseg(box '((-1,0),(1,0))')
lseg(point, point)	lseg	points to lseg	lseg(point '(-1,0)', point '(1,0)')
path(polygon)	point	polygon to path	path(polygon '((0,0),(1,1),(2,0))')
point(circle)	point	center	point(circle '((0,0),2.0)')
point(lseg, lseg)	point	intersection	point(lseg '((-1,0),(1,0))', lseg '((-2,-2),(2,2))')
point(polygon)	point	center	point(polygon '((0,0),(1,1),(2,0))')
polygon(box)	polygon	4-point polygon	polygon(box '((0,0),(1,1))')
polygon(circle)	polygon	12-point polygon	polygon(circle '((0,0),2.0)')
polygon(npts, circle)	polygon	npts polygon	polygon(12, circle '((0,0),2.0)')
polygon(path)	polygon	path to polygon	polygon(path '((0,0),(1,1),(2,0))')