database - How do we perform swap operation in conflict-serializability?

问题描述

Assume I have the following concurrent transactions:

----------------------
|Ti        | Tj      |
----------------------         
| write(Q) |         |
----------------------
|          | read(Q) |
----------------------
| read(Q)  |         |
----------------------
|          | write(Q)|
----------------------
| write(Q) |         |
----------------------
|          | write(Q)|
----------------------

If we draw the precedence-graph, we'll see that it is not conflict-serializable. Since the graph will be cyclic. The reason is:

----------------------
|          | write(Q)|
----------------------
| write(Q) |         |
----------------------
|          | write(Q)|
----------------------

From the book: "Database System Concepts - 6th edition" source

If a schedule S can be transformed into a schedule S' by a series of swaps of non-conflicting instructions, we say that S and S' are conflict equivalent. We say that a schedule S is conflict serializable if it is conflict equivalent to a serial schedule.

Now, what does this swap means?

Can I do something like:

----------------------
|Ti        | Tj      |
----------------------         
| write(Q) |         |
----------------------
| read(Q)  |         |
----------------------
| write(Q) |         |
----------------------
|          | read(Q) |
----------------------
|          | write(Q)|
----------------------
|          | write(Q)|
----------------------

Or can I change the order?

----------------------
|Ti        | Tj      |
----------------------         
| read(Q)  |         |
----------------------
| write(Q) |         |
----------------------
| write(Q) |         |
----------------------
|          | read(Q) |
----------------------
|          | write(Q)|
----------------------
|          | write(Q)|
----------------------

Regards

P.S. I looked at other answer but it is not explaining the swap operation.

标签： databaseconflict-serializability

解决方案

swap means moving the statements to the desired place. Therefore swap is a trivial terminology for detecting conflict-serializability. However, swaps of non-conflicting instruction is important.

Can I do something like:

----------------------
|Ti        | Tj      |
----------------------         
| write(Q) |         |
----------------------
| read(Q)  |         |
----------------------
| write(Q) |         |
----------------------
|          | read(Q) |
----------------------
|          | write(Q)|
----------------------
|          | write(Q)|
----------------------

No we can't do the above operation. Since the operation on Q ends at the end of the transaction. Swapping should not change the order.

Or can I change the order?

No changing the order is not permitted. Changing the order means updating the transaction which is not permitted unless the transaction is aborted.

Since we have a cycle, the operation is not conflict serializable. Serializable is important for Consistency and Isolation requirements. As we can wee the problem is caused by the last sentence of the Ti

What happens if we remove the last sentence of the `Ti`?

----------------------
|Ti        | Tj      |
----------------------         
| write(Q) |         |
----------------------
|          | read(Q) |
----------------------
| read(Q)  |         |
----------------------
|          | write(Q)|
----------------------
|          | write(Q)|
----------------------

Now the schedule becomes the conflict-serializable.

How about swapping?

If the situation is similar to the below:

----------------------
|Ti        | Tj      |
----------------------         
| write(Q) |         |
----------------------
|          | read(W) |
----------------------
| read(Q)  |         |
----------------------
|          | write(W)|
----------------------
|          | write(W)|
----------------------

Then we can swap read(Q) with read(W):

----------------------
|Ti        | Tj      |
----------------------         
| write(Q) |         |
----------------------
| read(Q)  |         |
----------------------
|          | read(W) |
----------------------
|          | write(W)|
----------------------
|          | write(W)|
----------------------

Interpretation

The transaction Ti starts with writing to Q column without reading the Q's current value. This might cause a violation if there is a trigger checking the database. Then Ti and Tj both do read(Q) operation. Suddenly Tj starts writing. Then Ti writes without waiting Tj to commit. Therefore by looking at the current state, we can say the situation is troubled.