《数据库系统原理：第二章关系模型与关系运算》由会员分享，可在线阅读，更多相关《数据库系统原理：第二章关系模型与关系运算（93页珍藏版）》请在金锄头文库上搜索。
1、第二章 关系模型与关系运算提纲n关系基本概念n关系模型n关系代数n元组关系演算n域关系演算n查询优化关系模型回顾nE.F.Codd于70年代初提出关系数据理论，他因此获得1981年的ACM图灵奖n关系理论是建立在集合代数理论基础上的，有着坚实的数学基础n早期代表系统nSystem：由IBM研制nINGRES：由加州Berkeley分校研制n目前主流的商业数据库系统nOracle，Informix，Sybase，SQL Server，DB2nAccess，VFP关系基本概念n域（Domain）n一组值的集合，这组值具有相同的数据类型n如整数的集合、字符串的集合、全体学生的集合n笛卡尔积（Cart
2、esian Product）n一组域D1 , D2 , Dn的笛卡尔积为:D1D2Dn = (d1 , d2 , , dn) | diDi , i=1,nn笛卡尔积的每个元素(d1 , d2 , , dn)称作一个n-元组（n-tuple）n元组的每一个值di叫做一个分量（component）n若Di的基数为mi，则笛卡尔积的基数为关系基本概念n例：设 D1为教师集合（T）= t1，t2 D2为学生集合（S）= s1，s2 ，s3 D3为课程集合（C）= c1，c2 则D1D2D3是个三元组集合，元组个数为232，是所有可能的（教师，学生，课程）元组集合元组集合n笛卡尔积可表为二维表的形式TS
3、Ct1s1c1t1s1c2t1s2c1t2s3c2关系基本概念n关系n笛卡尔积D1D2Dn的子集叫做在域D1 , D2 , Dn上的关系，用R(D1 , D2 , Dn )表示nR是关系的名字，n是关系的度或目n关系是笛卡尔积中有意义的子集n关系也可以表示为二维表关系TEACH(T, S, C)TSCt1s1c1t1s1c2t1s2c1t2s3c2元组属性关系基本概念n例：设 D1为母亲集合（M）= m1，m2 D2为儿子集合（S）= s1，s2 ，s3则 D1D2=， ， ， 而 母子关系母子关系 = ， 关系基本概念n三种类型的关系表n基本表n查询表n视图关系基本概念n候选键/码（Cand
4、idate Key）n关系中的一个属性组，其值能唯一标识一个元组。若从属性组中去掉任何一个属性，它就不具有这一性质了，这样的属性组称作候选码 如DEPT中的D#，DN都可作为候选码n任何一个候选码中的属性称作主属性主属性 如SC中的S#，C#n主键/码（Primary Key）n进行数据库设计时，从一个关系的多个候选码中选定一个作为主码 如可选定D#作为DEPT的主码n外部键/码（Foreign Key）n关系R中的一个属性组，它不是R的码，但它与另一个关系S的码相对应，则称这个属性组为R的外部码 如S关系中的D#属性关系基本概念n关系的性质n列是同质的n即每一列中的分量来自同一域，是同一类型
5、的数据。n如TEACH(T, S, C)=(t1 , s1 , c1), (t1 , t2 , c1)是错误的n不同的列可来自同一域，每列必须有不同的属性名。n如P=t1，t2 ， s1，s2 ，s3，C= c1，c2，则TEACH不能写成TEACH (P, P, C)，还应写成TEACH(T, S, C)n行列的顺序无关紧要n任意两个元组不能完全相同（集合内不能有相同的两个元素）n每一分量必须是不可再分的数据。满足这一条件的关系称作满足第一范式（1NF）的关系模型n数据结构n单一的数据结构关系n实体集、联系都表示成关系学生学生课程课程选修选修属于属于系系教师教师教授教授工作工作管理管理关系模
6、型关系模型关系模型n关系模式n关系的描述称作关系模式，包括关系名、关系中的属性名、属性向域的映象、属性间的数据依赖关系等，记作R(U, D, dom, F)， 简记为R(U) 或 R(A1 , A2 , An ) n属性向域的映象一般直接说明为属性的类型、长度等n某一时刻对应某个关系模式的内容(元组的集合)称作关系n关系模式是型，是稳定的 关系是某一时刻的值，是随时间不断变化的关系模型n关系数据库n其型是关系模式的集合，即数据库描述，称作数据库的内涵(Intension)n其值是某一时刻关系的集合，称作数据库的外延(Extension)关系模型n关系操作n关系操作是集合操作，操作的对象及结果都
7、是集合，是一次一集合（Set-at-a-time）的方式 而非关系型的数据操作方式是一次一记录（Record-at-a-time）n关系操作可以用关系代数和关系演算两种方式来表示，它们是相互等价的 如用关系代数来表示关系的操作，可以有选择、投影、连接、除、交、差、并等关系模型n关系模式的完整性n实体完整性n关系的主码中的属性值不能为空值n关系的主码值不能重复n空值：不知道或无意义n意义：关系对应到现实世界中的实体集，元组对应到实体，实体是相互可区分的，通过主码来唯一标识，若主码为空，则出现不可标识的实体，这是不允许的关系模型n参照完整性（引用完整性）n如果关系R2的外部码Fk与关系R1的主码P
8、k相对应，则R2中的每一个元组的Fk值或者等于R1 中某个元组的Pk 值，或者为空值n意义：如果关系R2的某个元组t2参照了关系R1的某个元组t1，则t1必须存在n例如关系S在D#上的取值有两种可能n空值，表示该学生尚未分到任何系中n若非空值，则必须是DEPT关系中某个元组的D#值，表示该学生不可能分到一个不存在的系中关系模型n用户定义的完整性n用户针对具体的应用环境定义的完整性约束条件n如S#要求是8位整数，SEX要求取值为“男”或“女”n系统支持n实体完整性和参照完整性由系统自动支持n系统应提供定义和检验用户定义的完整性的机制关系模型供应商号供应商名所在城市B01红星北京S10宇宙上海T2
9、0黎明天津Z01立新重庆零件号颜色供应商号010红B01312白S10 201蓝T20今要向关系P中插入新行，新行的值分别列出如下。哪些行能够插入？A(037，绿，null)B(null，黄，T20)C(201，红，T20)D(105，蓝，B01)E(101，黄，T11)零件关系P（主码是“零件号”，外码是“供应商号”） 供应商关系S（主码是“供应商号”）关系数据语言概述n关系数据语言的特点n一体化n一般关系系统的数据语言都同时具有数据定义、数据操纵和数据控制语言，而不是分为几个语言。对象单一，都是关系，因此操作符也单一。而非关系型系统，如DBTG，有对记录的操作，有对系的操作n非过程化n用户
10、只需提出“做什么”，无须说明“怎么做”，存取路径的选择和操作过程由系统自动完成n面向集合的存取方式n操作对象是一个或多个关系，结果是一个新的关系（一次一关系）。非关系系统是一次一记录的方式关系数据语言概述n抽象的查询语言n关系代数n用对关系的运算来表达查询，需要指明所用操作n关系演算n用谓词来表达查询，只需描述所需信息的特性n元组关系演算n谓词变元的基本对象是元组变量n域关系演算n谓词变元的基本对象是域变量关系数据语言概述n具体系统中的实际语言nSQLn介于关系代数和关系演算之间，由IBM公司在研制System R时提出nQUELn基于Codd提出的元组关系演算语言ALPHA，在INGRES上
11、实现nQBEn基于域关系演算，由IBM公司研制关系代数运算汇总n基本运算n一元运算n选择、投影、更名n多元运算n笛卡儿积、并、集合差n其它运算n集合交、自然连接、除、赋值n扩展运算n广义投影、外连接、聚集n修改操作n插入、删除、更新关系代数的一些记号 给定关系模式R(A1 , A2 , , An)，设R是它的一个具体的关系，tR是关系的一个元组n分量设tR，则tAi表示元组t中相应于属性Ai的一个分量n属性列A=Ai1, Ai2, ,AikA1, A2, ,An，称A为属性列或属性组A表示A1 ,A2 , ,An中去掉A后剩余的属性组tA = ( tAi1, tAi2, , tAik)表示元组
12、t在属性组A上的分量集合选择运算n基本定义在关系R中选择满足给定条件的元组（从行的角度） F(R)=t | t (R)=t | t R , F(t) = R , F(t) = 真真真真F是选择的条件，t R， F(t)要么为真，要么为假F的形式：由逻辑运算符逻辑运算符连接算术表达式算术表达式而成逻辑表达式：，算术表达式：X YX，Y是属性名、常量、或简单函数是比较算符， , , , , , 选择运算ABC367257723443RA5(R) ABC367257443A5 C=7(R) ABC367257ABC2572=5(R) 选择运算n示例n找年龄不小于20的男学生AGE20 SEX=男（S
13、）投影n定义n从关系R中取若干列组成新的关系（从列的角度） A(R) = tA | t R , A U n投影的结果中要去掉相同的行cbcfedcbaCBABCbcef R R B , C(R)投影n示例给出所有学生的姓名和年龄SN, AGE(S)找001号学生所选修的课程号C#( S#=001（SC）并运算n定义n所有至少出现在两个关系中之一的元组集合R R S = r | rS = r | r R R r r S S R Sn两个关系R和S若进行并运算，则它们必须是相容的：n关系R和S必须是同元的，即它们的属性数目必须相同n对i，R的第i个属性的域必须和S的第i个属性的域相同并运算ABC3
14、67257723443RABC345723SABC367257723443345RS 并运算n示例n求选修了001号或002号课程的学生号方案1：S#(C# = 001 C# = 002(SC) 方案2：S#(C# = 001 (SC)S#(C# = 002(SC)差运算n定义n所有出现在一个关系而不在另一关系中的元组集合R R S = r | rS = r | r R R r r S S nR和S必须是相容的R S差运算ABC367257723443RABC345723SABC367257443RS ABC345SR 差运算n示例求选修了001号而没有选002号课程的学生号S#(C# =00
15、1 (SC)S#(C# =002(SC)下列查询表达对不对？S#(C# = 001 C# 002 (SC)交运算n定义n所有同时出现在两个关系中的元组集合R S = r | r R r S n交运算可以通过差运算来重写RS = R (R S)R S交运算ABC367257723443RABC345723SABC723RS 交运算n示例求同时选修了001号和002号课程的学生号下面的查询表达正确吗？表达1：S#(C# = 001 C# = 002(SC)表达2：S#(C# = 001 (SC)S#(C# =002(SC)广义笛卡尔积运算n元组的连串（Concatenation）n若r = (r1
16、， ，rn)，s = (s1 ， ，sm)，则定义r与s的连串为：n定义n两个关系R，S，其度分别为n，m，则它们的笛卡尔积是所有这样的元组集合：元组的前n个分量是R中的一个元组，后m个分量是S中的一个元组nRS的度为R与S的度之和， RS的元组个数为R和S的元组个数的乘积rs = (r1， ，rn， s1 ， ，sm)R R S= S= rsrs | r | r R R s s S S 广义笛卡尔积运算AB12rCD10102010EaabbsAB11112222CD 1010201010102010Eaabbaabbr x s广义笛卡尔积运算nA=C(r x s)nr x snA=C(r
17、x s)AB11112222CD 1010201010102010EaabbaabbABCDE122102020aab更名运算（选学）n定义n给一个关系表达式赋予名字 x（E E）返回表达式E的结果，并把名字x赋给E x（A1 1， A2 2 ， ， An n ）（E E）返回表达式E的结果，并把名字x赋给E，同时将各属性更名为A1，A2， ，An n关系被看作一个最小的关系代数表达式，可以将更名运算施加到关系上，得到具有不同名字的同一关系。这在同一关系多次参与同一运算时很有帮助广义笛卡尔积运算n示例n求数学成绩比王红同学高的学生89数学张军86数学王红93物理张军成绩课程姓名S.姓名(R.成
18、绩S.成绩R.课程=数学S.课程=数学R.姓名=王红(RS( R)R86数学王红86数学王红86数学王红R.成绩R.课程R.姓名89数学张军86数学王红93物理张军S.成绩S.课程S.姓名连接n定义n从两个关系的广义笛卡儿积中选取给定属性间满足一定条件的元组 A,B为R和S上度数相等且可比的属性列 为算术比较符，为等号时称为等值连接n R S = rAsB( RS)A BA BR S = R S = R S = R S = rsrsrsrs | r | r | r | r R R R R s s s s S S S S rArArArA sBsBsBsB 连接n求数学成绩比王红同学高的学生。9
19、87654321CBADE3162ABCDE123311236245662 R S R S B D R R S SS.姓名(课程=数学姓名=王红(R) ( 课程=数学S(R)R.成绩2ABC456789 t | R(t) S(t) 元组关系演算ABC123346 t | S(t) u(R(u) tC uA)元组关系演算*n表达式的安全性n元组关系演算有可能会产生无限关系，这样的表达式是不安全的 如t | (t R)，求所有不在R中的元组n引入公式P的域域概念，用dom(P)表示 dom(P) = 显式出现在P中的值 + 在P中出现的关系的元组中出现的值（不必是最小集） 如dom ( t | (
20、t R) )是R中出现的所有值的集合n如果出现在表达式t | P（t）结果中的所有值均来自dom(P)，则称t | P（t）是安全的元组关系演算*ABA1B1A1B2A2B3dom( (t R) = A1 , A2 , B1 , B2 , B3ABA1B3A2B1A2B2R t | (t R) 元组关系演算n示例n找出工资在800元以上的老师t | PROF(t) tSAL 800n找出工资在800元以上的老师的姓名t | s(PROF(s) tPNAMEsPNAME sSAL800 )n给出计算机系老师的姓名t | u(DEPT(u)uDNAME=计算机系 s(PROF(s) sDNO=uD
21、NO tPNAME sPNAME )元组关系演算n求选修了全部课程的学生号t | us (C(u) SC(s) sCNO = uCNO tSNO sSNO )n求选修了张军同学所选修的全部课程的学生姓名课程，张军选之 所求同学选之t | u(C(u)( sw(SC(s)S(w)sCNO=uCNO wSNOsSNOwSNAME=张军) sw(SC(s)S(w)sCNO=uCNOwSNO sSNOwSNAME=tSNAME )元组关系演算n元组关系演算与关系代数的等价性n投影 A( R ) = t | s( R(s) tA = sA ) n选择 F(A)(R) = t | R(t) F(tA) n
22、广义笛卡儿积R(A) S(B) = t | us(R(u) S(s) tA=uA tB=sB)n并 RS= t | R(t) S(t)n差 RS= t | R(t) S(t)思考：连接运算应该如何表示？域关系演算n形式化定义 x1x2 xn | P（ x1 , x2 , , xn ）xi代表域变量，P为由原子构成的公式n原子公式nR( x1 , x2 , , xn )nxi是域变量或域常量nx yn域变量x与y之间满足比较关系 nx cn域变量x与常量c之间满足比较关系 域关系演算ABC123456789ABC123346569RSABC456R1= xyz | R(x, y, z) x3AB
23、C123456789346R2=xyz | R(x, y, z)S(x, y, z) y=4)DE7548WBDA574877847R2=xyz | (u) (v) ( R( z, x, u)W(y, v)uv)域关系演算n示例n找出工资在800元以上的老师 a b c d e | PROF(a , b , c , d , e) e800n找出工资在800元以上的老师的姓名 b | a , c , d , e ( PROF(a , b , c , d , e) e800 )n给出计算机系老师的姓名 b | l, m, n, s ( DEPT(l, m, n, s) m =计算机系计算机系 a
24、, c , d , e ( PROF(a , b , c , d , e) l = d ) ) 域关系演算域关系演算语言QBE*n基于屏幕表格的查询语言关系名属性名属性名操作命令元组属性值或查询条件域关系演算语言QBE*n查询基本要素StudentSnoSnameSsexSageSdeptP.张三20IS显示 示例元素(变量) 查询条件(与)域关系演算语言QBE*n示例n查询选修了001、002号课程的学生学号n查询选修了001或002号课程的学生学号SCSNOCNOGRADEP.95001001P.95001002SCSNOCNOGRADEP.95001001P.95002002域关系演算语
25、言QBE*n查询选修了DB及DS课程的学生姓名StudentSnoSnameSsexSageSdept99001P.张三SCSnoCnoGrade9900100199001002CourseCnoCname Credit001DB002DS查询优化n查询处理n查询优化n关系代数等价变化n查询优化策略n查询优化算法查询处理查询处理是指从数据库中提取数据的一系列活动。主要包括：n 将用高层数据库语言表示的查询语句翻译为能在文件系统这一物理层次上实现的表达式n 为优化查询而进行各种转换n 查询的实际执行输入：SQL语句输出：满足查询条件的数据查询优化查询优化是为关系代数表达式的计算选择最有效的查询计
26、划的过程。查询优化的过程：n 代数优化：力图找出与给定关系代数表达式等价的但执行效率更高的一个表达式。n 查询语句处理的详细策略的选择，例如选择执行运算所采用的具体算法，选择将使用的特定索引等等。查询优化查询代价的度量n查询代价：查询处理对各种资源的使用情况n 磁盘存取（简化为磁盘块传送数）n CPU时间n 通信开销n一个重要的影响因素：主存中缓冲区的大小Mn最好的情形，所有的数据可以读入到缓冲区中n最坏的情形，缓冲区只能容纳数目不多的数据块大约每个关系一块。查询优化对于关系数据库系统，查询优化是：n 挑战：必须进行好的优化，才有可接受的性能n 机会：关系表达式的语义层次高，提供了优化的可能性
27、。优化器有理由比程序员做得更好：n优化器具有丰富的可使用的信息n当数据库发生变化时优化器容易再次进行优化n优化器能够对多种实现策略逐一进行考虑n优化器集中了最优秀的程序员的智慧和经验表达式的等价性两个表达式等价：产生的结果关系具有相同的属性集和相同的元组集。例customer_name (branch-city=”gz” (branch (account depositor)等价于 customer_name (branch-city=”gz” (branch) (account depositor)表达式的等价性customer_namebranchcity=“gz” branch acco
28、unt depositorcustomer_namebranchcity=“gz” branch branch account depositor account depositor查询优化策略:启发式优化对关系代数表达式进行等价变换时，运用启发式规则。许多系统用启发式方法来减少在基于代价的方式中可选择的方案数。常用的规则：n尽早进行选择运算n尽早进行投影运算n避免进行笛卡尔积运算n.启发式规则通常能，但不总是能减少代价。查询基本运算的实现每一个基本的代数运算都有多种不同的实现算法。n适用于不同的情况n等值条件，范围条件n数据是聚集的，数据是非聚集的n相关属性上有索引，相关属性上没有索引n执行
29、代价不同主要有下列基本运算：n选择运算n排序运算n连接运算n其他运算作业S(SNO, SNAME, STATUS, CITY)P(PNO, PNAME, COLOR, WEIGHT, CITY)J(JNO, JNAME,CITY)SPJ(SNO, PNO, JNO, QTY)S S表表示示供供应应商商，它它的的各各属属性性依依次次为为供供应应商商号号，供供应应商商名名，供供应应商状态值，供应商所在城市；商状态值，供应商所在城市；P P表表示示零零件件，它它的的各各属属性性依依次次为为零零件件号号，零零件件名名，零零件件颜颜色色，零件重量，零件存放的城市；零件重量，零件存放的城市；J J表表示示工工程程，它它的的各各属属性性依依次次为为工工程程号号，工工程程名名，工工程程所所在在城城市；市；SPJSPJ表表示示供供货货关关系系，它它的的各各属属性性依依次次为为供供应应商商号号，零零件件号号，工工程号，供货数量。程号，供货数量。供应商供应商项目项目零件零件供应供应作业n用关系代数表达下列查询：（1）求供应工程J1(工程号)零件的供应商号码SNO；（2）求供应工程J1零件P1(零件号)的供应商号码SNO；（3）求供应工程J1零件为红色的供应商号码SNO；（4）求没有使用天津供应商生产的红色零件的工程号JNO；（5）求至少用了供应商S1所供应的全部零件的工程号JNO；
