关系数据库关系演算PPT讲稿.ppt

《关系数据库关系演算PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《关系数据库关系演算PPT讲稿.ppt（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关系数据库 关系演算第1页，共71页，编辑于2022年，星期五第一节 关系代数一.关系 1.定义：令 为D1，D2，Dn的笛卡尔集。若 ,则称r是D上的n元关系。例：第2页，共71页，编辑于2022年，星期五 2.元组与分量：t表示关系中某一行，表示这一行中的某一项数据。3.属性名：对一列的命名，D1,D2,.,Dn 称为属性的域。第3页，共71页，编辑于2022年，星期五二.关系的集合运算1.条件：列名相同，列数相同。每列有相同的域。2.并集：取两关系中的所有行。例1：设R,S为如下内容，求R S。第4页，共71页，编辑于2022年，星期五 S：R：R S：R S：ABC123323131A

2、BC123321ABC123323131321ABC123第5页，共71页，编辑于2022年，星期五 3.交集：R S取关系中相同的行。如上例所示。4.差集：R-S 取在R中且不在S中的行。例2：根据例1求R-S：得：5.交集可由差集表示：R S=R-（R-S）A B C323131第6页，共71页，编辑于2022年，星期五三.关系的专门运算1.笛卡尔积：R S：.模式组成：由两关系所有属性组成，包括相同的。.元组构成：两关系所有元组的配对。例3.求R SABD123231ABC123323131第7页，共71页，编辑于2022年，星期五例3的结果：R.AR.BCS.AS.BD12312312

3、3231323123323231131123131231第8页，共71页，编辑于2022年，星期五2.选择运算：（r).模式不变，满足条件的元组。条件的构成：比较条件：属性与常数，属性与属性比较。逻辑条件：AND()，OR()，NOT().第9页，共71页，编辑于2022年，星期五例4 求下列选择。ABC123131ABC123第10页，共71页，编辑于2022年，星期五3.投影：新模式为：R(A1，A2，An)选取新模式下的元组。例5.例6.BC23 31 A 1第11页，共71页，编辑于2022年，星期五请问：若要选取 中R的第一列和S的第一列，应如何写关系代数式。第12页，共71页，编辑

4、于2022年，星期五4.换名 改变属性或关系的名字 例如：将R的属性改为 C,D,E.得：CDE123323131第13页，共71页，编辑于2022年，星期五5.条件连接：R S 说明：模式由R，S所有属性构成。元组由满足条件的元组构成。条件：出现在两关系中的属性相比较组成。例如：R.A=S.A 或加上逻辑运算(AND)。例7.R S，其中：为 R.A=S.A AND R.BS.B。第14页，共71页，编辑于2022年，星期五例7的计算结果：条件连接可由笛卡尔积表示，请写出来。R S=R.AR.BR.CS.AS.BS.D131123第15页，共71页，编辑于2022年，星期五6.自然连接R S

5、 模式构成：由两模式中去掉重复属性后的属性组成。元组构成：相同属性下相等值连接而成。例8：计算R P.R:P:ABC123323131ABD124223132第16页，共71页，编辑于2022年，星期五例8的结果：请问：若对P进行换名 再进行自然连接，结果如何？ABCD12341312第17页，共71页，编辑于2022年，星期五7.除法：要求：S的属性是R属性的子集。计算方法：求R的原像：求所有原像包含S的x的集合。第18页，共71页，编辑于2022年，星期五例9 求 R:S:注意：如何求ABC123323131ABC123323C3第19页，共71页，编辑于2022年，星期五关系运算的独立性

6、1.交集的不独立性：2.条件连接：3.自然连接：R S=4.除法：第20页，共71页，编辑于2022年，星期五除法举例：以例9为例：S：（图一）(图二）一-RABC123323C31ABC123121323321ABC121321第21页，共71页，编辑于2022年，星期五四.关系代数举例1.2.R R设关系：XS（XH，XM，SZYX，XB）XK（XH，KH，CJ）KC（KH，KM，KKXY）求下列查询：第22页，共71页，编辑于2022年，星期五。1.求学号为“200201234”的学生。2.求信息学院学生所选课的课号，课名。3.求还没有选任何课的学生学号。4.求同时选了两门课以上的学生。

7、5.求每门课都及格了的学生。6.求选了信息学院所开所有课程的学生学号。第23页，共71页，编辑于2022年，星期五答案1 XH=“200201234”(XS)2.3.第24页，共71页，编辑于2022年，星期五答案2 4.5.6.第25页，共71页，编辑于2022年，星期五五.运算树满足如下条件的树称为运算树：叶子结点为关系。其他结点为运算符。例：与代数式等价的运算树是：第26页，共71页，编辑于2022年，星期五一棵运算数 第27页，共71页，编辑于2022年，星期五扩展的关系运算 外连接：在自然连接基础上添加未被连接上的元组。ABC232123ABD124323ABCD1234232NUL

8、L32NULL3第28页，共71页，编辑于2022年，星期五第二节 元组谓词演算一：谓词与集合 1 命题：有确定真假值的语句。2谓词：表示论域个体性质或关系的符号。3变元：表示论域个体的变量4谓词集合：使得谓词为真的个体集合。如：XY,X是素数。5.约束变元与自由变元：如：第29页，共71页，编辑于2022年，星期五一个例子 设：P表示：x是z学院的学生，c 表示学生选了y这门课。第30页，共71页，编辑于2022年，星期五二.原子公式的构成元组变元：s,t,x,y或加下标t1。关系谓词：R（t),P(x),等。算术比较谓词：sI与tj的比较。如：s2t4.第31页，共71页，编辑于2022年

9、，星期五三.合式公式的组成：1.原子公式是合式公式。2.逻辑运算引入：3.量词引入：4.元组演算的基本形式：其中：t为自由元组变元，为合式公式。第32页，共71页，编辑于2022年，星期五四.元组演算举例交集：并集：差集：笛卡尔积：第33页，共71页，编辑于2022年，星期五应用举例：(见上节）1.求学号为“200201234”的学生。2.求信息学院学生所选课的课号，课名。3.求还没有选任何课的学生学号。4.求同时选了两门课以上的学生。5.求每门课都及格了的学生。6.求选了信息学院所开所有课程的学生学号。第34页，共71页，编辑于2022年，星期五答案1.3.4.6.第35页，共71页，编辑于

10、2022年，星期五五.元组演算规则由元组演算所产生的关系必须是有限关系。如：是无效的。第36页，共71页，编辑于2022年，星期五第三节 域谓词演算一：基本概念：域变量：用来表示域的变量 域演算：由域变量谓词构成的逻辑公式。演算格式：第37页，共71页，编辑于2022年，星期五二.基本公式1.域变量关系谓词：2.算术比较谓词：如 xy,x=8等。第38页，共71页，编辑于2022年，星期五三.域演算合式公式基本公式是合式公式。用 组成的公式。引入 组成的公式。例如：R(x,y,z),是合式公式。不是合式公式。第39页，共71页，编辑于2022年，星期五域演算的一般方法：定义域变量。选择关系。确

11、定约束变量。第40页，共71页，编辑于2022年，星期五四.描述关系代数：.1.2.3.第41页，共71页，编辑于2022年，星期五四.描述2笛卡尔积：选择投影第42页，共71页，编辑于2022年，星期五五.应用举例1.2.第43页，共71页，编辑于2022年，星期五六.请说出下列描述的含义1.第44页，共71页，编辑于2022年，星期五续 2.第45页，共71页，编辑于2022年，星期五第四节 数据逻辑 DATALOG一 演算规则：1.比较谓词 2.关系谓词 导出关系谓词，基本关系谓词 3.域变量与哑元 4.规则：规则头 规则体5.查询：由一组规则组成。第46页，共71页，编辑于2022年，

12、星期五对规则的说明：规则头：只能是导出关系谓词。规则体：原子谓词 原子谓词的否定 用 (and)连接以上两类谓词。例如：T(x,y,z)S(x,y,z)AND x1 R(x,y)NOT Q(x,y)第47页，共71页，编辑于2022年，星期五规则的语义1.变量的作用域是一条规则。2.关系谓词的作用域是一个查询（全局的)3.每一个导出关系谓词都对应一个需要求解的关系，关系由所有满足规则体的元组构成。例10 T(x,y,z)S(x,y,z)AND x1T:S:ABD123231ABD231第48页，共71页，编辑于2022年，星期五又一例例10.T(x,y)S(x,y,-)R:T(x,y)R(x,

13、z,y)请问：T的值是多少？S:ABC123323131ABD123231第49页，共71页，编辑于2022年，星期五二.逻辑公式的转化 1.非内置否定的转化：NOT（A AND B）=NOT A AND NOT B2.OR 条件的转化：A OR B 转化为两条规则。如：T(x)S(x,y,z)and(x=1 or x=2)变为 T(x)S(x,y,z)and x=1 T(x)S(x,y,z)and x=2 第50页，共71页，编辑于2022年，星期五三 规则的安全性条件1.作用：排除无限关系。2.安全条件：在规则中所出现的变量必须在规则体中非否定的关系谓词中出现。如：Q(x,y)R(x)an

14、d y0 P(x,y)not S(x,y,z)and z=1Q(x,y)R(x)第51页，共71页，编辑于2022年，星期五四 规则的求解1.建立各关系的笛卡尔积2.一致性检查。3.若规则体为真，将元组加入导出关系中。例12 设R=,S=,求 规则 Q(x,y)R(x,z)and S(z,y)and x1 and not S(x,y).第52页，共71页，编辑于2022年，星期五求解过程 R S 一致性 X1 NOT S(x,y)(1,2)(2,2)t f(1,2)(3,4)f(5,3)(2,2)f(5,3)(3,4)t t t(3,3)(2,2)f(3,3)(3,4)?第53页，共71页，编

15、辑于2022年，星期五五 描述关系代数并集：交集：差集：第54页，共71页，编辑于2022年，星期五续笛卡尔集：Q(x,y,s,t)R(x,y)and S(s,t)投影：Q(x,y)R(x,y,z)自然连接：设 R(A,B),S(B,C)Q(x,y,z)R(x,y)and S(y,z)其它的运算请同学自己考虑。第55页，共71页，编辑于2022年，星期五Datalog的应用1.求信息和会计学院的学生2.求选了数据库的学生学号SJK(x)XK(x,y,-)and KC(y,z,-)and z=“数据库“第56页，共71页，编辑于2022年，星期五 六 递归查询1.递归查询：在规则中，导出关系谓词

16、在规则头和规则体中同时出现。如：Q(x,y)R(x,y)and Q(y,z)2.关系代数的不动点 设：y=f(x)是关于x的代数式子，若有r使得r=f(r)成立，则称r为该关系式的不动点。第57页，共71页，编辑于2022年，星期五3.最小不动点在所有不动点中行数最小的关系称为最小不动点。例：求下列式子的不动点：f(r)=S r 设 s=,，r与s同模式。则：r0=,r1=s是不动点。第58页，共71页，编辑于2022年，星期五4.递归查询的解递归查询的解是其代数方程的最小不动点。求解方法：1).令r0=2).计算f(),3).若 成立，则算法结束 否则，继续迭代。第59页，共71页，编辑于2

17、022年，星期五5.求不动点举例 其中：Q=,可见：是还有,还有吗？第60页，共71页，编辑于2022年，星期五6.算法举例 设S:A B 1 3 求：Q(x,y)S(x,y)2 4 Q(x,y)Q(x,z)and S(z,y)3 2 f(Q)=(计算最小不动点第61页，共71页，编辑于2022年，星期五计算最小不动点q0:C B q1:C B q2:C B q3=q2 1 3 1 3 1 3 2 4 2 4 2 4 3 2 3 2 3 2 1 2 1 2 3 4 3 4 1 4 第62页，共71页，编辑于2022年，星期五一个问题若第二条规则改为：Q(x,y)Q(x,z)and S(t,y）

18、and zt结果呢？q0:C B q1:C B q2:C B q3=q2?1 3 1 3 1 3 2 1 2 1 2 1 3 2 3 2 3 2 令s:A B *1 3 *1 3 1 3 1 1 3 3 2 1 3 3 1 1 3 2？第63页，共71页，编辑于2022年，星期五这是一个对选手排序的问题 请用DATALOG求出比 指定选手积分高的选手 编号。(2号选手)编号积分1302233 434 15第64页，共71页，编辑于2022年，星期五方法一 设：JF(BH,JF)gf(x)jf(s,t)and s=“2”and jf(x,y)and yt 方法二 第65页，共71页，编辑于202

19、2年，星期五方法三R(x,y,s,t)jf(x,y)and jf(s,t)and xsS(x,y)R(x,s,y,t)and stT(y)S(x,y)and x=“2”问：关系s第一列与 第三列有什么特 点？编号积分编号积分130223130343130415223343223415343415第66页，共71页，编辑于2022年，星期五这是一个可达问题，求 1.可达结点2.可达所有结点的结点1276453第67页，共71页，编辑于2022年，星期五 3.求三号节点的所有可达节点第68页，共71页，编辑于2022年，星期五续（一）jbkd(起点，到点）分析：1 2 递归求解：2 6 定义递归关

20、系谓词 kd(x,y)4 1 初始值 5 1 递归规则 6 5 KD(x,y)jbkd(x,y)6 7 kd(x,y)kd(x,z)and jbkd(z,y)7 6 7 3 第69页，共71页，编辑于2022年，星期五2的解 J(x)JBKD(x,-)J(x)JBKD(-,x)T(x,y)J(x)and J(y)and xy S(x)T(x,y)and not KD(x,y)R(x)JBKD(x,-)and not S(x)第70页，共71页，编辑于2022年，星期五3的解R(x,y)JBKD(x,y)R(x,y)R(x,z)and JBKD(z,y)D(x)R(y,x)and y=“3”第71页，共71页，编辑于2022年，星期五