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Θ₧ r^d-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.