Seminaari: Versioivat tietokantarakenteet

Pääteemat ja oppimistavoitteet »
58310305
3
Ohjelmistojärjestelmät
Syventävät opinnot
Vuosi Lukukausi Päivämäärä Periodi Kieli Vastuuhenkilö
2010 syksy 06.09-06.12. 1-2 Suomi

Luennot

Aika Huone Luennoija Päivämäärä
Ma 12-14 C220 Seppo Sippu 06.09.2010-11.10.2010
Ma 12-14 C220 Seppo Sippu 01.11.2010-29.11.2010
Ti 12-14 C220 Seppo Sippu 07.12.2010-07.12.2010

Yleistä

Perinteistä tietokantaa voidaan luonnehtia termein tilannevedostietokanta (snapshot database) tai yhden version tietokanta (single-version database) siinä mielessä, että se tarjoaa sovelluksille kustakin tietokantaan tallennettavasta tietoalkiosta vain yhden version, nimittäin tuoreimman. Tietoalkion päivitys hävittää vanhan version, joka ei tietoalkiota päivittäneen transaktion sitouduttua ole enää käyttäjien sovellusten saatavilla. Tietokannan hallintajärjestelmä tallentaa kylläkin tietoalkioiden vanhoja versioita lokitiedostoon ja varmuusnauhoille, mutta tämä tehdään ainoastaan tietokannan elvytys- ja varmistustarkoituksia varten eikä vanhan tietoalkion esillesaanti sitä kautta ole tehokasta eikä sitä varten edes ole standardoitua liittymää.

Järjestelmissä, joissa transaktioiden samanaikaisuuden hallinta perustuu tietoalkioiden versiointiin, pidetään transaktioiden saatavilla tuoreimman tietoalkioversion lisäksi jonkin aikaa myös tätä edeltäviä versioita, niin että transaktiolle voidaan tarjota luettavaksi lukkoja varaamatta ennen transaktion alkamista sitoutunut tuorein versio. Tässäkään tapauksessa ei sovellus voi päästä käsiksi kaikkiin vanhoihin versioihin, eikä luettava tai päivitettävä versio ole sovelluksen määrättävissä.

Monet modernit sovellukset vaativat kuitenkin pääsyä tietoalkion koko versiohistoriaan, jonka silloin pitäisi siis olla pysyvästi käyttäjien transaktioiden saatavilla. Teollisuuden suunnittelusovelluksissa on tarpeen säilyttää tuotesuunnitelman eri versioita. Varastonvalvontasovelluksissa täytyy olla mahdollista tutkia varaston aiempia tiloja. Liiketoimintakriittinen sovellus edellyttää usein mahdollisuutta jäljittää tietoalkion päivityshistoriaa taaksepäin, mitä tavanomaisessa tilannevedostietokannassa joudutaan simuloimaan herättimin aktivoitavin toimenpitein, joilla kriittisen tietoalkion päivityshistoriaa tallennetaan erityiseen sovellukselle näkyvään lokitauluun.

Versioivassa tietokannassa (multiversion database) jokaisen tietoalkion koko versiohistoria on näkyvissä loogisen tietokannan tasolla ja siis tietokantaa käyttävien sovellusten operoitavissa. Kun tilannevedostietokannassa yksittäinen tietoalkio on monikko (k,w), missä k on tietoalkion yksilöivä avainarvo ja w tietoalkion muiden attribuuttien arvot, niin versioivassa tietokannassa avainarvolla k varustettua tietoalkiota vastaa sen versiohistoria (k,v1,w1), (k,v2,w2), ..., (k,vn,wn), missä v1, v2, ..., vn ovat versionumeroita (tyypillisesti tietoalkiota päivittäneiden transaktioiden aikaleimoja) ja w1, w2, ..., wn tietoalkion attribuuttiarvoja vastaavissa versioissa.

Tilannevedostietokannassa annetulla avainarvolla k varustettu tietoalkio tai annetulle avainarvovälille [k1,k2] sijoittuvat tietoalkiot voidaan tehokkaasti hakea esille avaimen mukaan järjestetyn B-puuhakemiston (B-tree index) avulla, niin että haku on lineaarista avainvälin [k1,k2] tietoalkioiden lukumäärään ja hakemistopuun korkeuteen nähden (missä korkeus on logaritminen kaikkien tietoalkioiden lukumäärään nähden). Versioivassa tietokannassa tietoalkioiden versionumerot tuovat tietokantarakenteeseen ja tietokantahakuihin yhden dimension lisää: täytyy olla mahdollista hakea tehokkaasti annetulle avainvälille [k1,k2] sijoittuvat tietoalkiot annetusta tietokantaversiosta v tai annetulle versiovälille [v1,v2] sijoittuvat, annetulla avainarvolla k varustetut tietoalkioversiot. Tähän tarkoitukseen ei avainarvoparien (k,v) tai (v,k) mukaan järjestetty tavanomainen B-puuhakemisto ole riittävän tehokas.

Kirjallisuudessa on esitetty erilaisia ratkaisuja versioivan tietokannan indeksointiin. Näistä mainittakoon erityisesti Beckerin ja kumppaneiden versioiva B-puu (multiversion B-tree) sekä Lometin ja Salzbergin aikahalkaisu-B-puu (time-split B-tree) eli TSB-puu (TSB-tree) ja tämän toteutus osana ImmortalDB-järjestelmää.

Seminaarissa selvitetään versioivan tietokannan käsitteistöä, sovelluksia ja hallintamenetelmiä. Pääpaino on versioivan tietokannan hakemistorakenteissa. Aiheeseen voi perehtyä etukäteen esimerkiksi lukemalla Salzbergin ja kumppanien artikkelin ''A framework for access methods for versioned data'' (EDBT 2004, 730–747).

Seminaarin järjestäytymistilaisuuden esitelmä on saatavilla laitoksen sisäverkossa.

Esitietoina edellytetään Kandidaatin tutkielma (Tieteellisen kirjoittamisen kurssi) sekä Tietokannan suunnittelu.

Seminaarin aikataulusta sovittiin järjestäytymistilaisuudessa.

Kurssin suorittaminen

Seminaarille on varattu sali C220 ma klo 12–14 ajalle 6/9–11/10 ja 1–29/11 sekä 7/12 ti 12–14. Seminaari alkaa 6/9 2010 pidettävällä järjestäytymistilaisuudella, jossa kiinnitetään lopullisesti kunkin oppilaan seminaariesitelmän aihe sekä sovitaan tarkemmin seminaarin työskentelyaikataulusta.

Kukin oppilas laatii esitelmäaiheestaan kirjallisen seminaariraportin, jonka tulee muodoltaan noudattaa Tieteellisen kirjoittamisen kurssilla annettuja ohjeita. Raportti sisältää kansilehden, tiivistelmäsivun, sisällysluettelon, johdantoluvun, varsinaiset luvut, yhteenvetoluvun ja lähdeluettelon. Raportin varsinaisen sisällön eli johdantoluvun, varsinaisten lukujen, yhteenvetoluvun ja lähdeluettelon yhteinen pituus on noin 12 sivua.

Alla olevan esitelmäaiheluettelon kunkin aiheen yhteydessä on annettu pari kolme keskeistä lähdeviitettä, joihin seminaariraportin ja -esitelmän pääsisällön voi perustaa tai joita voi käyttää lähtökohtana aiheeseen liittyvää lähteistöä hakiessa. Raportille ja esitelmälle on eduksi, jos sen sisältöä on koottu useammasta lähteestä; viittauksia pitää olla aina useaan aihetta tai sen taustaa käsittelevään lähteeseen.

Kukin oppilas pitää aiheestaan kaksi suullista esitystä, joista ensimmäisessä, 15–20 minuuttia kestävässä esityksessä esitellään lyhyesti aihetta ja seminaariraportin jäsennystä. Tämä lyhyt esitys pidetään kolmen tai neljän viikon kuluttua järjestäytymistilaisuudesta. Pitempi, noin tunnin mittainen esitelmä pidetään lukukauden toisen periodin aikana seminaariraportin valmistuttua. Esitykset pidetään video- tai piirtoheitintä käyttäen.

Valmis seminaariraportti toimitetaan viikkoa ennen esitelmätilaisuutta sähköpostitse pdf-muotoisena liitetiedostona seminaarin ohjaajalle seminaarin verkkosivulle sijoitettavaksi. Vaihtoehtoisesti oppilas voi laittaa raportin pdf-muotoisena omalle verkkosivulleen ja toimittaa ohjaajalle tiedoksi linkin kyseiseen tiedostoon.

Esitelmätilaisuudessa saamansa palautteen perusteella oppilas toimittaa raportistaan korjatun version 13/12 2010 mennessä.

Seminaarissa on läsnäolovelvoite. Poissa saa olla korkeintaan kaksi kertaa.

Seminaarisuoritus arvostellaan skaalalla 0/5 (hylätty), 1/5, 2/5, 3/5, 4/5, 5/5. Arvosteluun vaikuttavat seuraavat tekijät (tärkeysjärjestyksessä): (1) kirjallisen raportin ja suullisten esitysten perusteella osoitettu oman esitelmäaiheen hallinta (suhteessa aiheen vaikeuteen), (2) kirjallisen raportin sisältö ja muoto, (3) suullisten esitysten (erityisesti pitemmän esitelmän) sisältö ja muoto, (4) osallistuminen yleiseen keskusteluun ja siinä osoitettu perehtyminen muiden osallistujien esitelmäaiheisiin sekä (5) läsnäolokerrat.

Kirjallisuus ja materiaali

Tarjolla on allamainitut esitelmäaiheet. Aiheen voi varata etukäteen. Oppilas voi myös esittää omaa aihetta.

  1. Tietokantojen aikakäsitteistä ja historiakyselytyypeistä. R. T. Snodgrass and I. Ahn: A taxonomy of time in databases. Proc. of the 1985 ACM SIGMOD Internat. Conf. on Management of Data, 236–246. B. Salzberg and V. J. Tsotras: Comparison of access methods for time-evolving data. ACM Computing Surveys 31:2 (1999), 158–221 (erit. sivut 158–175).
  2. Ajan mukaan ryvästävä versiointi. R. Elmasri, G. T. J. Wuu and Y.-J. Kim: The time index: an access structure for temporal data. Proc. of the 16th Internat. Conf. on Very Large Data Bases, 1990, 1–12. V. J. Tsotras and N. Kangelaris: The snapshot index: an I/O-optimal access method for timeslice queries. Information Systems 20:3 (1995), 237–260. B. Salzberg and V. J. Tsotras: Comparison of access methods for time-evolving data. ACM Computing Surveys 31:2 (1999), 158–221 (erit. kohta ''Time-only methods'' sivuilla 177–189).
  3. Kertakirjoittuvaan levyyn ja moniulotteiseen hakemistorakenteeseen perustuva versiointi. C. P. Kolovson and M. Stonebraker: Indexing techniques for historical databases. Proc. of the 5th IEEE Internat. Conf. on Data Engineering, 1989, 127–137. A. Guttman: R-trees: a dynamic index structure for spatial searching. Proc. of the 1984 ACM SIGMOD Internat. Conf. on Management of Data, 47–57. B. Salzberg and V. J. Tsotras: Comparison of access methods for time-evolving data. ACM Computing Surveys 31:2 (1999), 158–221 (erit. kohta ''R-tree-based methods'' sivuilla 190–194).
  4. Aika- eli versiohalkaisut avaimen ja ajan mukaan ryvästävässä versioinnissa. D. B. Lomet and B. Salzberg: Access methods for multiversion data. Proc. of the 1989 ACM SIGMOD Internat. Conf. on Management of Data, 315–324. D. B. Lomet and B. Salzberg: The performance of a multiversion access method. Proc. of the 1990 ACM SIGMOD Internat. Conf. on Management of Data, 353–363. B. Salzberg and V. J. Tsotras: Comparison of access methods for time-evolving data. ACM Computing Surveys 31:2 (1999), 158–221 (erit. kohta ''Time-split B-tree'' sivuilla 196–199). B. Salzberg, L. Jiang, D. B. Lomet, M. Barrena Garcia, J. Shan and E. Kanoulas: A framework for access methods for versioned data. Advances in Database Technology, Proc. of the 9th Internat. Conf. on Extending Database Technology, 2004, 730–747.
  5. Avainvälikyselyiden suhteen optimaalinen versioiva B-puu. B. Becker, S. Gschwind, T. Ohler, B. Seeger and P. Widmayer: On optimal multiversion access structures. Advances in Spatial Databases, Proc. of the 3rd Internat. Symp., 1993, 123–141. B. Becker, S. Gschwind, T. Ohler, B. Seeger and P. Widmayer: An asymptotically optimal multiversion B-tree. The VLDB Journal 5:4 (1996), 264–275. J. Van den Bercken and B. Seeger: Query processing techniques for multiversion access methods. Proc. of the 22th Internat. Conf. on Very Large Data Bases, 1996, 168–179. B. Salzberg and V. J. Tsotras: Comparison of access methods for time-evolving data. ACM Computing Surveys 31:2 (1999), 158–221 (erit. kohta ''Multiversion B-tree and multiversion access structure'' sivuilla 205–208).
  6. Transaktioajan hallinta tietokantapalvelimessa. C. S. Jensen and D. B. Lomet: Transaction timestamping in (temporal) databases. Proc. of the 27th Internat. Conf. on Very Large Data Bases, 2001, 441–450. D. B. Lomet, R. S. Barga, M. F. Mokbel, G. Shegalov, R. Wang and Y. Zhu: Immortal DB: transaction time support for SQL server. Proc. of the 2005 ACM SIGMOD Internat. Conf. on Management of Data, 939–941. D. B. Lomet, R. S. Barga, M. F. Mokbel, G. Shegalov, R. Wang and Y. Zhu: Transaction time support inside a database engine. Proc. of the 22nd Internat. IEEE Conf. on Data Engineering, 2006. D. B. Lomet, M. Hong, R. V. Nehme and R. Zhang: Transaction time indexing with version compression. Proc. of the VLDB Endowment 1:1 (2008), 870–881. D. B. Lomet and F. Li: Improving transaction-time DBMS performance and functionality. Proc. of the 25th Internat. IEEE Conf. on Data Engineering, 2009.
  7. Haarautuvien versiohistorioiden hallinta. S. Lanka and Eric Mays: Fully persistent B+-trees. Proc. of the 1991 ACM SIGMOD Internat. Conf. on Management of Data, 426–435. G. M. Landau, J. P. Schmidt and V. J. Tsotras: Historical queries along multiple lines of time evolution. The VLDB Journal 4:4 (1995), 703–726. L. Jiang, B. Salzberg, D. B. Lomet and M. Barrena Garcia: The BTR-tree: path-defined version-range splitting in a branched and temporal structure. Advances in Spatial and Temporal Databases, Proc. of the 8th Internat. Symp., 2003, 28–45. K. Jouini and G. Jomier: Indexing multiversion databases. Proc. of the 16th ACM Conf. on Information and Knowledge Management, 2007, 915–918.
  8. Fyysisen tietokannan pitkäikäiset tilannevedokset. L. Shrira and H. Xu: SNAP: efficient snapshots for back-in-time execution. Proc. of the 21st Internat. IEEE Conf. on Data Engineering, 2005, 434–445. R. Shaull, L. Shrira and H. Xu: Skippy: enabling long-lived snapshots of the long-lived past. Proc. of the 24th Internat. IEEE Conf. on Data Engineering, 2008, 1474–1476. R. Shaull, L. Shrira and H. Xu: Skippy: a new snapshot indexing method for time travel in the storage manager. Proc. of the 2008 ACM SIGMOD Internat. Conf. on Management of Data, 637–648.