数据库系统原理教案4

《数据库系统原理教案4》由会员分享，可在线阅读，更多相关《数据库系统原理教案4（10页珍藏版）》请在装配图网上搜索。

1、数据库系统原理教案教学内容第四章 关系系统的查询优化教材章节第四章 关系系统的查询优化教学周次教学课时2授课对象教学环境多媒体教室教学目标掌握关系系统的优化处理过程教学重点关系系统的基本概念，关系系统的优化处理。教学难点关系系统的优化处理教学过程一次课：关系系统的基本概念，关系系统的优化处理。作业与要求备注第四章 关系系统的查询优化4.1 关系系统4.1.1 关系系统的定义笼统的说，支持关系模型的数据库管理系统(DBMS)称为关系系统。可见，关系系统和关系模型是密切相关而又相互区别的两个概念。设计关系模型时，我们不苛求关系模型中每一部分的同等重要性，但是要满足如下几个方面：(1) 以提高用户的

2、生产率作为关系系统的主要目标，方便用户使用。(2) 保证和提高数据的物理独立性，即实现关系系统能够自动地选择路径。(3) 确保关系系统能够解决绝大部分的实际问题。定义4.1 一个系统是关系系统当且仅当支持关系数据库 (关系数据结构)。支持选择、投影和(自然)连接运算，对这些运算不必要求定义任何物理存取路径。需要说明的是，该定义是关系系统的最小要求。一个系统仅支持关系数据结构，但没有选择、投影和连接运算功能的系统仍不能算作关系系统。支持选择、投影和连接运算，但要求定义物理存取路径，需要用户建立索引才能检索记录，也不能算作真正的关系系统。当然并不要求关系系统的选择、投影、连接运算和关系代数的相应运

3、算完全一样，而只要求有等价的这三种运算功能就行。 4.1.2 关系系统的分类具体地说：目前的关系系统多是按照E.F.Codd的思想划分的(如图4-1)。图中的圆表示关系数据模型。每个圆分为三部分，分别表示关系模型的三个组成部分：结构S(Structure)、完整性I(Integrity)、数据操纵M(Manipulation)。图中阴影部分表示各类系统支持模型的程度。(1) 表式系统 这类系统仅支持关系数据结构，不支持集合的操作。表式系统不能算关系系统。(2) 最小关系系统 即定义中的关系系统。它们仅支持关系数据结构和三种关系操作。(3) 关系完备的系统这类系统支持关系数据结构和所有的关系代数

4、操作。(4) 全关系系统 这类系统支持关系模型的所有特征。即不仅是关系上完备的而且支持数据结构中域的概念，支持实体完整性和参照完整性。目前，大多数关系系统已不同程度上接近或达到了这个目标。根据分类可以看到不同关系系统对模型的支持不同如表4-1：表4-1 不同关系系统对模型的支持数据结构数据操纵数据完整性表式系统表不支持不支持最小关系系统表选择、投影、连接不支持关系完备的系统表全部不支持全关系系统全部全部完全支持目前，国内外涌现出了许多关系系统：如倒排列表(Inverted list)，FoxPro，DB2，ORACLE，SYBASE，以及我国自己开发的PBASE(中国人民大学)、COBASE(

5、北大、人大与中软)、OPENBASE(东大阿尔派)、DM2(华中理工大学)等。根据关系系统的定义及E.F.Codd的思想，我们可以对这些系统作严格的区分。如倒排表列(Inverted list)系统就属于表式系统。如FoxBASE、FoxPro等就属于最小关系系统。90年代初的许多关系数据库管理系统属于关系完备的系统。*4.1.3 全关系系统的十二条基本准则全关系型的系统应该完全地支持关系模型的所有特征，这是个原则。关系模型的奠基人E.F.Codd具体地给出了全关系型的关系系统应遵循的十二条基本准则。从实际意义上看，这十二条准则可以作为评价或购买关系型产品的标准。从理论意义上看，它是对关系数据

6、模型的具体而又深入的论述。准则0 一个关系型的DBMS必须能完全通过它的关系能力来管理数据库。准则0是下面十二条准则的基础。准则0的一个推论是：任何声称是关系型的DBMS必须在关系这个级别上支持数据的插入、修改和删除(即一次多个记录的操作级别)。不管一个系统是否还具有非关系的管理数据的能力，它必须满足准则0。任何不满足准则0的DBMS不配称为关系型DBMS。 准则0的另一个推论是：关系型DBMS必须遵循信息准则和保证访问(存取)准则。 准则1 信息准则 关系型DBMS的所有信息都应在逻辑一级上用一种方法即表中的值显式地表示。进一步地，表名、列名和域名等都用系统内部表中的值表示。数据字典本身是一

7、个动态的用来描述元数据的关系数据库。 满足信息准则不仅为了提高用户的生产率，使得DBA维护数据库的工作更简单、更有效，而且也为了使软件厂商在定义其他软件包时能够检索存储在数据字典中的信息，需要的话可以借助DBMS的操作把新的信息存入字典中，简便合理。 准则2 保证访问准则依靠表名、主键和列名的组合，保证能以逻辑方式访问关系数据库中的每个数据项。 保证访问准则表明关系系统所采用的是相联寻址的访问模式，而不是那种面向机器的寻址方法。这是关系系统独有的方式。 准则3 空值的系统化处理全关系型的DBMS应支持空值的概念，并用系统化的方式处理空值。以往处理空值的办法常常是对每个允许取空值的字段定义一种特

8、殊的值来表示空值。这不是系统化的好办法。因为这样的话，用户必须对每个字段或域采用不同的方法来处理空值。这种方法必然会大大降低用户生产率。准则4 基于关系模型的动态的联机数据字典 数据库的描述在逻辑级上应该和普通数据采用同样的表示方式，使得授权用户可以使用查询一般数据所用的关系语言来查询数据库的描述信息。准则5 统一的数据子语言准则 一个关系系统必须有一种语言，它的语句可以表示为具有严格语法规定的字符串，并能全面地支持以下功能： 数据定义、视图定义 数据操作完整性约束 授权 事务处理功能(事务开始、提交、回滚) 关系方法是高度动态的，即很少需要停止数据库的活动。非关系系统则不是这样。 准则6 视

9、图更新准则所有理论上可更新的视图也应该允许由系统更新。 什么叫“一个视图是理论上可更新的视图”呢？它是指对此视图的更新要求存在一个与时间无关的算法，该算法可以无二义性地把更新要求转换为对基本表的更新序列。准则7 高级的插入、修改和删除操作 关系系统的操作对象是单一的关系。以关系为操作对象不仅简化了用户查询，提高了用户生产率，而且也为系统提供了很大的余地来进行查询优化，提高了系统的运行效率。它允许系统来选择存取路径，以便得到最有效的运行代码。准则8 数据物理独立性 无论数据库的数据在存储表示或存取方法上作任何变化，应用程序和终端活动都保持逻辑上的不变性。 准则9 数据逻辑独立性 当对基本关系进行

10、理论上信息不受损害的任何变化时，应用程序和终端活动都保持逻辑上的不变性。 对基本关系来讲，什么样的变化在理论上是保持信息不受损害的变化呢？把一个基本表按行的内容或者按列名分解为两个表，若这两个表都保留原基本表的主键，则这种变换在理论上是保持信息不受损失的。用无损连接方法把两个表合成一个表也不会破坏信息的变换。 为了尽可能提高数据逻辑独立性，DBMS必须能对理论上可更新的视图执行插入、修改和删除操作，即必须满足准则6。准则l0 数据完整性的独立性 关系数据库的完整性约束条件必须是用数据库语言定义并存储在数据字典中的，而不是在应用程序中加以定义的。准则11 分布独立性 所谓分布独立性是指关系型DB

11、MS具有这样的数据库语言，它使应用程序和终端活动无论在最初的数据还是在以后的数据重新分布时都能在逻辑上保持不变准则12 无破坏准则 如果一个关系系统具有一个低级(指一次一个记录)语言，则这个低级语言不能违背或绕过完整性准则。 在关系方法中，为获得数据完整独立性就要让完整性约束条件和数据的逻辑结构相独立。用准则12就很容易帮助我们识别那些贴着“关系”标签的非关系系统。因为这一系统已经在关系接口之下有一个应用接口，因此很难满足准则12。这时DBA不能控制他们的数据库，不能保证数据库的完整性状态。4.2 查询优化处理关系系统的查询通常指用户向数据库系统提交的一些对数据操作的请求。由于数据库系统向用户

12、提供了非过程化的数据操纵语言，用户只要提出“干什么”，不必指出“怎么干”， DBMS就会自动根据用户的查询请求来完成任务，因此查询的优化处理就成了DBMS的重要任务。4.2.1 问题的提出我们首先来看一个简单的例子，说明为什么要进行查询优化。 例4.1 对于关系的Order-O_Details(订单-订单明细)： Order(OID,CID,ODate)属性分别为订单号，客户号，订单日期；O_Details(OID,PID,Qtity)属性分别为订单号，产品号，产品数量。 如果查询订购 5 号产品的客户的客户号，则有下面的查询语句： SELECT Order. CIDFROM Order, O

13、_DetailWHERE Order.OID=O_Details.OID AND O_Details.PID =5； 设O_O_Details中有l000个订单，l0000种产品，其中5号产品的记录为50个。对于此查询，系统可以提供多个等价策略。这里我们讨论如下三种：(1) Q1=CID(Order.OID=O_Details.OIDO_Details.PID=5(OrderO_Details) (2) Q2=CID (O_Details.PID=5 (OrderO_Details) (3) Q3=CID (OrderO_Details.PID=5(O_Details) 对Q1的处理过程和时间

14、开销分析l. Order和O_Details的笛卡尔积操作(1) 在内存缓冲区中读入某个表(如Order表)的未处理元组；(2) 另一块缓冲区中读入另一个表(如O_Details表)的未处理元组；(3) 把O_Details中的每个元组和Order中每个元组连接，连接后的元组装满一块后，送入输出缓冲区；如果溢出，则写入临时文件上；(4) 从O_Details中读入一块和内存中的Order元组连接，直到O_Details表处理完。(5) 再一次读入若干块Order元组，读入一块O_Details元组，量复上述处理过程，直到把Order表处理完。 根据上述步骤，设一个块能装l0个Order元组或l

15、00个O_Details元组，在内存中存放5块Order元组 和l块O_Details元组，需要读Order表l00块。读O_Details表20遍，每遍l00块。因此读取总块数为：2100块 。若每秒读写20块，则读取总计要花105秒。 Order和O_Details连接后的元组数为100010000=107。设每块能装l0个元组，则写出这些块要花5104秒。 2. 选择操作 如果满足条件的元组假设仅50个，均可放在内存。那么，依次读入连接后的元组，按照选择条件选取满足要求的的记录。假定内存处理时间忽略，这一步读取中间文件花费的时间(同写中间文件一样)需5104秒。3. 投影操作 把第2步的

16、结果在CID上作投影输出，得到最终结果。 因此，忽略所有内存处理时间，Q1执行查询的总时间大约要105秒。 对Q2的处理过程和时间开销分析l. 自然连接操作 自然连接可以看作是笛卡儿积特殊运算，因此读取Order和O_Details表的策略不变，总的读取块数仍为2100块花费l05秒。但由于自然连接包含了选择运算，相对Q1结果减少为104个。因此写出这些元组时间为50秒。仅为Q1的千分之一。 2. 选择操作选择运算是对自然连接结果进行读取，因此读取中间文件块花费时间为50秒。 3. 把第2步结果投影输出。 因此，Q2执行查询的总时间大约要205秒。 对Q3的处理过程和时间开销分析1由于先对O_

17、Details表作选择运算， 关系O_Details的每块只需读一遍，因此存取l00块花费时间为5秒。因为满足条件的元组仅50个，不必使用中间文件。 2. 读取Order表，把读入的Order元组和内存中的O_Details元组作连接也只需读一遍Order表，共l00块，花费时间为5秒。 3. 把连接结果投影输出。 因此，Q3总的执行时间大约为10秒。 假如O_Details表的PID字段上有索引，第l步就不必读取所有的O_Details元组而只需读取PID=5的那些元组(50个)。存取的索引块和O_Details中满足条件的数据块大约总共34块。若Order表在OID上也有索引，则第2步也不

18、必读取所有的Order元组，因为满足条件的O_Details记录仅50个，涉及最多50个Order记录，因此读取Order表的块数也可大大减少。总的存取时间将进一步减少到数秒。 这个简单的例子充分说明了查询优化的必要性，同时也给了我们一些查询优化方法的初步概念。如当有选择和连接操作时，应当先做选择操作，这样参加连接的元组就可以大大减少。下面给出优化的一般策略。4.2.2关系代数的优化规则1. 关系代数等价变换规则关系代数表达式的优化是查询优化的基本课题。而研究关系代数表达式的优化最好从研究关系表达式的等价变换规则开始。 两个关系表达式E1和E2是等价的，可记为E1E2。 常用的等价变换规则有：

19、(1) 连接、笛卡尔积交换律E1E2E2E1E1E2E2E1 E1E2E2E1其中E1和E2是关系代数表达式，F是连接运算的条件(2) 连接、笛卡尔积的结合律(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)其中E1、E2、E3是关系代数表达式，Fl和F2是连接运算的条件(3) 投影的级联 A1,A2,.,An (B1,B2,.,Bm(E)A1,A2,.,An (E) 其中，E是关系代数表达式，Ai(i=1,2,.,n)，Bj(j=l,2,.,m)是属性名且 A1,A2,.,An 是 B1,B2,.,Bm 的子集。 (4) 选择的级联F1(F2(E

20、)F1F2(E) 这里，E是关系代数表达式，Fl、F2是选择条件。F1F2=F2F1，因此交换律成立。(5) 选择与投影的交换律F(A1,A2,.,An (E)A1,A2,.,An (F(E) 这里，选择条件F只涉及属性A1,A2,.,An。若F中有不属于A1,A2,.,An的属性B1,B2,.,Bm，则有更一般的规则：A1,A2,.,An (F(E) A1,A2,.,An (F(A1,A2,.,An, B1,B2,.,Bm (E)(6) 选择与笛卡尔积的交换律如果F中涉及的属性都是El中的属性，则 F(E1E2)F(E1)E2 如果F=F1F2，并且F1只涉及E1中的属性，F2只涉及E2中的

21、属性，则由上面等价变换规则可推出： F(E1E2)F1(E1)F2(E2)若F1只涉及E1中的属性，F2涉及E1和E2两者的属性，则仍有F(E1E2)F2(F1(E1)E2)即将一部分选择条件放到笛卡尔积的前面。(7) 选择与并的交换 设E= E1E2，E1、E2有相同的属性名，则 F(E1E2)F(E1)F(E2)(8) 选择与差运算的交换 若E1与E2有相同的属性名，则 F(E1-E2)F(E1)- F(E2)(9) 投影与笛卡尔积的交换设E1和E2是两个关系表达式，A1,.,An是E1的属性，B1,B2,.,Bm是E2的属性，则A1,A2,.,An，B1,B2,.,Bm(E1E2)A1,

22、A2,.,An (E1)B1,B2,.,Bm (E2)(10) 投影与并的交换 设E1和E2 有相同的属性名，则 A1,A2,.,An (E1E2)A1,A2,.,An (E1)A1,A2,.,An (E2)2. 关系代数的优化规则 从本章第一节我们可以看出，关系代数表达式中，笛卡尔积和连接操作是最花费时间和空间的运算，因此引出如下对表达式进行转换的规则，以减少中间关系的大小。(1) 尽可能早的做选择操作。在优化策略中这是最重要、最基本的一条。它常常可使执行时间节约几个数量级，因为选择运算一般使计算的中间结果大大变小。 (2) 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算。相同

23、关系上的连接操作，特别是等值连接运算要比同样关系上的笛卡尔积省很多时间。(3) 把投影运算和选择运算同时进行。如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系。 (4) 把投影同其前或其后的双目运算结合起来。这样可以节省为单独完成投影操作而进行的关系扫描。(5) 找出公共子表达式。如果这种重复出现的子表达式的结果不是很大的关系，并且从外存中读入这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算的。当查询的是视图时，定义视图的表达式就是公共子表达式的情况。 4.2.3 关系代数的优化算法关系代数

24、表达式的优化是由DBMS的DML编译器完成的。我们可以应用关系到代数的变换法则来优化关系表达式，使优化后的表达式能满足关系代数优化原则。通过对关系代数进行语法分析得到一棵语法树。这是关系优化过程中最重要的一步。下面给出关系表达式的优化算法。 算法4.1 关系表达式的优化。 输入：一个关系表达式的语法树。 输出：计算该表达式的程序。 步骤：(1) 利用规则(4)把形如F1F2.Fn(E)变换为级联形式F1 (F2 (.(Fn (E).)(2) 利用规则(4)(8)尽可能把对每一个选择移到树的叶端。 (3) 利用规则(3)、(5)、(9)、(10)中的一般形式尽可能把对每一个投影移向树的叶端。规则

25、(3)使一些投影消失，而一般形式的规则(5)把一个投影分裂为两个，其中一个有可能被移向树的叶端。 (4) 利用规则(3)(5)把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成，尽管这种变换以乎违背“投影尽可能早做”的原则，但这样做效率更高。 (5) 把上述得到的语法树的内节点分组。每个双目运算(, -)和它所有的直接祖先(、)为一组。如果其后代直到叶子结点全是单目运算则也将它们并入该组；但当双目运算是笛卡尔积()，而且其后的选择不能与它结合为等值连接时除外。把这些单目运算单独分为一组。 (6) 生成一个程序，每组结点的计算是程

26、序中的一步。各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算。 例4.2 对于关系的Customer-Order-Order_Details(客户-订单-订单明细)： Customer(CustomerID,CompanyName,Address)属性分别为客户号，公司名称，公司地址；Order(OrderID,CustomerID,OrderDate)属性分别为订单号，客户号，订单日期；Order_Details(OrderID,ProductID,Quantity)属性分别为订单号，产品号，产品数量。为方便起见，我们将以上关系简写如下： C(CID,CName,Add)

27、O(OID,CID,ODate)O_Details(OID,PID,Qtity)检索订单中至少有一种产品的数量为100件的客户号和公司名称SELECT CID,CNameFROM C,O,O_DetailsWHERE C.CID=O.CID AND O.OID= O_Details.OID； 该查询语句对应的关系代数表达式如下：C.CID,CName(Qtity=100(L(C.CID=O.CIDO.OID= O_Details.OID(CO O_Details)其中L为(C.CID,CName,Add ,O_Details.OID,ODate,PID,Qtity)对应的语法树如图4-2所示：

28、下面用优化算法对语法树进行优化：(1) 将第二个选择操作分解为两个，可以得到3个选择操作：Qtity=100，C.CID=O.CID，O.OID= O_Details.OID(2) 利用等价变换规则(4)(8)将选择操作推向叶端。根据规则(4)、(5)将Qtity=100直接放到叶端。C.CID=O.CID不能移动，因为它的属性涉及到关系C。O.OID= O_Details.OID可以向下移动和就近的一个笛卡尔积交换。然后根据规则(3)将两个投影合并成CID,CName，可以得到如图4-3的语法树。(3) 利用规则(5)将投影和选择操作进行交换。由于C.CID=O.CID中有不属于 CID,CName 的属性，所以用一般规则将CID,CName和 C.CID=O.CID转化为：将C.CID,CName, O.CID分解为C.CID,CName 和O.CID与笛卡尔积交换，向叶端移动。其中O.CID与O.OID= O_Details.OID又构成了选择投影结构。利用规则(5)重复上面的过程，将得到的投影O.CID和O_Details.OID向相应的叶端移动。于是可以得到图4-4的语法树。(4) 对关系进行扫描时，从叶端依次向上进行。第 10 / 10 页