《数据库原理与设计基于SQL Server 2012》第2章 关系数据模型new.pptVIP

Database theroy and design数据库原理与设计 第2章关系模型与关系代数 2.4.4 关系运算的安全性和等价性 1. 关系运算的安全性 在关系代数中，基本的操作包括并、差、笛卡尔积、投影和选择，没有集合的补运算，所以关系代数的运算总是安全的。 关系的演算则不同，可能出现无穷关系和无穷的验证问题，例如{t|┓（R(t)）}表示不属于R的所有元组集合，表示的是一个无限关系。对于（?u）（R(u)）的真假问题，需要对所有的u进行验证，变为一个无限验证问题，因此在关系演算中需要采取措施防止无限关系和无限验证问题的出现。 在数据库技术中，不产生无限关系和无限验证的运算称为安全运算，与其相对应的表达式称为安全表达式，采取的措施称为安全约束。在关系演算中约定，运算只对表达式中公式在涉及到的关系的值范围内操作，这样就不会产生无限关系和无限验证问题，因此关系演算也是安全的。 2.4.4关系运算的安全性和等价性 2. 关系运算的等价性 并、差、笛卡尔积、投影和选择是关系代数的基本操作，构成了关系代数运算的最小完备集。在这个基础上关系代数、安全的元组演算、安全的域演算在关系的表达和操作上能力上完全等价的。 对应的语言的典型代表是ISBL、QUEL和QBE语言。 还有SQL语言介乎于关系代数和元组演算之间的一种关系查询语言，现在已经成为关系数据库的标准查询语言，我们将在后面介绍。 2.5 查询优化 2.5.1 关系代数表达式的优化问题 在关系代数表达式中通常包含有若干关系操作，系统应该按什么样的顺序执行这些操作，才能够执行起来既省时间又省空间，执行的效率比较高呢？这就是我们需要解决的查询优化问题。 在关系代数的运算中，连接运算和笛卡尔积最费时间，主要原因是当R有m个元组，S有n个元组时，R和S的笛卡尔积就有mn个元组。当R和S都比较大时，R和S占用的空间比较大，不能够同时读入内存，只能将R和S的部分元组读入内存，重复读写外存，造成执行效率低下，如何花费较少的时间和空间完成R和S的笛卡尔积的运算，就需要有一个策略问题。 2.5 查询优化 2.5.1 关系代数表达式的优化问题 【例2-14】查询至少选修了“数据库原理”课程的学生姓名。 E1= ?姓名（（?课程名=‘数据库原理’（课程） ? ?学号，课程号（选课） ? ?学号，姓名（学生）） E2=?姓名（?学号（?课程名=‘数据库原理’（（课程） ? （选课） ? （学生）） E3= ?姓名（?课号（?课程名=‘数据库原理’（课程） ? ?学号，课程号（选课） ? ?学号，姓名（学生）） 2.5 查询优化 2.5.1 关系代数表达式的优化问题 问题：三个表达式是等价的，但其执行效率明显不同，哪个最优呢？ 分析： E1的执行过程是首先对课程做了选择运算，减少了课程的元组数目；对选课做了投影运算减少了选课的元数；对学生做了投影运算减少了学生的元数，然后再做自然连接，减少了连接的数据量。最后对连接的结果做了投影运算。 E2的执行过程是先将选课、学生和课程所有的元组做了自然连接，然后对对连接的结果做了投影运算。 E3的执行过程是首先对课程做了选择运算，减少了课程的元组数目，又对新结果做了投影运算，过滤掉了不需要的元；对选课做了投影运算减少了选课的元数；对学生做了投影运算减少了学生的元数，然后再做自然连接，减少了连接的数据量。最后对连接的结果做了投影运算。 结论：E3是最优的，E1次之，E2的执行效率是最低的。 2.5 查询优化 2.5.2 关系代数表达式的等价变化原则 两个关系代数表达式等价是指用同样的关系实例代替两个关系代数表达式时所得到的结果相同。但得到的元组的属性的顺序可以不同，关系代数表达式E1和E2等价可以记为E1≡E2。 2.5 查询优化 2.5.2 关系代数表达式的等价变化原则 （1）连接和笛卡尔积的交换律 （2）连接和笛卡尔积的结合律 （3）投影的串接 （4）选择的串接 （5）投影和选择的交换 （6）选择对笛卡尔积的分配律 （7）选择对并的分配律 （8）选择对自然连接的分配律 （9）选择对差集的分配律 （10）投影对笛卡尔积的分配律 （11）涉及到的集合的操作并和交的交换律 （12）涉及到的集合的并和交的结合律 2.5 查询优化 2.5.3 关系代数表达式的优化策略 此处介绍的优化策略与存储技术无关，主要是如何安排操作顺序。我们只讨论优化的一般技术。优化的策略主要考虑一下几点： （1）在关系代数表达式中尽可能尽早地处理选择运算。原因是可以尽量减少元组个数，从而得到比较小的关系，减少运算量和读外存快的次数。 （2）尽可能吧笛卡尔积和随后的选择运算合并为F连接运算。原因是减少合并的元组数