Design sort-based algorithm for computing the relational division operation 设计基于排序的算法来计算关系除法运算
伪代码如下：
// 假设存在关系R、S
// 现依它们共同的属性以相同方式排序，不妨假设这里使用升序
sortBy(R, a0, a1...)
sortBy(S, a0, a1...)
// 设置临时空间
T = []
r = R.begin
s = S.begin
// 扫描R和S中的所有关系
while r != R.end and s!= S.end:
// 比较对应行中共同的属性a0, a1...，记作common
// 如果相等
if r.common == s.common:
// 则将r计入T中
T.append(r)
// 同时更新下一位
r += 1
s += 1
// 如果不相等，则根据情况分别前进更新，尝试找完所有相等的内容
else if r.common < s.common:
// 只进R
r += 1
else:
// 否则只进S
s += 1
// 对T根据R剩下的属性（不与S共有的部分）进行group by
// G是一系列分组的集合
G = group_by(T, R.uncommon)
// 对于一个分组，若它的大小等于S，即它在公共属性上仅包含S的所有行，则认为是满足除法运算要求的结果
for g in G:
if g.count == S.count:
print(g)
a. 证明：
因为$σ_{θ_1\wedgeθ_2\wedgeθ_3}(E) = σ_{θ_1\wedgeθ_2}(σ_{θ_3}(E))$
又因为$σ_{θ_1\wedgeθ_2}(σ_{θ_3}(E))=σ_{θ_1}(σ_{θ_2}(σ_{θ_3}(E)))$
故$σ_{θ_1\wedgeθ_2\wedgeθ_3}(E) = σ_{θ_1}(σ_{θ_2}(σ_{θ_3}(E)))$
b. 证明：
因为$σ_{θ_1\wedgeθ_2}(E_1\bowtie_{θ_3}E_2) =σ_{θ_1}(σ_{θ_2}(E_1\bowtie_{θ_3}E_2) )$
由于$θ_2$只与$E_2$中的元素相关，由分配关系所以：
$σ_{θ_1}(σ_{θ_2}(E_1\bowtie_{θ_3}E_2) = σ_{θ_1}(E_1\bowtie_{θ_3}(σ_{θ_2}(E_2)))$
故$σ_{θ_1\wedgeθ_2}(E_1\bowtie_{θ_3}E_2) = σ_{θ_1}(E_1\bowtie_{θ_3}(σ_{θ_2}(E_2)))$