《数据库系统原理与应用-Datalog语言》由会员分享，可在线阅读，更多相关《数据库系统原理与应用-Datalog语言（28页珍藏版）》请在金锄头文库上搜索。
1、数据库系统原理与应用教程(第二版)第1章 概述第8章 Datalog语言本章概述 本章的学习目标主要内容1数据库系统原理与应用教程(第二版)第1章 概述本章概述l关系代数是关系型数据库的理论基础，是数据库产品应用 和发展的坚实基础。随着数据技术的不断提高，关系代数 也暴露出了一些局限性，例如，无法有效地表示递归运算 、逻辑表达能力弱等。在这种情况下，Datalog语言应运 而生。lDatalog语言是一种基于逻辑编程语言Prolog的一种非过 程化的语言。就像使用关系演算一样，用户只需要给出所 描述的信息，不需要给出获取信息的具体过程。Datalog 语言使用声明的方式定义，简化了简单查询的书
2、写，使查 询优化更容易进行。l本章将要全面介绍Datalog语言的基本结构、规则、递归 编程以及从关系代数到Datalog语言的转换等内容。2数据库系统原理与应用教程(第二版)第1章 概述本章的学习目标l了解Datalog语言的基本概念；l掌握Datalog语言的基本结构；l掌握Datalog语言的基本规则；l掌握从关系代数到Datalog语言的转换过程 ；l认识和掌握Datalog语言的递归编程原理；l理解包的概念和其在关系代数和Datalog语 言中的作用。3数据库系统原理与应用教程(第二版)第1章 概述主要内容8.1 基本概念 8.2 关系代数向Datalog规则的转换 8.3 递归原理
3、 8.4 包的运算 8.5 本章小结 4数据库系统原理与应用教程(第二版)第1章 概述8.1 基本概念l逻辑也是一种表示关系查询的方法，例如 Datalog语言就可以表示相同类型的查询。 Datalog语言不是使用过程语言来表示查询 ，而是使用一种规则来表示出这种想法， 即可以通过已知的关系中的某些元组的组 合推测某个其他元组是否在某个其他关系 中。 5数据库系统原理与应用教程(第二版)第1章 概述基本结构 lDatalog语言包括了两种基本的原子，即关 系原子和算术原子。Datalog语言是由这些 原子按照一定的规则组成的。l在Datalog语言中，关系通过称为谓词的符 号来表示，每一个谓词
4、都有固定数量的参 数。关系原子是由符号谓词和其后的参数 组成，关系原子也经常简称原子。 l算术原子是两个算术表达式的比较。算术 原子的值也是布尔值。 6数据库系统原理与应用教程(第二版)第1章 概述一般规则 l在前面讲述的关系代数中，介绍了许多关系代数 运算，例如集合、笛卡尔乘积、自然连接等。这 些运算形式在Datalog语言中可以使用规则来描 述。规则就是Datalog语言中描述各种原子元素 关联的规范，包括下列三个组成部分： 1. 一个称为头部的关系原子，其后是 2. 左向箭头符号，读作if，其后是 3. 多个子目标组成的规则体。这些子目标既可以是关 系原子，也可以是算术原子。各个子目标之
5、间用逻辑 运算符AND连接，且各个子目标前面可以有选择地增 加取反逻辑运算符NOT。7数据库系统原理与应用教程(第二版)第1章 概述安全规则 l前面讲过，Datalog语言是一种由许多原子构成 的规则，规则包含了许多变量。规则的目标是使 规则的头部关系原子为真。由于关系实例总是有 限，所以还需要由规则保证得到的头部关系也都 是有限的。如果得到的头部关系是无限的，那么 这种规则是无意义的。l我们来分析一下，如何保证得到的查询结果是有 意义的。在子目标中，包括了关系子目标、求反 关系子目标、算术子目标和求反算术子目标。8数据库系统原理与应用教程(第二版)第1章 概述外延谓词和内涵谓词 l外延谓词和
6、内涵谓词是两个经常提到的概念。当谓词所指 的关系存储在数据库中时，称该谓词为外延谓词。当谓词 所指的关系是通过一个或多个Datalog规则计算得到的， 那么称该谓词是内涵谓词。外延谓词和内涵谓词之间的差 别类似关系代数表达式的运算项和使用关系代数表达式计 算的关系之间的差别。l在Datalog规则中，如果谓词分别是内涵的或外延的，那 么可以引用与内涵的或外延的谓词相对应的关系。有时， 我们使用IDB(Internal Database，内涵数据库)来引用内 涵谓词或相应的关系，使用EDB(External Database，外 延数据库)来引用外延谓词或相应的关系。9数据库系统原理与应用教程(
7、第二版)第1章 概述主要内容8.1 基本概念 8.2 关系代数向Datalog规则的转换 8.3 递归原理 8.4 包的运算 8.5 本章小结 10数据库系统原理与应用教程(第二版)第1章 概述8.2 关系代数向Datalog规则的转换l上一章介绍了关系代数的各种运算形式， 本节将介绍各种Datalog规则形式。一般地 ，可以使用一个或多个Datalog规则来模拟 关系代数的运算形式，并且可以模拟非常 复杂的运算形式。l这里，主要研究如何从关系代数的基本运 算形式以及连接运算形式转换到Datalog规 则。11数据库系统原理与应用教程(第二版)第1章 概述从集合运算到Datalog规则 l集合
8、运算是关系代数的最基本的运算形式，包括了交集、并集和差集 三种运算形式。下面介绍如何使用Datalog规则模拟这三种集合运算 形式。l交集运算可以使用一个Datalog规则来表示。由于交集运算涉及了两 个关系，那么在Datalog规则中，具有与两个关系对应的子目标。在 规则中，相应的参数使用相同的变量。l并集运算可以使用两个规则来表示。在Datalog规则中，每一个规则 都对应着一个并集运算中的关系，且两个规则的头部都有相同的IDB 谓词。头部的参数与各个子目标中的参数完全相同。l差集运算可以使用具有求反子目标的一个规则来计算。也就是说，如 果计算两个关系U和V的差集，那么可以这样来计算，非求
9、反子目标 是谓词U，求反子目标是谓词V。在该规则中，子目标和头部对于相 应的参数都有相同的变量。12数据库系统原理与应用教程(第二版)第1章 概述从投影运算到Datalog规则 l把关系代数中的投影运算形式转换成 Datalog规则，可以使用一个具有单一子目 标的规则。该子目标的参数是数量不同于 关系的属性数量的变量，每一个变量都对 应着关系的一个属性。头部是带有参数的 原子，这些参数是按照要求的顺序与投影 的属性表对应的变量。头部原子的这些变 量只是子目标投影过来的变量，因此两者 的数量不同。13数据库系统原理与应用教程(第二版)第1章 概述从笛卡尔乘积到Datalog规则 l两个关系U和V
10、的笛卡尔乘积UV可以使用单一的 Datalog规则来表示。在这个Datalog规则中，有 两个子目标。一个子目标对应关系U，另一个子 目标对应关系V。每一个子目标都有不同的变量 ，每一个变量对应着关系U或V中的一个属性。头 部的关系原子把出现的两个子目标中的所有变量 作为参数，且严格按照出现的先后顺序，即出现 在关系U子目标中的变量排列在关系V子目标的变 量之前。14数据库系统原理与应用教程(第二版)第1章 概述从选择运算到Datalog规则 l把关系运算中的选择转换成Datalog规则是比较复杂的。 我们首先研究一种简单的情况，然后再研究如何把具有复 杂条件的选择运算转变成Datalog规则
11、。l如果选择条件是一个算术比较表达式或多个比较表达式的 AND运算，那么可以建立一个具有下列子目标的Datalog 规则： 一个关系子目标对应于将其进行选择的关系。该关系子目标的每 一个分量都有不同的变量，且每一个分量都对应关系的一个属性 ； 多个算术子目标，每一个算术子目标都对应着选择条件的一个比 较运算。虽然在选择条件中使用属性名，但是在算术子目标中却 使用相应的变量，并且与关系子目标中建立的变量保持一致。15数据库系统原理与应用教程(第二版)第1章 概述从连接运算到Datalog规则 l连接包括了自然连接、连接和外部连接。这里主要介绍 如何把自然连接和连接转变成Datalog规则。l连接
12、运算非常类似于笛卡尔乘积的运算，因此可以使用像 乘积的规则来表示两个关系的自然连接，差别是如果希望 表示关系U和V的自然连接UV，并且这两个关系中有相同 名称的属性，那么必须使用相同的变量，否则必须使用不 同的变量。规则头部是每一个变量都出现一次的IDB谓词 。l连接可以使用带选择的笛卡尔乘积来表示。如果选择条 件是合取式，即比较运算通过AND逻辑运算符连接起来， 那么可以使用乘积对应的Datalog规则和附加的算术子目 标，且每一个算术子目标对应着一个比较运算来表示。 16数据库系统原理与应用教程(第二版)第1章 概述从多重运算到Datalog规则 l关系代数中的单一运算形式可以使用 Dat
13、alog规则表示，而且多重运算也可以使 用Datalog规则模拟。模拟多重运算的步骤 如下：l第一步，绘制关系代数的表达树。其中， 表达树就是使用树状结构表示关系代数表 达式的计算程序。l第二步，为表达树的每一个内部节点建立 一个IDB谓词。17数据库系统原理与应用教程(第二版)第1章 概述主要内容8.1 基本概念 8.2 关系代数向Datalog规则的转换 8.3 递归原理 8.4 包的运算 8.5 本章小结 18数据库系统原理与应用教程(第二版)第1章 概述8.3 递归原理l递归是一种常见的算法，即如果一个过程 直接或间接地调用它自身，那么称该过程 为递归过程。l本节将要研究为什么和如何使
14、用Datalog语 言描述递归过程。19数据库系统原理与应用教程(第二版)第1章 概述关系代数存在的问题 l在数据的查询过程中，经常会遇到递归现 象。例如，在出版社的人事管理中，经理 和雇员的问题就是一个递归问题。一个人 可以是某些雇员的经理，但是他又可能是 另外一个经理的雇员，经理又可能是更高 层经理的雇员，等等。20数据库系统原理与应用教程(第二版)第1章 概述计算最小固定点 l我们现在研究如何在关系代数中解决这种 问题。l假设关系Leader(a，b)表示了这种直接和 间接经理和雇员的联系。我们可以写出这 样的方程，这是一个包含了关系Leader和 Human的方程式，Leader的值是
15、满足该方 程式的最小关系，最小关系也称为最小固 定点。 21数据库系统原理与应用教程(第二版)第1章 概述使用Datalog规则表示固定点公式 l通过上面的分析可以看到，使用关系代数表示固 定点公式往往会非常复杂，但是使用Datalog规 则表示则比较容易。下面我们研究如何使用 Datalog规则表示固定点公式。l使用Datalog规则表示固定点公式的思路是：假 定一个或多个EDB关系已知，其他IDB关系则通 过出现在规则的头部来定义，规则体可能包含的 谓词是EDB或IDB的关系以及代数原子子目标。22数据库系统原理与应用教程(第二版)第1章 概述主要内容8.1 基本概念 8.2 关系代数向D
16、atalog规则的转换 8.3 递归原理 8.4 包的运算 8.5 本章小结 23数据库系统原理与应用教程(第二版)第1章 概述8.4 包的运算l前面我们已经讲过，关系中的元组是集合 ，这是一种自然的断言。但是，实际上， 在许多数据库产品中，允许相同的元组在 关系中重复出现。这时，关系中的元组不 是集合，而是包。l因此，我们不但需要理解集合的各种运算 ，还需要了解包是如何运算的。24数据库系统原理与应用教程(第二版)第1章 概述包的意义 l我们反复强调了集合、列表 和包的概念。集合中不允许 元组重复出现，元组的顺序 不重要。列表不但不允许元 组重复出现，而且元组的出 现顺序也是列表的重要特性 。相对而言，包的要求比较 宽松，它既允许元组重复出 现，又不重视元组的出现顺 序。图8-9就是一个包的示 例。 25数据库系统原理与应用教程(第二版)第1章 概述包的关系运算 l关系的基本运算包括并集、交集、差集、 投影、笛卡尔乘积、选择等形式，
