Hiram CPSC 356 - Transaction - CPSC 356 Database

Unformatted text preview:

TransactionsTransactionStates of a TransactionACID Properties of a Transaction (Härder and Reuter, 1983)Concurrency ControlLost Update ProblemDirty Read ProblemNonrepeatable Read ProblemInconsistent Analysis ProblemInterleaving Causes ProblemsDefinitions for SchedulingConflict SerializabilitySerializability TestingSerializability Testing (cont.)Generalizing SerializabilitySerializability Testing vs. EnforcementLocking AlgorithmsUsing LocksTypes of LocksLocking ProtocolsStatic Locking2 Phase Locking2-Phase Locking can cause Cascading RollbackRigorous & Strict 2 Phase LockingDeadlock2 Phase Locking can lead to DeadlockDeadlock DetectionDeadlock Prevention (Lock methods)Deadlock Prevention (Timestamp)Eliminating Deadlock with TimestampsLocking in a Real DBMSTransactionsCPSC 356 DatabaseEllen WalkerHiram College(Includes figures from Database Systems by Connolly & Begg, © Addison Wesley 2002)Transaction•A logical unit of work for a database–Example: “move $5 from savings to checking”–{ withdraw 5 from savings; add 5 to checking }•Must be prevented from interfering with each other•Transactions must be “all or nothing”–If the transaction doesn’t complete, no changes should be made at all!States of a Transaction•Successful transactions are committed•Failed partial transactions are rolled back•Committed transactions cannot be undone. We must create a new (compensating) transaction to fix the database.ACID Properties of a Transaction(Härder and Reuter, 1983)•Atomicity — a transaction is either performed in its entirety or not at all•Consistency — a transaction must take the database from one consistent state to another•Isolation (Serializable) — if two transactions run at the same time, the result must look as if they ran sequentially in some arbitrary order; a transaction’s updates must not be visible to other transactions until it commits•Durability — once a transaction commits, its result is permanent (must never be lost)Concurrency Control•Two or more transactions proceed concurrently, while preserving serializability (isolation)•Transactions cannot interfere with each other–Lost update problem–Dirty read problem–Inconsistent analysis problemLost Update Problem–Account A = $100, B = $200, C = $300•Transaction T transfers $4 from A to B•Transaction U transfers $3 from C to B•Should end A = $96, B = $207, C = $297–U’s update of B is lost:Transaction T Transaction Ubal=read(A) $100write(A,bal–4) $96bal=read(C) $300write(C,bal–3) $297bal=read(B) $200bal=read(B) $200write(B,bal+3) $203write(B,bal+4) $204Dirty Read Problem•Account A = $200, B = $200–Transaction T transfers $100 from A to B but fails!–Transaction U deposits $25 to A–Should end A = $225, B = $200•Problem: –Transaction U read “dirty value” of A after $100 was taken…Transaction T Transaction U bal=read(A) $200write(A,bal–100) $100bal=read(A) $100write(A, bal+25) $125bal=read(B) $200…ROLLBACK!Nonrepeatable Read Problem•Similar to dirty read, but the same transaction reads the same value twiceTransaction T Transaction U read(A) $1000sal=read(A) $1000 (unrelated actions)write(A,sal*1.1) $1100sal=read(A) $1100Inconsistent Analysis Problem–Situation:•Transaction T gives everyone a 10% raise•Transaction U computes the average salary–Problem: •Some salaries have been raised, some not when average is computed (avg should be 1500 or 1650)Transaction T Transaction U sal=read(A) $1000write(A,sal*1.1) $1100bal=read(A) $1100bal+=read(B) $3100sal=read(B) $2000write(B,sal*1.1) $2200avg = bal/2 $1550Interleaving Causes Problems•We need concurrency control mechanism–Allow as much concurrency among transactions as possible (throughput)–Prevent other transactions from viewing intermediate values (not yet committed)Definitions for Scheduling•Schedule–A sequence of operations by a set of concurrent transactions that preserves order of operations within each transaction•Serial Schedule–A schedule without any interleaving•Nonserial Schedule–A schedule where operations from different transactions are interleavedConflict Serializability•A serializable schedule has the same result as a serial schedule•Recognize conflicts between transactions–Both transactions access the same variable–At least one of those accesses is a write•When all conflicts happen in the same order (T before U or U before T), then the schedule is serializable; otherwise not.Serializability Testing•Draw a downward (forward in time) arrow for each conflict (when one transaction is writing). If all arrows point the same way, then the schedule is serializableTransaction T Transaction Ubal=read(A)write(A,bal–4)bal=read(C)write(C,bal–3)bal=read(B)write(B,bal+4)bal=read(B)write(B,bal+3)Serializability Testing (cont.)•If at least one arrow is pointing leftward and another arrow is pointing rightward, the schedule is not serializableTransaction T Transaction Ubal=read(A)write(A,bal–4)bal=read(C)write(C,bal–3)bal=read(B)bal=read(B)write(B,bal+4)write(B,bal+3)Generalizing Serializability•With more than two transactions, build a conflict serializable graph–Each transaction is a node of the graph–For each conflict, draw an arc from the earlier transaction to the later transaction.•If this graph has a cycle, then the schedule is not serializableSerializability Testing vs. Enforcement•To test serializability, you have to create the graph and check for cycles–This cannot be done efficiently (result from study of algorithms)•Instead, let’s create extra constraints (locking) to enforce serializabilityLocking Algorithms•Locking is a method of controlling concurrency using a lock (variable) to deny transactions access to certain objects•Types of locking–Static locking–2 Phase Locking•Other algorithms (we won’t cover)–Optimistic concurrency control–Timestamp orderingUsing Locks•Transaction must lock the data object before accessing it•Transaction should unlock the data object when done•If an item is locked, the transaction must wait until it is unlocked•Example transaction:–Lock B; read B; … write B; unlock B; commit.Types of Locks•Shared lock–Transaction can read item only (read lock)•Exclusive lock–Transaction can read and update item (write lock)•Shared lock can be upgraded to exclusive lock.•Exclusive lock can be downgraded to shared lock.Locking Protocols•Even locking doesn’t


View Full Document

Hiram CPSC 356 - Transaction - CPSC 356 Database

Download Transaction - CPSC 356 Database
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Transaction - CPSC 356 Database and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Transaction - CPSC 356 Database 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?