Tietokantajärjestelmät spatiaalisen tiedon louhinnassa
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, 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.
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.