语法树专题

第 1 题：基础双表连接

【题目描述】

• 表结构：学生表 $Student(Sno, Sname, Sage)$，选课表 $SC(Sno, Cno, Grade)$
• SQL 语句：

SELECT Grade
FROM Student, SC
WHERE Student.Sno = SC.Sno 
  AND Sname = '张三';

【1. 未优化语法树】

• 逻辑：先笛卡尔积，再统一筛选。

     [π] Grade
         |
     [σ] Student.Sno=SC.Sno ∧ Sname='张三'
         |
     [×] 笛卡尔积
     /      \
Student      SC

【2. 优化后语法树】

• 逻辑：Sname 条件下沉，$\times$ 变 $\bowtie$。

       [π] Grade
           |
       [⋈] (Student.Sno = SC.Sno)
       /      \
    [σ]        SC
Sname='张三'
     |
  Student

---

第 2 题：经典三表连接

【题目描述】

• 表结构：职工 $Emp(Eno, DeptNo)$，部门 $Dept(DeptNo, Dname)$，项目 $Project(Pno, Eno)$
• SQL 语句：

SELECT Pno
FROM Emp, Dept, Project
WHERE Emp.DeptNo = Dept.DeptNo
  AND Project.Eno = Emp.Eno
  AND Dname = '研发部';

【1. 未优化语法树】

• 逻辑：三表强行笛卡尔积，顶层做大筛选。

              [π] Pno
                  |
              [σ] (选择)
Emp.DeptNo=Dept.DeptNo ∧ Project.Eno=Emp.Eno ∧ Dname='研发部'
                  |
              [×] (笛卡尔积)
              /     \
         [×]       Project
        /   \
     Emp    Dept

【2. 优化后语法树】

• 逻辑：先筛 Dept，再向上逐层连接。

     [π] Pno
         |
     [⋈] (Project.Eno = Emp.Eno)
     /    \
Project   [⋈] (Emp.DeptNo = Dept.DeptNo)
          /    \
        Emp    [σ] Dname='研发部'
                  |
                 Dept

---

第 3 题：涉及多表的多重筛选

【题目描述】

• 表结构：订单 $Order(Ono, Cno, Date)$，客户 $Customer(Cno, City)$
• SQL 语句：

SELECT Ono, Date
FROM Order, Customer
WHERE Order.Cno = Customer.Cno
  AND City = '上海'
  AND Date > '2023-01-01';

【1. 未优化语法树】

              [π] Ono, Date
                   |
              [σ] (选择)
Order.Cno=Customer.Cno ∧ City='上海' ∧ Date>'2023-01-01'
                   |
              [×] (笛卡尔积)
              /      \
         Order     Customer

【2. 优化后语法树】

• 逻辑：两边各筛各的（Order筛日期，Customer筛城市），最后再连接。

           [π] Ono, Date
                |
           [⋈] (Order.Cno = Customer.Cno)
           /           \
       [σ]              [σ]
Date>'2023-01-01'     City='上海'
        |                |
      Order           Customer

---

第 4 题：投影与选择的结合

【题目描述】

• 表结构：教师 $T(Tno, Tname)$，课程 $C(Cno, Cname, Tno)$
• SQL 语句：

SELECT Tname
FROM T, C
WHERE T.Tno = C.Tno
  AND Cname = '数据库';

【1. 未优化语法树】

        [π] Tname
            |
        [σ] (选择)
T.Tno = C.Tno ∧ Cname='数据库'
            |
        [×] (笛卡尔积)
        /      \
       T        C

【2. 优化后语法树】

• 逻辑：Cname 条件下沉。

 [π] Tname
    |
 [⋈] (T.Tno = C.Tno)
 /      \
T       [σ] Cname='数据库'
           |
           C

---

第 5 题：逻辑推导（传递性）

【题目描述】

• 表结构：表 $A(a1, a2)$，表 $B(b1, b2)$
• SQL 语句：

SELECT a1
FROM A, B
WHERE A.a2 = B.b2
  AND A.a2 > 100;

【1. 未优化语法树】

• 注意：这里只写 SQL 原话。

       [π] a1
          |
       [σ] (选择)
A.a2 = B.b2 ∧ A.a2 > 100
          |
       [×] (笛卡尔积)
       /      \
      A        B

【2. 优化后语法树】

• 逻辑：既然 A.a2=B.b2 且 A.a2>100，那么 B.b2 一定也大于 100。利用这个隐含条件，把 B 表也先筛一遍。

     [π] a1
       |
     [⋈] (A.a2 = B.b2)
     /      \
  [σ]        [σ] <--- 关键加分点
a2 > 100   b2 > 100
   |          |
   A          B

---

总结

1. 怎么画“未优化树”？

考试时，未优化的树是送分题，一定要画成**“倒挂的T型结构”**：

1. 底部：把所有表列出来。
2. 连接：用 $\times$ 把它们全部连起来。
3. 中间：在最上面的 $\times$ 头上画一个 $\sigma$，把 WHERE 后面所有的条件抄进去。
4. 顶部：画一个 $\pi$，写上 SELECT 后面的列名。

2. 怎么画“优化树”？

1. 分家：把 $\sigma$ 里的条件拆开。
2. 下沉：
   • 如果是 Table.Col = 'Value' 这种条件，直接沉到对应的表头顶。
   • 如果是 A.id = B.id 这种连接条件，变成 $\bowtie$，放在 A 和 B 汇合的地方。
3. 推导：如果看到 A=B 且 A>10，记得给 B 也加上 B>10 的筛选。

---

👉 点击这里阅读下一篇：《2022 卷综合题练习》