database - 这个的可序列化图是什么？

Question

我试图弄清楚一个问题，但我不知道如何解决它，我在问题中的大部分条款都是未经宣布的。下面是问题:

Three transactions; T1, T2 and T3 and schedule program s1 are given below. Please draw the precedence or serializability graph of the s1 and specify the serializability of the schedule S1. If possible, write at least one serial schedule. r ==> read, w ==> write

T1: r1(X);r1(Z);w1(X);

T2: r2(Z);r2(Y);w2(Z);w2(Y);

T3: r3(X);r3(Y);w3(Y);

S1: r1(X);r2(Z);r1(Z);r3(Y);r3(Y);w1(X);w3(Y);r2(Y);w2(Z);w2(Y);

我不知道如何解决这个问题，我需要详细的描述。我应该在哪个资源中寻找？预先感谢。

Answer 1

有多种方法可以测试可序列化性。 可串行化的目标是找到允许事务在不相互干扰的情况下并发执行的非串行调度。

首先我们进行冲突等效测试。这将告诉我们调度是否可序列化。

为此，我们必须定义一些规则(i 和 j 是 2 个事务，R=Read，W=Write)。

如果等同于:

，我们不能交换操作顺序:

1. Ri(x), Wi(y) - Conflicts 
2. Wi(x), Wj(x) - Conflicts
3. Ri(x), Wj(x) - Conflicts 
4. Wi(x), Rj(x) - Conflicts

但这些都是完全有效的:

R1(x), Rj(y) - No conflict (2 reads never conflict)
Ri(x), Wj(y) - No conflict (working on different items)
Wi(x), Rj(y) - No conflict (same as above)
Wi(x), Wj(y) - No conflict (same as above)

因此应用上面的规则我们可以得出这个(为简单起见使用 excel):

从结果中，我们可以清楚地看到设法推导了一个序列关系(即您上面的时间表，可以拆分为 S(T1, T3, T2)。

现在我们有了一个可序列化的调度，并且有了串行调度，我们现在进行Conflict-Serialazabile 测试:

执行此操作的最简单方法是使用与冲突等效测试 相同的规则，查找可能发生冲突的任何组合。

r1(x); r2(z); r1(z); r3(y); r3(y); w1(x); w3(y); r2(y); w2(z); w2(y);
----------------------------------------------------------------------
              r1(z)                                     w2(z)
                            r3(y)                              w2(y)
                                          w3(y)  r2(y)
                                          w3(y)                w2(y)

使用上面的规则，我们最终得到一个像上面这样的表(例如，我们知道从一个事务中读取 z 然后从另一个事务中写入 z 会导致冲突(看规则 3)。

给定表格，从左到右，我们可以创建具有以下条件的优先级图:

T1 -> T2
T3 -> T2 (only 1 arrow per combination)

因此我们最终得到一个如下图:

从图中可以看出，由于它是非循环的(没有循环)，我们可以得出结论，该调度是可冲突序列化的。此外，因为它也是 View 可序列化的(因为每个冲突的时间表也是 View )。我们可以测试 View 来证明这一点，但这相当复杂。

关于学习本资料的来源，我推荐:

“数据库系统:设计、实现和管理的实用方法:国际版”，作者:Thomas Connolly； Carolyn Begg -(它相当昂贵，所以我建议寻找更便宜的 pdf 副本)

祝你好运!

更新我开发了 a little tool这将为您完成上述所有操作(包括图表)。它使用起来非常简单，我还添加了一些示例。