logo标签列表

“冲突可串行化”和“冲突等价”的区别是什么？

databaseconflictserializableequivalence
29
在数据库理论中，“冲突可串行化”和“冲突等价”有什么区别？我的教材有关于“冲突可串行化”的部分，但是对“冲突等价”只是简单地提及。这两个概念可能都很熟悉，但我不熟悉这个术语，所以我正在寻找解释。
8个回答
64

DBMS中的冲突可以定义为两个或更多个不同的事务访问相同的变量，其中至少一个是写操作。

例如：

T1: Read(X)   
T2: Read (X)

在这种情况下，没有冲突，因为两个事务都只执行读取操作。

但在以下情况下：

T1: Read(X)   
T2: Write(X)

有一个冲突。

假设我们有一个调度S，我们可以重新排序其中的指令，并创建另外两个调度S1和S2。

冲突等价: 指维持冲突指令顺序的S1和S2调度。例如，如果T1在S1中必须在T2写入X之前读取X，那么S2中也应该是这样。(只有冲突操作的顺序需要维护)

冲突可串行化: 如果S与一个串行调度(即按顺序一个接一个执行事务)是冲突等价的，则称S是冲突可串行的。

1
你在未编辑的回答中说如果不清楚的话会发布图片，那么请您无论如何都能够这样做吗？ - nbro
8

来源：维基百科

冲突等价性

如果满足以下条件，则称调度S1和S2具有冲突等价性：

  1. 调度S1和S2都涉及相同的事务集（包括每个事务内部的操作顺序）。

  2. S1和S2中每一对冲突操作的顺序相同。

冲突可串行化

当调度与一个或多个串行调度具有冲突等价性时，则称该调度为冲突可串行化。

另一种定义冲突可串行化的方法是，当只考虑已提交的事务时，其优先级图/可串行性图是无环的（如果将未提交的事务也包括在内，则可能会出现涉及未提交事务的循环而不违反冲突串行性）。

3
我知道，我已经阅读了维基......我只是不明白这两件事情究竟有什么不同。 - taz
7

只有两个术语来描述同一件事情的不同方式。

冲突等价：你需要说日程表A与日程表B是冲突等价的。它必须涉及到两个日程表。

冲突可串行化：仍然使用日程表A和B。我们可以说日程表A是冲突可串行化的。日程表B也是冲突可串行化的。

我们没有说日程表A/B是冲突等价的。

我们没有说日程表A与日程表B是冲突可串行化的。

1
那么您强调特定术语的差异吗？要使用“冲突等价”，必须引用维护相互冲突等价的两个单独的日程安排？而要使用“冲突可串行化”，必须引用具有与至少另一个日程安排相冲突等价属性的单个日程安排？所以，“冲突等价”指的是至少两个日程安排，每个日程安排均为“冲突可串行化”？ - taz
是的，这是我在我的事务处理课上刚学到的。而且应该是正确的。 - fengd
4

如果一个调度S可以通过一系列非冲突指令的交换被转化为一个调度S´，我们称S和S´是冲突等价的。

如果一个调度S与一个串行调度具有冲突等价性，我们称S是冲突可串行化的。

2
冲突可串行化（Conflict serializable）意味着与任何串行调度相冲突。
1
冲突等价调度：如果一个调度S可以通过一系列非冲突指令的交换转换为调度S'，我们称调度S和S'是冲突等价的。 冲突可串行化调度：如果调度S与一个串行调度是冲突等价的，则调度S是冲突可串行化的。
0

如果考虑的事务调度存在至少一个与之冲突等价的调度，则它是冲突可串行化的。

0

定义已经被很好地解释了，但我觉得这对某些人非常有用。

我开发了一个小型控制台程序（在Github上），它可以测试任何调度的冲突可串行化性，并且还会绘制优先级图。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接