A transaction can end in one of two ways: If it is successful, then the changes it made are stored in the database permanently—the transaction is committed—or if the transaction fails, all the changes made by transaction are undone, restoring the database to the state that it was in prior to the start of the transaction (a rollback). A transaction is an all-or-nothing unit. Either the entire transaction succeeds or the entire transaction fails and is undone. We therefore often call a transaction the unit of recovery.

Why might a transaction fail? There are several reasons:

When a transaction begins, it is given a number. Each time the transaction makes a change, the values prior to the change are written to a record in the log file. Records for transactions running concurrently are intermixed in the file. Therefore, the records for each transaction are connected into a linked list, with each record pointing to the next.

When a transaction commits, its changes are written to the database and its records purged from the log file. If a transaction fails for any reason, however, a rollback occurs conceptually in the following way:

There is one major problem with maintaining a log file: ensuring that all changes to the log file are actually written to disk. This is important because it is more efficient for a computer to wait until it has a complete unit of data to write before it actually accesses the disk than to write each time data are modified. Operating systems maintain disk I/O buffers in main memory to hold data waiting to be written. When a buffer is full, the write occurs. The buffering system is efficient because while memory—which is one of the computer’s fastest components—fills several buffers, the disk can be taking its time with the writing. Once it finishes a write, the disk empties the next buffer in line. In this way, the slower device—the disk—is kept busy. However, a problem occurs when the computer fails for any reason. (Even a power outage can be at fault.) Whatever data were in the buffers at that time, waiting to be written, are lost. If those lost buffer contents happen to contain database log records, then the database and the log may well be inconsistent.

The solution is something known as a checkpoint. A checkpoint is an instant in time at which the database and the log file are known to be consistent. To take a checkpoint, the DBMS forces the OS to write the I/O buffers to disk, even if they aren’t full. Both database changes and log file changes are forced to disk. The DBMS then writes a small file (sometimes called the “checkpoint file” or the “recovery file”) that contains the location in the log file of the last log record when the checkpoint was taken.

There will always be some unit of time between checkpoints during which log records are written to the log file. If a system failure occurs, anything after the checkpoint is considered to be suspect because there is no way to know whether data modifications were actually written to disk. The more closely spaced the checkpoints, the less data will be lost due to system failure. However, taking a checkpoint consumes database processing and disk I/O time, slowing down overall database processing. It is therefore the job of a database administrator to find a checkpoint interval that balances safety and performance.

Conceptually, a recovery would work like this:

No normal database processing can occur while the recovery operating is in progress. For large operations with many transactions in the log file, recovery may therefore take some time.

West Side Community Center has been accidentally left out of the delivery of posters for a special event on Saturday. The community center sends an e-mail to all the other community centers in the area, asking for 10–20 posters. Someone at the East Side Center calls in to say that they have 15 posters they can send. The West Side staff member who takes the call checks to see how many posters have been received, sees a 0, and then enters the 15 in the publicity_materials table.

About the same time, another call comes in from the North Side Center and is answered by a different staff member. North Side Center has 12 posters that can be sent. The second staff member queries the database and sees that there are 0 posters—the 15 posters from East Side Center haven’t been stored as of yet—and therefore enters the 12 into the database. However, in the few seconds that elapse between viewing 0 posters and entering 12 posters, the 15 posters are stored in the database. The result is that the 12 overlays the existing value, wiping out the 15 that was just stored. West Side Community Center will be receiving 27 posters, but they don’t know it. The second update wiped out the first. The unintentional loss of data when data are replaced by a newer value is the lost update.

You can see exactly how the first update to the database was lost if you look at the timeline in Figure 22.2. Notice first that the actions of the transactions (one for each user) overlap in time. We therefore say that the transactions are interleaved. One goal of concurrency control is to ensure that the result of interleaved transaction is the same as if the transactions ran one after the other.

In this particular example, regardless of which transaction runs first, the correct answer should be 27: The second staff member should retrieve something other than 0 from the database and know that he or she would need to add the second group of posters to the first. But, that’s not what happens without concurrency control. Instead, at time 4—when the second staff members stores 12 posters—the 0 that the staff member retrieved at time 2 is old data: The lost update occurs because the second transaction was based on old data.

Meanwhile, a customer calls the travel agent in Philadelphia. This customer also needs three seats from Chicago to Denver on the same date and at the same time as the customer in Boston. The travel agent checks the database, and discovers that there are exactly three seats available. These are the same three seats the Boston travel agent just saw.

While the Philadelphia travel agent is talking to her customer, the Boston travel agent receives an OK from the other customer to book the seats. The number of available seats on the flight is modified from three to zero.

The Philadelphia travel agent has also received an OK to book the reservations and proceeds to issue a command that reserves another three seats. The problem, however, is that the Philadelphia travel agent is working from old information. There may have been three seats available when the database was queried, but they are no longer available at the time the reservations are made. As a result, the flight is now overbooked by three seats.

A summary of what is happening can be found in Figure 22.3. This lost update—just like the previous example—occurs because the Philadelphia travel agent is working with old data at time 4 when he or she books three seats.

There are two general strategies for handling the lost update problem:

The first can be accomplished using locking, the second with timestamping, both of which will be discussed shortly.

A staff member needs to produce a report that totals the attendance for all events during the past week. As she starts running the report, the table looks something like Figure 22.4. If the report were to run without being interleaved with any other transactions, the sum of the total_attendance column would be 495.

A second staff member needs to make some modifications to the attendance figures in the events table, correcting two errors. He changes the attendance at the basketball practice on 10-1-20 to 35. He also changes the attendance at the handball tournament on 10-6-20 from 50 to 55.

After the modifications are made, the attendance total is 515. If the report runs before the modifications, the result for the attendance total is 495; if the report runs after the modifications are made, the result for the total is 515. Either one of these results is considered correct because both represent the result of running the transactions one after the other.

However, look what happens when the transactions are interleaved. As you can see in Figure 22.5, the report transaction begins running first. After accessing each of the first 10 rows, the interim total is 295. At time 2, the update transaction begins and runs to completion. At time 4, the report completes its computations, generating a result of 500. Given our definition of a correct result, this is definitely incorrect.

The problem occurred because the update transaction changed the basketball practice attendance figure after the report had processed that row. Therefore, the change is never reflected in the report total.

We can solve the inconsistent analysis problem by

The first can be done with locking, the second with timestamping.

The report generating transaction starts first. It retrieves and totals the first 10 rows. Then the update transaction begins, making changes to both the basketball and handball totals. The report transaction runs again at time 4, reading the modified totals written to the database by the update transaction. The result, as it was with the inconsistent analysis example in the preceding section, is 500. However, at time 5 the update transaction is rolled back, restoring the original values in the table. The correct result should be 495.

As with an inconsistent analysis, a dirty read can be handled by preventing the update transaction from making its modifications at times 2 and 3, using locking or using timestamping to prevent the report from completing because the data “may” have been changed.

Notice that the total attendance for the first read by the report transaction is correct at that time (495). However, when the transaction reads the table again, the total is correct for the data as modified but not the same as the first read of the data.

The nonrepeatable read can be handled by preventing the update transaction from making its modifications because another transaction has already retrieved the data or by preventing the report transaction from completing because the data have been modified.

Assuming that the report transaction is once again creating two output tables, the interaction might appear as in Figure 22.8. The report transaction’s second pass through the table once again produces an incorrect result, caused by the row inserted by the interleaved update transaction.

As with other concurrency control issues that involve the interaction of update and retrieval transactions, the phantom read problem can be solved by preventing the insertion of the new row at time 2 or preventing the report transaction from completing at time 3 because the needed data have been changed.

Let’s look at how shared locks can solve the inconsistent analysis problem. Figure 22.12 diagrams the situation in which the report transaction begins first. The transaction retrieves 10 rows to begin totaling attendance, and receives a shared lock on the table. At time 2, the update transaction begins. However, when it attempts to obtain the exclusive lock it needs for data modification, it must wait because at least one other transaction holds a shared lock on the data. Once the report transaction completes (generating the correct result of 495), the shared locks are released, and the update transaction can obtain the locks it needs.

Now consider what happens if the update transaction starts first. In this case, it is the report transaction that has to wait because it cannot obtain shared locks as long as the modification has exclusive locks in place. As you can see from Figure 22.13, the report transaction produces a result of 515. However, under our rules of correctness for serializable transactions, this is as correct a result as the 495 that was produced when the report transaction started first.

Two-phase locking works by giving an update transaction a shared lock when it retrieves data and then upgrading the lock to an exclusive lock when the transaction actually makes a data modification. This helps increase the amount of concurrent use by keeping the amount of data tied up in exclusive locks to a minimum and by minimizing the time that exclusive locks are in place. The trade-off is that an update transaction may not be able to obtain an exclusive lock for data on which it holds a shared lock because other transactions hold shared locks on the same data. The update transaction will then be rolled back, causing it to release all its locks. It can then be restarted.

One major drawback to two-phase locking is that some processes may need to wait a long time before obtaining the exclusive locks they need to complete processing. This is not an issue for most business databases. However, real-time systems, such as those that monitor oil refineries, nuclear plants, and chemical factories, cannot tolerate delays in transaction processing. Therefore, many real-time databases cannot use two-phase locking.

Some SQL implementations contain statements to indicate the start of a transaction (for example, START TRANSACTION). All, however, provide both COMMIT and ROLLBACK commands to terminate a transaction. The application program must intercept and interpret the code returned by the DBMS at the end of each SQL command to determine whether actions against the database have been successful.

The combination of the need to hold locks until a transaction ends, and programmer control over the length of an embedded SQL transaction means that a poorly written application program can have a major negative impact on database performance. A transaction that is too long, or that unnecessarily locks database resources, will impede the execution of concurrent transactions. It is, therefore, the responsibility of application developers to test their programs under concurrent use conditions to ensure that excessive locking is not occurring.