关系代数中的除

• 本文约 389 字,阅读大致需要 1 分钟 | Development

简单记一笔,感谢 Stanford 的 数据库入门 课程课后作业 (有人在 StackOverflow提问)。复习一下。

应用场景:找出一家能制作全部30岁以上人士需要的Pizza种类的Pizza店。

在示范数据库中给出的四个关系:

Person(name, age, gender)       // name is a key
Frequents(name, pizzeria)       // [name,pizzeria] is a key
Eats(name, pizza)               // [name,pizza] is a key
Serves(pizzeria, pizza, price)  // [pizzeria,pizza] is a key

通过一些计算,我们可以得到两个投影:

投影 A:

1
2
3
4
5
6
Chicago Pizza | cheese  | cheese
Chicago Pizza | cheese  | supreme
Chicago Pizza | supreme | cheese
Chicago Pizza | supreme | supreme
Dominos       | cheese  | cheese
Dominos       | cheese  | supreme

投影 B:

cheese  | cheese
cheese  | supreme
supreme | cheese
supreme | supreme

需要的结果是 A/B:

Chicago Pizza

有时,数据库系统并不直接提供关系除操作。这时可以用下面的方法替代:

首先,生成所有 Pizza 店,以及所有 Pizza 类型的笛卡尔积,记为T:

然后,计算该笛卡尔积和 Serves 上的投影R: π{pizzeria,pizza}(Serves) 之差:T-R。

这样,T-R得到的结果便是不存在的 pizzeria,pizza 组合。从其中取 π{pizzeria},然后从全部 pizzeria 中扣掉,即可得到希望的结果了。