Browsing by Author "Saari, Joona"

Tässä tutkielmassa syvennytään tietokannoista tuttuun relaatiomalliin ja tarkemmin sille annettuihin rajoituksiin, riippuvuuksiin. Erityisesti syvennytään tavanomaista funktionaalista riippuvuutta erikoisempiin moniarvoiseen ja sulautettuun moniarvoiseen riippuvuuteen (MVD- ja EMVD-riippuvuudet). Tämä tehdään matemaattisen formaalista näkökulmasta: todistetaan, että riippuvuudelle on mahdollista antaa eheä ja täydellinen aksiomatisointi. Tämä antaa erään vastauksen riippuvuuksille annettuun implikaatio-ongelmaan. Ensimmäisessä luvussa esitellään relaatiomalli. Malli koostuu riveistä ja sarakkeista. Rivit usein kuvaavat erilaisia entiteettejä, sarakkeet erilaisia ominaisuuksia. Malli sallii erilaisten riippuvuuksien asettamisen entiteettien ominaisuuksien välille. Yksinkertainen joukko entiteettejä voi olla esimerkiksi lista henkilötietoja. Toisessa luvussa esitellään riippuvuudet sekä eheys- ja täydellisyystodistukset. Moniarvoinen riippuvuus tarkoittaa riippuvuutta, jossa yksittäinen ominaisuus määrää sen, että jokin ominaisuus on riippumaton muista ominaisuuksista. Henkilötietolistassa, jossa on ominaisuuksina henkilön nimi ja tämän perheenjäsenen nimi, sekä riveinä luetteloitu henkilöiden perheenjäsenet, yksittäinen henkilö määrää riippumattomuuden perheenjäsenen nimen ja kyseisen henkilön välille. Moniarvoiselle riippuvuudelle annetaan yhdessä funktionaalisen riippuvuuden kanssa aksiomatisointi, joka todistetaan eheäksi ja täydelliseksi. Eheys ja täydellisyys todistetaan myös molemmille riippuvuuksille yksin. Rinnakkainen käsittely antaa mahdollisuuden riippuvuuksien syvälliseen vertailuun. Täydellisyystodistuksien argumentit rakentuvat vastaesimerkin ja ristiriitatodistuksen varaan. Konstruoidaan erityinen mm. Boolen algebran ominaisuuksia hyödyntävä relaatioskeema sekä relaatio ja osoitetaan, että näissä kaikki epäsuotuisat tapaukset ajautuvat ristiriitaan. Kolmannessa luvussa esitellään sulautettu moniarvoinen riippuvuus. Se poikkeaa moniarvoisesta riippuvuudesta hiukan: yksittäinen ominaisuus määrää sen, että jokin ominaisuus on riippumaton toisesta ominaisuudesta. Sulautetulle moniarvoiselle riippuvuudelle annetaan muutama eheä aksiooma. Todistetaan, että tälle riippuvuudelle ei löydy täydellistä aksiomatisointia. Tämän todistuksen argumentti rakentuu sille, että konstruoidaan ääretön määrä aksioomia, jotka ovat aina eheitä mutta eivät koskaan degeneroidu muiksi aksioomiksi. Tällä todistetaan se, että nämä aksioomat ilmaisevat aina jotain, mitä ei ole muunlaisilla aksioomilla mahdollista ilmaista ja näin ollen sulautettua moniarvoista riippuvuutta ei voi aksiomatisoida äärellisellä määrällä aksioomia. Aksioomien degeneroitumattomuus osoitetaan vastaesimerkkien avulla osoittamalla, että ei ole mahdollista, että aksiooman etujäsenet olisivat tosia ja näiden lisäksi jokin epätriviaali takajäsenestä poikkeava seuraus olisi tosi.