使用元组关系微积分查找成绩最高的学生

Question

假设我有一张学生表，其中包含他们的 ID 和成绩：

-----------------
| id  |  grade  |
-----------------
|  1  |    83   |
|  2  |    94   |
|  3  |    92   |
|  4  |    78   |

我如何编写引用最高分的学生的元组关系微积分公式？

我的尝试：

从 SQL 的角度考虑，我会编写一个查询，该查询对表与自身进行笛卡尔乘积，取比其他等级低的每个等级，然后从原始表中减去。但是，在元组关系演算中，不可能在子查询中构建子表，这就是我被卡住的原因。

但是，我在这个方向尝试了一些东西：

{ <id> | ? grade1 ? students (id, grade) ? ? grade2 ? students (id, grade2) ? grade1 > grade2}

我相信这会让我获得较低的成绩，但是我如何从原始学生表中减去所有这些？我不允许将此语句插入到另一个 TRC 查询中。在此先感谢您的帮助！

Answer 1

给定模式Students(id:integer,grade:integer)，您可以使用否定运算符 ( ¬)解决元组关系演算中的问题。

{T1.id | ?T1 ? Students ¬(?T2 ? Students (T2.grade > T1.grade))}

这将返回 T1 中所有学生的 id，其中 T2 中没有更高年级的学生。

因为 T1 和 T2 来自相同的关系，这有效地返回了成绩最好的学生集。

如果最高等级没有关系，它将只返回一个 id。

看起来您正在考虑关系代数而不是元组关系演算。

元组关系演算没有集合差分运算符，因此您无法通过减去所有非最大值来找到最大值。

参考

Ragu Ramakrishnan 和 Johannes Gerke为第三版数据库管理系统编写的解决方案手册帮助我解决了这个问题。

问题 4.3 要求您使用此模式解决一些问题：

Suppliers(sid:integer,sname:string,address:string)
Parts(pid:integer,pname:string,color:string)
Catalog(sid:integer,pid:integer,cost:real)

问题 4.3.11 与您的相似。

查找名为 Yosemite Sham 的供应商提供的最昂贵零件的 pid。

解决方案如下所示：

{T | ?T1 ? Catalog(?X ? Suppliers
(X.sname = 'Yosemite Sham' ? X.sid = T1.sid) ? ¬(?S ? Suppliers
(S.sname = 'Yosemite Sham' ? ?Z ? Catalog
(Z.sid = S.sid ? Z.cost > T1.cost))) ? T.pid=T1.pid)}

这里的解决方案由于供应商和目录之间的连接而更加复杂，但解决方案的本质是相同的。

省略连接以获得这个：

T1 ? Catalog ...
(... ¬(... ?Z ? Catalog
(... Z.cost > T1.cost)))

在参考解决方案中，自由变量 T 与绑定变量 T1 具有相同的 pid。

直接取 T1 的 pid 是获得相同结果的更简单方法。