COMPUTERWORLD
pod kapotou
Prostorové dotazy

S odkazem na předchozí díl databázové abecedy, navážeme na povídání o databázích prostorových objektů a relativně nových systémech řízení databází prostorových objektů (SŘDBPO). Každému je jasné, že databáze je zajímavá nejen tím, jaká data obsahuje, ale hlavně tím, jaké typy dotazů je možné nad ní formulovat. Samozřejmě, každý dotaz ještě musí být zpracován efektivně, tj. musí být zaručena rozumná doba odezvy. Jaké dotazy by měla umožňovat prostorová databáze?

Prostorové objekty se skládají alespoň z jednoho atributu, který popisuje geometrii objektů. Tento atribut obsahuje obecně vícerozměrná data, jako jsou body, přímky, plochy, mnohoúhelníky, tělesa apod. nebo data složitějších typů, které jsou nějakou kompozicí jednoduchých. Budeme dále takové atributy nazývat geometrické atributy. Ostatní atributy popisují kvalitativní a kvantitativní vlastnosti objektů, tj. tematickou komponentu. Např. relace MĚSTO(Jméno_m, PSČ, Populace, Území_m) obsahuje geometrický atribut Území_m, jehož hodnoty popisují hranice měst pomocí dvourozměrných mnohoúhelníků., tj. polygonů. Zřejmě půjde o nějakou množinu dat, takže relace není v 1NF. To ale nevadí, protože nejsme zatím v žádném relačním SŘBD. Mimochodem, nebyl by problém provést normalizaci, i když zde poněkud nepřirozenou, do 1NF.

Typickým dotazem je dotaz typu okno, tj. najít v daném čtverci (obdélníku) objekty města, které se v něm nacházejí. Relaci, obsahují alespoň jeden geometrický atribut, nazýváme prostorovou relací.

Typickou vlastností prostorových dotazů je, že omezují vyhledávací prostor tak, že je zadáno místo a jeho okolí. Takové dotazy se nazývají selektivní. Neselektivní dotazy tedy budou vyžadovat prohledávání rozsáhlého prostoru. Selektivní dotazy zachovávají uspořádání, tj. objekty ležící blízko sebe jsou často přistupovány dohromady. Na prostorovou databázi to tedy klade požadabek na fyzické shlukování objektů. Řada datových struktur pro organizaci prostorových objektů má tuto vlastnost. V opačném případě musí totiž být vzhledem k dotazu vyhodnocován každý uložený objekt, což vede v případě prostorových objektů k velkým časovým ztrátám.

Také vyhodnocování geometrických algoritmů je časově náročné, takže u databází prostorových objektů přestává být hlavním cílem minimalizace počtu diskových operací. Nelze již zanedbávat čas procesoru při vyhodnocování dat ve vnitřní paměti. Další nevýhodou geometrických algoritmů je, že pracují s celým objektem, přestože dotaz potřebuje jenom jeho část. Dotazy se vyhodnocují proto vícestupňově, přičemž v prvním kroku funguje jakýsi filtr, který pracuje ne se skutečnými objekty, ale efektivněji, pouze s jejich geometrickými aproximacemi.

Dobré zkušenosti jsou např. s dekompozičími technikami, i když počet jednoduchých objektů účastnících se zpracování může být vysoký.

Při zpracování požadavkù v databázích prostorových objektů se můžeme setkat s mnoha růnými typy operací a dotazů. Zaměříme se na prostorové relace s jedním geometrickým atributem. Protože tematické atributy pro prostorové operace nejsou podstatné, je možné se na relace dívat jako na množiny objektů, tj. A={ a1, a2,..., an} , B={ b1, b2,..., bm} . V SŘDBPO lze rozlišit následující třídy prostorových operací:

  • aktualizační operace: podobné jako u klasických DBS zahrnují operace pro vkládání, odstraňování a změny záznamů.
  • selekce:

Dotaz na bod - k danému bodu P naléztt takové objekty o z A, pro které P Î o.

Dotaz na oblast - k oblasti R daného typu (např. polygon) nalézt množinu objektů M Í A takovou, že pro každý m Î M platí m Ç R ¹ Æ .

Speciálním případem je dotaz-okno, kde R je obdélník, jehož hrany jsou rovnoběžné s osami.

Dotaz na okolí oblasti - k oblasti R nalézt množinu obdélníků M Í A takovou, že pro každý m Î M platí m Ê R.

  • Kombinace objektů: Nejznámější operací je prostorové spojení. Zde se zaměříme pouze na jeho binární variantu.

Prostorové spojení - je pro daný predikát P množinou dvojic (a,b), kde a Î A , b Î B a platí P(a,b). Prostorové spojení kombinuje geometrické objekty z relací podle nějakého prostorového predikátu, tj. počítá nějakou podmnožinu kartézského součinu daných relací. Značíme je A* B.

Spojení objektů - ve výsledku jsou objekty P(a,b), kde P je operace odpovídající predikátu P.

Je-li P predikát “je průnikem”, pak P je operace Ç . Spojení objektů tedy vede k výpočtu průniku objektů. Dotaz na spojení objektů se využívá ve speciálním geografickém dotazu - překrytí map, kdy nejde jen o test zdali se dvě mapy překrývají, ale o výpočet tohoto překrytí.

V SŘDBPO můžeme rozlišit mezi dvěma typy dotazů:

  • jednoduché prohlížení,
  • vícenásobné prohlížení.

V prvním případě přistupujeme k objektu nejvýše jednou a tedy časová složitost přístupu je lineární vzhledem k nějaké prostorové relaci A. Jako příklady této kategorie dotazů slouží dotaz-okno nebo dotazy na bod. V případě druhém může být jeden objekt přistupován vícekrát a tedy složitost přístupu již nebude lineární. Dotazem tohoto typu je prostorové spojení. Závěrem zdůrazněme, že dobrá technika pro manipulaci prostorových objektů by měla být efektivní i pro dotazy na body. Bod není nic jiného, než degenerovaný prostorový objekt.

Aby bylo možné realizovat prostorové dotazy, vyžadují databáze prostorových objektů, aby vedle přesných objektů, byly v databázi i jejich mnohem jednodušší aproximace. Někdy jsou prostorovými objekty dokonce výlučně tyto aproximace (viz např. plány měst založené na polygonech). Řada datových struktur pro prostorové objekty je založena na ukládání aproximací objektů pomocí minimálních ohraničujících obdélníků (MOO) v 2D, resp. minimálních ohraničujících vícerozměrných kostek (MOVK) v prostorech vyšších dimenzí. V těchto technikách je objekt reprezentován pouze na jednom místě - pomocí MOO a odkazu na korespondující objekt. Tento způsob umožňuje i jednodušší shlukování objektů a tím i ukládání shluku do jedné stránky ve vnější paměti.

K reprezentaci MOO stačí 4 parametry. Z hlediska prostorového spojení ovšem není MOO nejvýhodnější. Problémem totiž je nevyužitý (mrtvý) prostor. Čím je větší, tím častěji je potřeba načítání prostorových objektů do paměti.

Aproximace objektů mohou být i jiné než MOO. Rozlišíme je na konzervativní a progresivní. Pro konzervativní aproximaci platí, že každý bod objektu je bodem jeho aproximace. Konzervativní aproximace mohou být konkávní nebo konvexní. Větší uplatnění nacházejí konvexní konzervativní aplikace, protože pro ně existují efektivnější algoritmy. První, co nás napadne je, že prostorová spojení se budou moci dělat, i když nepřesně, pomocí MOO, a ne na základě porovnávání skutečných objektů.

MOO je příkladem konvexní konzervativní aproximace. Existují však i další, které mají většinou lepší vlastnosti než MOO. Vyžadují však většinou paměťově náročnější reprezentaci. Tak např. otočený MOO vyžaduje 5 parametrů. Možná je i minimální ohraničující kružnice (3 parametry) či elipsa (5 parametrů). Velmi dobré chování bylo zjištěno u pětiúhelníků, které vyžadují 10 parametrů. Nevyužitá plocha se pohybovala okolo 25%. Samotný MOO má chování nejhorší. Nevyužitá plocha zde může i překročit 100%.

Pro body progresivní aproximace platí, že jsou všechny obsaženy v objektu. Jako progresivní aproximace lze použít např. maximální vnořené obdélníky, nebo maximální vnořené kružnice. Obrázek 1 ukazuje objekt aproximovaný obdélníky jak konzervativně, tak progresivně.

 

 

 

 

 

 

Obr. 1 Konzervativní a progresivní aproximace

Jiným typem progresivní aproximace je dekompozice objektů. Objekty jsou rozděleny např. na trojúhelníky, lichoběžníky, či obecnější konvexní polygony.

Nejznámější problém prostorových objektů je svázán s jejich digitalizací. Je-li Eukleidovský prostor spojitý, pak již digitalizací geometrie objektů získáme pouhé aproximace. Problémy pak mohou nastat v případě modelování prostorových vztahů, které jsou řádově srovnatelné s nepřesností digitalizace. Může být problémem zjistit, zdali bod leží na přímce, je-li jeho skutečná vzdálenost srovnatelná s nepřesností digitalizace.

Pohybuje-li se např. robot prostorem řízeným prostorovou databází, mohla by daná nepřesnost vadit. Robot by mohl vrazit do zdi. Uživatele mapy tento problém tolik nebolí. Možná, že na daném místě nenalezne to, co chtěl, a je nucen si zajít o kousek dál.

Dotazy na prostorové objekty spolu s tematickou informací představují část možností multimediálních systémů. Vyžadují novou databázovou technologii, protože využití relační technologie je pouze částečné. Optimisticky řečeno, databázisti mají a ještě budou mít stále co dělat, stále co zkoumat.



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