Database Management Systems Functions

What You'll Learn This Week

• Transaction Processing
• Concurrency Control and Locking
  • Characteristics of Locks
  • Two Phase Locking
  • Deadlock
• Database Recovery and Backup
  • Reprocessing
  • Rollback / Rollforward
  • Database Backup
• For Next Week

Topic	Elmasri/Navathe (3rd ed.)	Kroenke (7th ed.)	McFadden (5th ed.)
Transaction processing	19 (19.1 through 19.5.1)	Chapter 12	Chapter 13 (pg. 498-512)
Concurrency Control	20 (Just part 20.1 on locking)	Chapter 12, 14	Chapter 13 (pg. 498-512)
Recovery and Backup	21 (Just part 21.1)	Chapter 12	Chapter 13 (pg. 498-512)

MultiUser Databases

• Multiuser database - more than one user processes the database at the same time
• Several issues arise:
  1. How can we prevent users from interfering with each other's work ?
  2. How can we safely process transactions on the database without corrupting or losing data ?
  3. If there is a problem (e.g., power failure or system crash), how can we recover without loosing all of our data ?

Transaction Processing

• We need the ability to control how transactions are run in a multiuser database.

• A transaction is a set of read and write operations that must either commit or abort.

• Consider the following transaction that reserves a seat on an airplane flight and changes the customer:
  1. Read customer information
  2. Write reservation information
  3. Write charges
  
• Suppose that after the second step, the database crashes. Or for some reason, changes can not be written...

• Transactions can either reach a commit point, where all actions are permanently saved in the database or they can abort in which case none of the actions are saved.

• Another way to say this is transactions are Atomic. All operations in a transaction must be executed as a single unit - Logical Unit of Work.

• Consider two users, each executing similar transactions:

  Example #1:
  
  User A                            User B
  Read Salary for emp 101           Read Salary for emp 101
  Multiply salary by 1.03           Multiply salary by 1.04
  Write Salary for emp 101          Write Salary for emp 101
  
  
  Example #2:
  
  User A                            User B
  Read inventory for Prod 200       Read inventory for Prod 200 
  Decrement inventory by 5          Decrement inventory by 7
  Write inventory for Prod 200      Write inventory for Prod 200
  

• First, what should the values for salary (in the first example) really be ?

• The DBMS must find a way to execute these two transactions concurrently and ensure the result is what the users (and designers) intended.

• These two are examples of the Lost Update or Concurrent Update problem. Some changes to the database can be overwritten.

• Consider how the operations for user's A and B might be interleaved as in example #2. Assume there are 10 units in inventory for Prod 200:

  Read inventory for Prod 200       for user A
  Read inventory for Prod 200       for user B
  Decrement inventory by 5          for user A
  Decrement inventory by 7          for user B
  Write inventory for Prod 200      for user A
  Write inventory for Prod 200      for user B
  

  Or something similar like:

  Read inventory for Prod 200       for user A
  Decrement inventory by 5          for user A
  Write inventory for Prod 200      for user A
  Read inventory for Prod 200       for user B
  Decrement inventory by 7          for user B
  Write inventory for Prod 200      for user B
  

• In the first case, the incorrect amount (3) is written to the database. This is called the Lost Update problem because we lost the update from User A - it was overwritten by user B.
• The second example works because we let user A write the new value of Prod 200 before user B can read it. Thus User B's decrement operation will fail.

• Here is another example. User's A and B share a bank account. Assume an initial balance of $200.

  User A reads the balance
  User A deducts $100 from the balance
  User B reads the balance
  User A writes the new balance of $100
  User B deducts $100 from the balance
  User B writes the new balance of $100
  

• The reason we get the wrong final result (remaining balance of $100) is because transaction B was allowed to read stale data. This is called the inconsistent read problem.

• Suppose, instead of interleaving (mixing) the operations of the two transactions, we execute one after the other (note it makes no difference which order: A then B, or B then A)

  User A reads the balance
  User A deducts $100 from the balance
  User A writes the new balance of $100
  User B reads the balance (which is now $100)
  User B deducts $100 from the balance
  User B writes the new balance of $0
  

• If we insist only one transaction can execute at a time, in serial order, then performance will be quite poor.

• Concurrency Control is a method for controlling or scheduling the operations in such a way that concurrent transactions can be executed.

• If we do concurrency control properly, then we can maximize transaction throughput while avoiding any chance.

• Transaction throughput: The number of transactions we can perform in a given time period. Often reported as Transactions per second or TPS.

• A group of two or more concurrent transactions are serializable if we can order their operations so that the final result is the same as if we had run them in serial order (one after another).

• Consider transaction A, B, C and D. Each has 3 operations. If executing:
  A1, B1, A2, C1, C2, B2, A3, B3, C3
  has the same result as executing:
  A1, A2, A3, B1, B2, B3, C1, C2, C3
  Then the above schedule of transactions and operations is serialized.

Concurrency Control and Locking

• We need a way to guarantee that our concurrent transactions can be serialized. Locking is one such means.

• Locking is done to data items in order to reserve them for future operations.
• A lock is a logical flag set by a transaction to alert other transactions the data item is in use.

Characteristics of Locks

• Locks may be applied to data items in two ways:
  Implicit Locks are applied by the DBMS
  Explicit Locks are applied by application programs.

• Locks may be applied to:
  1. a single data item (value)
  2. an entire row of a table
  3. a page (memory segment) (many rows worth)
  4. an entire table
  5. an entire database
  This is referred to as the Lock granularity

• Locks may be of type types depending on the requirements of the transaction:
  1. An Exclusive Lock prevents any other transaction from reading or modifying the locked item.
  2. A Shared Lock allows another transaction to read an item but prevents another transaction from writing the item.

Two Phase Locking

• The most commonly implemented locking mechanism is called Two Phased Locking or 2PL. 2PL is a concurrency control mechanism that ensure serializability.

• 2PL has two phases: Growing and shrinking.
  1. A transaction acquires locks on data items it will need to complete the transaction. This is called the growing phase.
  2. Once one lock is released, all no other lock may be acquired. This is called the shrinking phase.

• Consider our prior example, this time using locks:

  User A places an exclusive lock on the balance
  User A reads the balance
  User A deducts $100 from the balance
  
  User B attempts to place a lock on the balance 
         but fails because A already has an exclusive lock
         User B is placed into a wait state
  User A writes the new balance of $100
  User A releases the exclusive lock on the balance
  
  User B places an exclusive lock on the balance
  User B reads the balance
  User B deducts $100 from the balance
  User B writes the new balance of $100
  

• Here is a more involved example:

  User A places a shared lock on item raise_rate
  User A reads raise_rate
  User A places an exclusive lock on item Amy_salary
  User A reads Amy_salary
  
  User B places a shared lock on item raise_rate
  User B reads raise_rate
  
  User A calculates a new salary as Amy_salary * (1+raise_rate)
  
  User B places an exclusive lock on item Bill_salary
  User B reads Bill_salary
  User B calculates a new salary as Bill_salary * (1+raise_rate)
  User B writes Bill_salary
  
  User A writes Amy_salary
  User A releases exclusive lock on Amy_salary
  
  User B releases exclusive lock on Bill_Salary
  User B releases shared lock on  raise_rate
  
  User A releases shared lock on raise_rate
  

• Here is another example:

  User A places a shared lock on raise_rate
  
  User B attempts to place an exclusive lock on raise_rate
         Placed into a wait state
  
  User A places an exclusive lock on item Amy_salary
  User A reads raise_rate
  User A releases shared lock on raise_rate
  
  User B places an exclusive lock on raise_rate
  
  User A reads Amy_salary
  
  User B reads raise_rate
  
  User A calculates a new salary as Amy_salary * (1+raise_rate)
  
  User B writes a new raise_rate
  User B releases exclusive lock on raise_rate
  
  User A writes Amy_salary
  User A releases exclusive lock on Amy_salary
  
  

Deadlock

• Locking can cause problems, however.
• Consider:

  User A places an exclusive lock on item 1001
  User B places an exclusive lock on item 2002
  User A attempts to place an exclusive lock on item 2002
         User A placed into a wait state
  User B attempts to place an exclusive lock on item 1001
         User B placed into a wait state
  ...
  
  

• This is called a deadlock. One transaction has locked some of the resources and is waiting for locks so it can complete. A second transaction has locked those needed items but is awaiting the release of locks the first transaction is holding so it can continue.

• Two main ways to deal with deadlock.
  1. Prevent it in the first place by giving each transaction exclusive rights to acquire all locks needed before proceeding.
  2. Allow the deadlock to occur, then break it by aborting one of the transactions.

Database Recovery and Backup

• There are many situations in which a transaction may not reach a commit or abort point.
  1. An operating system crash can terminate the DBMS processes
  2. The DBMS can crash
  3. The system might lose power
  4. A disk may fail or other hardware may fail.
  5. Human error can result in deletion of critical data.
• In any of these situations, data in the database may become inconsistent or lost.

• Database Recovery is the process of restoring the database and the data to a consistent state. This may include restoring lost data up to the point of the event (e.g. system crash).

• Two approaches are discussed here: Reprocessing and Rollback/Rollforward.

Reprocessing

• In a Reprocessing approach, the database is periodically backed up (a database save) and all transactions applied since the last save are recorded
• If the system crashes, the latest database save is restored and all of the transactions are re-applied (by users) to bring the database back up to the point just before the crash.

• Several shortcomings:
  1. Time required to re-apply transactions
  2. Transactions might have other (physical) consequences
  3. Re-applying concurrent transactions is not straight forward.

Automated Recovery with Rollback / Rollforward

• We apply a similar technique: Make periodic saves of the database (time consuming operation). However, maintain a more intelligent log of the transactions that have been applied. This transaction log Includes before images and after images

• Before Image: A copy of the table record (or page) of data before it was changed by the transaction.
• After Image: A copy of the table record (or page) of data after it was changed by the transaction.

• Rollback: Undo any partially completed transactions (ones in progress when the crash occurred) by applying the before images to the database.
• Rollforward: Redo the transactions by applying the after images to the database. This is done for transactions that were committed before the crash.

• Recovery process uses both rollback and rollforward to restore the database.
• In the worst case, we would need to rollback to the last database save and then rollforward to the point just before the crash.

• Checkpoints can also be taken (less time consuming) in between database saves.
• The DBMS flushes all pending transactions and writes all data to disk and transaction log.
• Database can be recovered from the last checkpoint in much less time.

Database Backup

• When secondary media (disk) fails, data may become unreadable.
• We typically rely on backing up the database to cheaper magnetic tape or other backup medium for a copy that can be restored.
• However, when an DBMS is running, it is not possible to backup its files as the resulting backup copy on tape may be inconsistent.

• One solution: Shut down the DBMS (and thus all applications), do a full backup - copy everything on to tape. Then start up again.
  May be infeasible to do often.

• Most modern DBMS allow for incremental backups.
• An Incremental backup will backup only those data changed or added since the last full backup. Sometimes called a delta backup.

• Follows something like:
  1. Weekend: Do a shutdown of the DBMS, and full backup of the database onto a fresh tape(s).
  2. Nightly: Do an incremental backup onto different tapes for each night of the week.