Database Management Systems

Database Management Systems - Prof. Holowczak

Zicklin School of Business - Baruch College
City University of New York

Database Management Systems - DBMS Functions

Database Management Systems Functions

What You'll Learn This Week

Transaction Processing
Concurrency Control and Locking
Database Recovery and Backup
For Next Week

Connolly, Begg, Holowczak Elmasri/Navathe (3^rd) ed.
Chapter 14 Chapters 19, 20 and 21

Connolly, Begg, Holowczak	Elmasri/Navathe (3^rd) ed.
Chapter 14	Chapters 19, 20 and 21

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 P200      Read inventory for Prod P200 
Decrement inventory by 5          Decrement inventory by 7
Write inventory for Prod P200     Write inventory for Prod P200

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 Product P200:

Time  Operation                TA           TB            Value of P200
1     Begin Transaction TA     Begin                      10 
2     Begin Transaction TB                  Begin         10
3     TA Read inventory P200   Read(P200)                 10
4     TB Read inventory P200                Read(P200)    10
5     TA Decrement inventory   P200=P200-2                10
6     TB Decrement inventory                P200=P200-3   10
7     TA Wrtie inventory       Write(P200)                 8 (dirty)
8     TB Wrtie inventory                    Write(P200)    7 (dirty)
9     TA Commit                Commit                      7 (dirty)
10    TB Commit                             Commit         7 (clean)

Or something similar like:

Time  Operation                TA           TB            Value of P200
1     Begin Transaction TA     Begin                      10 
2     TA Read inventory P200   Read(P200)                 10
3     TA Decrement inventory   P200=P200-2                10
4     TA Wrtie inventory       Write(P200)                 8 (dirty)
5     TA Commit                Commit                      8 (clean)
6     Begin Transaction TB                  Begin          8
7     TB Read inventory P200                Read(P200)     8
8     TB Decrement inventory                P200=P200-3    8
9     TB Wrtie inventory                    Write(P200)    5 (dirty)
10    TB Commit                             Commit         5 (clean)

In the first case, the incorrect amount (7) is written to the database. This is called the Lost Update problem because we lost the update from TA - it was overwritten by T2.
The second example works because we let TA write the new value of Product P200 before TB can read it.

Here is another example.

Time  Operation                TA           TB            Value of P200
1     Begin Transaction TA     Begin                      10 
2     TA Read inventory P200   Read(P200)                 10
3     TA Decrement inventory   P200=P200-2                10
4     TA Wrtie inventory       Write(P200)                 8 (dirty)
5     Begin Transaction TB                  Begin          8
6     TB Read inventory P200                Read(P200)     8
7     TA Aborts/Rollback       Abort                      10 (clean)
8     TB Decrement inventory                P200=P200-3   10
9     TB Wrtie inventory                    Write(P200)    5 (dirty)
10    TB Commit                             Commit         5 (clean)

The reason we get the wrong final result is becaue TA had not committed before TB was allowed to read a value TA had written. This is called the uncomitted dependency or Dirty read problem.

Now consider a transaction trying to find a SUM of all units in inventory while another transaction is trying to update inventory
(d) means direty and (c) means clean.

Time  Operation                TA           TB            P200  P300  P400  Sum
1     Begin Transaction TA     Begin                      10    15    20     0
2     TA Read inventory P200   Read(P200)                 10    15    20     0
3     TA Sum up inventory      Sum=Sum+P200               10    15    20    10
4     TA Read inventory P300   Read(P300)                 10    15    20    10
5     TA Sum up inventory      Sum=Sum+P300               10    15    20    25
6     Begin Transaction TB                  Begin         10    15    20    25
7     TB Read inventory P200                Read(P200)    10    15    20    25
8     TB Decrement inventory                P200=P200-3   10    15    20    25
9     TB Wrtie inventory                    Write(P200)    7(d) 15    20    25
10    TA Read inventory P400   Read(P400)                  7(d) 15    20    45
11    TA Sum up inventory      Sum=Sum+P400                7(d) 15    20    45
12    TB Commit                             Commit         7(c) 15    20    45
13    TA Commit                             Commit         7(c) 15    20    45

The final sum is not correct. This happened because TB was allowed to write a data item that TA was trying to use in its work. This is called the incorrect analysis problem

Suppose we have a transaction that says if P300 is greater than P200 then decrement P300. At the same time another transaction is trying to update P300.

Time  Operation                TA              TB            P200    P300
1     Begin Transaction TA     Begin                         10      15
2     TA Read inventory P200   Read(P200)=10                 10      15
3     TA Read inventory P300   Read(P300)=15                 10      15
4     TB Begin Transaction                     Begin         10      15
5     TB Read inventory P300                   Read(P300)    10      15
6     TB Decrement inventory                   P300=P300-10  10      15
7     TB Wrtie inventory                       Write(P300)   10       5 (d)
8     TB Commit                                Commit        10       5 (c)
9     TA P300 > P200 so update                               10       5 (c)
10    TA Read inventory P200   Read(P200)=10                 10       5
11    TA Read inventory P300   Read(P300)=5                  10       5
12    TA Decrement inventory   P300=P300-5                   10       5
13    TA Wrtie inventory       Write(P300)                   10       0 (d)
14    TA Commit                Commit                        10       0 (c)

The two read operations that TA performas at time 3 and time 11 get different results.
This is called the non-repeatable read problem (or fuzzy read problem).

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:

Time  Operation                TA           TB            P200 
1     Begin Transaction TA     Begin                      10   
2     Begin Transaction TB                  Begin         10   
3     TA Excl. Lock P200       XL(P200)                   10   
4     TA Read inventory P200   Read(P200)                 10   
5     TB Excl. Lock P200                    Denied        10   
6     TA Decrement inventory   P200=P200-2                10   
7     TA Wrtie inventory       Write(P200)                 8 (dirty)   
8     TA Release Lock P200     Release(P200)               8 (dirty)   
9     TA Commit                Commit                      8 (clean)   
10    TB Read inventory P200                Read(P200)     8   
11    TB Decrement inventory                P200=P200-3    8   
12    TB Wrtie inventory                    Write(P200)    5 (dirty)   
13    TB Commit                             Commit         5 (clean)

Note that at time 5, Transaction B is Denied a lock. So Transaction B will "spin" in place until that lock on P200 is released.

Deadlock

Locking can cause problems, however.

Consider:

TA places an exclusive lock on item P1001
TB places an exclusive lock on item P2002
TA attempts to place an exclusive lock on item P2002
       TA placed into a wait state
TB attempts to place an exclusive lock on item P1001
       TB 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.

File: week12.html Date: 11:04 AM 11/22/2011
All materials Copyright, 1997-2011 Richard Holowczak

Zicklin School of Business - Baruch College City University of New York