数据库系统概念

第一章

1.1 Purpose of Database Systems

In the early days, database applications were built directly on top of file systems.

Problems:

• Data redundancy and inconsistency （冗余，不一致性）

• 数据访问困难（difficulty in accessing data）。Need to write a new program to carry out each new task (eg. Finding out the students who come from…)

• 数据孤立。Multiple files and formats

• Integrity problems （完整性问题）
  （1）Integrity constraints (e.g. account balance > 0) become “buried” in program code rather than being stated explicitly
  （2）当新的约束加入时，很难通过修改程序来体现这些新的约束。Hard to add new constraints or change existing ones

• 原子性问题（Atomicity of updates）
  比如说把A系的账户余额中的500美元转入B系的账户余额中的这样一个程序。计入在程序的执行过程中发生了系统故障。操作必须是原子的——它要么全部发生要么根本不发生。在传统的文件处理系统中，保持原子性是很难做到的。

• 并发访问异常（concurrent-access anomaly）

  Concurrent access by multiple users
  Uncontrolled concurrent accesses may lead to inconsistencies
  Example: (a1) A = account
  (a2) A = A – 100
  (b1) B = account
  (a3) account = A
  (b2) B = B – 100
  (b3) account = B

• Security problems
  Hard to provide user access to some, but not all, data
  Database systems offer solutions to all the above problems
  以上的问题促进了数据库系统的发展。

1.2 View of Data

数据抽象的三个层次：

• 物理层（physical level)。

  （1）describes how data is actually stored.
  （2）Database developers use this level.

• Logical level:
  （1）describes what data are stored in the database, and what relationships exist among those data
  （2）Database administrators and application programmers use this level.

• View level:
  （1）simplifies the interaction with the system. Views can also hide information for security purposes.
  （2）Computer users use this level.

1.2.1 Instances and Schemas（实例和模式）

特定时刻存储在数据库中的信息的集合称作数据库的一个实例。而数据库的总体设计称为数据库模式。

根据前面我们所讨论的不同的抽象层次，数据库系统可以分为几种不同的模式。物理模式（physical schema）在物理层描述数据库的设计。逻辑模式（logical schema）则在逻辑层描述数据库的设计。数据库在视图层也可以由几种模式，有时称为子模式（subschema）。

应用程序如果不依赖于物理模式，它们就被称为是具有物理数据独立性（physical data independence），因此即使物理模式改变了它们也无需重写。

1.2.2 数据模型（data model）

数据模型提供了一种描述物理层、逻辑层以及视图层数据库设计的方式

可分为四类：

• 关系模型（relational model）。

关系模型用表的集合来表示数据和数据间的关系。每个表有多个列，每列有唯一的列名。

• 实体-联系模型（entity-relationship model）。

实体-联系（E-R）数据模型基于对现实世界的这样一种认识：现实世界由一组称作实体的基本对象以及这些对象间的联系构成。

• 基于对象的数据模型（object-based data model）。

面向对象的数据模型可以看成是E-R模型增加了封装、方法（函数）和对象标识等概念后的拓展。

• 半结构化数据模型（semistructured data model）。

半结构化数据模型允许那些相同类型的数据项含有不同的属性集的数据定义。

1.3 数据库语言

数据库系统提供数据定义语言（data-definition language）来定义数据库模式，以及数据操纵语言（data-manipulation language）来表达数据库的查询和更新。

1.3.1 数据操纵语言

DML能让用户可访问或操纵那些按照某种适当的数据模型组织起来的数据。有以下访问类型：

• 对存储在数据库中的信息进行检索。
• 向数据库中插入新的信息。
• 从数据库中删除信息。
• 修改数据库中存储的信息

通常分为两类：

• 过程化DML（procedural DML)要求用户指定与要什么数据以及如何获得这些数据。
• 声明式DML（declarative DML)只要求用户指定需要什么数据，二不指明如何获得这些数据。

查询（query)是要求对信息镜像检索的语句。DML中设计信息检索的部分称为查询语言。

1.3.2 数据定义语言

数据库系统所使用的的存储结构和访问方式是通过一系列特殊的DDL语句来说明的。这种特殊的DDL称作数据存储和定义(data storage and definition)语言。

存储在数据库中的数据值必须满足某些一致性约束（consistency constraint）。

1.4 关系数据库

SQL（Structured Query Language）

1.5数据库设计

略

1.6事务管理

事物（transaction）是数据库应用中完成单一逻辑功能的操作集合。每一个事务是一个既具原子性又具一致性的单元。

1.7 数据库用户和管理员

• 无经验的用户(naive user)是默认经验的用户。
• 应用程序员（application programmer）是编写应用程序的计算机专业人员。
• 老练的用户（sophisticated user）不通过编写程序来同系统交互，而是用数据库查询语言或数据分析软件这样的工具来表达他们的要求。
• 专门的用户（specialized user）是编写专门的、不适合于传统数据框架的数据库应用的富有经验的用户。

第二章 关系模型

2.1 关系模型介绍

在关系模型的术语中，关系（relation）来指代表，而元祖（tuple）用来指代行。属性（attribute）指代的是表中的列。

对于关系的每个属性，都存在一个允许取值的集合，称为该属性的域（domain）。

2.2 码

超码（superkey）是一个或多个属性的集合。这些属性的组合可以使我们在一个关系中唯一地表示一个元组。超码也有可能包含无关紧要的属性。

候选码（candidate key)：任意真子集都不能成为超码

主码（primary key）：被数据库设计者选中的、主要用来在一个关系中区分不同元组的候选码。

外码（foreign key)：一个关系模式（如$r_1$)可能在它的属性中包括另一个关系模式（如$r_2$）的主码。这个属性在$r_1$上称作参照$r_2$的外码。关系$r_1$也称为外码依赖的参照关系（referencing relation），$r_2$叫做外码的被参照关系（referenced relation）。

2.3 模式图

一个含有主码和外码依赖的数据库模式可以用模式图（schema diagram）来表示。每一个关系用一个矩形来表示，关系的名字显示在矩形上方，矩形内列出各属性。主码属性用下划线标注。外码依赖用从参照关系的外码属性到被参照关系的主码属性之间的箭头来表示。

2.4 关系运算

符号	例子
$\sigma$ (选择)	$\sigma_{salary>=85000}(instructor)$
$\prod$ (投影，projection)	$\prod_{ID,salary}(instructor)$
$\bowtie$ (自然连接)	instructor$\bowtie$department
x (笛卡尔积)	instructor x department
$\cup$ （并）
$\rho$ ()

第三章 SQL

3.1 SQL数据定义

数据库中的关系集合必须由数据定义语言（DDL）指定给系统。SQL的DDL不仅能够定义一组关系，还能够定义每个关系的信息，包括：

• 每个关系的模式
• 每个属性的取值类型
• 完整性约束
• 每个关系维护的索引集合
• 每个关系的安全性和权限信息
• 每个关系在磁盘上的物理存储结构

3.1.1 基本类型

SQL标准支持多种固有类型，包括：

• char(n)：固定长度的字符串，用户指定长度n。也可以使用全称character。
• varchar(n)：可变长度的字符串
• int：整数类型
• smallint：小整数类型（和机器相关的整数类型的子集）
• numeric(p,d)：定点数，精度由用户指定。这个数由p位数字（加上一个符号位），其中d位数字在小数点右边。所以在一个这种类型的字段上，numeric(3,1)可以精确储存44.5，但不能精确存储444.5或0.32.
• real,double precision：浮点数与双精度浮点数，精度与机器相关。
• float(n)：精度至少为n位的浮点数。

3.1.2 基本模式定义

create table r
	(A1 D1,
     A2 D2,
     ...,
     An Dn,
     <完整性约束1>,
     ...,
     <完整性约束k>);
	

SQL支持许多不同的完整性约束。

• primary key

primary key 声明表示属性$A_{j1}、A_{j_2}…$构成关系的主码。主码属性必须非空其唯一，也就是说没有一个元组在主码属性上取空值，关系中也没有两个元组在所有主码属性上取值相同。

• foreign key

foreign key 声明关系中任意元组在属性上的取值必须对应于关系s中某元组在主码属性上的取值。

• not null

一个属性上的not null 约束表明在该属性上不允许空值。

3.1.3 Drop and Alter Table Constructs

• To delete the table (the schema is also deleted): drop table < table name>

• To delete all contents of table (the schema is retained):

  delete from < table name >

3.2 SQL查询的基本结构

3.2.1 单关系查询

select name

from instructor

现在考虑另一个查询：“找出所有教师所在的系名”。

select dept_name

from instructor

因为一个系有多个教师，所以上述查询到结果是一个包含多个系名的关系。在关系模型的形式化数学定义中，关系是一个集合。因此，重复的元组不会出现在关系中。在实践中，去除重复是相当费时的。所以SQL允许出现重复。

如果我们想要删除重复，可在select后加入关键词distinct。

默认是不去除重复的，如果我们想要显式保留重复，可以在select后加入关键词all。

select子句还可带含义+、-、*、/运算符的算术表达式。

where子句允许我们只选出那些在from子句的结果关系中满足特定谓词的元组。

3.2.2多关系查询

select A1，A2…,An

from r1,r2…rm

where P;

3.2.3 自然连接

natural join

另外，为了发扬自然连接的优点，同时避免不必要的相等属性带来的文献。SQL提供了一种自然连接的构造形式，允许用户来指定一个属性名列表——join … using …

3.3 附加的基本运算

3.3.1 更名运算

as子句。可出现在select 子句中也可出现在from子句中。

3.3.2 字符串运算

like子句来表示模式

select sept_name

from department

where building like ‘%Watson%’;

模式：（大小写敏感）

• %：匹配任意子串
• _：匹配任意一个字符

在like 比较运算中使用escape关键词来定义转义字符。

SQL允许使用not like 比较运算符搜寻不匹配项。

3.3.3 select 子句中的属性说明

星号*可以用在select子句中表示所有的属性。

3.3.4 排列元组的显示次序

order by 子句。默认使用升序，我们可以用desc表示降序，或者用asc表示升序。

select *

from instructor

order by salary desc, name asc

3.3.5 where子句谓词

SQL提供between比较运算符。

SQL允许我们用记号(v1,v2,…,vn)来表示一个n维元组，在元组上可以运用比较运算符，按字典顺序进行比较运算。

select name,course_id

from instructor ,teaches

where (instructor.ID,dep_name)=(teaches.ID,‘Biology’);

3.4 集合运算

union,intersect和except运算对应于数学集合论中的$\cup、\cap、-$运算。

且自动去除重复。

3.5 空值

SQL将涉及空值的任何比较运算的结果视为unknown。

• and:

true and unknown =unknown.

false and unknown =false.

unknown and unknown =unknown.

• or:

true or unknown =true.

false or unknown =unknown.

unknown or unknown =unknown

• not

null=null返回unknown,而不是true。

3.6 聚集函数

聚集函数是以值的一个集合（集或多重集）为输入、返回单个值的函数。SQL提供了五个固有聚集函数：

• 平均值:avg
• 最小值:min
• 最大值:max
• 总和：sum
• 计数:count

3.6.1 分组聚集

group by 子句。在该子句中的所有属性取值相同的元组将被分在一个组中。

3.6.2 having 子句

用于分组限定条件。

3.6.3 对空值和布尔值的聚集

除了count外所有的聚集函数都忽略输入集合中的空值。

count:规定空集的值为0。

3.7 嵌套子查询

select 、from、where语句都支持嵌套子查询。

A common use of subqueries is to perform tests for

• set membership: in, not in
• set comparisons: some, all
• empty set: exists, not exists
• set containment: not exists (B except A)

返回true值

• duplicate tuples: unique, not unique

3.7.1 with 子句

with 子句提供定义临时关系的方法。

with max_budget(value) as

​ (select max (budget)

​ from department)

select budget

from department,max_budget

where departmen.budget=max_budget.balue;

3.7.2 标量子查询

SQL允许子查询出现在返回单个值的表达式能够出现的任何地方，只要该子查询只返回包含单个数学的单个元组；这样的子查询称为标量子查询(scalar subquery)。

3.8 数据库的修改

3.8.1 删除

删除与查询类似，我们只能删除整个元组，不能删除某些属性上的值

delete from r

where P;

3.8.1.1 插入

insert into student

​ values (‘3003’,‘Green’,‘Finance’,null)

3.8.1.2 更新

undate 语句

undate instructor

set salary=salary*1.05s

第四章 中级SQL

4.1 连接表达式

4.1.1 连接条件

前面介绍了join…using子句

SQL还支持另外一种形式的连接。

on条件允许在参与连接的关系上设置统一的谓词。该谓词的写法与where子句谓词类似。

select *

from student join takes on student.ID =takes.ID;

4.1.2 外连接

外连接（outer join ）运算与我们已经学过的连接运算类似，但通过在结果中创建包含空值元组的方式，保留了那些在连接中丢失的元组。

实际上有三种形式的外连接：

• 左外连接（left outer join）只保留出现在左外连接运算之前（左边）的关系中的元组。
• 右外连接（right outer join）只保留出现在右外连接运算之前（右边）的关系中的元组。
• 全外连接（full outer join）保留出现在两个关系中的元组。

为了与外连接运算区分，前面我们学习的称为内连接。

on子句可以和外连接一起使用。on和where在外连接中的表现时不同的。on条件是外连接声明的一部分，但where不是。

outer join 的执行过程分为4步:

1、先对两个表执行交叉连接(笛卡尔积)

2、应用on筛选器

3、添加外部行

4、应用where筛选器

4.2 视图

在前面的例子中，我们一直都在逻辑模型层操作。

4.2.1 视图定义

我们在SQL中用create view命令定义视图。为了定义视图，我们必须给视图一个名称，并且必须提供计算视图的查询。

格式：

create view v as

为了创建一个视图，列出Physics 系在2009年秋季学期所开设的所有课程段，以及每个课程段在哪栋建筑的哪个房间授课的信息，我们可以写出：

create view physics_fall_2019 as

​ select course.course_id,sec_id ,building,room_number

​ from course,section

​ where course.course_id =section.course_id

​ and course.dept_name=‘phy’

​ and section.semester=‘Fall’

​ and section.year=‘2009’

4.2.2 SQL查询中使用视图

一旦定义了一个视图，我们就可以用视图名指代该视图生成的虚关系。

使用视图physics_fall_2009，我们可以这样查询

select cource_id

from physics_fall_2009

where building = ‘watson’

视图的属性名可以按下列方式显式指定：

create view department_total_salary(dept_name,total_salary) as

​ select dept_name,sum(salary)

​ from instructor

​ group by dept_name;

4.2.3 物化视图

特定数据库系统允许存储视图关系，但是它们保证：如果用于定义视图的实际关系改变，视图也跟着修改。这样的视图被称为物化视图（materialized view)。

4.3 事务

事务（transaction）由查询和（或）更新语句的序列组成。SQL标准规定当一条SQL语句被执行，就隐式地开始了一个事务。下列SQL语句之一会结束一个事务：

• **Commit work:**提交当前事务，也就是将该事务所做的更新在数据库中持久保存。在事务被提交后，一个新的事务自动开始。
• Rollback work：回退当前事务，即撤销改事务中所有SQL语句对数据库的更新。这样，数据库就恢复到执行该事务第一条语句之前的状态。

4.4 完整性约束

完整性约束保证授权用户对数据库的修改不会破坏数据的一致性。因此，完整性约束防止的是对数据的意外破坏。

完整性约束的例子有：

• 教师姓名不能为null
• 任意两位教师不能有相同的教师标识

完整性约束常被看作是数据库模式设计过程的一部分。也可以通过使用alter table table-name add constaint 命令施加到已有关系上。

create table 命令还可以包括完整性约束语句。

除了主码约束之外，还有其他命令。

比如：

• not null
• unique
• check(<谓词>)

check (semester in (’Fall’, ’Winter’, ’Spring’, ’Summer’))

• 初始值

tot_cred numeric(3,0) default 0

4.4.1 参照完整性

我们常常希望保证在一个关系上给定属性集上的取值中出现。这种情况称为参照完整性（referential integrity）。

一般地，令关系r1和r2的属性集分别为R1和R2，主码分别为K1和K2。如果要求对r2中任意元组t2，均存在r1中元组使得t1.K1=t2.$\alpha$，我们称R2的子集$\alpha$为参照关系r1中K1的外码。

这种要求称为参照完整性约束（referential-intergrity constraint)或子集依赖（subset dependency）。

dept_name varchar(20) references department

当违反参照完整性约束时，通常的处理是拒绝执行导致完整性破坏的操作（即镜像更新操作的事务被回滚）。

但是也可在foreign key子句中指明：如果被参照关系上的删除或更新动作违反了约束，那么系统必须采取一些步骤通过修改参照关系中的元组来恢复完整性约束，而不是拒绝这样的动作。

create table course

(…

foreign key (dept_name) reference department

​ on delete cascade

​ on update cascade,

…);

on delete cascade 子句 ：如果删除department 中的元组导致了此参照完整性约束被违反，则删除并不被系统拒绝，而是对course关系作“级联”删除，即删除参照了被删除系的元组。

on update cascade 子句：若果更新被参照字段时违反了约束，则更新操作并不被系统拒绝，而是将course中参照的元组的dept_name字段也改为新值。

4.4.2 事务中对完整性约束的违反

事务可能包括几个步骤，在某一步之后完整性约束也许会暂时被违反，但是后面的某一步也许就会消除这个违反。例如，假设我们有一个主码name的person关系，还有一个属性时spouse，并且spouse是在person上的一个外码。也就是说，约束要求spouse属性必须包含在person表里出现的名字。

为了处理“插入第一个元组违反外码约束，但是插入第二个元组后，外码约束又满足”的情况，SQL标准允许将initially deferred 子句加入到约束声明中；这样完整性约束不是在事务的中间步骤上检查，而是在事务结束的时候检查。

create table person

(name char(15) primary key,

spouse char(15),

foreign key spouse references person (name) initially deferred)

4.4.3 断言

断言(assertion)就是一个谓词，它表达了我们希望数据库总能满足的一个条件。域约束和参考完整性约束是断言的特殊形式。

格式：

create assertion < assertion-name > check < predicate >;

4.5 SQL的数据类型与模式

4.5.1 SQL中的日期和时间类型

SQL除了前面介绍的基本数据类型以外，SQL标准还支持与日期和时间相关的几种数据类型：

• date: 日历日期，包括年（四位）、月和日。

• time: 一天中的时间，包括小时、分和秒。可以用变量time(p)来表示秒的小数点后的数字位数（这里默认值为0）。通过指定time with timezone，还可以

• timestamp：date 和time的组合。可以用变量timestamp(p)来表示秒的小数点后的数字位数（这里默认值为6）。如果指定with timezone，则时区信息也会被存储。

4.5.2 大对象类型

SQL提供字符数据的大对象数据类（clob）和二进制数据的大对象数据类型（blob）。

4.5.3 用户定义的类型

SQL支持两种形式的用户定义数据类型。第一种称为独特类型（distinct type)。另一种称为结构化数据类型（structured data type）。

独特类型：

使用**create type **子句来定义新类型

create type Dollars as numeric (12,2) final

create type RMB **as numeric **(12,2) final

也可以使用cast命令强制转换

cast (department.budget to numeric(12, 2))

SQL提供了drop type和alter type 子句来删除或修改以前创建过的类型。

SQL还有一个相似但稍有不同的概念：域（domain），它可以在基本类型上世家完整性约束。例如

create domain DDollars as numeric(12,2) not null

DDollars域可以用作属性类型。然而类型和域直接有两个重大的差别：

1.在域上可以声明约束，例如not null，也可以为域类型变量定义默认值，然而在用户定义类型上不能声明约束或默认值。设计用户定义类型不仅是用它来指定属性类型，而且还将它用在不能施加约束的地方对SQL进行过程扩展。

2.域并不是强类型的。因此一个域类型的值可以被赋给另一个域类型，只要他们的基本类型是相容的。

4.6 授权

我们可能会给一个用户在数据库的某些部分授予几种形式的权限。对数据的授权包括：

• 授权读取数据
• 授权插入新数据
• 授权更新数据
• 授权删除数据

我们使用grant语句来授予权限

grant < 权限列表 >

on < 关系吗或视图名>

to < 用户/角色列表>

4.6.1 角色

角色：一组用户

在SQL创建角色如下所示：

create role instructor

4.6.2 权限的转移

默认方式下，被授予权限的用户/角色无权把得到的权限再授予给另外的用户/角色。如果我们在授权时允许接受者把得到的权限再传递给其他用户，我们可以在响应的grant命令后面附加with grant option子句。

grant select on department to Amit with grant option

第五章 高级SQL

5.1 使用程序设计语言访问数据库

可以通过以下两种方法从通用编程语言中访问SQL：

• 动态SQL

通用程序设计语言可以通过函数（对于过程式语言）或者方法（对于面对对象的语言）来连接数据库服务器并与之交互。利用动态SQL可以在运行时以字符串形式构建SQL查询，提交查询，然后把结果存入程序变量中，每次一个元组。动态SQL的SQL组件允许程序在运行时构建和提交SQL查询。

例如java语言的应用程序接口JDBC和另一种：ODBC

• 嵌入式SQL

如动态SQL类似，嵌入式SQL提供了另外一种使程序与数据库服务器交互的手段。然而，嵌入式SQL语句必须在编译时全部确定，并交给预处理器。预处理程序提交SQL语句到数据库系统进行预编译和优化，然后它把应用程序中的SQL语句替换成相应的代码和函数，最后调用程序语言的编译器进行编译。

第六章 形式化关系查询语言

6.1 关系代数

关系代数是一种过程化查询语言。它包括一个运算的集合，这些运算以一个或两个关系为输入，产生一个新的关系作为结果。

6.1.1 基本运算

（1）选择运算

（2）投影运算

即选出某几列

（3）关系运算的组合

（4）并运算

（5）集合差运算

（6）笛卡尔积运算

（7）更名运算

6.1.2 附加的关系代数运算

（1）集合交运算

（2）自然连接运算

（3）赋值运算

赋值用←表示

temp1← R $\times$ S

（4）外连接运算

6.1.3 扩展的关系代数运算

（1）广义投影

广义投影运算形式为：

$\prod_{F1,F2…,Fn}(E)$

其中E是任意关系代数表达式，而F1，F2，…，Fn中的每一个都是涉及常量以及E的模式中属性的算术表达式。最基本的情况下算术表达式可以仅仅是一个属性或常量。

（2）聚集

聚集函数像有sum、count等。

$\mathcal{G}_{sum(salary)}(instructor)$

关系代数运算$\mathcal{G}$表示聚集将被应用，它的下标说明采用的聚集运算。

有时，在计算聚集函数前我们必须去除重复值。如果我们想去除重复，我们仍然使用前面的函数名，但用连字符将"distinct"附加在函数名后（如count-distinct）

有时候我们希望对一组元组集合而不是单个元组集合执行聚集函数。

比如考虑查询“求出每个系的平均工资”。

${dept_name}\mathcal{G}{sum(salary)}(instructor)$

聚集运算（aggregation operation）通常的形式如下：

${G_1,G2,…,G_n}\mathcal{G}{F_1(A_1),F_2(A_2),…,F_n{A_n}}{E}$

其中E是任意关系代数表达式，$G_1,G_2,…,G_n$是用于分组的一系列属性；每个$F_i$是一个聚集函数，每个

$F_i$是一个聚集函数，每个$A_i$是一个属性名。运算的含义如下，表达式E的结果中元组以如下方式被分为若干组：

1.同一组中所有元组在$G_1,G2,…,G_n$上的值相同。

2.不同组中元组在$G_1,G2,…,G_n$上的值不同。

第七章 待写

待写

第八章 关系数据库设计

8.1 函数依赖

函数的定义：$y=f(x)\ \ \ \ \ \ \ \ x\in X,y\in Y$

• $X→Y$

• 对于任意的x1,x2都满足x1=x2→f(x1)=f(x2)

函数依赖的定义：

设R是一个关系模式，$\alpha \subseteq R$,$\beta \subseteq R$

函数依赖：$\alpha \in \beta成立

当且仅当任意R的实例r中的任意二行t1和t2都满足：

t1[$\alpha$]=t2[$\alpha$]→t2[$\beta$]=t2[$\beta$]

称为：$\alpha$确定$\beta$，$\beta$函数依赖于$\alpha$,$\alpha$可推出$\beta$

排除函数依赖：

只需要一组反例，满足：存在s,t$\in$r,s[X]=t[X],但s[Y]$\neq$t[Y]

确认函数依赖:

对于R的任意一个可能的实例r，都满足：不存在s,t$\in$r,s[X]=t[X],但s[Y]$\neq$t[Y]

**函数依赖集：**若干个函数依赖组成的集合

如果一个关系r没有违反函依赖集F，那么称关系r满足函数依赖集F（r satisfies F）

如果一个关系R的所有关系都满足函数依赖集F，那么称函数依赖集F在关系模式R上成立（F holds on R）

8.2 属性集的闭包

定义：根据一个给定的函数依赖集F，由属性集$\alpha$可退出的所有属性组成的集合，称为$\alpha$的闭包，记作$\alpha^+$

计算$\alpha^+$的算法:

result:=$\alpha$

repeat

​ 检查F中的每个函数依赖$\beta\in \gamma$

​ 若$\beta \subseteq result$,则把$\gamma$属性都加入result

until

​ 直到不能再添加属性到result

属性集闭包的用途：

（1）判断一个属性集是否超码

• 要判断$\alpha$是不是R的超码，只要看$\alpha^+$是不是包含R

（2）判断一个函数依赖是否成立

• 要判断$\alpha \in \beta$是不是成立，只要看$\beta \subseteq \alpha^+$是不是成立

（3）简洁的计算函数依赖集的闭包

8.2.1 计算函数依赖集的闭包

方法1：用Armstrong公理

• 自反律：若$\beta \subseteq \alpha$那么$\alpha →\beta$

• 增广律：若$\alpha → \beta$，那么$\gamma\alpha → \gamma\beta$

• 传递律：若$\alpha → \beta$，$\beta → \gamma$，那么$\alpha → \gamma$

• 合并律：若$\alpha → \beta$，$\alpha → \gamma$，那么$\alpha → \beta\gamma$

• 分解律：若$\alpha → \beta\gamma$那么$\alpha→\beta$并且$\alpha → \gamma$

• 伪传递律：若$\alpha → \beta$并且$\gamma\beta → \delta$，那么$\gamma\alpha → \gamma\beta$

方法二：利用属性集的闭包（穷举法）

• 对关系模式R的每一个子集S进行以下操作

为$S^+$的每一个子集T，输出函数依赖$S→ T$

8.2.2 函数依赖集的等价性

设F1和F2是两个函数依赖集，若由F1可以推出F2的所有函数依赖，由F2也可以推出F1的所有函数依赖，则说F1和F2是等价的。

• 设F1和F2是两个函数依赖集，以下两个命题是等价
  • F1、F2有相同的闭包（$F1^+=F2^+$
  • F1和F2是等价的

8.2.3 Canonical(最小覆盖/规范覆盖)

• 函数依赖集中某些函数依赖是多余的。

例如，{A→B，B→C，A→C}可以简化为{A→B，B→C}

• 函数依赖中某些属性是多余的。

例如，{A→B，B→C，AC→D}可以简化为{A→B，B→C，A→D}

把所有的多余属性和多余的函数依赖删掉，得到最小的函数依赖集合，称为F的最小覆盖或规范覆盖

8.2.3.1 规范覆盖的定义：

函数依赖集F的最小覆盖FC满足：

• F和FC是等价的
• FC的所有函数依赖都没有多余属性
• FC的每个函数依赖的决定部分（左氏）都是唯一的

X→Y

8.2.3.2 多余的属性

考虑函数依赖集F中的某个函数依赖$\alpha→\beta$

左式属性$A\in \alpha$是多余属性，如果函数依赖集F在逻辑上蕴含：$(F-{\alpha→\beta })\cup ({\alpha -A }→\beta)$

右式属性$B\in \alpha$是多余属性，如果函数依赖集F在逻辑上蕴含：$(F-{\alpha→\beta })\cup (\alpha→ {\beta -B })$

8.2.3.3 计算最小覆盖

函数依赖集F的最小覆盖FC的算法：

FC=F

repeat

​ 合并FC中有相同决定部分的函数依赖，即把$\alpha 1→\beta 1$和$\alpha 1→\beta 2$合并为$\alpha 1→\beta 1\beta 2$

​ 把FC中的多余属性删掉

until FC不再发生变化

---

(PPT44）