数据库系统原理与应用教程(第三版)ppt教学课件ch08.ppt

1、第1页,第8章 Datalog语言,本章概述 本章的学习目标 主要内容,第2页,本章概述,关系代数是关系型数据库的理论基础，是数据库产品应用和发展的坚实基础。随着数据技术的不断提高，关系代数也暴露出了一些局限性，例如，无法有效地表示递归运算、逻辑表达能力弱等。 在这种情况下，Datalog语言应运而生。Datalog语言是一种基于逻辑编程语言Prolog的一种非过程化的语言。同使用关系演算类似，用户只需要给出所描述的信息，不需要给出获取信息的具体过程。Datalog语言使用声明的方式定义，简化了简单查询的书写，使查询优化更容易进行。 本章将要全面介绍Datalog语言的基本结构、规则、递归编程

2、以及从关系代数到Datalog语言的转换等内容。,第3页,本章的学习目标,了解Datalog语言的基本概念； 掌握Datalog语言的基本结构； 掌握Datalog语言的基本规则； 掌握从关系代数到Datalog语言的转换过程； 认识和掌握Datalog语言的递归编程原理； 理解包的概念和其在关系代数和Datalog语言中的作用。,第4页,主要内容,8.1 基本概念 8.2 关系代数向Datalog规则的转换 8.3 递归原理 8.4 包的运算 8.5 本章小结,第5页,8.1 基本概念,逻辑也是一种表示关系查询的方法，例如Datalog语言就可以表示相同类型的查询。 Datalog语言不是使

3、用过程语言来表示查询，而是使用一种规则来表示出这种想法，即可以通过已知的关系中的某些元组的组合推测某个其他元组是否在某个其他关系中。,第6页,基本结构,Datalog语言包括了两种基本的原子，即关系原子和算术原子。Datalog语言是由这些原子按照一定的规则组成的。 在Datalog语言中，关系通过称为谓词的符号来表示，每一个谓词都有固定数量的参数。关系原子是由符号谓词和其后的参数组成，关系原子也经常简称原子。例如，如果谓词是R，其参数分别是t1，t2，tn，那么R(t1，t2，tn)就是一个关系原子。 算术原子是两个算术表达式的比较。算术原子的值也是布尔值。,第7页,一般规则,在前面讲述的关

4、系代数中，介绍了许多关系代数运算，例如集合、笛卡尔乘积和自然连接等。这些运算形式在Datalog语言中可以使用规则来描述。规则就是Datalog语言中描述各种原子元素关联的规范，包括下列三个组成部分： 1. 一个称为头部的关系原子，其后是 2. 左向箭头符号，读作if，其后是 3. 多个子目标组成的规则体。这些子目标既可以是关系原子，也可以是算术原子。各个子目标之间用逻辑运算符AND连接，且各个子目标前面可以有选择地增加取反逻辑运算符NOT。,第8页,安全规则,前面讲过，Datalog语言是一种由许多原子构成的规则，规则包含了许多变量。规则的目标是使规则的头部关系原子为真。由于关系实例总是有限

5、，所以还需要由规则保证得到的头部关系也都是有限的。如果得到的头部关系是无限的，那么这种规则是无意义的。 下面分析如何保证得到的查询结果是有意义的。在子目标中，包括了关系子目标、求反关系子目标、算术子目标和求反算术子目标。,第9页,外延谓词和内涵谓词,外延谓词和内涵谓词是两个经常提到的概念。当谓词所指的关系存储在数据库中时，称该谓词为外延谓词。当谓词所指的关系是通过一个或多个Datalog规则计算得到的，称该谓词是内涵谓词。外延谓词和内涵谓词之间的差别类似关系代数表达式的运算项和使用关系代数表达式计算的关系之间的差别。 在Datalog规则中，如果谓词分别是内涵的或外延的，可以引用与内涵的或外延

6、的谓词相对应的关系。有时，使用IDB(Internal Database，内涵数据库)来引用内涵谓词或相应的关系，使用EDB(External Database，外延数据库)来引用外延谓词或相应的关系。,第10页,主要内容,8.1 基本概念 8.2 关系代数向Datalog规则的转换 8.3 递归原理 8.4 包的运算 8.5 本章小结,第11页,8.2 关系代数向Datalog规则的转换,上一章介绍了关系代数的各种运算形式，本节将介绍各种Datalog规则形式。一般地，可以使用一个或多个Datalog规则来模拟关系代数的运算形式，并且可以模拟非常复杂的运算形式。 本节主要研究如何从关系代数的

7、基本运算形式以及连接运算形式转换到Datalog规则。,第12页,从集合运算到Datalog规则,集合运算是关系代数的最基本的运算形式，包括了交集、并集和差集三种运算形式。下面介绍如何使用Datalog规则模拟这三种集合运算形式。 交集运算可以使用一个Datalog规则来表示。由于交集运算涉及了两个关系，那么在Datalog规则中，具有与两个关系对应的子目标。在规则中，相应的参数使用相同的变量。 并集运算可以使用两个规则来表示。在Datalog规则中，每个规则都对应着一个并集运算中的关系，且两个规则的头部都有相同的IDB谓词。头部的参数与各个子目标中的参数完全相同。 差集运算可以使用具有求反子

8、目标的一个规则来计算。即如果计算两个关系U和V的差集，可以这样来计算，非求反子目标是谓词U，求反子目标是谓词V。在该规则中，子目标和头部对于相应的参数都有相同的变量。,第13页,从投影运算到Datalog规则,把关系代数中的投影运算形式转换成Datalog规则，可以使用一个具有单一子目标的规则。该子目标的参数是数量不同于关系的属性数量的变量，每个变量都对应着关系的一个属性。头部是带有参数的原子，这些参数是按照要求的顺序与投影的属性表对应的变量。头部原子的这些变量只是子目标投影过来的变量，因此两者的数量不同。,第14页,从笛卡尔乘积到Datalog规则,两个关系U和V的笛卡尔乘积UV可以使用单一

9、的Datalog规则来表示。在这个Datalog规则中，有两个子目标。一个子目标对应关系U，另一个子目标对应关系V。每个子目标都有不同的变量，每个变量对应着关系U或V中的一个属性。头部的关系原子把出现的两个子目标中的所有变量作为参数，且严格按照出现的先后顺序，即出现在关系U子目标中的变量排列在关系V子目标的变量之前。,第15页,从选择运算到Datalog规则,把关系运算中的选择转换成Datalog规则比较复杂。下面首先研究一种简单的情况，然后再研究如何把具有复杂条件的选择运算转变成Datalog规则。 如果选择条件是一个算术比较表达式或多个比较表达式的AND运算，可以建立一个具有下列子目标的D

10、atalog规则： 一个关系子目标对应于将其进行选择的关系。该关系子目标的每个分量都有不同的变量，且每个分量都对应关系的一个属性； 多个算术子目标，每个算术子目标都对应着选择条件的一个比较运算。虽然在选择条件中使用属性名，但是在算术子目标中却使用相应的变量，并且与关系子目标中建立的变量保持一致。,第16页,从连接运算到Datalog规则,连接包括了自然连接、连接和外部连接。这里主要介绍如何把自然连接和连接转变成Datalog规则。 连接运算非常类似于笛卡尔乘积的运算，因此可以使用像乘积的规则来表示两个关系的自然连接，区别是如果希望表示关系U和V的自然连接UV，并且这两个关系中有相同名称的属性，

11、那么必须使用相同的变量，否则必须使用不同的变量。规则头部是每一个变量都出现一次的IDB谓词。,第17页,从多重运算到Datalog规则,关系代数中的单一运算形式可以使用Datalog规则表示，而且多重运算也可以使用Datalog规则模拟。 模拟多重运算的步骤如下： 第一步，绘制关系代数的表达树。其中，表达树就是使用树状结构表示关系代数表达式的计算程序。 第二步，为表达树的每一个内部节点建立一个IDB谓词。,第18页,主要内容,8.1 基本概念 8.2 关系代数向Datalog规则的转换 8.3 递归原理 8.4 包的运算 8.5 本章小结,第19页,8.3 递归原理,递归是一种常见的算法，即如

12、果一个过程直接或间接地调用它自身，称该过程为递归过程。 本节将要研究为什么使用和如何使用Datalog语言描述递归过程。,第20页,关系代数存在的问题,在数据的查询过程中，经常会遇到递归现象。 例如，在出版社的人事管理中，经理和雇员的问题就是一个递归问题。一个人可以是某些雇员的经理，但是他又可能是另外一个经理的雇员，经理又可能是更高层经理的雇员等多种情况。,第21页,计算最小固定点,现在研究如何在关系代数中解决这种问题。 假设关系Leader(a，b)表示了这种直接和间接经理和雇员的联系。可以写出下面的方程，这是一个包含了关系Leader和Human的方程式，Leader的值是满足该方程式的最

13、小关系，最小关系也称为最小固定点。,第22页,使用Datalog规则表示固定点公式,通过上面的分析可以看到，使用关系代数表示固定点公式往往会非常复杂，使用Datalog规则表示则比较容易。下面研究如何使用Datalog规则表示固定点公式。 使用Datalog规则表示固定点公式的思路是：假定一个或多个EDB关系已知，其他IDB关系则通过出现在规则的头部来定义，规则体可能包含的谓词是EDB或IDB的关系以及代数原子子目标。,第23页,主要内容,8.1 基本概念 8.2 关系代数向Datalog规则的转换 8.3 递归原理 8.4 包的运算 8.5 本章小结,第24页,8.4 包的运算,前面已经讲过

14、，关系中的元组是集合，是一种自然的断言。但实际上，在许多数据库产品中，允许相同的元组在关系中重复出现。这时，关系中的元组不是集合，而是包。 因此，我们不但需要理解集合的各种运算，还需要了解包是如何运算的。,第25页,包的意义,集合中不允许元组重复出现，元组的顺序不重要。列表不但不允许元组重复出现，而且元组的出现顺序也是列表的重要特性。相对而言，包的要求比较宽松，既允许元组重复出现，又不重视元组的出现顺序。 图8-9就是一个包的示例。在该示例中，清华大学出版社元组出现了5次，高等教育出版社元组出现了4次，机械工业出版社元组出现了3次。,第26页,包的关系运算,关系的基本运算包括并集、交集、差集、

15、投影、笛卡尔乘积和选择等形式 下面研究如何对包进行这些运算。,第27页,包的并集运算,如果关系U是一个包，其中元组tupleA出现了n次，关系V也是一个包，其中元组tupleA出现了m次。那么，在包UV的结果中，元组tupleA出现的次数是n+m。 例如，如果关系U的一个实例如图8-12所示，其中高等教育出版社出现了3次，其他元组出现了一次。关系V的一个实例如图8-13所示，其中清华大学出版社元组出现了4次，其他元组均出现了一次。,第28页,包的交集运算,下面开始研究包的交集运算。如果关系U是一个包，其中元组tupleA出现了n次，关系V也是一个包，其中元组tupleA出现了m次。那么，在包U

16、V的结果中，元组tupleA出现的次数是min(n，m)。 例如，如果关系U和V的实例分别如图8-12和8-13所示，那么UV的结果如图8-15所示，即每个出版社都只出现了一次。,第29页,包的差集运算,包的差集运算也是一种集合运算。如果关系U是一个包，其中元组tupleA出现了n次，关系V也是一个包，其中元组tupleA出现了m次。那么，在包UV的结果中，元组tupleA出现的次数是max(0，nm)。,第30页,包的投影运算,图8-9所示的关系实例就是图8-10所示的关系实例投影的结果。 需要注意的是，如果在投影过程中因为消除一个或多个属性使得从几个元组中产生出相同的元组，那么这些重复的元

17、组不从包的投影结果中删除。,第31页,包的笛卡尔乘积运算,在包的笛卡尔乘积中，只需要将一个关系的每个元组和另外一个关系的每个元组匹配成对，不考虑这些元组是否重复。如果关系U是一个包，其中元组数量是n个，关系V也是一个包，其中元组数量是m个。那么，在包UV的结果中，元组的数量nm。 例如，已知关系U和V的实例，那么包UV的运算结果如图8-17所示。包的乘积中属性命名的方式与集合乘积运算中相同。,第32页,包的选择运算,包的选择运算与集合的选择运算非常类似。在包的选择运算中，把选择条件应用于每个元组，而不论这些元组是否重复。 例如，如果关系U如图8-12所示，那么包的选择name= 高等教育出版社 (U)的结果如图8-18所示。可见选择运算的结果依然是包。,第33页,包的逻