对学生-课程数据库，查询信息系学生选修了的所有课程名称。 SELECT Cname FROM Student, Course, sC WHERE Student.Sno=SC.Sno AND SC.no=Course.Cno AND Student.Sdept='IS' 试画出用关系代数[1]表示的语法树[2]，并用关系代数表达式优化算法对原始的语法树进行优化处理，画出优化后的标准语法树。

考查要点：本题主要考查关系代数表达式与SQL语句的转换，以及关系代数优化技术的应用，包括选择下推、投影下推和连接顺序优化。

解题核心思路：

1. SQL转关系代数：将SQL的连接和投影操作转换为关系代数中的连接（⨝）和投影（π）操作，并明确连接条件。
2. 优化策略：通过选择下推减少参与连接的数据规模，通过投影下推消除冗余字段，最终调整连接顺序以提高效率。

破题关键点：

• 选择条件的位置：将WHERE Student.Sdept='IS'下推到最靠近Student表的位置，提前过滤数据。
• 投影的简化：在连接前投影出后续操作所需的字段（如Sno和Cno），减少数据传输量。

1. 原始SQL转关系代数

原SQL语句等价于以下关系代数表达式：
$\pi_{\text{Cname}} \left( (\text{Student} \bowtie_{\text{Sno}} \text{SC}) \bowtie_{\text{Cno}} \text{Course} \right)$
其中：

• 连接条件：Student.Sno = SC.Sno 和 SC.Cno = Course.Cno
• 选择条件：Student.Sdept = 'IS' 隐含在Student表中。

2. 优化步骤

选择下推

将σ_{\text{Sdept='IS'}}下推到Student表，提前过滤数据：
$\pi_{\text{Cname}} \left( (\sigma_{\text{Sdept='IS'}}(\text{Student}) \bowtie_{\text{Sno}} \text{SC}) \bowtie_{\text{Cno}} \text{Course} \right)$

投影下推

在Student ⨝ SC前投影出后续所需的字段（Sno和Cno）：
$\pi_{\text{Cname}} \left( \left( \pi_{\text{Sno,Cno}} \left( \sigma_{\text{Sdept='IS'}}(\text{Student}) \right) \bowtie_{\text{Sno}} \text{SC} \right) \bowtie_{\text{Cno}} \text{Course} \right)$

连接顺序优化

调整连接顺序，优先连接SC与Course，减少中间结果规模：
$\pi_{\text{Cname}} \left( \pi_{\text{Sno,Cno}} \left( \sigma_{\text{Sdept='IS'}}(\text{Student}) \right) \bowtie_{\text{Sno}} \text{SC} \bowtie_{\text{Cno}} \text{Course} \right)$