quantifiers - 受量词约束的元组变量能否出现在“|”的左侧 在元组关系演算中？

Question

引用元组关系演算的一般表达式（数据库系统基础 - Elmasri，Navathe；第 6 版）

元组关系演算的一般表达式是

{t1.Aj, t2.Ak, ..., tn.Am | COND(t1, t2, ..., tn, tn+1, tn+2, ..., tn+m)}

其中 t1, t2, ..., tn, tn+1, ..., tn+ m是元组变量，每个Ai是ti范围的关系的属性，COND是元组关系演算的条件或公式。公式由谓词演算原子组成，可以是以下之一：

1. R(ti) 形式的原子，其中 R 是关系名称，ti 是元组变量。该原子将元组变量 ti 的范围标识为名称为 R 的关系。如果 ti 是关系 R 中的元组，则计算结果为 TRUE，否则计算结果为 FALSE。

2. ti.A op tj.B 形式的原子，其中 op 是集合 {=, <, ≤, >, ≥, ≠} 中的比较运算符之一，ti 和 tj 是元组变量，A 是ti 范围的关系的属性，B 是 t 范围的关系的属性。ti.A op c 或 c op tj.B 形式的原子，其中 op 是集合 {=, <, ≤, >, ≥, ≠} 中的比较运算符之一，ti 和 tj 是元组变量，A是ti 范围的关系的属性，B 是tj 范围的关系的属性，c 是常数值。

*编辑（感谢philipxy）：TRC中关于上述一般表达式的查询的含义是，

对于 {t|p}--“这种查询的结果是所有将 COND(t) 评估为 TRUE 的元组 t 的集合”。对于 {t.a1,t.a2,...|p}--“我们首先为每个选定的元组 t 指定请求的属性 […]。然后我们指定选择条形后面的元组的条件”。

也有提到，

元组关系演算表达式中唯一的自由元组变量应该是出现在条形 (|) 左侧的那些。

---

例如，考虑一个关系 Students(id, Grade)，我们想找到“所有获得最高成绩的学生的 id”。元组关系演算中指定的查询可以是

Q1 = {s1. 编号 | 学生(s1) ^ ¬(∃ s2, 学生(s2) ^ ( s2.grade > s1.grade) )}

这里，s1 是自由变量。

Q1 可以解释为元组变量 s1 的所有 id 值，其中 s1 范围在关系 student 内（即 s1 属于学生）并且不存在变量 s2 使得 s2 属于学生并且 s2.grade > s1.grade。

考虑查询，

Q2 = {s1。编号 | ∃ s1, 学生(s1) ^ ¬(∃ s2, 学生(s2) ^ ( s2.grade > s1.grade) )}

和

Q3 = {s1。编号 | ∀ s1, 学生(s1) ^ ¬(∃ s2, 学生(s2) ^ ( s2.grade > s1.grade) )}

正如我们所见，Q2 和 Q3 中的 s1（条形左侧的变量）也分别以 ∃ 和 ∀ 为界。

假设 Q2 和 Q3 甚至是可能的，那么 Q2 和 Q3 的解释与 Q1 有何不同？

---

笔记：

• 查询 Q2 和 Q3 由 Q1 组成，目的是试图了解如果“|”左侧的变量，查询将意味着什么 受存在量词或全称量词的约束。
• （编辑，多想后）我对 Q2 和 Q3 的解释是 Q2 和 Q1 的结果将相同不会相同，因为 Q2 会产生所有s1 的 id 值，如果存在至少一个属于 student 的 s1 并且不存在 s2 使得 s2 属于 student 并且 s2.grade > s1.grade （意思是，Q2 的结果是“所有学生的集合id 如果至少有一个学生获得了最高分”）。Q3 将产生 s1 的所有 id 值，如果对于每个属于 student 且不存在 s2 的 s1 使得 s2 属于 student 并且 s2.grade > s1.grade （意思是，Q3 的结果是“集合如果每个学生都获得最高分，则所有学生 id”）。但是，我不确定查询 Q2 和 Q3 是否可能，或者即使一般情况下可能会出现条形左侧的变量也受量词限制的情况。

标签： quantifierstuple-relational-calculus