制造信息技术_DB关系系统及其查询优化

1、现代制造信息技术基础第一部分 数据库系统概论关系系统及其查询优化,徐 世 新 北京航空航天大学 机械学院720 2002 年 7 月,主要内容,关系系统 关系系统的定义 关系系统的分类 全关系系统的十二条准则*,关系数据库系统的查询优化 关系系统及其查询优化 一个实例 查询优化的一般准则 关系代数等价变换规则 关系代数表达式的优化算法 优化的一般步骤,关系系统,关系系统的定义,一个系统可以定义为关系系统当且仅当它： (1) 支持关系数据库(关系数据结构)； (2) 支持选择、投影和(自然)连接运算，对这些运算不必要求定义任何物理存取路径。,一个系统仅支持关系数据库而没有选择、投影和连接运算功能

2、的，不能称为关系系统。 一个系统虽支持选择、投影和连接运算，但要求定义物理存取路径，也不能称为关系系统,关系系统的定义,对关系系统的定义的几点解释： (1) 为什么关系系统除了要支持关系数据结构外，还必须支持选择、投影和连接运算呢？ 不支持这三种关系运算的系统，用户使用仍不方便，不能提高用户的生产率，而提高用户的生产率正是关系系统的主要目标之一。 (2) 为什么要求这三种运算不能依赖于物理存取路径呢？ 依赖物理存取路径来实现关系运算就降低或丧失了数据的物理独立性。不依赖物理存取路径来实现关系运算就要求关系系统自动地选择路径。为此，系统要进行查询优化，以获得较好的性能。 (3) 要求关系系统支持

3、这三种最主要的运算而不是关系代数的全部运算功能，是因为它们是最有用的运算功能，能解决绝大部分的实际问题。,关系系统的分类,表式系统：这类系统仅支持关系(即表)数据结构，不支持集合级的操作。表式系统不能算关系系统。,图中的圆表示关系数据模型。圆分为三个部分，分别表示关系模型的三个组成部分：结构S(Structure)、完整性I(Integrity)、数据操纵M(Manipulation)。图中扇形部分表示各类系统支持模型的程度,关系系统的分类,(最小)关系系统：这类系统仅支持关系数据结构和选择、投影、连接三种关系操作。,图中的圆表示关系数据模型。圆分为三个部分，分别表示关系模型的三个组成部分：结

4、构S(Structure)、完整性I(Integrity)、数据操纵M(Manipulation)。图中扇形部分表示各类系统支持模型的程度,关系系统的分类,关系完备的系统：这类系统支持关系数据结构和所有的关系代数操作。,图中的圆表示关系数据模型。圆分为三个部分，分别表示关系模型的三个组成部分：结构S(Structure)、完整性I(Integrity)、数据操纵M(Manipulation)。图中扇形部分表示各类系统支持模型的程度,全关系系统：这类系统支持关系模型的所有特征。即不仅是关系上完备的而且支持数据结构中域的概念，支持实体完整性和参照完整性。,图中的圆表示关系数据模型。圆分为三个部分，

5、分别表示关系模型的三个组成部分：结构S(Structure)、完整性I(Integrity)、数据操纵M(Manipulation)。图中扇形部分表示各类系统支持模型的程度,关系系统的分类,全关系系统的十二条基本准则,准则0：一个关系型的DBMS必须能完全通过它的关系能力来管理数据库 推论： 任何声称是关系型的DBMS必须在关系这个级别上支持数据的插入、修改和删除操作。 关系型DBMS必须遵循信息准则和保证访问(存取)准则。,准则1：信息准则。关系型DBMS的所有信息都应在逻辑一级上用一种方法即表中的值显式地表示 表名、列名和域名等都用系统内部表(即数据字典表)中的值表示。数据字典本身是一个动

6、态的用来描述元数据的关系数据库。 满足信息准则不仅是为了提高用户的生产率，而且也是为了使软件厂商在定义其他软件包时更加简便合理。 满足信息准则的另一个原因是使得DBA维护数据库的工作更简单、更有效。,准则2：保证访问准则。依靠表名、主码和列名的组合，保证能以逻辑方式访问关系数据库中的每个数据项(分量值) 保证访问准则表明关系系统所采用的是关联寻址的访问模式。,全关系系统的十二条基本准则,准则3：空值的系统化处理。全关系的DBMS应支持空值的概念，并用系统化的方式处理空值 空值是“不知道”或“无意义”的值。用户应了解空值的概念和处理空值的策略。,准则4：基于关系模型的动态的联机数据字典。数据库的

7、描述在逻辑级上应该和普通数据采用同样的表示方式，使得授权用户可以使用查询一般数据所用的关系语言来查询数据库的描述信息,推论： 每个用户(无论是应用程序员还是最终用户)只需学习一种数据模型。 授权用户可以很容易地扩充数据字典，使之变成完备的主动的关系数据字典，即使厂商有时没有提供这样的数据字典。,全关系系统的十二条基本准则,准则5：统一的数据子语言规则。一个关系系统可以具有几种语言和多种终端使用方式(如表格填空方式、命令方式等)。但必须有一种语言，它的语句可以表示为具有严格语法规定的字符串，并能全面地支持以下功能：数据定义、视图定义；数据操作(交互式或程序式)；完整性约束；授权；事务处理功能(事

8、务开始、提交、回滚),全关系系统的十二条基本准则,准则6：视图更新准则。所有理论上可更新的视图也应该由系统更新 视图更新准则对于系统支持数据逻辑独立性是不可缺少的。,“一个理论上可更新的视图”是指对此视图的更新要求，存在一个与时间无关的算法，该算法可以无二义性地把更新要求转换为对基本表的更新序列,准则7：高级的插入、修改和删除操作。关系系统的操作对象是单一的关系。以关系为操作对象不仅简化了用户查询，提高了用户生产率，且也为系统提供了很大余地来进行查询优化，提高了系统运行效率。它允许系统来选择存取路径，以便得到最有效的运行代码,准则8：数据物理独立性。无论数据库的数据在存储表示或存取方法上作任何

9、变化，应用程序和终端活动都保持逻辑上的不变性 为了保证这一独立性，DBMS必须清楚明确地区分基本关系的逻辑和语义方面及其物理和效率方面，应用程序仅涉及逻辑方面。,全关系系统的十二条基本准则,准则9：数据逻辑独立性。当对基本关系进行理论上信息不受损害的任何改变时，应用程序和终端活动都保持逻辑上的不变性,准则10：数据完整性的独立性。关系数据库的完整性约束条件必须是用数据库语言定义并存储在数据字典中，而不是在应用程序中加以定义的,准则11：分布独立性。关系型DBMS具有分布独立性 所谓分布独立性是指关系型DBMS具有这样的数据库语言，它使应用程序和终端活动在下列情况下保持逻辑不变性：在第一次引入分

10、布式数据时，即若原来的DBMS只管理非分布式的数据，而现在引入了分布式的数据；当数据重新分布时，即若原来的DBMS能管理分布式数据，现在要改变原来的数据分布。,全关系系统的十二条基本准则,准则12：无破坏准则。如果一个关系系统具有一个低级(指一次一个记录)语言，则这个低级语言不能违背或绕过完整性准则,以上是E.F.Codd给出的衡量一个关系型DBMS的十二条准则。这十二条准则都以准则0为基础，但仅有准则0是不够的。不支持信息准则、不保证访问准则、不支持空值准则和数据字典准则就不能保证数据库的完整性。准则811要求全关系型DBMS具有四种独立性。其中数据的物理独立性和逻辑独立性已为大家所熟知，而

11、数据完整性的独立性和分布独立性也已为大家重视。,关系数据库的查询优化,(1)优化器可以从数据字典中获得许多统计信息，并据此选择有效的执行计划，而用户程序则难以获得这些信息。 (2)若数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。 (3)优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。 (4)优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些技术。,关系系统的查询优化既是RDBMS实现的关键技术又是关系系统的优点所在。它减轻了用户选择存取路径的负担。用户只要提出“做什么

12、”，不必指出“怎么做”。,关系系统及其查询优化,查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好。,关系系统及其查询优化,查询优化的总目标：选择有效的策略，求得给定关系表达式的值。,查询优化的一般实现步骤： (1)将查询转换成某种内部表示，通常是语法树。 (2)根据一定的等价变换规则把语法树转换成标准(优化)形式。 (3)选择底层的操作算法。 (4)生成查询计划(查询执行方案)。,在集中式数据库中，查询的执行开销主要包括： 总代价 = I/O代价 + CPU代价,求选修了2号课程的学生姓名。 SELECT Student.Sna

13、me FROM Student, SC WHERE Student.Sno=SC.Sno AND SC.Cno=2 假定学生-课程数据库中有1000个学生记录，10000个选课记录，其中选修2号课程的选课记录为50个。所有内存处理时间均忽略不计。 系统可以用多种等价的关系代数表达式来完成这一查询： Q1 = Sname ( Student.Sno=SC.SnoSC.Cno=2 (StudentSC) Q2 = Sname ( SC.Cno=2 (Student SC) Q3 = Sname (Student SC.Cno=2 (SC),一个实例,计算广义笛卡尔积(StudentSC) 连接的做

14、法：在内存中尽可能多地装入Student表的若干块元组，留出一块存放SC表的元组。然后把SC中的每个元组与Student中的每个元组连接，连接后的元组装满一块后就写到中间文件上，再从SC中读入一块和内存中的Student元组连接，直到SC表处理完。这时再一次读入若干块Student元组，读入一块SC元组，重复上述处理过程，直到把Student表处理完。 设一个块能装10个Student元组或100个SC元组，在内存中存放5块Student元组和1块SC元组，则读取的总块数为：1000/10+(10000/100)*(1000/(10*5)=2100。若每秒读取20块，则总计要花105 s。 连

15、接后的元组数为1000*10000=107。设每块能装10个元组，则写出这些块要用(107/10)/20=50000 s。,一个实例(情况1),根据连接的做法可以知道，整个连接过程需要将Student表读入内存一遍，而需要将SC表读入内存(1000/50)=20遍。读Student表一遍需1000/10=100块，读SC表一遍需10000/100=100块。故总块数为100+100*20=2100。,作选择操作 依次读入连接后的元组，按照选择条件选取满足要求的记录。这一步读取中间文件花费的时间(同写中间文件一样)需50000 s。满足条件的元组为50个，均可放在内存。 作投影 把上步的结果在S

16、name上作投影输出，得到最终结果。,一个实例(情况1),执行查询Q1的总时间 105+50000*2 100000 s。,一个实例(情况2),计算自然连接 为了执行自然连接，读取Student和SC表的策略不变，总的读取块数仍为2100块花费105s。但自然连接的结果比第一种情况大大减少，为10000个。因此写出这些元组的时间为(10000/10)/20=50 s。 作选择操作 依次读入自然连接后的元组，按照选择条件选取满足要求的记录。这一步读取中间文件花费的时间也为50 s。 作投影 把上步的结果在Sname上作投影输出，得到最终结果。,执行查询Q2的总时间 105+50*2 205 s。

17、,一个实例(情况3),先对SC表作选择运算，只需读一遍SC表，存取100块花费时间为5 s，因为满足条件的元组仅50个，不必使用中间文件。 读取Student表，把读入的Student元组和内存中的SC元组作连接。只需读一遍Student表共100块花费时间为5 s。 把连接结果作投影输出。,执行查询Q3的总时间 5+5 10 s。,(1)选择运算应尽可能先做 在优化策略中这是最重要、最基本的一条。它常常可使执行时间降低几个数量级 (2)在执行连接前对关系适当地预处理 预处理的方法主要有两种：索引连接方法，即在连接属性上建立索引，然后执行连接；排序合并连接方法，即在连接属性上对关系排序，然后执

18、行连接,查询优化的一般准则,索引连接方法的步骤(以Student SC为例)： 在SC上建立Sno的索引； 对Student中每一个元组，由Sno值通过SC的索引查找相应的SC元组； 把这些SC元组和Student元组连接起来。 Student表和SC表均只要扫描一遍。处理时间是两个关系大小的线性函数,查询优化的一般准则,排序合并连接方法的步骤(以Student SC为例)： 首先对Student表和SC表按连接属性Sno排序；,取Student表中第1个Sno，依次扫描SC表中具有相同Sno的元组，把它们连接起来； 当扫描到Sno不相同的第1个SC元组时，返回Student表扫描它的下一个元

19、组，再扫描SC表中具有相同Sno的元组，把它们连接起来； 重复上述步骤直到Student表扫描完。 Student表和SC表均只要扫描一遍。处理时间要加上对两表的排序时间。,查询优化的一般准则,(3)把投影运算和选择运算同时进行 如有若干投影运算和选择运算，且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系 (4)把投影同其前或其后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系 (5)把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算 连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间 (6)找出公共子表达式 若这种重复出现的子表

20、达式的结果不是很大的关系，且从外存中读入此关系比计算该表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算的,关系代数等价变换规则,关系代数表达式的等价：用相同的关系代替两个表达式中相应的关系所得到的结果是相同的,(1)连接、笛卡尔积交换律 E1 E2 E2 E1 E1 E2 E2 E1 E1 F E2 E2 F E1 (2)连接、笛卡尔积的结合律 (E1E2)E3 E1(E2E3) (E1 E2) E3 E1 (E2 E3) (E1 F1 E2) F2 E3 E1 F1 (E2 F2 E3) (3)投影的串接定律 A1,A2,An(B1,B2,Bm(E) A1,A2,An(

21、E)， A1,A2,An构成B1,B2,Bm的子集,关系代数等价变换规则,(4)选择的串接定律 F1(F2(E) F1F2 (E) 选择的条件可以合并，这样一次可检查全部条件 (5)选择与投影的交换律 F(A1,A2,An(E) A1,A2,An ( F (E) 这里条件F只涉及属性A1,A2,An (6)选择与笛卡尔积的交换律 若F中涉及的属性都是E1中的属性，则F(E1E2)F(E1)E2 若F1只涉及E1中的属性，F2只涉及E2中的属性，则 F1F2 (E1E2)F1(E1) F2(E2) 若F1只涉及E1中的属性，F2涉及E1和E2两者的属性，则 F1F2 (E1E2)F2(F1(E1

22、) E2), F1F2 (E1E2) F1(F2(E1E2) F1(E1F2(E2) F1(E1)F2(E2),关系代数等价变换规则,(7)选择与并的交换 设E1、E2有相同的属性名，则F (E1E2) F (E1)F (E2) (8)选择与差的交换 设E1、E2有相同的属性名，则F (E1E2) F (E1) F (E2) (9)投影与笛卡尔积的交换 设A1,A2,An是E1的属性， B1,B2,Bm是E2的属性，则A1,A2,An,B1,B2,Bm (E1E2) A1,A2,An (E1) B1,B2,Bm(E2) (10)投影与并的交换 设E1、E2有相同的属性名，则 A1,A2,An

23、(E1E2) A1,A2,An (E1) A1,A2,An(E2),利用规则4把形如 F1F2 Fn (E)变换为F1(F2(Fn(E) 对每个选择，利用规则48尽可能把它移到树的叶端 对每个投影利用规则3、9、10、5中的一般形式尽可能把它移向树的叶端 利用规则3、4、5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影 把上述得到的语法树的内结点分组 生成一个程序，每组结点的计算是程序中的一步。各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算,关系代数表达式的优化算法,算法：关系表达式的优化 输入：一个关系表达式的语法树 输出：计算该表达式的程序,每一双目运

24、算和它所有的直接祖先为一组(这些直接祖先是、运算)。若其后代直到叶子全是单目运算，则也将它们并入该组，但当双目运算是笛卡尔积，且其后的选择不能与它结合为等值连接时除外。把这些单目运算单独分为一组,优化的一般步骤,(1)把查询转换成某种内部表示(语法树),SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.Sno AND SC.Cno=2,优化的一般步骤,(2)把语法树转换成标准(优化)形式 利用优化算法，把原始的语法树转换成优化的形式,利用规则4：F1(F2(E)F1F2(E)、规则6： F1F2(E1E2)F2(F1(E1)E

25、2)把选择SC.Cno=2移到叶端。 Sname(SC.Cno=2(Student.Sno=SC.Sno(StudentSC) Sname(Student.Sno=SC.Sno(SC.Cno=2(StudentSC) Sname(Student.Sno=SC.Sno(StudentSC.Cno=2(SC),(3)选择低层的存取路径 根据第(2)步得到的优化了的语法树计算关系表达式值的时候要充分考虑索引、数据的存储分布等存取路径，利用它们进一步改善查询效率 (4)生成查询计划，选择代价最小的 查询计划是由一组内部过程组成的，这组内部过程实现按某条存取路径计算表达式的值。在计算代价时主要考虑磁盘读写的I/O数，内存CPU处理时间等。,优化的一般步骤,关系系统：支持关系模型的数据库系统。按照支持关系模型的程度，实际的数据库系统可分为(最小)关系系统、关系完备的和全关系的等若干类 完全地支持地支持关系模型的系统应遵循12条基本准则，这些准则可以作为评价或购买关系型产品的标准。(注：12条基本准则不作要求) 查询处理是DBMS的核心，而查询优化技术又是查询处理的关键技术。查询优化一般可分为代数优化和物理优化。代数优化是指关系代