第4章 关系数据库2

1关系模型的三个基本要素？关系数据结构关系操作集合关系完整性约束关系系统的三个基本特征？选择投影连接2关系系统（关系数据库系统）：支持关系模型的数据库管理系统。1．关系系统的定义一个系统可定义为关系系统，当且仅当它支持：（1）关系数据结构。（2）支持选择、投影和（自然）连接运算。对这些运算不必要求定义任何物理存取路径。3几个问题：1为什么关系系统除了要支持关系数据结构外，还必须支持选择、投影、连接运算？2为什么要求这三种运算不能依赖于物理存取路径？3为什么不要求支持关系代数的全部运算？42、关系系统的分类1）表式系统：仅支持数据结构。2）(最小)关系系统：数据结构+三种关系操作。3）关系完备的系统:数据结构+所有关系代数操作。4）全关系系统：支持关系模型的所有特征。S:结构M:数据操纵I:完整性SMIMISSIMSIM53、全关系系统的十二条基本准则准则0：一个关系型的DBMS必须能完全通过它的关系能力来管理数据库。一个关系型DBMS的关系能力包括属性指定、元组选择、插入和删除、关系合并以及数据完整性和并发控制等，准则0指出，一个RDBMS必须能完全通过这些关系能力来管理数据库，而不需要用户介入。6准则1：信息准则。准则2：保证访问准则。准则3：空值的系统化处理。准则4：基于关系模型的动态的联机数据字典。准则1-4保证数据库完整性7准则5：统一的数据子语言。准则6：视图更新准则。准则7：高级的插入、修改和删除操作。准则5-7保证数据库操作8准则8：数据物理独立性。准则9：数据逻辑独立性。准则10：数据完整性的独立性。准则11：分布独立性。准则12：无破坏准则。准则8-11保证数据库独立性9用户输入查询查询的内部表示执行查询步骤向用户报告查询结果查询语句的句法分析查询优化处理查询1、响应用户查询的一般过程10查询开销：集中式：总代价=I/O代价+CPU代价多用户：总代价=I/O代价+CPU代价+内存代价例：求选修了2号课程的学生姓名。Q1=πSname(σS.Sno=SC.Sno∧SC.Cno=‘2’(S×SC))Q2=πSname(σSC.Cno=‘2’(S∞SC))Q3=πSname(S∞σSC.Cno=‘2’(SC))11假设：S有n1个元组，SC有n2个元组；每块可放1个S元组或1个SC元组；主存能同时放入2块，其中1块S元组和1块SC元组；所以：S×SC读入时间=（n1+n1×n2)×pp是系统传送一块所需的时间现设：n1=10，n2=100，p=0.005(s/块)12第一种情况：Q1=πSname(σS.Sno=SC.Sno∧SC.Cno=‘2’(S×SC))读取时间：(10+10*100)*0.005=5.05s写入临时文件的时间：10*100*0.005=5s作选择操作所花的时间：5s符合条件的元组有50个作投影的时间忽略不计，以上所有CPU时间均忽略不记，总I/O时间：5.05+5+5=15.05S13第二种情况：Q2=πSname(σSC.Cno=‘2’(S∞SC))读取时间：(10+10*100)*0.005=5.05s写入临时文件的时间：100*0.005=0.5s作选择操作所花的时间：0.5s符合条件的元组有50个作投影的时间忽略不计，以上所有CPU时间均忽略不记，总I/O时间：5.05+0.5+0.5=6.0514第三种情况：Q3=πSname(S∞σSC.Cno=‘2’(SC))读取SC时间：100*0.005=0.5s符合条件的元组有50个读取S时间：10*0.005=0.05s作投影的时间忽略不计，以上所有CPU时间均忽略不记，第一种情况：5.05+5+5=15.05S第二种情况：5.05+0.5+0.5=6.05第三种情况：0.5+0.05=0.55S15常见查询优化途径1）代数优化：对查询表达式进行代数变换，从而改变基本查询操作的次序，提高查询语句的执行效率。2）物理优化：根据系统提供的存取路径，选择合适的存储策略，如运用关键字和索引这些特点进行查询等，这种方法依赖于存取路径的优化。3）代价估算优化：除根据一些基本规则外，还对可供选择的执行策略进行代价估算，从中选用代价最小的执行策略。161、尽可能早地执行选择操作（减少中间运算结果）2、对关系进行预处理（索引、排序）3、同时进行投影和选择运算4、把投影同其前或后的双目运算结合起来。（合并连接的选择与投影操作，以减少扫描的次数）5、合并选择与笛卡尔积组成一个连接6、寻找公共子表达式174、关系代数等价变换规则1）连接、笛卡尔积交换律E1×E2≡E2×E1E1E2≡E2E1E1E2≡E2E1FF2）连接、笛卡尔积结合律(E1×E2)×E3≡E1×(E2×E3)(E1E2)E3≡E1(E2E3)(E1E2)E3≡E1(E2E3)F1F2F1F2183、投影的串接定律πA1,A2,…,An(πB1,B2,…,Bm(E))≡πA1,A2,…,An(E)4、选择的串接定律σF1(σF2(E))≡σF1∧F2(E)5、选择与投影的交换律σF(πA1,A2,…,An(E))≡πA1,A2,…,An(σF(E))（F只涉及A1,A2,…,An）σF(πA1,A2,…,An(E))≡πA1,A2,…,An(σF(πA1,…,An,B1,…,Bm(E)))6、选择与笛卡尔积的交换律σF(E1×E2)≡σF(E1)×E2σF(E1×E2)≡σF1(E1)×σF2(E2)σF(E1×E2)≡σF2(σF1(E1)×E2)197、选择与并的交换σF(E1∪E2)≡σF(E1)∪σF(E2)8、选择与差的交换σF(E1-E2)≡σF(E1)-σF(E2)9、投影与笛卡尔积的交换律πA1,A2,…,An,B1,B2,…,Bm(E1×E2)≡πA1,A2,…,An(E1)×πB1,B2,…,Bm(E2)10、投影与并的交换πA1,A2,…,An(E1∪E2)≡πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)205、关系代数表达式的优化算法输入：一个关系表达式的语法树输出：计算该表达式的程序方法：1)把σF1∧F2∧...∧Fn(E)变换为σF1(σF2(…(σFn(E))…))2)对每一个选择尽可能把它移到树的叶端。3)对每一个投影尽可能把它移到树的叶端。4)合并选择和投影或一个选择后跟一个投影。5)将得到的语法树的内节点分组。(每一双目运算和它所有的直接祖先为一组。6)生成一个程序，每组节点的计算是程序中的一步。求值顺序为先子孙，后祖先。[规则4][规则3,5,9,10][规则4-8][规则3-5]21例：求981001号学生所选修的课程名及成绩πCN,G（σSC.S#=‘981001’∧SC.C#=C.C#（SC×C））πCN,GσSC.S#=‘981001’∧SC.C#=C.C#SCC×22说明：1.由规则6，可以把选择SC.S#=‘981001’下移至SC之上πCN,GσSC.C#=C.C#SCC×σSC.S#=‘981001’23πCN,GσSC.C#=C.C#SCC×σSC.S#=‘981001’πCN,G,SC.C#,C.C#2.由规则5，选择与投影交换率243.由规则9，可以把投影πCN,G,SC.C#,C.C#下移πCN,GσSC.C#=C.C#SCC×σSC.S#=‘981001’πC#,CNπG,C#25例：求选修了2号课程的学生姓名。Q1=πSname(σS.Sno=SC.Sno∧SC.Cno=‘2’(S×SC))Q2=πSname(σSC.Cno=‘2’(S∞SC))Q3=πSname(S∞σSC.Cno=‘2’(SC))要求：1、分别画出Q1、Q2、Q3的语法树2、对Q1、Q2、Q3进行优化。26πsnameσStudent.sno=SC.sno∧SC.cno=‘2’StudentSC×Q1语法树：27πsnameσSC.cno=‘2’StudentSC×Q2语法树：σStudent.sno=SC.sno28πsnameσStudent.sno=SC.snoStudentSC×Q3语法树：σSC.cno=‘2’29精品课件！30精品课件！311找出计算机系女同学名单2求选修课程号为2的学生名单3求选修数据库课程的学生姓名及所在系4同时选修数据库及数学的学生名单5没有选修任何课程的学生名单及所在系6没有被任何人选修的课程名