Tag Archives: relational algebra

备战软考数据库:8.4 关系代数表达式的优化

关系代数表达式的优化

示例,设关系R(A,B)和关系S(C,D)都是二元关系,下面三个查询是等价的,但是效率却不同:

  1. E_1=pi_A(sigma_{B=Cwedge D=text{'99'}}(R times S))
  2. E_2=pi_A(sigma_{B=C}(Rtimes sigma_{D=text{'99'}}(S)))
  3. E_3=pi_A(Runderset{B=C}{bowtie} sigma_{D=text{'99'}}(S))

关系代数表达式的等价变换规则

  1. 联接和笛卡尔积的交换律:
    E_1,E_2是关系代数表达式,F是联接条件
    E_1underset{F}{bowtie} E_2equiv{E_2}underset{F}{bowtie} E_1
    E_1 bowtie E_2 equiv E_2 bowtie E_1
    E_1 times E_2 equiv E_2 times E_1
  2. 联接和笛卡尔积的结合律:
    F_1,F_2是联接条件,F_1只涉及E_1,E_2的属性,F_2只涉及E_2,E_3的属性
    (E_1 underset{F_1}{bowtie} E_2) underset{F_2}{bowtie}E_3 equiv E_1 underset{F_1}{bowtie}(E_2 underset {F_2}{bowtie} E_3)
    (E_1 bowtie E_2) bowtie E_3 equiv E_1 bowtie (E_2 bowtie E_3)
    (E_1 times E_2) times E_3 equiv E_1 times (E_2 times E_3)
  3. 投影的级联:
    L_1,dots,L_n为属性集,且满足L_1subseteq L_2subseteq dots subseteq L_n
    pi_{L_1}(pi_{L_2}(dots(pi_{L_n}(E)))equiv pi_{L_1}(E)
  4. 选择的级联:
    sigma_{F_1}(sigma_{F_2}(E))equiv sigma_{F_1wedge F_2} (E)
    sigma_{F_1}(sigma_{F_2}(E))equiv sigma_{F_2}(sigma_{F_1}(E))
  5. 选择和投影操作的交换:
    F只涉及L中的属性:
    pi_{L}(sigma_{F}(E))equiv sigma_{F}(pi_L(E))
    F还涉及不再L中的属性集L_1则:
    pi_L(sigma_F(E))equiv pi_L(sigma_F(pi_{L cup L_1}(E)))
  6. 选择对笛卡尔积的分配律:
    F只涉及E_1中的属性,则:
    sigma_F(E_1 times E_2)equiv sigma_F(E_1)times E_2
    FF_1 times F_2的形式,且F_1只涉及E_1中的属性,F_2只涉及E_2中的属性:
    sigma_F(E_1 times E_2)equiv sigma_{F_1}(E_1) times sigma_{F_2}(E_2)
    FF_1 times F_2的形式,且F_1只涉及E_1中的属性,F_2只涉及E_1,E_2中的属性:
    sigma_F(E_1 times E_2)equiv sigma_{F_2}(sigma_{F_1}(E_1)times E_2)
  7. 选择对并的分配律:
    要求E_1,E_2具有相同的属性名
    sigma_{F}(E_1 cup E_2)equiv sigma_F(E_1)cup sigma_F(E_2)
  8. 选择对差的分配律:
    要求E_1,E_2具有相同的属性名
    sigma_F(E_1-E_2)equiv sigma_F(E_1)-sigma_F(E_2)
  9. 选择对自然联接的分配律:
    F只涉及E_1,E_2的公共属性
    sigma_F(E_1 bowtie E_2)equiv sigma_F(E_1)bowtie sigma_F(E_2)
  10. 投影对笛卡尔积的分配律:
    要求L_1E_1中的属性集,L_2E_2中的属性集
    pi_{L_1 cup L_2}(E_1 times E_2)equiv pi_{L_1}(E_1) times pi_{L_2}(E_2)
  11. 投影对并的分配律:
    要求E_1,E_2具有相同的属性名
    pi_L(E_1 cup E_2)equiv (E_1)cup pi_L(E_2)
  12. 选择与联接的结合:
    sigma_F(E_1 times E_2)equiv E_1underset{F}{bowtie}E_2
    sigma_{F_1}(E_1 underset{F_2}{bowtie}E_2)equiv E_1 underset{F_1wedge F_2}{bowtie}E_2
  13. 并和交的交换律:
    E_1 cup E_2equiv E_2 cup E_1
    E_1 cap E_2 equiv E_2 cap E_1
  14. 并和交的结合律:
    (E_1 cup E_2)cup E_3equiv E_1 cup (E_2cup E_3)
    (E_1 cap E_2)cap E_3equivE_1 cap (E_2cap E_3)

关系代数表达式的启发式优化(Heuristic Optimization):

3条启发式优化规则:

  1. 尽可能早地进行选择操作
  2. 尽可能早地进行投影操作
  3. 尽量避免直接笛卡尔积

对关系代数表达式进行语法分析,得到一颗语法树,对其进行优化:

  1. 利用规则4将型为sigma_{F_1wedge dots wedge F_n}(E)的子表达式转换为选择级联形式
  2. 使用规则4-9尽可能将把选择操作往下推
  3. 对投影操作利用规则3,10,11,5往下推
  4. 使用规则3-5将选择和投影合并
  5. 对语法树的内结点进行分组
  6. 生成序列,每一组结点是序列中的一步

备战软考数据库:8.2 关系代数

关系代数

操作的分类:

  • 传统的集合操作:并、差、交、笛卡尔积(乘)、笛卡尔积逆运算(除)
  • 扩充的关系操作:投影、选择、联接

5个基本操作:

  1. 并(Union)属于R或属于S的元组,两个关系应该有相同的关系模式
    Rcup S = left{t|tin R tin Sright}
  2. 差(Difference)属于R但不属于S的元组
    R-S=left{t|t in Rwedge tnotin Sright}
  3. 笛卡尔积、乘(Cartesian Product):前r个属性来自于R,后s个属性来自于S
    Rtimes S=left{t|t =<t^r,t^s data-recalc-dims= wedge t^r in R wedge t^s in Sright}" />
  4. 投影(Projection):选择关系的某些属性并且重新排序
    pi_{i_1,dots,i_m}(R)=left{t|t=<t_{i_1},dots,t_{i_m} data-recalc-dims=wedgein Rright}" />
  5. 选择(Selection):满足某条件表达式F的元组
    sigma_{F}(R)=left{t|tin Rwedge F(t)=text{true}right}

4个组合操作:

  1. 交(Intersection):属于R又属于S的元组
    Rcap S=left{t|tin Rwedge tin Sright}
  2. theta联接(Theta Join):RS的笛卡尔积中选择属性值满足某theta操作的元组
    Runderset{itheta j}{bowtie}S = left{t|t=<t^r,t^s data-recalc-dims=wedge t^r in R wedge t^s in S wedge t_{i}^{r}theta t_{j}^{s}right}" />
    Runderset{itheta j}{bowtie}S = sigma_{itheta(r+j)}(Rtimes S)
  3. 自然联接(Natural Join):RS公共属性属性值相同的元组的组合,公共属性值出现一次
    Rbowtie S = pi_{i_1,dots,i_m}(sigma_{R.{A_1}=S.{A_1}wedge dots wedge R.{A_k}=S.{A_k}}(Rtimes S))
    若无公共属性,则为笛卡尔积
  4. 除(Division):
    T=pi_{1,2,dots,r-s}(R)
    W = (Ttimes S) - R
    V = pi_{1,2,dots,r-s}(W)
    Rdiv S = T - V
    Rdiv S=pi_{1,2,dots,r-s}(R)-pi_{1,2,dots,r-s}((pi_{1,2,dots,r-s}(R)times S)-R)

示例:

  • 教师 T(T#, TNAME, TITLE)
  • 课程 C(C#, CNAME, T#)                        T#为外键
  • 学生 S(S#, SNAME, AGE, SEX)
  • 选课 SC(S#,C#,SCORE)
  1. 学习课程号为C2的学生的学号与成绩:
    pi_{text{S#,SCORE}}(sigma_{text{C#='C2'}}(SC))
  2. 学习课程号为C2的学生的学号与姓名:
    pi_{text{S#,SCORE}}(sigma_{text{C#='C2'}}(Sbowtie SC))
  3. 至少选修一门LIU老师的课的学生的学号与姓名:
    pi_{text{S#,SNAME}}(sigma_{text{TNAME='LIU'}}(Sbowtie SCbowtie Cbowtie T))
  4. 选修课程号为C2或C4的学生学号:
    pi_{text{S#}}(sigma_{text{C#='C2'}vee text{C#='C4'}}(SC))
  5. 至少选修了课程号C2和C4的学生的学号:
    pi_1(sigma_{1=4wedge text{2='C2'}wedge text{5='C4'}}(SCtimes SC))
  6. 没有选C2的学生姓名和年龄:
    pi_{text{SNAME,AGE}}(S)-pi_{text{SNAME,AGE}}(sigma_{text{C#='C2'}}(Sbowtie SC))
  7. 学习全部课程的学生姓名:
    查询学生选课情况操作为:pi_{text{S#,C#}}(SC)
    查询全部课程操作为:pi_{text{C#}}(C)
    学了全部课程的学生的学号,用除法操作:pi_{text{S#,C#}}(SC)div pi_{text{C#}}(C)
    最后再用自然联接和投影获得学生的姓名:pi_{text{SNAME}}(S bowtie{pi_{text{S#,C#}}}(SC)div pi_{text{C#}}(C))

2个扩充操作:

  1. 外联接(Outer Join):在做自然联接时,把应该舍弃的元组也放到新关系中,并且在这些元组的新增加属性上插入null值
    还有左外联接和右外联接,分别只保留一侧关系中应该舍弃的元组到新关系中
  2. 外并(Outer Union):两个关系可以不是相同的关系模式,新增属性插入空值