第2章
关系数据库

2.1　数学中关系的概念

在数学领域中，关系是代数集合中的一个基本概念，分为二元关系和多元关系。二元关系是多元关系的特例，多元关系是二元关系的推广。关系实际上是笛卡儿积的一个子集，在此先给出笛卡儿积的定义，然后给出多元关系的定义和相关的性质。

定义2.1： 设 D ₁ × D ₂ ×…× D _n 是 n （ n >1的自然数）个集合 D ₁ , D ₂ ,…, D _n 的 n 阶笛卡儿积，记作 D ₁ × D ₂ ×…× D _n ，并定义为：

其中，每个元素（ x ₁ , x ₂ ,…, x _n ）称为一个 n 元组， x _i ∈ D _i 称为元组的一个分量，集合 D _i 的取值范围称为域。

由上述定义可以看出， n 阶笛卡儿积实际上是由 n 元组构成的集合，它既可以是有限集合，也可以是无限集合。当笛卡儿积为有限集合时，可以用元素的列举法来表示。

【例2.1】 假设集合 D ₁ ={张清玫，刘逸}， D ₂ ={计算机专业，信息专业}， D ₃ ={李勇，刘晨，王敏}，则集合 D ₁ 、 D ₂ 、 D ₃ 的笛卡儿积为：

D ₁ × D ₂ ×…× D _n =（{ x ₁ , x ₂ ,…, x _n ）| x ₁ ∈ D ₁ , x ₂ ∈ D ₂ ,…, x _n ∈ D _n }

D ₁ × D ₂ × D ₃ ={(张清玫，计算机专业，李勇)，(张清玫，计算机专业，刘晨)，(张清玫，计算机专业，王敏)，(张清玫，信息专业，李勇)，(张清玫，信息专业，刘晨)，(张清玫，信息专业，王敏)，(刘逸，计算机专业，李勇)，(刘逸，计算机专业，刘晨)，(刘逸，计算机专业，王敏)，(刘逸，信息专业，李勇)，(刘逸，信息专业，刘晨)，(刘逸，信息专业，王敏)}。

当把集合 D ₁ ， D ₂ ， D ₃ 的笛卡儿积的每个元组作为一张二维表的每一行时， D ₁ ， D ₂ ， D ₃ 的笛卡儿积又可以用一张二维表来表示，如表2.1所示。

表2.1 D ₁ ， D ₂ ， D ₃ 的笛卡儿积

从上述具体实例可以看出， D ₁ ， D ₂ ， D ₃ 的笛卡儿积只是数学意义上的一个集合，它通常无法表达实际的语义。但是笛卡儿积的一个子集通常具有表达某种实际语义的功能，即关系具有某种具体的语义。

定义2.2： 假设 D ₁ , D ₂ ,…, D _n 是 n （ n >1的自然数）个集合，则 D ₁ , D ₂ ,…, D _n 的 n 阶笛卡儿积 D ₁ × D ₂ ×…× D _n 的一个子集称为集合 D ₁ , D ₂ ,…, D _n 上的一个 n 阶关系，记作 R （ D ₁ , D ₂ ,…, D _n ）。

【例2.2】 假设【例2.1】中的集合 D ₁ =导师集合={张清玫，刘逸}， D ₂ =专业集合={计算机专业，信息专业}， D ₃ =研究生集合={李勇，刘晨，王敏}，则集合 D ₁ ， D ₂ ， D ₃ 上的关系 R （ D ₁ ， D ₂ ， D ₃ ）={（张清玫，计算机专业，李勇），（张清玫，计算机专业，刘晨），（刘逸，信息专业，王敏）}有着明确的语义，即表示导师张清玫属于计算机专业，指导李勇和刘晨2名研究生；导师刘逸属于信息专业，指导王敏1名研究生。此关系的二维表如表2.2所示。

表2.2　导师与研究生的关系表

由于 D ₁ ， D ₂ ， D ₃ 的笛卡儿积包含所有的元组，因此没有明确的语义。例如，在 D ₁ ， D ₂ ， D ₃ 的笛卡儿积中，同时出现元组（张清玫，计算机专业，李勇）和（刘逸，信息专业，李勇），这两个元组分别表示李勇既是计算机专业张清玫导师的研究生，又是信息专业刘逸导师的研究生，这种情况与实际不符，所以笛卡儿积通常没有实际语义。

从关系的定义中可以得出，关系具有如下3条性质：

性质1： 关系不满足交换律，即 R （ D ₁ ， D ₂ ）≠ R （ D ₂ ， D ₁ ）。这可以解释为关系中元组分量的排列顺序是有序的，当分量排列顺序发生改变时，关系也会发生变化，表现了元组的有序性。

性质2： 关系可以是有限集合，也可以是无限集合。

性质3： 元组的分量不可以是2阶以上的元组。

2.2　关系数据模型

关系数据库是建立在关系数据模型上的数据库。本节主要介绍组成关系数据模型的两个要素，即关系数据结构和关系操作集合。

2.2.1　关系数据结构

在用关系描述关系模型的数据结构时，需要对2.1节中关系的3个性质进行限制和扩充，以满足数据库的需要。在关系数据模型中要求：

（1）关系是有限集合。

（2）关系的元组是无序的。

（3）元组的分量不能是2阶以上的元组，只能是单个的元素。

满足这3个条件的关系构成的关系模型中的数据结构可以用一个规范化的二维表（表中不能再有表）来表示。

关系数据结构涉及如下概念：

·　属性：若给关系中的每个 D _i （ i =1,2,…, n ）赋予一个有语义的名字，则把这个名字称为属性，属性的名不能相同。通过给关系集合附加属性名的方法取消关系元组的有序性。

·　域：属性的取值范围称为域，不同属性的域可以相同，也可以不同。

·　候选码：若关系中的某个属性组的值能唯一地标识一个元组，且不包含更多属性，则称该属性组为候选码。候选码的各个属性称为主属性，不包含在任何候选码中的属性称为非主属性或非码属性。在最简单的情况下，候选码只包含一种属性。在最极端的情况下，候选码包含所有属性，此时称为全码。

·　主码：当前使用的候选码或选定的候选码称为主码。用属性加下画线表示主码。

·　外码：若关系 R 中某个属性组是其他关系的主码，则该属性组称为关系 R 的外码。

·　关系模型：对关系模型的描述一般表示为：关系名（属性1，属性2，…，属性 n ）。

例如，【例2.2】导师与研究生之间的关系就是关系数据库的一个数据结构，可以用规范化的二维表（表2.2）来表示。此时的关系可以表示为导师与研究生（导师，专业，研究生），该关系包含导师、专业和研究生3个属性，属性的域值分别为{张清玫，刘逸}、{计算机专业、信息专业}、{李勇、刘晨、王敏}。若研究生没有重名，则研究生属性为主码，否则候选码为全码。这是一个基本关系。表2.3给出了非规范化的二维关系，它不能用来表示关系模型的数据结构。

表2.3　非规范化的二维关系

在关系模型中，实体及其之间的联系都用关系来表示。例如，学生实体、课程实体和学生与课程之间多对多的联系可以用关系表示如下：

     学生实体：学生(学号，姓名，年龄，性别，系名，年级)
     课程实体：课程(课程号，课程名，学分)
     学生实体与课程实体之间的联系：选修(学号，课程号，成绩)

通过增加一个包含学号和课程号属性的选修关系，将学生实体和课程实体之间的多对多联系表示出来。其中，“学号”和“课程号”分别是选修关系的外码，“学号，课程号”组是选修关系的主码。

以上表示的关系都称为基本关系或基本表，它是实际存在的表，是实际存储数据的逻辑表示。除此之外，还有查询表和视图表两种表：查询表是查询结果对应的表；视图表是由基本表或其他视图导出的虚表，不对应实际的存储数据。

2.2.2　关系操作

关系数据模型中常用的关系操作包括查询操作和更新操作两大部分。其中，更新操作又分为插入操作、删除操作和修改操作。

查询操作是关系数据库的一个主要功能。用来描述查询操作功能的方式有很多，早期主要使用关系代数和关系演算描述查询功能，现在使用结构化查询语言（structured query language，SQL）来描述。

关系代数和关系演算分别使用关系运算和谓词运算来描述查询功能，它们都是抽象的查询语言，且具有完全相同的查询描述能力。虽然抽象的关系代数和关系演算语言与具体关系数据库管理系统中实现的实际语言并不完全一致，但它们是评估实际系统中查询语言能力的标准或基础。关系数据库管理系统的查询语言除了提供关系代数或关系演算的功能外，还提供许多附加的功能，如聚集函数、关系赋值、算术运算等，这使得应用程序具备强大的查询功能。

SQL是介于关系代数和关系演算之间的结构化查询语言，不仅具有查询功能，还具有数据定义、数据更新和数据控制功能，是集数据定义、数据操作和数据控制于一体的关系数据语言。SQL充分体现了关系数据语言的特点和优点，是关系数据库的标准语言。

在关系数据语言中，关系操作采用集合操作的方式，即操作的对象是集合，操作的结果也是集合。这种方式称为一次一集合的方式。相应地，非关系数据模型的操作方式为一次一记录的方式。数据存储路径的选择完全由关系数据库管理系统优化机制来完成，不必向数据库管理员申请为其建立特殊的存储路径。因此，关系数据语言是高度非过程化的集合操作语言，具有完备的表达能力，功能强大，能够嵌入高级语言中使用。

2.3　数据库完整性

数据库的完整性（integrity）是指数据的正确性（correctness）和相容性（compatibility）。数据的正确性是指数据是符合现实世界语义、反映当前实际状况的；数据的相容性是指数据库同一对象在不同关系表中的数据是符合逻辑的。

数据库的完整性与安全性的区别：

·　数据的完整性：是为了防止数据库中存在不符合语义的数据，也就是防止数据库中存在不正确的数据。完整性检查和控制的防范对象是不合语义的、不正确的数据，防止它们进入数据库。

·　数据的安全性：是保护数据库，防止恶意破坏和非法存取。安全性控制的防范对象是非法用户和非法操作，防止他们对数据库数据进行非法存取。

为维护数据库的完整性，数据库管理系统必须实现如下功能：

1．提供定义完整性约束条件的机制

完整性约束条件也称为完整性规则，是数据库中的数据必须满足的语义约束条件。SQL标准使用了一系列概念来描述完整性，包括关系模型的实体完整性、参照完整性和用户定义完整性。这些完整性一般由SQL的数据定义语言（data definition language，DDL）语句来实现。

2．提供完整性检查的方法

数据库管理系统中检查数据是否满足完整性约束条件的机制称为完整性检查。一般在INSERT、UPDATE、DELETE语句执行后开始检查，也可以在事务提交时检查。

3．进行违约处理

数据库管理系统若发现用户的操作违背了完整性约束条件，将采取一定的动作，如拒绝（NO ACTION）执行该操作或级联（CASCADE）执行其他操作，进行违约处理，以保证数据的完整性。

关系的完整性指关系的完整性规则，即对关系的某种约束条件。实体完整性和参照完整性是关系模型必须满足的完整性约束条件，被称为关系的两个不变性，由关系系统自动支持。用户定义的完整性是应用领域应遵循的约束条件，体现在具体领域中语义的约束。

2.3.1　实体完整性

1．定义实体完整性

规则2-1： 实体完整性规则：

若属性（一个或一组） A 是基本关系 R 的主属性，则所有元组对应主属性 A 的分量都不能取空值，也称属性 A 不能取空值。

按照实体完整性规则的规定，基本关系主码不能取空值。例如，在选修关系“选修（ 学号，课程号 ，成绩）”中，若“学号，课程号”组为主码，则“学号”和“课程号”两个属性都不能取空值。

对实体完整性规则的说明如下：

（1）实体完整性规则是针对基本关系而言的。一个基本关系通常对应现实世界的一个实体集。

（2）现实世界中的实体是可区分的，即具有某种唯一性的标识，这个标识在关系数据模型中用主码表示。若主码为空，则说明存在某个不可标识的实体，这与现实世界的情况相矛盾。

关系模型的实体完整性在CREATE TABLE中用PRIMARY KEY定义。对于单属性构成的码，有两种说明方法：一种是定义为列级约束条件，另一种是定义为表级约束条件。对于多个属性构成的码，只有一种说明方法，即定义为表级约束条件。

【例2.3】 将Student表中的Sno属性定义为码，语句如下：

或者

【例2.4】 将SC表中的Sno、Cno属性组定义为码，语句如下：

2．实体完整性检查和违约处理

用PRIMARY KEY短语定义了关系的主码后，每当用户程序向基本表中插入一条记录或对主码列进行更新操作时，关系数据库管理系统按照实体完整性规则自动进行检查，包括：

（1）检查主码值是否唯一，如果不唯一，则拒绝插入或修改。

（2）检查主码的各个属性是否为空，只要有一个为空就拒绝插入或修改。

检查记录中主码值是否唯一的一种方法是进行全表扫描，依次判断表中每一条记录的主码值与将要插入的记录的主码值（或者要修改的新主码值）是否相同，如图2.1所示。

图2.1　用全表扫描方法检查主码唯一性

全表扫描的缺点是十分耗时。为了避免对基本表进行全表扫描，关系数据库管理系统一般都在主码上自动建立一个索引。如图2.2所示的B+树索引，通过索引查找基本表中是否已经存在新的主码值时不需要查看全部值，而是看特定的几个结点即可，大大提高了查找效率。

图2.2　使用索引检查主码唯一

新记录的主码值是25，通过主码索引，从B+树的根结点开始查找和读取3个结点：根结点（51）、中间结点（12 30）、叶结点（15 20 25）。该主码值已经存在，因此不能插入这条记录。

2.3.2　参照完整性

在现实世界中，实体与实体之间往往存在某种联系，而这种联系在关系模型中都用关系来表示，这就存在关系与关系之间的引用问题。通过定义外码和主码将不同的关系联系起来，外码与主码之间的引用规则称为参照完整性规则。

规则2-2： 参照完整性规则：

若属性（或属性组） F 是基本关系 R 的外码，它与基本关系 S 的主码 K _s 相对应（基本关系 R 与 S 可以是相同的关系），则对于 R 中每个元组在 F 上的值，要么取空值，要么等于 S 中某个元组的主码。其中，关系 R 称为参照关系，关系 S 称为被参照关系（目标关系）。显然，参照关系 R 的外码 F 和被参照关系 S 的主码 K _s 必须取自同一个域。

【例2.5】 学生实体和专业实体可以用下面的关系来表示：

     学生(学号，姓名，性别，专业号，年龄)
     专业(专业号，专业名)

在这两个关系中，“专业号”是学生关系的外码，专业关系的主码，用于描述学生实体与专业实体之间的一对一的联系。学生关系中的元组在“专业号”属性上的取值只能是空值或非空值：当取空值时，表示该学生还没分配专业；当取非空值时，这个值必须是专业关系中某个元组在“专业号”属性上的分量，表示该学生必须被分配到一个已存在的专业中，否则没有意义。

【例2.6】 若为学生关系再加一个“班长”属性，则可表示如下：

     学生-班长(学号，姓名，性别，专业号，年龄，班长)

在此关系中，“学号”是主码，“班长”是外码。虽然“学号”和“班长”的属性名不同，但是它们必须取自同一个“学号”的属性域。当“班长”属性值为空值时，表示该班还没选班长；当“班长”属性值非空时，此值必须是某元组在“学号”属性上的分量。“学号”主码和“班长”外码用于描述学生-班长实体内部之间的联系。

1．定义参照完整性

要定义关系模型的参照完整性，在CREATE TABLE中用FOREIGN KEY短语定义哪些列为外码，用REFERENCES短语指明这些外码参照哪些表的主码。

例如，关系SC中一个元组表示一个学生选修的某门课程的成绩，（Sno，Cno）是主码，Sno、Cno分别参照Student表的主码和Course表的主码。

【例2.7】 定义SC中的参照完整性，语句如下：

2．参照完整性检查和违约处理

参照完整性将两张表中的相应元组联系起来。因此，对被参照表和参照表进行增、删、改操作，有可能破坏参照完整性，必须进行检查以保证两张表的相容性。

例如，对于表SC和Student，有4种可能破坏参照完整性的情况：

（1）在表SC中增加一个元组，该元组的Sno属性值在表Student中找不到一个元组，其Sno属性值与之相等。

（2）修改表SC中的一个元组，修改后该元组的Sno属性值在表Student中找不到一个元组，其Sno属性值与之相等。

（3）从表Student中删除一个元组，造成表SC中某些元组的Sno属性值在表Student中找不到一个元组，其Sno属性值与之相等。

（4）修改表Student中一个元组的Sno属性，造成表SC中某些元组的Sno属性值在表Student中找不到一个元组，其Sno属性值与之相等。

当上述的不一致发生时，系统可以采用以下策略加以处理：

（1）拒绝（NO ACTION）执行：不允许该操作执行。该策略一般设置为默认策略。

（2）级联（CASCADE）操作：当删除或修改被参照表（Student）的一个元组导致与参照表（SC）的不一致时，删除或修改参照表中的所有导致不一致的元组。

（3）设置为空值：当删除或修改被参照表的一个元组时造成了不一致，则将参照表中的所有造成不一致的元组的对应属性设置为空值。

可能破坏参照完整性的情况及违约处理，如表2.4所示。

表2.4　可能破坏参照完整性的情况及违约处理

对于参照完整性，除了应该定义外码之外，还应定义外码列是否允许空值。

一般地，当对参照表和被参照表的操作违反了参照完整性时，系统选用默认策略，即拒绝执行。如果想让系统采用其他策略，则必须在创建参照表时显示地加以说明。

【例2.8】 显式说明参照完整性的违约处理示例。

关系数据库管理系统在实现参照完整性时，除了要提供定义主码、外码的机制外，还需要提供不同的策略供用户选择。具体选择哪种策略，要根据应用环境的要求来决定。

2.3.3　用户定义完整性

用户定义的完整性是指针对某一具体关系数据库的约束条件。它反映某一具体应用所涉及的数据必须满足的语义要求。例如，某个属性必须取唯一的值、某个非主属性不能取空值、某个属性的取值为0~100等。

关系模型应提供定义和检验这类完整性的机制，以便用统一的系统方法处理它们，而不由应用程序承担这种功能。

1．属性上的约束条件

1）属性上约束条件的定义

在CREATE TABLE中定义属性的同时，可根据应用要求定义属性上的约束条件，即属性值限制。包括：

·　列值非空（NOT NULL）。

·　列值唯一（UNIQUE）。

·　检查列值是否满足一个条件表达式（CHECK短语）。

（1）不允许取空值：

【例2.9】 在定义SC表时，说明Sno、Cno、Grade属性不允许取空值，语句如下：

（2）列值唯一：

【例2.10】 建立部门表DEPT，要求部门名称Dname列取值唯一，部门编号Deptno列为主码，语句如下：

（3）用CHECK短语指定列值应该满足的条件：

【例2.11】 表Student的Ssex只允许取“男”或“女”，语句如下：

【例2.12】 表SC的Grade的值应该在0和100之间，语句如下：

2）属性上约束条件的检查和违约处理

当往表中插入元组或修改属性的值时，关系数据库管理系统将检查属性上的约束条件是否被满足，如果不被满足，则拒绝执行操作。

2．元组上的约束条件

1）元组上约束条件的定义

与属性上约束条件的定义类似，在CREATE TABLE语句中可以用CHECK短语定义元组上的约束条件，即元组级的限制。同属性值限制相比，元组级的限制可以设置不同属性之间的取值的相互约束条件。

【例2.13】 当学生的性别是男时，其名字不能以“Ms.”开头。

性别是女性的元组都能通过该项检查，因为Ssex='女'成立；当性别是男性时，要通过检查则名字一定不能以“MS.”开头，因为Ssex='男'时，条件要想为真值，Sname NOT LIKE 'Ms.%'必须为真值。

2）元组上约束条件的检查和违约处理

当往表中插入元组或修改属性的值时，关系数据库管理系统将检查元组上的约束条件是否被满足，如果不被满足，则拒绝执行操作。

2.3.4　完整性约束命名子句

以上讲解的完整性约束条件都在CREATE TABLE语句中定义，SQL还在CREATE TABLE语句中提供了完整性约束命名子句CONSTRAINT，用来对完整性约束条件命名，从而可以灵活地增加、删除一个完整性约束条件。

1．完整性约束命名子句

完整性约束命名子句的语法如下：

     CONSTRAINT <完整性约束条件名> <完整性约束条件>

<完整性约束条件>包括NOT NULL、UNIQUE、PRIMARY KEY、FOREIGN KEY、CHECK短语等。

【例2.14】 建立学生登记表Student，要求学号在90000和99999之间，姓名不能取空值，年龄小于30岁，性别只能是“男”或“女”，语句如下：

【例2.15】 建立教师表TEACHER，要求每个教师的应发工资不低于3000元，应发工资是工资列Sal与扣除项Deduct之和，语句如下：

2．修改表中的完整性限制

使用ALTER TABLE语句可以修改表中的完整性限制。

【例2.16】 去掉【例2.14】的表Student中的对性别的限制，语句如下：

     ALTER TABLE Student DROP CONSTRAINT C4;

【例2.17】 修改表Student中的约束条件，要求学号改为在900000和999999之间，年龄由小于30岁改为小于40岁，语句如下：

2.3.5　域中的完整性限制

一般地，域是一组具有相同数据类型的值的集合。SQL支持域的概念，并可以用CREATE DOMAIN语句建立一个域以及该域应该满足的完整性约束条件，然后就可以用域来定义属性。数据库中不同的属性可以来自同一个域，当域上的完整性约束条件改变时，只需修改域的定义即可，而不用一一修改域上的各个属性。MySQL不支持域中的完整性限制。

【例2.18】 建立一个性别域，并声明性别域的取值范围，语句如下：

【例2.19】 建立一个性别域GenderDomain，并对其中的限制命名，语句如下：

【例2.20】 删除域GenderDomain的限制条件GD，语句如下：

【例2.21】 在域GenderDomain上增加性别的限制条件GDD，语句如下：

2.3.6　断言

在SQL中，数据定义语言允许使用CREATE ASSERTION语句，通过声明式断言定义更为一般的约束条件。这些断言能够定义跨多张表或包含聚合操作的复杂完整性约束。一旦断言被创建，关系数据库管理系统将在任何影响断言所涉及关系的数据库操作之前进行断言检查，任何使断言不为真值的操作都会被拒绝执行。

1．创建断言的语句格式

创建断言的语句格式如下：

     CREATE ASSERTION <断言名> <CHECK子句>

每个断言都被赋予一个名字，<CHECK子句>中的约束条件与WHERE子句的条件表达式类似。

【例2.22】 限制数据库课程最多60名学生选修，语句如下：

【例2.23】 限制每一门课程最多60名学生选修，语句如下：

【例2.24】 限制每个学期每一门课程最多60名学生选修，语句如下：

2．删除断言的语句格式

删除断言的语句格式如下：

     DROP ASSERTION <断言名>;

如果断言很复杂，则系统在检测和维护断言上的开销就比较高。这是在使用断言时应该注意的。

2.3.7　触发器

触发器（trigger）是用户定义在关系表上的一类由事件驱动的特殊过程。触发器保存在数据库服务器中。任何用户对表的增、删、改操作，均由服务器自动激活相应的触发器，在关系数据库管理系统核心层进行集中的完整性控制。触发器类似于约束，但比约束更加灵活，可以实施更为复杂的检查和操作，具有更精细和更强大的数据控制能力。

1．定义触发器

触发器又叫作事件−条件−动作（event-condition-action）规则。当特定的系统事件（如一张表的增、删、改操作，事务的结束等）发生时，对规则的条件进行检查，如果条件成立，则执行规则中的动作，否则不执行该动作。规则中的动作体可以很复杂，涉及其他表和其他数据库对象，通常是一段SQL存储过程。

定义触发器的一般格式如下：

定义触发器的语法说明如下：

（1）只有表的拥有者，即创建表的用户才可以在表上创建触发器，并且一张表上只能创建一定数量的触发器。

（2）触发器名可以包含模式名，也可以不包含模式名。同一模式下，触发器名必须是唯一的，且触发器名和表名必须在同一模式下。

（3）触发器只能定义在基本表上，不能定义在视图上。当基本表的数据发生变化时，将激活定义在该表上相应触发事件的触发器。

（4）触发事件可以是INSERT、DELETE或UPDATE，也可以是这几个事件的组合，还可以是UPDATE OF<触发列，...>，即进一步指明修改哪些列时激活触发器。

AFTER/BEFORE是触发的时机，AFTER表示在触发事件的操作执行之后激活触发器，BEFORE表示在触发事件的操作执行之前激活触发器。

（5）触发器类型包括行级触发器（FOR EACH ROW）和语句级触发器（FOR EACH STATEMENT）。

例如，在TEACHER表上创建一个AFTER UPDATE触发器，触发事件是UPDATE语句：

     UPDATE TEACHER SET Deptno=5;

假设表TEACHER有1000行，如果定义的触发器为语句级触发器，那么执行完该语句后触发动作只发生一次；如果是行级触发器，则触发动作将执行1000次。

（6）触发条件。触发器被激活时，只有当触发条件为真时，触发动作体才执行，否则触发动作体不执行。如果省略WHEN触发条件，则触发动作体在触发器激活后立即执行。

（7）触发动作体。触发动作体可以是一个匿名PL/SQL过程块，也可以是对已创建存储过程的调用。如果是行级触发器，用户可以在过程体中使用NEW和OLD引用UPDATE/INSERT事件之后的新值和UPDATE/DELETE事件之前的旧值；如果是语句级触发器，则不能在触发动作体中使用NEW或OLD进行引用。

如果触发动作体执行失败，激活触发器的事件就会终止执行，触发器的目标表或触发器可能影响的其他对象不发生任何变化。

【例2.25】 当对表SC的Grade属性进行修改时，若分数增加了10%，则将此次操作记录到另一张表的SC_U（Sno,Cno,Oldgrade,Newgrade）中，其中Oldgrade是修改前的分数，Newgrade是修改后的分数。

例子中REFERENCING指出引用的变量，如果触发事件是UPDATE操作并且有FOR EACH ROW子句，则可以引用的变量有OLDROW和NEWROW，分别表示修改之前的元组和修改之后的元组；若没有FOR EACH ROW子句，则可以引用的变量有OLDTABLE和NEWTABLE，OLDTABLE表示表中原来的内容，NEWTABLE表示表中变化后的部分。

【例2.26】 将每次对表Student进行插入操作所增加的学生个数记录到表StudentInsertLog中。

例子中出现的FOR EACH STATEMENT，表示触发事件INSERT语句执行完成后才执行一次触发器中的动作，这种触发器叫作语句级触发器。而【例2.25】中的触发器是行级触发器。默认的触发器是语句级触发器。DELTA是一个关系名，其模式与Student相同，包含的元组是INSERT语句增加的元组。

【例2.27】 定义一个BEFORE行级触发器，为教师表Teacher定义完整性规则“教授的工资不得低于4000元，如果低于4000元，则自动改为4000元”。

因为是BEFORE触发器，所以在插入和更新教师记录前就可以按照触发器的规则调整教授的工资，不必等插入后再检查和调整。

2．激活触发器

触发器的执行是由触发事件激活，并由数据库服务器自动执行的。一张数据表上可能定义了多个触发器，如多个BEFORE触发器、多个AFTER触发器等，同一张表上的多个触发器在激活时遵循如下的执行顺序：

·　执行该表上的BEFORE触发器。

·　激活触发器的SQL语句。

·　执行该表上的AFTER触发器。

对于同一张表上的多个BEFORE(AFTER)触发器，遵循“谁先创建谁先执行”的原则，即按照触发器创建的时间先后顺序执行。注意，有些关系数据库管理系统是按照触发器名称的字母排序顺序执行触发器的。

默认情况下，触发器在创建后将自动启用，如果不需要触发器起作用，则可以禁用它，然后在需要的时候再次启用。

1）禁用触发器

禁用触发器的语法如下：

     DISABLE TRIGGER { [schema_name. ] trigger_name [,... n ] | ALL}
     ON { object_name | DATABASE |ALL SERVER}

语法说明如下：

·　Schema_name：触发器所属架构名称，只针对数据操作语言（data manipulation language，DML）触发器。

·　trigger_name：触发器名称。

·　ALL：指示禁用在ON子句作用域中定义的所有触发器。

·　Object_name：触发器所在的表或视图名称。

·　DATABASE：对于DDL触发器，指示所创建或修改的trigger_name将在数据库作用域内执行。

·　ALL SERVER：适用于SQL Server 2008(10.0.x)及更高版本。

也适用于登录触发器。

禁用触发器不会删除触发器，该触发器仍然作为对象存在于当前数据库中。但是，当执行编写触发器程序所用的任何Transact-SQL语句时，不会激活该触发器。可以使用ENABLE TRIGGER重新启用触发器。还可以通过使用ALTER TABLE来禁用或启用为表定义的DML触发器。

【例2.28】 禁用DML触发器a_student，语句如下：

     DISABLE TRIGGER a_student ON student

【例2.29】 禁用DDL触发器a_table，语句如下：

     DISABLE TRIGGER a_table ON DATASASE

2）启用触发器

启用触发器的语法如下：

     ENABLE TRIGGER { [ scheme_name.] trigger_name [ ,… n] | ALL}
     ON {object_name|DATABASE |ALL SERVER}

启用触发器的语法和禁用触发器的语法大致相同，只是一个使用DISABLE关键字，另一个使用ENABLE关键字。

3．删除触发器

删除触发器的语法如下：

     DROP TRIGGER <触发器名> ON <表名>;

触发器必须是一个已经创建的触发器，并且只能由具有相应权限的用户删除。触发器是一种功能强大的工具，在使用时要慎重，因为每次访问表时都可能触发一个触发器，这样会影响系统的性能。

1）删除DML触发器

删除DML触发器的语法如下：

     DROP TRIGGER trigger_name [ ,...n]

【例2.30】 删除DML触发器a_student，语句如下：

     DROP TRIGGER a_student

2）删除DDL触发器

删除DDL触发器的语法如下：

     DROP TRIGGER trigger_name [ ,... n ]
     ON {DATABASE|ALL SERVER}

其中，DATABASE表示如果在创建或修改触发器时指定了DATABASE，删除时就必须指定DATABASE；ALL SERVER同理。

【例2.31】 删除DDL触发器a_table，语句如下：

     DROP TRIGGER a_table ON DATABASE

2.4　关系代数

关系代数是一种抽象的查询语言，用对关系的运算来表达查询，是研究关系数据语言的数学工具。关系代数的运算对象是关系，运算结果亦为关系。关系代数用到的运算符包括4类：集合运算符、专门的关系运算符、算术比较符和逻辑运算符。算术比较运算符和逻辑运算符是用来辅助专门的关系运算符进行操作的。因此，按照运算符的不同，关系代数主要分为传统的集合运算和专门的关系运算两类。

2.4.1　传统的集合运算

在数据库系统中，用到的集合运算仅包括集合的并、差、交和笛卡儿积4种。

假设有 n 阶关系 R 和 S ，若 R 和 S 对应的属性取自相同的域，则 R 与 S 的并、差和交分别定义为：

·　并：

R ∪ S ={ t | t ∈ R ∨ t ∈ S }

其运算结果仍为 n 阶关系，由属于关系 R 或 S 的元组组成。

·　差：

R - S ={ t | t ∈ R ∧ t ∉ S }

其运算结果仍为 n 阶关系，由属于关系 R 而不属于 S 的元组组成。

·　交：

R ∩ S ={ t | t ∈ R ∧ t ∈ S }

其运算结果仍为 n 阶关系，由既属于关系 R 又属于 S 的元组组成。

·　笛卡儿积：

假设有 n 阶关系 R 和 m 阶关系 S ，则关系 R 和 S 的笛卡儿积为：

R × S ={ t _r t _s | t _r ∈ R ∧ t _s ∈ S }

其运算结果是 n + m 阶关系。元组的前 n 列是关系 R 的一个元组，后 m 列是关系 S 的一个元组。

【例2.32】 若关系 R 和 S 分别如图2.3中的（a）和（b）所示，则关系 R 和 S 的并、交、差和笛卡儿积分别如图2.3中的（c）、（d）、（e）和（f）所示。

图2.3　传统集合运算举例

图2.3　传统集合运算举例（续）

2.4.2　专门的关系运算

专门的关系代数运算包括选择（selecting）、投影（projection）、连接（join）、除运算（division）等，现分别介绍如下：

1．选择

关系 R 的选择运算又称限制运算，它把关系 R 上满足某种关系或逻辑表达式 F 的元组选择出来，并组成一个新的关系，记作：

σ _F ( R )={ t | t ∈ R ∧ F ( t )='真'}

其中， t 为元组， F 为取值为真或假的关系表达式或逻辑表达式。选择运算实际上是选择关系 R 上某些行的运算。

【例2.33】 假设有一个学生－课程数据库，包括学生关系Student、课程关系Course和选课关系SC，如图2.4所示。现要查询信息系的全体学生和年龄小于20岁的学生。

查询信息系的全体学生可以表示为：

σ _Sdept ='IS'(Student)或 σ ₅ ='IS'(Student)

其中，下标5为Sdept属性的序号，查询结果如图2.5（a）所示。

查询年龄小于20岁的学生可以表示为：

σ _Sage <20(Student)或 σ ₄ <20(Student)

查询结果如图2.5（b）所示。

图2.4　学生−课程数据库

图2.5　选择运算结果

图2.5　选择运算结果（续）

2．投影

关系 R 的投影是从 R 中选择出若干个属性列组成新关系，记作：

π _A ( R )={ t [ A ]| t ∈ R }

其中， A 为 R 中的属性列， t [ A ]为由属性列是 A 的分量组成的元组。投影运算实际是选择关系 R 上某些列的运算。

【例2.34】 在【例2.33】的学生−课程数据库中，要查询学生的姓名和所在的系或查询有哪些系。

查询学生的姓名和所在的系实际上是求关系中学生姓名和所在系两个属性的投影，可以表示为：

π _Sname,Sdept (Student)或π _2,5 (Student)

查询结果如图2.6（a）所示。

查询有哪些系，即求Student关系所在系属性的投影，可以表示为：

π _Sdept (Student)或π ₅ (Student)

查询结果如图2.6（b）所示。

图2.6　投影运算结果

3．连接

假设有关系 R 和 S ， A 和 B 分别为与关系 R 和 S 阶数相等且可以进行比较的属性组， θ 是比较运算符，则关系 R 和 S 的连接运算可以表示为如下形式：

即连接运算是从关系 R 和 S 的笛卡儿积 R × S 中选取属性组 A 和 B 上的分量满足比较关系 θ （=、<、<=、>、>=、!=）的元组。

连接分为等值连接和非等值连接。等值连接是比较运算符取“=”的连接，其他连接都称为非等值连接。等值连接又分为自然连接和外连接。将两个关系中具有相同属性且按该属性进行等值连接，并去掉结果中的重复属性列的连接称为自然连接。自然连接是等值连接的一种特殊形式。等值连接和自然连接的形式可分别表示如下：

一般的连接操作是从行的角度进行运算的，但自然连接需要取消重复列，因此自然连接是从行和列的角度进行运算的。

【例2.35】 假设关系 R 和 S 分别如图2.7中的（a）和（b）所示，对关系 R 和 S 分别进行一般连接 、等值连接 和自然连接 R ∞ S ，其连接结果分别如图2.7中的（c）、（d）和（e）所示。

图2.7　连接运算

在自然连接中，选择两个关系中在公共属性上值相等的元组构成新的关系。如果把舍弃的元组保留在结果关系中，而在其他属性上填空值，这种连接就称为外连接，如图2.8（a）所示；如果只保留关系 R 中左边要舍弃的元组，就叫左外连接，如图2.8（b）所示；如果只保留关系 S 中右边要舍弃的元组，就叫右外连接，如图2.8（c）所示。

图2.8　外连接运算

4．除运算

给定关系 R （ X ， Y ）和 S （ Y ， Z ），其中 X 、 Y 、 Z 为属性组。 R 中的 Y 和 S 中的 Y 可以有不同的属性名，但必须取自相同的域。

R 与 S 的除运算是 R 中满足下列条件的元组在 X 属性上的投影，即元组在 X 上的分量值 x 的象集 Y _x 包含 S 在 Y 上投影的集合，记作：

R ÷ S ={ t _r [ X ]| t _r ∈ R ∧π _Y ( S )⊆ Y _x }

【例2.36】 假设关系 R （ A ， B ， C ）和 S （ B ， C ， D ）分别如图2.9（a）和图2.9（b）所示，则 R ÷ S 的结果如图2.9（c）所示。

R

图2.9　除运算

在关系 R 和 S 中，属性 X = A ，属性 Y ={ B ， C }，属性 X 的分量就是 A 的分量，因此可以取{ a ₁ ， a ₂ , a ₃ ， a ₄ }4个值。

· a ₁ 的象集 Y _{a 1} ={（ b ₁ , c ₂ ）,（ b ₂ , c ₃ ）,（ b ₂ , c ₁ ）}。

· a ₂ 的象集 Y _{a 2} ={（ b ₃ , c ₇ ）,（ b ₂ , c ₃ ）}。

· a ₃ 的象集 Y _{a 3} ={（ b ₄ , c ₆ ）}。

· a ₁ 的象集 Y _{a 4} ={（ b ₆ , c ₆ ）}。

S 在 Y =( B , C )上的投影π _Y ( S )=（{ b ₁ , c ₂ ）,（ b ₂ , c ₁ ）,（ b ₂ , c ₃ ）}。显然，只有 a ₁ 的象集 Y _{a 1} 包含 S 在 Y 属性组的投影π _Y ( S )，所以 R ÷ S ={ a ₁ }。

下面以学生−课程库为例，给出几个综合应用多种代数运算进行查询的实例。

【例2.37】 查询至少选修1号课程和3号课程的学生号码。

首先建立一个临时关系 K ：

然后求π _Sno,Cno ( SC )÷ K 。查询结果为{20160001}。

求解过程为，先对 SC 关系在（Sno，Cno）属性上进行投影，然后逐一求出每一个学生（Sno）的象集是否包含 K 。

【例2.38】 查询选修了2号课程的学生学号。

π _Sno ( σ _Cno='2' ( SC ))={20160001,20160002,20160004}

【例2.39】 查询至少选修了一门并且直接先修课是5号课程的学生姓名。

π _Sname ( σ _Cpno='5' (Course)∞ SC ∞π _Sno,Sname (Student))

或

π _Sname (π _Sno ( σ _Cpno='5' (Course)∞ SC )∞π _Sno,Sname (Student))

【例2.40】 查询选修了全部课程的学生的学号和姓名。

π _Sno,Cno ( SC )÷ σ _Cno (Course)∞π _Sno,Sname (Student)

关于关系演算的内容，请读者参考其他资料。

2.5　关系模式和范式理论

本节在1.3节模式概念的基础上，介绍在关系数据库中设计关系模式应遵守的规则，包括关系模式的形式定义、决定关系模式属性的依赖关系、范式理论、数据依赖的公理系统和模式分解等内容。

2.5.1　关系模式与属性依赖

在关系数据库中，关系和关系模式是两个非常重要的概念。关系是元组的集合，用一张二维表来表示。而关系模式是对关系元组逻辑结构和特征的描述，用于描述元组的属性、属性的域值、属性与域值之间的映像以及属性之间的依赖关系。因此，关系模式是型，关系则是关系模式的一个值，即实例。关系模式与关系是型与值之间的关系。关系模式的形式化定义如下：

R ( U , D , DOM , F )

其中：

· R 为关系名。

· U 为组成关系 R 的属性集。当属性集为 A ₁ , A ₂ ,…, A _n 时， U ={ A ₁ , A ₂ ,…, A _n }。

· D 为属性集 U 中属性 A ₁ , A ₂ ,…, A _n 的域。

· DOM 为属性到域的映射。

· F 为属性 U 上的一组数据之间的依赖关系。

定义2.3： 关系模式是一个4元组，记作：

在关系模式设计中，由于数据之间的依赖关系 F 决定了一个关系数据库中关系模式的个数和结构，因此先把关系模式看作二元组 R ( U , F )。

数据依赖实际上是一个关系的内部属性与属性之间的约束关系。这种约束关系是通过属性间值的相等与否体现出来的数据间相关的联系。它是现实世界属性间相互联系的抽象化，是数据内在的性质，是语义的体现。数据依赖主要有函数依赖和多值依赖。

定义2.4： 设 R ( U )是属性集 U 上的关系模式。 X ， Y 是 U 的子集。若对于 R ( U )的任意一个可能的关系 r ，不可能存在两个元组在 X 上的属性值相等，而在 Y 上的属性值不等的情况，则称 X 函数确定 Y 或 Y 函数依赖于 X ，记作 X → Y 。

函数依赖是语义范畴的概念。只能根据语义来确定一个函数的依赖。例如，姓名→年龄这个函数依赖只有在没有同名人的条件下成立，否则年龄就不再函数依赖于姓名。

下面介绍一些术语和记号：

·　若 X → Y ，但 Y ⊈ X ，则称 X → Y 是非平凡的函数依赖。

·　若 X → Y ，但 Y ⊆ X ，则称 X → Y 是平凡的函数依赖。对于任意一种关系模式，平凡函数依赖都是必然成立的，它不反映新的语义。若不特别声明，则讨论的是非平凡的函数依赖。

·　若 X → Y ，则 X 被称为这个函数依赖的决定属性组，也被称为决定因素。

·　若 X → Y ， Y → X ，则记作 Y —→ X 。

·　若 Y 不依赖于 X ，则记作 。

【例2.41】 假设有Student(Sno，Sname，Ssex，Sage，Sdept)，若不允许重名，则有：

Sno→Ssex，　　　Sno→Sage

Sno→Sdept，　　　Sno←→Sname

Sname→Ssex，　　Sname→Sage

Sname→Sdept

但Ssex Sage，Ssex Sdept

定义2.5： 在 R ( U )中，如果 X → Y ，并且对于 X 的任何一个真子集 X ＇，都有 X ＇→ Y ，则称 Y 对 X 完全函数依赖，记作：

若 X → Y ，但 Y 不完全函数依赖于 X ，则称 Y 对 X 部分函数依赖，记作：

定义2.6： 在 R ( U )中，如果 X → Y ，（ Y ⊈ X ）， ， Y → Z ， Z ⊈ Y ，则称 Z 对 X 传递函数依赖，记作：

候选码是关系模式中一个重要的概念。之前已经给出了有关候选码的定义，这里用函数依赖的概念定义等价的候选码。

定义2.7： 假设 K 为 R ( U ， F )中的一个或一组属性，若 ，则 K 为 R 的候选码。主码、外码的定义不变。

2.5.2　范式理论

在关系数据库设计中，所有数据的逻辑结构及其相互联系都由关系模式来表达，因此关系模式的结构是否合理直接影响关系数据库性能的好坏。

在数据库设计中，首先需要解决的问题是如何根据实际问题的需要来构造合适的数据模式，即需要设计关系模式的个数和每个关系模式的属性等，也就是关系数据库的逻辑设计问题。为了满足实际问题的需求，在任何数据库设计中都要遵循一定的规则，这些规则在关系数据库中被称为范式。范式实际上是关系数据库中的关系必须满足的条件。根据满足不同层次的条件，目前范式可以分为8种，依次为第一范式（1NF）、第二范式（2NF）、第三范式（3NF）、BCNF、第四范式（4NF）、第五范式（5NF）、DKNF、第六范式（6NF）。满足最低要求的范式是1NF，在1NF的基础上进一步满足更多要求的范式是2NF，以此类推。各个范式之间的关系为6NF⊂DKNF⊂5NF⊂4NF⊂BCNF⊂3NF⊂2NF⊂1NF。本节主要介绍函数依赖的前4个范式和多值依赖的4NF，其他范式可以参考相关文献。

一个低一级范式的关系模式，通过模式分解（schema decomposition）可以转换为若干个高一级范式的关系模式的集合，这个过程就叫作规范化（normalization）。

1．1NF

在一个关系模式中，关系对应一张二维表，如果表中的每个分量都是不可分的数据项，就称这个关系模式为第一范式。

【例2.42】 有关系模式：联系人（姓名，性别，电话）。在实际应用中，如果一个联系人有家庭电话和公司电话，这种表结构设计就不符合1NF的要求。要符合1NF的要求，只需把电话属性拆分为家庭电话和公司电话两个属性即可，关系模式为：联系人（姓名，性别，家庭电话，公司电话）。

2．2NF

定义2.8： 若 R ∈1NF，且每一个非主属性完全函数依赖于任何一个候选码，则 R ∈2NF。

【例2.43】 有关系模式：S-L-G（ Sno ，Sdept，Sloc， Cno ，Grade）。其中，Sloc为学生的住处，并且每个系的学生住在同一个地方；（Sno，Cno）为S-L-G的主码。函数依赖关系有：

·

·

·

上述依赖关系如图2.10所示，虚线表示部分函数依赖。此例中非主属性Sdept和Sloc并不完全依赖于主码，所以S-L-G（ Sno ，Sdept，Sloc， Cno ，Grade）不满足2NF的条件。

图2.10　函数依赖实例

一个关系模式 R 不属于2NF，就会产生以下几个问题：

1）插入异常

假如要在S-L-G（Sno，Sdept，Sloc，Cno，Grade）中插入一个学生Sno=S7，Sdept=PHY，Sloc=BLD2，但该学生还未选课（这个学生的主属性Cno值为空），这样的元组就无法插入S-L-C中。因为插入元组时主码不能为空值，而这时主码值的一部分为空，所以学生的固有信息无法插入。

2）删除异常

假如某个学生只选一门课，如 S ₄ 就选择了一门 C ₃ 课程。现在他不选 C ₃ 这门课程了，那么 C ₃ 这个数据项就要被删除。而 C ₃ 是主属性，如果删除了 C ₃ ，整个元组就必须被删除，这使得 S ₄ 的其他信息也会被删除，进而造成删除异常，即不应删除的信息也被删除了。

3）修改复杂

假如某个学生从数学系（MA）转到计算机科学系（CS），这本来只需修改此学生元组中的Sdept分量，但因为关系模式S-L-C中还含有系的住处Sloe属性，学生转系的同时将改变住处，所以还必须修改元组中的Sloc分量。另外，如果这个学生选修了 k 门课，则Sdept、Sloc重复存储 k 次，这样不仅存储冗余度大，还必须无遗漏地修改 k 个元组中全部Sdept、Sloc的信息，从而造成修改的复杂化。

分析上面的例子，可以发现问题在于有两种非主属性：一种如Grade，对主码是完全函数依赖；另一种如Sdept、Sloc，对主码不是完全函数依赖。解决的办法是用投影分解把关系模式S-L-C分解为两个关系模式。

·　SC（ Sno ， Cno ，Grade）

·　S-L（ Sno ，Sdept，Sloc）

关系模式SC与S-L中的函数依赖分别用图2.11和图2.12表示。

图2.11　SC中的函数依赖

图2.12　S-L中的函数依赖

关系模式SC的主码为（Sno，Cno），关系S-L的主码为Sno，这样使得非主属性对主码都是完全函数依赖。

3．3NF

定义2.9： 关系模式 R ( U , F )∈1NF，若 R 中不存在这样的码 X ，属性组 Y 及非主属性 Z （ Z ⊈ Y ），使得 X → Y 、 Y → Z 成立， ，则称 R ( U , F )∈3NF。

由定义2.9可以证明，若 R ∈3NF，则每一个非主属性既不部分依赖于主码，也不传递依赖于主码。

在图2.11的关系模式SC中没有传递依赖，而图2.12的关系模式S-L中存在非主属性对主码的传递依赖。在S-L中，由Sno→Sdept、（Sdept Sno）、Sdept→Sloc可得， 。因此， SC ∈3NF而S-L∉3NF。

一个关系模式 R 若不是3NF，则会产生与2NF相类似的问题。解决的办法同样是将S-L分解为：

·　S-D（Sno，Sdept）

·　D-L（Sdept，Sloc）

分解后的关系模式为S-D和D-L中不再存在传递依赖。

4．BCNF

BCNF是由Boyce与Codd提出的比3NF进一步的范式，通常被认为是修正的第三范式，有时也称为扩充的第三范式。

定义2.10： 假设关系模式 R ( U , F )∈1NF，若 X → Y 且 Y ⊆/ X 时 X 必含有主码，则 R ( U , F )∈BCNF。

也就是说，在关系模式 R ( U , F )中，若每一个决定因素都包含主码，则 R ( U , F )∈BCNF。

由BCNF的定义可知，一个满足BCNF的关系模式有如下特点：

·　所有非主属性对每一个主码都是完全函数依赖。

·　所有主属性对每一个不包含它的主码也是完全函数依赖。

·　没有任何属性完全函数依赖于非主码的任何一组属性。

由于 R ∈BCNF，按定义排除了任何属性对主码的传递依赖与部分依赖，因此 R ∈3NF。但若 R ∈3NF，则 R 未必属于BCNF。

【例2.44】 有关系模式S（Sno，Sname，Sdept，Sage），若Sname也具有唯一性，则S∈3NF，同时S∈BCNF。

在S模式中，因为Sno和Sname都是码，且是单个属性，彼此互不相交，其他属性不存在对主码的传递依赖与部分依赖，所以S∈3NF。同时，在S中，除了Sno和Sname外没有其他决定因素，所以S∈BCNF。

【例2.45】 在关系模式SJP（S，J，P）中，S表示学生，J表示课程，P表示名次。每一个学生选修的每门课程的成绩都有一定的名次，每门课程中每一个名次只有一个学生（没有并列名次）。由语义可得到下面的函数依赖：

（S，J）→P；（J，P）→S

因此，（S，J）与（J，P）都可以作为候选码。这两个码各由两个属性组成，而且它们是相交的。这个关系模式中显然没有属性对码的传递依赖或部分依赖，SJP∈3NF，而且除了（S，J）与（J，P）外没有其他决定因素，所以SJP∈BCNF。

【例2.46】 在关系模式STJ(S，T，J)中，S表示学生，T表示教师，J表示课程。每一名教师只教一门课，每门课有若干名教师，某一个学生选定某门课就对应一个固定的教师。由语义可得到函数依赖：（S，J）→T；（S，T）→J；T→J，如图2.13所示。其中，（S，J）和（S，T）都是候选码。

图2.13　STJ中的函数依赖

STJ是3NF，因为没有任何非主属性对码传递依赖或部分依赖。但STJ不属于BCNF关系，因为T是决定因素，且T不包含码。

对于不属于BCNF的关系模式，仍然存在不合适的地方。对于非BCNF的关系模式，可以通过分解的方法将其分成几个符合BCNF的模式。例如，STJ可分解为ST（S，T）与TJ（T，J），它们都是BCNF。

3NF和BCNF是在函数依赖条件下对模式分解所能达到的分离程度的一种测度。一个模式中的关系模式如果都属于BCNF，那么它在函数依赖范畴内已经实现了彻底分离，消除了插入和删除的异常。3NF的“不彻底”性表现在可能存在主属性对码部分依赖和传递依赖。

5．多值依赖

定义2.11 ：假设 R ( U )是属性集 U 上的一个关系模式。 X ， Y ， Z 是 U 的子集，并且 Z = U − X − Y 。关系模式 R ( U )中多值依赖 X →→ Y 成立，当且仅当对 R ( U )的任一关系 r 给定的一对( x ， y )值有一组 Y 的值，这组值仅决定于 x 值而与 z 值无关。

若 X →→ Y ，而 Z = ϕ ，即 Z 为空，则称 X →→ Y 为平凡的多值依赖。即对于 R ( X ， Y )，如果 X →→ Y 成立，则 X→→Y 为平凡的多值依赖。

举例，有这样一个关系<仓库管理员，仓库号，库存产品号>，假设一个产品只能放到一个仓库中，但是一个仓库可以有若干管理员，那么对于一个<仓库管理员，库存产品号>，有一个仓库号，而实际上，这个仓库号只与库存产品号有关，与管理员无关，就说这是多值依赖。

6．4NF

定义2.12： 关系模式 R ( U ， F )∈1NF，如果对于 R 的每个非平凡多值依赖 X→→Y ( Y ⊈ X )， X 都含有码，则称 R ( U ， F )>∈4NF。

4NF就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。因为根据定义，对于每一个非平凡的多值依赖 X→→Y ， X 都含有候选码，于是就有 X→Y ，所以4NF所允许的非平凡的多值依赖实际上是函数依赖。显然，如果一个关系模式是4NF，则必为BCNF。

【例2.47】 假设有关系模式WSC(W，S，C)，W表示仓库，S表示管理员，C表示商品。假设每个仓库有若干名管理员和若干种商品，每个管理员保管所在仓库的所有商品，每种商品被所有管理员保管，关系如表2.5所示。

表2.5　WSC的关系表

按照语义，对于W的每一个值W _i ，无论C取何值，S都有一个完整的集合与之对应，所以W→→S。因为每个管理员保管所有商品，同时每种商品被所有管理员保管，所以若W→→S，则必然有W→→C。

因为W→→S和W→→C都是非平凡的多值依赖，而W不是码，关系模式WSC的码是（W，S,C），所以WSC∉4NF。

WSC是一个BCNF，但不是4NF关系模式，它仍然有一些不好的性质。若某个仓库W _i 有 n 个管理员，存放 m 件物品，则关系中分量为 W _i 的元组数目一定有 m × n 个。每个管理员重复存储 m 次，每种物品重复存储 n 次，数据的冗余度太大，因此还应该继续规范化，使关系模式WSC达到4NF。

可以用投影分解的方法消去非平凡且非函数依赖的多值依赖。例如，可以把WSC分解为WS（W，S），WC（W，C）。在WS中虽然有W→→S，但这是平凡的多值依赖。WS中已不存在非平凡的非函数依赖的多值依赖，所以WS∈4NF，同理WC∈4NF。

函数依赖和多值依赖是两种最重要的数据依赖。如果只考虑函数依赖，则属于BCNF的关系模式规范化程度已经是最高的了；如果考虑多值依赖，则属于4NF的关系模式规范化程度是最高的。事实上，数据依赖中除函数依赖和多值依赖之外，还有其他数据依赖，例如连接依赖。函数依赖是多值依赖的一种特殊情况，而多值依赖实际上又是连接依赖的一种特殊情况。但连接依赖不像函数依赖和多值依赖那样可由语义直接导出，而是在关系的连接运算时才反映出来。存在连接依赖的关系模式仍可能遇到数据冗余及插入、修改、删除异常等问题。如果消除了属于4NF的关系模式中存在的连接依赖，则可以进一步达到5NF的关系模式。这里不再讨论连接依赖和5NF，有兴趣的读者可以参阅有关书籍。

2.5.3　数据依赖的公理系统

数据依赖的公理系统是模式分解算法的理论基础。下面首先讨论函数依赖的一个有效而完备的公理系统——Armstrong公理系统（Armstrong’s axiom）。

定义2.13： 对于满足一组函数依赖 F 的关系模式 R ( U ， F )，其任何一个关系 r ，若函数依赖 X → Y 都成立（即 r 中任意两元组 t 、 s ，若 t [ X ]= s [ X ]，则 t [ Y ]= s [ Y ]），则称 F 逻辑蕴涵 X → Y 。

为了从一组函数依赖求得蕴涵的函数依赖，例如已知函数依赖集 F ，要问 X → Y 是否为 F 所蕴涵，就需要一套推理规则，这组推理规则是1974年首先由Armstrong提出来的。

Armstrong公理系统设 U 为属性集总体， F 是 U 上的一组函数依赖，于是有关系模式 R ( U ， F )，对 R ( U ， F )来说，有以下公理：

·　自反律（reflexivity rule）：若 Y ⊆ X ⊆ U ，则 X → Y 为 F 所蕴涵。

·　增广律（augmentation rule）：若 X → Y 为 F 所蕴涵，且 Z ⊆ U ，则 XZ → YZ 为 F 所蕴涵。

·　传递律（transitivity rule）：若 X → Y 及 Y → Z 为 F 所蕴涵，则 X → Z 为 F 所蕴涵。

定理2.1： Armstrong推理规则是正确的。

下面从定义出发证明推理规则的正确性。

证明：

（1）设 Y ⊆ X ⊆ U 。

对 R ( U , F )的任一关系 r 中的任意两个元组 t 、 s ：若 t [ X ]= s [ X ]，由于 Y ⊆ X ，有 t [ Y ]= s [ Y ]，因此 X → Y 成立，自反律得证（ t [ X ]表示元组 t 在属性（组） X 上的分量，等价于 t . X ）。

（2）设 X → Y 为 F 所蕴涵，且 Z ⊆ U 。

对 R ( U , F )的任一关系 r 中的任意两个元组 t 、 s ：若 t [ XZ ]= s [ XZ ]，则有 t [ X ]= s [ X ]和 t [ Z ]= s [ Z ]；由于 X → Y ，于是有 t [ Y ]= s [ Y ]，因此 t [ YZ ]= s [ YZ ]， XZ → YZ 为 F 所蕴涵，增广律得证。

（3）设 X → Y 及 Y → Z 为 F 所蕴涵。

对 R ( U , F )的任一关系 r 中的任意两个元组 t 、 s ：若 t [ X ]= s [ X ]，由于 X → Y ，有 t [ Y ]= s [ Y ]；再由于 Y → Z ，有 t [ Z ]= s [ Z ]，因此 X → Z 为 F 所蕴涵，传递律得证。

根据上述这3条公理可以得到下面3条很有用的推理规则。

·　合并规则（unionrule）：由 X → Y ， X → Z ，有 X → YZ 。

·　伪传递规则（pseudo transitivity rule）：由 X → Y ， WY → Z ，有 XW → Z 。

·　分解规则（decomposition rule）：由 X → Y 及 Z ⊆ Y ，有 X → Z 。

根据合并规则和分解规则，很容易得到这样一个重要事实：

引理2.1： X → A ₁ A ₂ … A _k 成立的充分必要条件是 X → A _i 成立 i =1,2,…, k 。

定义2.14： 在关系模式 R ( U , F )中为 F 所逻辑蕴涵的函数依赖的全体叫作 F 的闭包（closure），记为 F ⁺ 。

人们把自反律、增广律和传递律称为Armstrong公理系统。Armstrong公理系统是有效且完备的。Armstrong公理的有效性指的是由 F 出发根据Armstrong公理推导出来的一个函数依赖一定在 F ⁺ 中；完备性指的是 F 中的每一个函数依赖，必定可以由 F 出发根据Armstrong公理推导出来。

要证明完备性，首先就要判定一个函数依赖是否属于由 F 根据Armstrong公理推导出来的函数依赖的集合。当然，如果能求出这个集合，问题就解决了。但不幸的是，这是一个NP完全问题。例如，从 F ={ X → A ₁ ，…， X → A _n }出发，至少可以推导出2 ⁿ 个不同的函数依赖。为此引入了下面的概念：

定义2.15： 设 F 为属性集 U 上的一组函数依赖， X 、 Y ⊆ U ， ={ A | X → A 能由 F 根据Armstrong公理导出}， 称为属性集 X 关于函数依赖集 F 的闭包。

由引理2.1容易得出引理2.2。

引理2.2： 设 F 为属性集 U 上的一组函数依赖， X 、 Y ⊆ U ， X → Y 能由 F 根据Armstrong公理导出的充分必要条件是 。

于是，判定 X → Y 是否能由 F 根据Armstrong公理导出的问题就转换为求出 ，判定 Y 是否为 的子集的问题。这个问题由算法2.1解决了。

算法2.1： 求属性集 X （ X ⊆ U ）关于 U 上的函数依赖集 F 的闭包 。

输入： X 、 F

输出：

步骤：

令 X ⁽⁰⁾ = X ， i =0。

求 B ，这里 B ={ A |(∃ V )(∃ W )( V → W ∈ F ∧ V ⊆ X ^{( i )} ∧ A ∈ W )}。

X ^{( i +1)} = B ∪ X ^{( i )} 。

判断 X ^{( i +1)} = X ^{( i )} 。

若 X ^{( i +1)} 与 X ^{( i )} 相等或 X ^{( i )} = U ，则它就是 ，算法终止。

若 X ^{( i +1)} ≠ X ^{( i )} 或 X ^{( i )} ≠ U ，则 i = i +1，返回 。

【例2.48】 已知关系模式 R ( U , F )，其中

U ={ A , B , C , D , E }， F ={ AB → C , B → D , C → E , EC → B , AC → B }。

求： 。

解： 由算法2.1，设 X ⁽⁰⁾ = AB 。

计算 X ⁽¹⁾ ：逐一扫描 F 集合中各个函数依赖，找左部为 A 、 B 或 AB 的函数依赖。得到两个： AB → C ， B → D 。于是 X ⁽¹⁾ = AB ∪ CD = ABCD 。

因为 X ⁽⁰⁾ ≠ X ⁽¹⁾ ，所以再找出左部为 ABCD 子集的那些函数依赖，又得到 C → E ， AC → B ，于是 X ⁽²⁾ = X ⁽¹⁾ ∪ BE = ABCDE 。

因为 X ⁽²⁾ 已等于全部属性集合，所以 。

对于算法2.1，令 a _i =| X ^{( i )} |，{ a _i }形成一个步长大于1的严格递增的序列，序列的上界是|U|，因此该算法最多进行 次循环就会终止。

定理2.2： Armstrong公理系统是有效且完备的。

Armstrong公理系统的有效性可由定理2.1得到证明。下面给出完备性的证明。证明完备性的逆否命题，即若函数依赖 X → Y 不能由 F 从Armstrong公理导出，那么它必然不为 F 所蕴涵。它的证明分为以下3步。

证明：

（1）若 V → W 成立，且 ，则 。

因为 ，所以 X → V 成立，于是 X → W 成立（因为 X → V ， V → W ），因此 。

（2）构造一张二维表 r ，它由下列两个元组构成，可以证明 r 必是 R ( U , F )的一个关系，即 F 中的全部函数依赖在 r 上成立。

若 r 不是 R ( U , F )的关系，则必由于 F 中有某一个函数依赖 V → W 在 r 上不成立所致。由 r 的构成可知， V 必定是 的子集，而 W 不是 的子集，可是这与第一步中的 矛盾。因此， r 必是 R ( U , F )的一个关系。

（3）若 X → Y 不能由 F 从Armstrong公理导出，则 Y 不是 的子集，因此必有 Y 的子集 Y ＇满足 ，则 X → Y 在 r 中不成立，即 X → Y 必不为 R ( U , F )蕴涵。

Armstrong公理的完备性及有效性说明了“导出”与“蕴涵”是两个完全等价的概念。于是 F ⁺ 也可以说是由 F 出发借助Armstrong公理导出的函数依赖的集合。

从蕴涵（或导出）的概念出发，又引出了两个函数依赖集等价和最小依赖集的概念。

定义2.16 ：如果 G ⁺ = F ⁺ ，就说函数依赖集 F 覆盖 G （ F 是 G 的覆盖或 G 是 F 的覆盖），或 F 与 G 等价。

引理2.3： F → G 的充分必要条件是 F ⁺ ⊆ G ⁺ 和 G ⊆ F ⁺ 。

证明： 必要性很明显，这里只证明充分性。

（1）若 F ⊆ G ⁺ ，则 。

（2）任取 X → Y ∈ F ⁺ ，则有 ，所以 X → Y ∈( G ⁺ ) ⁺ = G ⁺ ，即 F ⁺ ⊆ G ⁺ 。

（3）同理可证 G ⁺ ⊆ F ⁺ ，所以 F ⁺ = G ⁺ 。

而要判定 F ⊆ G ⁺ ，只需逐一对 F 中的函数依赖 X → Y 考察 Y 是否属于 即可。因此引理2.3给出了判断两个函数依赖集等价的可行算法。

定义2.17： 如果函数依赖集 F 满足下列条件，则称 F 为一个极小函数依赖集，亦称为最小依赖集或最小覆盖（minimal cover）。

（1） F 中任一函数依赖的右部仅含有一个属性。

（2） F 中不存在这样的函数依赖 X → A ，使得 F 与 F -{ X → A }等价。

（3） F 中不存在这样的函数依赖 X → A ， X 有真子集 Z 使得 F -{ X → A }∪{ Z → A }与 F 等价。

定义2.17（3）的含义是对于 F 中的每个函数依赖，它的左部要尽可能简。

【例2.49】 有关系模式 S ( U , F )，其中：

设 F ＇={Sno→Sdept,Sno→Mname,Sdept→Mname,(Sno,Cno)→Grade,(Sno,Sdept)→Sdept}。

根据定义2.17可以验证 F 是最小覆盖，而 F ＇不是。因为 F ＇−{Sno→Mname)与 F ＇等价 F ＇−{(Sno,Sdept)→Sdept}也与 F ＇等价。

定理2.3： 每一个函数依赖集 F 均等价于一个极小函数依赖集 F _m 。此 F _m 称为 F 的最小依赖集。

证明： 这是一个构造性的证明，分3步对 F 进行“极小化处理”，找出 F 的一个最小依赖集来。

（1）逐一检查 F 中各函数依赖 FD _i ： X → Y ，若 Y = A ₁ A ₂ … A _k ， k >2，则用{ X → A _j | j =1,2,…, k }来取代 X → Y 。

（2）逐一检查 F 中各函数依赖 FD _i ： X → A ，令 G = F −{ X → A }，若 ，则从 F 中去掉此函数依赖（因为 F 与 G 等价的充要条件是 ）。

（3）逐一取出 F 中各函数依赖 FD _i ： X → A ，设 X = B ₁ B ₂ … B _m ， m ≥2，逐一考查 B （ _i i =l,2,…, m ），若 ，则以 X − B _i 取代 X （因为 F 与 F −{ X − A }∪{ Z − A }等价的充要条件是 ，其中 Z = X − B _i )。

最后剩下的 F 就一定是极小依赖集，并且与原来的 F 等价。因为对 F 的每一次“改造”都保证了改造前后的两个函数依赖集等价。这些证明很简单，请读者自行补上。需要注意， F 的最小依赖集 F _m 不一定是唯一的，它与对各函数依赖 FD _i 及 X → A 中 X 各属性的处置顺序有关。

【例2.50】

这里给出了 F 的两个最小依赖集 F _{m 1} 、 F _{m 2} 。

若改造后的 F 与原来的 F 相同，说明 F 本身就是一个最小依赖集，因此定理2.3的证明给出的极小化过程也可以看作检验 F 是否为极小依赖集的一个算法。

两个关系模式 R ₁ ( U , F )、 R ₂ ( U , F )如果 F 与 G 等价，那么 R ₁ 的关系一定是 R ₂ 的关系；反过来， R ₂ 的关系也一定是 R ₁ 的关系。因此，在 R ( U , F )中用与 F 等价的依赖集 G 来取代 F 是允许的。

2.5.4　模式分解

在对函数依赖的基本性质有了初步了解之后，可以具体地来讨论模式的分解了。

定义2.18： 关系模式 R ( U , F )的一个分解是指，

ρ ={ R ₁ ( U ₁ , F ₁ ), R ₂ ( U ₂ , F ₂ ),…, R _n ( U _n , F _n )}

其中 ，并且没有 U _i ⊆ U _j ，1≤ i ， j ≤ n ， F _i 是 F 在 U _i 上的投影。

所谓“ F _i 是 F 在 U _i 上的投影”的确切定义见定义2.19。

定义2.19： 函数依赖集合{ X → Y | X → Y ∈ F ⁺ ∧ XY ⊆ U _i }的一个覆盖 F _i 叫作 F 在属性 U _i 上的投影。

1．模式分解的3个定义

对于一个模式的分解是多种多样的，但是分解后产生的模式应与原模式等价。人们从不同的角度去观察问题，对“等价”的概念形成了3种不同的定义：

·　分解具有无损连接性（lossless join）。

·　分解要保持函数依赖（preserve functional dependency）。

·　分解既要保持函数依赖，又要具有无损连接性。

这3个定义是实行分解的3条不同的准则。按照不同的分解准则，模式所能达到的分离程度各不相同，各种范式就是对分离程度的测度。

本节要讨论的问题是：

（1）无损连接性和保持函数依赖的含义是什么？如何判断？

（2）对于不同的分解等价定义究竟能达到何种程度的分离，即分离后的关系模式是第几范式。

（3）如何实现分离，即给出分解的算法。

先来看两个例子，说明按定义2.18，若只要求 R < U , F >分解后的各关系模式所含属性的“并”等于 U ，这个限定是不够的。

一个关系分解为多个关系，相应地原来存储在一张二维表内的数据就要分散存储到多张二维表中，要使这个分解有意义，起码的要求是后者不能丢失前者的信息。

【例2.51】 已知关系模式 R ( U , F )，其中 U ={Sno,Sdept,Mname}， F ={Sno→Sdept,Sdept→Mname}。 R ( U , F )的元组语义是学生Sno正在Sdept系学习，其系主任是Mname，并且一个学生（Sno）只在一个系学习，一个系中只有一名系主任。 R 的一个关系如表2.6所示。

表2.6 R 的一个关系

由于 R 中存在传递函数依赖Sno→Mname，因此会发生更新异常。例如，如果 S ₄ 毕业，则 D ₃ 系的系主任张二的信息也就丢掉了；反过来，如果一个系 D ₅ 尚无在校学生，那么这个系的系主任赵某的信息也无法存入。于是进行了如下分解：

p ₁ ={ R ₁ (Sno, ϕ ), R ₂ (Sdept, ϕ ), R ₃ (Mname, ϕ )}

分解后， R _i 的关系 r _i 是 R 在 U _i 上的投影，即 r _i = R [ U _i ]：

r ₁ ={ S ₁ , S ₂ , S ₃ , S ₄ }, r ₂ ={ D ₁ , D ₂ , D ₃ }, r ₃ ={王三，李四，张二，王六}

对于分解后的数据库，要回答“ S ₁ 在哪个系学习”也不可能了。这样的分解还有什么用呢？

如果分解后的数据库能够恢复到原来的情况，不丢失信息的要求也就达到了。 R _i 向 R 的恢复是通过自然连接来实现的，这就产生了无损连接性的概念。显然，本例的分解 p ₁ 所产生的诸关系自然连接的结果实际上是它们的笛卡儿积，元组增加了，信息丢失了。

于是对 R 又进行另一种分解：

p ₂ ={ R ₁ ({Sno,Sdept},{Sno→Sdept}), R ₂ ({Sno,Mname},{Sno→Mname})}

后面可以证明 p ₂ 对 R 的分解是可恢复的，但是前面提到的插入和删除异常仍然没有解决，原因就在于原来在 R 中存在的函数依赖Sdept→Mname，现在在 R 中都不存在了。因此，人们又要求分解具有“保持函数依赖”的特性。

最后对 R 进行以下分解：

p ₃ ={ R ₁ ({Sno,Sdept},{Sno→Sdept}), R ₂ ({Sdept,Mname},{Sdept→Mname})}

可以证明分解 p ₃ 既具有无损连接性，又保持函数依赖。它解决了更新异常的问题，又没有丢失原数据库的信息，这是所希望的分解。

由此可以看出为什么要对数据库模式“等价”提出3个不同定义。

下面严格地定义分解的无损连接性和保持函数依赖性，并讨论它们的判别算法。

2．分解的无损连接性和保持函数依赖性

先定义一个记号：设 ρ ={ R ₁ < U ₁ , F ₁ >,…, R _k < U _k , F _k >}是 R < U , F >的一个分解， r 是 R < U , F > m ( r ) rρ 的一个关系。定义，即 _ρ 是在中各关系模式上投影的连接。这里 。

引理2.4： 设 R < U , F >是一个关系模式， ρ ={ R ₁ < U ₁ , F ₁ >,…, R _k < U _k , F _k >}是 R 的一个分解， r 是 R 的一个关系， ，则

（1） r ∈ m _ρ ( r )。

（2）若 s = m _ρ ( r )，则 。

（3） m _ρ ( m _ρ ( r ))= m _ρ ( r )。

证明：

（1）证明 r 中的任何一个元组属于 m _ρ ( r )。

任取 r 中的一个元组 t ， t ∈ r ，设 t _i = t . U _i （ i =1,2,… k ）。对 k 进行归纳可以证明 ，所以 t ∈ m _ρ ( r )，即 r ⊆ m _ρ ( r )。

（2）由（1）得到 r ⊆ m _ρ ( r )，已设 s = m _ρ ( r )，所以 r ⊆ s ， 。现只需证明 ，就有 。

任取 ，必有 S 中的一个元组 v ，使得 v . U _i = S _i 。根据自然连接的定义 v = t ₁ t ₂ … t _k ，对于其中每一个 t _i ，必存在 r 中的一个元组，使得 t . U _i = t _i 。由前面 的定义可得 。又因 v = t ₁ t ₂ … t _k ，故 v . U _i = t _i 。又由上面证得 v . U _i = S _i ， ，故 。即 。

（3） 。

定义2.20 ： ρ ={ R ₁ < U ₁ , F ₁ >,…, R _k < U _k , F _k >}是 R < U , F >的一个分解，若对 R < U , F >的任何一个关系 r 均有 r = m _ρ ( r )成立，则称分解 ρ 具有无损连接性，简称 ρ 为无损分解。

直接根据定义2.20去鉴别一个分解的无损连接性是不可能的，算法2.2给出了一种判别方法。

算法2.2： 判别一个分解的无损连接性。

ρ ={ R ₁ < U ₁ , F ₁ >,…, R _k < U _k , F _k >}是 R < U , F >的一个分解， U ={ A ₁ ,…, An }， F ={ FD ₁ , FD ₂ ,…, FD _ρ }，不妨设 F 是一极小依赖集，记 FD _i 为 X _i → A _li 。

建立一张 n 列 k 行的表，每一列对应一个属性，每一行对应分解中的一个关系模式。若属性 A _i 属于 U _i ，则在 j 列 i 行交叉处填上 a _j ，否则填上 b _ij 。

对每一个 FD _i 做下列操作：找到所对应的列中具有相同符号的那些行，考察这些行中 li 列的元素，若其中有 a _li ，则全部改为 a _li ；否则全部改为 b _mli 。其中 m 是这些行的行号最小值。

应当注意的是，若某个 b _tli 被更改，那么该表的 li 列中凡是 b _tli 的符号（不管它是否开始找到的那些行）均应作相应的更改。

如在某次更改之后，有一行成为 a ₁ , a ₂ ,…, a _n ，则算法终止， ρ 具有无损连接性，否则 ρ 不具有无损连接性。

对 F 中 p 个 FD 逐一进行一次这样的处置，称为对 F 的一次扫描。

比较扫描前后的表有无变化，如有变化则返回 ，否则算法终止。如果发生循环，那么前次扫描至少应使该表减少一个符号。表中符号有限，因此循环必然终止。

定理2.4： 如果算法2.2终止时表中有一行为 a ₁ , a ₂ ,…, a _n ，则 ρ 为无损连接分解。

证明从略。

【例2.52】 已知 R < U , F >， U ={ A , B , C , D , E }， F ={ AB → C , C → D , D → E }， R 的一个分解为 R ₁ ( A , B , C )， R ₂ ( C , D )， R ₃ ( D , E )。

（1）首先构造初始表，如表2.7所示。

（2）对 AB → C ，因各元组的第1、2列没有相同的分量，所以表不改变。由 C → D 可以把 b ₁₄ 改为 a ₄ ，再由 D → E 可使 b ₁₅ 、 b ₂₅ 全改为 a ₅ 。最后结果如表2.8所示。表中第1行成为 a ₁ 、 a ₂ 、 a ₃ 、 a ₄ 、 a ₅ ，所以此分解具有无损连接性。

表2.7　初始表

表2.8　最终表

当关系模式 R 分解为两个关系模式 R ₁ 、 R ₂ 时，有下面的判定准则。

定理2.5： 对于 R < U ， F >的一个分解 ρ ={ R ₁ < U ₁ , F ₁ >, R ₂ < U ₂ , F ₂ >}，如果 U ₁ ∩ U ₂ → U ₁ - U ₂ ∈ F ⁺ 或 U ₁ ∩ U ₂ → U ₂ - U ₁ ∈ F ⁺ ，则 ρ 具有无损连接性。

定理的证明留给读者完成。

定义2.21： 若 ，则 R < U , F >的分解 ρ ={ R ₁ < U ₁ , F ₁ >,…, R _k < U _k , F _k >}保持函数依赖。

引理2.4给出了判断两个函数依赖集等价的可行算法，因此也给出了判别 R 的分解 ρ 是否保持函数依赖的方法。

3．模式分解的算法

关于模式分解的几个重要事实是：

（1）若要求分解保持函数依赖，那么模式分离总可以达到3NF，但不一定能达到BCNF。

（2）若要求分解既保持函数依赖，又具有无损连接性，那么模式分离可以达到3NF，但不一定能达到BCNF。

（3）若要求分解具有无损连接性，那么模式分离一定可达到4NF。

它们分别由算法2.3、算法2.4、算法2.5和算法2.6来实现。

算法2.3（合成法）： 转换为3NF的保持函数依赖的分解。

对 R < U , F >中的函数依赖集 F 进行“极小化处理”（处理后得到的依赖集仍记为 F ）。

找出所有不在 F 中出现的属性（记作 U ₀ ），把这样的属性构成一个关系模式 R ₀ < U ₀ , F ₀ >。把这些属性从 U 中去掉，剩余的属性仍记为 U 。

若有 X → A ∈ F ，且 XA = U ，则 ρ ={ R }，算法终止。

否则，对 F 按具有相同左部的原则分组（假定分为 k 组），每一组函数依赖所涉及的全部属性形成一个属性集 U _i 。若 U _i ⊆ U _j （ i ≠ j ），就去掉 U _i 。由于经过了 ，故 ，于是 构成 R < U , F >的一个保持函数的分解，并且每个 R _i < U _i , F _i >均属3NF。这里 F _i 是 F 在 U _i 上的投影，并且 F _i 不一定与 相等，但 一定被 F _i 所包含，因此分解 ρ 保持函数依赖是显然的。

下面证明每一个 R _i < U _i , F _i >一定属于3NF。

设 ， U _i ={ X , A ₁ , A ₂ ,…, A _k }

（1） R _i < U _i , F _i >一定以 X 为码。

（2）若 R _i < U _i , F _i >不属于3NF，则必存在非主属性A _m （1≤ m < k ）及属性组合 Y ， A _m ∉ Y ，使得 X → Y ， ，而 。

（3）若 Y ⊂ X ，则与 X → A _m 属于最小依赖集 F 相矛盾，因而 Y ⊆/ X 。不妨设 Y ∩ X = X ₁ ， Y - X ={ A ₁ ,…, A _ρ }，令 G = F -{ X → A _m }，显然 ，即X→Y∈G ⁺ 。

可以断言 Y → A _m 也属于 G ⁺ 。因为 ，所以 。若 Y → A _m 不属于 G ⁺ ，则在求 的算法中，只有使用 X → A _m 才能将 A _m 引入。于是按算法2.1必有 j ，使得 X ⊆ Y ( j )，这与 Y → X 成立是矛盾的。

于是 X → A _m 属于 G ⁺ ，与 F 是最小依赖集相矛盾。因此， R _i < U _i , F _i >一定属于3NF。

算法2.4： 转换为3NF的既有无损连接性又保持函数依赖的分解。

（1）设 X 是 R < U , F >的码。 R < U , F >已由算法2.3分解为 ρ ={ R ₁ < U ₁ , F ₁ >, R ₂ < U ₂ , F ₂ >,…, R _k < U _k , F _k >}∪ R ₀ < U ₀ , F ₀ >，令 τ ← ρ ∪{ R *< X , F _x >}。

（2）若有某个 U _i ， X ⊆ U _i ，将 R *< X , F _x >从 τ 中去掉，或者 U _i ⊆ X ，将 R < U _i , F _x >从 τ 中去掉。

（3） τ 就是所求的分解。

R *< X , F _x >显然属于3NF，而保持函数依赖也很显然，因此只需判定无损连接性即可。

由于 τ 中必有某关系模式 R ( T )的属性组 ， X 是 R < U , F >的码，任取 U − T 中的属性 B ，必存在某个 i ，使 B ∈ T ^{( i )} （按算法2.1）。对 i 施行归纳法可以证明（由算法2.2），表中关系模式 R ( T )所在的行一定可成为 a ₁ , a ₂ ,…, a _n 。因此， τ 的无损连接性得证。

算法2.5（分解法）： 转换为BCNF的无损连接的分解。

令 ρ ={ R < U , F >}。

检查 ρ 中各关系模式是否均属于BCNF。若是，则算法终止。

设 ρ 中 R _i < U _i , F _i >不属于BCNF，那么必有 （ A ∉ X ，且 X 非 R _i 的码）。因此， XA 是 U _i 的真子集。对 R _i 进行分解：σ={ S ₁ , S ₂ }， Us ₁ = XA ， Us ₂ = U _i −{ A }，以σ代替 R _i ( U _i , F _i )，返回 。

由于 U 中属性有限，因而有限次循环后算法2.5一定会终止。

这是一个自顶向下的算法。它自然地形成一棵针对 R < U , F >的二叉分解树。应当指出， R < U , F >的分解树不是唯一的。这与 中具体选定的 X → A 有关。算法2.5最初令 ρ ={ R < U , F >}，显然 ρ 是无损连接分解，而以后的分解则由下面的引理2.5保证它的无损连接性。

引理2.5： 若 ρ ={ R ₁ < U ₁ , F ₁ >,…, R _k < U _k , F _k >}是 R < U , F >的一个无损连接分解， σ ={ S ₁ , S ₂ ,…, S _m }是 ρ 中 R _i ( U _i , F _i )的一个无损连接分解，那么 ρ ＇={ R ₁ , R ₂ ,…, R _{i -1} , S ₁ ,…, S _m , R _{i +1} ,…, R _k }， ρ ＇={ R ₁ ,…, R _k , R _{k +1} ,…, R _n }（ ρ ＇是 R < U , F >包含 ρ 的关系模式集合的分解）均是 R < U , F >的无损连接分解。

证明的关键是自然连接的结合律，下面给出结合律的证明，其他部分留给读者。

引理2.6： ( R ₁ ∞ R ₂ )∞ R ₃ = R ₁ ∞( R ₂ ∞ R ₃ )

证明：

设 r _i 是 R _i < U _i , F _i >的关系， i =1,2,3。

设 U ₁ ∩ U ₂ ∩ U ₃ = V ； U ₁ ∩ U ₂ - V = X ； U ₂ ∩ U ₃ - V = Y ； U ₁ ∩ U ₃ - V = Z ，如图2.14所示。

图2.14　引理2.6的三个关系属性示意图

容易证明 t 是 中的一个元组的充要条件是： T _{R 1} 、 T _{R 2} 、 T _{R 3} 是 t 的连串，这里 T _Ri ∈ r _i ( i =1，2，3)， T _{R 1} [ V ]= T _{R 2} [ V ]= T _{R 3} [ V ]， T _{R 1} [ X ]= T _{R 2} [ X ]， T _{R 1} [ Z ]= T _{R 3} [ Z ]， T _{R 2} [ Y ]= T _{R 3} [ Y ]。而这也是 t 为 中的元组的充要条件。于是有

在2.5.2节中已经指出，一个关系式中若存在多值依赖（指非平凡的非函数依赖的多值依赖），则数据的冗余度大且存在插入、修改、删除异常等问题。为此要消除这种多值依赖，使模式分离达到一个新的高度——4NF。下面讨论达到4NF的具有无损连接性的分解。

定理2.6： 关系模式 R < U , D >中， D 为 R 中函数依赖和多值依赖的集合。 X →→ Y 成立的充要条件是 R 的分解 ρ ={ R ₁ ( X , Y ), R ₂ ( X , Z )}具有无损连接性，其中 Z = U - X - Y 。

证明： 先证充分性。

若 ρ 是 R 的一个无损连接分解，则对 R < U , F >的任一关系 r ，有

设 t 、 s ∈ r ，且 t [ X ]= s [ X ]，于是 t [ XY ]、 。由于 t [ X ]= s [ X ]，因此 t [ XY ]∙ s [ XZ ]与 t [ XZ ]∙ s [ XY ]均属于 ，也即属于 r 。

令 u = t [ XY ]∙ s [ XZ ]， v = t [ XZ ]∙ s [ XY ]，就有 u [ X ]= v [ X ]= t [ X ]， u [ Y ]= t [ Y ]， u [ Z ]= s [ Z ]， v [ Y ]= s [ Y ]， v [ Z ]= t [ Z ]，所以 X →→ Y 成立。

再证必要性。

若 X →→ Y 成立，对于 R < U , D >的任一关系 r ，任取 ，则必有 t 、 s ∈ r ，使得 ω = t [ XY ]∙ s [ XZ ]，由于 X →→ Y 对 R < U , D >成立， ω 应当属于 r ，因此 ρ 是无损连接分解。

定理2.6给出了对 R < U , D >的一个无损的分解方法。若 R < U , D >中 X →→ Y 成立，则R的分解 ρ ={ R ₁ ( X , Y ), R ₂ ( X , Z )}具有无损连接性。

算法2.6： 达到4NF的具有无损连接性的分解。

首先使用算法2.5得到 R 的一个达到了BCNF的无损连接分解 ρ ，然后对某一 R _i < U _i ， D _i >，如果它不属于4NF，则可按定理2.6进行分解，直到每一个关系模式均属于4NF为止。定理2.6和引理2.5保证了最后得到的分解的无损连接性。

4．小结

关系模式 R < U , D >， U 是属性总体集， D 是 U 上的一组数据依赖函数依赖和多值依赖，对于包含函数依赖和多值依赖的数据依赖，有一个有效且完备的公理系统。该系统有以下8条公理：

（1）若 Y ⊆ X ⊆ U ，则 X → Y 。

（2）若 X → Y ，且 Z ⊆ U ，则 XZ → YZ 。

（3）若 X → Y ， Y → Z ，则 X → Z 。

（4）若 X →→ Y ， V ⊆ W ⊆ U ，则 XW →→ YV 。

（5）若 X →→ Y ，则 X →→ U - X - Y 。

（6）若 X →→ Y ， Y →→ Z ，则 X →→ Z − Y 。

（7）若 X → Y ，则 X →→ Y 。

（8）若 X →→ Y ， W → Z ， W ∩ Y =∅， Z ⊆ Y ，则 X → Z 。

公理系统的有效性是指，从 D 出发根据8条公理推导出的函数依赖或多值依赖一定为 D 蕴涵；完备性是指，凡 D 所蕴涵的函数依赖或多值依赖均可以从 D 根据8条公理推导出来。也就是说，在函数依赖和多值依赖的条件下，“蕴涵”与“导出”是等价的。

前面3条公理的有效性在2.5.2节已经证明了，其余的有效性证明留给读者自行完成。

由8条公理可得如下4条有用的推理规则：

（1）合并规则： X →→ Y ， X →→ Z ，则 X →→ YZ 。

（2）伪传递规则： X →→ Y ， WY → Z ，则 WX →→ Z − WY 。

（3）混合伪传递规则： X →→ Y ， XY → Z ，则 X → Z − Y 。

（4）分解规则： X →→ Y ， X → Z ，则 X →→ Y ∩ Z ， X →→ Y − Z ， X →→ Z − Y 。 dM1vLAiYh+Z8eQCjS7O4EKb3fTJUnoCUjDpQZmtfSEwKBNa08agdREhHdKZyIQXC