我们如何在冲突可串行化中执行交换操作？

Question

假设我有以下并发事务：

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

如果我们绘制优先级图，我们会发现它不是冲突序列化的。由于图形将是循环的。原因是：

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

来自书籍：《数据库系统概念 - 第 6 版》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.

现在，swap 是什么意思？

我可以这样做吗：

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

或者我可以更改顺序吗？

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

此致

P.S。我查看了 other answer 但它没有解释 swap 操作。

Answer 1

swap 表示将语句移动到所需位置。因此 swap 是一个用于检测冲突可串行化的普通术语。但是，swaps of non-conflicting instruction 很重要。

Can I do something like:

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

不行，我们不能做上面的操作。由于对 Q 的操作在事务结束时结束。交换不应改变顺序。

Or can I change the order?

不允许更改顺序。更改订单意味着更新交易，除非交易被中止，否则不允许更新。

因为我们有一个循环，操作是不冲突可序列化的。可序列化对于一致性和隔离性要求很重要。我们可以看出问题是由 Ti

的最后一句引起的

如果我们删除 Ti 的最后一句会怎样？

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

现在调度变成了冲突序列化。

交换怎么样？

如果类似下面的情况：

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

然后我们可以将 read(Q) 与 read(W) 交换：

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

解读

事务 Ti 从写入 Q 列开始，而不是读取 Q 的当前值。如果有触发器检查数据库，这可能会导致违规。然后Ti和Tj都做read(Q)操作。突然 Tj 开始写作。然后 Ti 写入而不等待 Tj 提交。所以从现在的状态来看，可以说是麻烦不断。