关系代数中的项目和限制
Project and restrict in relational algebra
下面使用的 SELECT 和 PROJECT 运算符的定义可以在 "Relational Database Design and Implementation" 的第 6 章中找到，第 4 版，Harrington，Jan L。
PROJECT（resp. RESTRICT）的 SQL 等价物是 SELECT（resp. WHERE 带有谓词以减少关系中元素的数量）。在您建议的符号中（感谢您这样做）让我们使用 b_pred 将谓词 "pred" 应用于关系以减少其元素。然后 a(b_pred(relation))=b_pred(a(relation)) 当且仅当 b_pred 不消除支持谓词 "pred" 的列。此外，如果 b_pred 使用被 a 删除的列，则 RHS 表达式不正确。
问题：先执行RESTRICT操作，结果总是正确的吗？如果能有该声明的正式证明，那就太好了。
跟进：为什么我们会对考虑相反的操作顺序感兴趣？我猜性能是唯一可能的原因，但我不确定。
感谢您的回复！
可用于更改保持表达式语义的限制和投影顺序的两个规则如下：
πY(σΦX(E))=σΦX(πY(E)), 如果 X ⊆ Y
否则，如果条件涉及属性X⊈Y：
πY(σΦX(E))=πY(σΦX(πXY(E)))
其中 E 是与一组属性产生关系的任何关系表达式，包括 X 和 Y，πX(E) 是 E 在属性集 X 和 σΦX[ 上的投影=134=](E) 是对 E 的限制，条件为 ΦX 对属性集 X.
这两条规则是等价规则，可以双向应用。通常，如果可能，优化器会尝试在任何其他操作之前应用限制，而不是在连接之前应用投影。
已添加
第一条规则说，如果你与属性 Z = Y ∪ W 有关系，对 Y 的属性子集执行限制，然后将结果投影到 Y 上，相当于先执行投影，然后是限制。
这个等价性可以用下面的方式证明。
给定 E 与属性 Z = Y ∪ W 的关系，限制的定义是：
σΦX(E) = { t | t ∈ E ∧ X ⊆ Z ∧ ΦX(t) }
即满足ΦX(t)为真的E的所有元组的集合。
投影的定义是：
πY(E) = { t1 | t ∈ E ∧ Y ⊆ Z ∧ t1 = t[Y] }
这是通过考虑得到的元组集合，对于E的每个元组t，一个（子）元组只包含t的属性Y。
所以，
πY(σΦX(E))=πY(E') =
{ t1 | t ∈ E' ∧ Y ⊆ Z ∧ t1 = t[Y] }
其中 E' = σΦX(E) = { t | t ∈ E ∧ X ⊆ Z ∧ ΦX(t) }
结合这两个公式，我们得到：
πY(σΦX(E)) = { t1 | t ∈ E ∧ X ⊆ Z ∧ ΦX(t) ∧ Y ⊆ Z ∧ t1 = t[Y] }
但是因为我们知道 X ⊆ Y，我们可以将公式重写为：
πY(σΦX(E)) = { t1 | t ∈ E ∧ X ⊆ Y ⊆ Z ∧ ΦX(t) ∧ t1 = t[Y] } [1]
从另一学期开始，
σΦX(πY(E)) = σΦX(E'') = { t | t ∈ E'' ∧ X ⊆ Z ∧ ΦX(t) }
其中 E'' = πY(E) = { t1 | t ∈ E ∧ Y ⊆ Z ∧ t1 = t[Y] }
同样，结合这两个公式并注意 X ⊆ Y，我们得到：
σΦX(πY(E)) = { t1 | t ∈ E ∧ X ⊆ Y ⊆ Z ∧ ΦX(t1) ∧ t1 = t[Y] } [2]
[1] = [2] 如果我们可以证明 ΦX(t) = ΦX(t[Y])，这是真的，因为两个条件同时为真或假，给定条件仅涉及属性 X，它同时存在于 t 和 t[Y] 中（因为 X ⊆ Y）。
第二条规则说，如果你有一个关系，属性Z = X ∪ Y ∪ W，X - Y ≠ ∅ 对X的属性进行限制，然后将结果投影到Y，是相当于先对属性 X ∪ Y 进行投影，然后进行约束，最后对属性 X 进行新的投影。
在这种情况下，也可以通过与上述证明类似的方式进行推理，给出正式证明，但为了简洁起见，此处省略。
下面使用的 SELECT 和 PROJECT 运算符的定义可以在 "Relational Database Design and Implementation" 的第 6 章中找到，第 4 版，Harrington，Jan L。
PROJECT（resp. RESTRICT）的 SQL 等价物是 SELECT（resp. WHERE 带有谓词以减少关系中元素的数量）。在您建议的符号中（感谢您这样做）让我们使用 b_pred 将谓词 "pred" 应用于关系以减少其元素。然后 a(b_pred(relation))=b_pred(a(relation)) 当且仅当 b_pred 不消除支持谓词 "pred" 的列。此外，如果 b_pred 使用被 a 删除的列，则 RHS 表达式不正确。
问题：先执行RESTRICT操作，结果总是正确的吗？如果能有该声明的正式证明，那就太好了。
跟进：为什么我们会对考虑相反的操作顺序感兴趣？我猜性能是唯一可能的原因，但我不确定。
感谢您的回复！
可用于更改保持表达式语义的限制和投影顺序的两个规则如下：
πY(σΦX(E))=σΦX(πY(E)), 如果 X ⊆ Y
否则，如果条件涉及属性X⊈Y：
πY(σΦX(E))=πY(σΦX(πXY(E)))
其中 E 是与一组属性产生关系的任何关系表达式，包括 X 和 Y，πX(E) 是 E 在属性集 X 和 σΦX[ 上的投影=134=](E) 是对 E 的限制，条件为 ΦX 对属性集 X.
这两条规则是等价规则，可以双向应用。通常，如果可能，优化器会尝试在任何其他操作之前应用限制，而不是在连接之前应用投影。
已添加
第一条规则说，如果你与属性 Z = Y ∪ W 有关系，对 Y 的属性子集执行限制，然后将结果投影到 Y 上，相当于先执行投影，然后是限制。
这个等价性可以用下面的方式证明。
给定 E 与属性 Z = Y ∪ W 的关系，限制的定义是：
σΦX(E) = { t | t ∈ E ∧ X ⊆ Z ∧ ΦX(t) }
即满足ΦX(t)为真的E的所有元组的集合。
投影的定义是：
πY(E) = { t1 | t ∈ E ∧ Y ⊆ Z ∧ t1 = t[Y] }
这是通过考虑得到的元组集合，对于E的每个元组t，一个（子）元组只包含t的属性Y。
所以，
πY(σΦX(E))=πY(E') = { t1 | t ∈ E' ∧ Y ⊆ Z ∧ t1 = t[Y] }
其中 E' = σΦX(E) = { t | t ∈ E ∧ X ⊆ Z ∧ ΦX(t) }
结合这两个公式，我们得到：
πY(σΦX(E)) = { t1 | t ∈ E ∧ X ⊆ Z ∧ ΦX(t) ∧ Y ⊆ Z ∧ t1 = t[Y] }
但是因为我们知道 X ⊆ Y，我们可以将公式重写为：
πY(σΦX(E)) = { t1 | t ∈ E ∧ X ⊆ Y ⊆ Z ∧ ΦX(t) ∧ t1 = t[Y] } [1]
从另一学期开始，
σΦX(πY(E)) = σΦX(E'') = { t | t ∈ E'' ∧ X ⊆ Z ∧ ΦX(t) }
其中 E'' = πY(E) = { t1 | t ∈ E ∧ Y ⊆ Z ∧ t1 = t[Y] }
同样，结合这两个公式并注意 X ⊆ Y，我们得到：
σΦX(πY(E)) = { t1 | t ∈ E ∧ X ⊆ Y ⊆ Z ∧ ΦX(t1) ∧ t1 = t[Y] } [2]
[1] = [2] 如果我们可以证明 ΦX(t) = ΦX(t[Y])，这是真的，因为两个条件同时为真或假，给定条件仅涉及属性 X，它同时存在于 t 和 t[Y] 中（因为 X ⊆ Y）。
第二条规则说，如果你有一个关系，属性Z = X ∪ Y ∪ W，X - Y ≠ ∅ 对X的属性进行限制，然后将结果投影到Y，是相当于先对属性 X ∪ Y 进行投影，然后进行约束，最后对属性 X 进行新的投影。
在这种情况下，也可以通过与上述证明类似的方式进行推理，给出正式证明，但为了简洁起见，此处省略。