备战软考数据库:8.3 关系演算

关系演算

把谓词演算加入到关系运算中即是关系演算为基础的运算,又分:元组关系演算和域关系演算。

元组关系演算(Tuple Relational Calculus)

  • 变量为元组
  • 元组表达式的一般形式为:
    left{t|P(t)right}t为元组变量,P为公式(谓词)
    整个表达式表示满足Pt的集合

原子(Atoms)有三种形式:

  1. R(s)
    元组s是关系R的一个元组
  2. s[i]theta u[j]
    元组s的第i个属性值与元组u的第j个属性值之间满足关系theta
    例如:s[1]<u[2]
  3. s[i]theta a
    元组s的第i个属性值与常数a之间满足关系theta
    例如:s[2]=5

公式(formula)定义如下:

  1. 每个原子都是一个公式
  2. P_1,P_2是公式,则neg P_1,P_1wedge P_2,P_1 vee P_2,P_1Rightarrow P_2也是公式
  3. P_1是公式,则(exists s)P_1,(forall s)P_1也是公式

公式中运算符的优先级别(高到低):theta  data-recalc-dims=exists forall >neg > wedge vee > Rightarrow" />

转换规则:

  1. P_1wedge P_2等价于neg(neg P_1 vee neg P_2)
    P_2vee P_2等价于neg(neg P_1 wedge neg P_2)
  2. (forall s)(P_1(s))等价于neg (exists s)(neg P_1(s))
    (exists s)(P_1(s))等价于neg(forall s)(neg P_1(s))
  3. P_1 Rightarrow P_2等价于neg P_1 vee P_2

关系代数表达式到元组表达式的转换

  1. Rcup Sleft{t| R(t)vee S(t)right}表示
  2. R-Sleft{t|R(t)wedge neg S(t)right}表示
  3. Rtimes Sleft{t|(exists u)(exists v)(R(u)wedge S(v)wedge t[1]=u[1]wedge{t[2]}=u[2]wedge t[3]=u[3]wedge t[4]=v[1]wedge t[5]=v[2]wedge t[6]=v[3]wedge)right}
    (假设R,S的元数均为3)
  4. pi_{2,3}(R)left{t|(exists u)(R(u)wedge t[1]=u[2]wedge t[2]=u(3))right}表示
  5. sigma_{F}(R)left{t|R(t)wedge F'right}表示,F'F的等价表示形式

之前例子中的关系代数表达式转化示例:

  1. 学习课程号为C2的学生的学号与姓名:
    pi_{text{S#,SCORE}}(sigma_{text{C#='C2'}}(Sbowtie SC))
    left{t|(exists u)(exists v)(S(u)wedge SC(v)wedge v[2]='C2'wedge u[1]=v[1]wedge t[1]=u[1]wedge t[2]=u[2])right}
  2. 选修课程号为C2或C4的学生学号:
    pi_{text{S#}}(sigma_{text{C#='C2'}vee text{C#='C4'}}(SC))
    left{t|(exists u)(SC(u)wedge (u[2]='C2'vee u[2]='C4')wedge t[1]=u[1])right}

域关系演算(Domain Relational Calculus)

  • 变量为域
  • 域演算表达式的形式:
    left{t_1,t_2,dots,t_k|P(t_1,dots,t_k)right}

原子的两种形式

  1. R(x_1,dots,x_k)k元关系R,其中x_i是常量或域变量
  2. xtheta yx,y是常量或域变量,theta是算术比较符

公式:

也可以包含各种逻辑运算符,也可以包括全称量词和存在量词

元组表达式到与表达式的转换:

转换规则:

  1. 对于k元的元组变量,可引入k个域变量t_1,dots,t_k,原公式中的tt_1,t_2,dots,t_k替换,元组分量t[i]t_i替换
  2. 对于每个量词(exists u),(forall u),若um元的元组变量,引入m个新的域变量u_1,dots,u_m,在原公式量词的辖域内的uu_1,dots,u_m替换,u[i]u_i替换,(exists u)(exists u_1),dots,(exists u_m)替换,(forall u)(forall u_1),dots,(forall u_m)替换

之前例子中的关系代数表达式转化示例:

  1. 学习课程号为C2的学生的学号与姓名:
    关系代数表达式:pi_{text{S#,SCORE}}(sigma_{text{C#='C2'}}(Sbowtie SC))
    元组表达式:left{t|(exists u)(SC(u)wedge (u[2]='C2'vee u[2]='C4')wedge t[1]=u[1])right}
    域演算表达式:left{t_1 t_2|(exists u_1)(exists u_2)(exists u_3)(exists u_4)(exists v_1)(exists v_2)(exists v_3)(S(u_1 u_2 u_3)wedge SC(v_1 v_2 v_3)wedge v_2 = 'C2' wedge u_1 = v_1 wedge t_1 = u_1 wedge t_2 = u_2)right}
    可简化为:left{t_1 t_2|(exists u_3)(exists u_4)(exists v_3)(S(t_1 t_2 u_3 u_4)wedge SC(t_1 'C2' v_3))right}

关系运算的等价性:关系代数、安全的元组关系演算和安全的域关系演算在关系的表达和操作能力上是完全等价的

Leave a Reply

Your email address will not be published. Required fields are marked *