![]() |
![]() |
Prostorové spojení
Představme si na chvíli mapu území a dotaz “Najdi všechny lesy ve městech na daném území”. Jsou-li oba typy objektů součástí mapy, jistě nebude problém získat po troše úsilí odpověď. Poněkud horší situace nastane, budou-li města na jedné mapě a lesy na druhé. Pomineme-li řešení, že mapy jdou překrýt a prohlédnout proti světlu, nebude již získání výsledku tak triviální. O co jde? Překrytí a průniky objektů souvisí s operací, kterou nazýváme prostorové spojení. V databází prostorových objektů budeme předpokládat prostorové relace MĚSTO(Jméno_m, PSČ, Populace, Území_m) a LES(Označení_l, Jméno_l, Území_l), kde geometrické atributy - území popisují hranice měst resp. lesů. Prostorový predikát P, kterým se daný dotaz řeší, je průnik dvou množin. Odmyslíme-li si ostatní atributy relací, pak platí-li P(a,b) = TRUE, nazveme dvojici objektů (a,b) hitem. P může být i jiný prostorový predikát. V každém případě však jde o operaci na dvou prostorových relacích, která vrací další relaci - relaci hitů, které spojují jisté řádky relací na vstupu. Zdá se, že prostorová spojení mají pro prostorové databáze podobnou důležitost jako operace spojení v klasických databázích. Důležitým aspektem implementace prostorových objektů je jejich reprezentace pomocí aproximací. Jednou z možností jsou již v předchozích dílem Databázové abecedy zmiňované MOO, které slouží jako první krok pro výpočet prostorového spojení. Skutečný vztah dvou objektů je aproximován vztahem jejich MOO. Takové spojení nazveme MOO-spojení. Pro průnik dává operace dvojice (Id(a),Id(b)) takové, že platí MOO(a) Ç MOO(b) ¹ Æ . Bohužel, ne všechny dvojice objektů takto získaných jsou hity. Takovým případům budeme říkat falešné hity. Pro přesnější odlišení budeme používat další aproximace a teprve v nerozhodnutelných případech se přistoupí přesné k geometrické reprezentaci prostorových objektů a odpovídajícímu vyhodnocení P(a,b). Nejsilnější operaci pro spojení objektů je ta, která vrací průniky objektů, tj. v případě lesů a měst ty části města, které jsou lesem. Naopak, slabší operace spojení poskytuje pouze identifikátory objektů z dvojice, tj. Id-spojení je definováno jako množina dvojic (Id(a),Id(b)) takových, že platí P(a,b). Hledat pro prostorové spojení inspiraci v relačních databázích nepřináší mnoho užitečného. Algoritmus setřídění-slévání požaduje setřídění objektů a tedy jednorozměrnou reprezentaci dvourozměrných objektů. Bohužel úplné uspořádání prostorových objektů které zachovává prostorové vzdálenosti, neexistuje. Tato cesta je možná pouze u operátoru “překrývá”, kdy se může použít např. z-uspořádání (Peanovy křivky). Omezené možnosti mají díky tomu i indexy, které většinou spoléhají na uspořádání. Hašovaná spojení nejsou vůbec vhodná, takže vlastně zbývá algoritmus vnořených cyklů. Lze ho použít jako odrazový můstek pro další úvahy. Algoritmus PROSTOROVÉ_SPOJENÍ1(A,B) Vstup: prostorové relace A, B Výstup: množina dvojic objektů, které se překrývají Metoda begin ODPOVĚĎ:=Æ ; for i:=1 to m do begin přečti objekt ai z A do bufferA; for j:=1 to n do begin přečti objekt bj z B do bufferB; if P(ai,bj) then ODPOVĚĎ:= ODPOVĚĎ È (ai,bj) end end end Nevýhodou uvedeného algoritmu může být jeho náročnost časová i paměťová v kroku přenášení objektů do vnitřní paměti (buffer). Objekty totiž mohou obsahovat mnoho bodů. Navíc, jeden objekt může být čten vícekrát a také počet cyklů může být vysoký. Zaměříme se proto na postupné zpracování spojení, které vlastní přenos objektů oddaluje a používá ho jen když už neexistuje jiná možnost. Prostorové objekty budeme předpokládat organizované pomocí nějaké vhodné datové struktury, např. R-stromu. Prostorové spojení lze realizovat ve třech krocích:
relace A relace B Procesor pro zpracování prostorových dotazů Prostorové indexy * MOO
geometrický filtr
hity chybné hity dvojice kandidátů
přesný geometrický procesor
Obr. 1 Zpracování prostorového spojení Třetí krok je výpočetně nejdražší, používá algoritmů výpočetní geometrie. Výsledná architektura zpracování je na obrázku 1. Zatím jsme uvažovali pro aproximaci objektů pouze MOO, tj. pouze konzervativní aproximace. Jsou-li spolu s objekty a jejich konzervativními aproximacemi ukládány i jejich nevyužité plochy nebo progresivní aproximace, lze jednoduše získat několik testů pro přesnější rozpoznání hitů. Označme KApr, resp. PApr funkci přiřazující objektu jeho konzervativní, resp. progresivní aproximaci. Funkce NA přiřazuje konzervativní aproximaci objektu jeho nevyužitou plochu. Pak existují postačující podmínky pro to, aby bylo splněno Ç (o1,o2). Lze tak částečně zlepšit algoritmus pro prostorové spojení založené na průniku objektů. Platí následující dvě tvrzení:
Při praktickém řešení problému spojení prostorových objektů, např. pomocí R-stromů, lze postupovat klasicky podle MOO nebo podle nějaké jiné konzervativní aproximace, nebo udržovat vedle MOO ve struktuře ještě další progresivní aproximaci. Základní trik spočívá v tom, že testování “na hrubo” podle MOO je levné. Čím více parametrů konzervativní aproximace, tím složitější je vyhodnocení Ç (o1,o2). Ukládání dalších aproximací znamená také nárůst paměti. Na závěr si ještě vyzkoušíme spojení pomocí z-uspořádání a R-stromů. Prostorové spojení z-uspořádáním Každý prostorový objekt je (v 2D) dekomponován do čtverců rekurzivním dělením objektu Orientace a pozice dělení jsou takové, že výsledné regiony jsou reprezentovány množinou z-hodnot. Dekompozice poskytuje jednu nebo několik takových množin z-hodnot z1,..., zn. Prostorový objekt je definován sjednocením oblastí korespondujících k z1,..., zn. Tyto oblasti obsahují objekt, tj. jde o konzervativní aproximaci objektu. Každý prostorový objekt je dán jako množin dvojic [ z1, o] ,...,[ zn, o] . Prostorové spojení je založeno na algoritmu setřídění-slévání pro dvě posloupnosti, které jsou z-uspořádány, tj. každá z nich je setříděna podle z-hodnoty. V prvním kroku algoritmu prostorového spojení se získají dvojice (Id(a),Id(b)), pro které z-hodnota z a je obsažena mezi z-hodnotami z b nebo naopak. Ve druhém kroku se přejde ke geometrickému porovnání. Prostorové spojení pomocí R-stromù Budeme předpokládat, že pro každou prostorovou relaci A, B existuje odpovídající R-strom. Dalším (ne nutným) předpokladem bude stejná hloubka obou R-stromů. Algoritmus MOO-spojení lze popsat následovně. Algoritmus PROSTOROVÉ_SPOJENÍ3(T,U) Vstup: R-stromy s kořeny T, resp. U Výstup: množina dvojic identifikátorů objektů, jejichž MOO se překrývají Metoda foreach ET Î T do forach EU Î U with ET.I Ç EU .I ¹ Æ do if U je list then PRINT(ET.Id , EU .Id) else PROSTOROVÉ_SPOJENÍ3(ET. p, ET.p); end end Pro algoritmus je důležité minimalizovat nejenom počet přístupů na disk, ale i čas CPU, který může při vyhodnocování operace průnik vzrůstat. Jedno ze zlepšení algoritmu bude zahrnovat omezení prohledávaného prostoru, tj. redukci počtu porovnání dvojic kostek. Další možná zlepšení využívají možností jistého uspořádání kostek v uzlu. <seznam dílů seriálu> <COMPUTERWORLD> |