谓词逻辑在关系数据库中的应用

摘要：本文旨在研究将谓词逻辑及公理化理论应用于关系数据库中表示数据子语言，应用谓词逻辑作为它的数学基础，使得对这些语言的研究成为对谓词逻辑的研究，优化数据子语言的表示成为对谓词逻辑的化简问题。

关键词：关系数据库；数据库；关系；谓词逻辑；

中图分类号：TP399 文献标识码：A文章编号：1009-3044(2007)17-31213-03

The Application of Predicate Logic on Relational Database

LU Yan-xin

(Institute of Logic, Shanghai Academy of Social Sciences,Shanghai 200025,China)

Abstract：This paper is intended to study the application of predicate logic and the theory of axiomatization on the relational database to denote data sublanguage。Application predicate logic on data sublanguage as its mathematical foundation would make the study of data sublanguage become the research of predicate logic and the optimization of data sublanguage become the matters of simplification of predicate logic.

Key words：relational database；database；relation；predicate logic

1 引言

任何一门学科在其研究和发展过程中都要借助一些工具和方法。计算机科学也不例外。19世纪末迅速发展起来的数理逻辑作为现代逻辑的分支，直接为计算机科学的产生和根本性发展提供了重要的思维方法和研究工具，正如美国科学促进会在题为“On the Unusual Effectiveness of Logic in Computer Science”的会议中的总结：

Logic has permeated through computer science during the past thirty years much more than it has through mathematics during the past one hundred years。Indeed，at present concepts and methods of logic occupy a central place in computer science，Insomuch that logic has been called “the calculus of computer science”。[1]

在研究将谓词逻辑及公理化理论应用于关系数据库之前，有必要先介绍相关知识。

2 关系数据库简介

随着信息管理水平的不断提高，信息资源已成为社会各行各业的重要资源和财富，用于信息管理的数据库技术也得到了很大的发展，是计算机科学的重要分支，由于数据库具有数据结构化、较低的冗余度、较高的程序与数据独立性、易于扩充和易于编制应用程序等优点，所以大中型信息系统都是建立在数据库设计之上的。数据库技术成为目前最活跃、应用最广泛的计算机领域之一，几乎所有的应用系统都涉及到数据库，以数据库方式存储系统数据。

数据库是计算机管理数据的一种机构，是计算机数据处理的核心，是现代信息科学与技术的重要组成部分。数据库一般由两部分组成，即数据库的硬件部分和数据库的软件部分。其硬件部分是供存放数据用的大量物理存储空间，如磁盘、磁带、光盘等外存空间；其软件部分是管理数据库中数据的一组程序，这组程序叫作数据库管理系统，简称DBMS。它的主要目的是提供一可以方便地、有效地存取数据库信息的环境。对数据库的一切操作都是通过DBMS进行的。

DBMS的主要功能为：

（1）数据库的定义功能

（2）数据库的操纵功能

（3）数据库的保护功能

（4）数据库的存储管理

（5）数据库的维护功能

（6）数据库的描述功能

鉴于下文的需要，这里我们介绍只数据库管理系统的第二个功能，数据库的操纵功能。该功能是面向用户的主要功能，用户可以使用数据库管理系统所提供的语言――数据操作语言（DML），使用数据库中的数据。供用户使用数据库的语言有的从终端装置输入，这种语言叫终端查询语言（SQL）；有的可附属于某些宿主语言，如可附属于FORTRAN、COBOL等语言作为这些语言的扩充成分。基本的数据操作有以下几个方面：

数据的查询：从数据库中取出满足一定条件要求的数据；

数据的修改：可以修改数据库中指定的数据；

数据的插入：将一些数据存储到数据库中供以后使用；

数据的删除：删除数据库内指定的数据。

数据库内的数据一般都按一定格式组织与存放，为了清晰理解数据库内数据的基本组织格式，我们要引入以下概念：

实体：将现实世界中客观存在的能够相互区分的事物经过加工、分类，抽象成为数据库中数据的基本存放单位，如职工的简历、工资单、一次考试、一个学生、物资供销情况等均是实体。在数据库内实体是一个整体，它内部的数据相互间是有逻辑联系的。

实体集：所有具有相同结构形式的实体集合。

联系：实体集之间的对应关系称为联系，它反映现实世界中事物之间的相互关联。在数据库中实体是基本的数据单位，但是各实体间是有一定联系的，如实体集学生通过选课和课程之间联系起来，这个联系是学生选修课程，教师也是实体，而教师与学生、课程也有联系。在数据库中存储数据时不仅要存放实体的数据，还要存放联系的数据，如上例上，不仅要存放有关学生、教师和课程的实体，而且还要存放学生选修哪门课程的情况及教师教授哪门课程的情况，只有这样数据库中的这个数据信息才是完整的。

关键字：如果某个属性或属性组合的值能够惟一地标识出实体集中的每一个实体，那么该属性或属性组合就可以叫做关键字。用做标识的关键字也称为码。如学校的学生管理系统中的学生的学号（学生的学号是惟一的，一个学生只能有一个学号，并且每个学生都不相同。）

属性：现实世界中事物的特征，即实体的性质，这些性质称为此实体的属性，如学生这个实体就可以用学号、姓名、性别、出生日期、系和年级等属性来描述。用这些属性的具体值可以描述一个具体的实体。

属性域：实体的每个属性的表现形式都是统一的，如学号是由n个数字所组成的号码，性别为{M，F}中之一（M代表男性，F代表女性），年龄由三个数字所组成，对每个属性都有一个表示范围，如年龄的表示范围是从0到150间的数字；性别的表示范围是集合{M，F}，这种属性的表示范围就是属性域，每个属性都有一个属性域。

数据库目前可以有三种结构数据模型，它们分别是层次模型、网络模型、关系模型。

层次模型是用树形结构表示实体间联系的数据模型，它是数据库系统中最早出现的数据模型。层次模型对一对多的层次关系描述比较直观、自然且容易理解，该模型本身比较简单。但现实世界的很多联系是非层次性的，这样一来，若仍用层次模型表示这类非层次性的联系，则显得很笨拙，并且会产生大量的数据冗余。网状模型对于处理这种联系，则非常有效。

网状模型是用有向图结构表示实体类型及实体间联系的数据模型。其优点是具有良好的性能，存取效率高，并且能够更为直接地描述现实世界。但是网状模型结构复杂，不容易实现，不利于扩充。

关系模型可以克服上述层次模型和网状模型的缺点。关系模型有以下优点：

结构简单直观、用户易理解；

有严格的设计理论；

存取路径对用户透明，从而具有更高的独立性、更好的安全保密性，同时简化了程序员的工作，减少了数据库开发建立的工作量。

正是因为它的诸多优点，使得关系模型是结构数据模型中最为重要的数据模型。关系数据模型是由IBM公司的E.F.Codd于1970年首次提出，20世纪80年代以来，数据库管理系统几乎都支持关系数据模型，非关系系统的产品也大都加上了关系接口。数据库领域当前的研究工作都是以关系方法为基础。以关系数据模型为基础的数据库管理系统，称为关系数据库系统（RDBMS）。关系数据库系统目前是各类数据库中最重要，也是最流行的数据库，技术也最为成熟。本文将重点讨论关系式数据库，其他的两种结构模型将不作介绍了。

关系数据模型是指实体和联系均用二维表来表示的数据模型。关系模型有以下性质：

二维表中的每一列属性都是不能再分的基本字段，也就是说不允许表中有表；

二维表中的各列被指定一个相异的名字；

二维表中的各行不允许重复；

二维表上的行列排列次序不重要。

在用户看来，一个关系模型的逻辑结构是一张二维表，它由行和列组成，如下:

表1 学生人事记录表

关系：对应通常说的二维表，如表1所示的这张学生人事记录表。

元组：二维表中的一行即为一个元组，相当于一个记录值。

下面我们举例说明关系，设有实体集S表示学生概貌，它有五个属性：学号、姓名、性别、年龄、系别，分别可用S#、NAME、SEX、AGE、DEP。这个实体集存放5个学生的概貌，表2用来表示以上关系。

表2 实体集S

设有实体集C表示课程的概况，它有三个属性，分别为：课程号、课程名、课程学分，分别用C#，CN，CC。这个实体集存放5门课的概况。

表3 实体集C

实体集与实体集间的联系也可用关系表示，如学生选修课程的情况可用学号与课程号、课程成绩构成一个新关系SC，它描述了学生修课情况及课程成绩CG，这个关系如下：

表4 联系SC的关系

数据实体集与联系都可以用以上的这种二维表表示，在数据库中，用这种二维表构造数据的模型就是关系数据库。关系数据库中的数据库管理系统向用户提供使用数据库的语言，即数据子语言，这种语言目前以关系代数表示，但为了优化数据子语言的表示方法，下面，我们将引入用谓词逻辑中的方法表示数据子语言，使得对数据子语言的研究成为对谓词逻辑的研究。

3 关系演算

应用谓词逻辑表示关系数据库中的数据子语言，就叫关系演算。关系数据库中的基本数据结构二维表是一个n元有序组的集合，而关系演算是基于谓词逻辑的，因此这个n元有序组的集合可以用一个谓词逻辑公式表示，下面我们举例加以详细说明：

设有二维表如图1所示：

图1

图1所示二维表可用谓词公式F（x，y）=（y=x+1）ΛN（x）表示，其中N（x）表示x为自然数。

通过上例说明，我们可以建立集合论与谓词逻辑公式间的一一对应关系。数据子语言的操作对象二维表可用谓词公式表示，而对其对象的操作也可用谓词公式表示，下面我们加以详细说明：

谓词公式的基本符号：

由规则1得到的公式称为原子公式，而其余的公式称为合式公式。

接下来，我们用谓词公式来表示基本操作。我们先讨论插入、删除和修改。在关系代数中我们知道可以用并运算与差运算分别表示插入与删除，而在谓词逻辑中联结词“或者”相当于并运算，而联结词“并且”再在第二项中加以否定相当于差运算。假设：

上面的操作没有提到修改，是因为它是由删除和插入两个操作组合而成的，因此删除操作、插入操作可以由谓词刻划，则修改操作也可由谓词刻划。通过以上的谓词逻辑公式我们可以把关系数据库中的数据子语言变成谓词逻辑中的谓词公式，因而可以用谓词公式研究数据子语言。而应用上面的谓词公式对关系数据库的研究所形成的理论叫关系演算。

用关系演算中的公式表示关系数据库中的数据操作，在实际应用中它能够方便地对数据作检索及增加、删除、修改操作。接下来，我们将举例详细说明。

我们以上文中的表3-2，3-3，3-4所定义的二维表S、C、SC作为操作对象，将它们的谓词定义为：S（S#，NAME，SEX，AGE，DEP），C（C#，CN，CC），SC（S#，C#，CG）。 下面，我们进一些操作：

关系演算公理系统所采用的推理方法、定理及证明过程与谓词逻辑是相同的。由于谓词逻辑中的公理是永真的，因此谓词逻辑中的公理在关系演算中也可以认为是公理。

参考文献：

[1]赵永霞.数据库系统原理与应用[M].武汉大学出版社，2006.

[2]王志梅.关系数据库基础与技术[M].国防工业出版社，2005.

[3]李春葆，曾慧.数据库原理[M].清华大学出版社，2006.

[4]周定康，许婕.关系数据库理论及应用[M].华中科技大学出版社，2005.

[5]德特.数据库系统导论[M].中国电力出版社，2006.

[6]戴特.数据库系统导论[M].机械工业出版社，2007.

[7]Geoff Sutcliffe.Logic for Programming，Artificial Intelligence，and Reasoning.Springer，2006.

[8]布勒斯.可计算性与数理逻辑[M].电子工业出版社，2005.

[9]王国俊.数理逻辑引论与归结原理[M].科学出版社，2006.

[10]胡思.面向计算机科学的数理逻辑系统建模与推理[M].机械工业出版社，2005.

[11]恩德滕.数理逻辑[M].人民邮电出版社，2007.

[12]陆钟万.面向计算机科学的数理逻辑[M].科学出版社，2002.

[13]陈慕泽，余俊伟.数理逻辑基础：一阶逻辑与一阶理论[M].中国人民大学出版社，2003.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。