数据库技术与应用教程中的一个简单例子

2023-11-24 理论教育版权反馈

【摘要】：首先通过一个简单的例子来看一下查询优化的必要性。设每块能装10个元组，则写出这些块要用5×104s。满足条件的元组假设仅50个，均可放在内存中。因此，第1种情况下执行查询的总时间≈105＋2×5×104≈105。自然连接的结果比广义笛卡儿积减少了很多，为104个，所以写出这些元组的时间为50s，仅为第1种情况的千分之一。总的存取时间将进一步减少到数秒。

首先通过一个简单的例子来看一下查询优化的必要性。

设学生选课库的关系模式为

学生（学号，姓名，年龄，所在系）；

选课（学号，课程号，成绩）。

求选修了C1号课程的学生姓名，用SQL语言表达如下：

SELECT学生，姓名

FROM学生，选课

WHERE学生.学号＝选课.学号AND选课.课程号＝’C1’；

假定学生选课库中有1000个学生记录，10000个选课记录，其中选修C1号课程的选课记录有50个。这个查询系统可以用多种等价的关系代数表达式来完成。

这里列出其中3种：

pagenumber_ebook=40,pagenumber_book=34

下面分析这3种查询的策略，看看策略的不同会对查询的时间效率产生怎样的影响。

1.第1种情况

（1）计算广义笛卡儿积

把学生和选课的每个元组连接起来。连接的做法一般是这样的：在内存中尽可能多地装入某个表（如学生表）的若干块元组，留出一块存放另一个表（如选课表）的元组。然后把选课中的每个元组和学生中的每个元组连接，连接后的元组装满一块后就写到中间文件上，再从选课中读入一块和内存中的学生元组连接，直到选课表处理完。这时再一次读入若干块学生元组，读入一块选课元组。重复上述处理过程，直到把学生表处理完。

设一个块能装10个学生元组或100个选课元组，在内存中存放5块学生元组和一块选课元组，则读取总块数为

pagenumber_ebook=41,pagenumber_book=35 (www.chuimin.cn)

其中读学生表100块。读选课表20遍，每遍100块。若读写20块/s，则总计要花105s。

连接后的元组数为103×104＝107。设每块能装10个元组，则写出这些块要用5×104s。

（2）进行选择操作

依次读入连接后的元组，按照选择条件选取满足要求的记录。假定内存处理时间忽略，这一步读取中间文件花费的时间（同写中间文件一样）需5×104s。满足条件的元组假设仅50个，均可放在内存中。

（3）进行投影操作

把第（2）步的结果在姓名上做投影输出，得到最终结果。

因此，第1种情况下执行查询的总时间≈105＋2×5×104≈105（s）。这里，所有内存处理时间忽略不计。

2.第2种情况

（1）计算自然连接花费的时间。执行自然连接仍需读取学生和选课表，因此读取块数仍为2100块，花费时间为105 s。自然连接的结果比广义笛卡儿积减少了很多，为104个，所以写出这些元组的时间为50s，仅为第1种情况的千分之一。

（2）执行选择运算花费时间。执行选择运算花费时间为50s。

（3）把第（2）步结果投影输出。第2种情况总的执行时间≈105＋50＋50≈205（s），比第1种情况大大减少。

3.第3种情况

（1）先对选课表作选择运算。只需读一遍选课表，存取100块花费时间为5 s，因为满足条件的元组仅50个，不必使用中间文件。

（2）读取学生表。把读入的学生元组和内存中的选课表进行连接。同样只需读一遍学生表（共100块）花费时间为5 s。

（3）把连接结果投影输出。第3种情况总的执行时间≈（5＋5）s≈l0s，比第2种情况又减少了很多。

如果在选课表的课程号上建有索引，则第1步就不必读取所有的选课元组，而只需读取课程号＝’C1’的那些元组（50个）。存取的索引块和选课表中满足条件的数据块总共3～4块。如果学生表在学号上也建有索引，则第2步也不必读取所有的学生元组，因为满足条件的选课记录只有50个，最多涉及50个学生记录，因此读取学生表的块数也可大大减少。总的存取时间将进一步减少到数秒。

数据库技术与应用教程中的一个简单例子

相关推荐