《制造信息技术_DB关系系统及其查询优化》由会员分享，可在线阅读，更多相关《制造信息技术_DB关系系统及其查询优化（38页珍藏版）》请在金锄头文库上搜索。
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.S
13、name 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个，均可放在内存。 作投影 把上步的结果
16、在Sname上作投影输出，得到最终结果。,一个实例(情况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。,一个实例(情况3),先对SC表作选择运算，只需读一遍SC表，存取100块花费时间为5 s，因为满足条件的元组仅50个，不必使用中间文件。 读取Student表，把读入的Student元组和内存中的SC元组作连接。只需读一遍Student表共100块花费时间为5 s。 把连接结果作投影输出。,
