第2章关系型数据库.ppt-淘文阁

资源描述

《第2章关系型数据库.ppt》由会员分享，可在线阅读，更多相关《第2章关系型数据库.ppt（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第第2章章关系型数据库关系型数据库主要内容：主要内容：关系数据库概述。关系数据库概述。关系模型的物理与数学定义。关系模型的物理与数学定义。关系代数运算。关系代数运算。关系演算：元组演算与域演算。关系演算：元组演算与域演算。重点：重点：关系代数运算关系代数运算2.1 关系数据库概述关系数据库概述关系数据库系统是支持关系模型的数据库系统。关系数据库系统是支持关系模型的数据库系统。关系数据结构关系数据结构关系操作关系操作关系完整性约束关系完整性约束关系模型由三部分组成：关系模型由三部分组成：1、关系数据结构、关系数据结构关系模型中的数据结构是二维表格。关系模型中的数据结构是二维表格。关系模

2、型数学定义为笛卡尔集中的有意义的子集。关系模型数学定义为笛卡尔集中的有意义的子集。2、关系操作、关系操作查询操作查询操作更新（增、删、改）操作更新（增、删、改）操作其中，其中，查询是更新的基础查询是更新的基础，它是关系最重要和最基本的操作。，它是关系最重要和最基本的操作。关系的操作：关系的操作：关系操作的结果：关系（集合）。关系操作的结果：关系（集合）。关系代数关系代数:选择、投影、连接、除、并、交、差等。选择、投影、连接、除、并、交、差等。关系元组演算关系元组演算关系域演算关系域演算关系演算：关系演算：关系操作关系操作的数学表达：的数学表达：常用的关系操作的语言：常用的关系操作的语言

3、：SQL关系操作语言的特点：关系操作语言的特点：n 具有完备的表达能力。具有完备的表达能力。n 非过程化的集合操作语言。非过程化的集合操作语言。n 语句即可交互使用又可嵌套到高级语言中使用。语句即可交互使用又可嵌套到高级语言中使用。3、关系完整性约束、关系完整性约束关系的完整性：指关系中关系的完整性：指关系中数据的相容性和正确性数据的相容性和正确性。实体完整性实体完整性参照完整性参照完整性用户定义完整性用户定义完整性关系三类完整性关系三类完整性：关系模型关系模型物理表示：二维表格。物理表示：二维表格。数学表示：笛卡尔积上有意义的子集。数学表示：笛卡尔积上有意义的子集。关系模型：直观地

4、说就是关系模型：直观地说就是用二维表格表示实体集，外键表示实体用二维表格表示实体集，外键表示实体间联系的数据模型。间联系的数据模型。关系模型表示：关系模型表示：一、关系模型的物理表示一、关系模型的物理表示二维表格表示，如：一张学生注册表二维表格表示，如：一张学生注册表学号学号姓名姓名性别性别出生年月出生年月99019902 张一张一王三王三男男女女80.179.12行行关系模式关系模式R(表头表头)元组元组1元组元组2实体集实体集(文件文件)r:元组集合元组集合(关关系系)值域值域(列列)关系模型关系模型=关系模式关系模式+关系关系n 关系模式关系模式:它是静态的它是静态的(不随时间

5、变化不随时间变化),稳定的稳定的,它由属性名组成它由属性名组成.n 关系是由元组组成的值集关系是由元组组成的值集.它是随操作而变化它是随操作而变化.1、关系模式、关系模式(relation schema)组成组成:取自二维表的表头中的数据取自二维表的表头中的数据.一般组成一般组成:关系模式是一个五元组关系模式是一个五元组:R(U,D,DOM,F)其中其中:R为关系模式名为关系模式名:可取自二维表的表名可取自二维表的表名;不同的关系模式其名不同不同的关系模式其名不同.U 为为属性名表属性名表:上例上例:学号学号,姓名姓名,出生年月出生年月,性别性别;属性名各异属性名各异.D 为属性的域名为属性的

6、域名,指指属性取值的类型属性取值的类型;如如:学号的类型为字符串学号的类型为字符串.DOM 为为属性的取值的宽度属性的取值的宽度(长度长度);如如:学号取值学号取值8个字符个字符(最大最大).F 为为属性间依赖关系的集合属性间依赖关系的集合,表明属性间的语义表明属性间的语义;如如:学号学号姓名姓名.关系模式通常简记为关系模式通常简记为:R(A1,A2,.,An);其中：其中：A1,A2,.,An为属性名。为属性名。如如:上例上例:student(sno,name,sex,date)2、关系、关系关系（表体中的数据）：元组的集合。关系（表体中的数据）：元组的集合。每一个元组描述一个实体，关系

7、对应实体集。每一个元组描述一个实体，关系对应实体集。基本表：实际存在的表，实际存储数据的逻辑表示。基本表：实际存在的表，实际存储数据的逻辑表示。查询表：对查询表：对DB操作后的结果表（结果关系）。操作后的结果表（结果关系）。视图视图(虚表虚表)：由基本表或其他视图导出的表，不：由基本表或其他视图导出的表，不对应实际存储数据。对应实际存储数据。注：在实际中，常把关系和关系模式系统称为关系，可根据上注：在实际中，常把关系和关系模式系统称为关系，可根据上下文区分。下文区分。关系的三种关系的三种类型类型：3、基本关系的性质（对关系的限定）、基本关系的性质（对关系的限定）关系中每一列（关系中每一列（

8、属性）必须是不可再分的基本数据项属性）必须是不可再分的基本数据项，且具，且具有同一类型，列名各异，列的排列次序无关紧要。有同一类型，列名各异，列的排列次序无关紧要。关系中关系中不允许出现相同的元组不允许出现相同的元组，元组之间的次序任意。，元组之间的次序任意。4、关键字（、关键字（Key）超键：唯一标识元组的属性集超键：唯一标识元组的属性集。如。如(sno,name)侯选键：不含多余属性的超键。如侯选键：不含多余属性的超键。如sno 或或name（无同名同姓时）（无同名同姓时）。主键：被选用的侯选键。如：主键：被选用的侯选键。如：sno 或可选或可选name（无同名同姓时）（无同名同姓时）。外

9、键外键：用来联系关系的键。用来联系关系的键。如：如：stu(sno,name,sex,date,dno)dno是外键；是外键；dept(dno,dname,addr)5、名词对照表、名词对照表人工管理人工管理信息世界信息世界关系领域关系领域层次、网状层次、网状领域领域计算机计算机表头表头表框架表框架关系模式关系模式记录型记录型记录型记录型表体表体实体集实体集关系（元组集）关系（元组集）记录值集记录值集文件文件行行实体实体元组元组记录值记录值记录值记录值列（栏目）列（栏目）属性属性属性属性数据项数据项字段字段列值列值属性值集属性值集属性值集属性值集

10、域值域值字段值字段值识别项识别项实体标识符实体标识符关键字（键）关键字（键）码（键）码（键）码码二、关系模型的数学定义二、关系模型的数学定义关系模型是建立在集合代数的基础之上。关系模型是建立在集合代数的基础之上。关系用笛卡尔积来定义的。关系用笛卡尔积来定义的。笛卡尔积定义：给定一组域笛卡尔积定义：给定一组域D1，D2，Dn，这些域可以完全，这些域可以完全相同或不同或部分相同，则相同或不同或部分相同，则n个集合的笛卡尔积：个集合的笛卡尔积：D1 D2Dn=(d1,d2,dn)|diDi,i=1,2,Di,i=1,2,n,n 其中每一个元素（其中每一个元素（d1,d2,dn）称为一个元组；元素

11、中每一个分）称为一个元组；元素中每一个分量值量值di 称为元组的一个分量。称为元组的一个分量。笛卡尔积是一个以元组为元素的集合，且笛卡尔积可以表示一笛卡尔积是一个以元组为元素的集合，且笛卡尔积可以表示一个二维表。个二维表。例：给定例：给定D1=0,1,D2=a,b,c，则：，则：D1 D2=(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)(即每个元组的第一即每个元组的第一个分量取值为个分量取值为D1,第二个分量取值为第二个分量取值为D2,)笛卡尔积的二维表示：笛卡尔积的二维表示：D1D201abc=D1D2000111abcabc基数：基数：23=6个元组个元组关系模式

12、的笛卡尔积定义：关系模式的笛卡尔积定义：笛卡尔积笛卡尔积D1D2Dn的任一子集称为定义在的任一子集称为定义在D1，D2，Dn上的一个上的一个n元关系模式，简记为元关系模式，简记为:R（D1，D2，Dn)。注：实际关系数据库中的每一个关系都是一个注：实际关系数据库中的每一个关系都是一个笛卡尔积的有意义笛卡尔积的有意义的子集的子集,即其中的每个元组必须符合实际意义。即其中的每个元组必须符合实际意义。例：设例：设D1=张三，李四张三，李四，D2=男，女男，女则有：则有：D1D2=（张三，男），（张三，女），（李四，男），（张三，男），（张三，女），（李四，男），（李四，女）（李四，女）假定：张三本是

13、男，李四本是女，显然（张三，女）和（李假定：张三本是男，李四本是女，显然（张三，女）和（李四，男）是没有意义的元组四，男）是没有意义的元组,应该去掉。即有意义的子集：应该去掉。即有意义的子集：D1D2=（张三，男），（李四，女）（张三，男），（李四，女）注意：注意：关系的基数：就是元组的个数。关系的基数：就是元组的个数。上例：关系的基数为上例：关系的基数为6 关系的元数（度或目）：属性的个数关系的元数（度或目）：属性的个数。上例：关系的元数为上例：关系的元数为2。三、关系完整性三、关系完整性为了保证关系模型中数据的正确性和一致性，必须对关系中数为了保证关系模型中数据的正确性和一致性，必须对关系

14、中数据作完整性的约束。据作完整性的约束。三类完整性约束三类完整性约束规则：规则：实体完整性约束规则实体完整性约束规则参照完整性约束规则参照完整性约束规则用户自定义约束规则用户自定义约束规则：用户定义，系统检查。：用户定义，系统检查。系统自动支持系统自动支持 1、实体完整性规则、实体完整性规则关系中所有主属性都不能取空值关系中所有主属性都不能取空值。而不是仅主关键字不能取空。而不是仅主关键字不能取空值。值。组成候选关键字的属性称为主属性。组成候选关键字的属性称为主属性。如：选课（如：选课（学号学号，课号课号，成绩）中：主属性学号和课号都应有，成绩）中：主属性学号和课号都应有值，即不能为空值（无

15、值）。值，即不能为空值（无值）。2、参照完整性规则、参照完整性规则不引用不存在的实体不引用不存在的实体.例：有关系模式例：有关系模式s(sno,name,sex,age)sc(sno,cno,grade)其中：其中：sno是是s的主关键字，也是的主关键字，也是sc中的外键，它联系着中的外键，它联系着s与与sc，这，这时称时称s为参照关系；为参照关系；sc为被参照关系（或称依赖关系）。为被参照关系（或称依赖关系）。如果关系如果关系sc中有一个元组（中有一个元组（s7,c4,80），此时学号），此时学号s7在关系在关系s中找不到中找不到,则认为在则认为在sc中引用了一个不存在的学生实体，这就违

16、中引用了一个不存在的学生实体，这就违反了参照完整性规反了参照完整性规则。则。3、用户自定义完整性规则、用户自定义完整性规则用户自定义完整性规则反映某一具体应用涉及的数据必须满足用户自定义完整性规则反映某一具体应用涉及的数据必须满足的语义的语义要求。要求。如：学生的如：学生的“年龄年龄”定义两位整数，则值范围太大；写一条规则，定义两位整数，则值范围太大；写一条规则，把把“年龄年龄”属性取值规定属性取值规定1530之间。之间。2.3 关系代数关系代数关系关系DB操作语言是以数学中的关系代数和谓词演算为基础研制操作语言是以数学中的关系代数和谓词演算为基础研制的。的。关系查询语言：关系查询语言

17、：关系代数语言：以集合代数操作为基础运算关系代数语言：以集合代数操作为基础运算的的DML（非过程性弱）（非过程性弱）关系演算语言：以谓词演算为基础的关系演算语言：以谓词演算为基础的DML （非（非过程性强）过程性强）分为：分为：元组关系演算语言元组关系演算语言域关系演算语言域关系演算语言一、关系代数的一、关系代数的5种基本操作种基本操作关系代数的操关系代数的操作：作：传统的集合运算：传统的集合运算：，-，扩充的关系运算：扩充的关系运算：（投影）、（投影）、（选择）、（选择）、（联接）、（联接）、（除）（除）关系代数完备的且基本的操作集：关系代数完备的且基本的操作集：，,五种。五种。其它的

18、运算并非基本，都可由这其它的运算并非基本，都可由这5 种操作导出。种操作导出。1、并（、并（）设设R和和S是同类关系（模式相同：属性相同，个数相等），是同类关系（模式相同：属性相同，个数相等），RSS结果果为一同一同类关系，它由既属于关系，它由既属于R R又属于又属于S S中的元中的元组构成的集合。构成的集合。用元用元组变量形式定量形式定义：RSt|tRRSt|tR tS;ttS;t为元元组变量。量。ABCadcbabcfdAB Cbdgaaf例：例：ABCadcbbabgcfdaRSRSS相同元组相同元组只选一个只选一个特征：特征：为二目运算为二目运算从从“行行”上取值上取值作用：在一个关

19、系中插入一个数据集合，自动去掉相同元组。作用：在一个关系中插入一个数据集合，自动去掉相同元组。2、差（、差（）设设R与与S为同类关系，则为同类关系，则R和和S的差是由属于的差是由属于R而不属于而不属于S 的所有元组组成的集合。的所有元组组成的集合。用元组变量形式定义：用元组变量形式定义：例：例：ABCacbbcd作用：从某关系中删去另一关系作用：从某关系中删去另一关系 R-S3、笛卡尔积（、笛卡尔积（）设设R为为K1元关系，元关系，S为为K2元关系，则元关系，则RS是一个（是一个（K1+K2）元数）元数的集合，其中元组的前的集合，其中元组的前K1个分量是个分量是R的一个元组，后的一个元组，后K

20、2个分量个分量是是S的一个元组。共有的一个元组。共有nm个元组（个元组（n为为R元组数，元组数，m为为S元组数）。元组数）。用元组变量形式定义：用元组变量形式定义：RS S t|t=t R t S t|t=t R t S k1k1k2k2例：例：ABC142536 D EacbdABCDE114422553366acacbdbdRSRSk1=3k2=2k1+k2=3+2=5属性属性nm=22=4个个元元组组特征：特征：“列列”合并，合并，“行行”组合组合作用：将两个关系（同类或不同类）无条件地连成一个新关系。作用：将两个关系（同类或不同类）无条件地连成一个新关系。4、投影（、投影（）在在n元关

21、系元关系R（A1，A2，An）中选取中选取k（kn）列属性，并去掉）列属性，并去掉重复元组构成的新关系：重复元组构成的新关系：R1(A1，A2，Ak）。）。用元组变量定义用元组变量定义i1,i2,im(R)(R)t|t=tt|t=R R 例：例：ABC147258369AC147369RA，C（R R）=11，33（R R）若有重复元组应去掉。若有重复元组应去掉。特征：运算对象为单个关系，在特征：运算对象为单个关系，在“列列”上纵向分割关系。上纵向分割关系。作用：在关系中选取某些列组成一个新关系。作用：在关系中选取某些列组成一个新关系。5、选择（、选择（）其中：其中：F由下列成分组成：由下列成

22、分组成：运算对象：常数（用引号括起来），属性名或属性的列号。运算对象：常数（用引号括起来），属性名或属性的列号。算术比较符：算术比较符：,=,=,;逻辑运算符：，逻辑运算符：，,用元组变量形式定义：用元组变量形式定义：F（R）t|tRt|tR F(t)=true F(t)=true从关系从关系R中挑选满足条件中挑选满足条件F为真的元组组成新关系为真的元组组成新关系，记为，记为F（R）例：例：ABCadcbcbcbdABCacbbcdR B=bB=b(R)(R)2=b2=b(R)(R)特征：对一个关系进行特征：对一个关系进行“行行”运算，即为横向选择。运算，即为横向选择。作用：在一个关系中，选择

23、作用：在一个关系中，选择满足条件的元组构成新关系满足条件的元组构成新关系（关系模式不变）（关系模式不变）运算符：运算符：二、关系代数的二、关系代数的4种组合运算种组合运算包括：交（包括：交（），联接（），联接（），自然联接（），自然联接（）和除法（）和除法（）操作。操作。1.交（交（）求同类关系求同类关系R和和S中相同的元组的集合中相同的元组的集合.用元组变量形式定义：用元组变量形式定义：RSSt|tt|tRtSRtS 例：例：ABCb2cABCab32bcABCabc124bcdSRRS S注：注：RS=R-S=R-（R-SR-S）用差运算表示。）用差运算表示。特征：关系模式不变，从两关系中

24、取相同的元组。特征：关系模式不变，从两关系中取相同的元组。2.联接（联接（）设设R（A1，A2，Ak1）和）和S（B1，B2，Bk2（1ik1,1jk2ik1,1jk2），），i，j分分别是别是R和和S的第的第i个分量和第个分量和第j个分量；个分量；联接是笛卡尔积中的一个子集，其元组必联接是笛卡尔积中的一个子集，其元组必须符合须符合R的第的第i个分量值和个分量值和S的第的第j个分量值之间的个分量值之间的关系，记为关系，记为R S。用元组变量形式定义：用元组变量形式定义：R St|=t t R Rt t S St t t t 其中：其中：t 和和 t 分别表示分别表示R中的第中的第i个分量值，和

25、个分量值，和S中第中第j个分量值，个分量值，t t t 表示这两个分量值满足表示这两个分量值满足操作。操作。iijjk1k1k1k2k2k2ijiijjk1k2ijk2k1ji即：即：R S (RS S)ijij运算步骤：（运算步骤：（1）求求RS=T（A1，A2，Ak1，B1，B2，Bk2）R S （2）在在T中选择中选择 i j 成立的元组成立的元组。例：求例：求R S=S=35 (RS S)ABC147258369DEab78ABCD E778899ab78ABCDE114477225588336699ababab787878RS（1）求求RS S（2）35 (RS S)ABCDE789

26、a732注：当注：当为为“=”时，时，R S 称为等值联接。称为等值联接。i=j求：求：R S1=2特征：两个关系不一定有公共属性特征：两个关系不一定有公共属性不去掉重复属性。不去掉重复属性。作用：将两个关系按一定的条件联接在一起。作用：将两个关系按一定的条件联接在一起。3.自然联接（自然联接（）自然联接是自然联接是的的特殊情况。特殊情况。设关系设关系R和和S有相同的属性名有相同的属性名Ai(i=1,2,k)，则，则R S S是从是从RS中中挑选挑选RA1=SA1RRA2=SA2=SA2A2RRAk=S.AkAk=S.Ak的所有元组，的所有元组，并去掉重复属性的元组集合并去掉重复属性的元组

27、集合。元组变量形式表示元组变量形式表示:t|t=t|t=(R(t)S(t)R(R(t)S(t)RA1=SA1=SA1RA1RA2=SA2=SA2A2RRAi=SAi=SAiAi 运算过程：运算过程：计算计算RS挑选挑选RAi=SAi（即属性名相同，值相等）的所有元组（即属性名相同，值相等）的所有元组去掉重复属性去掉重复属性即：即：R SSi1,i2,i1,i2,im,im(R RA1=SA1=SA1A1 R RAKAK=S=SAKAK(R(RS)S)R s=例例:B C D259368235A B C147258369A B C D14253623RS RS S 去掉重复属性去掉重复属性B,C

28、：R S ABCS.BS.C D 1 2 3 2 3 2 1 2 3 5 6 3 1 2 3 9 8 5 4 5 6 2 3 2 4 5 6 5 6 3 4 5 6 9 8 5 7 8 9 2 3 2 7 8 9 5 6 3 7 8 9 9 8 5ABCS.BS.C D 1 2 3 2 3 2 4 5 6 5 6 3R.B=S.BR.C=S.C (RS)注：（注：（1）在无公共属性时，自然联接变化为笛卡尔积。）在无公共属性时，自然联接变化为笛卡尔积。（2）等值联接与自然联接的区别：）等值联接与自然联接的区别：a.等值联接要求相等的属性不一定相同。等值联接要求相等的属性不一定相同。自然联接要求相

29、等的属性一定相同。自然联接要求相等的属性一定相同。b.等值联接不要求去掉重复属性。等值联接不要求去掉重复属性。自然联接要求去掉重复属性。自然联接要求去掉重复属性。（3）自然联接是关系）自然联接是关系DB中最重要的操作之一。中最重要的操作之一。4.除法（除法（）设关系设关系R和和S分别为分别为m元和元和n元关系，则元关系，则RS 结果为一个结果为一个mn元关系。其元组决定为：先将被除关系元关系。其元组决定为：先将被除关系R中的中的mn 列按列按值分成若干组，每个组中参入分组的值分成若干组，每个组中参入分组的mn 列以外的那些列列以外的那些列中是否包含除关系中是否包含除关系S的全部元组，包含则取该

30、的全部元组，包含则取该mn 列的值列的值作为商关系的一个元组，否则不取。作为商关系的一个元组，否则不取。用元组变量形式表示用元组变量形式表示:RSt|t=St|t=t 若若t s,t s,则则RR m1n2nnm-nn例例:ABCDaaaeebbbddcedcedfedfCDcedfABaebdRSRS S 三、关系代数表达式及应用三、关系代数表达式及应用用关系代数对关系运算，即用关系代数对关系运算，即写出运算表达方式。写出运算表达方式。步骤：步骤：根据已知条件确定关系根据已知条件确定关系根据查询结果确定关系根据查询结果确定关系根据运算语义写出查询代数表达式。根据运算语义写出查询代数表

31、达式。是否其条件属性与是否其条件属性与结果属性在同一关系中，结果属性在同一关系中，若不在同一关系中，若不在同一关系中，根据什么属性联系的。根据什么属性联系的。例：设例：设DB中有三个关系模式：中有三个关系模式：学生关系：学生关系：s(s#，sname，age，sex)学习关系：学习关系：sc（s#，c#，grade）课程关系：课程关系：c（c#，cname，teacher）用关系代数表达式，表示下列各种查询。用关系代数表达式，表示下列各种查询。1查找学习课程号为查找学习课程号为C2的学生的学号与成绩的学生的学号与成绩s#,grade(s#,grade(c#=c#=c2c2(sc)(sc)(学号

32、、成绩与课程号在同一关系学号、成绩与课程号在同一关系scsc中中)2查找选修课程号为查找选修课程号为C2或为或为C4的学生的学号的学生的学号s#(s#(c#=c#=c2c2c#=c#=c4c4(sc)(sc)(学号与课程号在同一关系学号与课程号在同一关系scsc中中)或：或：s#(s#(c#=c2 c#=c4（s#,c#s#,c#(sc)(说明表达式不唯一说明表达式不唯一)3查找至少学习查找至少学习C2和和C4课程的学生的学号课程的学生的学号 11(1=41=42=2=c2c25 5=c4c4(scscscsc)s#1c#2grade3s#4c#5grade6sc sc4查找不学习查找不学习C

33、2课的学生的姓名与学号课的学生的姓名与学号 sname,s#sname,s#(s)-(s)-sname,s#sname,s#(c#=c#=c2c2(s (s scsc）错误写法错误写法 :s#,sname(s#,sname(c#c#c2c2(s (s scsc）)5查找选修全部课程的学生姓名查找选修全部课程的学生姓名 snamesname(s (s (s#,c#s#,c#(sc)(sc)c#(c)(c#(c)(在三个关系中关联查在三个关系中关联查找找)6查找学习课程名为查找学习课程名为DB的学生姓名的学生姓名 snamesname(s (s s#s#(scsc c#c#(cname=cname

34、=DBDB(c)c)在三个关系中找在三个关系中找,或或 snamesname(s#,sname(s)s#,sname(s)s#(s#(s#,c#(sc)s#,c#(sc)c#(cname=DB(C)课号与姓名不在同一关系中，分别在课号与姓名不在同一关系中，分别在 sc 和和s，但，但 s 和和sc 通通过过s#联系的联系的 2.3.3 关系代数式的查询优化关系代数式的查询优化一一.关系关系DB的查询优化概述的查询优化概述关系关系DB的查询优化分为：代数优化和物理优化。的查询优化分为：代数优化和物理优化。代数优化：指关系代数表达式的优化。（本节重点）代数优化：指关系代数表达式的优化。（本节

35、重点）物理优化：指存取路径的选择和低层操作算法的选择。物理优化：指存取路径的选择和低层操作算法的选择。1.关系关系DB的查询处理过程的查询处理过程查询处理过程：查询分析，查询检查，查询优化，查询执行。查询处理过程：查询分析，查询检查，查询优化，查询执行。查询分析：对查询语句进行扫描，词法分析和语法分析。判断查询分析：对查询语句进行扫描，词法分析和语法分析。判断查询语句是否合法。查询语句是否合法。查询检查：根据数据字典，检查查询语句的语义，用户的存取权查询检查：根据数据字典，检查查询语句的语义，用户的存取权限和完整性的定义。检查通过后，把限和完整性的定义。检查通过后，把SQL语句转换成等价的关

36、系语句转换成等价的关系代数表达式。代数表达式。一般用查询树（又称：语法分析树）表示关系代数表达式。一般用查询树（又称：语法分析树）表示关系代数表达式。查询优化：选择高效执行的查询处理策略。查询优化：选择高效执行的查询处理策略。查询执行：由代码生成器执行根据查询策略生成的查询计划的代码。查询执行：由代码生成器执行根据查询策略生成的查询计划的代码。查询优化过程：查询优化过程：查询语句查询语句词法分析词法分析，语法分析，语义分析，符号名转换，语法分析，语义分析，符号名转换安全性检查，完整性检查安全性检查，完整性检查查询树查询树代数优化，物理优化代数优化，物理优化执行策略描述执行策略描述代码生

37、成代码生成查询计划的执行代码查询计划的执行代码数据库数据字典数据库数据字典查询语句查询语句代数表达式的语法分析树代数表达式的语法分析树物理优化策略物理优化策略查询优化代码查询优化代码代码生成器代码生成器 2.关系代数运算的优化问题关系代数运算的优化问题问题：选择怎样的关系代数表达式表示查询，省时，省空问题：选择怎样的关系代数表达式表示查询，省时，省空间，速度快呢？间，速度快呢？例：有三个等价的关系代数表达式例：有三个等价的关系代数表达式E1，E2，E3：E1=A（B=CD=99（RS）)，先做笛卡尔积，后做选择和投影。，先做笛卡尔积，后做选择和投影。E2=A（B=C（R D=99（

38、S）)，先做选择，后做笛卡尔积。，先做选择，后做笛卡尔积。E3=A（R （D=99（S），先做选择，后做联接。），先做选择，后做联接。注：注：E1：先做笛卡尔积，占大量的内存空间。：先做笛卡尔积，占大量的内存空间。E2和和E3:先对先对S做选择操作会减少大量的元组，再与做选择操作会减少大量的元组，再与R做联做联接时，内存空间花费小，存取的次数少，花费接时，内存空间花费小，存取的次数少，花费CUP的时间少。的时间少。关系代数运算的优化原则：在保证语义正确的情况下，关系代数运算的优化原则：在保证语义正确的情况下，先先安排选择，投影运算，然后进行笛卡尔积，联接运算。安排选择，投影运算，然后进行笛卡尔

39、积，联接运算。B=C 二二.关系代数表达式的优化算法关系代数表达式的优化算法利用等价变换规则（见利用等价变换规则（见p53）对关系代数表达式优化的算法）对关系代数表达式优化的算法如下：如下：算法：算法：输入：关系代数表达式的一棵语法树。输入：关系代数表达式的一棵语法树。（树中的叶子结点是关系，非叶子结点是操作符）（树中的叶子结点是关系，非叶子结点是操作符）输出：计算该表达式的优化程序。输出：计算该表达式的优化程序。算法思想：算法思想：.利用变换规则将表达式写成只包含五种关系代数的基利用变换规则将表达式写成只包含五种关系代数的基本运算本运算(，)，绘出表达式的语法树；，绘出表达式的语法树；.

40、将选择操作尽量向叶子结点移动（即，先做选择操作）将选择操作尽量向叶子结点移动（即，先做选择操作）；然后，将投影操作尽量向叶子结点移动（即，后做投影操；然后，将投影操作尽量向叶子结点移动（即，后做投影操作）。最后得到一棵表达式的优化的语法树。作）。最后得到一棵表达式的优化的语法树。.对优化的语法树，由下至上扫描，就是计算该表达式对优化的语法树，由下至上扫描，就是计算该表达式的优化程序。的优化程序。例子：教学数据库：例子：教学数据库：S(SNO,SNAME,AGE,SEX);SC(SNO,CNO,GRADE);C(CNO,CNAME,TEACHER)。有一查询：查询至少学习有一查询：查询至少学习L

41、I老师所授一门课的女学生的学号与姓老师所授一门课的女学生的学号与姓名。名。关系代数表达式：关系代数表达式：SNO，SNAME（TEACHER=LI SEX F（SC C S）(1)建立语法树建立语法树将上式中的将上式中的用用,操作表示：操作表示：SNO，SNAME（TEACHER=LI SEX F(L(SC.CNO=C.CNO SC.SNOS.SNO（SC C S）)）其中：其中：L为：SNO,SNAME,AGE,SEX,CNO,CNAME,GRADE,TEACHER.语法树如下：语法树如下：|SNO，SNAME|TEACHER=LI SEX=F|L:SNO,SNAME,AGE,SEX,C

43、次向上扫描。2.4 关系演算关系演算把数理逻辑的谓词引入到关系中的运算。把数理逻辑的谓词引入到关系中的运算。元组关系运算：以元组为变量。元组关系运算：以元组为变量。域关系运算：以属性（域）为变量。域关系运算：以属性（域）为变量。关系演算：关系演算：一、元组关系运算（一、元组关系运算（tuple relation calculus）1元组运算表达式元组运算表达式一般形式：一般形式：t|p(t)其中：其中：t 为元组变量；为元组变量；P（t）是由原子公式和运算符组成的公式。）是由原子公式和运算符组成的公式。含义：满足公式含义：满足公式P 所有元组的集合。所有元组的集合。（1）原子公式）原子公式

44、aR（t）：）：R为关系名，为关系名，t为元组变量。为元组变量。含义：含义：t为为R中的任意一个元组。中的任意一个元组。b.tiuj：t和和u是元组变量，是元组变量，ti和和uj为分量，为分量，是算术比较符。是算术比较符。含义：元组含义：元组t的第的第i个分量与元组个分量与元组u的第的第j个分量满足个分量满足关系为真。关系为真。例：例：t3 u2：t 的第的第3个分量值大于个分量值大于u的第的第2个分量值时为真。个分量值时为真。c.tic或或cuj:c为常量。为常量。含义：元组含义：元组t的第的第i分量与常量分量与常量c满足满足关系时为真。关系时为真。例：例：t2=2:表示元组表示元组t的第的

45、第2个分量的值等于个分量的值等于2时为真。时为真。（2）运算符）运算符算术比较符算术比较符，=，存在量词：存在量词：和全程量词和全程量词:逻辑运算符：逻辑运算符：（非），（非），（与），（与），（或）（或）括号运算优先级最高括号运算优先级最高低低高高高高低低2元组运算元组运算例：设有关系例：设有关系R和和S如下如下A1A2A31790afec1895A1 A2A31342aacb1540RS计算下列元组表达式的值计算下列元组表达式的值:(1)R1=t|R(t)(1)R1=t|R(t)s(t)s(t)R-SR-SA1 A2 A3342acb540R1A1 A2 A313aa15R2(2)R2=t

46、|R(t)(2)R2=t|R(t)t2=at2=a 22 =a=a(R)(R)说明：说明：若若t作为作为R的元组变量：的元组变量：R(t)，则，则t1,t2,t3分量分别表示分量分别表示A1,A2,A3(3)R3=t|(3)R3=t|(u u)(R(t)(R(t)s(u)s(u)t1u3 t1u3 t2 t2 b)b)R 1S 3R 1V1 u1V1 t1 t1 =u2 =u2 t2=v2 t2=v2 t3=u1)t3=u1)RA2 SA2RA1aaaccbbcacacac1334422A1 A2 A3143aca145A3A115401342R5R4R3例：已知学生关系模式例：已知学生关系模

47、式S（Sno,Sname,age,sex）用元组演算表达式表示查询用元组演算表达式表示查询查询所有男同学姓名和学号查询所有男同学姓名和学号:t|(u u)(S(u)u4=男男 t1=u2 t2=u1)二、域关系运算二、域关系运算(domain relation calculus)(domain relation calculus)1.1.域关系表达式域关系表达式一般形式：一般形式：X X1 1，X X2 2,X,XK K (X X1 1，X X2 2,X,XK K )其中：其中：X X1 1，X X2 2X Xk k表示关系中的域表示关系中的域变变量；量；是原子公式与运算符是原子公式与运算符组

48、组成的公式成的公式含含义义：所有使得：所有使得为为真的那些真的那些X X1 1，X X2 2X XK K组组成的元成的元组组集合。集合。R R（X X1 1，X X2 2，X XK K）；）；R R 为为 K K 元关系元关系,Xi,Xi为为常量或域常量或域变变量量含含义义：由分量：由分量X X1 1，X X2 2，X XK K 组组成的元成的元组组属于属于R.R.X Xi iCC或或CXCXi i：C C为为常量，常量，X Xi i为为域域变变量量;为为运算符，含运算符，含义义同同前前 X Xi iXXj j ：x xi i和和y yj j 分分别为别为元元组组X X和和Y Y的域的域

49、变变量。量。原子原子公式：公式：例：设关系例：设关系R 和和 S，W如下：如下：DEF254abcdefABC552bdc634ABC541bac168RSW计算计算（1 1）R1=xyf|R(xyf)R1=xyf|R(xyf)(f5(f5 y=a)y=a)(2)R2=xyf|R(xyf)(2)R2=xyf|R(xyf)S(xyf)S(xyf)x=5 x=5 f f66(3)R3=xyf|(3)R3=xyf|(v v)()(u u)(R(yxu)(R(yxu)w(vTf)w(vTf)u u v)v)ABC41ac68BAFaaaccc444111defdefABC5415bacd1683R1R

50、2R32域演算例子域演算例子将元将元组组表达式化表达式化为为等价的域表达式等价的域表达式方法：方法：元元组变组变量量t,用用域变域变量名替代量名替代：对对于于k元的元元的元组变组变量量t，引入，引入k 个域变量个域变量t1,t2,tk；在公式中在公式中t,用用t1，t2，tk 替替换换。元元组组分量分量t i ，用用域变量名域变量名t i 替替换换。每每个个量量词词（u u）或或（u u）元元组组变变量量u,u,用用域域变变量量u1，u2，um代替。代替。u i 用用u i 替替换换例：例：W|(u u)(v)v)(R(u)S(v)u2=v1 w1=u1 w2=v2 S(v)u2=v1 w1=

展开阅读全文

第2章 关系型数据库.ppt

第2章关系型数据库.ppt