Advisor: Dr. Chris Pollett

Description:

ARIES (Algorithms for Recovery and Isolation Exploiting Semantics) - family of locking, logging and recovery algorithms for persistent data management. All updates of a transaction are logged, including those performed during rollbacks. By appropriate chaining of the log records written during rollbacks to those written during forward progress, a bounded amount of logging is ensured during rollbacks even in the case of repeated failures during restart or of nested rollbacks. [Mohan90] ARIES is designed around the redo history paradigm, that is, during the redo phase, database sub-system redo all updates even with loser transactions.

NATIX, a native XML database management system has been recently developed (from scratch), introduce the novice of subsidiary logging and annihilator undo. Suppose a record is updated multiple times by the same transaction i.e. when a sub-tree is added node by node multiple times. In such case, the log size would be reduced if we log only the composite update operation as one operation. It is called subsidiary logging. Undo operations that imply undo of other operations following them in the log is called annihilators. To improve the performance in XML context, annihilator undo skips undo operations implied by the annihilators. For example, update operation(s) to a record that has been created by the same transaction doesn't need to be undone when the transaction is aborted because the record will be deleted anyway.[Kan03] Natix, on the other hand, supports selective redo and selective undo to accelerate restart recovery.

The goal that I want to accomplish in this CS297 is to study the structure of an open source, object database that implements ARIES, and experiments with the log records to simulate transaction rollback/abort and transaction restart recovery. We chose PREDATOR because PREDATOR is an object-relational database system that was built on top of the SHORE (Scalable Heterogeneous Object REpository) storage manager under development at the University of Wisconsin (also publicly available software) - a persistent object storage engine that supports creation of persistent files and records. Records can range from a few bytes to megabytes or larger. Records can be retrieved by object identifier or by scanning files. Shore supports log-based recovery based on ARIES mechanism [Venkatarman96]. My intention in CS298 is to implement subsidiary logging, annihilator undo, and selective redo/undo on top of Predator.

Schedule:

Deliverables:

The full project will be done when CS298 is completed. The following will be done by the end of CS297:

1. Install SHORE storage manager up running on windows 2000

2. Install PREDATOR on top of Shore

3. 2 testcases/jobs that go through rollback/abort, and restart recovery code path (maybe combines with breakpoint in the source code)

4. Results of transaction rollback/abort after added log records.

5. Results of restart recovery after added log records.

6. Final report

References:

[Kan03] Core Technologies for Native XML Database Management System. Carl-Christian Kanne. Mannheim. 2003.

[Mohan90] ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh, P. Schwarz. ACM Transactions on Database Systems, 1990.

[Seshadri97] PREDATOR: An OR-DBMS with Enhanced Data Types. P. Seshadri, M. Paskin. SIGMOD, 1997, p. 568-571.

[Venkatarman96] Global Memory Management for Multi-server Database Systems. S. Venkatarman. University of Wisconsin - Madison, 1996.

[Mohan92] ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. C. Mohan. In Proc. of the 12th International Conference on Distributed Computing Systems, Yokohama, 1992.

[Mohan99] Repeating History Beyond ARIES. C. Mohan. Proc. 25th International Conference on Very Large Data Bases, Edinburgh, 1999.

[Molesky95] Recovery Protocols for Shared Memory Database Systems. L. Molesky, K. ramamritham. ACM, 1995.

[Lahiri01] Fast-Start: Quick Fault Recovery in Oracle. T. Lahiri, A. Ganesh, R. Weiss, A. Joshi. ACM SIGMOD, 2001.

[Mohan93] ARIES/LHS: A Concurrency Control and Recovery Method Using Write-Ahead Logging for Linear Hashing with Separators. C. Mohan. Proceedings of the 9th IEEE International Conference on Data Engineering, 1993.

Shore SM source code available at: ftp://ftp.cs.wisc.edu/shore/current/

Predator source code available at http://www.distlab.dk/predator/download.htm