Tietokantaoperaatioiden esittäminen automaateilla
Lähteenmäki, Marika (2022)
Lähteenmäki, Marika
2022
Matematiikan maisteriohjelma - Master´s Programme in Mathematics
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2022-11-17
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202210247777
https://urn.fi/URN:NBN:fi:tuni-202210247777
Tiivistelmä
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.
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.