《第3章关系运算及关系系统PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第3章关系运算及关系系统PPT讲稿.ppt（178页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第3章关系运算及关章关系运算及关系系统系系统第1页，共178页，编辑于2022年，星期二3.1 关系代数关系代数 第2.2节已对关系模型的数据结构和完整性约束做了介绍。本节主要讨论数据操作，即关系运算。关系运算分为两种方法：一种方法基于代数的定义，称为关系代数；另一种方法基于逻辑的定义，称为关系演算。下面分两节讨论关系运算。第2页，共178页，编辑于2022年，星期二关系代数是一种抽象的查询语言，是关系数据操纵语言的一种传统表达方式。关系代数中给出的功能在任何实际语言中应该都能实现。关系代数是通过关系的运算来表达查询的。它的运算对象是关系，运算结果也是关系。第3页，共178页，编辑于2022
2、年，星期二关系代数的运算分为两类：（1）传统的集合运算：并、交、差和广义笛卡尔乘积。（2）专门的关系运算：选择、投影、连接和除。在集合运算中，还涉及到两类辅助运算符：（1）比较运算符：（大于）、（大于等于）、（小于）、（小于等于）、（等于）、（不等于）。（2）逻辑运算符：（非）、（与）、（或）。第4页，共178页，编辑于2022年，星期二3.1.1传统的集合运算传统的集合运算是二目运算（又称二元操作）。以下运算用到的两个关系R和S均为n度关系，且相应的属性取自同一个域。基本运算如下：1并（Union）关系R和S的并为：RS=t|tRtS其结果仍为n目关系。任取元组t，当且仅当t属于R或t属于S
3、时，t属于RS。第5页，共178页，编辑于2022年，星期二2差（Difference）关系R和S的差为：RS=t|tRt(S其结果仍为n目关系。任取元组t，当且仅当t属于R且t不属于S时，t属于R-S。3交（Intersection）关系R和S的交为：RS=t|tRtS其结果仍为n目关系。任取元组t，当且仅当t既属于R又属于S时，t属于RS。从集合论的观点分析，关系的交运算可表示为差运算：RS=R-(R-S）。第6页，共178页，编辑于2022年，星期二4笛卡尔乘积（CartesianProduct）设R为m目关系，S为n目关系，则R和S的广义笛卡尔乘积为：RS=t|t=tr，tstrRts
4、S其结果为m+n目关系。元组的前m列是关系R的一个元组，元组的后n列是关系S的一个元组。若R有k1个元组，S有k2个元组，则RS有k1k2个元组。第7页，共178页，编辑于2022年，星期二实际运算时，可从R的第一个元组开始，依次与S的每一个元组组合，然后对R的下一个元组进行同样的操作，直至R的最后一个元组也进行完相同操作为止，即可得到RS的全部元组。【例3.1】给定两个相容性关系R和S，计算RS，RS，RS，RS的结果。解：依据四种运算的定义，可得到如图3.2(a)、(b)、(c)、(d)所示的结果。第8页，共178页，编辑于2022年，星期二第9页，共178页，编辑于2022年，星期二图3
5、.2传统集合运算举例第10页，共178页，编辑于2022年，星期二3.1.2专门的关系运算专门的关系运算包括选择、投影、连接和除。前两个是一元操作，后两个为二元操作。1选择（Selection）设R是n目关系，F是命题公式，其结果为逻辑值，取“真”或“假”，则R的选择操作定义为：F（R）=t|tRF（t）=true即取出满足条件F的所有元组。其中，F包含下列两类符号：第11页，共178页，编辑于2022年，星期二运算对象（元组分量（属性名或列序号）、常数）；运算符（、）。例 如，对 表 3.1可 写 出：学 号 9811018（student），性 别=男6600（student）。前者取出学
6、号大于9811018的元组，后者取出入学成绩大于等于600的男性。F中的常量需用单引号括起。选择操作一般从行的角度进行运算。第12页，共178页，编辑于2022年，星期二2投影（Projection）设R是n目关系，R在其分量为1到m之间的整数，可不连续）上的投影操作定义为：即取出所有元组在特定分量上的值。第13页，共178页，编辑于2022年，星期二例如，对图3.1可写出：姓名，入学成绩（student），1，4，6（student）。前者取出所有元组的姓名、入学成绩两个分量的值，后者取出第一、第四、第六分量的值。ACa1a2c1c2图3.3投影说明举例第14页，共178页，编辑于2022年
7、，星期二投影操作一般从列的角度进行运算，可以改变关系中列的顺序。需要说明的是，投影操作消去部分列后，可能会出现重复元组，根据关系特性，应将重复元组删去。如例3.1给出的关系S，在域列A，C上投影后结果如图3.3所示。第15页，共178页，编辑于2022年，星期二3连接（Join）连接也称为连接，是从两个关系的笛卡尔乘积中选取属性间满足一定条件的元组。记作：=t|t=tr，tstrRtsStrAtsB=AB（RS）其中，A和B分别是R和S上目数相等且可比的属性组（名称可不相同）。AB作为比较公式F，F的一般形式为F1F2Fn，每个Fi是形为trAisBj的式子。第16页，共178页，编辑于202
8、2年，星期二下面介绍两种比较重要的连接：等值连接和自然连接。（1）等值连接（Equijoin)。当一个连接表达式中所有运算符取“=”时的连接就是等值连接，是从两个关系的广义笛卡尔乘积中选取A，B属性间相等的元组。记作：=t|t=tr，tstrRtsStrA=tsB=A=B（RS）若A和B的属性个数为n，A和B中属性相同的个数为k（nk0），则等值连接结果将出现k个完全相同的列，即数据冗余，这是它的不足。第17页，共178页，编辑于2022年，星期二（2）自然连接（Naturaljoin）。等值连接可能出现数据冗余，而自然连接将去掉重复的列。自然连接是一种特殊的等值连接，它要求两个关系中进行比较
9、的分量必须是相同的属性组，并且将去掉结果中重复的属性列。如 果 R和 S有 相 同 的 属 性 组 B，Att（R）和Att（S）分别表示R和S的属性集，则自然连接记作：Att(R)(Att(S)-B)（tB=tB(RS）)此处t表示：t|tRS。第18页，共178页，编辑于2022年，星期二自然连接和等值连接的区别是：等值连接相等的属性可以是相同属性，也可以是不同属性；自然连接相等的属性必须是相同的属性。自然连接必须去掉重复属性（指相等比较属性，其它相同属性不管），而等值连接无此要求。一般地，自然连接用于有公共属性的情况中。如果两个关系没有公共属性，那么它们的自然连接就退化为笛卡尔乘积。第1
10、9页，共178页，编辑于2022年，星期二例3.2给定如下关系R和S，计算：B5（R），A，B（R），RBDS，RR.B=S.BR.C=S.CS及RS（R和S及结果如图3.4所示）。第20页，共178页，编辑于2022年，星期二图3.4选择、投影、连接举例第21页，共178页，编辑于2022年，星期二图3.4选择、投影、连接举例第22页，共178页，编辑于2022年，星期二4除(Division)给定关系R（X，Y）和S（Y，Z），其中X，Y，Z为属性或属性组合。R中的Y和S中的Y可以有不同的属性名，但必须出自相同的域集。RS是满足下列条件的最大关系：其中每个元组t与S中的各个元组s组成的新元
11、组t，s必在关系R中。定义形式为：RS=X（R）X（X（R）S）R）=t|tX（R）且sS，t，sR关系的除操作需要说明的是：第23页，共178页，编辑于2022年，星期二（1）RS的新关系属性是由属于R但不属于S的所有属性构成的。（2）RS的任一元组都是R中某元组的一部分。但必须符合下列要求：即任取属于RS的一个元组t，则t与S的任一元组相接后，结果都为R中的一个元组。（3）R（X，Y）S（Y，Z）R（X，Y）Y（S）第24页，共178页，编辑于2022年，星期二（4）RS的计算过程如下：T=X（R）;W=（TS）R;V=X（W）;RS=TV。【例3.3】给定关系R和S，求RS（如图3.5）
12、。第25页，共178页，编辑于2022年，星期二图3.5除法操作举例第26页，共178页，编辑于2022年，星期二【例3.4】基于前边给出的关系数据库E、P、EP：E（E，EN，EA，EE，ED）Key=EP（P，PN，PL）Key=PEP（E，P，L）Key=E，P用关系代数完成下列问题的查询：第27页，共178页，编辑于2022年，星期二用关系代数完成下列问题的查询：检索维修班的全体职工。ED=WX（E）检索年龄大于48岁的女职工。EE=女348（S）查询职工的姓名和所在的部门。EN，ED（P）第28页，共178页，编辑于2022年，星期二检索参与了P5项目的职工的职工号与工时，进而给出对
13、应职工的姓名。1，3（2=P5（EP）EN（P=P5（EP）E）检索未参与名为“礼堂”项目的职工号、姓名。EN（PN=礼堂（P）EP）E）EN（E）EN（PN=礼堂（P）EP）E）第29页，共178页，编辑于2022年，星期二检索参与项目号为P2或P4的职工号、姓名。T=E（P=P2P=P4（EP）R=EN（TE）检索同时参与项目号为P2和P4的职工号。2（2=P25=P41=4（EPEP）或构造临时关系T，再求E，P（EP）T第30页，共178页，编辑于2022年，星期二检索参与全部项目职工姓名。EN（E，P（EP）P（P）E）检索参与项目包含职工E3参与项目的职工号，或参与项目不包含职工E
14、3所参与项目的职工号及姓名。E，P（EP）P（E=E3（EP）E（E）（E，P（EP）P（E=E3（EP）EN（E（E）（E，P（EP）P（E=E3（EP）E）第31页，共178页，编辑于2022年，星期二3.1.3扩充的关系代数运算根据前面讨论可知，涉及两个及两个以上关系表的查询必然用到连接运算,包括等值连接、非等值连接、自然连接。除此之外，为了保留更多信息，还有外连接、半连接、外部并、复合连接，这四类连接就是扩充的关系代数运算。第32页，共178页，编辑于2022年，星期二1外连接（Outerjoin）两个关系R和S在作自然连接时，选择两个关系在所有公共属性上值相等的元组组成新关系的元组。
15、此时，两个关系公共属性上值不相等的元组无法进入连接后的新关系，造成R和S中部分元组值被舍弃。这种舍弃是正常的，但有时希望该舍弃的元组继续保留在新关系中。第33页，共178页，编辑于2022年，星期二【例3.5】关系数据库S和SC两个关系有如下元组（如图3.6）：S（S，SN，SA，SE，SD）SC（S，C，G）执行运算SSC后，结果如图3.7。第34页，共178页，编辑于2022年，星期二图3.6基本关系R和S第35页，共178页，编辑于2022年，星期二图3.7SSC运算结果第36页，共178页，编辑于2022年，星期二从例3.5可见，结果关系中没有95003和95004两个学生的数据，原因
16、在于他们没有选课，即SC中无相应元组，这是正确的。但是，有时我们想以S为主体列出每个学生的基本情况及其选课情况，若该生未选课，则只输出其基本信息，其选课信息为空值，即产生如图3.8所示的结果(此时用到外连接)。第37页，共178页，编辑于2022年，星期二图3.8外连接说明举例第38页，共178页，编辑于2022年，星期二【定义3.1】如果R和S在作自然连接时，把该舍弃的元组也保留在新关系中，在新增加的属性上填上空值（NULL），那么这种操作称为外连接，用符号：RS表示。根据保留元组的不同，外连接又分为左外连接和右外连接。（1）左外连接。如果R和S在作自然连接时，只把R中原该舍弃的元组保留在新
17、关系中，那么这种操作称为左外连接，用符号RS表示。第39页，共178页，编辑于2022年，星期二（2）右外连接。如果R和S在作自然连接时，只把S中原该舍弃的元组保留在新关系中，那么这种操作称为右外连接，用符号：RS表示。【例3.6】在图3.9中给出两个基本关系R和S为(a)和(b)，可将其自然连接、外连接、左外连接、右外连接分别为(c)，(d)，(e)，(f)。从上述结果可见，外连接的交换律不成立，即RSRS.第40页，共178页，编辑于2022年，星期二图3.9外连接操作举例第41页，共178页，编辑于2022年，星期二2外部并（Outerunion）关系代数的传统集合运算中，讨论过关系的并
18、运算RS，由属于R或属于S的元组构成。此时要求两个关系R和S均为n目关系，且相应的属性取自同一个域。现实应用中，经常需要在具有不同关系模式（目不同或属性来自的域不同）的两个关系R和S上进行并运算，此涉时及到外部并运算。第42页，共178页，编辑于2022年，星期二【定义3.2】如果R和S具有不同的关系模式，RS是一种操作，其结果仍是关系，该关系的属性由R和S的所有属性组成（公共属性只取一次），该关系的元组由属于R或属于S的元组构成，此时元组在新增加的属性上填上空值，那么这种操作称为外部并操作。【例3.7】在例3.6中给出两个基本关系R和S，其外部并操作结果如图3.10。第43页，共178页，编
19、辑于2022年，星期二图3.10外部并操作举例第44页，共178页，编辑于2022年，星期二3半连接（Semijoin）【定义3.3】两个关系R和S的自然连接运算结果在关系R所有属性上的投影，记作：RS，即：RSAtt(R)（RS）=RAtt(R)Att(S)（S）第45页，共178页，编辑于2022年，星期二【例3.8】在例3.6给出的两个基本关系R和S，其自然连接和半连接操作结果如图3.11。图3.11半连接操作举例第46页，共178页，编辑于2022年，星期二4复合连接（Compoundjoin）复合连接是指在关系R和S的自然连接（RS）结果中，去除连接属性所产生的新关系。以上对关系代数
20、的主要运算已进行了详尽论述，其查询功能是相当强的。可以证明，关系代数操作集（，-，）是完备的操作集，任何其它关系代数操作都可以用这五种操作的组合来表示。任何一个DBMS，只要它能完成这五种操作，则称它是关系完备的。第47页，共178页，编辑于2022年，星期二3.2 关系演算关系演算 3.2.1元组关系演算元组演算中，元组演算关系表达式用t|(t)来表示。其中，t是元组变量，(t)为元组演算公式，简称公式。t|(t)表示所有使(t)为真的元组的集合。公式可以是原子公式，也可以由原子公式组合而成。第48页，共178页，编辑于2022年，星期二1(t)的基本形式原子公式原子公式有三类。（1）R(t
21、)。R是关系名，t是元组变量。R(t)表示t是R的元组。t|R(t)表示：任取t，只要t是R中的一个元组，t就是结果中的一个元组。t|R(t)即表示关系R。第49页，共178页，编辑于2022年，星期二（2）tiuj。t和u均为元组变量，是比较运算符（、），ti和uj分别表示t的第i个分量和u的第j个分量。原子公式tiuj表示：元组t的第i个分量和元组u的第j个分量之间满足运算。例如t1u3表示：元组t的第1个分量大于元组u的 第 3个 分 量。对 元 组 表 达 式t|R(t)t3t5，读者自行说出它的含义。第50页，共178页，编辑于2022年，星期二（3）tic或cti。此处，c为常量。
22、tic表示：元组t的第i个分量和常量c之间满足运算。如t130表示元组t的第1个分量不等于30。对元组表达式t|R(t)t355，读者自行说出它的含义。第51页，共178页，编辑于2022年，星期二2变量的约束特性程序设计中大量使用变量，根据变量作用域的不同，变量可分为局部变量和全局变量。类似的，元组谓词演算中也涉及同类问题。另外，离散数学的命题与关系代数部分也介绍了全称（）和存在（）两类量词。基于以上内容，下面介绍元组变量的自由和约束概念。第52页，共178页，编辑于2022年，星期二（1）自由元组变量。一个公式中，元组变量的前面没有全称量词（）或存在量词（）等符号，那么该元组变量称为自由元
23、组变量。自由元组变量类似于程序外部定义的外部变量或全局变量。（2）约束元组变量。一个公式中，元组变量的前面或者有全称量词（），或者有存在量词（）等符号，那么该元组变量称为约束元组变量。约束元组变量类似于程序内部定义的局部变量。第53页，共178页，编辑于2022年，星期二3公式(t)的递归定义公式(t)的递归定义有6条。（1）每个原子公式是公式。原子公式中的元组变量是自由元组变量。（2）如果1和2为公式，则1，12，12，12为公式。其含义分别表示：1为假，则1为真；1和2同时为真，则12为真；1或2为真，则12为真；1为真，则2为真。第54页，共178页，编辑于2022年，星期二（3）如果1
24、为公式，则t(1)为公式。表示：存在一个元组t使1为真。元组变量t在1中是自由的，在t(1)中是约束的。1中其它元组变量是自由还是约束的，在t(1)中没有改变。（4）如果1为公式，则t(1)为公式。表示：对于所有元组t均使1为真。元组变量的自由约束特性同（3）。第55页，共178页，编辑于2022年，星期二（5）在公式中各种运算符的优先级从高到低依次是：算术比较运算符最高；量词次之，且高于；逻辑运算符最低，且内部按、顺序计算；括号最优先，嵌套时先内后外；（6）有限次地使用上述五条规则得到的公式是元组关系演算公式，其它公式不是元组关系演算公式。第56页，共178页，编辑于2022年，星期二【例3
25、.9】图3.12（a）、（b）是给定的两个关系R和S，（c）、（d）、（e）、（g）分别是下列四个元组演算表达式的值(图(f)是投影前的中间结果，在t1,t2,t3上投影后即图(g)。R1=t|R(t)S(t)R2=t|(u)(S(t)R(u)t3u2)R3=t|(u)(R(t)S(u)t3u1)R4=t|(u)(v)(R(u)S(v)u1v2t1=u2t2=v3t3=u1)第57页，共178页，编辑于2022年，星期二图3.12元组关系演算举例第58页，共178页，编辑于2022年，星期二进一步分析可以发现，上述结果与特定的关系代数运算结果相同，例如R1相当于RS；R2相当于Att(R)（R
26、R.BS.CS）；R3相当于Att(R)（RR.CS.AS）；R4相当于R.B,S.C,R.A（RR.AS.BS）；所以关系代数与关系演算也存在等价性。第59页，共178页，编辑于2022年，星期二4关系演算内部的等价规则关系演算内部的等价规则有：（1）12等价于(12)12等价于(12)。（2）(t)(1(t)等价于(t)(1(t)(t)(1(t)等价于(t)(1(t)。（3）12等价于12。上述等价规则可用于关系演算表达式的分析证明。第60页，共178页，编辑于2022年，星期二5元组关系演算与关系代数的等价性从例3.9可知：关系代数运算可用元组关系演算表示；反之，元组关系演算可用关系代数
27、运算表示。同时所有关系代数运算都能用五种基本操作（，-，）来表示。因此只要把五种基本操作表示为元组演算表达式，其它复杂问题将迎刃而解。第61页，共178页，编辑于2022年，星期二（1）并操作（）：RS=t|R(t)S(t)（2）差操作（-）：RS=t|R(t)S(t)（3）笛卡尔乘积（）：RS=t(m+n)|(u(m)(v(n)(R(u)S(v)t1=u1t2=u2tm=umtm+1=v1tm+2=v2tm+n=vn)第62页，共178页，编辑于2022年，星期二式中，R是m目关系，S是n目关系，t(m+n)表示t的目数为m+n。（4）投影（）：i1,i2,ik=t(k)|(u)(R(u)t
28、1=ui1t2=ui2tk=uik)（5）选择（）：F（R）=t|R(t)FF是F在元组演算中等价的表示形式。第63页，共178页，编辑于2022年，星期二【例3.10】给定关系R和S均为二元关系，将关系代数表达式1,4（2=3（RS）转换成元组演算表达式。解：此题分步完成。第一步：先转换RS。RS=t|(u)(v)(R(u)S(v)t1=u1t2=u2t3=v1t4=v2)第64页，共178页，编辑于2022年，星期二第二步：再完成转化2=3（RS）。2=3（RS）=t|(u)(v)(R(u)S(v)t1=u1t2=u2t3=v1t4=v2t2=t3)第65页，共178页，编辑于2022年，
29、星期二第三步：最后完成转化1,4（2=3（RS）。1,4（2=3（RS）=w|(t)(u)(v)(R(u)S(v)t1=u1t2=u2t3=v1t4=v2t2=t3w1=u1w2=v2)上述结果化简，去掉元组变量t可得到如下结果：1,4（2=3（RS）=w|(u)(v)(R(u)S(v)u2=v1w1=u1w2=v2)第66页，共178页，编辑于2022年，星期二【例3.11】对例3.4给出的关系数据库E、P、EP：E（E，EN，EA，EE，ED）Key=EP（P，PN，PL）Key=PEP（E，P，L）Key=E，P用元组关系演算完成下列问题的查询：检索维修班的全体职工。t|E(t)t5=W
30、X检索年龄大于48岁的女职工。t|E(t)t3=48t4=女第67页，共178页，编辑于2022年，星期二查询职工的姓名和所在部门。t|(u)(E(u)t1=u2t2=u5)检索参与了P5项目的职工号和工时，进而给出对应职工的姓名。t|(u)(EP(u)u2=P5t1=u1t2=u2)t|(u)(v)(E(u)EP(v)v2=P5u1=v1t1=u2)第68页，共178页，编辑于2022年，星期二检索未参与名为“礼堂”项目的职工号及姓名。假定“礼堂”项目号为“P9”，先按项目号求解，再按项目名求解。.t|(u)(v)(E(u)EP(v)u1=v1v2P9t1=u1t2=u2).t|(u)(v)
31、(w)(E(u)EP(v)P(w)w1=v2u1=v1w2礼堂t1=u1t2=u2)第69页，共178页，编辑于2022年，星期二检索参与项目号为P2或P4的职工号，姓名。t|(u)(v)(EP(u)E(v)(u2=P2u2=P4)u1=v1t1=u1t2=u2)检索同时参与项目号为P2和P4的职工号及姓名。t|(u)(v)(w)(EP(u)EP(v)E(w)u2=P2v2=P4u1=v1u1=w1t1=w1t2=w2)第70页，共178页，编辑于2022年，星期二检索参与全部项目的职工姓名。t|(u)(v)(w)(E(u)P(v)EP(w)u1=w1w2=v1t1=u1)检索参与项目中包含职
32、工E3所参与项目的职工号，或参与项目不包含职工E3所参与项目的职工号及姓名。第71页，共178页，编辑于2022年，星期二先求参与项目中包含职工E3所参与项目的职工号：t|(u)(EP(u)(v)(EP(v)v1=E3(w)(EP(w)w1=u1w2=v2)t1=u1)再求参与项目中包含职工E3所参与项目的职工号及姓名：t|(u)(x)(EP(u)E(x)(v)(EP(v)v1=E3(w)(EP(w)w1=u1w2=v2)x1=u1t1=x1t2=x2)第72页，共178页，编辑于2022年，星期二最后求参与项目中不包含职工E3所参与项目职工号和姓名：t|(u)(x)(EP(u)E(x)(v)
33、(EP(v)v1=S3(w)(EP(w)w1=u1w2=v2)x1=u1t1=x1t2=x1)第73页，共178页，编辑于2022年，星期二3.2.2域关系演算关系演算的另一种形式是域关系演算。域关系演算和元组关系演算类似，所不同的是公式中的元组变量由域变量代替，且域变量具体代替的是元组变量的每一个分量，其变化范围是某个值域而不是一个关系。第74页，共178页，编辑于2022年，星期二域 关 系 演 算 表 达 式 的 一 般 形 式 为：t1t2tk|(t1,t2,tk)。其中，t1,t2,tk是域变量，(t1,t2,tk)为域关系演算公式，简称公式。t1t2tk|(t1,t2,tk)表示所
34、有使为真的那些t1,t2,tk所组成元组的集合。公式可以是原子公式，也可以由原子公式组合而成。第75页，共178页，编辑于2022年，星期二1的基本形式原子公式原子公式有三类：（1）R(t1,t2,tk)。R是一个k元关系，每个ti是常量或域变量。R(t1,t2,tk)表示由分量t1,t2,tk组成的元组属于R。（2）tiuj。ti为元组t的第i个分量，uj为元组u的第j个分量。原子公式tiuj表示域变量ti和uj满足关系。是比较运算符（、）。例如t1u3表示：元组t的第1个分量大于元组u的第3个分量。第76页，共178页，编辑于2022年，星期二（3）tic或cti。此处，c为常量。tic表
35、示：域变量ti和常量c之间满足运算。t130表示域变量ti不等于30。对域演算表达式t1t3|R(t1,t2,t3)t355，读者自行说出它的含义。2变量的约束特性域关系演算中变量的约束特性与元组关系演算变量的约束特性完全相同，也分为自由域变量和约束域变量。对此不再赘述。第77页，共178页，编辑于2022年，星期二3公式(t)的递归定义公式(t)的递归定义有6条：（1）每个原子公式是公式。原子公式中的域变量是自由域变量。（2）如果1和2为域关系演算公式，则1，12，12也是域关系演算公式。（3）如果为域关系演算公式，则(ti)也是域关系演算公式。（4）如果为域关系演算公式，则(ti)也是域关
36、系演算公式。第78页，共178页，编辑于2022年，星期二（5）在公式中各种运算符的优先级从高到低依次是：算术比较运算符最高；量词次之，且高于；逻辑运算符最低，且内部按、顺序计算；括号最优先，嵌套时先内后外；（6）有限次地使用上述五条规则得到的公式是域关系演算公式，其它公式不是域关系演算公式。第79页，共178页，编辑于2022年，星期二【例3.12】图3.13（a）、（b）、（c）是给定的三个关系R、S和W，（d）、（e）、（f）分别是下列三个域关系演算表达式的值。R1=xyz|R(xyz)x5y3R2=xyz|R(xyz)(S(xyz)y=4)R3=xyz|(u)(v)(R(zxu)w(y
37、v)uv)这里(u)(v)可简写成(uv)。第80页，共178页，编辑于2022年，星期二图3.13域关系演算举例第81页，共178页，编辑于2022年，星期二4元组表达式向域表达式的转换首先来介绍元组表达式向域表达式的转换。后边我们将进一步讨论：元组关系演算和域关系演算是等价的。设元组表达式是t|P(t)，t是k元变量，那么引进k个域变量t1t2tk，在公式中t用t1t2tk替换，ti用ti来替换。第82页，共178页，编辑于2022年，星期二对于每个量词（u）或（u），若u是m元的元组变量，那么引入m个新的域变量u1u2um。在量词的辖域内，u用u1u2um替换，ui用ui替换，（u）用（
38、u1）（u2）（um）替换（简写为（u1u2um），（u）用（u1）（u2）（um）替换（简写为（u1u2um）。第83页，共178页，编辑于2022年，星期二【例3.13】给定关系R和S均为二目关系，将关系代数表达式1,4（2=3（RS）转换成域演算表达式。解：此题在例3.11中已转化为如下的元组演算表达式：w|(u)(v)(R(u)S(v)u2=v1w1=u1w2=v2)第84页，共178页，编辑于2022年，星期二用上述方法转化为下列域表达式：w1w2|(u1u2)(v1v2)(R(u1u2)S(v1v2)u2=v1w1=u1w2=v2)进一步简化后可得到：w1w2|(u2)(R(w1u
39、2)S(u2w2)第85页，共178页，编辑于2022年，星期二【例3.14】将例3.4给出的关系数据库E、P、EP。用域关系演算完成下列问题的查询：E（E，EN，EA，EE，ED）Key=EP（P，PN，PL）Key=PEP（E，P，L）Key=E，P第86页，共178页，编辑于2022年，星期二检索维修班的全体职工。t1t2t3t4t5|E(t1t2t3t4t5)t5=WX检索年龄大于48岁的女职工。t1t2t3t4t5|E(t1t2t3t4t5)t3=48t4=女查询职工的姓名和所在部门。w1w2|(t1t2t3t4t5)(E(t1t2t3t4t5)w1=t2w2=t5)第87页，共17
40、8页，编辑于2022年，星期二检索参与了P5项目的职工号和工时，进而给出对应职工的姓名。w1w2|(t1t2t3)(EP(t1t2t3)t2=P5w1=t1w2=t2)t1|(u1u2u3u4u5)(v1v2v3)(E(u1u2u3u4u5)EP(v1v2v3)v2=P5u1=v1t1=u2)第88页，共178页，编辑于2022年，星期二检索未参与名为“礼堂”项目的职工号及姓名。假定“礼堂”项目号为“P9”，先按项目号求解，再按项目名求解。x1x2|(u1u2u3u4u5)(v1v2v3)(w1w2w3)(E(u1u2u3u4u5)EP(v1v2v3)P(w1w2w3)w1=v2u1=v1w2
41、礼堂x1=u1x2=u2)检索参与项目号为P2或P4的职工号及姓名。t1t2|(u1u2u3)(v1v2v3v4v5)(EP(u1u2u3)E(v1v2v3v4v5)(u2=P2u2=P4)u1=v1t1=u1t2=u2)第89页，共178页，编辑于2022年，星期二检索同时参与项目号为P2和P4的职工号及姓名。t1t2|(u1u2u3)(v1v2v3)(w1w2w3w4w5)(EP(u1u2u3)EP(v1v2v3)E(w1w2w3w4w5)u2=P2v2=P4u1=v1u1=w1t1=w1t2=w2)检索参与全部项目的职工姓名。t1|(u1u2u3u4u5)(v1v2v3)(w1w2w3)
42、(E(u1u2u3u4u5)P(v1v2v3)EP(w1w2w3)u1=w1w2=v1t1=u1)第90页，共178页，编辑于2022年，星期二检索参与项目中包含职工E3所参与项目的职工号，或参与项目不包含职工E3所参与项目的职工号及姓名。先求参与项目中包含职工E3所参与项目的职工号：t|(u1u2u3)(w1w2w3w4w5)(EP(u1u2u3)E(w1w2w3w4w5)(v1v2v3)(EP(v1v2v3)v1=E3(x1x2x3)(EP(x1x2x3)x1=u1x2=v2)w1=u1t1=w1t2=w2)第91页，共178页，编辑于2022年，星期二最后求参与项目中不包含职工E3所参与
43、项目职工号和姓名：t|(u1u2u3)(w1w2w3w4w5)(EP(u1u2u3)E(w1w2w3w4w5)(v1v2v3)(EP(v1v2v3)v1=E3(x1x2x3)(EP(x1x2x3)x1=u1x2=v2)w1=u1t1=w1t2=w2)第92页，共178页，编辑于2022年，星期二3.2.3关系运算的安全性前边已经明确，计算机不能处理无限关系，也不能进行无穷验证，所以我们不希望关系运算导致无限关系和无穷验证。在数据库技术中，不产生无限关系和无穷验证的运算称为安全运算，相应的表达式称为安全表达式，所采取的措施称为安全约束。关系代数中，以集合论为基础研究的关系均为有限元组的集合，基本
44、操作是并、差、笛卡尔乘积、投影和选择，其运算结果是有限的，所以关系代数运算总是安全的。第93页，共178页，编辑于2022年，星期二关系演算可能产生无限关系和无穷验证。例如，元组关系演算t|R(t)是有限的，由属于R的元组构成；而t|R(t)是无限的，由不属于R的元组构成。又如，域关系演算t1|S(t1t2)t2=20是有限的，取出t2分量为20的元组在t1上投影构成的集合；而t1t2|S(t1t2)t220是无限的，t2分量大于20的值是无限的。同样验证，(t)(t)为假时，必须对所有可能的元组t进行验证，当所有的t都使(t)为假时，第94页，共178页，编辑于2022年，星期二才 能 断
45、定 公 式(t)(t)为 假；验 证(t)(t)为真时，必须对所有可能的元组t进行验证，当所有的t都使(t)为真时，才能断定公式(t)(t)为真。上述这些判定实际上是行不通的，一方面计算机的存储空间不允许无限关系，另一方面在计算机上进行无穷验证永远得不到结果。因此，我们必须对关系演算加以限定，使之具有安全性。下面我们先讨论元组演算公式的安全性。第95页，共178页，编辑于2022年，星期二1元组演算公式的安全性【定义3.4】设是一个元组关系演算公式。由如下两类符号构造集合：（1）中的常量；（2）中出现的关系的所有元组的所有属性值。我 们 把 该 集 合 称 作 的 符 号 集 合（记 作：DO
46、M（）。例如公式P(t)是t1=aR(t)，若R是二元关系，则DOM（P）=a1(R)2(R)。第96页，共178页，编辑于2022年，星期二【例3.14】给定关系R和S（如图3.14），=t|t 1=b R(t)S(t)，求DOM（）。图3.14符号集求解用例关系第97页，共178页，编辑于2022年，星期二解：根据定义进行解答：DOM（）=bA(R)B(R)C(R)D(S)E(S)F(S)=b,a,3,5,g,h,1,6,7,d,c,f,e第98页，共178页，编辑于2022年，星期二定义3.5一个元组关系演算表达式t|(t)是安全的，如果:（1）如果（t）为真，则元组t的每个分量都属于D
47、OM（）；（2）对于中每个形如(t)(F(t)的子表达式，如果F(u)为真，则元组u的每个分量都属于DOM（）。换言之，如果u有某个分量不属于DOM（），那么F(u)必为假；第99页，共178页，编辑于2022年，星期二（3）对于中每个形如(t)(F(t)的子表达式，如果F(u)为假，则元组u的每个分量都属于DOM（）；换言之，如果u有某个分量不属于DOM（），那么F(u)必为真。上面(2)和(3)保证，要确定具有量词的公式(t)(F(t)和(t)(F(t)的真假值，只需考虑DOM（F）中符号组成的元组t。第100页，共178页，编辑于2022年，星期二【例3.16】给定关系R（如图3.15（
48、a），=t|R(t)，若不进行安全限制，则元组运算表达式是不安全的，求DOM（）。第101页，共178页，编辑于2022年，星期二图3.15符号集求解用例关系第102页，共178页，编辑于2022年，星期二解：根据定义进行解答：DOM（）=A(R)B(R)C(R)=a1,a2,b1,b2,c1,c2不限制时，t|R(t)只要取不属于R的元组即可，为无限关系，如图3.15（b）。如果进行限定：要求（t）为真的元组各分量的值来自DOM（），则此时构成关系如图3.15（c），而且是惟一的，为有限关系。所以施加限制，t|R(t)演算结果将会变得安全。本例中是DOM（）中各域的笛卡尔乘积与R的差集。第1
49、03页，共178页，编辑于2022年，星期二2域演算公式的安全性【定义3.6】一个域关系演算表达式t1t2tk|(t1,t2,tk)是安全的：（1）如果(t)为真，则为真元组t1t2tk的每个分量ti都属于DOM()；（2）对于的每个形如(x)(1(x)的子表达式，如果x使1(x)为真，那么x必在DOM（1）中。换言之，如果有x不属于DOM（1），那么1(x)必为假；第104页，共178页，编辑于2022年，星期二（3）对于的每个形如(x)(1(x)的子表达式，如果x使1(x)为假，那么x必在DOM（1）中。换言之，如果有x不属于DOM（1），那么1(x)必为真；同样上面(2)和(3）保证，要
50、确定具有量词的公式(x)(1(x)和(x)(1(x)的真假值，只须考虑DOM（1）中符号组成的元组t。通过上述定义，施加相应约束，原本不安全的域关系演算表达式t1t2|S(t1t2)t220变安全了。第105页，共178页，编辑于2022年，星期二【例3.19】若R和S是同类的k元关系，证明：集合的差运算表达式t1t2tk|R(t1t2tk)S(t1t2tk)是安全的。证明（紧扣定义3.6，证明（1）即可）根据关系演算基本规律可知：任何使R(t1t2tk)S(t1t2tk)为真的元组t1t2tk必然在R中，从而每个分量ti一定在DOM(R)中。由于DOM(R)(DOM(RS)，所以每个分量ti