Advisor: Dr. Chris Pollett

Description:

This is a modified proposal presnted due to the fact that Predator and Shore seem to now require incompatible and obsolete versions of gcc.

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 build a stripped-down educational test version of a native XML database with features that allows user to insert, load, update, delete from the XML tree structure. This database can then be used to test the Recovery Manager techniques implemented in NATIX. For my CS298, I will implement ARIES and the NATIX extensions given in the research paper "The Core Technologies for Native XML Database Management System" [Kan03] in my toy database.

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. Make a simple DML for our toy XML database

3. Create overall structure for XML database

4. Code for CREATE DATABASE, CREATE XMLDOC, DROP DATABASE, DROP XMLDOC, LOAD, printTree(), UPDATE, SELECT, INSERT, UPDATE

5. 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