查询优化-逻辑优化 对于下面的关系数据库模式： Teacher (Tno, Tname, Tage, Tsex); Department(Dno, Dname, Tno); Work(Tno, Dno, Year, Salary); 数据库上的一个查询为“检索 CS 部门工资高于 15000 年龄小手 35 岁的女老师的工号和姓名”。 1.写出该查询的初始关系代数表达式(注：初始关系 代数表达式为先笛卡尔积，再选择，最后 投影的 形式)； 1. 画出初始关系代数表达式对应的查询树; 2. 使用启发式代数优化规则对该查询进行优化，画出优化的过程和最后结果。

1. 初始关系代数表达式为：
$$
\pi_{Tno, Tname}(\sigma_{Dname='CS' \wedge Salary > 15000 \wedge Tage < 35 \wedge Tsex='女'}(Teacher \bowtie_{Teacher.Tno = Work.Tno} Work \bowtie_{Work.Dno = Department.Dno} Department))
$$

2. 查询树如下图所示：

               Project(Tno, Tname)
                    |
              Select(Dname='CS' ^ Salary > 15000 ^ Tage < 35 ^ Tsex='女')
                    |
               Join(Work.Dno = Department.Dno)
               /                          \
             Join(Teacher.Tno = Work.Tno)  Scan(Department)
             /                          \
    Scan(Teacher)                Scan(Work)

3. 使用启发式代数优化规则进行优化的过程如下：

Step 1: 选择 (Select) 操作的推入

将选择操作推入到关系表 Teacher，得到以下代数表达式：
$$
\pi_{Tno, Tname}(\sigma_{Tsex='女' \wedge Tage < 35}(Teacher) \bowtie_{Teacher.Tno = Work.Tno} \sigma_{Dname='CS' \wedge Salary > 15000}(Work \bowtie_{Work.Dno = Department.Dno} Department))
$$

查询树如下：

               Project(Tno, Tname)
                    |
              Join(Teacher.Tno = Work.Tno)
              /                         \
         Select(Tsex='女' ^ Tage < 35)    Select(Dname='CS' ^ Salary > 15000)
              |                         /               \
         Scan(Teacher)             Join(Work.Dno = Department.Dno)  Scan(Department)
                                    /                          \
                              Scan(Work)                   Scan(Department)

Step 2: 投影 (Project) 操作的推入

将投影操作推入到关系表 Teacher，得到以下代数表达式：
$$
\sigma_{Tsex='女' \wedge Tage < 35}(\pi_{Tno, Tname}(Teacher) \bowtie_{Teacher.Tno = Work.Tno} \sigma_{Dname='CS' \wedge Salary > 15000}(Work \bowtie_{Work.Dno = Department.Dno} Department))
$$

查询树如下：

               Select(Tsex='女' ^ Tage < 35)
                    |
               Project(Tno, Tname)
                    |
              Join(Teacher.Tno = Work.Tno)
              /                         \
                |                    Select(Dname='CS' ^ Salary > 15000)
         Scan(Teacher)                 |
                                    Join(Work.Dno = Department.Dno)
                                    /                          \
                              Scan(Work)                   Scan(Department)

Step 3: 连接 (Join) 操作的交换

将连接操作的顺序交换，得到以下代数表达式：
$$
\sigma_{Tsex='女' \wedge Tage < 35}(\pi_{Tno, Tname}(Teacher) \bowtie_{Teacher.Tno = Department.Tno} \sigma_{Dname='CS' \wedge Salary > 15000}(Department \bowtie_{Department.Dno = Work.Dno} Work))
$$

查询树如下：

               Select(Tsex='女' ^ Tage < 35)
                    |
               Project(Tno, Tname)
                    |
              Join(Teacher.Tno = Department.Tno)
              /                         \
                |                    Select(Dname='CS' ^ Salary > 15000)
             Scan(Department)         |
                                    Join(Department.Dno = Work.Dno)
                                    /                          \
                              Scan(Work)                   Scan(Department)

最终优化后的代数表达式为：
$$
\pi_{Tno, Tname}(\sigma_{Tsex='女' \wedge Tage < 35 \wedge Dname='CS' \wedge Salary > 15000}(Teacher \bowtie_{Teacher.Tno = Department.Tno} Department \bowtie_{Department.Dno = Work.Dno} Work))
$$

对应的查询树如下：

               Project(Tno, Tname)
                    |
       Select(Tsex='女' ^ Tage < 35 ^ Dname='CS' ^ Salary > 15000)
                    |
              Join(Teacher.Tno = Department.Tno)
              /                         \
        Scan(Teacher)               Join(Department.Dno = Work.Dno)
                                    /                          \
                              Scan(Department)              Scan(Work)