relational-algebra - 如何理解关系代数中的除法运算符 `u=r÷s` ？

Question

让我们成为一个具有以下关系方案的数据库:R(A,B,D) 和 S(A,B) 在同一域中具有相同名称的属性，并具有 r 和 n 实例。
r 的一个实例

s 的一个实例



什么是方案，什么是 u=r÷s 的元组？如何用 r 和 s 用英语定义它们？

我的尝试

我知道
u=r÷s =

这让我认为它只会是一个 A 列的数组，但我不确定在数组中会产生什么结果。

你能帮我理解 u=r÷s 吗？

Answer 1

关系代数的除法运算符的一个直观性质就是它是笛卡尔积的逆。例如，如果您有两个关系 R 和 S，那么，如果 U 是定义为它们的笛卡尔积的关系:

U = R x S

除法是这样的运算符:

U ÷ R = S

和:

U ÷ S = R

因此，您可以将 U ÷ R 的结果视为:“ U 的投影，乘以 R ，产生 U ”，以及 ÷ 运算，作为找到 U 与所有“部分”组合的运算 R 的元组。

然而，为了有用，我们希望这个操作可以应用于任何一对关系，也就是说，我们想要划分一个不是笛卡尔积的结果的关系。为此，正式定义更为复杂。

因此，假设我们有两个关系 R 和 S，分别具有属性 A 和 B，它们的划分可以定义为:

R÷S = πA-B(R) - πA-B((πA-B(R) x S) - R)

可以这样读:

πA-B(R) x S:将 R 投影到不在 S 中的 R 的属性上，并将此关系与 S 相乘(笛卡尔积)。这会产生与 R 的属性 A 和所有可能行的关系S 的行和 R 的投影的组合；

从前面的结果中减去所有原来在 R 中的元组，即执行 (πA-B(R) x S) - R。这样我们就得到了“额外”的元组，即笛卡尔积中的元组不存在于原始关系中。

最后，从原始关系中减去那些额外的元组(但同样，仅对 S 中不存在的 R 属性执行此操作)。所以，最后的运算是:πA-B(R) - πA-B(步骤 2 的结果)。

因此，以您的示例为例， r 在 D 上的投影等于:

(D)
d1
d2
d3 
d4

s 的笛卡尔积是:

(A,  B,  D)
 a1  b1  d1
 a1  b1  d2
 a1  b1  d3
 a1  b1  d4

现在我们可以从这个集合中删除同样在原始关系 r 中的元组，即前两个元组和最后一个，以便我们获得以下结果:

(A,  B,  D)
 a1  b1  d3

最后，我们可以从原始关系(再次投影到 D)中删除之前的元组(投影到 D)，即我们删除:

(D)
d3

从:

(D)
d1
d2
d3
d4

我们得到以下结果，这是除法的最终结果:

(D)
d1
d2
d4

最后，我们可以通过将其与原始关系 s (仅由元组 (a1, b1) 组成)相乘来双重检查结果:

(A  B  D)
 a1 b1 d1
 a1 b1 d2
 a1 b1 d4

查看原始关系 r 的行，您可以看到这个事实，这应该让您对除法运算符的含义有了重要的了解:

the only values of the column D in r that are present together with (a1, b1) (the only tuple of s), are d1, d2 and d4.

你也可以在 Wikipedia 中看到另一个例子，关于除法的详细解释，连同它的转换是 SQL，你可以看这些 slides 。