Rules for Transforming Order Dependent Transaction into Order Independent Transaction
A transaction is a collection of operations that performs a single logical function in a database application. Each transaction is a unit of both atomicity and consistency. Thus, transactions are required not to violate any database consistency constraints. In most cases, the update operations in a transaction are executed sequentially. The effect of a single operation in a transaction potentially may be changed by another operation in the same transaction. This implies that the sequential execution sometimes does some redundant work. A transaction with a set of update operations is order dependent if and only if the execution of the transaction following the serialibility order as in the transaction produce an output which will be different from the output produced by interchanging the operations in the transaction. Otherwise, the transaction is order independent [8]. In this paper, we present rules that can be applied to generate order independent transaction given an order dependent transaction. An order independent transaction has an important advantage of its update statements being executed in parallel without considering their relative execution orders. With an order independent transaction, we can consider its single updates in an arbitrary order. Furthermore, executing transaction in parallel can reduce the execution time .
[1] Chakravarthy U. S., Grant J., and Minker J., “Logic-Based Approach to Semantic Query Optimization,” ACM TODS, vol. 15, no. 2, pp. 162-207, 1990.
[2] Christof H. and Gerhard W., “Inter- and Intra- Transaction Parallelism in Database Systems,” in Proceedings of the 14th Speedup Workshop on Parallel and Vector Computing , Zurich, Switzerland, 1993.
[3] Connolly T. M. and Begg C. E., Database Systems: A Practical Approach to Design , Implementation and Management, Addison- Wesley, 2002.
[4] Ibrahim, H., “Extending Transactions with Integrity Rules for Maintaining Database Integrity,” in Proceedings of the International Conference on Information and Knowledge Engineering (IKE’02) , in Arabnia H. R., Mun Y., and Prasad B. (Eds), Computer Science Research, Education and Application Technical (CSREA) Press, Las Vegas, USA, pp. 341-347, 2002.
[5] McCaroll N. F., “Semantic Integrity Enforcement in Parallel Database Machines,” PhD Thesis, University of Sheffield, Sheffield, UK, 1995
[6] Michael R., Moira C. N., and Hans-Jorg S., “Intra-Transaction Parallelism in the Mapping of an Object Model to a Relational Multi-Processor System,” in Proceedings of the 22nd Very Large Databases (VLDB) Conference , Bombay, India, pp. 1-12, 1996.
[7] ODS Group, “ A Reader in Transaction Processing ,” http://www.cs.uit.no/forskning/ ODS/ODSProjects/adtrans/ReaderTrans.html.
[8] Sang H. L., Lawrence J. H., Myoung H. K., and Yoon-Joon L., “Enforcement of Integrity Constraints against Transactions with Transition Axioms,” in Proceedings of the 16th. Annual International Computer Software and Applications , pp. 162-167, 1992.
[9] Shasha D., Llirbat F., Simon E., and Valduriez P., “Transaction Chopping: Algorithms and Performances Studies,” Journal of ACM Transaction Database Systems , vol. 20, no. 3, pp. 325-363, 1995.
[10] Sushil J., Indrakshi R., and Paul A., “Implementing Semantic-Based Decomposition of Transactions,” in Proceedings of CAiSE'1997, pp. 75-88, 1997.
[11] Wang X. Y., “The Development of a Knowledge- Based Transaction Design Assistant,” PhD Thesis , University of Wales College of Cardiff, Cardiff, UK, 1992. Hamidah Ibrahim is currently an associate professor at the Faculty of Computer Science and Information Technology, Universiti Putra Malaysia. She obtained her PhD in computer science from the University of Wales Cardiff, UK in 1998. Her current research interests include distributed databases, transaction processing, and knowledge- based systems.