(续)选择操作的实现算法二：找到Sdept='CS'的一组元组指针，·通过这些元组指针到Student表中检索·并对得到的元组检查另一些选择条件（如Sage>20）是否满足●把满足条件的元组作为结果输出。数据库系统概论An Introduction to Database System
An Introduction to Database System 选择操作的实现（续） ◼ 算法二：找到Sdept=’CS’的一组元组指针， ⚫ 通过这些元组指针到Student表中检索 ⚫ 并对得到的元组检查另一些选择条件(如Sage>20)是否满足 ⚫ 把满足条件的元组作为结果输出
2.连接操作的实现连接操作是查询处理中最耗时的操作之一心本节只讨论等值连接（或自然连接）最常用的实现算法[例9.2]SELECTFROMStudent,ScWHEREStudent.Sno=SC.Sno;活店AnIntroductiontoDatabaseSystem
An Introduction to Database System 2.连接操作的实现 ❖连接操作是查询处理中最耗时的操作之一 ❖本节只讨论等值连接(或自然连接)最常用的实现 算法 ❖[例9.2] SELECT * FROM Student, SC WHERE Student.Sno=SC.Sno;
(续）连接操作的实现（1）嵌套循环算法(nestedloopjoin)（2）排序-合并算法(sort-mergejoin或mergejoin（3）索引连接(indexjoin)算法数据库系统概论（4）HashJoin算法AnIntroductiontoDatabaseSystem
An Introduction to Database System 连接操作的实现（续） （1）嵌套循环算法(nested loop join) （2）排序-合并算法(sort-merge join 或merge join) （3）索引连接(index join)算法 （4）Hash Join算法
(续)连接操作的实现（1）嵌套循环算法(nestedloopjoin）对外层循环(Student表）的每一个元组（s），检索内层循环（SC表）中的每一个元组（Sc)检查这两个元组在连接属性（Sno)上是否相等如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止。*参见爱课程网9.1节动画《连接操作的实现（1)--嵌套循环》SRAnIntroductiontoDatabaseSystem
An Introduction to Database System 连接操作的实现（续） （1）嵌套循环算法(nested loop join) ◼ 对外层循环(Student表)的每一个元组(s)，检索内层循 环(SC表)中的每一个元组(sc) ◼ 检查这两个元组在连接属性(Sno)上是否相等 ◼ 如果满足连接条件，则串接后作为结果输出，直到外 层循环表中的元组处理完为止。 ❖参见爱课程网9.1节动画《连接操作的实现(1)-嵌 套循环》
(续）连接操作的实现（2）排序-合并算法（sort-mergejoin或mergejoin)如果连接的表没有排好序，先对Student表和Sc表按连接属性Sno排序取Student表中第一个Sno，依次扫描Sc表中具有相同Sno的元组当扫描到Sno不相同的第一个SC元组时，返回Student表扫描它的下一个元组，再扫描sc表中具有相同Sno的元组，把它们连接起来重复上述步骤直到Student表扫描完AnIntroductiontoDatabaseSystem
An Introduction to Database System 连接操作的实现（续） （2）排序-合并算法(sort-merge join 或merge join) ◼ 如果连接的表没有排好序，先对Student表和SC表按 连接属性Sno排序 ◼ 取Student表中第一个Sno，依次扫描SC表中具有相 同Sno的元组 ◼ 当扫描到Sno不相同的第一个SC元组时，返回 Student表扫描它的下一个元组，再扫描SC表中具有 相同Sno的元组，把它们连接起来 ◼ 重复上述步骤直到Student 表扫描完