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.
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
Ti
?----------------------
|Ti | Tj |
----------------------
| write(Q) | |
----------------------
| | read(Q) |
----------------------
| read(Q) | |
----------------------
| | write(Q)|
----------------------
| | write(Q)|
----------------------
Now the schedule becomes the conflict-serializable.
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)|
----------------------
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.