数据库系统原理-第五章代数和逻辑查询语言

1、第第5章章 代数和逻辑查询语言代数和逻辑查询语言 5.1 关系代数操作5.2 包上的关系操作5.3 关系代数的扩展操作符5.4 关系逻辑5.5 关系代数与DatalogPage 15.1 关系代数操作关系代数操作(1) 关系代数的传统定义关系代数的传统定义 一个元组集合一个元组集合(即关系即关系)，能用来进行典型的基于关系的，能用来进行典型的基于关系的查询查询 集合上的五个操作：并、差、笛卡尔积、选择、投集合上的五个操作：并、差、笛卡尔积、选择、投影影 在基本操作上定义的附加操作：各种连接在基本操作上定义的附加操作：各种连接 关系代数的操作规则对于集合和包是不一样的关系代数的操作规则对于集合和

2、包是不一样的 简单的说，包是以空间代价换取时间效率简单的说，包是以空间代价换取时间效率所以对一般小例子来说，包的综合效率更高所以对一般小例子来说，包的综合效率更高但对实际应用中的数据库来说，用集合更加合理但对实际应用中的数据库来说，用集合更加合理Page 25.1 关系代数操作关系代数操作(2) 关系中的集合操作关系中的集合操作 基本集合操作：并、交、差基本集合操作：并、交、差 应用到关系操作时，需要附加约束应用到关系操作时，需要附加约束 属性列表和属性类型必须一致属性列表和属性类型必须一致 属性的排列顺序也要一致属性的排列顺序也要一致 原则上属性名也要对应一致，如果不一致，需要原则上属性名也

3、要对应一致，如果不一致，需要利用重命名操作处理利用重命名操作处理Page 35.1 关系代数操作关系代数操作(3) 投影投影A1,A2,An(R) 只保留指定部分列只保留指定部分列 由于属性减少，元组可能会重值，进而合并，因由于属性减少，元组可能会重值，进而合并，因此数目可能减少此数目可能减少 选择选择C(R) 该操作产生的新关系的元组必须满足条件该操作产生的新关系的元组必须满足条件C 结果关系和原关系的模式相同结果关系和原关系的模式相同Page 45.1 关系代数操作关系代数操作(4) 笛卡尔积笛卡尔积 RS 一个有序对的集合，有序对的第一个元素来自一个有序对的集合，有序对的第一个元素来自R

4、，第二个，第二个元素来自元素来自S 一般地，笛卡尔积对应一个关系，其元组维度更大，一般地，笛卡尔积对应一个关系，其元组维度更大，个数更多个数更多 如果如果R和和S有重名属性，则在结果中加前缀区分有重名属性，则在结果中加前缀区分 连接操作连接操作 参与连接操作的一般是两个关系，且连接时相应的元组参与连接操作的一般是两个关系，且连接时相应的元组在某些方面具有一致性，连接分为三类在某些方面具有一致性，连接分为三类 全连接即笛卡尔积全连接即笛卡尔积 自然连接自然连接 连接连接Page 55.2 包上的关系操作包上的关系操作(1) 一组元素的一种聚集形式，允许重复元素出现，一组元素的一种聚集形式，允许重

5、复元素出现，而集合而集合setset中不允许元素重复出现。中不允许元素重复出现。 对一个包去掉其中重复元素，就可得到一个集合对一个包去掉其中重复元素，就可得到一个集合。 一个集合可认为是一个特殊的包，其中没有重复一个集合可认为是一个特殊的包，其中没有重复元组。元组。什么是包什么是包bagbagPage 6 关系看作为集合，则不允许有重复元组，如果看作为包，则允许有重复元组。AB12341212AB1234包包集合集合5.2 包上的关系操作包上的关系操作(1)Page 7为何需要包为何需要包 关系中的元组应该不重复，但经运算得到的新关关系中的元组应该不重复，但经运算得到的新关系中的元组可以重复；

6、数据库系统支持系中的元组可以重复；数据库系统支持 提高投影计算效率提高投影计算效率 对聚合运算有用对聚合运算有用( (汇总值、平均值、计数等汇总值、平均值、计数等) )Page 8例子 商业DBMS实现的都是包，为什么呢？包的实现效率较高。 包的并操作和投影操作实现简单例如：对下面关系在A、B属性上的投影A BC125346127128AB12341212AB1234包包集合集合Page 9例子 例如：对下面关系R，要求A属性的平均值，则先对A属性投影，如果允许结果为包，则均值为1.5，否则为2(错)。A BC125346127128A1311A13包包集合集合Page 105.2 包上的关系

7、操作包上的关系操作(2) 包上的运算：并包上的运算：并( (交、差交、差) )、投影、选择、乘积和、投影、选择、乘积和连接等都允许运算之前和之后元组重复连接等都允许运算之前和之后元组重复 对两个关系求并，集合方式要先合并再去重，而包方对两个关系求并，集合方式要先合并再去重，而包方式只合并不去重，所以效率更高式只合并不去重，所以效率更高 投影操作后不去重投影操作后不去重 对后面要出现的聚集操作来说，只能用包方式，用集对后面要出现的聚集操作来说，只能用包方式，用集合方式的话会出现逻辑错误。合方式的话会出现逻辑错误。Page 11 包的并、交、差包的并、交、差 设设R和和S是包，若元组是包，若元组t

8、在在R和和S中分别出现中分别出现n次和次和m次次（这里的（这里的m和和n可以是可以是0），则：），则： R S的包并操作结果中：元组的包并操作结果中：元组t出现出现m+n次；次； R S的包交操作结果中：元组的包交操作结果中：元组t出现出现 min (m, n)次；次； R-S的包差操作结果中：元组的包差操作结果中：元组t出现出现 max(0, n-m)次；次； /减后为负数则取减后为负数则取0Page 12 包的并、交、差举例：设关系包的并、交、差举例：设关系R、S如下：如下：AB13112422AB13352446nRS：AB1311133524222446nRS：AB1324nR- -S

9、：AB1122R =S =Page 135.2 包上的关系操作包上的关系操作(2) 集合上的包操作（文本框内容释义）集合上的包操作（文本框内容释义） 如果对两个集合如果对两个集合R、S进行基于包的交和差操作，其结进行基于包的交和差操作，其结果与集合方式运算一样果与集合方式运算一样 因为作为被处理对象的两个关系本身没有重复的元因为作为被处理对象的两个关系本身没有重复的元组，所以交或差之后结果中仍然没有重值元组组，所以交或差之后结果中仍然没有重值元组 但对两个集合但对两个集合R和和S，进行基于包的并操作，其操作结，进行基于包的并操作，其操作结果可能不再是集合果可能不再是集合 结论：必须看清（答题）

10、结论：必须看清（答题）/声明（出题）是包方式还是声明（出题）是包方式还是集合方式集合方式Page 14如果在投影操作过程中，产生了多个同样的元组，那些重复的元组将不会被从包投影结果中除去。如对enroll表的cid投影包包关系关系5.2 包上的关系操作包上的关系操作(3)Page 15举例RAB 125612 A (R) =A151Page 16如果在进行选择操作时，要独立地对每个元组应用选择条件。在结果中不去除重复元组RC6(R)ABC125346127127ABC3461271275.2 包上的关系操作包上的关系操作(4)Page 17举例RAB 125612 A+B 5 (R) = AB

11、1212Page 18一个关系中的每个元组与另一个关系中的每个元组配对，而不问这个元组是否重复出现RRSAB1212A R.B S.B C122312451245122312451245BC234545S5.2 包上的关系操作包上的关系操作(5)Page 19举例RAB SBC 1234567812R S =AR.BS.BC123412785634567812341278Page 20包的连接操作也跟预想的一样，首先对比两个关系中的元组，看是否能组成一对，如果能，则配对起来的元组就是结果关系中的一员。RR SAB1212BC234545SABC1231235.2 包上的关系操作包上的关系操作(

12、6)Page 21连接如下：RR R.BS.B SAB1212A R.B S.B C1245124512451245BC234545S5.2 包上的关系操作包上的关系操作(6)Page 22举例RAB SBC 1234567812R R.B=2(cname,avg(grade)avggrade,count(sno)snum(course sc)Page 32是的特殊情况如果R(A1，A2，An)是关系，则A1，A2，An(R)与(R)等价。Page 33举例参演关系如下：starsin(title, year, starname) 找出至少出演了三部电影的影星，以及他们在电影中出现的最早年份s

13、tarname,minyear(cttitle=3(starname,MIN(year)minyear,count(title)cttitle(starsin)Page 34 扩展的投影操作符扩展的投影操作符 L(R)L(R)，其中L是R的一些属性序列。L的组成可以做如下扩展：1.R的属性；2.形如：xy，x是R的属性，y为结果模式中的新属性名；3.Ez，E是表达式，z是表达式E计算结果的属性的新名字。如：a+bx，表示a和b属性的和并生命名为xPage 35举例令R关系如下：ABC125346127127那么那么A,B+CX(R)为为：AX173101919Page 36举例令R关系如下：A

14、BC125346127127那么那么B-AX,C-BY(R)为为：XY13121515Page 37举例令R关系如下：ABC125346127127那么那么A,B+CX(R)为为：AX173101919Page 38举例令R关系如下：ABC125346127127那么那么B-AX,C-BY(R)为为：XY13121515Page 39排序操作符有时人们希望对关系中的元组按照一个或多个属性值排序。L(R)，L是R中某些属性的列表，对R中的元组按照L列出的属性排序，作为结果返回。如果L是A1,A2,An，那么R的元组就先按属性A1的值排序，对于A1属性相等的元组就按A2的值排序，依此类推。Page

15、 40举例令R关系如下：ABC125346227127那么那么B,C,A(R)为为：ABC125127227346Page 41外连接外连接 连接操作的缺陷连接操作的缺陷 连接操作的一个性质是可能产生连接操作的一个性质是可能产生悬挂元组。悬挂元组。而而这些元组不能跟另外关系的任何一个元组匹配，这些元组不能跟另外关系的任何一个元组匹配，所以这种连接操作并不能完全反映原始关系的全所以这种连接操作并不能完全反映原始关系的全部信息。部信息。 什么是外连接什么是外连接 先计算两个关系先计算两个关系R和和S的自然连接，然后再把来的自然连接，然后再把来自自R或或S的悬浮元组加入其中，用的悬浮元组加入其中，用

16、null符号符号 补齐结补齐结果元组中那些不具有值的属性。我们称之为果元组中那些不具有值的属性。我们称之为外连外连接，接，用符号用符号 表示。表示。Page 42设有关系设有关系ABC123456789BCD231023116712UVABCD12310123114567896712U VPage 43外连接的不同变体外连接的不同变体 只是将左变量只是将左变量R R的悬浮元组补齐的悬浮元组补齐 加入到结果中，加入到结果中，称之左外连接，用符号称之左外连接，用符号R R L LS S表示。表示。 只是将右变量只是将右变量S S的悬浮元组补齐的悬浮元组补齐 加入到结果中，加入到结果中，称之左外连接

17、，用符号称之左外连接，用符号R R R RS S表示。表示。 外连接的操作是，先进行外连接的操作是，先进行连接，然后将那些不连接，然后将那些不能匹配其他关系的元组，也用能匹配其他关系的元组，也用 补齐，用补齐，用U U C CV V表表示一个带条件示一个带条件C C的的外连接。同样，可用外连接。同样，可用L L或或R R来修来修饰这个算符，使其表示饰这个算符，使其表示的左外连接或右外连接。的左外连接或右外连接。Page 44如果只将左边关系中的悬浮元组加入到结果关系中，就是左外连接oL BCD2342356787810ABCD123412356781097810SR oL S456A B C1

18、23456678978R外连接的不同变体外连接的不同变体Page 45如果只将右边关系中的悬浮元组加入到结果关系中，就是右外连接oR A B C123456678978ABCD123412356781097810RR oR S678BCD2342356787810S外连接的不同变体外连接的不同变体Page 46类似于自然连接，连接也有对应的外连接。A B C123678978BCD231235789AR.B R.C S.B S.CD123235123789678789RSR AD S外连接的不同变体外连接的不同变体Page 47举例A B C123678978BCD231235789AR.B

19、R.C S.B S.CD123235123789678789RSR OAD S978231Page 48举例A B C123678978BCD231235789AR.B R.C S.B S.CD123235123789678789RSR LAD S978Page 49举例A B C123678978BCD231235789AR.B R.C S.B S.CD123235123789678789RSR RAD S231Page 50练习练习 P130 习题习题5.2.1 a, c, e, f, g, k, n已知关系已知关系R(A,B):(0, 1),(2, 3),(0, 1),(2, 4),(3

20、, 4)S(B,C):(0, 1),(2, 4),(2, 5),(3, 4),(0, 2),(3, 4)计算下面的表达式：计算下面的表达式：a)Page 5122,( )A B ABR练习练习 P130 习题习题5.2.1 a, c, e, f, g, k, n已知关系已知关系R(A,B):(0, 1),(2, 3),(0, 1),(2, 4),(3, 4)S(B,C):(0, 1),(2, 4),(2, 5),(3, 4),(0, 2),(3, 4)计算下面的表达式：计算下面的表达式：c)Page 52,( )B AR练习练习 P130 习题习题5.2.1 a, c, e, g, k, n已

21、知关系已知关系R(A,B):(0, 1),(2, 3),(0, 1),(2, 4),(3, 4)S(B,C):(0, 1),(2, 4),(2, 5),(3, 4),(0, 2),(3, 4)计算下面的表达式：计算下面的表达式：e)Page 53( )R练习练习 P130 习题习题5.2.1 a, c, e, g, k, n已知关系已知关系R(A,B):(0, 1),(2, 3),(0, 1),(2, 4),(3, 4)S(B,C):(0, 1),(2, 4),(2, 5),(3, 4),(0, 2),(3, 4)计算下面的表达式：计算下面的表达式：g)Page 54,()( )A SUM B

22、R练习练习 P130 习题习题5.2.1 a, c, e, g, k, n已知关系已知关系R(A,B):(0, 1),(2, 3),(0, 1),(2, 4),(3, 4)S(B,C):(0, 1),(2, 4),(2, 5),(3, 4),(0, 2),(3, 4)计算下面的表达式：计算下面的表达式：k)Page 55oLRS 练习练习 P130 习题习题5.2.1 a, c, e, g, k, n已知关系已知关系R(A,B):(0, 1),(2, 3),(0, 1),(2, 4),(3, 4)S(B,C):(0, 1),(2, 4),(2, 5),(3, 4),(0, 2),(3, 4)计

23、算下面的表达式：计算下面的表达式：n)Page 56.oR B S BRS 随着数据技术的不断提高，关系代数也暴露出了一些局限随着数据技术的不断提高，关系代数也暴露出了一些局限性，例如，无法有效地表示递归运算、逻辑表达能力弱等性，例如，无法有效地表示递归运算、逻辑表达能力弱等。 在这种情况下，在这种情况下，Datalog语言应运而生。语言应运而生。Datalog语言是一种语言是一种基于逻辑编程语言基于逻辑编程语言Prolog的一种非过程化的语言。同关系的一种非过程化的语言。同关系演算类似，用户只需要给出所描述的信息，不需要给出获演算类似，用户只需要给出所描述的信息，不需要给出获取信息的具体过程

24、。取信息的具体过程。 本节介绍本节介绍Datalog语言的基本结构、规则以及从关系代数到语言的基本结构、规则以及从关系代数到Datalog语言的转换等内容。语言的转换等内容。 5.4 关系逻辑关系逻辑(1)Page 57基本概念基本概念 逻辑也是一种表示关系查询的方法，例如逻辑也是一种表示关系查询的方法，例如Datalog语语言就可以表示相同类型的查询。言就可以表示相同类型的查询。 Datalog语言不是使用过程语言来表示查询，而是使语言不是使用过程语言来表示查询，而是使用一种规则来表示出这种想法，即可以通过已知的关用一种规则来表示出这种想法，即可以通过已知的关系中的某些元组的组合来推测元组是

25、否在关系中。系中的某些元组的组合来推测元组是否在关系中。Page 58基本结构基本结构 Datalog语言包括两种基本的原子，即关系原子和算术原子语言包括两种基本的原子，即关系原子和算术原子,由原子按照一定的规则组成由原子按照一定的规则组成Datalog查询语句。查询语句。 在在Datalog语言中，关系通过语言中，关系通过 “谓词谓词”来表示，每一个谓词来表示，每一个谓词都有固定数量的参数。都有固定数量的参数。 关系原子是由符号谓词和其后的参数组成，常简称原子。关系原子是由符号谓词和其后的参数组成，常简称原子。 例如，如果谓词是例如，如果谓词是R，其参数分别是，其参数分别是t1，t2，tn，

26、那么那么R(t1，t2，tn)就是一个关系原子。就是一个关系原子。 算术原子是两个算术表达式的比较，算术原子的值是布尔算术原子是两个算术表达式的比较，算术原子的值是布尔值。值。 Page 59例子例子 Page 60一般规则一般规则 规则是规则是Datalog语言中描述原子之间关联的规范，包括下列语言中描述原子之间关联的规范，包括下列三个组成部分：三个组成部分：1. 一个称为头部的关系原子，其后是一个称为头部的关系原子，其后是2. 左向箭头符号左向箭头符号，读作，读作if，其后是，其后是3. 主体部分，由一个或多个称为子目标的原子组成。主体部分，由一个或多个称为子目标的原子组成。 子目标既可以

27、是关系原子，也可以是算术原子。各个子子目标既可以是关系原子，也可以是算术原子。各个子目标之间用逻辑运算符目标之间用逻辑运算符AND连接，且各个子目标前面可连接，且各个子目标前面可以有选择地增加取反逻辑运算符以有选择地增加取反逻辑运算符NOT。 规则的目标是使规则的头部关系原子为真。规则的目标是使规则的头部关系原子为真。例如：例如：LongMovie(t,y)Movies(t,y,l,g,s,p) AND l100等价于等价于LongMovie:=title,year(length) 100(Movies)Page 61例子例子 Page 62例子例子 Page 63例子例子 Page 64例子

28、例子 Page 65Page 66安全规则安全规则 安全规则：安全规则： 由于关系实例总是有限，所以还需要由规则保证得到的由于关系实例总是有限，所以还需要由规则保证得到的头部关系也都是有限的。头部关系也都是有限的。 每个在规则中任意位置出现的变量都必须出现在主体的每个在规则中任意位置出现的变量都必须出现在主体的某些非否定的关系子目标中。某些非否定的关系子目标中。 尤其是，任何在规则头部、否定关系子目标或任意算术尤其是，任何在规则头部、否定关系子目标或任意算术子目标中出现的变量，也必须出现在主体的非否定的关子目标中出现的变量，也必须出现在主体的非否定的关系子目标中。系子目标中。Page 67 例

29、例5.19 安全规则安全规则 LongMovie(t,y)Movies(t,y,l,g,s,p) AND l100 例例5.20 非安全规则，不允许出现在非安全规则，不允许出现在Datalog中中 P(x,y)Q(x,z) AND NOT R(w,x,z) AND xyPage 68扩展谓词和内涵谓词扩展谓词和内涵谓词 若谓词所指的关系存储在数据库中，称该谓词为扩展谓词若谓词所指的关系存储在数据库中，称该谓词为扩展谓词。 当谓词所指的关系是通过一个或多个当谓词所指的关系是通过一个或多个Datalog规则计算得到规则计算得到的，称该谓词是内涵谓词。的，称该谓词是内涵谓词。 扩展谓词和内涵谓词分别

30、对应关系代数表达式中的操作数扩展谓词和内涵谓词分别对应关系代数表达式中的操作数和使用关系代数表达式计算得到的关系。和使用关系代数表达式计算得到的关系。 在在Datalog规则中，可以使用规则中，可以使用EDB(External Database，扩，扩展数据库展数据库)表示扩展谓词或相应的关系，使用表示扩展谓词或相应的关系，使用IDB(Internal Database，内涵数据库，内涵数据库)表示内涵谓词或相应的关系表示内涵谓词或相应的关系 。 例如，例如，Movies是一个是一个EDB关系，而关系，而LongMovie是一个是一个IDB关系。关系。Page 69练习练习 P136 习题习题

31、5.3.1 b, c, db)Page 70ker100(Pr()mahdoductLaptop 练习练习 P136 习题习题5.3.1 b, c, dc)Page 71 mod,kermod,kermod,ker1:(Pr)2:(Pr)3:(PrPrint)4:123el pricemaBel pricemaBel pricemaBRoductPCRoductLaptopRoducterRRRR 练习练习 P136 习题习题5.3.1 b, c, dd)Page 72mod(Print)elcolor true And type laserer5.5 关系代数与关系代数与Datalog 一般

32、地，可以使用一个或多个一般地，可以使用一个或多个Datalog规则来模拟关系代数规则来模拟关系代数的运算形式，并且可以模拟非常复杂的运算形式。的运算形式，并且可以模拟非常复杂的运算形式。 本节主要研究如何从关系代数的基本运算形式以及连接运本节主要研究如何从关系代数的基本运算形式以及连接运算形式转换到算形式转换到Datalog规则。规则。Page 73从集合运算到从集合运算到Datalog规则规则 交集运算可以使用一个交集运算可以使用一个Datalog规则来表示。由于交集运算规则来表示。由于交集运算涉及了两个关系，那么在涉及了两个关系，那么在Datalog规则中，具有与两个关系规则中，具有与两个

33、关系对应的子目标。在规则中，相应的参数使用相同的变量。对应的子目标。在规则中，相应的参数使用相同的变量。 假设假设R和和S的关系模式是的关系模式是R(A,B,C)和和S(A,B,C)，则则RS可以使用规则可以使用规则: I(a, b, c) R(a, b, c) AND S(a, b, c)Page 74 并集运算使用两个规则来表示，每个规则对应着一个并集并集运算使用两个规则来表示，每个规则对应着一个并集运算中的关系，且两个规则的头部都有相同的运算中的关系，且两个规则的头部都有相同的IDB谓词。谓词。头部的参数与各个子目标中的参数完全相同。头部的参数与各个子目标中的参数完全相同。 假设假设R和

34、和S的关系模式是的关系模式是R(A,B,C)和和S(A,B,C)，则则R S可以使用规则可以使用规则: U(x, y, z) R(x, y, z) U(x, y, z) S(x, y, z) 或或U(a, b, c) S(a, b, c) 注意：变量名对于规则是局部的，即每条规则是独立计算的注意：变量名对于规则是局部的，即每条规则是独立计算的，并且向其头部关系提供元组，与其他规则无关，因此变，并且向其头部关系提供元组，与其他规则无关，因此变量名是独立于规则的。量名是独立于规则的。Page 75 差集运算可以使用具有求反子目标的一个规则来计算。即差集运算可以使用具有求反子目标的一个规则来计算。即

35、如果计算两个关系如果计算两个关系U和和V的差集，非求反子目标是谓词的差集，非求反子目标是谓词U，求反子目标是谓词求反子目标是谓词V。 在该规则中，子目标和头部对于相应的参数都有相同的变在该规则中，子目标和头部对于相应的参数都有相同的变量。量。 假设假设R和和S的关系模式是的关系模式是R(A,B,C)和和S(A,B,C)，则则R-S可以使用规则可以使用规则: D(a, b, c) R(x, y, z) AND NOT S(x, y, z)Page 76从投影运算到从投影运算到Datalog规则规则 将关系代数中的投影运算转换成将关系代数中的投影运算转换成Datalog规则，可以使用规则，可以使用

36、一个具有单一子目标的规则。该子目标的参数是不同的变一个具有单一子目标的规则。该子目标的参数是不同的变量，每个变量代表关系的一个属性。量，每个变量代表关系的一个属性。 头部是带有参数的原子，其参数按照期望顺序对应于投影头部是带有参数的原子，其参数按照期望顺序对应于投影列表的属性。列表的属性。 例例5.25 将关系将关系Movies (title, year, length, genre, studioName, producerC#)投影到前三个属性：投影到前三个属性： P(t,y,l) Movies(t,y,l,g,s,p)Page 77从选择运算到从选择运算到Datalog规则规则 如果选择

37、条件是一个或多个算术比较表达式的如果选择条件是一个或多个算术比较表达式的AND运算，运算，可以建立一个具有下列子目标的可以建立一个具有下列子目标的Datalog规则：规则： 一个关系子目标对应于将其进行选择的关系。该关系子一个关系子目标对应于将其进行选择的关系。该关系子目标的每个分量都有不同的变量，且每个分量都对应关目标的每个分量都有不同的变量，且每个分量都对应关系的一个属性；系的一个属性； 多个算术子目标，每个算术子目标对应选择条件的一个多个算术子目标，每个算术子目标对应选择条件的一个比较运算。虽然在选择条件中使用属性名，但是在算术比较运算。虽然在选择条件中使用属性名，但是在算术子目标中却使

38、用相应的变量，并且与关系子目标中建立子目标中却使用相应的变量，并且与关系子目标中建立的变量保持一致。的变量保持一致。 复杂条件可以将逻辑表达式转化成复杂条件可以将逻辑表达式转化成“析取范式析取范式”，即正负，即正负文字的合取的析取。文字的合取的析取。Page 78例5.26 length100 and studioName=Fox (Movies) S(t,y,l,g,s,p) Movies(t,y,l,g,s,p) AND l 100 and s=Fox例例5.27 length100 or studioName=Fox (Movies) S(t,y,l,g,s,p) Movies(t,y,

39、l,g,s,p) AND l 100 S(t,y,l,g,s,p) Movies(t,y,l,g,s,p) AND s=Fox例例5.28 NOT(length100 or studioName=Fox） (Movies) 根据狄摩根定律，等价于根据狄摩根定律，等价于 (NOT(length100) AND (NOT (studioName=Fox)） (Movies) 即即length100 AND studioNameFox (Movies) 再转化为再转化为Datalog规则：规则：S(t,y,l,g,s,p) Movies(t,y,l,g,s,p) AND l100 and s Fox

40、Page 79从笛卡尔乘积到从笛卡尔乘积到Datalog规则规则 RS可以使用单一的可以使用单一的Datalog规则来表示，规则包含两个规则来表示，规则包含两个子目标，一个对应子目标，一个对应R一个对应一个对应S，两个子目标有不同的变，两个子目标有不同的变量分别对应量分别对应R和和S的属性。的属性。 头部头部IDB谓词拥有所有在这两个子目标中出现的参数，谓词拥有所有在这两个子目标中出现的参数，R子目标中的变量列在子目标中的变量列在S子目标中变量的前面。子目标中变量的前面。 p(a,b,c,x,y,z) R(a,b,c) AND S(x,y,z)Page 80从连接运算到从连接运算到Datalo

41、g规则规则 自然连接自然连接R S使用一条近似于笛卡尔积的使用一条近似于笛卡尔积的Datalog规则来表规则来表示，区别在于示，区别在于R和和S的同名属性使用相同的变量，否则使用的同名属性使用相同的变量，否则使用不同的变量。不同的变量。 规则头部是一个规则头部是一个IDB谓词，它的每个变量出现一次。谓词，它的每个变量出现一次。 假设假设R和和S的关系模式是的关系模式是R(A,B)和和S(B,C,D)，则自然连接，则自然连接R S 可以用规则可以用规则 J(a,b,c,d) R(a,b) AND S(b,c,d)Page 81 连接连接 先对笛卡尔积进行转化，再对选择条件进行转化。先对笛卡尔积进

42、行转化，再对选择条件进行转化。例例5.32 考虑关系考虑关系U(A,B,C)和和V(B,C,D)，其，其连接连接 对应的对应的Datalog规则：规则： J(a,ub,uc,vb,vc,d) U(a,ub,uc) AND V(vb,vc,d) AND ad AND ubvb例例5.33 J(a,ub,uc,vb,vc,d) U(a,ub,uc) AND V(vb,vc,d) AND ad J(a,ub,uc,vb,vc,d) U(a,ub,uc) AND V(vb,vc,d) AND ubvbU AD AND U.BV .BVU AD OR U.BV .BVPage 82从多重运算到从多重运算到Datalog规则规则 关系代数中的单一运算形式可以使用关系代数中的单一运算形式可以使用Datalog规则表示，而规则表示，而且多重运算也可以使用且多重运算也可以使用Datalog规则模拟。规则模拟。 模拟多重运算的步骤如下：模拟多重运算的步骤如下： 绘制关系代数的表达树。其中，表达树就是使用树状结绘制关系代数的表达树。其中，表达树就是使用树状结构表示关系代数表达式的计算程序。构表示关系代数表达式的计算程序。 为表达树的每一