Peanon relaatiot ja Peanon algebra

• Helsinki 21.2.1997
• Paikkatietojärjestelmät-seminaari
• HELSINGIN YLIOPISTO
• Tietojenkäsittelytieteen laitos

Tavallisen relaatiomallin käyttö paikkatiedon tallentamiseen ja kyselyiden tekemiseen on houkutteleva ajatus. Tavallisen relaatiomallin teoria on laajalti tunnettu ja valmiita siihen perustuvia järjestelmiä on yleisesti saatavilla. Ongelmana on, että tavallinen relaatiomallin ei periaatteeltaan sovellu paikkatiedon kuvaamiseen. Syy on siinä, että tavallinen relaatiomalli on luonteeltaan ekstensionaalinen mutta paikkatieto on luonteeltaan sekä ekstensionaalista että intensionaalista.

Esimerkiksi sopii pelto, joka on täsmälleen neliön muotoinen. Se voidaan tallettaa tavalliseen relaatiotietokantaan yhtenä monikkona. Se voidaan myös jakaa neljään osaan, joista kukin talletetaan omana monikkona. Näitä monikkoja yhdistää oliotunniste, josta tiedetään monikkojen kuvaavaan osaa isommasta oliosta, pellosta. Paikkatiedossa siis ei ole tarkoin määrätty, miten maailma koodataan tietokantaan sopivaan muotoon ja millä tarkkuudella maailman tiedot talletetaan. Tavanomaisessa relaatiomallissa taas yhtä monikkoa ei voi vastata joukko monikkoja vaan kaikki tarvittava tieto olisi talletettava eksplisiittisesti. Tavanomainen relaatiomalli ei siis sovellu hyvin paikkatiedon hallintaan.

Myös kyselyjen esittäminen aiheuttaa ongelmia mikäli käytetään tavallista relaatiomallia ja kyselyt esitetään relaatioalgebralla tai siihen perustuvalla SQL-kielellä (Structured Query Language).

On olemassa eräs kätevä tapa mallintaa maailmaa. Tämän tavan nimi on Peanon malli. Peanon malli on pohjimmiltaan intensionaalis-ekstensionaalinen menetelmä ja siinä maailma kuvataan Peanon relaation (Peano relation) avulla. Lisäksi malliin liittyy Peanon algebra (Peano-tuple algebra), jonka avulla on mahdollista ratkaista hankalilta vaikuttavia kyselyitä yksinkertaisesti pitkälti tavallisen relaatioalgebran tavoin.

Peanon malli on pizza-malli. Pizza-mallit ovat läheistä sukua rasterimalleille. Peanon mallissa valitaan ruudukko (grid), jonka ruutukoko on sopiva maailman kuvaamiseen. Sitten maailma peitetään tällä ruudukolla ja tämän jälkeen kunkin ruudun alle jäävää aluetta kohdellaan yhtenä atomisena maailman osana. Peanon mallissa hyödynnetään tilan täyttävien käyrien (space-filling curve) ja nelipuiden (quadtree) tekniikkaa.

Tilan täyttävä käyrä (space-filling curve) on ääretön jono käyriä, joiden raja arvo täyttää annetun neliön. Kuvassa 1 on esitetty tilan täyttäviä Peanon käyriä. Tilan täyttävän käyrän avulla voidaan moniulotteinen maailma linearisoida eli saamme alkioille järjestyksen jonka avulla ne voidaan luetella yksiulotteisesti jonona.

Nelipuu (quadtree) on yleistys binääripuusta. Siinä haaraumasolmulla on aina neljä lasta ja jokainen solmu esittää vanhempansa yhtä neljännestä (quadrant). Nelipuun avulla tietoa saadaan tiivistettyä, sillä mikäli vanhemman kaikkien neljän lapsen ominaisuudet ovat samat, voidaan nämä neljä lasta kuvata pelkän vanhemman avulla.

Peanon mallissa maailman ylle asetetun ruudukon ruudut numeroidaan Peanon käyrän mukaisessa järjestyksessä. Kuhunkin ruutuun liittyvä järjestysnumero on nimeltään Peanon avain. Koska Peanon mallissa ruutuja on voitu yhdistellä, täytyy tallentaa myös ruudun sivun pituus. Nyt kukin ruutu voidaan ilmaista parin [p,s] avulla, jossa p on Peanon avain ja s on ruudun sivun pituus.

Kuvassa 2 on esitetty ruudukko, jonka ruudut on numeroitu Peanon käyrän mukaisesti ja maailma, joka on kuvattu tämän ruudukon avulla. Kuvassa näkyy myös nelipuu aukipiirrettynä. On huomattava, että “ison” ruudun Peanon avaimeksi otetaan sen vasemman alanurkan neliön Peanon avain.

Peanon avaimien ja tavallisten x- ja y-koordinaattien välillä oleva yhteys hyvin saattaa vaikuttaa monimutkaiselta. Itse asiassa yhteys on hyvin yksinkertainen: Peanon avain saadaan x- ja y-koordinaateista lomittamalla nämä bittitasolla. Katsotaan esimerkiksi kuvan 2 ruudukkoa ja valitaan siinä esiintyvä Peanon avain 11 lähemmän tarkastelun kohteeksi. Tämän neliön x-koordinaatti on 3 (2-kantaisena 00 11) ja y-koordinaatti 1 (2-kantaisena 00 01). Lomitamme nämä valiten ensin bitin x-koordinaatista, sitten y-koordinaatista jne. Tulos on 00 00 10 11 eli 10-kantaisena 11.

Kuten aikaisemmin jo todettiin, Peanon malli muistuttaa läheisesti rasterimallia. Nelipuutiivistyksen vuoksi se on kuitenkin tiiviimpi tapa mallintaa maailmaa. Peanon mallissa pyritään aina minimoimaan ruutujen määrä nelipuutiivistyksen avulla tiettyjen myöhemmin esitettävien sääntöjen mukaan.

Edellä tutustuimme Peanon malliin pitkälti graafisesti. Katsotaan nyt, miten Peanon mallin mukainen tieto maailmasta saadaan esitettyä matemaattisen mallin avulla. Tavallinen relaatiomalli ei sopinut tarkoitukseen, kuten kappaleessa 1 todettiin. Tarvitaan uusi relaatio, Peanon relaatio, joka määritellään seuraavasti:

PR ( OID, P, S, A1, A2, ..., An )

jossa OID on olion tunniste, P Peanon avain, S sivun pituus ja A1, A2, …, An ovat temaattisia attribuutteja. Tämä on Peanon relaation perusmuoto. Perusmuodosta voidaan viritellä erilaisia muunnoksia kuten se, että kullekin oliolle voidaan ilmoittaa siihen kuuluvien ruutujen Peanon avainten alku- ja loppuarvo. Tässä esityksessä keskitytään kuitenkin pelkästään perusmuotoon.

On huomattava, että Peanon avaimen esiintyminen ei tee relaatiosta Peanon relaatiota. Peanon avainta voidaan käyttää aivan hyvin tavallisen relaatiokaavion avulla määritellyssä relaatiossa. Vastaavasti Peanon relaation yhteydessä ei ole välttämätöntä käyttää juuri Peanon avainta vaan voidaan valita jokin muu tilanteeseen sopivampi avain, esim. Hilbertin avain.

Yhdestä Peanon mallin atomisesta alkiosta voidaan käyttää useaa nimeä: monikko, neljännes, ruutu tai neliö (engl. tuple, quadrant, square).

Tavallisen relaatiomallin yhteydessä olemme tutustuneet ns. normaalimuotoihin, joiden ehtojen täyttyminen takaa relaation tietynlaisen oikeellisuuden ja eheyden. Peanon relaatiollekin voidaan määritellä samantapaisia ehtoja. Peanon relaatioiden yhteydessä puhutaan yhdenmukaisuustasoista (consistent conformance levels), joita on kolme:

• ensimmäinen yhdenmukaisuustaso (first conformance level) 1CL: Neljännesten oikea valinta ja sijoittelu
• toinen yhdenmukaisuustaso 2CL: päällekkäisiä neljänneksiä ei ole
• kolmas yhdenmukaisuustaso 3CL: mahdollisimman suuri tiivistys

Seuraavassa käsitellään yhdenmukaisuustasoja tarkemmin. Ehtojen tarkat matemaattiset kaavat on jätetty pois ja ne on löydettävissä lähdemateriaalista.

Ensimmäinen yhdenmukaisuustaso määrää, että kunkin relaatiossa olevan monikon on oltava todellisen nelipuun neljännes. Mikä tahansa neljännes ei ole mahdollinen johtuen nelipuun määritelmästä. Tämä ehto koostuu oikeastaan seuraavasta kolmesta osaehdosta:

• Sivunpituuden on oltava aina kahden potenssi (1, 2, 4, 8, … )
• Neljänneksen koko ei saa ylittää maailmamme rajoja
• On voimassa seuraava ehto kunkin monikon sivunpituuden ja Peanon avaimen välillä: sivunpituuden bittiesityksessä olevien nollien määrä on oltava alle puolet Peanon avaimen bittiesityksen oikeassa laidassa olevien nollien määrästä

Kolmas ehto saattaa kuulostaa ihmeelliseltä, mutta siinä on vinha perä. Kuvassa 7 nähdään mitä nämä ehdot käytännössä tarkoittavat. Peanon avaimessa 8 (2-kantaisena 1000) on kolme nollaa oikeassa laidassa, siis sivunpituuden ainoat mahdolliset arvot ovat 1 (2-kantaisena 1) ja 2 (2-kantaisena 10) koska nollia saa olla korkeintaan 1 (tarkemmin 1,5 mutta pyöristys tehdään alaspäin). Samalla tavoin Peanon avaimessa 16 (2-kantaisena 10000) on neljä nollaa oikeassa laidassa, joten sivun pituuden mahdolliset arvot ovat 1, 2 ja 4.

Kuvassa 6 nähdään Peanon relaation ilmentymä, joka rikkoo ensimmäisen yhdenmukaisuustason kolmatta sääntöä. Kuvan 6 monikko R (A, 3, 2) rikkoo kolmannen säännön, koska Peanon avaimessa 3 (2-kantaisena 0011) ei ole yhtään oikean laidan nollaa ja sivun pituudessa 2 (2-kantaisena 10) on yksi nolla. Ongelma ratkaistaan hajoittamalla monikko neljäksi monikoksi, jotka on esitetty kuvassa 8. Kuvassa 5 nähdään hajoittaminen havainnolistettuna.

Toisen yhdenmukaisuustason saavuttamiseksi relaatiossa ei saa olla päällekkäisiä neljänneksiä. Tämä tarkistetaan helposti järjestelemällä relaatio Peanon avaimen mukaan ja poistamalla identtisistä ilmentymistä ylimääräiset siten, että vain yksi jää jäljelle. Lisäksi muutkin ilmenevät päällekkäisyydet on poistettava. Nimittäin voihan olla niin, että monikot (ruudut) leikkaavat toisiaan olematta täysin päällekkäisiä.

Peanon relaatio täyttää toisen yhdenmukaisuustason, jos se täyttää ensimmäisen yhdenmukaisuustason ja sen lisäksi mille tahansa kahdelle monikolle pätee epäyhtälö, joka on voimassa vain jos päällekkäisyyksiä ei esiinny.

Kolmannen yhdenmukaisuustason mukaan pitää nelipuun olla mahdollisimman tiivis. Olio on siis oltava kuvattu mahdollisimman tiiviillä esityksellä (minimal valid description). Operaatio toteutetaan ensiksi hajoittamalla kaikki monikot mahdollisimman pieniksi (sivunpituus on 1) ja kokoamalla sitten hajoitetut monikot mahdollisimman suuriksi. Jokaisen hajoitus-kokoamis-operaation (aggregation-disaggregation operation) jälkeen täytyy tarkastaa, että tuloksena syntynyt olio täyttää kaikki yhdenmukaisuustasot (1CL, 2CL ja 3CL). Kuvassa 9 on esimerkki hajoitus-kokoamisoperaation etenemisestä.

Peanon relaatio voidaan hyvin yksinkertaisesti laajentaa kolmeen tai useampaan ulottuvuuteen. Nelipuun sijasta kolmiulotteinen Peanon relaatio on puu, jossa jokaisella vanhemmalla on kahdeksan lasta (octtree). Kappaleessa 4 esitetyt yhdenmukaisuustasojen ehdot on helposti muutettavissa useampaan ulottuvuuteen sopiviksi. Kuvassa 14 on esimerkki kolmiulotteisesta Peanon maailmasta.

Olemme edellä esitelleet Peanon maailman ja Peanon relaation. Peanon relaation avulla kuvattua maailmaa voidaan käsitellä Peanon algebran (Peano-tuple algebra) avulla. Peanon algebra tarjoaa keinot kyselyjen toteuttamiseen ilman vaativaa laskentaa. Peanon algebrassa operaatioita on kolmea eri lajia:

• Boolen operaatiot: yhdiste, leikkaus ja erotus
• Geometriset operaatiot: translaatio, rotaatio, skaalaus, symmetria ja yksinkertaistaminen
• Relaatio-operaatiot: Projektio ja liitos

Osa operaatioista käsitellään seuraavassa pintapuolisesti, osaan syvennytään tarkemmin.

Peanon algebrassa on myös muutama muu operaatio, jotka jäävät tämän esityksen ulkopuolelle.

Kahden olion yhdiste (union) saadaan aikaan (välittämättä mitään Peanon relaatiossa olevan tiedon luonteesta) yhdistämällä olioiden monikot samaan relaatioon. Tämän jälkeen täytyy päällekkäisyyden poistaa (2CL). Kuvassa 10 on esitetty kaksi esimerkkioliota. Kuvan 10 olioiden yhdiste nähdään kuvan 11 kohdassa a.

Kahden olion leikkaus (intersection) selvitetään monikkojen välisen leikkauksen määrittämisellä. Jos olioiden monikot menevät päällekkäin, täytyy ne hajoittaa pienemmiksi monikoiksi. Tämän jälkeen olioiden monikot käydään läpi ja vain ne monikot säästetään, jotka esiintyvät kummassakin oliossa. Kuvan 11 kohdassa b on esitetty kuvan 10 esimerkkiolioiden leikkaus.

Erotus (difference) määritetään leikkauksen tapaan, eli mahdollisten päällekkäisyyksien esiintyessä monikot pilkotaan riittävän pieniksi. Sitten määritetään erotus käymällä läpi olioiden monikot ja säilyttämällä vain erotuksen määräämät monikot. Kuvan 11 kohdassa c on esitetty kuvan 10 esimerkkiolioiden erotus.

Olion translaatio (translation) eli siirto toiseen paikkaan on edellisiin verrattuna hieman monimutkaisempi operaatio. Siirrettäessä kunkin monikon Peanon avain hajoitetaan komponentteihin (x ja y) ja näihin lisätään sen pisteen koordinaatit johon olio halutaan siirtää. Tämän jälkeen koordinaatit lomittamalla saadaan siirretyn olion monikon Peanon avain. Neljännesten kokoon voi myös joutua puuttumaan. Merkitään kirjaimella t sen pisteen Peanon avaimen binääriesityksen oikean laidan nollaparien määrää, johon siirto tehdään. Neljänneksiin joiden koko on pienempi tai yhtäsuuri kuin 2t ei tarvitse koskea vaan ne siirretään sellaisenaan. Neljännekset joiden koko on suurempi kuin 2t täytyy pilkkoa 2t-kokoisiksi. Siirretty olio täytyy lopuksi erikseen korjata kolmanteen yhdenmukaisuustasoon (3CL). Kuvassa 12 on kuvan 10 A-olion translaatio.

Rotaatio (rotation) on translaatiotakin monimutkaisempi. Monikot täytyy ensin hajoittaa minikokoon (eli sivun pituuteen 1). Tämän jälkeen kaikki monikot pitää pyörittää erikseen. Sitten monikot järjestetään ja normalisoidaan (1CL, 2CL, 3CL).

Skaalaus (scaling) on sattumanvaraisella tekijällä sotkee olion rakenteen yleensä pahasti. Jos tekijä on 2i eli kahden potenssi ei nelipuun rakenne muutu. Skaalaus toteutetaan tällöin kertomalla Peanon avaimet tekijällä 4i ja sivun pituudet tekijällä 2i. Yhdenmukaisuustasotkin säilyvät eli normalisointia ei tarvita.

Symmetrian (symmetry) toteuttaminen vaihtelee täysin sen mukaan, minkä suhteen se tehdään (piste, suora, koordinaattiakseli). Asiaa ei käsitellä tässä tarkemmin.

Yksinkertaistaminen (simplify) voi tarkoittaa kahta eri operaatiota:

• Kynnysarvoa pienemmät ruudut poistetaan
• Kynnysarvoa pienemmät ruudut korvataan kynnysarvon kokoisilla

Molempiin siis liittyy kynnysarvo, joka on ruudun sivun pituus. Molemmat operaatiot on esitetty kuvassa 13.

Geometrinen projektio on yksinkertainen operaatio mikäli kappale projisoidaan koordinaattiakselien muodostamalle tasolle. Tällainen projektio on esitetty kuvassa 10. Kuvassa olio projisoidaan tasolle xz nollaamalla y-bitit Peanon avaimista. Esim. Peanon avaimesta 47 (2-kantaisena 101111, y-koordinaatit alleviivattu) tulee 15 (2-kantaisena 1111). Sivun pituudet eivät muutu. Projisoinnin tulos pitää vielä muuttaa täyttämään yhdenmukaisuustasojen vaatimukset. Esim. kuvan 10 kuutioista 44 ja 46 tulee kaksi päällekäistä neliötä eli toisen yhdenmukaisuustason ehdot rikkoontuvat. Geometrinen projektio siis saadaan ilman geometrisia laskelmia, mikäli projisointi tehdään koordinaattiakselien muodostamalle tasolle. Muulle tasolle projisointi onkin vaikeampi juttu ja sitä ei käsitellä tässä.

Eräs mielenkiintoisimmista operaatioista on Peanon relaatioiden liitos. Liitoksen avulla voidaan ratkaista paikkatietoon tyypillisesti liittyvät pistekyselyt ja aluekyselyt. Aluekyselystä on esimerkki kuvassa 16. Kuvan 16 alueet on esitetty relaatioina kuvassa 15.

Kuten kuva 16 kertoo, leikkaa kyselyalue alueita A ja B mutta ei aluetta C. Kysely toteutetaan liittämällä kuvan 15 relaatiot normaalilla relaatioiden liitosoperaatiolla ja sitten projisoimalla valitaan halutut sarakkeet. Tämä välitulos projisoidaan edelleen niin että vain oliotunnisteet jäävät jäljelle. Kuva 17 esittää kuvan 16 kyselyn tuloksen.

Pistekysely tapahtuu kuten aluekysely. Kyselyalue on pistekyselyssä tietenkin resoluution sallima pienin alue (yksi monikko, jonka sivun pituus on 1).

Peanon mallin hyviä puolia ovat se, että se muistuttaa tavallista relaatiotietomallia ja on siten helposti ymmärrettävissä. Samoin tiettyjen kyselyjen helppo toteuttaminen on Peanon mallin hyvä puoli.

Varjopuolena osa muunnoksista (esim. rotaatio) ovat hyvin raskaita operaatioita.

Lähdemateriaalissa oli esitetty kaksi esimerkkiä Peanon mallin käytöstä käytännössä. Nämä esimerkit olivat kuitenkin suppeita ja vaikeasti ymmärrettäviä joten niitä ei esitetä tässä.

• Laurini, R., Thompson, D., Fundamentals of Spatial Information Systems. Academic Press, 1992, s. 507 - 532
• Tässä seminaarissa aiemmin pidetyt esitykset