什么是可串行化图？

Question

我试图找出一个问题,但是我不知道如何解决它,我在问题中大多数条款没有宣布.这是一个问题:

三笔交易; 下面给出T1,T2和T3以及调度程序s1.请绘制s1的优先级或可序列化图,并指定计划S1的可序列化.如果可能,请至少编写一个串行计划.r ==>读,w ==>写

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).

现在我们有一个可序列化的时间表,并且我们有连续时间表,现在我们进行冲突 - 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-s).我们可以测试视图来证明这一点,但它相当复杂.

关于学习这些材料的来源,我建议:

"数据库系统:设计,实施和管理的实用方法:国际版",作者:Thomas Connolly; Carolyn Begg - (相当贵,所以我建议寻找更便宜的pdf副本)

祝好运!

更新 我开发了一个小工具,可以为你完成上述所有工作(包括图形).它使用起来非常简单,我还添加了一些例子.