05 查询优化专项：关系代数、查询树、优化树

查询优化题经常让人慌，因为题目会说“画语法树”“画优化树”“给优化过程”。其实套路非常固定。

一、考试到底要画几棵树

看题目措辞：

• “画出原始语法树及优化后的语法树”：画 2 棵树，原始树 + 优化树。
• “写关系代数表达式，画语法树，并给优化后的表达式”：至少画 1 棵原始树；为了得满分，最好再画 1 棵优化树。
• “Draw a syntax tree ... and give a procedure for query optimization”：画原始树，然后列优化步骤；若时间允许补优化树。

推荐考场固定输出：

1. SQL 对应的原始关系代数表达式，通常用笛卡尔积。
2. 原始查询树。
3. 优化规则。
4. 优化后的查询树。
5. 优化后的关系代数表达式。

这样无论题目要求 1 棵还是 2 棵树，都能覆盖。

二、基本优化规则

最核心的规则：

1. 选择条件分解：σ_{F1 ∧ F2}(E) = σ_{F1}(σ_{F2}(E))
2. 选择下推：只涉及某个关系的选择尽早下推到该关系。
3. 投影下推：只保留最终输出属性、连接属性、选择属性。
4. 笛卡尔积 + 连接条件改写为连接。
5. 先做选择、投影，减少中间结果；避免大笛卡尔积。
6. 连接顺序要让中间结果尽量小。

三、标准例题

SQL：

SELECT p.PNO, PName, Price, StockNum
FROM Product AS p, Stock AS s
WHERE p.PNO = s.PNO
  AND StockPlace = 'Warehouse1'
  AND Price > 4;

1. 原始关系代数

题目要求“using Cartesian product equivalent to the query”，所以先写笛卡尔积：

π_{p.PNO, PName, Price, StockNum}
(
  σ_{p.PNO = s.PNO ∧ StockPlace = 'Warehouse1' ∧ Price > 4}
  (Product × Stock)
)

2. 原始查询树

π p.PNO, PName, Price, StockNum
└── σ p.PNO=s.PNO ∧ StockPlace='Warehouse1' ∧ Price>4
    └── ×
        ├── Product
        └── Stock

这棵树的特点：先做笛卡尔积，产生巨大中间结果，再筛选，效率差。

3. 优化过程

把选择条件拆开：

p.PNO = s.PNO
StockPlace = 'Warehouse1'
Price > 4

下推单表选择：

σ_{Price > 4}(Product)
σ_{StockPlace = 'Warehouse1'}(Stock)

把笛卡尔积加连接条件改为连接：

σ_{p.PNO=s.PNO}(Product × Stock)
=> Product ⋈_{p.PNO=s.PNO} Stock

投影下推：

• Product 侧保留：PNO, PName, Price
• Stock 侧保留：PNO, StockNum

4. 优化后的查询树

π PNO, PName, Price, StockNum
└── ⋈ Product.PNO = Stock.PNO
    ├── π PNO, PName, Price
    │   └── σ Price > 4
    │       └── Product
    └── π PNO, StockNum
        └── σ StockPlace = 'Warehouse1'
            └── Stock

5. 优化后的关系代数

π_{PNO, PName, Price, StockNum}
(
  π_{PNO, PName, Price}(σ_{Price > 4}(Product))
  ⋈_{Product.PNO = Stock.PNO}
  π_{PNO, StockNum}(σ_{StockPlace = 'Warehouse1'}(Stock))
)

四、画树规范

树从上到下：

• 根节点一般是最终投影 π。
• 中间是选择 σ、连接 ⋈、笛卡尔积 ×。
• 叶子是基本表。

原始树常见结构：

π
└── σ
    └── ×
        ├── R
        └── S

优化树常见结构：

π
└── ⋈
    ├── π
    │   └── σ
    │       └── R
    └── π
        └── σ
            └── S

如果有三个表，原始树：

π
└── σ
    └── ×
        ├── ×
        │   ├── R
        │   └── S
        └── T

优化树：

π
└── ⋈
    ├── ⋈
    │   ├── σ/π R
    │   └── σ/π S
    └── σ/π T

连接顺序按条件和选择率决定；考试没给统计信息时，优先把选择条件最强的关系先过滤，再连接。

五、关系代数等价变换常用公式

交换律：

R × S = S × R
R ⋈ S = S ⋈ R

结合律：

(R × S) × T = R × (S × T)
(R ⋈ S) ⋈ T = R ⋈ (S ⋈ T)

选择串接：

σ_{F1 ∧ F2}(E) = σ_{F1}(σ_{F2}(E))

投影串接：

π_A(π_{A,B}(E)) = π_A(E)

选择与投影交换：

π_A(σ_F(E)) = π_A(σ_F(π_{A ∪ attrs(F)}(E)))

意思是：投影下推时不能把选择条件需要的属性提前删掉。

选择与笛卡尔积交换：

σ_F(R × S) = σ_F(R) × S

前提是 F 只涉及 R 的属性；若只涉及 S 就下推到 S。

连接改写：

σ_{R.a=S.a}(R × S) = R ⋈_{R.a=S.a} S

六、常见扣分点

• 一开始就写连接表达式，题目明明要求“using Cartesian product”。应先写笛卡尔积原始表达式，再优化为连接。
• 原始树和优化树画成一样。
• 投影下推时删掉连接属性，如 Stock 侧删掉 PNO，导致后面无法连接。
• 选择条件没有拆分，无法下推。
• 把 Price > 4 下推到 Stock，把 StockPlace 下推到 Product，表搞反。
• 优化表达式最终输出列与 SQL 不一致。

七、答题模板

原始关系代数：
π_{输出属性}(σ_{连接条件 ∧ 单表条件1 ∧ 单表条件2}(R × S))

原始树：
π
└── σ
    └── ×
        ├── R
        └── S

优化规则：
1. 分解选择条件。
2. 将只涉及单个关系的选择下推。
3. 将笛卡尔积和连接选择转换为连接。
4. 投影下推，保留输出属性和连接属性。

优化树：
π
└── ⋈
    ├── π
    │   └── σ
    │       └── R
    └── π
        └── σ
            └── S

优化关系代数：
π_{输出属性}((π(...σ...(R))) ⋈ 条件 (π(...σ...(S))))