关系数据库 关系演算

关系数据库关系演算第一页，共七十一页，2022年，8月28日第一节关系代数关系1.定义：令为D1，D2，Dn的笛卡尔集。若,则称r是D上的n元关系。例：

第二页，共七十一页，2022年，8月28日2.元组与分量：t表示关系中某一行，

表示这一行中的某一项数据。3.属性名：对一列的命名，D1,D2,..,Dn称为属性的域。第三页，共七十一页，2022年，8月28日二.关系的集合运算1.条件：列名相同，列数相同。每列有相同的域。2.并集：取两关系中的所有行。例1：设R,S为如下内容，求RS。

第四页，共七十一页，2022年，8月28日S：R：RS：RS：

ABC123323131ABC123321ABC123323131321ABC123第五页，共七十一页，2022年，8月28日3.交集：RS取关系中相同的行。如上例所示。差集：R-S取在R中且不在S中的行。例2：根据例1求R-S：得：5.交集可由差集表示：RS=R-（R-S））

ABC323131第六页，共七十一页，2022年，8月28日三.关系的专门运算笛卡尔积：RS：.模式组成：由两关系所有属性组成，包括相同的。.元组构成：两关系所有元组的配对。例3.求RSABD123231ABC123323131第七页，共七十一页，2022年，8月28日例3的结果：

R.AR.BCS.AS.BD123123123231323123323231131123131231第八页，共七十一页，2022年，8月28日2.选择运算：（r).模式不变，满足条件的元组。条件的构成：比较条件：属性与常数，属性与属性比较。逻辑条件：AND()，OR()，NOT().第九页，共七十一页，2022年，8月28日例4求下列选择。

ABC123131ABC123第十页，共七十一页，2022年，8月28日3.投影：新模式为：R(A1，A2，…，An)选取新模式下的元组。例5.例6.BC2331

A1第十一页，共七十一页，2022年，8月28日请问：若要选取中R的

第一列和S的第一列，应如何写关系代数式。

第十二页，共七十一页，2022年，8月28日4.换名改变属性或关系的名字例如：将R的属性改为C,D,E.得：CDE123323131第十三页，共七十一页，2022年，8月28日5.条件连接：RS说明：模式由R，S所有属性构成。元组由满足条件的元组构成。条件：出现在两关系中的属性相比较组成。例如：R.A=S.A或加上逻辑运算(AND)。例7.RS，其中：为R.A=S.AANDR.B>S.B。第十四页，共七十一页，2022年，8月28日例7的计算结果：

条件连接可由笛卡尔积表示，请写出来。RS=R.AR.BR.CS.AS.BS.D131123第十五页，共七十一页，2022年，8月28日6.自然连接RS模式构成：由两模式中去掉重复属性后的属性组成。元组构成：相同属性下相等值连接而成。例8：计算RP.R:P:ABC123323131ABD124223132第十六页，共七十一页，2022年，8月28日例8的结果：

请问：若对P进行换名再进行自然连接，结果如何？ABCD12341312第十七页，共七十一页，2022年，8月28日7.除法：要求：S的属性是R属性的子集。计算方法：求R的原像：求所有原像包含S的x的集合。

第十八页，共七十一页，2022年，8月28日例9求R:S:

注意：如何求ABC123323131ABC123323C3第十九页，共七十一页，2022年，8月28日关系运算的独立性交集的不独立性：条件连接：自然连接：RS=除法：

第二十页，共七十一页，2022年，8月28日除法举例：以例9为例：S：

（图一）(图二）一-RABC123323C31ABC123121323321ABC121321第二十一页，共七十一页，2022年，8月28日四.关系代数举例1.2.RR设关系：XS（XH，XM，SZYX，XB）XK（XH，KH，CJ）KC（KH，KM，KKXY）求下列查询：第二十二页，共七十一页，2022年，8月28日。

求学号为“200201234”的学生。求信息学院学生所选课的课号，课名。求还没有选任何课的学生学号。求同时选了两门课以上的学生。求每门课都及格了的学生。求选了信息学院所开所有课程的学生学号。第二十三页，共七十一页，2022年，8月28日答案1XH=“200201234”(XS)2.3.第二十四页，共七十一页，2022年，8月28日答案24.

5.6.第二十五页，共七十一页，2022年，8月28日五.运算树满足如下条件的树称为运算树：叶子结点为关系。其他结点为运算符。例：与代数式等价的运算树是：第二十六页，共七十一页，2022年，8月28日一棵运算数

第二十七页，共七十一页，2022年，8月28日扩展的关系运算外连接：在自然连接基础上添加未被连接上的元组。ABC232123ABD124323ABCD1234232NULL32NULL3第二十八页，共七十一页，2022年，8月28日第二节元组谓词演算一：谓词与集合1命题：有确定真假值的语句。谓词：表示论域个体性质或关系的符号。变元：表示论域个体的变量谓词集合：使得谓词为真的个体集合。如：X>Y,X是素数。5.约束变元与自由变元：如：第二十九页，共七十一页，2022年，8月28日一个例子设：P表示：x是z学院的学生，c表示学生选了y这门课。第三十页，共七十一页，2022年，8月28日二.原子公式的构成元组变元：s,t,x,y或加下标t1。关系谓词：R（t),P(x),等。算术比较谓词：s[I]与t[j]的比较。如：s[2]>t[4].第三十一页，共七十一页，2022年，8月28日三.合式公式的组成：1.原子公式是合式公式。逻辑运算引入：量词引入：元组演算的基本形式：其中：t为自由元组变元，为合式公式。第三十二页，共七十一页，2022年，8月28日四.元组演算举例交集：并集：差集`：笛卡尔积：第三十三页，共七十一页，2022年，8月28日应用举例：(见上节）

求学号为“200201234”的学生。2.求信息学院学生所选课的课号，课名。3.求还没有选任何课的学生学号。4.求同时选了两门课以上的学生。5.求每门课都及格了的学生。6.求选了信息学院所开所有课程的学生学号。第三十四页，共七十一页，2022年，8月28日答案1.3.4.6.第三十五页，共七十一页，2022年，8月28日五.元组演算规则由元组演算所产生的关系必须是有限关系。如：是无效的。第三十六页，共七十一页，2022年，8月28日第三节域谓词演算一：基本概念：域变量：用来表示域的变量域演算：由域变量谓词构成的逻辑公式。演算格式：第三十七页，共七十一页，2022年，8月28日二.基本公式域变量关系谓词：算术比较谓词：如x>y,x=8等。第三十八页，共七十一页，2022年，8月28日三.域演算合式公式基本公式是合式公式。用组成的公式。引入组成的公式。例如：R(x,y,z),是合式公式。不是合式公式。第三十九页，共七十一页，2022年，8月28日域演算的一般方法：定义域变量。选择关系。确定约束变量。第四十页，共七十一页，2022年，8月28日描述关系代数：.1.2.3.第四十一页，共七十一页，2022年，8月28日描述2笛卡尔积：选择投影第四十二页，共七十一页，2022年，8月28日五.应用举例1.2.第四十三页，共七十一页，2022年，8月28日六.请说出下列描述的含义1.第四十四页，共七十一页，2022年，8月28日续2.第四十五页，共七十一页，2022年，8月28日第四节数据逻辑DATALOG一演算规则：1.比较谓词2.关系谓词导出关系谓词，基本关系谓词3.域变量与哑元4.规则：规则头规则体5.查询：由一组规则组成。第四十六页，共七十一页，2022年，8月28日对规则的说明：规则头：只能是导出关系谓词。规则体：原子谓词原子谓词的否定用(and)连接以上两类谓词。例如：T(x,y,z)S(x,y,z)ANDx>1R(x,y)NOTQ(x,y)第四十七页，共七十一页，2022年，8月28日规则的语义变量的作用域是一条规则。关系谓词的作用域是一个查询（全局的)每一个导出关系谓词都对应一个需要求解的关系，关系由所有满足规则体的元组构成。例10T(x,y,z)S(x,y,z)ANDx>1T:S:ABD123231ABD231第四十八页，共七十一页，2022年，8月28日又一例例10.T(x,y)S(x,y,-)R:T(x,y)R(x,z,y)请问：T的值是多少？S:ABC123323131ABD123231第四十九页，共七十一页，2022年，8月28日二.逻辑公式的转化1.非内置否定的转化：NOT（AANDB）=NOTAANDNOTBOR条件的转化：AORB转化为两条规则。如：T(x)S(x,y,z)and(x=1orx=2)变为T(x)S(x,y,z)andx=1T(x)S(x,y,z)andx=2第五十页，共七十一页，2022年，8月28日三规则的安全性条件作用：排除无限关系。安全条件：在规则中所出现的变量必须在规则体中非否定的关系谓词中出现。如：Q(x,y)R(x)andy>0P(x,y)notS(x,y,z)andz=1Q(x,y)R(x)第五十一页，共七十一页，2022年，8月28日四规则的求解建立各关系的笛卡尔积一致性检查。若规则体为真，将元组加入导出关系中。例12设R={<1,2>,<5,3>,<3,3>},S={<2,2>,<3,4>}求规则Q(x,y)R(x,z)andS(z,y)andx>1andnotS(x,y).第五十二页，共七十一页，2022年，8月28日求解过程RS一致性X>1NOTS(x,y)(1,2)(2,2)tf(1,2)(3,4)f(5,3)(2,2)f(5,3)(3,4)ttt(3,3)(2,2)f(3,3)(3,4)???第五十三页，共七十一页，2022年，8月28日五描述关系代数并集：交集：差集：第五十四页，共七十一页，2022年，8月28日续笛卡尔集：Q(x,y,s,t)R(x,y)andS(s,t)投影：Q(x,y)R(x,y,z)自然连接：设R(A,B),S(B,C)Q(x,y,z)R(x,y)andS(y,z)其它的运算请同学自己考虑。第五十五页，共七十一页，2022年，8月28日Datalog的应用求信息和会计学院的学生求选了数据库的学生学号SJK(x)XK(x,y,-)andKC(y,z,-)andz=“数据库“

第五十六页，共七十一页，2022年，8月28日六递归查询递归查询：在规则中，导出关系谓词在规则头和规则体中同时出现。如：Q(x,y)R(x,y)andQ(y,z)2.关系代数的不动点设：y=f(x)是关于x的代数式子，若有r使得r=f(r)成立，则称r为该关系式的不动点。第五十七页，共七十一页，2022年，8月28日3.最小不动点在所有不动点中行数最小的关系称为最小不动点。例：求下列式子的不动点：f(r)=Sr设s={<1,2>,<1,3>}，r与s同模式。则：r0=,r1=s是不动点。

第五十八页，共七十一页，2022年，8月28日4.递归查询的解递归查询的解是其代数方程的最小不动点。求解方法：1).令r0=2).计算f(),3).若成立，则算法结束否则，继续迭代。

第五十九页，共七十一页，2022年，8月28日5.求不动点举例其中：Q={<1,2>,<2,1>},可见：是还有{<1,2>,<2,1>,<1,1>,<2,2>},还有吗？

第六十页，共七十一页，2022年，8月28日6.算法举例设S:AB13求：Q(x,y)S(x,y)24Q(x,y)Q(x,z)andS(z,y)32f(Q)=(计算最小不动点第六十一页，共七十一页，2022年，8月28日计算最小不动点q0:CBq1:CBq2:CBq3=q21313132424243232321212343414第六十二页，共七十一页，2022年，8月28日一个问题若第二条规则改为：Q(x,y)Q(x,z)andS(t,y）andz>t结果呢？q0:CBq1:CBq2:CBq3=q2?131313212121323232令s:AB*13*1313113321331132？第六十三页，共七十一页，2022年，8月28日这是一个对选手排序的问题请用DATALOG求出比指定选手积分高的选手编号。(2号选手)编号积分130223343415第六十四页，共七十一页，2022年，8月28日方法一设：JF(BH,JF)gf(x)jf(s,t)ands=“2”andjf(x,y)andy>t

方法二

第六十五页，共七十一页，2022年，8月28日方法三R(x,y,s,t)j