Spatial databases bring new requirements on a query formulation. These queries use spatial relationships of objects and they imply new requirements on associated data structures used for representation of the objects. The paper introduces a taxonomy of spatial query types and a survey of data structures they support these queries. We focus mainly on special types of trees such as R-, R+-, and R*-trees.
Abstrakt
Databáze prostorových objektů přinášejí nové požadavky na formulaci dotazů. Tyto dotazy využívají prostorových vztahů objektů a kladou speciální požadavky na datové struktury, pomocí kterých jsou objekty reprezentovány. V článku je uvedena kategorizace typů prostorových dotazů a přehled datových struktur, které je podporují. Patří sem zejména speciální typy stromů, jako jsou R-, R+-, R*-stromy.
Úvod
V poslední době zvýšená pozornost databázové komunity o prostorová data má kořeny ve zpracování rozsáhlých dat o objektech v CAD (Computer Aided Design), CIM (Computer Integrated Manufacturing), CASE (Computer Aided Software Engineering) a geografických databázích. Kromě vlastních prostorových dat je samozřejmé reprezentovat v databázi další vztažené údaje, jež jsou svojí podstatou formátovanými daty. Zatímco formátovaná data jsou snadno udržovatelná (např. v relační databázi), prostorová data vyžadují jistý speciální přístup. Historicky se tak vyvíjely dvě technologie, které se jen obtížně dařilo integrovat v jeden systém. Časem se přidružily další aplikace, např. dvojrozměrná (vrstvená) data VLSI, z trojrozměrného prostoru jmenujme vedle dat o trojrozměrných tělesech např. bio-computing, tj. zpracování dat biologických struktur. Zdrojem prostorových dat mohou být i roentgenové či satelitní snímky, z nichž jsou odpovídající prostorová data extrahována. Uvedené příklady aplikací se obecně zahrnují pod tzv. netradiční aplikace. Poskytují možnosti realizace prostorových dotazů, jako je nalezení průniku dvou objektů, nalezení objektů v dané vzdálenosti od daného objektu apod. O jaké objekty jde? Všeobecně známým příkladem v dvojrozměrném prostoru může být třeba mapa, na kterou se můžeme dívat jako na soustavu polygonů. Jiným dobře studovaným typem objektu jsou polygony s dírami, kterými lze modelovat např. zemi s jezery.
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 kterýmikoliv jinými daty, nevyužíváme geometrických vlastností prostoru.
Existují tři podstatné rysy prostorových objektů:
S novými aplikacemi se ustanovily pojmy prostorová databáze a obrázková databáze. Tyto pojmy se někdy zaměňují. Prostorové databáze obsahují vícerozměrná včetně údajů o objektech a jejich pozici v prostoru. Objekty jsou obvykle reprezentovány v nějaké vektorové formě, jejich relativní pozice je buď explicitní nebo implicitní. Obrázkové databáze poskytují neanalyzovaná obrazová data, typicky reprezentovaná v nějakém rastrovém formátu. Článek je zaměřen spíše na prostorové databáze, přesněji – na vícerozměrné přístupové metody, které mohou být v takových databázích využity.
Mezi požadavky na vícerozměrné přístupové metody patří zejména [GG98]:
? Dynamika. Protože objekty jsou do databáze a z databáze odstraňovány v libovolném pořadí, je nutné, aby přístupová metoda odrážela stopu těchto změn.
? Řízení sekundární a terciární paměti. Přes neustálý růst vnitřních pamětí je nutné počítat s tím, že přístupová metoda by měla umožnit přistupovat k datům uloženým na sekundární či terciární paměti.
? Podpora širokého okruhu operací. Přístupová metoda by neměla podporovat např. pouze rychlé vyhledávání, ale i další operace jako INSERT atd.
? Nezávislost vstupních dat a posloupnosti jejich vkládání do databáze. Účinnost přístupové metody by neměla být ovlivnitelná např. nerovnoměrným rozložením dat.
? Jednoduchost. Metody s mnoha speciálními případy a triky jsou obtížné k implementaci a mohou vést k chybám v krajních situacích.
? Škálovatelnost. Metoda by měla být způsobilá k adaptaci v případě růstu databáze.
? Časová účinnost. Časová složitost vyhledávání by neměla přerůst logaritmickou složitost v nejhorším případě. Složitost by neměla záviset na rozložení dat, posloupnosti aplikací operace INSERT a na výběru podmnožiny prostorových atributů pro dotaz.
? Prostorová účinnost. Index založený na přístupové metodě by měl být malý ve srovnání s velikostí databáze.
? Souběžnost a zotavení. Přístupová metoda by měla poskytovat dobré možnosti pro souběžný přístup (transakční zpracování).
? Minimální škodlivý vliv. Integrace přístupové metody do databázového systému by měla mít minimální škodlivý vliv na jeho ostatní části.
V odstavci 1 se zaměříme na reprezentaci prostoru, která hraje hlavní roli při konstrukci prostorových přístupových metod. Odstavec 2 je věnován aproximaci objektů. V odstavci 3 je podán výčet typů prostorových dotazů. V odstavci 3 jsou rozebrány typy prostorových přístupových metod s podrobnější ukázkou R-stromů a jejich variant.
1. Reprezentace prostoru
Cílem prostorové přístupové metody je organizace a reprezentace prostoru. 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. Nazveme tuto techniku vystřihováním (clipping).
Pravidelné rozdělování do hierarchické soustavy buněk se obvykle zadává pomocí radixových stromů zvaných též rd-stromy. Známými představiteli radixových stromů jsou 4-stromy a 8-stromy. 4-strom je radixový strom s d = 2 a r= 2, 8-strom je radixový strom s d = 3 a r = 2. Na obrázku 1 je ukázka 4-stromu spolu s reprezentací jistého prostorového objektu v rovině, který je pomocí radixového stromu přístupný.
Obr.1 Objekt a jeho reprezentace 4-stromem
Základní ideou těchto metod 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 už v r. 1974 ?FB74?. Patří vedle K-D - stromů z r. 1975 ?Be75? k nejstarším technikám pro ukládání vícerozměrných dat. 4-stromy jsou ovšem vhodné v případech, kdy se nacházejí celé ve vnitřní paměti, snadno je též vidět, že mohou být výškově nevyvážené.
Buňky lze číslovat různým způsobem. Na obrázku 2a) je varianta známá pod jménem z-uspořádání. V z-uspořádání jsou buňky identifikovány jistým 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. Nevýhodou je, že stejný odkaz na objekt se může vyskytovat v mnoha buňkách. 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 2b) je ukázána křivka, která odpovídá z-uspořádání. Nazývá se Peanova. Křivek, které umožňují vhodně vyplnit prostor, je více typů. Peanova je však nejznámější . Užitečná je např. Hilbertovu metoda použitá pro uspořádání v ?FR89?. Hilbertova křivka má, narozdíl od z-uspořádání, tu vlastnost, že body, které jsou sousední v Hilbertově uspořádání jsou sousední i v původním prostoru. Nevýhodou je složitější konstrukce Hilbertovy křivky.
a) b)
Obr. 2 Číslování buněk
Výhodou křivek vyplňujících prostor je, že jsou použitelné pro jakýkoliv počet dimenzí. Transformace do jednorozměrného prostoru znamená, že na data takto získaná lze použít jednorozměrné techniky (např. B-stromy). Chceme-li však použít dva indexy založené na těchto křivkách pro společné zpracování (např. prostorové spojení), je nutné jeden z nich přepočítat (nemusí být totiž kompatibilní).
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 (MOO). V prostoru libovolné dimenze budeme hovořit o vícerozměrných kostkách, event. minimálních ohraničujících (vícerozměrných) kostkách (MOK). V této technice je každý objekt přiřazen právě jedné oblasti. Nejznámějšími technikami jsou zde R- a R?-stromy (?Gu84?, ?BKSS90?). Při pokrývání prostoru se metody různí ještě v jednom důležitém aspektu: zdali pokrývají úplně celý prostor nebo ne. Ze známých technik pouze jedna se řadí do druhé kategorie. Jde o tzv. buddy-stromy ?SK90?.
Zobecněním techniky překrývajících se oblastí je technika více vrstev. Vrstvy jsou organizovány v hierarchii, přičemž v každé vrstvě se oblasti nepřekrývají. Data z různých vrstev se ale mohou překrývat. Z přístupových metod sem patří např. víceúrovňová vícerozměrná mřížka [SW88] a R-file [Hu90].
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ů pak lze použít techniky jako vícerozměrná mřížka apod., tj. techniky pro víceatributové klíče. Jednoduchý příklad poskytuje metoda na zobrazování úseček (intervalů) jako bodů ve dvojrozměrném prostoru. Transformuje se počáteční a koncový bod intervalu nebo střed intervalu a polovina délky. Poněvadž pravý koncový bod intervalu je vždy větší než levý koncový bod, leží výsledné body transformace nad diagonálou datového prostoru. Jinou alternativou může být transformace z d rozměrů do lineárního prostoru. Mezi takové metody patří transformace využívající křivek vyplňujících prostor. Nevýhodou zmíněných metod ovšem je, že transformací mohou být narušeny původní prostorové vztahy objektů.
2. Aproximace objektů
Již jsme zmínili, že řada přístupových metod pro prostorové objekty je založena na ukládání aproximací objektů pomocí MOO, resp. MOK. V těchto technikách je objekt reprezentován pouze na jednom místě - pomocí MOO a odkazu na korespondující objekt. Tímto je umožněno i jednodušší shlukování objektů a následné ukládání shluku do jedné stránky na 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 větší je tato plocha, 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 nejprve 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.
MOO je příkladem konvexní konzervativní aproximace. Existují však i další, které většinou mají lepší vlastnosti než MOO. Vyžadují ovšem většinou paměťově náročnější reprezentaci. Tak např. otočený MOO vyžaduje 5 parametrů, minimální ohraničující n-úhelník vyžaduje 2n parametrů atd. Možná je i minimální ohraničující kružnice (3 parametry) či elipsa (5 parametrů). V ?BKSS94? jsou popsána měření takových aproximací, přičemž 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 3 ukazuje objekt aproximovaný obdélníky jak konzervativně, tak progresivně.
Obr. 3 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.
3. Prostorové dotazy
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. Např. relace MĚSTO(Jméno_m, PSČ, Populace, Území_l) obsahuje geometrický atribut Území_m, který popisuje hranice měst pomocí dvourozměrných mnohoúhelníků. Typickým dotazem je dotaz - okno, tj. najít v daném čtverci (obdélníku) objekty města, která se v něm nacházejí. Relace, obsahují alespoň jeden geometrický atribut, se nazývá prostorová relace.
Typickou vlastností prostorových dotazů je, že omezují nějakým způsobem vyhledávací prostor zadáním místa a jeho okolí. Takové dotazy se nazývají selektivní. Neselektivní dotazy vyžadují tedy 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. Je tedy požadováno fyzické shlukování objektů. Řada prostorových přístupových metod má tuto vlastnost. V opačném případě musí totiž být každý uložený objekt vyhodnocován vzhledem k dotazu, což vede právě v případě prostorových objektů k velkým časovým ztrátám.
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í a 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 skutečnými objekty, ale efektivněji pouze s jejich geometrickými aproximacemi. Dobré zkušenosti jsou např. s dekompozičními technikami, i když počet jednoduchých objektů účastnicí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ůznými typy operací a dotazů. Zaměříme se na prostorové relace s jedním geometrickým atributem. Nebudou-li tematické atributy pro danou operaci podstatné, je možné se na relace dívat jako na množiny objektů, tj. A=?a1, a2,..., an?, B=?b1, b2,..., bm?.
? aktualizační operace: podobně jako u klasických DBS zahrnují operace pro vkládání (INSERT), odstraňování (DELETE) a změny záznamů (UPDATE).
? selekce: může se týkat jednak tematické komponenty, jednak prostorové komponenty. Zaměříme se pouze na druhý případ.
Dotaz na úplnou shodu - k danému objektu nalézt všechny stejné objekty.
Dotaz na bod - k danému bodu b nalézt takové objekty o ? A, pro které b ? 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 najít množinu objektů M ? A takovou, že pro každý m ? M platí m ? R.
Dotaz na obsah oblasti - k oblasti R najít množinu objektů M ? A takovou, že pro každý m ? M platí m ? R.
Uvažovat lze také dotaz na přiléhající sousedy a dotaz na nejbližší sousedy.
? kombinace objektů: Nejznámější operací je prostorové spojení. Může být obecně definováno na více relacích. Zde se zaměříme na binární případ. Prostorové spojení pro daný predikát P je množina 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, podobně jako v relační algebře, 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ů 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 výpočet tohoto překrytí.
Operace nad prostorovými objekty nemusí být uzavřené, jak tomu je v relační algebře. Např. průnik dvou polygonů může být několik bodů, hrana, nebo několik polygonů.
4. Vícerozměrné přístupové metody
Mnoho vícerozměrných přístupových metod vzniklo zobecněním jednorozměrných. Mezi základní jednorozměrné metody patří B-stromy a rozšiřitelné hašování (viz např. [Po97]). V obou případech jde o dynamické struktury, z nich zvláště první patří mezi principiální při řešení implementace indexů v relačních databázích.
Důležité místo ve vývoji vícerozměrných přístupových metod zaujímají techniky určené pro implementaci ve vnitřní paměti. Patří sem již zmiňované čtyřstromy, K-D stromy a z novějších technik BD-stromy [OS83].
Další metody již jsou navrženy tak, že existuje jednoduchá korespondence oblastí dat a diskových stránek. Z metod, které byly vytvořeny pro přístup k bodům vícerozměrného prostoru, jmenujme alespoň vícerozměrnou mřížku, vícerozměrné hašování a buddy stromy. Řada metod pro bodová data je založena na použití křivek vyplňujících prostor. Body ležící v prostoru blízko sebe se s vysokou pravděpodobností vyskytují blízko sebe i v úplném uspořádání daném příslušnou křivkou.
Zřejmě nejpotřebnější, ale také nejsložitější, jsou metody umožňující organizovat vícerozměrné prostorové objekty, případně tyto objekty spolu s body. Příslušné techniky vycházejí z uspořádání prostoru, kde se objekty nacházejí. Lze je rozdělit do těchto kategorií:
? transformační,
? překrývající se oblasti,
? vystřihování,
? techniky více vrstev.
Ukážeme zde pouze metody využívající překrývající se oblasti – R-stromy a R*-stromy.
Nejznámější přístupovou metodou pro prostorové objekty jsou R-stromy navržené Guttmanem v roce 1984 ?Gu84?. R-strom představuje jednoduchou modifikaci B-stromů, kde záznamy v listových uzlech stromu obsahují ukazatele k datovým objektům reprezentujícím prostorové objekty. Technika používá MOO, či obecněji MOK.
Databáze d-rozměrných prostorových objektů obsahuje n-tice reprezentující tyto prostorové objekty např. pomocí jednoznačných identifikátorů. Vlastní indexace takových objektů je dána pomocí dvojic (I, indentifikátor n-tice), přičemž I je d-rozměrná kostka ohraničující odpovídající prostorový objekt. Tyto záznamy budeme nazývat indexové. Kostka má tvar (I0, I1,..., Id-1), kde Ii je interval ?ai,bi? popisující ohraničení objektu v dimenzi i. Vnitřní uzly obsahují záznamy tvaru (I, ukazatel), přičemž ukazatel ukazuje na podstrom v R-stromu takový, že I pokrývá všechny kostky, které se v něm vyskytují. Na rozdíl od B-stromu není striktně dodrženo pravidlo o polovičním naplnění uzlů v nejhorším případě. Je-li R-strom m-ární strom, pak m1 budeme označovat parametr, pro který platí m1 ? m/2. Minimální počet následníků uzlu R-stromu bude m1. R-strom je tedy m-ární strom, který má následující vlastnosti:
1. Každý jeho vnitřní uzel má n bezprostředních následníků, n ??m1, m ?.
2. Každý listový uzel obsahuje n indexových záznamů n ??m1, m?.
3. Kořen má nejméně dva bezprostřední následníky, není-li listem.
4. Všechny cesty v R-stromu jsou stejně dlouhé.
Pro E indexových záznamů je v nejhorším případě hloubka R-stromu ?logmE? -1, nejhorší naplněnost stránky je m1/m. Příklad R-stromu pro m = 4 spolu s objekty ukazuje obrázek 4.
R-strom je struktura dynamická, tj. je založena na štěpení stránek (pro INSERT) a slévání stránek (pro DELETE). Na rozdíl od B-stromů není hledání v R-stromu určeno jednou větví. Protože vícerozměrné kostky ohraničující kostky v jednotlivých podstromech se mohou překrývat, je možné, že existuje více než jedna možnost, jak pokračovat při prohledávání stromu z jednoho uzlu. Tím je hledání složitější a veškeré optimalizace používané při konstrukci R-stromu jsou založeny na požadavku co nejvíce separovat ohraničující kostky, aby se omezil prostor vyhledávání. Z toho plynou speciální požadavky na algoritmy typu INSERT, kde se realizují různé heuristiky nabízející víceméně uspokojivá řešení daného problému.
Algoritmus vkládání indexového záznamu do R-stromu má pro zpracování dotazů strukturu zásadní důležitost. Je založen na strategii nalézt takovou větev ve stromě, tj. takový list R-stromu, že opravy kostek po cestě ke kořenu povedou k co nejmenším změnám. Důležitá bude i procedura pro štěpení. Tam se řeší problém, jak rozdělit neuspořádanou množinu kostek do dvou uzlů. Rozdělení záznamů do dvou uzlů je děláno tak, aby bylo co nejméně pravděpodobné, že bude potřeba oba uzly při prohledávání zkoušet. Protože uzly jsou navštěvovány z uzlu-předchůdce, je nutné minimalizovat celkový objem kostek v uzlech.
Pro rozdělení uzlů je možné použít algoritmus uvažující všechny možnosti. Hledá se globální minimum, přičemž algoritmus má exponenciální složitost. Guttman uvádí další algoritmy, lineární a kvadratický, které pouze aproximují řešení.
Obr. 4 Příklad R-stromu
Při budování R-stromu dynamickým způsobem pomocí operace INSERT se používaly dva parametry, které byly minimalizovány:
? prostor pokrývaný kostkou z vnitřního uzlu R-stromu,
? překrytí dvou kostek z vnitřního uzlu R-stromu.
Existují však další možnosti. Za vhodné může být např. zvoleno kritérium minimalizace plochy kostek. V dvojrozměrném prostoru jde tedy o MOO. Protože nejmenší obvod má čtverec, pokrývající kostky by mohly být čtverce (krychle). Toho lze využít v dotazech typu okno, kde okno je čtverec.
Dalším parametrem je využití paměti.
? Paměť by měla být minimalizována.
Jde o to udržet nízkou hloubku R-stromu, což vede k nižší ceně dotazu. Parametry se ovšem ovlivňuje netriviálním způsobem. Např. uplatnění prvních dvou parametrů vyžaduje větší volnost v uzlech a tím tedy vede k nižšímu využití paměti. Také MOO budou méně čtvercové. Naopak použití čtverců (krychlí) vede k lepšímu seskupování, tj. k efektivněji využité paměti.
Zajímavou variantou R-stromu je R+-strom [St86], kde na jednotlivých úrovních R-stromu nedochází k překrývání MOO.
Závěr
Zhodnocení prostorových přístupových metod je obtížné. Každá taková metoda, podobně jako je tomu u každé datové struktury, je optimalizovaná pouze v některých parametrech. Často závisí na rozložení dat, na růstu datové struktury, dokonce i na obratnosti, s jakou je metoda naprogramována. Jedno je zřejmé – budoucí prostorové databáze se neobejdou bez robustních a efektivních přístupových metod či dokonce více alternativních metod sloužících k optimalizaci různých aspektů chování databáze. Kromě vlastních metod a jejich implementace představuje výzvu i jejich začlenění do chodu již existujícího DBS. Již zmíněné prostorové nadstavby relačních systémů umožňují „zasouvat“ do SŘBD moduly dokonce v alternativních implementacích, nicméně zatím bez náležitého ošetření na úrovni globálního optimalizátoru dotazů. Objevují se tak motivace pro vývoj nových databázových architektur.
Literatura
?Be75? Bentley, J.: Multidimensional Binary Search Trees used for Associative Searching. Communications of ACM, 18, 9, Sep. 1975, pp. 509-517.
?BKSS90? Beckmann, N. et all: The R?-tree: An Efficient and Robust Access Method for points and Rectangles. Proc. 1990 ACM/SIGMOD International Conf. on Management of Data, May, Atlantic City, USA, 1995, pp. 23-25
?BKSS94? Brinkhoff, T. et al: Multi-Step processing of Spatial Joins. Proc. of SIGMOD 94, 1994.
[BSTW86] Bentley, J.L., et al: A locally adaptive data compression schema. CACM, 29, 4, 1986.
?FB74? Finkel, R., Bentley, J.: Quad Trees: A Data Structure for Retrieval on Multiple Keys. Acta Informatica, Vol. 4, No. 1, 1974, pp. 1-9.
?FR89? Faloutsos, C., Roseman, S.: Fractals for Secondary Key Retrieval. Proc of the ACM Conf. on Principles of DBS, 1989, pp. 247-252.
?GG98? Gaede, V., Günter, O.: Multidimensional Access Methods. Computing Surveys, Vol. 30, No. 2, 1998.
?Gu84? Guttman, A.: R-trees: a dynamic index structure for spatial searching. Proc. of SIGMOD Int. Conf. of Management of Data, 1984, pp. 47-54.
[OS83] Oshawa, Y., Sakauchi, M.: BD-tree: A new N-dimensional data structure with efficient dynamic characteristics. Proc. 9th World Computer Congress. IFIP, 1983, pp. 539-544.
[Po97] Pokorný, J.: Základy implementace souborů a databází. Skripta MFF UK, Vydavatelství Karolinum, Praha, 1997.
?SK90? Seeger, B., Kriegel, H.-P.: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. Proc. of the 16th VLDB Conference, Brisbane, Australia, 1990.
[SO82] Scheuermann, P., Ouksel, M.: Multidimensional B-trees for associative searching in DBS. Information systems, 7., 2, 1982.
[St86] Stonebraker, M. et al: An Analysis of rule indexing implementation in database systems. Proc. of 1st Conf. on Expert Data Base Systems, 1986.
[SW88] Six, H.W., Widmayer, P.: Spatial searching in geometric databases. Proc. 4th IEEE Int. Conf. of Data Engineering, 1988, pp. 496-503.