A theory of transactions on recoverable search trees

Seppo Sippu, Eljas Soisalon-Soininen

    Forskningsoutput: Kapitel i bok/rapport/konferenshandlingKonferensbidragVetenskapligPeer review

    Sammanfattning

    We consider transactions running on a database that consists of records with unique totally-ordered keys and is organized as a sparse primary search tree such as a B-tree index on disk storage. We extend the classical read-write model of transactions by considering inserts, deletes and key-range scans and by distinguishing between four types of transaction states: forward-rolling, committed, backward-rolling, and rolled- back transactions. A search-tree transaction is modelled as a two-level transaction containing structure modifications as open nested subtransactions that can commit even though the parent transaction aborts. Isolation conditions are defined for search-tree transactions with nested structure modifications that guarantee the structural consistency of the search tree, a required isolation level (including phantom prevention) for database operations, and recoverability for structure modifications and database operations.
    Bidragets titel på inmatningsspråkElpyviin hakupuihin kohdistuvien transaktioiden teoria
    Originalspråkengelska
    Titel på gästpublikationDatabase Theory – ICDT 2001 : 8th International Conference, London, UK, January 4-6, 2001 Proceedings
    RedaktörerJean Van den Bussche, Victor Vianu
    Antal sidor16
    UtgivningsortBerlin-Heidelberg-New York
    FörlagSpringer-Verlag
    Utgivningsdatum2001
    Sidor83-98
    ISBN (tryckt)3-540-41456-8
    DOI
    StatusPublicerad - 2001
    MoE-publikationstypA4 Artikel i en konferenspublikation
    EvenemangInternational Conference on Database Theory (ICDT) - London, Storbritannien
    Varaktighet: 4 jan 20016 jan 2001
    Konferensnummer: 8

    Publikationsserier

    NamnLecture Notes in Computer Science
    FörlagSpringer-Verlag
    Volym1973
    ISSN (tryckt)0302-9743

    Vetenskapsgrenar

    • 113 Data- och informationsvetenskap

    Citera det här