Abstract
In some database applications the traditional approach of seerializability, in which transactions appear to execute atomically and in isolation on a consistent database state, fails to satisfy performance requirements. Although many researchers have investigated the process of decomposing transactions into steps to increase concurrency, such research typically focuses on providing algorithms necessary to implement a decomposition supplied by the database application developer and pays relatively little attention to what constitutess a desirable decomposition or how the developer should obtain one. We focus onthe decomposition itself. A decomposition generates proof obligations whose descharge ensures desirable properties with respect to the original collection of transactions. We introduce the notion of semantic histories to formulate and prove the necessary properties, and the notion of successor sets to describe efficiently the correct interleavings of steps. The successor set constraints use information about conflicts between steps so as to take full advantage of conflict serializability at the level of steps. We propose a mechanism based on two-phase locking to generate correct stepwise serializable histories.
- AGRAWAL, D., EL ABBADI, A., AND SINGH, A.K. 1993. Consistency and orderability: Semantics-based correctness criteria for databases. ACM Trans. Database Syst. 18, 3, (Sept.) 460-486. Google ScholarDigital Library
- ABRIAL, J.R. 1993. B-Technology Technical Overview. B-Core(UK) Ltd., Oxford, UK.Google Scholar
- AMMANN, P., JAJODIA, S., AND RAY, I. 1995. Using formal methods to reason about semantics-based decomposition of transactions. In Proceedings of the International Conference on Very Large Databases (Zurich, Switzerland, Sept.), 218-227. Google ScholarDigital Library
- ARORA, A. AND KULKARNI, S. S. 1995. Designing masking fault-tolerance via nonmasking fault-tolerance. In Proceedings of Symposium on Reliable Distributed Systems, (Bad Neuenahr, Germany, Sept.), 174-185. Google ScholarDigital Library
- BERNSTEIN, P. n., HADZILACOS, V., AND GOODMAN, N. 1987. Concurrency Control and Recovery in Database Systems. Addison-Wesley, Reading, MA. Google ScholarDigital Library
- BADRINATH, B. R. AND RAMAMRITHAM, K. 1992. Semantics-based concurrency control: Beyond commutativity. ACM Trans. Database Syst. 17, 1 (Mar.) 163-199. Google ScholarDigital Library
- CHRYSANTHIS, P. K. AND RAMAMRITHAM, K. 1994. Synthesis of extended transaction models using ACTA. ACM Trans. Database Syst. 19, 3 (Sept.), 450-491. Google ScholarDigital Library
- Du, W. AND ELMAGARMID, A.K. 1989. Quasi serializability: A correctness criterion for global concurrency control in interbase. In Proceedings of the International Conference on Very Large Databases, (Amsterdam, Netherlands), 347-355. Google ScholarDigital Library
- ELMASRI, R. AND NAVATHE, S. B. 1989. Fundamentals of Database Systems. Benjamin/ Cummings, Redwood City, CA. Google ScholarDigital Library
- FARRAG, A. A. AND OZSU, M.T. 1989. Using semantic knowledge of transactions to increase concurrency. ACM Trans. Database Syst. 14, 4 (Dec.) 503-525. Google ScholarDigital Library
- GARCIA-MOLINA, H. 1983. Using semantic knowledge for transaction processing in a distributed database. ACM Trans. Database Syst. 8, 2 (June) 186-213. Google ScholarDigital Library
- GARCIA-MOLINA, H. AND SALEM, K. 1987. Sagas. In Proceedings of ACM-SIGMOD International Conference on Management of Data, (San Francisco, CA), 249-259. Google ScholarDigital Library
- HERLIHY, M. 1987. Extending multiversion time-stamping protocols to exploit type information. IEEE Trans. Comput., 36, 4 (April), 443-448. Google ScholarDigital Library
- HERLIHY, M. P. AND WEIHL, W.E. 1991. Hybrid concurrency control for abstract data types. J. Comput. Syst. Sci. 43, 1 (Aug.) 25-61. Google ScholarDigital Library
- JAJODIA, S. AND MEADOWS, C. 1987. Managing a replicated file in an unreliable network. In Proceedings of 3rd IEEE International Conference on Data Engineering, (Los Angeles, CA, Feb.), 396-404. Google ScholarDigital Library
- KORTH, H. F., LEVY, E., AND SILBERSCHATZ, A. 1990. A formal approach to recovery by compensating transactions. In Proceedings of the International Conference on Very Large Databases, (Brisbane, Australia), 95-106. Google ScholarDigital Library
- KORTH, H. F. AND SPEEGLE, G.D. 1988. Formal model of correctness without serializability. In Proceedings of ACM-SIGMOD International Conference on Management of Data, (June), 379-386. Google ScholarDigital Library
- KORTH, H. F. AND SPEEGLE, a. 1994. Formal aspects of concurrency control in long-ouration transaction systems using the NT/PV model. ACM Trans. Database Syst. 19, 3 (Sept.), 492-535. Google ScholarDigital Library
- LEVY, E., KORTH, H. F., AND SILBERSCHATZ, A. 1991. An optimistic commit protocol for distributed transaction management. In Proceedings of the ACM-SIGMOD International Conference on Management of Data, (Denver, CO, May), 88-97. Google ScholarDigital Library
- LEVY, E., KORTH, H. F., AND SILBERSCHATZ, A. 1991. A theory of relaxed atomicity. In Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, (Aug.), 95-109. Google ScholarDigital Library
- LYNCH, N., MERRITT, M., WEIHL, W., AND FEKETE, A. 1994. Atomic Transactions. Morgan Kaufmann, San Mateo, CA.Google Scholar
- LYNCH, N.A. 1983. Multilevel atomicity--A new correctness criterion for database concurrency control. ACM Trans. Database Syst. 8, 4 (Dec.), 484-502. Google ScholarDigital Library
- OWICKI, S. AND GRIES, D. 1976. Verifying properties of parallel programs: An axiomatic approach. Commun. ACM, 19, 5 (May), 279-285. Google ScholarDigital Library
- POTTER, B., SINCLAIR, J., AND TILL, D. 1991. An Introduction to Formal Specification and Z. Prentice-Hall, New York. Google ScholarDigital Library
- RASTOGI, R., KORTH, H. F., AND SILBERCHATZ, A. 1995. Exploiting transaction semantics in multidatabase systems. In Proceedings of the International Conference on Distributed Computing Systems, (Vancouver, Canada, June), 101-109. Google ScholarDigital Library
- SHA, L., LEHOCZKY, J. P., AND JENSEN, E.D. 1988. Modular concurrency control and failure recovery. IEEE Trans. Comput., 37, 2 (Feb.), 146-159. Google ScholarDigital Library
- SPIVEY, J. M. 1992. The Z Notation: A Reference Manual, Second Edition. Prentice-Hall, Englewood Cliffs, NJ. Google ScholarDigital Library
- SHASHA, D., SIMON, E., AND VALDURIEZ, P. 1992. Simple rational guidance for chopping up transactions. In Proceedings of the ACM-SIGMOD International Conference on Management of Data, (San Diego, CA, June), 298-307. Google ScholarDigital Library
- WEIHL, W.E. 1984. Specification and Implementation of Atomic Data Types. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
- WEIHL, W.E. 1988. Commutativity-based concurrency control for abstract data types. IEEE Trans. Comput., 37, 12 (Dec.), 1488-1505. Google ScholarDigital Library
- WACHTER, H. AND REUTER, A. 1992. The ConTract model. In Database Transaction Models for Advanced Applications, A. K. Elmagarmid, Ed., Morgan Kauffman, San Mateo, CA, 219-263. Google ScholarDigital Library
Index Terms
- Applying formal methods to semantic-based decomposition of transactions
Recommendations
A concurrency control protocol for read-only transactions in real-time secure database systems
RTCSA '00: Proceedings of the Seventh International Conference on Real-Time Systems and ApplicationsA read-only transaction (ROT) or a query is a transaction that only reads data items, without modifying them. When we use a protocol that takes care of ROTs distinctively from update transactions, the number of conflicts between ROTs and update ...
Multiversion Cautious Schedulers for Database Concurrency Control
Let MC stand for a class of logs (i.e. sequences of read/write steps of transactions) that are serializable when multiple versions of the data items are maintained. The multiversion cautious scheduler, MCS(MC) which is introduced, outputs a sequence ...
Using importance of transactions and optimistic concurrency control in firm real-time databases
RTCSA '00: Proceedings of the Seventh International Conference on Real-Time Systems and ApplicationsIn a real-time database system, it is difficult to meet all of the timing constraints due to the consistency requirements of the underlying database. However, when the transactions in the system are heterogeneous, they are not all of the same importance-...
Comments