Chris Pollett > Students >

    ( Print View )


    [Project Blog]











    [Source code-ZIP]


CS297 Proposal

Schemes to make Aries and XML work in harmony

Thien An Nguyen (

Advisor: Dr. Chris Pollett


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.


Week 1 & 2: Jan. 29 - Feb 121. Read "The Core Technologies for Native XML Database Management System" [Kan03]

2. Read "ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging" [Mohan90]

3. Read Shore Storage Manager architecture

Week 3: Feb. 19Deliverable 1: Install Shore SM
Week 4 & 5: Mar. 4

1. Read PREDATOR System Design Document: A detailed description of internal design decisions and implementation details

2. Read PREDATOR User Manual and Tutorial: A tutorial of the user of the system, along with interactive examples.

3. Read PREDATOR, Design and Implementation [Seshadri97].

Week 6: Mar. 11Deliverable 2: Install PREDATOR v2.1 for Windows (on top of Shore SM )
Week 7 & 8: Mar. 25

Study Predator's recovery code. Class hierachy

Read "ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes" [Mohan92]

Week 9: Apr 1Spring Break
Week 10: Apr. 15

Read "Recovery Protocols for Shared Memory Database Systems" [Molesky95]

Deliverable 3: Writing Testcases/jobs that go through transaction abort/restart recovery

Week 11: Apr. 22 Deliverable 4: Result for transaction rollback/abort
Week 12 & 13: May 6Deliverable 5: Result for Restart Recovery
Week 14 & 15: May 20Deliverable 6: Final Report


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


[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:

Predator source code available at