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 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.