Tietokantajärjestelmät spatiaalisen tiedon louhinnassa

 

Mikko Valjento

Helsinki 10. maaliskuuta 2003
Tiivistelmä, Spatiaalisen tiedon louhinnan seminaari
HELSINGIN YLIOPISTO
Tietojenkäsittelytieteen laitos

 

Johdanto

Tässä esitelmässä pyrin luomaan yleiskuvan spatiaalisessa tietojen louhinnassa käytettävien tietokantajärjestelmien rakenteesta ja toiminnasta. Aluksi esittelen spatiaalisessa mallinnuksessa käytettyjä perustietotyyppejä ja operaatioita. Tämän jälkeen käsittelen spatiaalisia tiedon indeksointimenetelmiä ja indeksoinnissa käytettyjä tietorakenteita. Tämän jälkeen käsittelen spatiaaliseen tietojen louhintaan sopivan järjestelmäarkkitehtuurin yleispiirteitä ja lopuksi esittelen lyhyesti GeoMiner-nimisen geografisen tiedon louhintaan kehitetyn järjestelmän.

Spatiaaliset tietokantajärjestelmät

Spatiaaliset tietokantajärjestelmillä (spatial database systems, SDBS) tarkoitetaan tietokantajärjestelmiä, joiden avulla voidaan käsitellä normaalin ei-spatiaalisen tiedon lisäksi suuria suhteellisen yksinkertaisista geometrisista elementeistä koostuvia tietomassoja (vector data) tai rasterimuotoisesta kuvatiedosta koostuvia tietomassoja (raster data) [Güt94].

Jotta erilaiset spatiaaliset perusoperaatiot olisivat mahdollisia toteuttaa, pitää käsiteltävä tieto mallintaa ns. spatiaalisilla tietotyypeillä (spatial data types) [Güt94]. Spatiaalisen tietotyyppien toteutuksen pitää olla yhteensopiva sekä tietokantajärjestelmän että spatiaalisten operaatioiden ja muiden spatiaalisten tietotyyppien kanssa. Spatiaalisten tietorakenteiden ja niihin kohdistuvien algoritmien tehtävänä on mahdollistaa spatiaalisten tietotyyppien ja operaatioiden toteutus siten, että ne voidaan liittää olemassa olevan tietokantajärjestelmän kyselyarkkitehtuuriin.

Spatiaalisen tiedon indeksointi

Spatiaalisella indeksoinnilla (spatial indexing) pyritään nopeuttamaan spatiaalisia kyselyoperaatioita. Spatiaalinen indeksi organisoi tilan ja siinä olevat kohteet siten, että kyselyoperaatioiden tarvitsee käydä läpi ainoastaan pieni osa spatiaalisten kohteiden koko joukosta [Güt94]. Indeksirakenteeseen tallennetaan spatiaalisia kohteita vastaavia spatiaalisia avainarvoja (spatial keys), jotka ovat todellisia spatiaalisia tietotyyppejä huomattavasti yksinkertaisempia, esim. suorakaiteita.

Spatiaalisten tietotyyppien indeksoinnissa voidaan käyttää R-puuta tai sen muunnelmia [Kub01]. R-puu on rakenteeltaan tasapainotettu puu ja se jakaa tilan suorakaiteisiin, jotka voivat olla päällekkäisiä. R-puun jokainen solmu on ns. rajaava suorakaide (bounding box), joka sisältää kaikki kyseisen solmun alapuun solmut. Jokainen puun lehtisolmu sisältää osoittimen varsinaiseen spatiaaliseen tieto-olioon.

Spatiaaliset relaatiot

Spatiaaliset relaatiot, ns. naapurustorelaatiot (neighbourhood relations), jakautuvat kolmeen perustyyppiin: topologisiin relaatioihin (topological relations), etäisyysrelaatioihin (distance relations) ja suuntarelaatioihin (direction relations) [EKS01]. Yhdistelemällä näitä perusrelaatioita loogisilla operaattoreilla voidaan määritellä monimutkaisempia spatiaalisia relaatioita.

Spatiaalisten naapurien etsiminen tietokannasta on hidas operaatio johtuen spatiaalisten kohteiden monimutkaisuudesta. On ehdotettu, että varsinaisten spatiaalisten kohteiden käsittelemisen sijasta käsiteltäisiin ns. naapurustokaavioita, jotka on tallennettu erilliseen naapurustoindeksiin (neighbourhood index) [EKS01]. Jokainen naapurustoindeksin rivi sisältää spatiaalisen olioparin sekä niiden välisen relaation.

Spatiaalisen tiedon louhintajärjestelmän arkkitehtuuri

Tiedonlouhintajärjestelmä voidaan käsittää useasta ohjelmistokomponentista koostuvaksi mahdollisimman pitkälle automatisoiduksi järjestelmäksi, joka sisältää seuraavat peruskomponentit: ohjain (controller), tietokantaliittymä (database interface), tietämyskanta (knowledge base), kohdistus (focus), kuvioiden etsintä (pattern extraction) ja arviointi (evaluation) [MCP93].

Käsiteltävä tieto noudetaan tietokannasta tietokantaliittymässä luotujen kyselyjen (queries) avulla. Tietokantaliittymän toteutus on keskeisessä asemassa tehokkaan tiedonlouhinnan kannalta [EKX95]. Spatiaalisia kyselyitä voidaan tehostaa käyttämällä edellä kuvattuja spatiaalisia indeksirakenteita, kuten R-puita.

Spatiaalisen tiedon louhintajärjestelmän toteutustavaksi on ehdotettu spatiaalisten tietorakenteiden ja operaatioiden liittämistä olemassa olevaan ns. laajennettavaan (extensible) tietokannanhallintajärjestelmään  [Güt94]. Tällaista ratkaisua kutsutaan integroiduksi arkkitehtuuriksi (integrated architecture).

Arkkitehtuurissa, jossa ei-spatiaalinen tieto sijaitsee tavallisissa tietokantarelaatioissa ja spatiaalinen tieto spatiaalisissa tietorakenteissa kutsutaan SAND-arkkitehtuuriksi (Spatial And Non-spatial Data) [AS91]. SAND-arkkitehtuurissa spatiaalisten ja ei-spatiaalisten tietojen välillä ylläpidetään kaksisuuntaista viittauksia.

GeoMiner

GeoMiner on DBMiner-nimisen relaatiotietokantapohjaisen tiedon louhintajärjestelmän laajennukseksi kehitetty järjestelmä spatiaalisen tiedon louhimiseen [JKS97]. GeoMiner perustuu monikomponenttiarkkitehtuuriin, ja spatiaalisen tiedon tallennuksessa käytetään SAND-arkkitehtuuria. GeoMiner sisältää mm. graafisen käyttöliittymän vuorovaikutteiseen tietojen louhintaan, joukon erilaisiin tiedon louhintatehtäviin tarkoitettuja moduuleja ja spatiaalisen tiedon louhintaan tarkoitetun kyselykielen, GMQL:n.


Lähteet

AS91                Aref, W. G., Samet, H., Optimization strategies for spatial query processing. Proc. 17th international conference on very large databases (VLDB), Barcelona, Spain, 1991. 81-90.

EKS01              Ester, M., Kriegel, H., Sander, J., Algorithms and applications for spatial data mining. Geographic Data Mining and Knowledge Discovery, Research Monographs in Geographic Information Systems, Taylor and Francis, 2001.

EKX95             Ester, M., Kriegel, H., Xu, X., Knowledge discovery in large spatial databases: focusing techniques for efficient class identification. Proc. 4th international symposium on large spatial databases (SSD’95), Berlin, 1995. 67-82.

Güt94               Güting, R. H., An introduction to spatial database systems. VLDB Journal, Special issue on spatial database systems, 3(4), 1994. 357-399.

JKS97              Jiawei, H., Koperski, K., Stefanovic, N., GeoMiner: a system prototype for spatial data mining. Proc. ACM SIGMOD international conference on management of data, Arizona, 1997. 553-556.

Kub01              Kuba, P., Data structures for spatial data mining. FI MU report series, Masaryk University, 2001.

LHO93             Lu, W., Jiawei, H., Ooi, B. C., Discovery of general knowledge in large spatial databases. Proc. Far East workshop on geographic information systems, Singapore, 1993. 275-289.

MCP93             Matheus, C. J., Chan, P. K., Piatetsky-Shapiro, G., Systems for knowledge discovery in databases. IEEE transactions on knowledge and data engineering, 5(6), 1993. 903-913.