COMPUTERWORLD
pod kapotou
Databáze prostorových objektů

Klasická data organizovaná pomocí záznamů přestavují hlavní zdroj pro databázové zpracování. V 90. letech se začínají realizovat požadavky na údržbu dat odpovídajících objektům v nějakém prostoru. V 2D může jít o geografické aplikace typu GIS, plánování zástavby aglomerací, VLSI design apod., ve 3D o objekty používané v CAD, CIM, CASE, či v astronomických aplikacích. Zájem vzniká i v tzv. biocomputing, tj. zpracování dat biologických struktur.

Uvedené příklady se obecně zahrnují pod netradiční aplikace. Jejich společnou charakteristikou je nutnost podpory velkého množství relativně jednoduchých geometrických objektů. Zmíněné objekty mají své umístění v prostory, tvar a identitu, na rozdíl od rastrovaných obrázků umístěných v prostoru. Je proto vhodné rozlišovat databáze prostorových objektů a databáze obrázků.

Systém řízení databází prostorových objektů (SŘDBPO) je softwarový systém

  • zajišťující funkce SŘBD,
  • poskytující možnosti definovat prostorové datové typy a formulovat prostorové dotazy, jako je nalezení průniku dvou objektů, nalezení objektů v dané vzdálenosti od daného objektu apod.
  • umožňující indexaci prostorových objektů a efektivní algoritmy zpracování prostorových operací, jako např. prostorové spojení množin objektů.

O jaké objekty jde? Všeobecně známým příkladem v 2D může být třeba mapa, na kterou se lze dívat jako na polygon. Jiným dobře studovaným typem objektu jsou polygony s dírami, kterými lze např. modelovat zemi s jezery. K objektům typu mapa mohou existovat indexové struktury umožňující nalézt k danému objektu např. sousední objekty, prostorovým spojením jezer a měst můžeme obdržet města na břehu jezera.

Tradiční databázové techniky nejsou pro reprezentaci takových objektů vhodné. Představme si např. těleso složené (nebo aproximované) z disjunktních čtyřstěnů. Čtyřstěny jsou dány pomocí rovin, hran a bodů. Využijeme-li relační databázi, lze odpovídající data uložit ve čtyřech relacích: ČTYŘSTĚNY, ROVINY, HRANY a BODY. Relace ČTYŘSTĚNY obsahuje dvojice (t,f), kde t je identifikátor čtyřstěnu, f je identifikátor jedné z jeho rovin. Relace ROVINY obsahuje dvojice (f,e), kde f je identifikátor roviny a e je jedna z hran v té rovině. Relace HRANY obsahuje trojice (e,p,q), kde e je identifikátor hrany, p a q jsou koncové body hrany. Relace BODY obsahuje čtveřice (p,x,y,z), kde p je identifikátor bodu a x, y, z jeho souřadnice. Je zřejmé, že tato reprezentace nepodporuje geometrii potřebnou pro prostorové dotazy. Nalézt např. odpověď na dotaz, zdali daná přímka protíná daný čtyřstěn vyžaduje více vstupů do více relací, které obecně mohou být uloženy na více místech na disku. Zacházíme zde s prostorovými daty jako s jinými daty, nevyužíváme geometrických vlastností prostoru.

Existují tři podstatné rysy prostorových objektů:

  • objekty jsou součástí Eukleidovského prostoru,
  • objekty mají složitější strukturu než běžný datový záznam,
  • dotazy na objekty souvisí s jejich umístěním v prostoru.

Důležité je, v čem se odlišují dotazy na prostorové objekty od databázových dotazů na data formátována v relační databázi nebo v textech. Zdál-li se výše uvedený dotaz někomu příliš “geometrický”, představme si, že prostorové objekty jsou řeky a města. Pak má smysl dotaz “Nalezni města, kterými protéká řeka nebo je od jejich katastru vzdálená 1 km”. Je patrné, že datová struktura pro efektivní řešení tohoto problému by měla podporovat “prostorovost” nebo lépe geometrické vlastnosti objektů.

Nalézt efektivní možnosti přístupu k prostorovým objektům v databázi uvedlo jejich tvůrce do řady problémů. Ani indexové struktury založené na klasických datových strukturách (např. B-stromech) se neukázaly pro vyhledávání prostorových objektů příliš vhodné. Jde o to, že je jednak požadováno intervalové vyhledávání a navíc je potřeba více dimenzí. Vhodnější vícerozměrné datové struktury, jako např. 4-stromy, jsou zase definovány ve vnitřní paměti a obtížně se implementují v diskovém prostředí.

Ve druhé polovině 80. let se objevila řada nových datových struktur pro organizaci dat prostorových objektů a technik, které byly vytvořeny přímo pro prostorové objekty. Patří sem nové typy stromů, aproximace a různé transformace objektů apod. V podstatě je nutné řešit tři problémy:

  • reprezentaci prostoru,
  • aproximaci objektů,
  • operace nad prostorovými objekty.

V dnešní databázové abecedě se budeme věnovat podrobněji prvnímu z nich. Druhý problém souvisí s tím, že práce s objekty definovanými pomocí složitých geometrických křivek je pro řešení prostorových dotazů v mnoha případech zbytečně komplikovaná. Vystačí se s jednoduchými aproximacemi objektů. Studium třetího problém vede k definici operací podobným např. relační algebře (či prostorovým variantám SQL).

Reprezentace prostorových objektů znamená řešit současně organizaci a reprezentaci prostoru. jako takového. Jednou z možností je rozdělit prostor do disjunktních oblastí, zvaných často buňky, a umístit objekty do těchto oblastí. Důležitá je korespondence mezi buňkami a objekty. Vyhledávací struktura může existovat nad buňkami a teprve v dalších fázích hledání se přistupuje k objektům.

Pravidelné rozdělování do hierarchické soustavy buněk se obvykle zadává pomocí radixových stromů zvaných též rd-stromy, kde d označuje dimenzi. 4-strom je radixový strom s d=2 a r=2. Na obrázku 1 je ukázka 4-stromu spolu s prostorovým objektem, který je pomocí 4-stromu přístupný. Základní ideou 4-stromů je dekomponovat datový prostor do nepřekrývajících se buněk, které se počítají rekurzivním dělením prostoru, zde do čtyř částí stejné velikosti. Pro úplnost poznamenejme, že 4-stromy byly uvedeny Finkelem a Bentleyem už v r. 1974, tj. jsou jen o něco mladší než B-stromy.

 

 

 

 

 

 

Obr.1 Objekt a jeho reprezentace 4-stromem

Buňky lze číslovat různým způsobem. Na obrázku 2 a) je ukázáno tzv. z-uspořádání, jak je uvádějí Orenstein a Merrett v r. 1984. V z-uspořádání jsou buňky identifikovány kódem umístění, tzv. z-hodnotou, a kódem velikosti buňky, tzv. úrovní. Buňky mohou být uloženy např. do relační databáze, do B-stromů apod. z-uspořádání vznikne ze souřadnic buněk proložením bitů jejich binárních reprezentací. Jsou-li souřadnice buňky (x1x0, y1y0), pak (lineární) adresa buňky je x1y1x0y0. Na obrázku 2 b) je ukázána křivka, která odpovídá z-uspořádání. Nazývá se Peanova křivka. Křivek, které umožňují vhodně vyplnit prostor je více typů. Peanova je však nejznámější.

 

11 5 7 13 15

10 4 6 12 14

0

01 1 3 9 11

00 0 2 8 10

00 01 10 11

a) b)

Obr. 2 Číslování buněk v 2D pomocí z-uspořádání

Nevýhodou těchto technik je, že stejný odkaz na objekt se může vyskytovat v mnoha buňkách. Poměr počtu odkazů ku počtu reprezentovaných objektů může být vysoký a ztěžovat vyhodnocování dotazů. Výhodou z-uspořádání je linearizace 2D. Lze si všimnout, že většina bodů blízkých v prostoru bude blízko sebe i na Peanově křivce.

Další možností, jak organizovat prostor, je technika překrývajících se oblastí. Často jde o minimální ohraničující obdélníky, kdy skutečný objekt je ohraničen nejmenším možným obdélníkem, jehož reprezentace i manipulace je jednoduchá. V této technice je každý objekt přiřazen právě jedné oblasti. Nejznámějšími technikami využívající překrývající se oblasti jsou R- a R* -stromy.

Konečně transformační techniky zobrazují objekty z d-rozměrného prostoru jako body v 2d-rozměrném prostoru. Pro indexaci takových objektů - bodů pak lze použít jako datovou strukturu techniky pro víceatributové klíče známé z klasických databází.

Databáze prostorových objektů mají rozsáhlé využití i v IS v pohyblivém prostředí. Jedeme v autě a chceme vědět, kde je nejbližší čerpací stanice. K úspěšné odpovědi stačí chytře konstruovaný GIS a napojení osobní stanicí v autě vzduchem na nějaký blízký server. Každý tuší, že dnes už nejde o žádné utopie.



<seznam dílů seriálu>   <COMPUTERWORLD>