备战软考数据库: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. 生成序列,每一组结点是序列中的一步

Leave a Reply

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