Tietokantaoperaatioiden esittäminen automaateilla

Abstract

Tietokanta on järjestäytynyt kokoelma jäsentynyttä tietoa, joka on tyypillisesti varastoitu tietojärjestelmään. Tutkielmassa ollaan kiinnostuneita tällaisen tietokannan taulujen operaatioista. Automaattiteoria taas on tietojenkäsittelytieteiden ja matematiikan haara, joka tutkii laskennan matemaattista abstraktia mallia. Tutkielman tavoitteena on tarkastella tietokantaoperaatioiden esittämistä äärellisillä automaateilla. Operaatioiksi valittiin projektio, yhdiste, leikkaus, liitos, karteesinen tulo sekä komplementti. Esitellään ensin tarvittavaa automaattiteorian käsitteistöä deterministisistä ja epädeterministisistä äärellisistä automaateista, sekä automaatin hyväksymästä kielestä ja vakiomittaisesta kielestä. Tarkastellaan automaattien erilaisia ominaisuuksia kuten täydellinen automaatti, tyhjiä siirtymiä sisältävien epädeterminististen automaattien tyhjiä sulkeumia ja tyhjien siirtymien poistamista sekä automaattien tasojen käsitettä ja määritellään zip-automaatin muunnelma tietokannan taulun rakennetta edustamaan. Esitellään tietokannan operaatiot projektio, yhdiste, leikkaus, liitos, karteesinen tulo sekä komplementti määritelmien ja esimerkkien avulla.

Automaateille määriteltävät operaatiot ovat edellä mainitut tietokannan operaatiot, joita käsitellään määritelmien, lauseiden, algoritmien sekä esimerkkien kautta. Yhdiste ja leikkaus ovat vastaavia kuin automaattien tavanomaiset yhdiste- ja leikkausoperaatiot. Projektion käsittelyyn on otettu avuksi automaatin tasojen käsite. Liitos on yksinkertaistettu tietokannan taulun yhden sarakkeen vastaavuuden mukaiseksi liitosoperaatioksi. Karteesinen tulo on yksinkertaistettu tyhjien siirtymien avulla. Komplementti on usean vaiheen kautta rakentuva automaatti, joka vastaa tietokannan taulun sisällön komplementtia. Lopuksi tarkastellaan automaattien operaatioiden ja niiden algoritmien kompleksisuuksia.