O grafach w Oracle Spatial słów kilka

Zazwyczaj grafy i związane z nimi implementacja struktur danych i algorytmów kojarzy się nam zazwyczaj z warstwą aplikacyjną systemu. Systemowy bazodanowe obecnie umożliwiają przechowywanie tych struktur w postaci relacyjnej. Związane jest z rozwojem systemów GIS ( Geography Information Systems ) , czyli polskie SIP. Chciałbym omówić jak jest to robione w Oracle 10g database.

Obiekty do analizy (Java)

NODES

LINKS

PATHS

PLINKS

SDO_NET




Cała architektura może być podzielona na dwa zasadnicze segmenty. Pierwszy segment to część bazodanowa. Cała informacja przechowywana jest w tabelach. Na rysunku przedstawiono cztery tabele opisujące sieć. Zasadniczo wymagane są dwie : Nodes oraz Links. Pozostałe tabele umożliwiają przechowywanie analiz przeprowadzanych na sieci – w najprostszym przypadku wyliczone ścieżki.

Drugi segment to część analityczna. Sieć zostaje załadowana do aplikacji -> obszar Network. Jeżeli chcemy przeprowadzić jakieś operacje na sieci dotyczące , np. wyszukiwania najbliższych sąsiadów danego wierzchołka musimy wywołać statyczne funkcje klasy NetworkManager. W przypadku modyfikowania struktury sieci (dodawanie, usuwanie i modyfikacja jej elementów) posługujemy się funkcjami klasy NetworkFactory.



Do przeprowadzania analiz w sieci można użyć dwóch interfejsów programistycznych: Javy lub PL/SLQ’a. Z racji tego, że większość analiz jest przeprowadzanych w warstwie aplikacyjnej, właściwsze będzie omówienie możliwości interfejsu programistycznego z poziom Javy.

Interfejs programistyczny został podzielony ze względu na funkcjonalność na dwie części:

- obliczenia i analizy na istniejącej sieci -> klasa NetworkManager

Znajdowanie najkrótszej ścieżki między dwoma obiektami(wierzchołkami) w sieci ( wersje używają algorytmu Dijkstry lub algorytmu A* ).

Znajdowanie najbliższych sąsiadów dla danego wierzchołka. Działa podobnie jak operator przestrzenny SDO_NN, z tą różnicą że drogę możemy pokonywać tylko po krawędziach sieci. Znajdowanie wierzchołków znajdujących się w określonej odległości od wierzchołka startowego
Rozwiązanie problemu komiwojażera, czyli znalezienie optymalnej ścieżki przy zadanej liście wierzchołków, które należy odwiedzić Obliczanie Minimalnego Drzewa Rozpinającego ( ang. Minimum Cost Spaning Tree) dla sieci