关系代数 域关系演算

关系演算的第二种形式称为域关系演算( domain relational calculus ),它使用从属性域中取值的( domain )变量,而不是对于整个元组的值。尽管如此,域关系演算同元组关系演算是联系紧密的。
就像关系代数作为 SQL 语言的基础一样,域关系演算是作为 QBE 语言的理论基础。

形式化定义

关系代数 域关系演算


查询示例

我们现在对于我们在前面考虑过的示例给出域关系演算查询形式。请注意这些表达式和对应的元组关系演算表达式的相似之处。
关系代数 域关系演算


表达式的安全性

我们注意到在元组关系演算中,有可能写出会产生无限关系的表达式。这使得我们为元组关系演算表达式定义了安全性( safety )。对于域关系演算也会出现类似的情况。诸如

{<i,n,d,s> | ┓(<i,n,d,s> ∈ instructor)}

这样的表达式是不安全的,因为它允许在结果中的值并不在表达式的域中
对于域关系演算,我们还必须关注在“存在”和“对于所有的”子句中公式的形式。请考虑表达式

{< x > | ヨy(<x,y> ∈ r) ∧ ヨz(┓(<x,z> ∈ r) ∧ P(x,z))}

其中 P 是涉及 x 和 z 的某个公式。我们可以通过只考虑在 r 中的值来测试公式的第一个部分:ヨy(<x,y> ∈ r)。可是,为了测试公式的第二个部分:ヨz(┓(<x,z> ∈ r) ∧ P(x,z)),我们必须考虑并不在 r 中出现的、对于 z 的值。由于所有的关系都是有限的,并不在 r 中出现的值是无限多的。因此在通常情况下,如果不考虑对于 z 的潜在的值有无限多个,就不可能测试公式的第二个部分。事实上我们并不这样做,我们增加一些约束来限制诸如上面这样的表达式
在元组关系演算中,我们将任何存在量化的变量限制在一个特定关系的范围内。由于在域演算中我们还没有这样做,我们增加用于定义安全性的规则,以处理类似于我们示例的情况。我们认为表达式

{<x1,x2,...,xn> | P(x1,x2,...,xn)}

是安全的,如果下列条件全部成立的话:

  • 1)在表达式的元组中出现所有值均是来自于 dom ( P )的值
  • 2)对于每个形如ヨx( P1 ( x ))的“存在”子公式而言,当且仅当在 dom ( P1 )中存在一个值
    x 使 P1 ( x )为真的情况下,该子公式为真
  • 3)对于每个形如 ∀x ( P1 ( x ))的“对于所有的”子公式而言,当且仅当 P1 ( x )对于来自 dom ( P1 )的所有值 x 均为真的情况下,该子公式为真

附加规则的目的是保证我们无须测试无限多种可能性就可以完成对“存在”和“对于所有的”子公式的测试。请考虑在安全性定义中的第二条规则。要使ヨx( P1 ( x ))为真,我们只需找到一个 x 使 P1 ( x )为真。通常说来,存在无限多个值需要测试。但是,如果表达式是安全的,我们知道可以只关注来自 dom ( P1)的值。这种限制将我们必须考虑的元组减少到有限个
形如∀x ( P1 ( x ))的子公式的情况是类似的。要断言 ∀x ( P1 ( x ))为真,我们通常必须测试所有可能的值,因此我们必须检査无限多的值。跟前面一样,如果我们知道表达式是安全的,则针对来自 dom ( P1)的那些取值来测试 P1 ( x )对于我们来说就足够了。
除了我们在前面见过的不安全查询的示例之外,我们在本节的示例查询中书写的所有域关系演算表达式都是安全的。

上一篇:IJCAI 2016 DPSH 《Feature Learning based Deep Supervised Hashing with Pairwise Labels》李武军


下一篇:Java面向对象1