关系代数 - 笛卡尔积与自然连接的区别？

Question

我正在备考考试，但无法找到可靠的标准来确定是使用笛卡尔积 x 还是自然连接 |X|。

我想出了一个大致的指南：

“如果您需要投影与要连接的表中具有相同名称的属性，则必须使用 x 并声明要投影的表名： tableA.colname1 = tableB.colname1”

然而，这并不遵循我的笔记中的某些解决方案，我的讲师似乎会交替使用上述约定的 x 或 |x|。

有没有人有规则可以遵循，以定义何时使用其中之一？

---

以这个模式为例（仅涉及问题的模式）：

takes(ID, course_id, sec_id, semester, year, grade)
student(ID, name, dept_name, tot_cred)

问题：查找所有选修在2011年春季或秋季教学的学生姓名。

我的答案尝试：

π name(σ semester="Spring" ^ year=2011(takes ⋈ student)) ∪ π name(σ semester="Autumn" ^ year=2011(takes ⋈ student))

实际答案：

π name(σ semester="Spring" ^ year=2011 ^ takes.ID=student.ID(takes x student)) ∪ π name(σ semester="Autumn" ^ year=2011 ^ takes.ID=student.ID(takes x student))

有人能提供一个原因吗？

在我看来，自然连接应该处理 takes.ID=student.ID 了吧？

- Myles Gray

---

现实世界中的数据库几乎 从不 使用笛卡尔积。 - Joel Coehoorn

Joel，我不同意。我经常发现笛卡尔积在“现实世界”中非常有用。 - nvogel

@sqlvogel 我也用过它们，但这很少见。 - Joel Coehoorn

Answer 1

自然连接，据我理解，是投影、过滤的笛卡尔积：

- 取出笛卡尔积 - 筛选，使得同名列中的值相等 - 投影，从而保证所有列都有唯一的名称

在这种假设下，您的答案与实际答案同构。

为了说明这一点，您可能需要将自然连接展开到上述运算符序列，并使用关系代数定律进行浮动。您会发现由于对 `name` 进行投影，投影消失了，选择条件与上述选择合并在一起。最终你会得到与实际答案完全相同的树形结构，即使您从未改变自己答案的含义！

我可以想到一个原因，为什么您的讲师会交替使用这些概念：您的讲师希望您明白这些概念可以互换使用，因为“自然连接只是一种捷径”（虽然这是有争议的）。

- user824425

---

那么你的意思是这样的：r ⋈ s == π r.A, r.B, r.C, r.D, s.E (σ r.B = s.B ^ r.D = s.D (r x s))，比如模式为：R(A,B,C,D)和S(B,D,E)？ - Myles Gray

好的，我明白了，只是有点担心“答案”只显示了问题的一种解决方案，而实际上有两种方案，那我会被标记为不正确。 - Myles Gray

有太多可能的答案，只有最小的才能被称为正确。你的解决方案比实际解决方案更小，所以如果允许使用⋈，你的答案就是“更正确”的。不过，还有更短的解决方案。将投影浮动到集合并上，就可以节省一个运算符。 - user824425

好观点，但我也不知道。这取决于您被允许使用哪些运算符。如果不能使用逻辑析取，那么您必须使用集合并。但如果可以使用，则几乎是最短的答案。 - user824425

π name(σ (semester="Spring" ∨ semester="Autumn") ^ year=2011 (takes ⋈ student))，我想是这样的。除非您还可以测试集合成员资格，否则它将是 π name(σ (semester in {"Spring", "Autumn"}) ^ year=2011 (takes ⋈ student))。 - user824425

Answer 2

笛卡尔积只是自然连接的一个特殊情况，其中连接的关系没有任何共同的属性名。在 Codd 的原始代数中，重命名是一个完全独立的操作。如果要获得两个具有某些共同属性的关系的真正笛卡尔积，则必须在执行（自然）连接之前重命名这些属性。

为了简洁起见，有时会在书面示例中省略重命名，并使用乘号。不幸的是，这掩盖了一个重要的观点，即只有一种连接方式。

- nvogel

Answer 3

我认为有两种极端情况：

1. 内连接中没有重复行： 内连接等同于交集（我的意思是仅结果）。 去重后的内连接 ~ 交集

2. 内连接中没有共同特征： 内连接等同于笛卡尔积。

- spearous