Portal de Periódicos da CAPES

A Theory of Transactions on Recoverable Search Trees

2001; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-44503-x_6

1611-3349

Seppo Sippu, Eljas Soisalon-Soininen,

Advanced Data Storage Technologies

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.