关系代数中的除

• 本文约776字,阅读大致需要2分钟 • 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:

投影B:

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

需要的结果是A÷BA \div B:

Chicago Pizza

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

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

然后,计算该笛卡尔积和Serves上的投影R=Πpizzeria,pizza(Serves)R = \Pi_{\mathrm{pizzeria},\mathrm{pizza}}(\mathrm{Serves})之差:T−RT - R。

这样,T−RT - R得到的结果便是不存在的pizzeria, pizza组合。从其中取Πpizzeria(T−R)\Pi_{\mathrm{pizzeria}}(T - R),然后从全部pizzeria(即Πpizzeria(Serves)\Pi_{\mathrm{pizzeria}}(\mathrm{Serves}))中扣掉,即可得到希望的结果:

Πpizzeria(Serves)−Πpizzeria(T−R)\Pi_{\mathrm{pizzeria}}(\mathrm{Serves}) - \Pi_{\mathrm{pizzeria}}(T - R)