tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 工学 >>

数据库原理


第一章
本章要求: 1、了解数据管理的发展过程

绪 论

2、掌握数据库系统的基本概念和主要特点
3、掌握数据库系统的三级模式结构和数据库系统的组成 4、掌握实体、记录等有关概念和三种数据模型 本章内容: §1 数据库系统概述
请选择内容

§2
§3

数据

模型
DBS的结构 返回
1

§4 数据库系统的组成
2015/9/23 数据库系统

第一章

绪 论

§1 数据库系统概述
一、基本概念

1、数据:描述事务的符号记录。可用文字、图形等多种形式表
示,经数字化处理后可存入计算机。 2、数据库(DB):按一定的数据模型组织、描述和存储在计算

机内的、有组织的、可共享的数据集合。
3、数据库管理系统(DBMS):位于用户和操作系统之间的一 层数据管理软件。主要功能包括:

数据定义功能:DBMS提供DDL,用户通过它定义数据对象。
数据操纵功能:DBMS提供DML,用户通过它实现对数据库的 查询、插入、删除和修改等操作。
2015/9/23 数据库系统 2

第一章

绪 论

数据库的运行管理:DBMS对数据库的建立、运行和维护进 行统一管理、统一控制,以保证数据的安全性、完整性、并发 控制及故障恢复。 数据库的建立和维护功能:数据库初始数据的输入、转换,

数据库的转储、恢复、重新组织及性能监视与分析等。
4、数据库系统(DBS):计算机中引入数据库后的系统,包括 数据库DB

数据库管理系统DBMS
应用系统 数据库管理员DBA和用户
2015/9/23 数据库系统 3

第一章
二、数据管理与数据处理 1、数据管理:

绪 论

对数据收集、整理、组织、存储、维护、检索、传送等 对象 操作

目标:在妥当的时候以妥当的形式给妥当的人提供妥当的数据。 2、数据处理:对数据进行加工、计算、提炼, 从而产生新的有效数据的过程

数据
2015/9/23

信息
数据库系统 4

第一章
3、管理与处理的关系: 管理是处理的基础

绪 论

处理为管理服务
源数据

管理和处理又可看 成一个问题的两个阶 段,故可以统一起来, 其中心是管理

数据管理

数据处理

……

数据处理

新数据

新数据

2015/9/23

数据库系统

5

第一章

绪 论

三、数据管理的发展阶段 ? 人工管理阶段(50年代中期以前) ? ? 文件系统阶段(50年代中期至60年代后期) 数据库系统阶段(60年代后期以后)

2015/9/23

数据库系统

6

第一章

绪 论

1、人工管理阶段(程序员管理阶段) ? 数据不保存 特点:

? 程序员负责数据管理的一切工作
? 数据和程序一一对应,没有独立性和共享性 数据和程序的关系: 应用程序1 应用程序2 …… 应用程序n
2015/9/23

数据1

数据2

数据n
数据库系统 7

第一章

绪 论

2、文件系统阶段 硬件:有了大容量直接存储外存设备,如磁盘、磁鼓等 基 软件:有了专门的数据管理软件--文件系统 础 处理方式:有批处理、联机实时处理等

{

又可分为两个阶段 (1)60年代初期出现了初等的文件系统 主要特点:? 组织方式:顺序文件 ? 数据结构:物理结构 = 逻辑结构 ? 软件功能:仅有简单I/O操作

(2 )60年代中期出现了成熟的文件系统 ? 组织方式:顺序和随机存取并用 主要特点: ? 数据结构:物理结构和逻辑结构有了简单的变换 ? 软件功能:软件系统提供了存取方法
2015/9/23 数据库系统 8

第一章
数据与程序的关系:
应用程序1

绪 论
数据1 数据2 ……

应用程序2 ……
应用程序n

存取方法

操作系统负责

数据n

三个主要缺点: ? 数据高度冗余:数据基本上还是面向应用或特定用户的。

? 数据共享困难:文件基本上是私有的,只能提供很弱的文
件级共享 ? 数据和程序缺乏独立性:只有一定的物理独立性,

完全没有逻辑独立性。
2015/9/23 数据库系统 9

第一章
3、数据库系统阶段

绪 论

文件系统不能适应大数据量、多应用共享数据的根本原因: 数据没有集中管理 数据库方法的基本出发点: 把数据统一管理、控制,共享使用 数据与程序的关系:
应用程序1 应用程序2 DBMS 数 据 库

应用程序n
2015/9/23 数据库系统 10

……

第一章

绪 论

(1) 数据高度结构化集成,面向全组织 (2) 数据共享性好。可为多个不同的用户共同使用 (3) 数据冗余少,易扩充 (4) 数据和程序的独立性高 物理独立性: 存储结构变,逻辑结构可以不变,从 主 而应用程序也不必改变。 要 逻辑独立性: 总体逻辑结构变,局部逻辑结构可以 不变,从而应用程序也不必改变。 优 好处:简化应用程序的编写和维护 点 (5)数据控制统一 安全性控制:防止泄密和破坏 完整性控制:正确、有效、相容 并发控制: 多用户并发操作的协调控制 故障恢复:发生故障时,将数据库恢复到正确状态
2015/9/23 数据库系统 11

第一章
4、各个阶段的比较: 从四个方面 人工管理

绪 论

文件系统

数据库系统 系统集中管理 面向系统 充分共享 较高的独立性

谁管理数据 程序员 操作系统提供存取方法 面向谁 共享性 数据独立性 特定应用 不能 没有 基本上是特定用户 共享很弱 一定的物理独立性

文件系统和数据库系统的本质区别: 内部:数据库的数据是结构化的,有联系的
文件系统的各记录无联系 外部:数据库系统是共享的 文件系统基本上是面向特定用户的
2015/9/23 数据库系统 12

第一章 §2

绪 论 数据模型

数据处理的抽象过程(涉及三个领域) 抽象 转换 现实世界 ===? 信息世界 =====? 机器世界(数据世界)
? ? 建立概念模型 建立数据模型 (便于用户和DB设计人员交流) (便于机器实现)

一、概念模型(信息模型)

把现实世界中的客观对象抽象成的某种信息结构,主要用
于数据库设计。 ? 独立于具体的计算机系统

?独立于具体的DBMS支持的数据模型
2015/9/23 数据库系统 13

第一章
1、实体与记录 信 息 世 界

绪 论

实体:客观存在并可相互区分的事物。
实体集:性质相同的同类实体的集合。 属性: 实体具有的某一特性。 实体标识符:能将一个实体与其它实体区分开来的一个 或一组属性。 记录 ?? 实体 (抽象表示) 文件 ?? 实体集 字段或数据项 ?? 属性 关键字 ?? 实体标识符。唯一地标识一个记录。 又称码、键。

数 据 世 界

2015/9/23

数据库系统

14

第一章
2、型与值

绪 论

在DBS中,每一个对象广义上讲都有型与值之分: 型是对象的结构或特性描述, 值是一个具体的对象实例。 类似于程序设计语言中数据类型与数据值的概念。 (1)实体型:对实体固有特性或结构的描述。 用实体名及其属性名集合来抽象和刻画。 如 汽车(车牌号,车型,车主) 实体值:实体型的一个实例,即一个具体的实体。 如 (豫A00001,丰田,张三) (2) 记录型:记录格式。 记录值:一个具体的记录。
2015/9/23 数据库系统 15

第一章
如: 车牌号 豫A00001 名称 丰田

绪 论
车主 张三

(3)几点说明 ? 区分型与值的实质 ? DBS中讨论的重点是型 ? 通常只说实体、记录,含义根据上下文自明 3、实体间的联系 ? 实体内部的联系(属性间的联系): 反映在数据上就是记录内部数据项间的联系

? 实体之间的联系:
反映在数据上就是记录之间的联系
2015/9/23 数据库系统 16

第一章
实体之间的联系可归结为三类:

绪 论

(1) 1对1联系(1 :1):两个实体



集中的每一个实体至多和另一个实体集
中的一个实体有联系。

国家 —— 总统 学员队—— 队长

(2) 1对多联系(1 :n):若实体集A 中的每个实体与实体集B中0个或多个实 体有联系,而B中每个实体至多与A中的 如 国家 —— 部长 学员队—— 学员 一个实体有联系,则称从A到B为1对多 的联系。 (3) 多对多联系(m :n):两个实 体集中的每一个实体都和另一个实体集 如 学员—— 课程

中0个或多个实体有联系。
2015/9/23 数据库系统 17

第一章

绪 论

DBS的核心问题之一: 如何表示和处理实体及实体间的联系。 4、概念模型的表示方法之一: 实体—联系方法(Entity-Relationship Approach) 用E—R图( Entity-Relationship Diagram)描述: ? 实体型:用长方形表示 属性名 实体名 联系 :用菱形表示 1 属性 :用椭圆形表示 ? 框内写上相应的名称 属性名 联系名 ? 用无向边连接: n 实体与其属性 属性名 实体名 联系与其属性 联系与有关实体,并标上联系类型
2015/9/23 数据库系统 18

第一章
说明:

绪 论

? 联系也必须命名
? 多个实体之间也可以有联系 单个实体之间也可以有联系 ? 联系也可以有属性 供应商 p m 项 目 供应量
2015/9/23 数据库系统

学员 1 领导 n

供应

n 零 件

19

第一章
例:某工厂物资管理E--R图(P20)
姓名 供应商号 电话号码 帐号 面 积 仓库号

绪 论

地址 供应商 m

电话号 1

职工号 n 1

姓名

年龄 职称

仓 库 m 库存 p n

工作

职 工 n 领导

供应量 n

供应

库存量

项 目

零 件
零件号 规格 名称
数据库系统 20

单价

描述

项目号

预算

开工日期

2015/9/23

第一章

绪 论

二、数据模型 是对现实世界进行抽象的工具,它按计算机系统的观点对 数据建模,用于提供数据库系统中信息表示和操作手段的形式 框架,主要用于DBMS的实现,是数据库系统的核心和基础。
1、常用的数据模型 层次模型 网状模型 称作非关系模型,是下 列基本层次联系的集合 Ri Ri,Rj是实体型(记录型) Lij是从Ri到Rj的1:1或1:n联系
数据库系统 21

关系模型

面向对象模型

}
Lij
Rj

2015/9/23

第一章
2、数据模型 的 三要素 形式化描述数据、 数据之间的联系 以及数据操作 和有关的语义 约束规则的方法

绪 论

数据结构 (静态)

数据操作(动态) 完整性约束

如何表示 如 何 实 现 如何保证数据的 实体及联系 查、增、删、改 约束条件得到满足 (难点是表示联系) 根据现实世界实体间联系的特征 用四种不同的方法进行抽象 层次模型 (因此,是按照数据结构 网状模型 的类型来命名数据模型) 关系模型 面向对象模型
2015/9/23 数据库系统 22

第一章

绪 论

3、层次模型 根据一个单位的组织结构直观地得出 学院 部 系 教研室 教员 处 学员队 学员

方框表示一个实体型
(结点) 线表示联系 (边)

(1)定义:用树形结构来表示实体以及实体间联系的模型。 其特征是:(a)有且仅有一个结点无双亲(根结点);

(b)其它结点有且仅有一个双亲。
2015/9/23 数据库系统 23

第一章

绪 论

(2)说明: (a)树中实体间联系只能是从父到子的1:1或1:n联系, 对m:n联系,须使用辅助手段转换成多个1:n联系, 但不易掌握 (b)简单直观,结构清晰,运行效率高,但编程复杂 4、网状模型 (1)定义:用图结构来表示实体以及实体间联系的模型。 其特征是:任一结点都可以无双亲或有一个以上的双亲。 学校


教员 课程
2015/9/23 数据库系统

班级 学生
24

第一章

绪 论

(2)优:可表示m:n的联系,运行效率高 缺:过于复杂,实现困难 (3)说明 (a)即使对网状模型,具体在计算机上实现时,m:n 的

联系仍需分解成若干个1:n的联系。(因此,网状模型的图
结构实质上是有向图),如 学 生 m 选课 n 课 程
2015/9/23

学号 姓名 年龄 性别 学生成绩单

课程号 名称 课程成绩单

学号 课程号 得分
数据库系统 25

第一章

绪 论
工 人

(b)网状模型中允许两结点间有多条边,
层次模型则不允许 5、关系模型

使用

保养

设 备

层次、网状模型基本上是面向专业人员的,使用极不方便

问题:寻找一种能面向一般用户的数据模型?
(1)定义:用二维表(关系)来描述实体及实体间联系的模 型。 (2)示例 供应商
2015/9/23

m
数据库系统

供应

n

零 件
26

第一章
供应商S

绪 论
零件P P# P1 P2 …

S#
S1 S2 …

SNAME SADDR
张三 李四 … 北京 郑州 …

PNAME PRICE
电机 螺丝 … 2000 2 …

(联系)供应SP S# S1 S1 …
2015/9/23

P# P1 P3 …

QTY 200 22 …

关系:对应一张表, 每表起一个名称即关系名 元组:表中的一行 属性:表中一列, 每列起一个名称即属性名 主码:唯一确定一个元组的属 性组 域:属性的取值范围
数据库系统 27

第一章

绪 论

(3)关系模式:对关系的描述,一般表示为: 关系名(属性1,属性2,…,属性n)
(4)优点: ? 无论实体还是实体之间的联系都用统一的数据结构 (二维表、关系)来表示,可方便地表示m:n联系,因此概 念简单,用户易懂易用 m n 如: 学生 选修 课程 可表示为: 学生(学号,姓名,性别,系和年级) 课程(课程号,课程名,学分) 选修(学号,课程号,成绩) ? 表格中行、列次序无关 ? 有坚实的理论基础(关系理论)
2015/9/23 数据库系统 28

第一章

绪 论

? 存取路径对用户透明,用户只需指出“做什么”,不 需说明“怎么做”,因此数据独立性更高 缺点:由于存取路径对用户透明,查询效率不够高,必 须对查询请求进行优化。 说明: 关系必须规范化,关系的每个分量必须是一个不可分的 数据项,不允许表中套表。规范化理论将在后续章节讲解。 (5)关系模型与非关系模型的比较 关系模型 统一 实体及实体间联系 采用的数据结构 均为关系 操作方式 存取路径
2015/9/23

非关系模型 不统一

一次一集合 一次一记录 对用户透明 对用户不透明
数据库系统 29

第一章 §3

绪 论 DBS的结构

三级模式(外模式、模式、内模式) 两级映象(外模式/模式,模式/内模式映象) 一、DBS的三级模式结构 1、模式(Schema):又称逻辑模式。DB的全局逻辑结构。 说明 ① 模式只涉及到型的描述,不涉及具体的值(实例),反映的是 数据的结构及其联系 ② 模式不涉及物理存储细节和硬件环境,也与应用程序无关 ③ 模式承上启下,是DB设计的关键 ④ DBS提供模式DDL(Data Definition Language)来定义模式 (描述DB结构)
2015/9/23 数据库系统 30

即DB中全体数据的逻辑结构和特征的描述。

第一章

绪 论

⑤ 模式定义的任务 (概念模型 ? 模式) ? 定义全局逻辑结构(构成记录的属性名、类型、宽度等) ? 定义有关的安全性、完整性要求 ? 定义记录间的联系 ⑥ 一个数据库只有一个模式 2 、外模式:又称子模式或用户模式。DB的局部逻辑结构。 即与某一应用有关的数据的一个逻辑表示。 说明: ? 外模式是某个用户的数据视图, 模式是所有用户的公共数据视图; ? 一个DB只能有一个模式,但可以有多个外模式; ? 外模式通常是模式的子集,但可以在结构、类型、长度等 方面有差异; ? DBS提供外模式DDL。
2015/9/23 数据库系统 31

第一章

绪 论

3、内模式:又称存储模式。数据的物理结构和存储方式的描述。 即DB中数据的内部表示方式。
说明: ? 一个数据库只有一个内模式 ? DBS提供内模式DDL; 记录存储格式, ?内模式定义的任务 索引组织方式, 数据是否压缩、是否加密等。 4、两级映象及其作用 (1)外模式/模式映象:定义外模式和模式间的对应关系。对 应同一个模式可以有多个外模式,对每个外模式都有一个外模 式/模式映象。 作用:模式变,可修改映象使外模式保持不变,从而应用程 序不必修改,保证了程序和数据的逻辑独立性。
2015/9/23 数据库系统 32

第一章

绪 论

(2)模式/内模式映象:定义DB全局逻辑结构和存储结构间的 对应关系。一个数据库只有一个模式,也只有一个内模式,因此 模式/内模式的映象也是唯一的。 作用:存储结构变,可修改映象使逻辑结构(模式)保持不变, 从而应用程序不必修改,保证了数据与程序的物理独立性。

2015/9/23

数据库系统

33

第一章

绪 论

§4 数据库系统的组成 一、数据库系统(DataBase System,DBS)的组成 广义上讲,DBS就是计算机系统中引进数据库后的构成。 有下面四部分: 1、数据库:一个或多个数据库 数据库的四要素:用户数据、元数据、索引和应用元数据 2、 软件 ? 操作系统;支持DBMS的运行 ? 数据库管理系统 DBMS(DataBase Management System): 操纵和管理数据库的大型软件系统,是数据库系统的核心 ? 数据库应用开发工具等辅助软件 ? 具有数据库接口的高级语言与编译系统,如C、C++等 ? 某个数据库应用系统
2015/9/23 数据库系统 34

第一章
3、人员 用户 应用程序员 (使用) (开发)

绪 论
数据库管理员DBA (管理)

DBA(Data Base dministrator)的职责:
① 决定数据库的内容和逻辑结构、存储结构 ② 确定数据的安全性要求和完整性约束条件

③ 监控数据库的使用和运行,维护数据库
④ 决定数据库的存储结构和存储策略 ⑤ 负责数据库的改进和重组重构

4、硬件 计算机及有关设备,要求有足够大的内、外存储容量及较 高的处理速度。
2015/9/23 数据库系统 35

第一章
数据库系统图示:
用户1 应用 程序员 应用程序1 用户2

绪 论
??? ???

用户n

应用程序m

辅助软件 DBMS

操作系统

DBA 负责 数据库
36

数据库
2015/9/23

???
数据库系统

第一章

绪 论

二、数据库系统研究的对象 如何高效巧妙地进行数据管理,而又花费最少

三个主要研究领域:
DBMS及其辅助软件 数据库设计

如:占用空间少 查询快 维护方便等

数据库理论 作业:3,5,7,12,13,20,22

2015/9/23

数据库系统

37

第二章

关系数据库

本章要求:
1、掌握关系、关系模式、关系数据库等基本概念 2、掌握关系的三类完整性的含义 3、掌握关系代数运算 本章内容: §1 关系模型的基本概念 §2 RDBS的数据操纵语言:关系代数 §3 RDBS的数据操纵语言:关系演算语言 返回
2015/9/23 数据库系统数据库系统 38

请选择内容

第二章

关系数据库

§1 关系模型的基本概念 层次、网状数据库是面向专业人员的,使用很不方便 。程序员必须经过良好的培训,对所使用的系统有深入的

了解才能用好系统。
关系数据库就是要解决这一问题,使它成为面向用户 的系统。 关系数据库是应用数学方法来处理数据的。它具有结 构简单、理论基础坚实、数据独立性高以及提供非过程性 语言等优点。
2015/9/23 数据库系统数据库系统 39

第二章 一、关系的数学定义

关系数据库

1、域(Domain): 值的集合。它们具有相同的数据类型 ,语义上通常指某一对象的取值范围。 例如:全体整数, 0到100之间的整数, 长度不超过10的字符串集合 2、笛卡尔积(Cartesian Product):设D1、D2、…、Dn 是n个域, 则它们的笛卡尔积为 D1?D2?…?Dn={(d1,d2,…,dn) | di ? Di, i=1,2,…,n}

其中每一个元素称为一个n元组(n-tuple), 简称元组;
元组中的每个值di称为一个分量(component).
2015/9/23 数据库系统数据库系统 40

第二章

关系数据库 张三 张三 张三 张三 李四 李四 李四 李四 数学 数学 语文 语文 数学 数学 语文 语文 优 良 优 良 优 良 优 良

笛卡尔积可以写成一个二维表 例如: 设 D1={张三,李四}, D2={数学,语文}, D3={优,良} 则D1×D2×D3可用二维表表示为: 3、关系(Relation) 笛卡尔积D1?D2?…?Dn的子集合, 记作 R(D1,D2,…,Dn) 关系名
2015/9/23 数据库系统数据库系统

n为关系的目或度

41

第二章

关系数据库

4、说明 ? 关系是一个二维表。 ? 每行对应一个元组。 ? 每列可起一个名字,称为属性。属性的取值范围为一个 域,元组中的一个属性值是一个分量。 5、关系的性质 ? 列是同质的,即每列中的数据必须来自同一个域 ? 每一列必须是不可再分的数据项(不允许表中套表,即 满足第一范式) ? 不能有相同的行

? 行、列次序无关
2015/9/23 数据库系统数据库系统 42

第二章 二、关系模型

关系数据库

三部分:关系数据结构、关系操作集合、关系的完整性

(一)数据结构
1、单一的数据结构:关系(二维表) 不论是实体还是实体间的联系都用关系表示。 实体值 ? 关系的元组,在关系数据库中通常称为记录 属性值 ? 元组的分量,在关系数据库中通常称为字段 关键字(码):唯一标识一个元组的属性组 关键字可以有多个,统称候选关键字。在使用时,通 常选定一个作为主关键字。主关键字的诸属性称为主属

性,其它为非主属性。
2015/9/23 数据库系统数据库系统 43

第二章

关系数据库

2、关系模式:关系的描述。 包括关系名、诸属性名、属性向域的映象、属性间的依赖。 关系的型 属性的类型、长度等

一个元组为关系的一个值 表示: R(U,D,dom,F) 关系数据库模式:对关系数据库的描述,包括域 型

的定义及在域上定义的所有关系模式。
关系数据库:所有实体及实体间联系的关系的集 合。是某时刻所有关系模式对应的关系的集合。
2015/9/23 数据库系统数据库系统


44

第二章 3、关系的三种类型

关系数据库

基本关系:客观存在的基本表

查询表:由基本表按一定条件检索得到的结果
视图(View): 从一个或多个基本关系上导出的关系。它 不对应实际的存储数据,是一个虚关系,然而可永久存在。 相当于关系模型的外模式。 由于二维表的存储策略非常简单,关于数据库的物理 存储完全由DBMS自动完成。因此,在关系模型中不需要 与内模式相应的概念。

2015/9/23

数据库系统数据库系统

45

第二章 (二)关系操作

关系数据库

查询操作

1、种类:选择、投影、连接、除、并、交、差

增加、删除、修改
2、特点:

维护操作

? 集合操作,一次操作 一次一集合(关系型) 一次一记录(非关系型) 可存取多个元组 ? 非过程化语言:用户只需告诉做什么(What)

不需告诉怎么做(How)
? 数据定义、数据操纵、数据控制语言集成在一起

DDL
DML
2015/9/23

DCL:权限控制、完整性控制等
数据库系统数据库系统 46

第二章

关系数据库

(三)关系模型的三类完整性 1、实体完整性(Entity Integrity)

基本关系的所有主属性不能取空值
原因:基本关系 主关键字是 唯一性标识, 故不能空 实体集 实体必可区分 (标识符)

2、参照完整性(Referential Integrity),也叫引用完整性

若基本关系R含有与另一个基本关系S的主关键字相对
应的属性组F(F称为R的外键或外部码),则R中每个元 组在F上的值或为空值,或等于S中某个元组的主关键字值
2015/9/23



数据库系统数据库系统

47

EMP的外键 例: 职工关系 EMP(ENO,ENAME,DNO) ,只能取空 值或DEPT 部门关系 DEPT(DNO,DNAME) 中某关键字 DEPT的主键 的值 又如:学生关系(SNO,SNAME,AGE,SEX)
课程关系(CNO,CNAME)

第二章

关系数据库

选课关系(SNO,CNO,G)
3、用户定义的完整性 用户定义的某一属性值必须满足的语义要求。 一经定义,DBMS会自动检查,从而不必在应用程序 中作检查。 本节开头
2015/9/23

本章开头

下一节
48

数据库系统数据库系统

第二章

关系数据库

§2 RDBS的数据操纵语言:关系代数 关系代数的运算对象是关系,运算结果也为关系 。其运算按运算符的不同可分为两类。 一、传统的集合运算 1、并(Union): R ? S = { t | t∈R∨t∈S} 2、交(Intersection):R ? S = { t | t∈R∧t∈S} 3、差(Difference): R ? S = { t | t∈R∧t∈S} 4、笛卡尔积(广义): R ? S = { trts | tr ∈ R ∧ ts ∈ S}

2015/9/23

数据库系统数据库系统

49

第二章 二、专门的关系运算

关系数据库 从行的角度的运算

1、选择(Selection),又称限制(Restriction) ? (R):在关系R中选出满足条件F的诸元组形成一个新 F 关系。 条件表达式 2、投影(Projection)

从列的角度的运算

:在R中选出若干属性列组成一个新关系。 ?A (R) 属性组 投影后若有重复行,则自动保留一个

2015/9/23

数据库系统数据库系统

50

第二章 3、连接(Join) R
R中属性

关系数据库

S :从两个关系的笛卡尔积中选取属性间 A? B 满足条件A? B的元组。 连接是同时处理 多个关系的 重要运算

S中属性 比较运算符

说明: R ? ?
2015/9/23

S = ? (R?S) A? B A? B
S

当?为等号且A、B两属性相同时,称为自然连接
,记作 R 若仅有?为等号的条件, 自然连接将去掉重复属性 称为等值连接
数据库系统数据库系统 51

?

第二章 4、除(Division)

关系数据库

R(X,Y)? S(Y,Z):把R按X的值分组,若某一组 属性组 中属性组Y的值包含S在Y上投影的全部 元组,则该X的值作为
按S1分组

商关系的一个元组 例:求至少选修C1、 C3课程的学生号码 设一临时关系K:C# C1 C3 关系代数表达式 S1,… } ?S#,C# (SC)? K = {?
2015/9/23 数据库系统数据库系统

SC:S# C# G
S1 S1 S1 S1 S2 S2 S2 S3 S3 S3 S4 S4 C1 C2 C3 C5 C1 C2 C4 C2 C3 C4 C1 C3 A A A B B C C B C B B A

52

第二章 4、除(Division)

关系数据库

R(X,Y)? S(Y,Z):把R按X的值分组,若某一组 属性组 中属性组Y的值包含S在Y上投影的全部 元组,则该X的值作为 SC:S# C# G
S1 S1 S1 S1 S2 S2 S2 S3 S3 S3 S4 S4 C1 C2 C3 C5 C1 C2 C4 C2 C3 C4 C1 C3 A A A B B C C B C B B A

商关系的一个元组 例:求至少选修C1、 C3课程的学生号码 设一临时关系K:C# C1 C3 关系代数表达式
按S2分组

?S#,C# (SC)? K = { S1,… }
2015/9/23 数据库系统数据库系统

53

第二章 4、除(Division)

关系数据库

R(X,Y)? S(Y,Z):把R按X的值分组,若某一组 属性组 中属性组Y的值包含S在Y上投影的全部 元组,则该X的值作为 SC:S# C# G
S1 S1 S1 S1 S2 S2 S2 S3 S3 S3 S4 S4 C1 C2 C3 C5 C1 C2 C4 C2 C3 C4 C1 C3 A A A B B C C B C B B A

商关系的一个元组 例:求至少选修C1、 C3课程的学生号码 设一临时关系K:C# C1 C3 关系代数表达式

按S3分组

?S#,C# (SC)? K = { S1,… }
2015/9/23 数据库系统数据库系统

54

第二章 4、除(Division)

关系数据库

R(X,Y)? S(Y,Z):把R按X的值分组,若某一组 属性组 中属性组Y的值包含S在Y上投影的全部 元组,则该X的值作为
S1 S1 S1 S1 S2 S2 S2 S3 S3 按S4分组 S3 S4 S4

商关系的一个元组 例:求至少选修C1、 C3课程的学生号码 设一临时关系K:C# C1 C3 关系代数表达式 S4 S1, …}} ?S#,C# (SC)? K = { S1,
2015/9/23 数据库系统数据库系统

SC:S# C# G
C1 C2 C3 C5 C1 C2 C4 C2 C3 C4 C1 C3 A A A B B C C B C B B A

55

第二章

关系数据库 SC: S# C# G

三、关系代数运算举例
求至少选修这样一

S: S#

SN SD SA

S1 S2 课的直接先行课是C2 ? S3 S4 ? 先找出先行课为C2的课程号: S5 ? (C),记为PC S6 PC#=?C2‘

门课的学生姓名,这门

A B C D E F

CS 20 CS 21 MA 19 CI 19 MA 20 CS 22
CN PC# G H C1 I C2 J C2 K C4

? 找选修该类课程的学生学号: C: C# PC ? (SC) C1 S#,C# C2 记为PCS ? C3 ? 找出学生姓名: C4 C5 ? (S)) ? SN ( PCS S#,SN
2015/9/23

S1 S1 S1 S1 S2 S2 S2 S3 S3 S3 S4 S4 S5 S5 ? S5 S6 S6

C1 C2 C3 C5 C1 C2 C4 C2 C3 C4 C2 C5 C2 C3 C5 C1 C5

A A A B B C C B C B B D C B B A A
56

数据库系统数据库系统

第二章

关系数据库

最终的关系代数表达式:

(C ? SN (? PC#=?C2‘ )

? S#,C# (SC )

? S#,SN (S) )

PCS 说明: PC 用关系代数表示查询时,若查询涉及多个关系,需用连 接操作实现;若查询诸如“选修了全部课程”的学生、“使 用了全部零件”的工程等,需用除法操作实现。 作业:1,4,5,6 本节开头
2015/9/23

本章开头
数据库系统数据库系统

下一节
57

第二章

关系数据库

§3 RDBS的数据操纵语言:关系演算语言

关系演算:基于谓词演算 面向元组:谓词变量的获得值是关系中的元组 按谓词变量 (元组变量) 的特征划分 面向域:谓词变量的获得值是关系中某属性的值 一、元组关系演算
(域变量) t为元组变量

1、元组关系演算表达式: { t | ? (t) }

公式
2015/9/23 数据库系统数据库系统

运算的结果 还是一个关系
58

第二章 2、原子公式

关系数据库

? R (t): 表示t是关系R中的一个元组

? t[i]?u[j]: 表示t的第i个分量和u的第j个分量满足比较关系?
? t[i]?C 或 C? t[i] :含义同上,只不过C为常量

3、公式的递归定义 (1)每个原子公式是一个公式;

(2)设?1、?2是公式,则 ? ?1、 ?1 ? ?2、 ?1 ? ?2 也是公式;
(3)设?是公式,t是元组变量,则 ( ? t) ? 、 ( ?t) ? 也是公式; (4)除此之外没有其它形式的公式。
2015/9/23 数据库系统数据库系统 59

第二章

关系数据库

4、关系代数运算均可用关系演算来表示,反之亦然 见教材P71。 5、用关系演算来表达查询 例1,求年龄大于或等于20的学生: S20 = { t | S(t) ? t[4]?20 } 例2,求学生姓名及所在的系: S1={ t (2) | (? u )(S(u) ? t[1]=u[2] ? t[2]=u[3] )}

S: S#
S1 S2 S3 S4 S5 S6 S1 S2 S3 S4 S5 S6

SN SD SA A B C D E F A B C D E F CS 20 CS 21 MA 19 CI 19 MA 20 CS 22 CS 20 CS 21 MA 19 CI 19 MA 20 CS 22
60

2015/9/23

数据库系统数据库系统

第二章

关系数据库

二、未实现的元组关系演算语言——ALPHA E. F. Codd提出,但并未实现。

1、检索操作(GET)
(1)不设元组变量 例:取出计算机系学生的学号: GET W (S.S#): S.SD=?CS‘
工作空间名 表达式 限定条件

2015/9/23

数据库系统数据库系统

63

第二章

关系数据库

二、未实现的元组关系演算语言——ALPHA E. F. Codd提出,但并未实现。

1、检索操作(GET)
(1)不设元组变量 (事实上关系名起到元组变量的作用) 例:取出计算机系学生的学号: GET W (S.S#): S.SD=?CS‘ 相当于投影 相当于原子公式t[i]?C

取出一个计算机系学生的学号 GET W (1) (S.S#): S.SD=?CS‘ 定额
2015/9/23 数据库系统数据库系统 64

第二章 (2) 使用元组变量 应用场合
变量范围说明

关系数据库

用较短的名字代替较长的关系名 使用量词时 关系名

例 查找不选C1课程的学生姓名 元组变量
RANGE SC X GET W (S.SN): ?X(X.S# ? S.S# ? X.C# ? ‘C1‘) 查找选修全部课程的学生姓名 RANGE C CX RANGE SC SCX GET W(S.SN): ?CX?SCX(SCX.S# =S.S# ? SCX.C# =CX.C#)
2015/9/23 数据库系统数据库系统 65

第二章 2、存储操作 (1)修改:UPDATE

关系数据库

关键字不能修改,

(2)插入:PUT
(3)删除:DELETE 参阅教材P67--P69。

只能先删除、再插入

2015/9/23

数据库系统数据库系统

66

第二章 三、域关系演算

关系数据库

与元组关系演算类似,只不过这里的变量取值范围是属 性值,其谓词变元称作欲变量,关系的属性名可视作欲变量 。 关系代数、元组关系演算、域关系演算的表达能力是

四、域关系演算语言——QBE 等价的。
QBE是Query By Example 的缩写,1978年在IBM370上 实现。

1、特点
? 用户通过表格形式提出查询,查询结果也通过表格显示 出来

? 用户容易掌握,易学易用
2015/9/23 数据库系统数据库系统 67

第二章 2、使用方法

关系数据库

(1) 用户提出使用要求(如键入某一命令)

(2) 机器显示空白表格
(3) 用户输入关系名

S

S#

SN

SD

SA

如 学生关系 S
(4)机器自动显示属性名

2015/9/23

数据库系统数据库系统

68

第二章 2、使用方法

关系数据库

(1) 用户提出使用要求(如键入某一命令)

(2) 机器显示空白表格
(3) 用户输入关系名

查询条件SD=?CS‘

如 学生关系 S
(4) 机器自动显示属性名 (5) 提出查询要求 如 查询计算机系 的学生姓名和年龄
P.是操作符 示例元素 S S# SN P.张三 SD CS SA P.30

(任选一个可能的值)
2015/9/23 数据库系统数据库系统 69

第二章 3、其他例子: (1)查询操作 例1:查计算机系年龄大 于19的学生姓名 两个条件写两行, 示例元素相同, 表示 条件之间是“与”的关 系 例2:查计算机系或年龄 大于19的学生姓名

关系数据库
S S# SN SD SA

P.张三

CS

>19

S

S#

SN P.张三 P.张三

SD CS

SA

>19

S

S#

SN P.张三 P.李四

SD CS

SA

示例元素不同, 表示 条件之间是“或”的关系
2015/9/23 数据库系统数据库系统

>19
70

第二章

关系数据库

例3:查选修C2的学生名字 (涉及两个关系,需要连接操作)
SC S# S1 C# C2 G

不同关系中的 两个示例元素相同, 表示了连接操作。

S

S#

SN

SD

SA

S1

P.张三

2015/9/23

数据库系统数据库系统

71

第二章 (2) 修改操作

关系数据库

修改操作符为“U.‖,不允许修改主码,若要修改主码, 需先删除元组,再插入。
S S# SN SD SA

例1:把学号为S1的学 生转入计算机系。

S1

U. CS

修改操作不包含表 达式,可有两种表 示方法。

S U.

S# S1

SN

SD CS

SA

例2:将计算机系所有 学生的年龄增加1岁。
2015/9/23

S

S# S1

SN

SD CS

SA 19

U.

S1

19+1
72

数据库系统数据库系统

第二章 (3) 插入操作

关系数据库

操作符为“I.‖,新元组必须包含码,其他属性值可为空。 例:
S I. S# S8 SN 美丽 SD CS SA 19

(4)删除操作 操作符为“D.‖。 例:删除计算机系 的学生。
S D. S# SN SD CS SA

2015/9/23

数据库系统数据库系统

73

第三章 关系数据库标准语言——SQL
本章要求: 1、掌握SQL定义基本表和建立索引的方法 2、掌握SQL中各种查询方法和数据更新方法 3、掌握SQL中视图的定义方法和用法 4、掌握SQL的授权机制 5、了解嵌入式SQL的基本使用方法 本章内容: §1 §2 §3 §4 §5 §6
2015/9/23

SQL概述 SQL数据定义功能 SQL数据操纵功能 视图 SQL数据控制功能 嵌入式SQL
数据库系统数据库系统

请选择内容

返回
74

第三章 关系数据库标准语言——SQL

§1
一、SQL 的发展

SQL概述

SQL是 Structured Query Language的缩写 (ANSI解释为Standard Query Language)

74年 Boyce &Chambarlin提出,在IBM的System R上
首先实现 79年 Oracle

82年 IBM的DB2
84年 Sybase

采用SQL作为数据库语言

2015/9/23

数据库系统数据库系统

75

第三章 关系数据库标准语言——SQL
86年10月 成为美国国家标准 87年 国际标准化组织(ISO)采纳为国际标准 89年 92年 ISO推出SQL89 ISO推出SQL2

目前正制定SQL3标准 二、SQL的主要特点 1、一体化:两方面 集DDL、DML、DCL为一体 实体和联系都是关系,因此每种操作只需一种操作符

2015/9/23

数据库系统数据库系统

76

第三章 关系数据库标准语言——SQL
2、高度非过程化语言 (WHAT ? HOW ? ) 3、面向集合的操作方式(一次一集合) 4、交互式和嵌入式两种使用方式,统一的语法结构 5、语言简洁,易学易用 完成核心功能只有9个动词: 数据查询: SELECT 数据定义: CREATE,DROP,ALTER 数据操纵: INSERT,DELETE,UPDATE 数据控制: GRANT,REVOKE 6、支持三级模式结构 视图 ? 外模式 基本表(的集合) ? 模式 存储文件和索引 ? 内模式
2015/9/23 数据库系统数据库系统 77

第三章 关系数据库标准语言——SQL
用户 SQL View V1 Base table B1 View V2 外模式

Base table B2
Stored file S1

Base table B3

Base table 模式 B4
Stored file 内模式 S2

SQL支持的三级模式结构
2015/9/23 数据库系统数据库系统 78

第三章 关系数据库标准语言——SQL
说明: ? 基本表是独立存在的表。一个关系对应一个表。一个( 或多个)表对应一个存储文件,每个表可有若干索引,这 些索引也可放在存储文件中。 ? 视图是从一个或几个基本表中导出的表,概念上同基 本表。但它并不真正存储数据,也不独立存在,它依赖 于导出它的基本表,数据也存放在原来的基本表中。

? 对内模式,只需定义索引,其余的一切均有DBMS自 动完成 本节开头
2015/9/23

本章开头
数据库系统数据库系统

下一节
79

第三章 关系数据库标准语言——SQL §2 SQL数据定义功能
三部分: ? 定义和修改基本表(定义模式):CREATE TABLE DROP TABLE ALTER TABLE ? 定义视图(定义外模式):CREATE VIEW DROP VIEW ? 定义索引(定义内模式): CREATE INDEX DROP INDEX 说明:视图是从基本表导出的虚表,索引依赖于基本表, SQL没有修改视图和索引的操作,可通过先删除,再创建 达此目的。
2015/9/23 数据库系统数据库系统 80

第三章 关系数据库标准语言——SQL
一、基本表的定义和修改 1、定义:基本格式为

CREATE TABLE 表名(列名1 类型 [列级完整性约束]
[,列名2 类型 [列级完整性约束]…); 示例 CREATE TABLE S( S# CHAR(3) NOT NULL UNIQUE ,

SN CHAR(15), 说明: SD CHAR(15), 不允许取空值 ? 注意SQL语句的书写格式 SA SMALLINT); ? SQL支持空值的概念。允许空值的列未输入数据时系统 自动置为空值。 ? SQL支持的数据类型随系统不同而有所差异。
2015/9/23 数据库系统数据库系统

取值唯一

81

第三章 关系数据库标准语言——SQL
不支持NOT NULL选择 2、修改基本表 如 ALTER TABLE S ADD SD INT; (1)增加列:

ALTER TABLE 表名 ADD 列名 类型 [完整性约束];
(2)修改列 如 ALTER TABLE S MODIFY SD CHAR(20 ALTER ) TABLE 表名 MODIFY 列名 类型;

(3)删除完整性约束
ALTER TABLE 表名 DROP 完整性约束名; 注意:不能删除列,新增列的值一律为空值, 可增加列宽,但一般不能减小列宽,修改可能 会破坏已有数据。 在定义基本表时要考虑充分
2015/9/23 数据库系统数据库系统 82

第三章 关系数据库标准语言——SQL
3、删除: DROP TABLE 表名;

注意:删除基本表时,表中的数据、建立在表上的
索引和视图将一并被删除,因此应格外小心。

二、索引的建立和删除
由DBA或表的属主进行,存取数据时由系统自动选 取合适的索引作为存取路径,用户不必也不能选择索引



2015/9/23

数据库系统数据库系统

83

第三章 关系数据库标准语言——SQL
1、建立 一个索引项值仅对应唯一的数据记录

CREATE [ UNIQUE ] [CLUSTER] INDEX 索引名
ASC ASC [,列名 ]…); DESC DESC 改变记录的物理顺序使之与索引项值的排列顺序 升序或降序 相同,称为聚簇索引。显然一个表只能建立一个 缺省为升序 聚簇索引。可通过在经常查询而改动小的表上建 立这种索引来提高查询效率。 ON 表名(列名

如 CREATE UNIQUE INDEX XSNO ON S(S#); CREATE UNIQUE INDEX SCNO ON SC(SNO ASC,CNO DESC); 2、删除 DROP INDEX 索引名;
2015/9/23 数据库系统数据库系统 84

第三章 关系数据库标准语言——SQL
§3 SQL数据操纵----查询 查询是数据库的核心操作。SQL仅提供了唯一的

语句SELECT,其使用方式灵活,功能非常丰富。 相当于投影 1、一般格式 细节见P115 全部字段 SELECT [ALL | DISTINCT]
FROM 基本表(或视图) [ WHERE 条件表达式 ]

* | 目标列
被查询的关系 相当于选择或连接

分组 统计

[ GROUP BY 列名1 [ HAVING 内部函数表达式 ] ] ASC [ ORDER BY 列名2 ]; 满足条件的组才输出 DESC 对查询结果排序
数据库系统数据库系统 85

2015/9/23

第三章 关系数据库标准语言——SQL
2、简单查询 例1:求选修了课程的学生学号 SELECT DISTINCT S# FROM SC; 从结果中去掉重复的元组

例2:SELECT的后面可以是表达式。 如求计算机系学生的学号和出生年份: SELECT S#,‘Birthday:’,2000-SA FROM S WHERE SD=?CS‘; 例3:连续范围查询,使用BETWEEN (NOT BETWEEN) SELECT S#,SA 即求20到22岁之间 FROM S WHERE SA BETWEEN 20 AND 22; 的学生学号和年龄
2015/9/23 数据库系统数据库系统 86

第三章 关系数据库标准语言——SQL
例4:离散范围查询,使用 IN (NOT IN) SELECT * 星号表示无投影 相当于若干 FROM S ‘OR‘的缩写 WHERE SD IN (‘MA‘,‘CS‘);

SD=?MA‘ OR SD=?CS‘

2015/9/23

数据库系统数据库系统

87

第三章 关系数据库标准语言——SQL
2、简单查询 例1:求选修了课程的学生学号 SELECT DISTINCT S# FROM SC; 从结果中去掉重复的元组

例2:SELECT的后面可以是表达式。 如求计算机系学生的学号和出生年份: SELECT S#,‘Birthday:’,1998-SA FROM S WHERE SD=?CS‘; 例3:连续范围查询,使用BETWEEN (NOT BETWEEN) SA>=20 AND 相当于若干 SELECT S#,SA SA<=22 ‘AND‘ 的缩写 FROM S WHERE SA BETWEEN 20 AND 22;
2015/9/23 数据库系统数据库系统 88

第三章 关系数据库标准语言——SQL
例4:离散范围查询,使用 IN (NOT IN) SELECT * 相当与若干 FROM S ‘OR‘的缩写 WHERE SD IN (‘MA‘,‘CS‘); 例5:模糊查询,使用 LIKE (NOT LIKE)

SELECT * 查姓名中有‘清’字的学生 FROM S WHERE SN LIKE ?%清%‘; DB2中,下划线 ‘_‘表示匹配任何单个字符 其它语言中, 常用 ‘?‘ 百分号‘%‘表示匹配任何字符串 常用 ‘*’ 例6: 涉及空值的查询 , IS NULL (IS NOT NULL) SELECT S#, C# FROM SC WHERE G IS NULL ;
2015/9/23 数据库系统数据库系统 89

第三章 关系数据库标准语言——SQL
3、连接查询:涉及至少两个表的查询 SQL中没有专门的JOIN命令,而是靠SELECT语句中的 WHERE子句来达到连接运算的目的,因此更加灵活、简便。 用来连接两个表的条件称为连接条件或连接谓词。 连接条件的一般格式为:

[表名1.]列名 1 比较运算符 [表名2.]列名2
[表名1.]列名1 BETWEEN [表名2.]列名2 AND [表名2.]列名3 比较运算符主要有:=、> 、< 、>=、<=、!=。

等值连接:运算符为“=‖时。
非等值连接:运算符不是“=‖时。 自然连接:等值连接且目标列不含重复属性。 连接操作的实现过程:见教材P102中部。
2015/9/23 数据库系统数据库系统 90

第三章 关系数据库标准语言——SQL
例1:简单的连接查询 S : S# SN SD SA SC:S# C# G 求选修C1课程的学生学号、 01 A MA 20 01 C1 A 02 B CS 19 01 C2 A 姓名和成绩 03 C IS 21 02 C2 B 连接字段 SELECT S.S#, SN, G 04 D MA 19 02 C3 C FROM S, SC 05 E MA 20 03 C3 B 04 C1 B WHERE S.S#=SC.S# 连接条件 04 C4 A AND SC.C#=?C1‘; 或称连接谓词 表名前缀 (字段名 唯一时可省略)

2015/9/23

数据库系统数据库系统

91

第三章 关系数据库标准语言——SQL
例1:简单的连接查询 S : S# SN SD 求选修C1课程的学生学号、 01 A MA 02 B CS 姓名和成绩 03 C IS SELECT S.S#, SN, G 04 D MA FROM S, SC 05 E MA WHERE S.S#=SC.S# AND SC.C#=?C1‘; SA 20 19 21 19 20 SC:S# 条 01 件 01 满 02 不 足 02 满 足 03 04 04 C# G C1 A C2 A C2 B C3 C C3 B C1 B C4 A

查询结果:S# SN G 01 A A

在多个表中出现的列名 ,必须用表名限定,仅 在一个表中出现的属性 ,可省略表名。
数据库系统数据库系统 92

2015/9/23

第三章 关系数据库标准语言——SQL
例2:多表连接 求学生学号、姓名、 SC: S# C# G

S: S#
S1 S2 S3 S4 S5 S6

SN SD SA

选修课程名、成绩

A B C D E F

CS 20 CS 21 MA 19 CI 19 MA 20 CS 22
CN G H I J K PC# C1 C1 C2 C4

直观的查找过程

C:

C# C1 C2 C3 C4 C5

S1 S1 S1 S1 S2 S2 S2 S3 S3 S3 S4 S4 S5 S5 S5 S6 S6

C1 C2 C3 C5 C1 C2 C4 C2 C3 C4 C3 C5 C2 C3 C5 C4 C5

A A A B B C C B C B B D C B B A A
93

2015/9/23

数据库系统数据库系统

第三章 关系数据库标准语言——SQL
例2:多表连接 求学生学号、姓名、 SC: S# C# G

S: S#
S1 S2 S3 S4 S5 S6

SN SD SA

选修课程名、成绩
SELECT S.S#,SN,CN,G FROM S,C,SC

WHERE S.S#=SC.S# AND
SC.S#=C.C#;

A B C D E F

CS 20 CS 21 MA 19 CI 19 MA 20 CS 22
CN G H I J K PC# C1 C1 C2 C4

C:

C# C1 C2 C3 C4 C5

S1 S1 S1 S1 S2 S2 S2 S3 S3 S3 S4 S4 S5 S5 S5 S6 S6

C1 C2 C3 C5 C1 C2 C4 C2 C3 C4 C3 C5 C2 C3 C5 C4 C5

A A A B B C C B C B B D C B B A A
94

2015/9/23

数据库系统数据库系统

第三章 关系数据库标准语言——SQL
例3: 单表连接 求每一门课程的 C: C# CN C1 G C2 H C3 I C4 J C5 K PC# C1 C1 C2 C4 C: C# C1 C2 C3 C4 C5 CN G H I J K PC# C1 C1 C2 C4

间接先行课
直观的查找过程

FIRST SQL语句为: SELECT FIRST.C#, SECOND.PC#

SECOND

FROM C FIRST, C SECOND
WHERE FIRST.PC# = SECOND.C# ;

别名引入
2015/9/23 数据库系统数据库系统

查询结果为: C# PC# C2 C3 C4 C1 C5 C2
95

第三章 关系数据库标准语言——SQL
S:S# SN SD SA SC:S# S1 S1 A CS 20 S1 S2 B CS 21 课程及成绩。 S2 S3 C MA 19 S2 S4 D CI 19 使用外连接时 不使用外连接时 S2 SQL语句为: 查询结果为: S# SN C# G SELECT S.S#, SN, C#, G S1 A C1 A FROM S, SC S1 A C2 A S2 B C1 B WHERE S.S# = SC.S# ;(*); S2 B C2 C S2 B C4 C 有些数据库系统用+ S3 C 有些将*放在=前后,*=、=* S4 D 例4:外连接查询 求每个学生选修的
2015/9/23 数据库系统数据库系统

C# C1 C2 C1 C2 C4

G A A B C C

96

第三章 关系数据库标准语言——SQL
SC: S# S1 S:S# SN SD SA S1 S1 S1 A CS 20 S1 ? S2 B CS 21 S2 S3 C MA 19 ‘J‘ S2 S4 D CI 19 S2 的学生学号和姓名 分析:可用连接来实现,但 分析:可用连接来实现, S5 E MA 20 S3 S3 SELECT S.S#, S.SN 最后结果只包含 S中的字段, S6 F CS 22 S3 C : C# CN PC# FROM S, C, SC 应该考虑更为有效、 直观 S4 C1 G WHERE S.S#=SC.S# S4 的方法: C2 H C1 ? S5 AND SC.C#=C.C# ? 在C中找课程‘J‘的编号 C3 I C1 S5 ? C.CN=―J‖ ; S5 C4 J C2 ? AND 在SC中找选修该课的学号 S6 C5 K C4 ? 在S中找选修该课的学生姓名 S6 4、嵌套查询(子查询) SELECT-FROM-WHERE 查询块嵌入另一个查询块中 例1:求选修了课程名为
2015/9/23 数据库系统数据库系统

C# C1 C2 C3 C5 C1 C2 C4 C2 C3 C4 C3 C5 C2 C3 C5 C4 C5

G A A A B B C C B C B B D C B B A A

97

第三章 关系数据库标准语言——SQL
SC: S# ? 在C中找课程‘J‘的编号 S1 S:S# SN SD SA S1 SELECT C# S1 S1 A CS 20 FROM C S1 ? S2 B CS 21 WHERE CN=?J‘; S2 S3 C MA 19 S2 S4 D CI 19 ? 在SC中找选修该课的学号 S2 S5 E MA 20 S3 SELECT S# S3 S6 F CS 22 FROM SC S3 C : C# CN PC# WHERE C# IN (‘C4‘); S4 C1 G S4 ? 在S中找选修该课的学生姓名 C2 H C1 ? S5 C3 I C1 S5 SELECT S#,SN ? S5 C4 J C2 FROM S S6 C5 K C4 WHERE S# IN (?S2‘,?S3‘,?S6‘); S6
2015/9/23 数据库系统数据库系统

C# C1 C2 C3 C5 C1 C2 C4 C2 C3 C4 C3 C5 C2 C3 C5 C4 C5

G A A A B B C C B C B B D C B B A A

98

第三章 关系数据库标准语言——SQL
? 在C中找课程‘J‘的编号
最后的查询语句:

SELECT S#,SN FROM S WHERE S# IN ( (‘S2‘,?S3‘,?S6‘); ? 在SC中找选修该课的学号 SELECT S# SELECT S# FROM SC FROM SC WHERE C# IN (?C4‘); WHERE C# IN (‘C4‘); ( SELECT C# ? 在S中找选修该课的学生姓名 FROM C SELECT S#,SN WHERE CN=?J‘ FROM S ) WHERE S# IN (?S2‘,?S3‘,?S6‘); );
2015/9/23 数据库系统数据库系统 99

SELECT C# FROM C WHERE CN=?J‘;

第三章 关系数据库标准语言——SQL
说明: (1)嵌套查询由内向外处理 (2)SQL允许多层嵌套 (3)嵌套查询中最常用的 最后的查询语句: SELECT S#,SN FROM S WHERE S# IN ( SELECT S# FROM SC WHERE C# IN ( SELECT C# FROM C WHERE CN=?J‘ ) );
100

谓词是IN
(4)嵌套查询层次分明、 容易理解

2015/9/23

数据库系统数据库系统

第三章 关系数据库标准语言——SQL
带有比较运算符的子查询
当用户确切知道内层查询的结果是单值(只有一个元组,且 该元组只有一个字段)时,可将外层查询的某字段与内层查

询的结果用>、<、=、>=、<=、!=等比较运算符进行比较。
例2:求“张三”选修的课程名称及成绩(设无同名学生) SELECT C.CN, SC.G FROM C, SC S(S#, SN, SD,SA) WHERE C.C# = SC.C# AND C(C#, CN, PC#) SC.S# = SC(S#, C#, G) (SELECT S# 子查询必须出现在比 FROM S 较符之后。 WHERE SN=―张三”);
2015/9/23 数据库系统数据库系统 101

第三章 关系数据库标准语言——SQL
使用存在量词 EXISTS 和 NOT EXISTS 的查询 例3:求至少一门不及格的学生姓名 SELECT SN 若内层查询结果非空,则为真 FROM S 否则为假 WHERE EXISTS (SELECT * FROM SC WHERE S# = S.S# AND G=?D‘); 等价于: SELECT S.SN 相当于一个变量,根据它的值处理 称为相关子查询: FROM S, SC 查询条件依赖于外层 内层查询, S中有多少个学号,内层 WHERE S.S#=SC.S# AND SC.G=?D‘ ; 查询中某个值 查询就进行多少次
2015/9/23 数据库系统数据库系统 102

第三章 关系数据库标准语言——SQL
例4:查询没有选修“C1‖课程的学生姓名。 SELECT SN SELECT SN FROM S WHERE S# NOT IN

FROM S
WHERE NOT EXISTS (SELECT *

(SELECT S#
FROM SC WHERE C#=―C1‖);

FROM SC
WHERE S# = S.S# AND C#=―C1‖);

哪种形式效率高 ?
2015/9/23 数据库系统数据库系统 103

第三章 关系数据库标准语言——SQL
例5:对全称量词的处理 带全称量词的谓词 (?x)P(x) 想一想:用关系代数如何实现? 求选修了全部课程的学生姓名 带存在量词的谓词 ?(? x(? P(x))

用除法!

本例变为:选这样的学生姓名,没有一门课程是他不选修的

分析: 任给一学号S#, 若不存在他不选修的课, 则显示他的姓名
? ( ? C# (学号为S#的学生没修课程C#) ) ? ( ? C# (在SC中不存在选课单 (S#, C#,… ) ) )
2015/9/23 数据库系统数据库系统 104

第三章 关系数据库标准语言——SQL
SELECT SN FROM S 为真 WHERE NOT EXISTS ( SELECT * 查询结果为空 FROM C WHERE NOT EXISTS 都为假 ( SELECT * 查询结果都非空 FROM SC WHERE S#=S.S# AND C#=C.C# ) );
2015/9/23 数据库系统数据库系统 105

即所有的课程 都选修

第三章 关系数据库标准语言——SQL
SELECT SN 选修全部课课 FROM S WHERE NOT EXISTS ? ( ? C# (学号为S#的学生没修课程C#) ) ( SELECT * FROM C WHERE NOT EXISTS 在SC中不存在选课单 (S#, C#,… )? ( SELECT * FROM SC 在SC中查选课单 (S#, C#,… ) WHERE S#=S.S# AND C#=C.C# ) );
2015/9/23 数据库系统数据库系统 106

第三章 关系数据库标准语言——SQL
例6 对“蕴涵”的处理 P ? Q ? ?P ? Q

如: 求这样的学生学号, 该生至少选修了学生S2所修的全部课程
即找这样的学号Sx, 对所有的课程Cy, 若S2选修了Cy, 则Sx也选修了Cy P表示谓词“学生S2选修课程Cy‖ Q表示谓词“学生Sx选修课程Cy‖ 查询条件为: (?Cy) (P?Q) ? ??Cy (? (P?Q)) ? ??Cy (? (?P?Q)) ? ??Cy (P??Q)
2015/9/23 数据库系统数据库系统 107

第三章 关系数据库标准语言——SQL
SELECT DISTINCT S# FROM SC SCX

WHERE NOT EXISTS
( SELECT * FROM SC SCY

条件 ?? Cy ( P ? ?Q )

WHERE SCY.S# = ?S2‘ AND
NOT EXISTS ( SELECT * FROM SC SCZ WHERE SCZ.S# = SCX.S# AND SCZ.C# =SCY.C# ) );
2015/9/23 数据库系统数据库系统 108

请思考: 直观的查找过程?

第三章 关系数据库标准语言——SQL
问题: 上例可否改为下面的SQL语句? SELECT S# 选这样的学号Sx, 不 FROM S 存在S2选修的一门 WHERE NOT EXISTS 课程Sx未选修 ( SELECT * FROM SC SCY 选这样的学号Sx,S2 WHERE SCY.S# = ?S2‘ AND 选修的课程Sx都选 NOT EXISTS 修了 ( SELECT * FROM SC SCZ WHERE SCZ.S# = S.S# AND SCZ.C# =SCY.C# ) );
2015/9/23 数据库系统数据库系统 109

第三章 关系数据库标准语言——SQL
例7:使用UNION的查询 求C1和C4课程成绩为 A的学生的学号及姓名 S# C# G S:S# SN SD SA SC: S1 A CS 17 S1 C1 A S2 B CS 21 S1 C3 A S3 C MA 19 S1 C5 B SELECT S.S#, S.SN S4 D CI 17 S2 C1 A FROM S, SC S5 E MA 20 S2 C2 C WHERE S.S#=SC.S# AND S6 F CS 20 S2 C4 A SC.C#=?C1‘ AND S9 Z IS 18 S3 C3 SC.G=?A‘ S3 C4 参加UNION操 UNION S4 C3 B 查询结果 作的各结果表 SELECT S.S#, S.SN 再选择C1 C4课 先选择 S4 C5 D S# SN 的列数、对应 FROM S,SC 程成绩为A的 S5 C2 S1 A 项的数据类型 WHERE S.S#=SC.S# AND 学号姓名 S5 C3 S2 B 必须相同 SC.C#=?C4‘ AND S5 C5 S6 F SC.G=?A‘; S6 C4 A
2015/9/23 数据库系统数据库系统 110

第三章 关系数据库标准语言——SQL
S# S : 例7:使用UNION的查询 S1 求C1和C4课程成绩为A S2 的学生的学号及姓名 S3 S4 等价于: S5 SELECT DISTINCT S.S#,S.SN S.S#,S.SN S6 FROM S, SC S9 WHERE (S.S#=SC.S# AND SC.C#=?C1‘ AND SC.G=?A‘) OR 有 重 (S.S#=SC.S# AND 复 SC.C#=?C4‘ AND 的 SC.G=?A‘); 行
2015/9/23

SN A B C D E F Z

SD CS CS MA CI MA CS IS

S# SC: S1 S1 S1 S2 S2 S2 S3 S3 查询结果 S4 S# SN S4 S1 A S5 S2 B S5 S2 B S5 S6 F S6

SA 17 21 19 17 20 20 18

C# C1 C3 C5 C1 C2 C4 C3 C4 C3 C5 C2 C3 C5 C4

G A A B B C C 0 0 B D 0 0 0 A
111

数据库系统数据库系统

第三章 关系数据库标准语言——SQL
S# S : 例7:使用UNION的查询 S1 求C1和C4课程成绩为A S2 的学生的学号及姓名 S3 S4 等价于: S5 SELECT DISTINCT S.S#,S.SN S.S#,S.SN S6 FROM S, SC S9 WHERE AND WHERE (S.S#=SC.S# S.S#=SC.S# AND SC.C#=?C1‘ AND SC.G='A' AND SC.G=?A‘ ) (SC.C#='C1'OR SC.C# INSC.C#='C4'); ('C1‘,'C4'); OR (S.S#=SC.S# AND SC.C#=?C4‘ AND SC.G=?A‘);
2015/9/23

SN A B C D E F Z

SD CS CS MA CI MA CS IS

S# SC: S1 S1 S1 S2 S2 S2 S3 S3 查询结果 S4 S# SN S4 S1 A S5 S2 B S5 S6 F S5 S6

SA 17 21 19 17 20 20 18

C# C1 C3 C5 C1 C2 C4 C3 C4 C3 C5 C2 C3 C5 C4

G A A B B C C 0 0 B D 0 0 0 A
112

数据库系统数据库系统

第三章 关系数据库标准语言——SQL
说明: (1)用UNION查询时,每个子查询选择的目标列必须相同,

但所基于的表可以不同 ( 2)UNION查询实际上是将几个子查询的结果合并在一起 例:求计算机系及选修 C5课程的学生学号和姓名
(3)UNION查询时自动去掉重复的行 SELECT S.S#, S.SN ( 4)可以通过将各子查询的限制条件合并而将 UNION查询 FROM S WHERE SD='CS' 变成一个单一查询 UNION SELECT S.S#, S.SN FROM S, SC WHERE S.S#=SC.S# AND SC.C#='C5';
2015/9/23 数据库系统数据库系统 113

第三章 关系数据库标准语言——SQL
例8:求选修课程C1的学生 与选修C2的学生的交集。 即求同时选修了课程C1和C2 的学生学号。 例9:求计算机系学生与年龄小 于20岁的学生的差集。

即求计算机系年龄不小于20岁
的学生。

SELECT S#
FROM SC WHERE C# =?C1‘

SELECT S#,SN
FROM S WHERE SD=?CS‘AND

AND S# IN
(SELECT S# FROM SC

SA>=20;

WHERE C# =?C2‘);
2015/9/23 数据库系统数据库系统 114

第三章 关系数据库标准语言——SQL
5、库函数(聚集函数) COUNT SUM AVG 统计一列中的(NOT NULL)值的个数 对一列求和 对一列求平均值

COUNT(*) 计算记录个数

MAX
MIN

对一列求最大值
对一列求最小值

例1:求选修了课程的学生人数

SELECT COUNT(DISTINCT S#)
FROM SC;
2015/9/23

重复的只记一个
数据库系统数据库系统 115

第三章 关系数据库标准语言——SQL
例2 分组统计:使用GROUP BY 求选修各门课程的学生人数 SELECT C#,COUNT(S#) FROM SC GROUP BY C#; 将表按列的值分组,列 的值相同的分在一组,产生 一个结果行。GROUP BY常 和库函数一起使用,用于分

组统计。 SELECT SC.C#,C.CN, COUNT(S# 上例中,如果要求显 目标列中没有作用库 示课程名称,则可以 ) 函数的列必须出现在 GROUP BY中,并且 FROM SC, C WHERE SC.C#=C.C# 这里,实际上仅需按 先按第一列的值分组 GROUP BY SC.C#, CN; C#分组 即可,不必 SELECT SC.C#,MIN(C.CN), COUNT(S#) ,第一列值相同的再 再按CN分组,为此 按第二列分组,依次 FROM SC, C WHERE SC.C#=C.C# 可用MIN函数作用之 类推。 GROUP BY SC.C#; 。因为同一分组中 2015/9/23 116 数据库系统数据库系统 C#相同,CN也相同

第三章 关系数据库标准语言——SQL
例3 带条件的分组查询、统计:使用HAVING 求选修课程超过3门的学生学号 WHERE是选择记录的条件; HAVING是选择分组的条件且 SELECT S# 必须和GROUP BY一起使用 FROM SC GROUP BY S# 库函数只能作用于HAVING和 HAVING COUNT(*)>3; 目标列,而不能用于WHERE 。 假定SC中的G用百分制表示,求最低成绩不低于 85分,平均 成绩不低于90分的学生学号和姓名,并按学号降序排序。 SELECT SC.S#,MIN(S.SN) FROM S,SC 通过一个库函数, 过滤分组,可用 WHERE S.S#=SC.S# 使之可不必出现在 库函数多次作用 建立两个表的连接 按学号分组 GROUP BY SC.S# GROUP BY中 同一字段 HAVING MIN(SC.G)>=85 AND AVG(SC.G)>=90 ORDER BY SC.S# DESC; 按学号降序排序
2015/9/23 数据库系统数据库系统 117

第三章 关系数据库标准语言——SQL
§4 SQL数据操纵----数据更新 一、插入数据

1、插入单个元组
INSERT INTO 表名 [(字段名 [,字段名 ] … ] VALUES (常量 [,常量] … ] ; 例1:插入一条选课记录(S1,C5)。

INSERT
INTO SC(S#,C#) VALUES(‘S1‘,‘C1‘);
2015/9/23 数据库系统数据库系统 118

第三章 关系数据库标准语言——SQL
说明: ★ 当在INTO后面仅指定部分属性列时,插入记录后其它

列的值为空值;
★ 如果INTO后面没有指定属性列,则必须按表列的定义 次序为每个列指定一个值; ★ 具有NOT NULL属性的列,必须指定值。 2、插入子查询结果 INSERT

INTO 表名 [(字段名 [,字段名 ] … ]
子查询;
2015/9/23 数据库系统数据库系统 119

第三章 关系数据库标准语言——SQL
例2:求每个学生的平均成绩,并按学号、姓名、平均成

绩存入数据库。(设成绩G是数值型) 先创建一个表
CREATE TABLE AG(S# CHAR(8), SN CHAR(8), 将计算结果插入上表中 INSERT

AG SMALLINT);
为什么用MIN()函数 ?

INTO AG(S#,SN,AG)
FROM S,SC

SELECT S.S#,MIN(SN),AVG(G)

WHERE S.S# = SC.S# GROUP BY S.S# ;
2015/9/23 数据库系统数据库系统 120

第三章 关系数据库标准语言——SQL
二、修改数据 UPDATE 表名

SET 列名 = 表达式[,列名 = 表达式]…
[WHERE 条件]; 说明:

★ 当省略WHERE子句时,修改表中所有记录,否则仅
修改满足条件的记录; ★ 条件也可以使用子查询。 例1:将所有学生的年龄增加1岁。 UPDATE S

SET SA = SA +1 ;
2015/9/23 数据库系统数据库系统 121

第三章 关系数据库标准语言——SQL
例2:把数学系全体学生的成绩置零
UPDATE SC SET G=0 WHERE ?MA‘= (SELECT SD FROM S WHERE S.S# = SC.S# ); 对SC中的每个选课单,检 查其对应学生所在的系是 否‘MA‘。
2015/9/23

UPDATE SC SET G=0 WHERE S# IN ( SELECT S# FROM S WHERE SD=?MA‘ );

找出‘MA‘系的所有学生, 检查SC选课单所对应的学生 是否是这些学生中的一员。
122

数据库系统数据库系统

第三章 关系数据库标准语言——SQL
三、删除数据:
DELETE 例1:删除不及格的学生记录。 DELETE FROM SC WHERE G < 60; 例2:删除物理课的全部选课单 DELETE FROM SC

FROM 表名
[ WHERE 条件 ];

只能删除表记录,不删除表
结构。无条件时,删除全部 记录,仅剩一个空表;有条

件时删除满足条件的记录。 为物理删除命令 删除表结构用DROP TABLE
2015/9/23

C# = WHERE ? 物理’ = (SELECT C# CN
FROM C WHERE CN == ?物理’) C.C# SC.C#) ;
123

数据库系统数据库系统

第三章 关系数据库标准语言——SQL
四、更新操作与数据库的一致性 增、删、改操作只能对一个表操作,可能会造成数据 的不一致性。例如: 删除“物理”课程的全部信息,需使用两个操作实现 ,删除C表的课程记录和删除SC表的选课记录。若在完成

第一个操作后发生意外,致使第二个操作未能实现,则造
成数据库的不一致。因为SC中的物理课程号还存在,而被 参照的C表中已没有该课程号的课程了。所以应保证这两个

操作要么全做,要么全不做,为此,在数据库系统中引入
了事物的概念。 为保证数据的一致性,大型数据库系统一般都提供若

干策略:
2015/9/23 数据库系统数据库系统 124

第三章 关系数据库标准语言——SQL
删除主表(被参照表)中的数据时 (1)自动删除参照表中的相应数据;

(2)检查参照表中是否有数据参照,若有则拒绝删除。
向参照表中插入数据时 检查所有被参照表中是否有被参照的信息,若没有则拒

绝插入。
修改主表中的被参照字段 检查参照表中是否有数据参照,若有则拒绝修改。 虽说SQL的DML语句只有4个,但语句中成分多

样,因此简单易学、功能丰富、灵活多样。
2015/9/23 数据库系统数据库系统 125

第三章 关系数据库标准语言——SQL
§5 视 图 ? 视图是从一个或几个基本表(或视图)导出的表。

(用户外模式是由若干基本表和/或若干视图构成的)
? 视图是一个虚表,只存储视图的定义,数据存在所基于 的基本表中。 ? 视图定义后就可象基本表一样来使用。

?可创建、删除视图
?可用来定义新的视图 ?可在视图上查询(SELECT)

?可更新(INSERT,DELETE,UPDATE)视图,但受
限制
2015/9/23 数据库系统数据库系统 126

第三章 关系数据库标准语言——SQL
一、视图的定义 视图中包含的字段 1、建立视图 格式:CREATE VIEW 视图名 [(字段名 [,字段名]…)] AS 子查询 对视图UPDATE或 [WITH CHECK OPTION ]; INSERT时,记录要 满足子查询中的条件 功能:在数据字典中存储视图的定义 (但并不执行子查询), 此后视图名就可作为一个表来使用。 例1:建立计算机系的学生视图 CREATE VIEW CS_S AS SELECT S#, SN, SA FROM S WHERE SD=?CS‘;
127

属性列省略,隐含同
2015/9/23

数据库系统数据库系统

第三章 关系数据库标准语言——SQL
★ 组成视图的属性列名,要么全部写出,要么全部省 略,省略时,隐含视图的属性列同子查询的目标列。当 SELECT语句中有库函数、或字段表达式、或多表连接 有同名字段时,则视图中必须指定字段名。 例2:把学生的学号和平均成绩定义为一个视图 CREATE VIEW S_G(S#, GAVG) AS SELECT S#, AVG(G) FROM SC GROUP BY S#; ★ 视图中字段名可以和基本表中的字段名不同 例3:建一个课程号、课程名及选课人数(不少于10)的视图 CREATE VIEW C_N(KCH, KCM, XXRS) AS SELECT SC.C#, MAX( CN), COUNT(S#) FROM C, SC WHERE C.C#=SC.C# GROUP BY SC.C# HAVING COUNT(S#)>=10 ;
2015/9/23 数据库系统数据库系统 128

第三章 关系数据库标准语言——SQL
★ 没有修改视图的方法,要实现此功能,唯一的途径是先 删除,再重建。 ★ 视图的子查询可以基于一个或多个基本表或/和视图上 。 2、删除视图 DROP VIEW 视图名;

★ 删除基本表或视图后,由被删除的基本表或视图导出
的视图仍然存在,但已无法使用,需另行删除。 二、视图上的查询 1、执行过程 从数据字典中取出视图的定义,把定义中的子查询和用 户的查询结合起来,转换成等价的对基本表的查询,最后在 基本表上执行修改后的查询,这一转换称为视图消解。
2015/9/23 数据库系统数据库系统 129

第三章 关系数据库标准语言——SQL
例1:SELECT S#,SA FROM CS_S 修改为 SELECT S#,SA FROM S WHERE SD=?CS‘ AND SA < 20;

WHERE SA < 20;
CS_S 视图中的子查询 SELECT S#, SN, SA FROM S WHERE SD=?CS‘ 2、注意事项

当视图中的字段对应的是一个库函数或字段表达式时,
有些系统 转换后的查询可能会不正确

请看下例
130

2015/9/23

数据库系统数据库系统

第三章 关系数据库标准语言——SQL
例2:求平均成绩90分以上的学生 SELECT * FROM S_G WHERE GAVG >=90; S_G视图中的定义是 CREATE VIEW S_G(S#, GAVG) AS SELECT S#, AVG(G) FROM SC GROUP BY S#
2015/9/23

修改为

SELECT S#, AVG(G) FROM SC WHERE AVG(G) >=90 GROUP BY S# ; 正确的应为: SELECT S#, AVG(G) FROM SC GROUP BY S# HAVING AVG(G) >=90;

正 确 吗 ?

数据库系统数据库系统

131

第三章 关系数据库标准语言——SQL
三、视图上的更新(ISNERT,DELETE,UPDATE) 1、执行方式

将对视图的更新语句转化为对相应的基本表的更新语句
,然后执行。为防止更新基本表中不属于本视图的数据,可 在视图定义时加上WITH CHECK OPTION子句。

例1: INSERT
INTO CS_S VALUES (?S12‘, ?YanXi‘, 19) INSERT INTO S(S#, SN, SA, SD)

视图中的子查询 SELECT S#, SN, SA FROM S WHERE SD=?CS‘

VALUES (?S12‘, ?YanXi‘, 19,?CS‘)
2015/9/23 数据库系统数据库系统 132

第三章 关系数据库标准语言——SQL
例2:将计算机系学号为“S2‖的学生姓名改为“刘辰”。 UPDATE CS_S SET SN = ―刘辰” WHERE S#=―S2‖; DELETE FROM CS_S WHERE S#=―S2‖; 2、注意事项 不是所有的视图更新都可正确转化为对基本表的更新语句
2015/9/23 数据库系统数据库系统 133

UPDATE S SET SN = ―刘辰” WHERE S#=―S2‖ AND SD=―CS‖; DELETE FROM S

例3:删除计算机系学号为“S2‖的学生 .

WHERE S#=―S2‖ AND SD=―CS‖;

第三章 关系数据库标准语言——SQL
例如:UPDATE S_G 不能有意义地转化 SET GAVG=90 WHERE S#=?S1‘; ? 有些视图是可更新的, 有些视图是不可更新的。但现在还 无判别方法。

? 肯定可以更新的视图是 行列子集视图
从单个表导出,且只是去掉 了基本表的某些行和某些列 并保留了码 ? 处理方式:只有从单个表导出的视图才允许更新操作, 且作一系列的限制。(限制见P127)

? 从概念上分清不可更新视图和不允许更新视图。
2015/9/23 数据库系统数据库系统 134

第三章 关系数据库标准语言——SQL
四、视图的优点(P128) 1、能够简化用户的操作 2、用户能以不同的方式对待同一数据,方便灵活 3、提供一定程度的逻辑独立性

4、有利于安全保密

本节开头

本章开头

下一节

2015/9/23

数据库系统数据库系统

135

第三章 关系数据库标准语言——SQL
§6 SQL数据控制功能 数据控制功能包括事物管理功能和数据保护功能。即 数据的安全性、完整性、事务控制、并发控制和恢复功能 本节只讨论安 全性机制,即 用户对数据的 存取权力。 一、授权 1、机制:大的DBMS中有一个超级用户DBA,其他用户能否 存在、对某类数据具有何种操作权力是由DBA决定 可通过在CREATE TABLE、ALTER 在后面 TABLE语句中定义码、取值唯一的列 章节介 、不允许空值的列、外码(参照完整 绍。 性)及其它一些约束条件来体现。

的,系统提供授权机制。执行过程为:
2015/9/23 数据库系统数据库系统 136

第三章 关系数据库标准语言——SQL
(1)用数据控制语言把授权决定告知系统; (2)系统把授权的结果存入数据字典; (3)当用户提出 操作请求时,系统根据授权情况进行检查, 以决定是否执行。

2015/9/23

数据库系统数据库系统

137

第三章 关系数据库标准语言——SQL
2、权力的授予与收回 授予: 若干权力 操作对象

GRANT 权力 [,权力 ] … [ ON 对象类型 对象名 ] TO 用户名 [,用户名] …

获得权力的用户

[ WITH GRANT OPTION ];
有此项,被授权用户可再授权给其他用户 收回: REVOKE 权力 [,权力 ] … [ ON 对象类型 对象名 ] FROM 用户名 [,用户名] …;

3、操作权力分类: 见P130表3.4
2015/9/23 数据库系统数据库系统 138

第三章 关系数据库标准语言——SQL
4、示例: 见P131 5、说明 ? 数据库的属主、表的属主、数据库对象的属主在他创建 的对象上具有一切可能的权力,其他用户得不到主人的授 权就不能在该对象上操作; ? SQL的授权机制十分灵活,各种系统又作了适当的补充 , 使用十分方便; ? SQL的安全性控制除了上述授权机制外,还可设置口令 进一步保密。 本节开头
2015/9/23

本章开头
数据库系统数据库系统

下一节
139

第三章 关系数据库标准语言——SQL
§7 嵌入式SQL 一、SQL的使用方式

1、交互式:在终端上每输入一条SQL语句,系统立即执行
,然后等待用户输入下一条语句。 2、自编程式:在实际的DMBS中,都对SQL进行了扩充, 增加了条件、循环等控制语句,并提供编程机制。如SYBASE 中,用户可以编写存储过程并调用它。 3、嵌入式(嵌入到某种主语言中使用): 宿主语言负责:运算、处理、流程控制等 SQL负责:数据库操作
2015/9/23 数据库系统数据库系统 140

第三章 关系数据库标准语言——SQL
二、嵌入式SQL使用时的问题 必须解决和主语言相互配合、连接等问题 1、标识SQL语句 用前缀,如EXEC SQL或$等,标记SQL语句的开始; 用END-EXEC或分号‘;’等标记SQL语句的结束。 SQL语句标识是通知主语言的预编译程序将SQL语句转 化为等价的主语言语句,然后再由编译程序形成目标代码 2、SQL语句与主语言之间的通信 (1)通过SQL通信区(SQLCA)将SQL语句的执行状 态传递给主语言。 SQLCA是一个数据结构,其中有一个重 要变量SQLCODE,存放SQL语句是否执行成功的信息, 每执行一个SQL语句,主语言都应测试该变量。
2015/9/23 数据库系统数据库系统 141

第三章 关系数据库标准语言——SQL
(3)SQL语句中可使用主语言的程序变量(叫主变量 ),但要加前缀标志,一般用冒号‘:’。 (4)SQL语句和主语言的数据交换一般通过字段变量 和主变量进行,但两者数据类型要匹配

(5)一个SQL语句可以产生一组记录,而主语言一次
只能处理一个记录,为此需协调两种方式 办法:用游标(Cursor),有的叫位置指针 (6)通常用CONNECT语句来连接(申请使用)数据库

例子见P136
2015/9/23 数据库系统数据库系统 142

第三章 关系数据库标准语言——SQL
三、不需游标的SQL语句 ? 说明性语句

? 数据定义语句
? 数据控制语句

}

最简单的一类语句,不需返回 结果,不使用主变量,在主语 言中只需加前缀EXEC SQL和 语句结束符即可。

? 查询结果为单记录的SELECT语句

? 非CURRENT形式的UPDATE语句
? INSERT语句

? 非CURRENT形式的DELETE语句

}

一般均使 用主变量

1、说明、数据定义、数据控制语句 见教材P137-138
2015/9/23 数据库系统数据库系统 143

第三章 关系数据库标准语言——SQL
2、查询结果为单记录的SELECT语句 查询结果存 入这三个主 例 根据主变量的值查找学生的信息 变量中 EXEC SQL SELECT S#,C#,G INTO :SNO,:CNO,:G :GID FROM SC WHERE S#= :GS AND C#=:GC; 指示变量 ,<0说明 取得的G 为空值

待查的学号存在 GIVENS#中

? SELECT语句的INTO、WHERE、HAVING子句中可使

用主变量
? 可在INTO子句中使用指示变量,以指明某字段是否空值 ? 若SQLCODE=100,说明没有满足条件的记录

?当查询到的记录多于1条时,在SQLCODE中返回错误信息
2015/9/23 数据库系统数据库系统 144

第三章 关系数据库标准语言——SQL
3、非CURRENT形式的UPDATE语句 例 将计算机系全体学生的成绩置为空值

GID = -1;
EXEC SQL UPDATE SC SET G = :GG :GID

这里使用了值为负的指示 变量GID, 主变量GG可为 任意值

WHERE ―CS‖=
(SELECT SD FROM S WHERE S.S#=SC.S#); ? WHERE、SET子句中可以使用主变量,同时SET子句中 还可以使用指示变量 ?通过检查SQLCA的值,判别更新是否成功
2015/9/23 数据库系统数据库系统 145

第三章 关系数据库标准语言——SQL
4、非CURRENT形式的DELETE语句 例 学号在主变量X1和X2之间的学生已毕业,删除他们的 信息。 先删除他们的选课信息 EXEC SQL DELETE FROM SC WHERE S# BETWEEN :X1 AND :X2;

再删除他们的基本情况信息
EXEC SQL DELETE FROM S
2015/9/23 数据库系统数据库系统

? WHERE子句 中可使用主变量

WHERE S# BETWEEN :X1 AND :X2;
146

第三章 关系数据库标准语言——SQL
5、INSERT语句 例 插入一条学生选课记录 GID = -1; EXEC SQL INSERT INTO SC(S#,C#,G) VALUES(:SNO, :CNO, :GG :GID); 四、使用游标的SQL语句 欲插入记录的值由主语 言存放在三个主变量中 ,GID指示成绩字段值 为空值,GG可为任意值

下列情况必须使用游标
? 查询结果为多条记录的SELECT 语句 ? CURRENT形式的UPDATE语句

? CURRENT形式的DELETE语句
2015/9/23 数据库系统数据库系统 147

第三章 关系数据库标准语言——SQL
1、查询结果为多条记录的SELECT语句 如:查找由主变量DEPT中给出的某个系的全体学生信息 EXEC SQL DECLARE SX CURSOR FOR 定义游标 SELECT S#,SN,SA FROM S WHERE SD=:DEPT; EXEC SQL OPEN SX; 打开游标 DO WHILE EXEC SQL FETCH SX INTO :S#, :SNAME, :AGE; …… 推进游标 END; 关闭游标 EXEC SQL CLOSE SX;
2015/9/23 数据库系统数据库系统 148

第三章 关系数据库标准语言——SQL
EXEC SQL DECLARE SX CURSOR FOR S:S# SELECT S#,SN,SA 游标SX S0 FROM S S1 游标SX WHERE SD=:DEPT; S2 S3 EXEC SQL OPEN SX; ? S4 DO WHILE S5 EXEC SQL FETCH SX S6 S7 INTO :S#, :SNAME, :AGE; SN SD SA X MA 18 A CS 20 B CS 21 C MA 19 D CI 19 E MA 20 F CS 22 G CI 21

主变量 S# SNAME AGE 假设DEPT中为‘CS‘ END; S1 A 20 EXEC SQL CLOSE SX;
2015/9/23 数据库系统数据库系统 149

……

第三章 关系数据库标准语言——SQL
EXEC SQL DECLARE SX CURSOR FOR S:S# SN SD SA S0 X MA 18 FROM S S1 A CS 20 WHERE SD=:DEPT; S2 B CS 21 游标SX S3 C MA 19 EXEC SQL OPEN SX; ? S4 D CI 19 DO WHILE S5 E MA 20 EXEC SQL FETCH SX S6 F CS 22 INTO :S#, :SNAME, :AGE; S7 G CI 21 …… 假设DEPT中为‘CS‘ 主变量 S# SNAME AGE END; S1 A S2 B 20 21 EXEC SQL CLOSE SX; SELECT S#,SN,SA
2015/9/23 数据库系统数据库系统 150

第三章 关系数据库标准语言——SQL
EXEC SQL DECLARE SX CURSOR FOR S:S# SN SD SA S0 X MA 18 FROM S S1 A CS 20 WHERE SD=:DEPT; S2 B CS 21 S3 C MA 19 EXEC SQL OPEN SX; S4 D CI 19 DO WHILE ? S5 E MA 20 EXEC SQL FETCH SX 游标SX S6 F CS 22 INTO :S#, :SNAME, :AGE; S7 G CI 21 …… 假设DEPT中为‘CS‘ 主变量 S# SNAME AGE END; S2 S6 B F 21 22 EXEC SQL CLOSE SX; SELECT S#,SN,SA
2015/9/23 数据库系统数据库系统 151

第三章 关系数据库标准语言——SQL
EXEC SQL DECLARE SX CURSOR FOR S:S# S0 FROM S S1 WHERE SD=:DEPT; S2 S3 EXEC SQL OPEN SX; S4 DO WHILE S5 EXEC SQL FETCH SX S6 INTO :S#, :SNAME, :AGE; S7 游标SX …… SELECT S#,SN,SA END; EXEC SQL CLOSE SX;
2015/9/23 数据库系统数据库系统

SN SD SA X MA 18 A CS 20 B CS 21 C MA 19 D CI 19 E MA 20 F CS 22 G CI 21

主变量 S# SNAME AGE

S6

F

22
152

第三章 关系数据库标准语言——SQL
2、CURRENT形式的UPDATE和DELETE语句 可修改或删除当前活动游标所指向的记录. 例子见P144-146

本节开头
2015/9/23

本章开头
153

数据库系统数据库系统

第四章
本章要求:

关系系统及其查询优化

1、掌握关系系统的有关概念
2、了解全关系系统的十二条基本准则 3、掌握查询优化的一般策略 4、掌握关系代数的等价变换规则 5、掌握关系代数表达式的优化算法和优化的一般步骤 本章内容:
请选择内容

§1 关系系统
§2 关系系统的查询优化 返回

2015/9/23

数据库系统

154

第四章

关系系统及其查询优化 §1 关系系统

一、关系系统的定义 1、关系模型: 数据结构: 关系(二维表) 数据操纵: 关系代数(或关系演算) 完整性约束:实体完整性、参照完整性、用户定义的完整性 2、关系系统的定义 要求过于严格 ? 关系系统是关系数据库系统的简称 ? 从概念上讲,支持关系模型的系统称为关系系统。 ? 按最小要求定义关系系统: 一个系统称为关系系统,当且仅当 (1)支持关系数据结构; (2)支持选择、投影和连接运算。 对运算不要求定义任何物 理存取路径。
2015/9/23 数据库系统 155

第四章

关系系统及其查询优化

二、关系系统的分类 按对关系模型的支持程度来分 数据操纵
S M

结构

I

完整性 1、表式系统 仅支持关系结构,

SS I

M

不支持集合级操作 如:倒排表
2015/9/23

数据库系统

156

第四章

关系系统及其查询优化

2、(最小)关系系统 支持关系结构, 支持选择、投影和连接运算 如:FoxBASE、FoxPro 3、关系上完备的系统 支持关系结构, 支持所有的关系代数操作 SS I M M M SS I MM

如:SYBASE、ORACLE、DB2

2015/9/23

数据库系统

157

第四章

关系系统及其查询优化

4、全关系系统 支持关系模型的所有特征 SYBASE、ORACLE、 DB2等系统已接近这个目标 三、全关系系统的十二条基本准则 基础(准则 0):关系型DBMS必须能完全通过它的关系能 力来管理数据库 在关系一级上支持数据的插入、删除、修改, 没有任何操作必须通过非关系的能力才能实现
2015/9/23 数据库系统 158

S S S II

M M

第四章

关系系统及其查询优化

准则1:信息准则。逻辑上可用一种方法(表中的值)来表示 所有信息。 用户数据、元数据、索引、应用元数据统一用表格来表示
好处:? 提高用户生产率 ? 便于DBA维护数据库

? 便于与其它软件接口 准则2:保证访问准则。依靠表名、主键、列名的组合,保证 能以逻辑方式(而不是物理方式)访
问到每一个数据项。 准则3:空值的系统化处理。

好处:? 完善完整性约束 ? 对库函数计算的准确性极为重要
2015/9/23 数据库系统 159

第四章

关系系统及其查询优化

准则4:基于关系模型的动态的联机数据字典。 数据库自身的描述(元数据)也用关系,且授权用户 也可以查询。 好处:? 学习简单 ? 授权用户可扩充数据字典 准则5:统一的数据子语言准则。 一种语言全面支持以下功能: 数据定义、视图定义 数据操作 完整性约束 授权 事务处理功能
2015/9/23 数据库系统 160

第四章

关系系统及其查询优化

准则6:视图更新准则。所有理论上可更新的视图也应该允许 由系统更新。 提高逻辑独立性

准则7:高级的插入、修改、删除操作。把一个基本关系或导 出关系作为单一的操作对象进行处理。
? 简化用户操作 ? 便于系统优化 ? 便于分布式处理 准则8:数据物理独立性。 准则9:数据逻辑独立性。 准则10:数据完整性的独立性。 完整性约束条件必须是用数据子语言定义并存储在数 据字典中。 好处:
2015/9/23 数据库系统 161

第四章

关系系统及其查询优化

准则11:分布独立性。 数据子语言能使应用程序和终端活动在下列情况下保持 逻辑不变性: ? 首次分布数据时; ? 数据重新分布时。 准则12:无破坏准则。 如果一个关系系统具有一个低级(指一次一记录)语言, 则这个低级语言不能违背或绕过完整性准则。 E. F. Codd提出的12条准则

本节开头
2015/9/23

本章开头
数据库系统

下一节
162

第四章

关系系统及其查询优化

§2 关系系统的查询优化 关系数据语言只需用户指出“干什么”,不必指出“怎 么干”,为什么能做到这一点? 一个重要原因就是系统能自动进行查询优化。 查询优化的总目标: 选择有效的策略,求得给定的关系表达式的值。 一、为什么要进行查询优化? 例:求选修了课程C2的学生姓名 SELECT S.SN

FROM S, SC
WHERE S.S# = SC.S# AND SC.C# = ?C2‘;
2015/9/23 数据库系统 163

第四章

关系系统及其查询优化

也可用SQL语言如下实现: SELECT SN FROM S WHERE S.S# IN ( SELECT SC.S# FROM SC WHERE C# = ?C2‘ ) ; 对于一个复杂的查询,不同的用户可能会写出许许多多不

同的查询方法。这些方法有的简单,有的复杂。它们的执行结
果是一样的,但执行效率可能是不一样的。系统能解决这一问 题吗?
2015/9/23 数据库系统 164

第四章

关系系统及其查询优化

对这一查询,可以考虑下面几种实现方式: 1、先求S和SC的笛卡尔积,然后从中选出两学号字段值相等、

课程号为C2的元组: Q1 = ? SN (? S.S#=SC.S# ? SC.C#=?C2‘ (S?SC))
2、先做S和SC的自然连接,然后从中选出课程号为C2的元组: Q2 = ? (? (S SN SC.C#=?C2‘ SC))

3、先从SC中选出课程号为C2的元组,然后将该结果与S 连接: Q3 = ? (S SN
2015/9/23

?

(SC)) SC.C#=?C2‘
165

数据库系统

第四章

关系系统及其查询优化

分析三种实现策略的执行时间: 设有1000学生记录,10000选课记录,选修C2课程的学生有50名。 1、第一种策略: Q1 = ? SN (? S.S#=SC.S# ? SC.C#=?C2‘(S?SC)) (1)计算广义笛卡尔积 S?SC: 执行方式: 读SC表 读S表 S1 A CS 20 S1 C1 A S2 B CS 21 S1 C2 A S1 C3 A S3 C MA 19
每次读 S5 E MA 22 若干块 S6 F CS 19
2015/9/23

S4 D CI 19

每次读 一块
数据库系统

S?SC存于临时文件中 S1 A CS 20 S1 C1 A S1 A CS 20 S1 C2 A S1 A CS 20 S1 C3 A S2 B CS 21 S1 C1 A S2 B CS 21 S1 C2 A S2 B CS 21 S1 C3 A …… …… S6 F CS 19 S1 C1 A S6 F CS 19 S1 C2 A S6 F CS 19 S1 C3 A
166

第四章
读S表

关系系统及其查询优化
读SC表

S1 A CS 20 S2 B CS 21
S3 C MA 19 S4 D CI 19 S5 E MA 22 S6 F CS 19

S1 C5 C1 B A S1 S1 C1 C2 B A S2 S1 C2 C3 C A S2

读下一块

相当于 外循环

相当于 内循环

S?SC存于临时文件中 S1 A CS 20 S1 C1 A S1 A CS 20 S1 C2 A S1 A CS 20 S1 C3 A S2 B CS 21 S1 C1 A S2 B CS 21 S1 C2 A S2 B CS 21 S1 C3 A …… …… S6 F CS 19 S1 C1 A S6 F CS 19 S1 C2 A S6 F CS 19 S1 C3 A S1 A CS 20 S1 C5 B S1 A CS 20 S2 C1 B S1 A CS 20 S2 C2 C …… ……
167

2015/9/23

数据库系统

第四章

关系系统及其查询优化

设一块能装10个学生记录或100个选课记录,每次在内存中 存放5块S的元组、1块SC的元组,则S表和SC表的总块数各为 100。外循环一次,内循环20次,要读取的总块数为 100 + 100?20 = 2100块 连接后的元组数为 1000 ? 10000 = 1千万,设每块能装10个元组, 则 S ? SC的总块数为1百万块 设每秒能读写20块,则 读的时间:2100块? 20块/秒 = 105秒 写的时间:1000000块? 20块/秒 = 50000秒 (2)依次读入S ? SC的元组,然后执行选择:

读的时间:1000000块 ? 20块/秒 = 50000秒 满足条件的元组50个,设全部放入内存(不再临时存储)
2015/9/23 数据库系统 168

第四章

关系系统及其查询优化

(3)在上步基础上执行投影得最终结果(此步时间不计)。 第一种策略的总时间为: 105 + 50000 + 50000 ? 10万秒(近28小时) 2、第二种策略 Q2 = ? (? (S SC)) SN SC.C#=?C2‘ (1)计算自然连接 读取S表和SC表的策略不变,执行时间还是105秒。 因为SC表中的每一个学号都在S表中出现,而S表中无重复 学号,故连接后的表和SC表的行数一样,为10000行,将它 们临时存入盘中需 (10000 ? 10)块? 20块/秒 = 50秒 计算自然连接需时:105 + 50 = 155秒
2015/9/23 数据库系统 169

第四章
(2)执行选择运算

关系系统及其查询优化

主要为读取中间文件的时间:为50秒 (3)把上一步结果投影,时间忽略不计 第二种策略的总时间为: 155 + 50 = 205秒 3、第三种策略

Q3 = ? (S SN

? (SC)) SC.C#=?C2‘

(1)先对SC表作选择 只需读一遍SC表,需时 100块? 20块/秒 = 5秒
中间结果只有50个记录,不需使用中间文件 (2)作自然连接 只需读一遍S表,边读边和内存中的中间结果连接,结果 仍为50个元组需时 5秒
2015/9/23 数据库系统 170

第四章

关系系统及其查询优化
5 + 5 = 10秒

(3)把上一步结果投影,时间忽略不计

第三种策略的总时间为:

结论:不同的查询策略其执行时间可能差别很大 二、优化的一般策略 1、选择、投影运算应尽可能先做 ? SN (? SD=?CS‘ (S )) SN SD SA A CS 20 B CS 21 C MA 19 D CI 22 ??

表S S# 好处:减少下一步运算的数据量 S1 S2 2、把选择和投影运算同时进行 S3 S4 好处:减少扫描关系的次数

2015/9/23

数据库系统

171

第四章

关系系统及其查询优化
C# C3 C2 C5 C4 C1 C3 C2 C1 C4 C2 C3 C3 C5 C2 C4 C5 C5 G B A B A B B C A C B A C D C B B A
172

3、在执行连接前对文件适当地预处理 SC: S# S4 S1 例如:计算 S SC S1 S6 S: S# SN SD SA S2 S5 S1 A CS 20 S2 执行连接时,对S 表 S2 B CS 21 S1 只需扫描一遍,但若S S3 C MA 19 S2 S3 S4 D CI 19 的元组不能整个放入 S1 S5 E MA 20 内存,则S需多少次读 S3 S6 F CS 22 S4 入内存,对SC S5 表就要扫描多少遍 S3 S5 S6
2015/9/23 数据库系统

第四章
若对S表和SC表 按连接字段先排序
或索引,效果如何? 对S表和SC表都 只需一遍扫描

关系系统及其查询优化
S: S# SN SD SA S1 S2 S3 S4 S5 S6 A B C D E F CS 20 CS 21 MA 19 CI 19 MA 20 CS 22

SC:

S# C# G S1 S1 S1 S1 S2 S2 S2 S3 S3 S3 S4 S4 S5 S5 S5 S6 S6 C1 C2 C3 C5 C1 C2 C4 C2 C3 C4 C3 C5 C2 C3 C5 C4 C5 A A A B B C C B C B B D C B B A A

2015/9/23

数据库系统

173

第四章

关系系统及其查询优化

4、把投影同其前或其后的双目运算结合起来 如: ? S#,SN,C#,G(S SC)

每形成一个连接后的元组,就立即取出投影字段。而不是先 连接形成一个临时关系,然后在再此临时关系上投影。 又如: SC (? S#,SN ( S))

每取出S的一个元组,先取出投影字段,然后与SC进行连接 5、把某些选择和笛卡尔乘积结合起来成为连接运算 6、找出公共子表达式
2015/9/23 数据库系统 174

第四章

关系系统及其查询优化

三、关系代数等价变换规则

设E、E1、E2是关系代数表达式。
1、关系代数表达式的等价 若用相同的关系代替E1、E2中相应的关系变量后所得的

结果关系相同,则称E1、E2等价,记作 E1 ? E2。
2、一元运算的串接定律(幂等律) (1)投影的串接定律 ? (? (E))? ? (E) A1,A2,…,An B1,B2,…,Bm A1,A2,…,An

其中{A1,A2,…,An} ? {B1,B2,…,Bm}

2015/9/23

数据库系统

175

第四章
图示: A1 B1 A2 B2 B3

关系系统及其查询优化
A3 B4 A1 A2 A3

(2)选择的串接定律 ? F1 (? (E))? ?F1?F2 (E) F2

2015/9/23

数据库系统

176

第四章
3、二元运算的交换律

关系系统及其查询优化

笛卡尔积: E1?E2 ? E2?E1 连 接: E1 F E2 ? E2 F E1

自然连接: E1
4、二元运算的结合律

E2 ? E2

E1

笛卡尔积: (E1?E2)? E3 ? E1?(E2? E3)
自然连接: ( E1 F1 自然连接: ( E1
2015/9/23

E2) E2)

F2

E3 ? E1 E3 ? E1

(E2 E3) F2 F1 (E2 E3)
177

数据库系统

第四章

关系系统及其查询优化

5、两个运算间的交换律 (1)选择和投影: ? (? (E))? ? (? (E)) A1,A2,…,An F F A1,A2,…,An 其中F只涉及{A1,A2,…,An}的属性 A1 A2 A3 A1 A2 A3

结果相同

先投影后选择
2015/9/23 数据库系统

先选择后投影
178

第四章

关系系统及其查询优化

若F中有不属于{A1,A2,…,An}的属性{B1,B2,…,Bm},则 ? (? (E)) 无意义, F A1,A2,…,An 但根据投影的串接定律和上面的投影与选择的交换律,有: ? A1,A2,…,An(? F (E)) ?? ?? (? (? (E))) A1,A2,…,An A1,A2,…,An ,B1,B2,…,Bm F (? (? (E))) A1,A2,…,An F A1,A2,…,An , B1,B2,…,Bm

(2) 选择与笛卡尔积
若F只涉及到E1中的属性,则? F (E1?E2)? ? F(E1)? E2
2015/9/23 数据库系统 179

第四章

关系系统及其查询优化

6、一元运算对二元运算的分配律 (1)选择对笛卡尔积的分配律 若F=F1?F2,F1只涉及E1中的属性,F2只涉及E2中的属性, 则 ?F (E1?E2)? ? F1 (E1)? ? F2 ( E2) S1 如:? (S?SC) S1 SD=?CS‘?G=?A‘ S1 S1 ?? (S)? ? G=?A‘ ( SC) S1 SD=?CS‘ S2 S2 S表 SC表 S2 S2 S1 A CS 20 S1 C1 A S2 笛卡尔积 S2 B MA 21 S1 C2 A S3 S3 S3 C CS 19 S2 C2 A S3 S3 C1 B S3 S3 C3 A S3
2015/9/23 数据库系统

A A A A A B B B B B C C C C C

CS CS CS CS CS MA MA MA MA MA CS CS CS CS CS

20 20 20 20 20 21 21 21 21 21 19 19 19 19 19

S1 S1 S2 S3 S3 S1 S1 S2 S3 S3 S1 S1 S2 S3 S3

C1 C2 C2 C1 C3 C1 C2 C2 C1 C3 C1 C2 C2 C1 C3

A A A B A A A A B A A A A B A

180

第四章

关系系统及其查询优化

(2)投影对笛卡尔积的分配律 ? (E1?E2) A1,A2,…,An, B1,B2,…,Bm ?? (E1)? ? (E2) A1,A2,…,An B1,B2,…,Bm 其中A1,A2,…,An是E1的属性, B1,B2,…,Bm是E2的属性。 (3)选择对连接的分配律

若F=F1?F2,F1只涉及E1的属性,F2只涉及E2的属性,则 ?F (E1 E2)? ? F1 (E1) ? F2 ( E2) F3 F3 因为:
? (E1 E2) ? ? (? (E1?E2))? ? (? (E1?E2)) F F3 F F3 F F3 ? ? ( ? ( E1)? ? ( E2))? ? (E1) ? ( E2) F1 F3 F1 F2 F3 F2
2015/9/23 数据库系统 181

第四章

关系系统及其查询优化

(4)投影对连接的分配律 ? (E1 E2) A1,A2,…,An, B1,B2,…,Bm F ?? (E1) ? (E2) A1,A2,…,An B1,B2,…,Bm F 其中F只涉及 {A1,A2,…,An, B1,B2,…,Bm}中的属性 若F涉及{A1,A2,…,An, B1,B2,…,Bm}以外的属性,可如下处理 ? SN,C#,G (S ?? SN,C#,G ? SC) S.S#=SC.S# (S S.S#,SN,SC.S#,C#,G SC) S.S#=SC.S#

?? SN,C#,G (?

(S) ? (SC)) SC ) S#,SN S.S#=SC.S# S#,C#,G
数据库系统 182

此处投影可去掉
2015/9/23

第四章

关系系统及其查询优化

(5)选择对并的分配律

?F (E1? E2)? ? F(E1)? ? F ( E2)
(6)投影对并的分配律 ? (E1?E2) A1,A2,…,An ?? (E1)? ? (E2) A1,A2,…,An A1,A2,…,An

(7)选择对差的分配律
?F (E1 – E2)? ? F(E1) – ? F ( E2)

2015/9/23

数据库系统

183

第四章

关系系统及其查询优化

四、关系代数表达式的优化

1、语法树 用来表示关系代数表达式的一棵树,其内结点表示一种
运算,叶结点表示一个关系。例:

SELECT S.SN FROM S, SC
WHERE S.S# = SC.S# AND SC.C# = ?C2‘; 可转化为如下关系运算: Project (SN) (Restrict (SC.C#=?C2‘) (Join (S.S#=SC.S#) (S,SC) ) ) Project (SN)

Restrict(SC.C#=?C2‘) Join(S.S#=SC.S#) S SC
184

语法树
2015/9/23 数据库系统

第四章

关系系统及其查询优化

为简化优化算法,可将关系代数运算限制在“并、差、笛卡 尔积、投影、选择”五种基本运算上。

Project (SN) Restrict(SC.C#=?C2‘) Join(S.S#=SC.S#) S SC S 规范化为

?SN ?SC.C#=?C2‘ ?S.S#=SC.S#
? SC

2015/9/23

数据库系统

185

第四章

关系系统及其查询优化

2、关系代数表达式的优化算法 输入:一棵关系代数表达式的语法树 输出:计算该表达式的程序 (1)分解选择

利用选择的串接定律,把形如 ?
变换为

(E)的式子 F1?F2???Fn

? (? F2 (?(? Fn (E)?)) F1

(2)选择下移
对每一个选择,利用“选择的串接定律、选择和投影的 交换律、选择对笛卡尔积的分配律、选择对并的分配律、 选择对差的分配律”尽可能把它移到树的叶端
2015/9/23 数据库系统 186

第四章
(3)投影下移

关系系统及其查询优化

对每一个投影,利用“投影的串接定律、选择和投影的 交换律、投影对笛卡尔积的分配律、投影对并的分配律” 尽可能把它移到树的叶端 (4)选择、投影合并 利用“投影的串接定律、选择的串接定律、选择和投影的 交换律”把选择和投影合并成单个选择、单个投影、或选择 后跟投影等三种情况,使多个选择和 / 或投影能同时执行、 或在一次扫描中完成

2015/9/23

数据库系统

187

第四章

关系系统及其查询优化
不超过别的 二元运算结点

(5)按点分组(每组只有一个二元运算) 把上面得到的语法树分组:

每个二元运算和它的 一元直接祖先 为一组。若它的后代 直到叶子全是一元运算,则也将它们并入该组。 但对于笛卡尔积,若后面(父结点)是不能与它结合为等

值连接的选择运算时,其一直到叶子的一元运算结点需单独
算一组。 (6)生成程序 按照每组的求值应在其后代组求值之后进行的顺序为每组 生成一个程序,以产生整个表达式的求值程序。
2015/9/23 数据库系统 188

第四章

关系系统及其查询优化

例子:考虑由以下关系组成的图书馆数据库

BOOKS(TITLE,AUTHOR,PNAME,LC-NO) BORROWERS(NAME,ADDR,CITY,CARD-NO)
LOANS(CARD-NO,LC-NO,DATE) 借书证号 图书编号 借出日期 查询:找出2000年01月01日前借出书籍的书名和借书人姓名。

用SQL 语言可如下表达: SELECT TITLE,NAME
FROM BOOKS,BORROWERS,LOANS

WHERE BOOKS.LC-NO=LOANS.LC-NO AND
BORROWERS.CARD-NO=LOANS.CARD-NO AND DATE < {2000-01-01};
2015/9/23 数据库系统 189

第四章

关系系统及其查询优化
转化为连接

转化为投影 SELECT TITLE,NAME FROM BOOKS,BORROWERS,LOANS

WHERE BOOKS.LC-NO=LOANS.LC-NO AND BORROWERS.CARD-NO=LOANS.CARD-NO AND DATE < {2000-01-01}; 把上述SQL语句转化为关系代数表达式: ? (? TITLE,NAME DATE<{2000-01-01} ( BOOKS ( BORROWERS LOANS))) 转化为选择

2015/9/23

数据库系统

190

第四章

关系系统及其查询优化

若把连接用笛卡尔积来实现,上式变为: ? ( TITLE,NAME ? ( DATE<{2000-01-01} ? TITLE,AUTHOR,PNAME,LC-NO, ( NAME,ADDR,CITY,CARD-NO,DATE ? BOOKS.LC-NO=LOANS.LC-NO AND BORROWERS.CARD-NO=LOANS.CARD-NO ( BOOKS ?( BORROWERS ? LOANS)))))

2015/9/23

数据库系统

191

第四章

关系系统及其查询优化

上述表达式的语法树 ? TITLE,NAME

? DATE<{2000-01-01}
? TITLE,AUTHOR,PNAME,LC-NO, NAME,ADDR,CITY,CARD-NO,DATE ? BOOKS.LC-NO=LOANS.LC-NO AND BORROWERS.CARD-NO=LOANS.CARD-NO ? BOOKS ? 根据算法第1步, 分解该选择

BORROWERS LOANS
2015/9/23 数据库系统 192

第四章

关系系统及其查询优化
选择和投影 可以交换

第1步优化(分解选择)后的语法树 ? TITLE,NAME ? DATE<{2000-01-01}

? TITLE,AUTHOR,PNAME,LC-NO, 分解之后 ? BOOKS.LC-NO=LOANS.LC-NO ? BOOKS ? LOANS
数据库系统 193

NAME,ADDR,CITY,CARD-NO,DATE

? BORROWERS.CARD-NO=LOANS.CARD-NO

BORROWERS
2015/9/23

第四章

关系系统及其查询优化
? DATE<{2000-01-01}

选择和投影交换后的语法树 ? TITLE,NAME

? TITLE ? DATE<{2000-01-01} ,AUTHOR,PNAME,LC-NO,
NAME,ADDR,CITY,CARD-NO,DATE ? TITLE ? DATE<{2000-01-01} 根据算法第 2步, ,AUTHOR,PNAME ,LC-NO , 该选择可下移 NAME,ADDR,CITY,CARD-NO ,DATE ? BOOKS.LC-NO=LOANS.LC-NO ? BORROWERS.CARD-NO=LOANS.CARD-NO ? BOOKS ? LOANS
数据库系统 194

该选择也可下移

BORROWERS
2015/9/23

第四章

关系系统及其查询优化
这两个投 影可以合 并(串接 )

第2步优化(选择下移)后的语法树 ? TITLE,NAME

? TITLE,AUTHOR,PNAME,LC-NO,
? BOOKS.LC-NO=LOANS.LC-NO ? BOOKS

NAME,ADDR,CITY,CARD-NO,DATE

? BORROWERS.CARD-NO=LOANS.CARD-NO ?

BORROWERS
2015/9/23

? DATE<{2000-01-01} LOANS
数据库系统 195

第四章

关系系统及其查询优化
不能!

第4步优化(合并投影)后的语法树
? TITLE,NAME 该投影能否下移?

怎么办?

? BOOKS.LC-NO=LOANS.LC-NO
? BOOKS ? BORROWERS.CARD-NO=LOANS.CARD-NO ? BORROWERS ? DATE<{2000-01-01} LOANS
2015/9/23 数据库系统 196

第四章

关系系统及其查询优化

另一种形式的投影与选择交换后的语法树 ? TITLE,NAME ? BOOKS.LC-NO=LOANS.LC-NO 该投影可下移

? TITLE,NAME,BOOKS.LC-NO,LOANS.LC-NO

? BOOKS
? BORROWERS.CARD-NO=LOANS.CARD-NO ? BORROWERS ? DATE<{2000-01-01}

LOANS
2015/9/23 数据库系统 197

第四章

关系系统及其查询优化

投影对笛卡尔积分配后的语法树 ? TITLE,NAME ? BOOKS.LC-NO=LOANS.LC-NO ? 对该投影 可同样 处理

? NAME,LOANS.LC-NO ? TITLE, BOOKS.LC-NO ? BORROWERS.CARD-NO=LOANS.CARD-NO

BOOKS

? ? DATE<{2000-01-01}

BORROWERS

LOANS
2015/9/23 数据库系统 198

第四章

关系系统及其查询优化

第3步优化(投影下移)后的语法树 ? TITLE,NAME
? BOOKS.LC-NO=LOANS.LC-NO ? ? TITLE, ? NAME,LOANS.LC-NO BOOKS.LC-NO ? BORROWERS.CARD-NO=LOANS.CARD-NO BOOKS ? ? LC-NO,CARD-NO ? DATE<{2000-01-01} LOANS
2015/9/23 数据库系统 199

? NAME, CARD-NO
BORROWERS

第四章

关系系统及其查询优化

对结点分组: 共分为二组 ? TITLE,NAME ? BOOKS.LC-NO=LOANS.LC-NO ? ? TITLE, ? NAME,LOANS.LC-NO BOOKS.LC-NO ? BORROWERS.CARD-NO=LOANS.CARD-NO BOOKS ? ? LC-NO,CARD-NO ? DATE<{2000-01-01} LOANS
2015/9/23 数据库系统 200

? NAME, CARD-NO
BORROWERS

第四章

关系系统及其查询优化

3、优化的一般步骤 (1)把查询转换成某种内部表示 如语法树

(2)按优化算法对语法树进行优化(标准形)
(3)选择低层的存取路径 充分考虑索引、数据的存储分布,然后选取存储路径 (4)生成查询计划,选择代价最小的 如对连接运算,考虑各种实现策略,从中选出代价最小的 作业:1、4

本节开头
2015/9/23

本章开头
数据库系统 201

第五章

关系数据理论

本章要求: 1、掌握为什么不合适的关系模式会带来插入异常、删除异常、 存储异常、修改困难等严重问题 2、深刻理解函数依赖、多值依赖等有关概念 3、掌握关系的1NF、2NF、3NF、BCNF、4NF的概念和特征 4、掌握函数依赖的Armstrong公理系统、求属性集的闭包算法 以及求极小函数依赖集的方法等 5、掌握模式分解的无损连接性和保持函数依赖性以及分解算法 本章内容:
§1 §2 §3 §4 §5
2015/9/23

为什么需要对关系模式规范化? 请选择内容 数据依赖 关系的范式 函数依赖的Armstrong公理系统 返回 关系模式的分解
数据库系统数据库系统 202

第五章
§1 据模式?

关系数据理论
问题的提出

一个基本的问题:给出一组数据,如何构造一个合适的数

例如:对关系模型,给了一组数据,应该构造几个关系?
每个关系由哪些属性组成?…… 这就是数据库逻辑设计问题 网状、层次模型的数据库设计,主要凭设计者的经验直观 地选择和确定实体集、属性以及实体间的联系。哪些实体应该 合并或分解以及如何合并和分解、每个实体中应该包括哪些属 性为宜、属性间的联系如何确定和处理等一系列问题的解决是

没有什么固定规则和理论可循的。
2015/9/23 数据库系统数据库系统 203

第五章

关系数据理论

关系数据库的设计是借助近代数学工具而提出来的,形成
了一整套定义、公理、定理及各种实用算法,产生了确定、评 价关系数据库模式的好方法。 关系数据库的规范化理论 ——数据库逻辑设计的有力工具 要考虑的几个问题: ? 为什么要规范化? 这就是本章的主题

? 怎样规范化?
? 规范化到什么程度后最合适? 本节首先用一个例子来说明对关系模式为什么要规范化, 不经过规范化会产生什么样的结果。
2015/9/23 数据库系统数据库系统 204

第五章

关系数据理论

例:假设车间考核职工完成生产定额的关系模式如下: W(工号,日期,姓名,工种,定额,超额,车间,车间主任) 比如设某工号某年月超额完成定额的20%,其记录的内容为: (1001,98年11月,张三,车工,180,20%,金工车间,李四) 该关系的主键为? 工号 ? 日期 该关系模式存在以下四个严重问题: (1)数据冗余大 对同一个人来说,其姓名、工种、车间、车间主任等多次重复 …… …… 1001,98年08月,张三,车工,???,???,金工车间,李四 1001,98年09月,张三,车工,???,???,金工车间,李四 1001,98年10月,张三,车工,???,???,金工车间,李四 1001,98年11月,张三,车工,???,???,金工车间,李四 …… ……
2015/9/23 数据库系统数据库系统 205

第五章
(2)插入异常

关系数据理论

应该存储的信息无法存储

若新调来一个职工并将他分配到某个车间,根据上述关 系模式,在对该职工统计工作之前,他的信息是装不进数据 库中的。因为他的日期值是空值,而日期是主键的属性之一 ,不允许为空。 (1005,NULL,天然,车工,NULL,NULL,金工车间,李四) (3)删除异常 不该删除的信息被删除

若想删除某人的所有定额完成情况,则该职工的其他信 息也都被删除。 比如在98年底要删除97年以前的所有定额完成信息,则 98年由于种种原因未参加现实工作的职工的所有信息全部被 删除。
2015/9/23 数据库系统数据库系统 206

第五章

关系数据理论

(4)修改困难,容易造成数据的不一致性 (也称更新异常)
若某车间换了主任,则该车间所有职工的上述记录都要修改; 又如某人换了车间,则其工种、车间、车间主任等信息都要修改 。 修改工作量大; 即使漏改一处都会造成数据的不一致性 ; 上例充分说明对关系模式若随意设计,其后果是严重的。 本章将要讨论产生上述问题的原因以及解决办法,即如何改 造一个不好的关系模式。这就是规范化理论要解决的主要问题 。
2015/9/23 数据库系统数据库系统 207

第五章

关系数据理论

比如,对于上述关系模式,若分解成下面三个关系,则前面 提到的几个问题将全部或部分地得到解决: 职工关系(工号,姓名,工种,车间号) 车间关系(车间号,车间名,车间主任) 定额关系(工号,日期,定额,超额,车间号)

本节开头
2015/9/23

本章开头
数据库系统数据库系统

下一节
208

第五章

关系数据理论

§2 数据依赖 数据模型中我们讨论了实体间的联系,同时提到实体内部 属性间也有联系。事实上上一节中的问题都是由于属性间的联 系引起的。 一、数据依赖

1、属性间的联系:也是1:1,1:n,m:n三种 ? 1:1联系:设A、B为某实体集中的两个属性的值集,如 果对于A中的任一值,B中至多有一个值与之 如:车间--主任 对应,且反之亦然。
? 1:n联系:设A、B为某实体集中的两个属性的值集,如 果对于A中的任一值,B中有多个值(包括0个 如:队长 ) --学号 与之对应;而对于B中的任一值,A中至多有 2015/9/23 209 数据库系统数据库系统 一个值与之对应。

第五章

关系数据理论

? m:n联系:设A、B为某实体集中的两个属性的值集, 如:学号--课程号 如果对于A中的任一值,B中有多个值(包 括0个)与之对应,且反之亦然。 实体间的联系表示实体之间相互依赖又相互制约的关系; 属性间的联系表示属性之间相互依赖又相互制约的关系。 2、数据依赖 通过一个关系中属性间值的相互关联(主要体现于值的 相等与否)体现出来的数据间的相互联系。 (是数据内在的性质,语义的体现) 两类最重要的数据依赖
2015/9/23

函数依赖

多值依赖
210

数据库系统数据库系统

第五章
二、关系的形式化定义 1、关系的两个主要方面 语法:属性的描述 语义:数据依赖

关系数据理论

2、关系模式:

R <U,D,dom,F>
关系名 属性组 U上的一组数据依赖 3、关系: 对关系模式 R<U, F>,当且仅当U上的一个关系r满足

F时,称r为关系模式 R<U, F>的一个关系。
2015/9/23 数据库系统数据库系统 211

第五章
三、函数依赖

关系数据理论

不严格地讲,函数依赖指的是一组属性值唯一决定另 一组属性值的这种数据依赖。
如学生关系中,当学号确定后,其姓名也就唯一确定了。 选课关系中,当学号和课程号确定后,其成绩也就唯一确 定了。 1、函数依赖(Functional Dependency,缩写FD): 设 R(U)是属性集U上的关系模式,X、Y是U的子集。若 对于R中的任意关系 r,对于 r中的任意两个元组u、v都有 u[X]=v[X] ? u[Y]=v[Y] 成立,则称X函数决定Y,或称Y函数依赖于X,记作X?Y。 称X为决定因素。
2015/9/23 数据库系统数据库系统 212

第五章

关系数据理论

例:对学生关系 S(S#,SN,SD,SA),有 S# ?SN, S# ?SD, S# ?SA 对选课关系 SC(S#,C#,G),有(S#,C# )? G 说明: ? 函数依赖类似于变量间的单值函数关系(一个自变量只

能对应一个

函数值),因此也称为单值函数依赖;
Y

? 若X?Y且Y?X ,则记作 X?Y; ? 若Y不函数依赖于X,则记作 X

函数依赖是指关系模式R的任 一关系都要满足的约束条件
2015/9/23 数据库系统数据库系统 213

第五章

关系数据理论

2、函数依赖与属性间的联系之关系 (1)若X、Y之间是“1:1联系”, 则存在函数依赖X?Y和 Y?X, 即X?Y. (2)若X、Y之间是“m:1联系”, 则存在函数依赖关系X?Y 。 (3)若X、Y之间是“m:n联系”, 则X、Y之间不存在函数 依赖关系。 3、函数依赖分类
(1)非平凡的函数依赖: X?Y,但Y? X。 (2)平凡的函数依赖: X?Y,但Y ? X。

(3)完全函数依赖:X?Y,且对任意的X‘? X,都有 Y。 记作 X f Y X‘ 如在 SC(S#,C#,G)中,(S#,C#)? G, f G。 G, C# G,因此(S#,C#) 但S#
2015/9/23 数据库系统数据库系统 214

第五章

关系数据理论

(4)部分函数依赖: X?Y,但Y不完全函数依赖于X。 p 记作 X Y 如在 S(S#,SN,SD,SA)中,因为 S#?SD, p 所以 (S#,SN) SD (5)传递函数依赖:若X?Y,Y X,Y?Z, 且Z?(X?Y)= ?,则称Z对X是传递函数依赖。 例如,在学生关系模式 S(S#,SN,SD,SA)中,增 加属性SL(系的位置),则 S#?SD,SD?SL,SD 传递 ,所以 S# SL。 S#

2015/9/23

数据库系统数据库系统

215

第五章

关系数据理论

四、多值依赖 (教材P178) 1、例子:设学校中一门课由多位教员讲授,他们使用相同
的参考书,比如: “物理”,教员为汪洋、大海,参考书为《普通物理学》 、

《光学原理》、 《物理习题集》
; “数学”,教员为大海、白云,参考书为《数学分析》、 《微分方程》、 《高等代数》; “计算”,教员为蓝天、白云,参考书为《数学分析》、 …… ……
2015/9/23 数据库系统数据库系统 216

第五章
课程C 物理 物理 物理 物理 物理 物理 数学 数学 数学 数学 数学 数学 计算 …… 2015/9/23 教员T 汪洋 汪洋 汪洋 大海 大海 大海 大海 大海 大海 白云 白云 白云 白云 ……

关系数据理论
该关系模式中,任 何两个属性都不能函 数决定第三个属性。 该关系模式存在

用模式为 TEACH(C,T,B)的关系表示上述数据: 参考书B 普通物理学 光学原理 物理习题集 普通物理学 光学原理 物理习题集 数学分析 微分方程 高等代数 数学分析 微分方程 高等代数 数学分析 …… 数据库系统数据库系统

冗余大、增删不方便
等问题。

没有函数依赖, 需要另行分析
217

第五章
课程C 教员T
物理 汪洋 物理 汪洋 物理 汪洋 物理 大海 物理 大海 物理 大海 数学 大海 数学 大海 数学 大海 数学 白云 数学 白云 数学 白云 计算 白云 …… 2015/9/23 ……

关系数据理论
在该关系模式中,对

参考书B

普通物理学 于一个(物理,普通物理 光学原理 学),有一组教员{汪洋 物理习题集 ,大海},而对于另一个 普通物理学 (物理,光学原理),对 光学原理 物理习题集 应的教员仍是{汪洋,大 数学分析 海}。因此,所对应的教 微分方程 员只与课程的值有关而与 高等代数 参考书的值无关。 数学分析 微分方程 高等代数 这是产生问题的原因吗? 数学分析 …… 218 数据库系统数据库系统

第五章

关系数据理论

2、多值依赖(MultiValued Dependency,缩写为MVD) 设 R(U)是属性集U上的关系模式,X、Y、Z是U的子集, 且Z=U?X?Y,多值依赖X??Y成立当且仅当对R(U)的任一关

系r,任给的一对(x,z)值有一组Y的值,这组值仅仅取决于
x值而与z值无关。 课程C 教员T 参考书B 称X多值决定Y或Y多值依赖于X。 物理 汪洋 普通物理学 物理 汪洋 光学原理 例如,在关系模式TEACH中 物理 汪洋 物理习题集 有 C??T 物理 大海 普通物理学 物理 大海 光学原理 直观上看,若X??Y, 物理 大海 物理习题集 数学 大海 数学分析 则X的一个值唯一决定一组 数学 大海 微分方程 Y值,且这组值与X、Y之外 数学 大海 高等代数 数学 白云 数学分析 的属性值无关 计算 白云 数学分析 2015/9/23 数据库系统数据库系统 …… …… …… 219

第五章

关系数据理论

多值依赖的另一等价定义: 多值依赖X??Y成立当且仅当对R(U)的任一关系r,若 存在元组s、t使得s[X]=t[X],则必存在元组w、v?r(w、v 可以与s、t相同),使得w[X]=v[X]=t[X],而w[Y]=t[Y], w[Z]=s[Z],v[Y]=s[Y],v[Z]=t[Z]。 X s t w Y s[Y] t[Y] w[Y] v[Y] Z s[Z] t[Z] 左图直观显示, w[Z] v[Z]
数据库系统数据库系统

交换s、t的Y值 所得新元组仍在r中

x决定一组y值, 这组值与z无关
220

v
2015/9/23

第五章

关系数据理论

由前面例子,可看出X、Y、Z之间有下述关系: 汪洋 物理 大海

普通物理学 光学原理 物理习题集
大海 白云 完全二分图

数学
数学分析
2015/9/23

微分方程

高等代数
221

数据库系统数据库系统

第五章
3、多值依赖的性质:

关系数据理论

(1)对称性:若 X??Y, Z=U?X?Y,则 X??Z。 (2)函数依赖可看成是多值依赖的特例:若 X?Y,则 X??Y (3)若U=XY(表示X ? Y),则 X??Y显然成立。 (这种多值依赖无任何实际意义,故称为 平凡的多值依赖 ) 4、多值依赖与函数依赖的区别 (1)函数依赖X?Y的有效性仅取决于X、Y,与X、Y之外 的属性无关:

(R)上成立 X?Y在? (R)上成立 XY W 其中W满足 XY ? W ? U(U是关系模式R的属性集)。 Y Z R(U): X X是否函数决定Y
与这一部分属性无关
2015/9/23

X?Y在?

W

数据库系统数据库系统

222

第五章

关系数据理论

多值依赖X??Y的有效性与X、Y之外的属性范围有关: 若X??Y在U上成立,则在W( XY ? W ? U)上也成立, 可缩小范围但不一定能扩大范围 但反之不然。 R(U): X Y Z

X是否多值决定Y 与这一部分属性密切相关
W X??Y在U上成立 反之 不成立 X??Y在W上也成立 W

R(W):X

Y

2015/9/23

数据库系统数据库系统

223

第五章

关系数据理论

X??Y在W上成立, 不一定有 X??Y在U上也成立 例如,在前面的例子中,若增加属性“教室”(R),则在 {C,T,B,R}上C??T不再成立。因为若汪洋在一号教室上 物理课,大海在二号教室上物理课,关系中会有下述两个元组 R T : C 物理 汪洋 普通物理学 一号教室 但交换汪洋和大海 …… …… 物理 大海 普通物理学 二号教室 后的两个元组不存在 …… …… W (2)对函数依赖,若X?Y,则对Y的任意子集Y‘,都有X?Y‘ 对多值依赖,没有上述性质。 即 X??Y成立
2015/9/23

不能保证 X??Y‘成立
数据库系统数据库系统 224

第五章
例:

关系数据理论
在U上C ??{T,R}, 但C ??T不成立,因

C R T 物理 汪洋 普通物理学 一号教室 …… …… 物理 大海 普通物理学 二号教室 …… ……
五、关键字

为交换汪洋和大海后
的两个元组不存在

从函数依赖的角度给关键字一个形式化的定义。 1、候选关键字和主关键字: 设K是R<U, F>中的属性或属性组合, f 若K U,则称K为U的候选关键字(候选码); (主键、主码)。
2015/9/23 数据库系统数据库系统 225

比以前的直观定义 准确、严谨

若候选关键字多于一个,则选定其中的一个作为主关键字

第五章

关系数据理论
? K能唯一确定 一个元组 ? K中无多余属性

例:借书证关系 C(CARD#,S#,SN,SD ) CARD#、S#都是候选关键字

通常选择CARD#作为主键 2、外键(外部码) 若R<U, F>中的属性或属性组合X不是R的关键字,但X是 另一个关系的关键字,则称X是R的外键。
主键与外键提供了一个表示关系间联系的手段 3、全键(All-key,全码) f 若R<U, F>的整个属性组是关键字,即U 是全键。
2015/9/23 数据库系统数据库系统 226

U,则称U

第五章

关系数据理论

例:关系模式 R(P,W,A) 注意: 一般来讲,全键是没有什 演奏者 作品 听众 (P,W,A)是R的全键。 么实际意义的。主键包含的 属性应尽可能少为好。

4、主属性和非主属性 主属性: 包含在某个候选关键字中的属性
非主属性:不包含在任何侯选关键字中的属性 例:SC(S#,C#,G)中, (S#,C#)是关键字,故S#,C#是主属性 G不包含在任何关键字中 ,故G是非主属性。
2015/9/23 数据库系统数据库系统 227

第五章

关系数据理论

§3 关系的范式 本节讨论下述问题: ? 如何根据关系模式属性间的数据依赖情况来判断它是否 具有某些不合适的性质? ? 如何将具有不合适性质的关系模式转换为更合适的形式 ? 一、规范化 1、范式(Normal Form) 按关系模式所具有的数据依赖性质对关系模式的分类 。也就是关系的规范化程度。 满足不同程度要求的为不同范式。 2、规范化 把一个低一级范式的关系模式通过模式分解转化为若 干个高一级的关系模式的过程。
2015/9/23 数据库系统数据库系统 228

第五章

关系数据理论

二、第一范式(1NF) 1、定义:关系的每个分量必须是不可再分的数据项。 记作R?1NF。(每个属性必须是原子的) 2、说明: ? 属性不可再分(不允许出现嵌套的属性定义) 这两个表 ? 属性下的值不可再分(不允许出现多个值) 都可变为 ? 这是对关系的最起码的要求,但远远不够。 规范关系 (满足1NF的关系称为规范关系) 例:借书表 例:职工情况表
工 资 职工 部门 …… 基本工资 奖金 号 借书人 所借书名 借书日期

张三
李四

B1 B2 B3 B2 B5

D1 D2 D3
D3
229

2015/9/23

数据库系统数据库系统

第五章

关系数据理论

3、仅属于1NF的关系模式可能会产生的问题: 例:车间考核职工完成生产定额的关系模式:

W(工号,日期,姓名,工种,定额,超额,车间,车间主任) 主属性 非主属性 显然W? 1NF,但第一节中我们已讨论知它有 四个严重问题 四个严重问题 因此仅是第一范式的关系模式完全不能满足需要。 数据冗余 插入异常 删除异常 修改困难 分析出现问题的原因: 工号函数决定非主属性姓名、工种、车间、车间主任。因 此,关键字(工号,日期)部分函数决定这些属性。 这显然是产生冗余的一个主要原因。
三、第二范式(2NF) 1、定义:若 R?1NF,且每一非主属性都完全函数依赖于R的 码,则称R是第二范式,记作R ?2NF。
2015/9/23 数据库系统数据库系统 230

第五章

关系数据理论

2、属于1NF但不属于2NF的例子:
? 关系模式W(工号,日期,姓名,工种,定额,超额,车间,车间主任)
? 关系模式S_L_C(S#,SD,SL,C#,G)

学生宿舍楼,且每个系学生只住一栋楼

关键字:(S#,C#) 函数依赖: f (S#,C#) G 完全 S# ?SD,SD ?SL, G S# 传递 SL (S#,C#) p p (S#,C#) SD SL

S# C# 关键字

SD

部分

SL

对关系模式S_L_C,同样存在数据冗余大、插入异常、 删除异常、修改困难等问题。(产生问题的原因同W)
2015/9/23 数据库系统数据库系统 231

第五章

关系数据理论

3、解决办法:用投影分解 消除非主属性对关键字的部分函数依赖转换为2NF S# S# SD G

G
C# 关键字

SC?2NF 部分
SL S# ?2NF S_L

C#
SD

?
2015/9/23

SL

分解之后,与S_L_C相比, SC和S_L性质如何?
数据库系统数据库系统 232

第五章

关系数据理论

分解前 S_L_C(S#,SD,SL,C#,G) 分解后 SC(S#,C#,G) S_L(S#,SD,SL)

分解之后,与S_L_C相比: ? 数据冗余减小
(原来伴随学生所学的每门课都要存储一遍SD、SL的值)


? 没选课的学生信息可以存储; ? 删除选课记录不会误删学生其他信息;

? 冗余数据的减少使得修改变得容易些。 1NF的上述四个问题得到了部分解决 S_L还有问题吗?
2015/9/23 数据库系统数据库系统 233

第五章
(1)数据冗余

关系数据理论
S_L(S#,SD,SL)

4、仅属于2NF的关系模式可能会产生的问题 数据冗余仍然较大:SL的值重复严重 (2)插入异常 若一个系刚成立但尚无学生,该系名称等无法存储 (3)删除异常 若一个系的学生全部毕业,删除全部学生数据的同时把 该系的数据(如系名等)也都删除了 (4)修改困难 数据冗余大势必造成修改困难 (这可以说是个必然联系)
2015/9/23 数据库系统数据库系统

可能的原因:
存在传递函数依赖 S#?SL
234

第五章
四、第三范式(3NF)

关系数据理论

1、定义;若关系模式 R<U, F>?1NF,并且R中不存在码 X、属性组Y和非主属性Z(Z ? Y)使得X→Y( Y → X),Y → Z成立,则称 R?3NF。 2、定理:若 R?3NF,则 R?2NF。 分析 要证R?2NF R的每一非主属性都完全函数依赖于码 不存在任何非主属性部分函数依赖于码 希望推出 由3NF的定义, 若R?3NF , 则R中不存在码X、属性组Y和非主属性Z(Z

? Y)使得X→Y( Y → X),Y → Z成立 只需证:若存在非主属性部分函数依赖于码
2015/9/23 数据库系统数据库系统

R?3NF
235

第五章

关系数据理论

四、第三范式(3NF) 1、定义;若关系模式 R<U, F>?1NF,并且R中不存在码 X、属性组Y和非主属性Z(Z ? Y)使得X→Y( Y → X),Y → Z成立,则称 R?3NF。 2、定理:若 R?3NF,则 R?2NF。 只需证:若存在非主属性部分函数依赖于码 R?3NF p A 证明 设A是R的一个非主属性,K是R的码,且 K
则存在 K‘? K,使得K‘?A。故有 K? K‘ ,K‘?A。 因为一个候选关键字不可能函数依赖于它的真子集, 所以有 K‘ K. 又因为A是非主属性,K是码,且K‘? K,故 A ? K‘。 所以R ? 3NF。
2015/9/23 数据库系统数据库系统

要找Y,满足

K?Y,Y

K,Y?A
236

第五章

关系数据理论

3、说明 ? 根据以上证明,也可这样定义3NF: 若 R?2NF,并且R中不存在任何非主属性传递函数依 赖于R的码,则称R?3NF。 ? 若R<U, F>中U是全键,则一定有 R?3NF。 4、属于2NF但不属于3NF的例子: S# SD ? 关系模式S_L(S#,SD,SL) 传递 5、解决办法:用投影分解 SL 消除非主属性对关键字的传递函数依赖,转换为3NF 如将S_L分解为: S_D(S#,SD) D_L(SD,SL)
2015/9/23 数据库系统数据库系统

S#

SD

SD

SL
237

第五章

关系数据理论

6、仅属于3NF的关系模式可能会产生的问题 由上可知,部分函数依赖和传递函数依赖是产生异常的 两个重要原因。

3NF中不存在非主属性对于关键字的部分函数依赖和传
递函数依赖,因此具有较好的性质。 通常设计关系模式时至少应该是属于3NF的。

虽说3NF是广泛使用的一种关系范式,但3NF仍然存在某
些“异常”。

例:关系模式 R(S,T,J)
学生
2015/9/23

教师

课程

每个教师只教一门课, 每门课有若干教师,学 生选定某门课就对应固 定的教师。
238

数据库系统数据库系统

第五章

关系数据理论
S T 学生1 教师1 …… 学生K 教师1 学生L 教师2 …… 学生M 教师2 学生1 教师3 …… 学生K 教师3 …… J 课程1
课程1 课程1

例:关系模式 R(S,T,J) 函数依赖:(S,J)? T; (S,T)? J;T ?J

候选关键字:(S,J);(S,T)
R中无非主属性,显然R?3NF。

课程1 课程2
课程2

J 重复,产生冗余,

带来可能的不一致性等问题

因为这是关键字

也是传递函数依赖 可能的原因: R中存在部分函数依赖 (S,T) ? J。
2015/9/23 数据库系统数据库系统 239

第五章

关系数据理论

由例子可以看出,虽然3NF消除了一大类 数据冗余问题(冗余也是产生异常操作的直接 原因),但这种数据冗余是非主属性下的冗余。 3NF并没有涉及主属性下的数据冗余问题。

2015/9/23

数据库系统数据库系统

240

第五章

关系数据理论

五、Boyce-Codd范式(BCNF) 1、定义:若R ? 1NF,且对任何非平凡的函数依赖X?Y, X必包含码。则R ? BCNF。 2、另一种等价的定义: 即每一决定因素都包含码 若 R?1NF,并且R中不存 在任何属性传递函数依赖于R的某个码,则称R? BCNF。

证明 (1)定义?等价定义
即要证:若对任何非平凡的函数依赖X?Y,X必包含码,

则R中不存在任何属性传递函数依赖于R的某个码。 反证法:假设R中存在属性Z传递函数依赖于码X, 则必存在属性组Y,使得 X ?Y,Y X,Y ? Z。 显然Y不是码,也不包含码,矛盾。
2015/9/23 数据库系统数据库系统 241

第五章

关系数据理论

(2)等价定义?定义 仍用反证法:假设存在非平凡函数依赖X?Y,X不包含码, 设X‘是一关键字,则X‘ ?X, X X‘,因此 X‘ 传递 Y, 矛盾。 证毕 3、说明 若 R?1NF,并且R中不存在 ? 若R? BCNF,则R? 3NF。 任何非主属性传递函数依赖于 (也称BCNF为修正的3NF) R的某个码,则称 R?3NF。 ? BCNF又消除了主属性对码的部分函数依赖和传递函数依赖。 ? 从完全函数依赖的观点看,属于BCNF的关系模式满足: ? 所有非主属性对每一个码都是完全函数依赖; ? 所有主属性对每一个不包含它的码也是完全函数依赖; ? 没有任何属性完全函数依赖不是码的任何一组属性。
2015/9/23 数据库系统数据库系统 242

第五章

关系数据理论

? 在函数依赖的范畴内,BCNF已做到彻底的分离,消除了插 入异常、删除异常(3NF的“不彻底性”在于可能存在主 属性对关键字的部分函数依赖和传递函数依赖)。 4、属于3NF但不属于BCNF的例子: ? 关系模式 R(S,T,J) 码:(S,T);(S,J) 函数依赖:(S,J) ?T;(S,T) ?J;T ?J 因为J部分函数依赖于码(S,T),或T是决定因素,但T 不包含码。故R不属于BCNF。 5、解决办法:用投影分解 消除主属性对码的部分或传递函数依赖,转换为BCNF。 将R(S,T,J)分解为: R1(S,T) R2(T,J)
2015/9/23 数据库系统数据库系统 243

第五章

关系数据理论

6、仅属于BCNF的关系模式可能会产生的问题 以前面讨论过的关系模式 TEACH(C,T,B)为例 课程C 教员T 参考书B 课程 教员 参考书 物理 汪洋 普通物理学 物理 汪洋 光学原理 物理 汪洋 物理习题集 TEACH的关键字是 物理 大海 普通物理学 (C,T,B),即全键。 物理 大海 光学原理 因此 TEACH?BCNF 物理 大海 物理习题集 数学 大海 数学分析 数学 大海 微分方程 问题:冗余大, 数学 大海 高等代数 增、删不便 数学 白云 数学分析 数学 白云 微分方程 数学 白云 高等代数 原因:存在多值依赖 …… …… ……
2015/9/23 数据库系统数据库系统 244

第五章

关系数据理论

六、第四范式(4NF) 1、定义:设R ? 1NF,若对于R的每个非平凡的多值依赖 X??Y(Y? X),X都包含码,那么称 R ? 4NF 。 2、定理:若 R ? 4NF,则 R ? BCNF。
3、属于BCNF但不属于4NF的例子: ? 关系模式 TEACH(C,T,B) 4、解决办法:用投影分解 消除不合适的多值依赖,转换为4NF 全码

(存在非平凡多值依赖C??T,而C不是关键字)

对于TEACH(C,T,B)分解为: C-T(C,T) C-B(C,B)
2015/9/23 数据库系统数据库系统 245

第五章
七、范式小结 1、规范化的目的

关系数据理论

解决 数据冗余、插入异常、删除异常、修改困难 等问题 2、规范化的基本思想 逐步消除不合适的数据依赖,让一个关系描述一个概念 、一个实体或实体间的一种联系。即“一事一地”的模式设 计原则。

2015/9/23

数据库系统数据库系统

246

第五章
3、范式

关系数据理论

1NF 消除决 定因素 非码的 非平凡 函数依 赖
消除非主属性对码的部分函数依赖 2NF 消除非主属性对码的传递函数依赖 3NF

消除主属性对码的部分和传递函数依赖
BCNF 消除非平凡且非函数依赖的多值依赖 4NF ……

2015/9/23

数据库系统数据库系统

247

第五章
范式间的关系:
1NF 2NF 3NF BCNF 4NF 5NF

关系数据理论
4、规范化的过程 对关系模式分解,把 一个低一级关系模式分解 成若干个高一级的关系模 式。 5、规范化与操作效率 片面追求高级的模式, 会使数据库操作效率降低

本节开头
2015/9/23

本章开头
数据库系统数据库系统

下一节
248

第五章
§4

关系数据理论

函数依赖的Armstrong公理系统

上一节给出了范式的定义,并用例子说明了如何确定一个 关系模式属于第几范式以及如何把低一级的模式分解成高一级 的模式,但都是直观的方法。 本节及下节将从理论上探讨: 如何确定一个关系模式的极小函数依赖集? 如何分解关系模式? 一、Armstrong公理系统 模式分解算法的理论基础 问题:对于给定的一组函数依赖,如何判断其它函数依 赖是否成立?或者说哪些函数依赖是不独立的?如:对 关系模式R有:A?B,B?C。 问:A?C是否成立?
2015/9/23 数据库系统数据库系统 249

第五章

关系数据理论

1、逻辑蕴涵 设F是关系模式R<U, F>的函数依赖集,X、Y是R的属性 子集。如果在R<U, F>上函数依赖X?Y成立,则称F逻辑蕴涵 X?Y。 即对R的任一关系r,对r中的任意两元组t、s, 若t[X]=s[X],则t[Y]=s[Y]
下面将会看到(我们的本意也是如此),可以用下述方式 来表述逻辑蕴涵: 若从F中的函数依赖能够推出X?Y,则F逻辑蕴涵X?Y。 2、Armstrong公理 对关系模式R<U, F>,有如下的推理规则: A1、自反律(Reflexivity):若Y?X?U,则X?Y为F所蕴涵。

简写:若Y?X,则X?Y
2015/9/23 数据库系统数据库系统 250

第五章

关系数据理论

A2、增广律(Augmentation):若X?Y为F所蕴涵,且Z?U, 则XZ?YZ为F所蕴涵。 简写:若X?Y,则XZ?YZ A3、传递律(Transitivity):若X?Y和Y?Z为F所蕴涵, 则X?Z为F所蕴涵。 简写:若X?Y、Y ? Z,则X?Z 证明很简单,自己看书 P184 决定每一部分必决定全部 3、Armstrong公理的正确性 定理: Armstrong推理规则是正确的。 4、Armstrong公理的推论 (1)合并规则:由X?Y, X?Z,有X?YZ。 (2)分解规则:由X?Y及Z?Y,有X?Z。 (3)伪传递规则:由X?Y, WY?Z,有XW?Z。 决定全部必决定部分
2015/9/23 数据库系统数据库系统 251

第五章
证明

关系数据理论

(1)合并规则:由X?Y, X?Z,有X?YZ。 因为 X?Z,由增广律有 XY?YZ, 由传递律有 XX?YZ 因为 X?Y,由增广律有 XX?XY, 又因为 X?XX (自反律),所以 X?YZ(传递律)。 (2)分解规则:由X?Y及Z?Y,有X?Z。 Armstrong公理 若Y?X,则 X?Y 因为Z?Y,所以Y?Z(自反律), 若X?Y,则 XZ?YZ 由X?Y、 Y?Z,又有X?Z(传递律)。 若X?Y、Y ? Z,则 X?Z 伪传递规则的证明作为习题自己证。 根据合并规则和分解规则,可以得出一个重要的结论: 定理:X?A1 A2 …Ak的充要条件是X?Ai(i=1,2,…,k)。
2015/9/23 数据库系统数据库系统 252

第五章

关系数据理论

二、函数依赖集的闭包 有了上述推理规则,对一个给定的函数依赖集F,我们 自然希望知道哪些函数依赖可由F推出,哪些不能由F推出 ,由F能推出的函数依赖有多少等。 1、闭包的定义:在关系模式R<U, F>中F所逻辑蕴涵的函数 依赖的全体称为F的闭包。记作F+。 例:设关系模式R<U, F>,其中U={X,Y,Z},F={X?Y, Y?Z},则F的闭包F+为:
X?? X ?X X ?Y X ?Z X?XY X?XZ X?YZ X?XYZ
2015/9/23

XY?? XY?X XY?Y XY?Z XY?XY XY?XZ XY?YZ XY?XYZ

XZ?? XZ?X ZX?Y XZ?Z XZ?XY XZ?XZ XZ?YZ XZ?XYZ

XYZ?? Y?? XYZ?X Y?Y XYZ?Y Y?Z XYZ?Z Y?YZ XYZ?XY XYZ?XZ XYZ?YZ XYZ?XYZ

YZ?? Z?? YZ?Y Z?Z YZ?Z YZ?YZ

数据库系统数据库系统

253

第五章

关系数据理论

2、求函数依赖集的闭包问题是NP完全问题 3、属性集的闭包 设关系模式 R<U, F>,X? U,X关于函数依赖集F的闭包为: X+ F ={ A | X?A能由F根据Armstrong公理推出} 函数依赖集的闭包是一个(更大的)函数依赖集 属性集的闭包 是一个(更大的)属性集合 设F为属性集U上的一组函数依赖,X,Y ? U, X?Y能 由F根据Armstrong公理导出的充分必要条件是Y? X+ 。 F 于是判定X?Y能否由F根据Armstrong公理导出的问题, + 的子集的问题。 就转化为求出X+ ,判定 Y 是否为 X F F
2015/9/23 数据库系统数据库系统 254

第五章
4、求闭包 X+ F 的算法

关系数据理论

Armstrong公理 分析:根据定义,要求所有这样 若Y?X,则 X?Y 的属性A:X?A能由F经数次使用 若X?Y,则 XZ?YZ Armstrong公理推出。 若X?Y、Y? Z,则X?Z A应具备何种特征? 分析Armstrong公理的形式可以看出,A应该属于X,或

A属于F中某个函数依赖的右部,而该函数依赖的左部属性
应是属于X的闭包。 算法思想:采用逐步扩张X的策略求X的闭包。方法是: 扫描F,找出左部属性属于当前X的闭包的函数依赖,将右部 属性加入当前X的闭包。经若干次扩张,直到当前闭包集不再 扩大为止。
2015/9/23 数据库系统数据库系统 255

第五章
算法

关系数据理论

计算时在F中寻找未用过的 输入:X,U,F; 左部是X(i)的子集的函数依赖 + 输出:X关于F的闭包 XF (1)初始:令X(0)=X, i=0; (2)迭代:求B={A | (?V)(?W) (V?W?F ? V?X(i) ? A?W)}; X(i+1)=B?X(i);

(3)判断: X(i+1)=X(i)?
若相等或X(i)=U,转下一步; 否则,用i+1取代i,转第(2)步继续迭代; (4)结束:X(i)就是 X+ ,算法终止. F 每次迭代都添加属性到当前闭包(不增加时算法就 结束)故至多迭代|U|-|X|次算法终止
2015/9/23 数据库系统数据库系统 256

第五章

关系数据理论

例:设F={ AC?PE,PG?A,B?CE,A?P,GA?B, GC?A,PAB?G,AE?GB,DP?H }, X=BG, 左部 右部 迭代号 求 X+ F 3 PE AC PE 求解过程 4 A PG A 初始:X(0) = X = BG B CE 1 CE 第1次迭代: 找左部为B、G或BG的 P A P 3 函数依赖,将其右部属性放入闭包 B GA B 3 X(1) = X(0) ? CE = BCEG GC 2 A A 第2次迭代: PAB 4 G G X(2) = X(1) ? A = ABCEG AE GB 3 GB 第3次迭代: DP H X(3) = X(2) ? PEBG = ABCEGP 第4次迭代: X(4)与X(3)相同,算法结束, X(4) = X(3) ? AG = ABCEGP X(4)=ABCEGP就是BG的闭包
2015/9/23 数据库系统数据库系统 257

第五章

关系数据理论

又如,若关系模式为 R(A1,A2,A3),F={A1?A2, A2?A3}, 则当 X=A1 时,X的闭包为 A1A2A3; 留作习题 当 X=A2 时,X的闭包为 A2A3; 当 X=A3 时,X的闭包为 A3; 思考:对关系模式R<U, F>, 若 X+ 求X的闭包算法的正确性 F = U, 我们不做证明。 问X有何性质?

2015/9/23

数据库系统数据库系统

258

第五章

关系数据理论

三、Armstrong公理系统的有效性和完备性

函数依赖集F的闭包F+是F所逻辑蕴涵的函数依赖的全体
。关于逻辑蕴涵,我们已经建立了一套推理规则( Armstrong 公理系统),因此自然要问:

? 由F出发根据Armstrong公理能推出的函数依赖是否一定
是F逻辑蕴涵的,即是否一定在F+中? ? F+中的每一个函数依赖,即F逻辑蕴涵的每一个函数依

赖,是否一定可以根据Armstrong公理推出?
F+ = { 由F出发根据Armstrong公理能推出的函数依赖的全体 }



2015/9/23

数据库系统数据库系统

259

第五章

关系数据理论

1、何谓有效性?何谓完备性?
Armstrong公理的有效性: 有效性就是正确性, Armstrong公理的正确性就是由该公 理系统推出的函数依赖都是正确的。而正确性的标准就是只要 F中的函数依赖为真,则由公理推出的函数依赖也为真。换句 话说,由F出发根据Armstrong公理能推出的函数依赖一定在F+ 中 Armstrong公理的完备性: 完备性就是要讨论用公理能否推出所有的函数依赖。因为

如果存在F逻辑蕴涵的函数依赖不能用公理推出,则说明这些
公理不够用,是不完全的,还必须补充新的公理。因此,完备 性就是指F+中的每一个函数依赖,一定可以根据Armstrong公 理推出
2015/9/23 数据库系统数据库系统 260

第五章

关系数据理论

公理的正确性保证了推出的所有函数依赖都是正确的; 公理的完备性保证了可以推出所有的函数依赖。 2、 Armstrong公理的有效性 回忆一下Armstrong公理系统(自反律、传递律和增广律) 以及前面讨论过的定理“ Armstrong推理规则是正确的”,可 证Armstrong公理系统是有效的。 3、 Armstrong公理的完备性

要证完备性,必须解决如何判断 一个函数依赖是否可由F出发根据Armstrong公理推出 如果能方便地求出F+,将有助于解决上述问题,但计算F+是 NP完全问题。 前面已经给出求属性集的闭包的有效算法。对一个函数依赖 X?Y,X的闭包对我们要解决的问题有何帮助?
2015/9/23 数据库系统数据库系统 261

第五章

关系数据理论

根据求闭包的算法,可知 X ? X+ F 因此,若 Y ? X+ ,则 X ? Y。 反之是否成立? F 引理:对关系模式R<U, F>,X、Y? U, Y? X+ X ?Y能由F根据Armstrong公理推出 F 证明 充分性: 设Y=B1B2…Bk,Bi ? X+ ,(i=1,2,…,k) F 根据属性闭包的定义可得 X?Bi(i=1,2,…,k)都可由F根据Armstrong公理 推出, 再由合并规则可得 X?B1B2…Bk,
即 X?Y可由F根据Armstrong公理推出,

必要性:
2015/9/23

此处证明从略,留作习题
数据库系统数据库系统 262

第五章
分析

关系数据理论

定理: Armstrong公理系统是完备的。

根据定义,需证:
对F+中的每一个函数依赖,必 定可由F用Armstrong公理推出 再由F+的定义,需证: 对F所蕴涵的每个函数依赖, 必定可由F用Armstrong公理推 出 因此,只需证明: 若存在函数依赖 X?Y不能 由Armstrong公理推出,则它
2015/9/23 不为 F所蕴涵

欲证 X?Y不为F所蕴涵, 只需证: 存在符合关系模式 R<U, F>的一个关系r,函数依赖

X?Y在r上不成立
因此,需要构造一个关系r: r的属性集是U,且r满足F

中的所有函数依赖,但X?Y
在r上不成立

关键是证明这两点
263

数据库系统数据库系统

第五章

关系数据理论

欲构造关系r,使得X?Y在r上不成立,最简单的情形是: r X Y Z

表示相等

1 1

1 0

表示不相等

但这样构造的r显然不合要求,因为r不一定满足F中的所有 函数依赖。
属性集的闭包在Armstrong公理可推导的意义下具有封闭 性,我们这里要讨论的就是Armstrong公理的完备性。所以 构造r时利用X的闭包更为合理: 关系r X+ F 11…1 11…1
2015/9/23

U– X+ F 11…1 00…0

关系r只有两个元组, 在X的闭包上分量值相等

数据库系统数据库系统

264

第五章

关系数据理论
根据前面引理易证

证明 假设函数依赖 X?Y不能由Armstrong公理推出

(1)先证F中的函数依赖和X的闭包有下述关系: 若V?W是F中的函数依赖,且 V?X + ,则W ? X + F F 设V?W 是F中的任一函数依赖,

(2)再证前面构造的关系 r 是 R<U, F>的关系,即满足F中的全部函数依赖

要证V?W在r上成立。
分两种情情形: 第一种情形:V? X + F 根据第(1)步结论,有W ? X + F

关系r

X+ F
11…1 11…1 W

+ U– X F 11…1 00…0

W的值在仅有的两个元组上相等,因此必有若t[V]=s[V]则t[W]=s[W], 所以此时V?W在r上成立。

2015/9/23

数据库系统数据库系统

265

第五章

关系数据理论

第二种情形:V? X + F 此时存在属性A?V,但A? X + F r中仅有的两个元组在属性A上的值不等,

关系r

X+ F
1 1

+ U– X F A 1 0

所以在r中不存在两个元组t、s满足t[V]=s[V],

V

因此“若t[V]=s[V],则t[W]=s[W]‖在关系r上恒成立,故V?W在r上成立。 综上可知F的任一函数依赖在r上成立,即r是 R<U, F>的关系 (3)最后证明函数依赖X?Y在r上不成立 由假设, X?Y不能由Armstrong公理推出,根据引理有Y? X + F 所以有Y的子集Y‘满足Y‘? U– X + ,故对r中仅有的两元组t、s,有 F + t[Y‘]?s[Y‘],进而有t[Y]?s[Y]。 但由于X? X F ,所以有t[X]=s[X], 因此得X?Y在r上不成立。即X?Y必不为F所蕴涵。 证毕
2015/9/23 数据库系统数据库系统 266

第五章

关系数据理论

四、函数依赖集的等价和极小依赖集 1、函数依赖集的等价(覆盖): 定义:设F和G都是关系模式R上的两个函数依赖集,如果 F+ = G+,则称F与G等价(或称F覆盖G,或G覆盖F)。 等价具有自反性、对称性、传递性,即是一等价关系。

定理:F+ = G+ 的充要条件是 F?G+和 G ?F+ 。
证明:必要性显然。因为F?F+、G ?G+成立, 即F可由G推出 若 F+ = G+,则必有F?G+、G ?F+成立。 G也可由F推出 充分性:要证当F?G+、G ?F+时,有F+ = G+成立。 先证对任意的X?Y?F+,有X?Y?G+。这样就有F+ ?G+。 + 。 X 因为X?Y?F+,所以Y? F
2015/9/23 数据库系统数据库系统 267

第五章

关系数据理论

证毕 同理可证 G+ ?F+,所以 F+ = G+。 对本定理也可先证命题:(1)若F ? G,则F+ ? G+; (2)F+ =(F+)+。 然后有:F ? G+ ? F+ ?(G+)+ = G+; F+ = G+ G ? F+ ? G+ ?(F+)+ = F+;
2、极小(最小)函数依赖集 根据分解与合并规则,可以证明下述引理:

若F?G+,则 X+ ? X+ F G+ + 所以Y? X G+ ,从而得X?Y?(G+)+=G+。 于是证得F+ ?G+。

引理:每个函数依赖集F都与一个右部只有单个属性的函数 依赖所构成的函数依赖集G等价。
2015/9/23 数据库系统数据库系统 268

第五章

关系数据理论

证明;设F中的函数依赖由两部分构成: F = F1 ? F2 右边是一个以上属性的函数依赖子集
右边是单属性的函数依赖子集

设F2中的函数依赖形如 X?A1A2…Ak,k?2。 令F3是将F2中所有函数依赖分解成形如 X?Ai 的函数依赖全体,

G = F1 ? F3,要证明F与G等价
对G中任一个形如 X?Ai ?F3,由于F中存在X?A1A2…Ak ,i?k,根据分解规则可推出 X?Ai,所以 X?Ai?F+,而F1 ? F ? F+。 故G?F+。 根据合并规则,同理可证 F?G+。 根据前面的引理,有F与G等价。
2015/9/23 数据库系统数据库系统

证毕
269

第五章

关系数据理论

定义:若函数依赖集F满足下列条件,则称F为极小(函数)
依赖集,亦称最小(函数)依赖集、最小覆盖: (1)F的每个函数依赖的右部仅含有一个属性;右部都是单属性

(2)对F中的任一个函数依赖X?A,
都有F与F?{X?A}不等价;

不存在多余的函数依赖

每个函数依赖的左部 (3)对F中的任一个函数依赖X?A, 没有多余的属性 都有F与(F?{X?A})? {Z?A}不等价, 其中Z是X的任一真子集。 例:关系模式 S<U, F>,U ={ S#,SD,MN,CN,G }, F ={ S#?SD,SD?MN,(S#,CN)?G }, 则F是最小覆盖。 设函数依赖集F‘ ={ S#?SD,S#?MN, SD?MN, (S#,CN)?G ,(S#,SD)?SD }, 则F‘不是最小覆盖。 2015/9/23 270 数据库系统数据库系统

第五章

关系数据理论

3、如何求极小函数依赖集 定理:每一个函数依赖集F均等价于一个极小函数依赖集Fm。 对F极小化处理 (1)分解:将F中右部多于一个属性的函数依赖分解成单属性 函数依赖。 逐一检查F中各函数依赖FDi:X?Y,若Y=A1A2…Ak, k?2,则用{X?Ai | i=1,2, …k }取代X?Y。

证明

这样每个函数依赖的右部都为单属性,由引理知该函数依
赖集与F等价。 (2)去多余依赖: 对经第一步处理后的F,逐一检查F中各函数依赖 X?A, 令G=F-{X?A},若A? X+ ,则从F中去掉X?A。 G
2015/9/23 数据库系统数据库系统 271

第五章

关系数据理论

此处我们考虑X?A 是否多余,即F是否与G等价。 因为G是F的子集,且只比F少一个函数依赖X?A,所以 A ? X+ X?A可由G推出 F与G等价 G (3)去左部多余属性: 对经第二步处理后的F,逐一检查F中各函数依赖 X?A, + ,则以X-Bi 设X=B1B2…Bm,逐一考察Bi,若 A?(X-Bi) F 取代X。这样得到的函数依赖集仍与F等价,且去掉了左部多余 的属性。 F 与( F-{X?A})? {( X-Bi)?A }等价 (X-Bi)?A 可由F推出 + A?(X-Bi) F 证毕
2015/9/23 数据库系统数据库系统 272

第五章

关系数据理论

? 此定理表明:任一函数依赖集都可极小化。定理的 证明过程就是“极小化处理”过程,也就是求一个函数依

赖集的极小依赖集的方法。
? F的极小依赖集不一定唯一(例子见P187)。当以 不同的顺序考察各函数依赖时,得到的极小函数依赖集可 能不同。

2015/9/23

数据库系统数据库系统

273

第五章

关系数据理论

例:求下列函数依赖集F的极小依赖集。 F=

AB?C, D D ? ? EG EG , , C?A, BE?C, , BC?D,CG CG? ?BD BD , ACD?B, CE CE? ?AG AG

解:(1)分解右部为单属性 AB?C, D?E, C?A, BE?C, D?G, G= BC?D,CG?B,ACD?B,CE?A, CG?D, CE?G (2)去掉G中多余的函数依赖 具体做法是:从G的第一个依赖开始,依次判别是否多 余。设处理到函数依赖 X?Y,从函数依赖集中先去掉它, 求X关于此函数依赖集的闭包,再判属性Y是否属于该闭包 。若是,则去掉X?Y;否则,保留。然后处理下一个。
2015/9/23 数据库系统数据库系统 274

第五章

关系数据理论

AB?C,D?E,D?G,C?A,BE?C, BC?D, G= CG?B,CG?D,ACD?B,CE?A, CE?G 对此例:先判 AB?C 是否多余? 求AB关于G-{AB?C}的闭包,根据求闭包的算法,仍为 {A,B},而 C?{A,B},所以不能去掉AB?C; 同样可判D?E, D?G, C?A, BE?C, BC?D也不能去掉; 求CG关于G-{CG?B}的闭包,得ABCDEG,B在其中, 故去掉CG?B; 对G-{CG?B}继续进行,可得CG?D,ACD?B保留, CE?A去掉, CE?G保留。 问:CG?B如何由H推出? 最后得: CG ?CCG ?ACG ?ACCG ?ACD ?B AB?C,D?E,D?G,C?A,BE?C,BC?D, H= CG?D,ACD?B, CE?G
数据库系统数据库系统 275

2015/9/23

第五章

关系数据理论

(3)从H中去掉左部多余的属性 具体做法是:依次检查左部为多属性的函数依赖,对每一个 这样的函数依赖,检查其中是否有多余属性:若XB?A,求X 关于H的闭包,看它是否包含A。 AB?C,D?E,D?G,C?A,BE BE ? C ? C , H= , BC?D,CG?D,ACD?B,CE?G BC?D,CG?D,ACD?B,CE?G 看AB?C,因为A关于H的闭包为{A},B关于H的闭包为 {B},它们都不包含C,故AB?C无多余属性; 同样可得BE?C,BC?D,CG?D,CE?G中无多余属性 ; 看ACD?B,因为 AC关于H的闭包为{A,C}, AD关于H的闭包为{A,D,E,G}, 不含B 不含B A多余

包含B 2015/9/23 CD关于H的闭包为 276 数据库系统数据库系统 {A,B,C,D,E,G},

第五章

关系数据理论

因此在H中把 ACD?B 换成 CD?B: AB?C, D?E, D?G, C?A, BE?C, H= BC?D,CG?D,ACD?B,CE?G F的极小依赖集为: AB?C, D?E, D?G, C?A, BE?C , BC?D,CG?D,CD?B,CE?G F还有另一个极小依赖集为: Fm = Fm2 = AB?C, D?E, D?G, C?A, BE?C,BC?D,CG?B,CE?G 本章开头
数据库系统数据库系统

本节开头
2015/9/23

下一节
277

第五章

关系数据理论

§5 关系模式的分解 一、模式分解的有关概念 1、分解的定义:对关系模式 R<U, F>,若模式集合 ? = { R1<U1, F1>, R2<U2, F2>,…, Rn<Un, Fn> } 满足 ? U = U1 ? U2 ? …? Un,且 Ui ? Uj,1? i?j ?n, ? Fi是F在Ui上的投影。 函数依赖集合 { X?Y ? X?Y?F+ ? XY?Ui }的一个覆盖 例:设模式为R<U, F>,其中U={S#,SD,MN}, F={S#?SD,SD?MN},考虑下面几种分解: (1)U1 = { S# }, U2 = { SD },U3 = { MN } F1 = ?, F2 = ?, F3 = ? ? = { R1<U1, F1>, R2<U2, F2>,R3<U3, F3> }是R的一 个分解。
2015/9/23 数据库系统数据库系统 278

第五章

关系数据理论

(2)U1 = { S#,SD }, U2 = { S#,MN } F1 = { S#?SD },

参考前面的例子:设关系模式为R<U, F>,其中U={X,Y,Z}, F={X?Y,Y?Z}, F的闭包F+为: X?? X ?X X ?Y X ?Z XY?? XY?X XY?Y XY?Z XZ?? XZ?X XZ?Y XZ?Z XYZ?? XYZ?X XYZ?Y XYZ?Z Y?? Y? Y Y? Z YZ?? YZ?Y YZ?Z Z?? Z?Z

Y?YZ YZ?YZ

X?XY
X?XZ X?YZ

XY?XY
XY?XZ XY?YZ

XZ?XY
XZ?XZ XZ?YZ

XYZ?XY
XYZ?XZ XYZ?YZ

X?XYZ XY?XYZ XZ?XYZ XYZ?XYZ
2015/9/23 数据库系统数据库系统 279

第五章

关系数据理论

(2)U1 = { S#,SD }, U2 = { S#,MN } F1 = { S#?SD }, F2 = { S#?MN } ? = { R1<U1, F1>, R2<U2, F2> }也是R的一个分解。
参考前面的例子:设关系模式为R<U, F>,其中U={X,Y,Z}, F={X?Y,Y?Z}, F的闭包F+为: X?? X ?X X ?Y X ?Z XY?? XY?X XY?Y XY?Z XZ?? XZ?X XZ?Y XZ?Z XYZ?? XYZ?X XYZ?Y XYZ?Z Y?? Y? Y Y? Z YZ?? YZ?Y YZ?Z Z?? Z?Z

Y?YZ YZ?YZ

X?XY
X?XZ X?YZ

XY?XY
XY?XZ XY?YZ

XZ?XY
XZ?XZ XZ?YZ

XYZ?XY
XYZ?XZ XYZ?YZ

X?XYZ XY?XYZ XZ?XYZ XYZ?XYZ
2015/9/23 数据库系统数据库系统 280

第五章

关系数据理论

(3)U1 = { S#,SD }, U2 = { SD,MN } F1 = { S#?SD }, F2 = { SD?MN } ? = { R1<U1, F1>, R2<U2, F2> }也是R的一个分解。 2、分解可能会带来的问题 问题:关系r分解为 (1)分析第一种情形: r1、r2、r3三个关 U1 = { S# },U2 = { SD },U3 = { MN } 系,但根据这三个 关系,无法回答诸 F1 = ?, F2 = ?, F3 = ? 如“S1是哪个系的 学生?”、“D1系 设关系r为: r1为:r2为: r3为: 的系主任是谁?” S# SD MN S# SD MN 等许多提问。 S1 D1 张五 S1 D1 张五 S2 D2 李四 S2 D1 张五 S3 D3 王一 S3 D2 李四 S4 S4 D3 王一
2015/9/23 数据库系统数据库系统 281

第五章

关系数据理论

分解后的关系应该能够恢复成原来的形式,这是最 基本的要求。恢复通常由自然连接来实现。 r1、r2、r3自然连接的结果与r相比元组增加了,但 信息丢失了。 分解不能丢失信息,这就是“无损连接性”的概念

(2)分析第二种情形: U1 = { S#,SD }, U2 = { S#,MN }
F1 = { S#?SD }, F2 = { S#?MN } 对此分解,可正确恢复出原来的关系。但原关系模式 的数据冗余、插入异常、删除异常的问题仍然存在。 分析原因,原来具有的函数依赖SD?MN现在没有了。

分解应该“保持函数依赖”
2015/9/23 数据库系统数据库系统 282

第五章

关系数据理论

(3)分析第三种情形: U1 = { S#,SD }, U2 = { SD,MN } F1 = { S#?SD }, F2 = { SD?MN } 对此分解,通过自然连接可正确恢复,且原来的函数依赖都保持。 3、分解准则 分解后的模式应和原来的模式“等价”。 根据以上分析,可提出以下不同标准: ? 分解具有“无损连接性”(Lossless join) ? 分解要“保持函数依赖”(Preserve dependency) ? 分解既要“保持函数依赖”,又要具有“无损连接性”

本节讨论: ? 何谓“无损连接性”和“保持函数依赖”? ? 分离程度如何? ? 如何分解?
2015/9/23 数据库系统数据库系统 283

第五章

关系数据理论

二、分解的无损连接性和保持函数依赖性 1、无损连接性的形式化定义: 设? = { R1<U1, F1>, R2<U2, F2>,…, Rk<Uk, Fk> }是 R<U, F>的一个分解。若对R的任何一个关系r都有
成立,则称?具有无损连接性,简称?为无损分解。 例:设关系模式 R(A,B,C), 不是无损分解 分解为R1(A,B)、R2(B,C)。 又设其中一个关系为: (r) r1 (r)r2 =? B,C r2 ? r r A B C r1=?A,B A B C A B a1 b1 c1 B C a1 b1 c1 a1 b1 a2 b1 c2 b1 c1 a1 b1 c2 多一个元组 a2 b1 a1 b1 c2 b1 c2 a2 b1 c1 a2 b1 c2
2015/9/23 数据库系统数据库系统 284

r =? U1 ( r)

? U2 ( r)



? Uk ( r)

第五章

关系数据理论

例: 设模式为R<U, F>,其中U={S#,SD,MN}, F={S#?SD,SD?MN}, 分解为:U1 = { S#,SD },U2 = { S#,MN } F1 = { S#?SD }, F2 = { S#?MN } r2 = r r1=?S#,SD (r) r2 =? S#,MN (r) r1 设关系r为: S# S1 S2 S3 S4 SD D1 D1 D2 D3 MN 张五 张五 李四 王一 S# S1 S2 S3 S4 SD D1 D1 D2 D3 S# MN S1 张五 S2 张五 S3 李四 S4 王一 S# S1 S2 S3 S4 SD D1 D1 D2 D3 MN 张五 张五 李四 王一

此时是否可以说这是一个无损分解?

不行!

如何判断是否为无损分解?
2015/9/23 数据库系统数据库系统 285

第五章

关系数据理论

2、无损连接性判定算法 输入: R<U, F>的一个分解? ={ R1(U1,F1), …, Rk(Uk,Fk) }, U={A1,A2,…,An}, F={FD1,FD2,…,FDp}为最小覆盖,FDi:Xi?Ali; 输出: ?是否为无损连接的判定结果; ? 构造一个k行n列的表:第i行对应关系模式Ri,第j列对应属
性Aj;若Aj?Ui,则在第i行第j列处写入aj;否则写入bij。 ? 逐个检查F中的每一个函数依赖,并修改表中的元素: 对每个FDi :Xi?Ali,在Xi对应的列中寻找符号相同的行, 并将这些行中Ali对应的列全改为相同的符号。修改规则为:若 其中有ali,则全改为ali;否则全改为bmli,m是这些行中行号 的最小值。(若某个btli被改动,则该列中凡是btli的符号都要 作同样的修改。)
2015/9/23 数据库系统数据库系统 286

第五章

关系数据理论

? 判别:若某一行变成a1,a2 ,…an,则算法终止(此时?
为无损分解);否则,比较本次扫描前后的表有无变化,若有 ,重复第?步;若无,算法终止(此时? 不是无损分解) 无损连接判定举例: 设模式为R<U, F>,U={ A, B, C, D, E },F ={ AB?C, C?D, D?E }, 分解为 R1(A, B, C)、R2(C, D)、R3(D, E)。
算法第一步:构造初始表
A R1 R2 R3 B C D E 算法第二步:扫描F,修改表 对AB?C,看A、B对应的第1、2两列有 无相同的行。没有,不做处理。 对C?D,看C对应的第3列有无相同的行 第1、2行相同,将D列的b14改为a4。 对D?E,进行同样处理。 算法第三步:判断 表中第一行为a1、a2、a3、a4、a5,算 法终止,R1、R2、R3是R的无损分解
287

a1 a2

a3 b14 a4 b15 a5
a4 a4 b25 a5 a5 a5

b21 b22 a3

b31 b32 b33 a4 a4
2015/9/23

数据库系统数据库系统

第五章

关系数据理论

例:设有关系模式 R(A, B, C, D, E, F ), 其函数依赖集合F={A?B,C?F,E?A,CE?D}, 分解为 ? = { R1(C, F), R2(B, E), R3(E, C, D), R4(A, B) } 解: (1)构造表 (2)修改表,第一次扫描F ? A?B:无修改 A B C D E F ? C?F: R1(C,F) b11 b12 a3 b14 b15 a6 b36改为a6 ? E?A: R2(B,E) b21 a2 b23 b24 a5 b26 b31改为b21 R3(E,C,D) b21 b31 b32 a2 a3 a4 a5 b36 a6 ? CE?D:无修改 (3)第二次扫描F R4(A, B) a1 a2 b43 b44 b45 b46 ? A?B:b32改为a2 其余无修改 (4)第三次扫描: 表无变化, 算法终止 (5)判断:不是无损分解
2015/9/23 数据库系统数据库系统 288

第五章

关系数据理论

3、算法的正确性: 定理:?为无损连接分解的充分必要条件是:

证明略

算法终止时,表中有一行为a1,a2,?,an。

4、分解为两个关系模式时的简单判定法 例:设关系模式为R<U, F>, U={ A, B, C }, F ={ A?B, C?B }, 分别检查下列分解的无损连接性: (1) ?1 = { R1(A, B), R2(B, C) } (2) ?2 = { R1(A, C), R2(B, C) } A B C A B C R1(A, B) a1 a2 b13 R1(A, C) a1 b12 a2 a3 R2(B, C) b21 a2 a3 R2(B, C) b21 a2 a3 对A?B,表无修改 对A?B,表无修改 对C?B,表无修改 对C?B,修改b12为a2
2015/9/23 数据库系统数据库系统 289

第五章

关系数据理论

定理:设? = { R1<U1, F1>, R2<U2, F2> }是R<U, F>的一个分解。 那么?是无损分解的充分必要条件是 U1?U2 ? U1-U2 ? F+ 或 U1?U2 ? U2-U1 ? F+ + 即 (U1-U2) ? (U1?U2) F 或 (U2-U1) ? (U1?U2) + 证明略 F 看上例:关系模式为R<U, F>, U={ A, B, C }, F ={ A?B, C?B }, (1) ?1 = { R1(A, B), R2(B, C) } (2) ?2 = { R1(A, C), R2(B, C) }

U1?U2 ? U1-U2 为: U1?U2 ? U1-U2 为: B ? A C ? A U1?U2 ? U2-U1 为: U1?U2 ? U2-U1 为: B ? C C ? B + = {B} 因为 B F 因为C?B ? F,所以 不包含A,也不包含C, ?2是无损分解 所以B?A和B?C不为F所蕴涵 ?1不是无损分解
2015/9/23 数据库系统数据库系统 290

第五章

关系数据理论

5、保持函数依赖性的形式化定义: 设? = { R1<U1, F1>, R2<U2, F2>, …, Rk<Uk, Fk> }是R<U, F> + + 的一个分解,若 F = (F1?F2???Fk),则称?保持函数依赖。 判别定理:F+ = G+ 的充要条件是 F?G+和 G ?F+ 。

6、说明 ? 一个无损连接分解

不一定是 一个保持函数依赖的分解

? 一个保持函数依赖的分解 不一定是 一个无损连接分解 例:关系模式为R<U, F>, U={ A, B, C }, F ={ A?B, C?B }, (1) ?1 = { R1(A, B), R2(B, C) } (2) ?2 = { R1(A, C), R2(B, C) } 有损连接 其 F1={A?B},F2={C?B } 保持函数依赖
2015/9/23

无损连接 其 F1=?,F2={C?B } 不保持函数依赖
291

数据库系统数据库系统

第五章

关系数据理论

三、模式分解的算法 1、模式分解的分离程度 保持函数依赖 3NF 具有无损连接性 4NF 保持函数依赖 3NF 具有无损连接性 2、转换为3NF的保持函数依赖的分解算法——合成法 算法思想: 若要将一个关系模式的极小函数依赖集中的每 一个函数依赖都要保留下来,最简单的方法就是把每一个函 数依赖的左右部属性组成一个模式。 如假设 F = {A?B,A?C,C?D},则可考虑分解为: 考虑合并 ? = { R1(A, B), R2(A, C), R3(C, D) } 但A?B,A?C左部相同,分解成两个模式是否有必要呢?

直 观 的 想 法 最 重 要

(左部相同的函数依赖放在一起考虑)
2015/9/23 数据库系统数据库系统 292

第五章

关系数据理论

算法5.3:把一个关系模式分解为3NF,且使它保持函数依赖 输入:关系模式 R<U, F>; 输出:R的一个分解? ={R1,R2,…Rk},每个Ri均为3NF,且? 保持函数依赖 (1)极小化:对F进行极小化处理(处理后的函数依赖集仍记 为F); (2)分离无关属性:把U中不出现在F中的属性组成一个关系 模式,从U中去掉这些属性(剩余的属性仍记为U); (3)判是否需分解:若有X?A?F,且XA=U,则? ={R},算 法终止; (4)分解:对F分组:左部相同的为一组, 设为Fi‘,每组所包 含的全部属性形成一个属性集Ui。若有Ui?Uj(i?j),去掉Ui 。设最后保留下来U1,U2,…,Uk,则 ? ={ R1(U1), R2(U2), … Rk(Uk) },算法终止。
2015/9/23 数据库系统数据库系统 293

第五章

关系数据理论

例1:设关系模式 R(A,B,C,G,H,R,S,T), F = { C?T,CS?G,HT?R,HR?C,HS?R } 求:(a)R的一个侯选关键字; (b)将R分解为3NF,并且保持函数依赖性。 + 解 (a)求关键字:设X为候选关键字,则必有XF =U。 + + 要等于U, X 而 XF -X只能取F中函数依赖右部的属性, F
至少应有ABHS ?X。 + = ABHSRCTG=U 求ABHS关于F的闭包有:(ABHS) F 所以ABHS是一个候选关键字。 (b)分解R:(1) 先对F极小化:F已是最小依赖集。 (2) 分离无关属性:AB未在F中出现,分离出去。 (3) 判是否需分解:需要。 (4) 分解:按左部相同的原则分组。 则 ? ={ R1(A,B), R2(C,T),R3(C,S,G), R4(H,T,R), R5(H, R, C), R6(H,S,R) }为一个保持函数依赖且达到3NF 的分解。
数据库系统数据库系统 294

2015/9/23

第五章

关系数据理论

例2:设有关系模式 R(A,B,C,D,E),R的一个函数依 赖集为F = { A?D,A?B,E?D,D?B,BC?D,DC?A }, (a)求R的候选关键字; (b)将R分解为3NF,并且保持函数依赖性。

解 (a)求关键字:设X为候选关键字,则必有X + =ABCDE。 F + + X 而 XF -X只能取F中函数依赖右部的属性,要使 F 等于 ABCDE,必须有CE?X。 + 再求CE关于F的闭包,得(CE) F = CEDBA。 所以CE是一个候选关键字。 若此时还不等于 (b)分解R: R的属性集U, (1)先对F极小化: 怎么办? ①分解右部为单属性:不需要;
②去掉多余函数依赖:A?B多余;
2015/9/23 数据库系统数据库系统 295

第五章

关系数据理论

例2:设有关系模式 R(A,B,C,D,E),R的一个函数依 赖集为F = { A?D,A?B,E?D,D?B,BC?D,DC?A }, (a)求R的候选关键字; (b)将R分解为3NF,并且保持函数依赖性。

③去掉左部多余属性:没有。 所以极小函数依赖集为: F = { A?D,E?D,D?B,BC?D,DC?A } (2)分离无关属性:没有。 (3)判是否需分解:需要。 (4)分解:
{AD,ED,DB,BCD,DCA} ? ={R1( E, D),R2(B, C, D),R3(D, C, A) }
2015/9/23 数据库系统数据库系统 296

第五章

关系数据理论

例3:设有关系模式 R(A,B,C,D),R的一个函数依赖集为 F = { A?B,B?C,C?D,D?A }, 试将R分解为3NF,并且保持函数依赖性。 解 (1)先对F极小化:F就是最小依赖集。 (2)分离无关属性:没有。 (3)判是否需分解:需要。 (4)分解:

? ={R1(A, B),R2(B, C),R3(C, D),R4(D, A)}
算法的正确性: 按算法5.3得到的关系模式R的分解? ={R1,R2,…Rk}满足: 每个Ri均为3NF,且?保持函数依赖。
2015/9/23 数据库系统数据库系统 297

第五章

关系数据理论

证明:(a)?保持函数依赖显然成立。
(b)证每个 Ri<Ui, Fi> 均为3NF(Fi是F在Ui上的投影): 设F是R的最小依赖集,Fi‘是分解算法中得到Ri的那组函数依赖, 要证不存在非主属性对关键字的传递函数依赖。 设 Fi ‘={ X?A1, X?A2, … X?An },Ui ={X, A1, …An }, 则X一定是Ri的候选关键字。 反证法:假设Ri不是 3NF ,则 Ui中存在非主属性Am(1?m?n) Fi‘ 系由 F按左部相同的原则分组而得。 和属性组合Y使得Am?Y,X?Y、Y?Am?Fi + , 而Y?X ?Fi +。

非主属性Am传递依赖于侯选关键字X 下面证 X?Am在F中多余,从而与F是最小依赖集矛盾。 令G=F-{ X?Am },欲证 X?Am?G + 。
2015/9/23 数据库系统数据库系统 298

+ 因为Y是Ui的子集,且不包含Am,所以 Y? X G , 因此X?Y?G + 。 要证 X?Am?G + ,只需再证Y?Am?G +。 因为Y?Am?Fi +,所以Am?Y +。 F + 若Y?Am?G +,则在求Y 的算法中,只有使用X?Am才能 F 将Am引入。 根据求闭包的算法,存在j使得X?Y (j),故得Y?X?F +, 与Y?X ?Fi+ 相矛盾, 所以Y?Am?G +成立。

第五章

关系数据理论

证毕

说明:因为保持函数依赖的分解可能不是无损连接的分解, 而不具有无损连接性就会丢失信息,所以这样的分解是没有 意义的。因此单单算法5.3没有实用价值,但它是下一算法的 基础。
2015/9/23 数据库系统数据库系统 299

第五章

关系数据理论

2、转换为3NF既保持函数依赖又具有无损连接性的分解算法 算法思想: 在算法5.3分解的基础上,增加一个模式,该模式以 原模式的一个关键字作为属性组,使该模式起到正确连接其它 各模式的作用。 例如,对 R(A,B,C,D),其最小依赖集F={A?B,C?D}, 按算法5.3得到的分解是 ?1 ={AB,CD}, ?不具有无损连接性。 R的关键字是AC,分解成?2 ={AB, CD, AC}就具有无损连接性。

算法5.4: 输入:关系模式R<U, F>; 输出:R的一个分解? ={R1,R2,…Rp},每个Ri均为3NF, 且 ? 既保持函数依赖又具有无损连接性; (1)用算法5.3将R分解为 ? ={ R1(U1), R2(U2), … Rk(Uk) }; (2)求R的一个关键字X; (3)若X是某个Ui的子集,输出 ? = ?; 否则, 输出? = ? ? { R * (X)} ;算法结束。
2015/9/23 数据库系统数据库系统 300

第五章

关系数据理论

算法的正确性:按算法5.4得到的关系模式R的分解? ={R1, R2, …Rp}满足: 每个Ri均为3NF,且? 既保持函数依赖又具有无损连接性。 证明;(a) ? 保持函数依赖显然成立。 (b)证每个 Ri均为3NF: * 之外的Ri都为3NF;R* 中没有非主属性,因此也为3NF。 算法5.3保证R (c) 证?为无损分解:

分析:增加 R*的目的就是为了达到无损连接,
按照无损连接判定算法,R* 所对应的行应该成为全a。 R* 不一定在?中,但?中必存在某关系模式的属性组T包含X, 为简单起见,不妨设T就是X, R* 就在?中。 按照无损连接判定算法,在构造初始判定表时,对 R* 所对应的行, X对应的列全为a,设 U-X={A1,A2,…As},欲证经有限步执行判定算法,

该行中A1,A2,…As所对应的列也被改为全a。
2015/9/23 数据库系统数据库系统 301

第五章
+ 因为X是关键字,故X F =U.
所以在求X的闭包时,A1、 A2、…As将进入X的闭包, 不妨设进入的次序就是A1、 A2、…As,则根据求闭包的 算法,会产生序列: X?X (1)?X (2) ??X (i) ?=U

关系数据理论
属性 模式 … R*(X) … R1(Y1A1) … Ri(YiAi) … Rs(YsAs) … X … aaa…aaaa … baa…abba … bab…babb … aab…abaa … U- X A1 … Ai … As … b b…b b … b … a a b…b b … b … b a…a b … b … a b…b a … a …

满足 (i–1) Yi?Ai?F,且Yi?X =XA1A2 … A(i–1)。 不失一般性,可设R1(Y1A1)、 R2(Y2A2)、 … Rs(YsAs)在?中, 初始判定表如右上角所示。
2015/9/23 数据库系统数据库系统 302

第五章

关系数据理论

证按无损判定算法, R* 对应的行中A1,A2,…As所对应的列被改为全a。
用归纳法: 属性 U- X X 当s=1时,有Y1?A1?F,故R1 模式 A1 … Ai … As 所在的行中Y1对应的列全a; … … … (0) a … a ab… aaa…aaaa ba b…b …a b R*(X) * 因为Y1?X =X,而R 所在 … … … 行中X对应的列全a,所以至少这 R1(Y1A1) baa…abba a a b…b b … b … … … 两行中Y1对应的列全a,故相等。 Ri(YiAi) bab…babb b a…a a b…b 考察A1对应的列: … … … 因R1行对应的为a,故R* 行A1 Rp(YpAp) aab…abaa a b…b a … a … … … 列也改为a。 假设s=i–1时,R* 所在行A1、A2、A(i–1)对应列能够全改为a。 =XA1A2 … A(i–1) 。 * 行Ai列也改为a。 与s=1时的同样道理,根据Ri行的Ai列为a,可将R 根据归纳法原理,结论成立。 证毕
2015/9/23 数据库系统数据库系统 303 Yi?Ai?F,且Yi?X (i–1) =XA1A2 … A (i–1) 。

当s=i时,有Yi?Ai?F,且Yi?X

(i–1)

第五章

关系数据理论

3、转换为BCNF的无损连接分解——分解法 算法思想: 按自顶向下的方式,从关系模式R<U, F>开始,选择 不是BCNF的模式将其一分为二,直到都为BCNF。(二叉分解) 算法5.5: 输入:关系模式R<U, F>; 输出:R的一个分解? ={R1,R2,…Rk},每个Ri均为 BCNF,且 ?具有无损连接性; (1)初始:令?={R<U, F>}。 正确性证明自己看 (2)检查:检查?各关系模式是否都是BCNF。若是,算法终止。 (3)分解:设?中Ri<Ui, Fi>不是BCNF, 则存在X?A?Fi + (A?X),X不是Ri的关键字; 对Ri作无损分解:?={S1,S2} Ui-X X 因X不是Ri的关键字,故XA是Ui的真子集, A Ui-X-A 且容易验证,?是Ri的一个无损分解。
S1<XA> a…a a 以?代Ri,返回第(2)步。 S2<X(Ui-X-A)> a…a b a
2015/9/23 数据库系统数据库系统

bbb … bb aaa … aa
304

第五章

关系数据理论

4、转换为4NF的无损连接分解 定理:设关系模式为R<U, D>,其中D为R中函数依赖和多值依赖的集合, 则 X??Y成立
R的分解 ? ={ R1<XY>,R2 <XZ> }具有无损连接性, 其中Z=U-X-Y。 证明:充分性。要证 若? 是无损连接,则X??Y成立。

多值依赖的定义: 多值依赖X??Y成立当且仅当对R(U)的任一关系r,若存在元组s、t 使得s[X]=t[X],则必存在元组w、v?r(w、v可以与s、t相同),使得

w[X]=v[X]=t[X],而w[Y]=t[Y],w[Z]=s[Z],v[Y]=s[Y],v[Z]=t[Z]。

交换s、t的Y值 所得新元组仍在r中
2015/9/23 数据库系统数据库系统 305

第五章

关系数据理论

4、转换为4NF的无损连接分解 定理:设关系模式为R<U, D>,其中D为R中函数依赖和多值依赖的集合, 则 X??Y成立
R的分解 ? ={ R1<XY>,R2 <XZ> }具有无损连接性, 其中Z=U-X-Y。 证明:充分性。要证 若? 是无损连接,则X??Y成立。 欲证:对R的任一关系r,若t、s?r,且t[X]=s[X],则存在u、v?r使得 u[X]=v[X]=t[X],而u[Y]=t[Y],u[Z]=s[Z],v[Y]=s[Y],v[Z]=t[Z]。 因为? 是无损连接,对R的任一关系r,有 r = ? (r) XY 若t、s?r,且t[X]=s[X], 关系r: X s Y s[Y] t[Y] Z s[Z] t[Z] ? (r) XY X s Y s[Y] t[Y] ? (r)。 XZ Z s[Z] t[Z]
306

?

(r) XZ X s t

t
2015/9/23

t

数据库系统数据库系统

第五章
若t、s?r,且t[X]=s[X], 令 u = t[X]?t[Y]?s[Z], ?

关系数据理论
(r) XY X
s Y s[Y] t[Y] X s t

?

(r) XZ X s t
Y s[Y] t[Y] t[Y] s[Y]

Z s[Z] t[Z] Z s[Z] t[Z] s[Z] t[Z]

v = s[X]?s[Y]?t[Z], 则 u、v?r满足u[X]=v[X]=t[X], 而u[Y]=t[Y],u[Z]=s[Z], v[Y]=s[Y],v[Z]=t[Z]。

t

所以 X??Y成立。
必要性。要证 若X??Y成立,则? 是无损连接。 欲证:对R的任一关系r,有 r = ? (r) ? (r)。 XY XZ 而 r ? ? (r) ? (r)显然成立, XY XZ

u
v

故只需证 r ??
2015/9/23

(r) XY

?

(r) XZ

数据库系统数据库系统

r = ? (r) ? (r) (自己证) XY XZ 证毕
307

第五章

关系数据理论

说明:上述定理是在函数依赖和多值依赖的范畴内讨论问题,因此需要 建立一套新的公理系统来保证“逻辑蕴涵”和“导出”仍是等价的。 幸运的是,只要简单扩充Armstrong公理系统(增加关于多值依赖的 公理),该公理系统仍是有效的和完备的。 转换为4NF的无损连接分解算法: 以算法5.5作为第一步,规范化到4NF时方法也同算法5.5 (二叉分解)。 算法5.6: 输入:关系模式R<U, D>;

输出:R的一个分解? ={R1,R2,…Rk},每个Ri均为4NF,
且 ?具有无损连接性; (1)用算法5.5先将R分解到BCNF,且具有无损连接性。

(2)对其中没达到4NF的模式,根据前面定理分解,直到所有模式都
为4NF时为止。

2015/9/23

数据库系统数据库系统

308

第五章

关系数据理论

作业:
P196 习题 2、3、12 补充:

1、设F={ AC?PE,PG?A,B?CE,A?P,GA?B,GC?A,
PAB?G,AE?GB,DP?H }, X=AG, 求 X+ F 2、设有关系模式 R(ABCDE),R的函数依赖集为 F={A?C,B?C,C?D,DE?C,CE?A}, (1)设? ={ R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE) } 是R的一个分解。试判断?是否为无损分解。

(2)给出R的一个既保持函数依赖又具有无损连接的3NF分解。

本节开头
2015/9/23 数据库系统数据库系统

本章开头
309

第六章
本章内容:

数据库设计

§1 数据库设计概述 §2 需求分析
§3 概念结构设计 §4 逻辑结构设计 §5 物理结构设计
请选择内容

§6 数据库的实施和维护

返回

2015/9/23

第六章 数据库设计

310

§1 数据库设计概述
数据库设计是指对一个给定的应用环境,构造最优的 数据库模式,建立数据库及其应用系统,使之能够有效地 存取数据,满足各种用户的应用需求。 一、数据库和信息系统 大型数据库的设计和开发是涉及多学科的综合性技术, 对涉及人员来说应具备多方面的技术知识,主要有:
? ? ? ?

数据库的基本知识和数据库的设计知识;

计算机科学的基础知识和程序设计的方法和技巧
软件工程的原理和方法 应用领域的知识
第六章 数据库设计 311

2015/9/23

二、数据库设计的特点: ? “三分技术,七分管理,十二分基础数据” ? 数据库设计和应用系统设计相结合,即将结构设计和 行为设计相结合

2015/9/23

第六章 数据库设计

312

三、数据库设计方法简述
数据库设计方法中著名的新奥尔良方法,将数据库 的设计分为四个阶段:
? ? ? ?

需求分析(分析用户要求) 概念设计(信息分析和定义) 逻辑设计(设计实现) 物理设计(物理数据库设计)

数据库设计工具:ORACLE 公司 Design 2000 Sybase 公司的PowerDesigner 四、数据库设计的基本步骤
2015/9/23 第六章 数据库设计 313

数据库设计的基本步骤 ?: 需求分析:了解与分析用户需求,是最困难、最费时间的一步。 ? 概念结构设计
?

通过对用户的需求进行综合、归纳和抽象,形成一个独立于具 体的DBMS的概念模型

?

逻辑结构设计
?

将概念结构转换为某个DBMS所支持的模型,并对其进行优化 为逻辑数据模型选取一个最适合应用环境的物理结构(包括存 取结构和存取方法)

?

物理结构设计
?

?

数据库实施
?

运用DBMS提供的数据语言及其宿主语言,根据逻辑设计和物
理设计的结果建立数据库,编制与调试应用程序,组织数据入 库,并进行试运行

?

数据库运行和维护
第六章 数据库设计 314

2015/9/23

应用需求(数 据、处理 转换规则、 DBMS功能 、优化方法 应用要求、 DBMS详细 特征

需求收集和分析 设计概念结构 设计逻辑结构

需求分析阶段 概念设计阶段

逻辑设计阶段 数据模型优化

设计物理结构
物理设计阶段 评价设计、性能检测 物理实现 数据库实施阶段 实验性运行 使用、维护数据库
第六章 数据库设计

数据库运行、维护阶段
315

2015/9/23

§2 需求分析
一、需求分析的任务 通过详细调查现实世界要处理的对象(组织、部门、企业 等),充分了解原系统工作概况,明确用户的各种需求,然后 在此基础上确定新系统的功能。 调查的重点是“数据”和“处理”,通过调查、收集与分 析,获得用户对数据库的如下要求:
?

信息要求
?

指用户需要从数据库中获得信息的内容和性质,从而导出应 在数据库中存储哪些数据 用户完成什么样的处理功能,对处理的响应时间有什么要求 处理方式是批处理还是联机事务处理
第六章 数据库设计 316

?

处理要求
? ?

?

安全性与完整性要求

2015/9/23

二、需求分析的方法
?

调查组织机构情况
?

了解该组织的部门组成情况,各部门的职责,为分析信息流 程做准备 了解各部门的输入和使用什么样的数据 如何加工这些数据 输出什么信息 输出到什么部门 信息输出结果的格式 信息要求、处理要求、安全性与完整性要求 确定那些由计算机来完成,那些由人工来完成
第六章 数据库设计 317

?

调查各部门的业务活动情况
? ? ? ? ?

?

协助用户明确对新系统的各种要求
?

?

确定新系统的边界
?

2015/9/23

需求调查的方法:
?

?

?

?
?

?

跟班作业 参加业务工作来了解业务活动的情况,此种方 法可以准确地了解用户的需求,但是比较耗费时间 开会调查 通过与用户座谈来了解业务活动情况,座谈时, 参加者之间可以相互启发 请专人介绍 询问 设计调查表请用户填写。如果调查表设计的合理,这种方 法是很有效,也易于为用户接受。 查阅记录 做需求调查时,往往需要同时采用上述多种方法。但是无 论采用何种方法,都需要用户的配合。
2015/9/23 第六章 数据库设计 318

三、数据字典
数据流图表达了数据和处理的关系,数据字典则是系统 中各类数据描述的集合,是进行详细设计的数据收集和数据 分析所获得的主要成果,数据字典在数据库设计中占有很重 要的作用。数据字典通常包括数据项、数据结构、数据流、 数据存储和处理过程五个部分。 ? 数据项
数据项是不可再分的数据单位。对数据项的描述通常包括以下内容

数据项描述= {数据项名,数据项含义说明,别名,数据类型,长
度,取值范围,取值含义,与其它数据项的逻辑关系,数据项 之间的联系 }
?

数据结构 :反应了数据之间的组合关系
数据结构描述= { 数据结构名,含义说明,组成:{数据项或数据结 构}

数据流:是数据结构在系统内传输的路径。
2015/9/23 第六章 数据库设计 319

数据流描述={数据流名,说明,数据流来源,数据流去向,组成:

{数据结构},平均流量,高峰期流量 }
?

数据存储
是数据结构停留或保存的地方,也是数据流的来源和去向之一,也 可以是手工文档或手工凭单,也可以是计算机文档。 数据存储描述={ 数据存储名,说明,编号,输入的数据流,输出的 数据流,组成:{数据结构},数据量,存取频度,存取方式 }

?

处理过程
处理过程描述= { 处理过程名,说明,输入:{ 数据流},输出: { 数据流 },处理:{ 简要说明 } } 简要说明:说明该处理过程的功能及处理要求,功能是指该处理过 程用来干什么 处理要求包括处理频度要求,如单位时间里处理多少事务、多少、 的数据量、响应时间。
2015/9/23 第六章 数据库设计 320

§3 概念结构设计
将需求分析得到的用户需求抽象为信息结构即概念模 型的过程就是概念结构设计。 一、概念结构的主要特点:
?

? ? ?

能真实充分地反映客观世界,包括事物和事物之间的 联系,满足用户对数据的处理要求 易于理解 易于更改 易于向关系、网状、层次等各种数据模型转换

2015/9/23

第六章 数据库设计

321

二、概念结构设计的方法与步骤 概念结构设计的方法:
?
?

?

?

自顶向下 首先定义各全局概念框架,然后逐步细化 自底向上 首先定义各局部应用的概念框架,然后将他 们集中起来,得到全局概念结构 逐步扩张 首先定义最重要的核心概念结构,然后向 外扩充,以滚雪球的方式逐步生成其它概念结构,直 至总体概念结构 混合策略 将自顶向下和自底向上相结合,用自顶向下 策略设计一个全局的概念结构框架,以它为骨架集成 由底向上策略中设计的各局部概念框架。

2015/9/23

第六章 数据库设计

322

自顶向下分析需求与自底向上设计概念结构 需求
需求分析( 自顶向下)

需求1 需求1.1 需求1.2

......

需求n 需求n.1 需求n.2

概念模式1.1 概念模式1.2
概念结构设计 (自底向上)

概念模式n.1

概念模式n.2

概念模式1

......

概念模式n

概念模式
2015/9/23 第六章 数据库设计 323

需求分析
数据抽象、局 部视图的设计 返回用户征求意 见直到满意为止 视图集成

DFD DD

分E-R图

总E-R图

逻辑结构设计

图6.9逻辑结构设计步骤
第六章 数据库设计

2015/9/23

324

三、数据抽象与局部视图设计
抽象是对实际的人、物、事和概念进行人为处理,抽取所关心的 共同特性,忽略非本职的细节,并把这些特性用各种概念精确地加以 描述,这些概念组成了某些模型。
?

?

?

分类 定义某一类概念作为现实世界中的一组对象的 类型。这些对象具有某些共同的特性和行为。它抽象 了对象值和型之间的(is member of)语义。 聚集 定义了某一类型的组成成分。它抽象了对象内 部类型和成分之间的 (is part of ) 语义。 概括 定义了类型之间的一种子集联系。它抽象了类 型之间的(is subset of)的语义。如学生是一个实体

型,本科生、研究生也是一个实体型。本科生和研究 生是学生的子集,把学生作为超类(Superclass),本 科生、研究生是子类(Subclass)。
2015/9/23 第六章 数据库设计 325

概念结构设计的第一步是利用抽象机制对需求分析阶段收集的数 据进行分类、组织(聚集),形成实体、实体的属性,标识实体的码 ,确定实体之间的联系(1:1,1:m,n:m),设计分E-R图。具体步骤:

?

选择局部应用 逐一设计分E-R图

?

2015/9/23

第六章 数据库设计

326

四、视图的集成
各子系统的分E-R图设计好之后,就要将各分E-R图 综合成一个系统的总E-R图。视图集成的方式有两种: 多个分E-R图一次集成 复杂,难度大 ? 逐步集成 用累加的方法一次集成两个分E-R图 每次只集成两个分E-R图,可以降低复杂度 无论采用以上那种方式,每次集成局部E-R图都要分两步走 ? 合并 解决各分E-R图的冲突,将各分E-R图合并起来生 成初步的E-R图。 ? 属性冲突 属性值冲突和属性域冲突 ? 命名冲突 同名异义和异名同义
?

2015/9/23

第六章 数据库设计

327

? 结构冲突

同一对象在不同应用上有不同的抽象 同一实体在不同的分E-R图中所包含的属性 个数和属性排列次序不完全相同。

?

修改和重构 消除不必要的冗余,生成基本E-R图

消除冗余的方法: 1. 分析方法:即以数据字典和数据流图为依据,根据数 据字典中关于数据项之间的逻辑关系的说明来消除冗余 。 2. 用规范化理论中函数依赖的概念来消除冗余

2015/9/23

第六章 数据库设计

328

用规范化理论中函数依赖的来消除冗余的方法如下: ? 确定分E-R图实体之间的数据依赖 实体之间的一对一、一对多或多对多的联系可以用实 体码之间的函数依赖来表示 ? 求函数依赖集Fl的最小覆盖Gl,差集为D= Fl - Gl 逐一检查D中的函数依赖,确定是否是冗余的联系,若 是就去掉 注意的问题:
? ?

冗余的联系一定在D中,但D中的联系不一定是冗余的 当实体之间存在多种联系时,要将实体之间的联系在形式 上加以区分

2015/9/23

第六章 数据库设计

329

§4 逻辑结构设计
逻辑结构分三步进行:
? ?

将概念结构转换成一般的关系、层次、网状模型

将转换来的关系、层次、网状模型向特定的DBMS支持下 的数据模型转换
?

对数据模型进行优化
一般数据模型 关系、层次、网状 特定的DBMS支 持下的数据模型 优化的数 据模型

概念结构 基本E-R图

转换规则
2015/9/23

DBMS的特 点和限制
第六章 数据库设计

优化方法
330

一、E-R图向关系模型的转换
由于E-R图是由实体、实体的属性和实体之间的联 系组成,所以就要将实体、实体的属性和实体之间的 联系转换为关系模式,这种转换遵循如下规则:
?

?

一个实体转换成一个关系模式。实体的属性就是关系 的属性,实体的码就是关系的码。对于实体间的联系 则有以下几种情况: 一个1:1的联系可以转换为一个独立的关系模式,也可 以与任意一端对应的关系模式合并。如果转换成一个 独立的关系模式,则与该联系相联的各实体的码以及 联系本身的属性均转换为关系的属性,每个实体的码 均是该关系的候选码,如果与某一端实体对应的关系 模式合并,则需要在关系模式的属性中加入另一个关 系模式的码和联系本身的属性。
第六章 数据库设计 331

2015/9/23

?

?

?

?

一个1:n的联系可以转换为一个独立的关系模式,也可 以与n端对应的关系模式合并。如果转换成一个独立的 关系模式,则与该联系相联的各实体的码以及联系本 身的属性均转换为关系的属性,而关系的码为n端关系 的码。 一个m:n的联系可以转换为一个关系模式。与该实体 相联的各实体的码以及联系本身的属性均转换为关系 的属性,而关系的码为各实体码的组合。 三个或三个以上的实体间的一个多元联系可以转换为 一个关系模式。与该多元联系相连的各实体码以及联 系本身的属性均转换为关系属性,而关系的码为各实 体码的组合。 具有相同的码的关系模式可以合并。
第六章 数据库设计 332

2015/9/23

二、数据模型的优化
? ?

?

?

?

确定数据依赖; 对于各个关系模式之间的数据依赖进行极小化处理, 消除冗余的联系; 按照数据依赖的理论对关系模式逐一进行分析,考察 是否存在部分函数依赖、传递函数依赖,多值函数依 赖等,确定各关系模式属于第几范式; 按照需求分析阶段得到的处理要求,分析这些模式对 于这样的应用环境是否合适,确定对某些模式是否要 进行合并或分解; 对关系模式进行必要的分解,提高数据操作的效率和 存储空间的利用率。常用的分解方法是水平分解和垂 直分解。
第六章 数据库设计 333

2015/9/23

三、设计用户子模式
一般DBMS都提供了视图的概念,可利用这一功能为局 部用户设计更合适的用户外模式,并考虑下列因素:
? ?

?

使用更符合用户习惯的别名 可以对不同级别的用户定义不同的View,以保证系统 的安全性 简化用户对系统的操作

2015/9/23

第六章 数据库设计

334

§5 物理结构设计
数据库的物理设计通过分为两步:
? ?

确定数据库的物理结构 对物理结构进行评价,评价的重点是时间和空间效率

一、数据库的物理设计的内容和方法
对于数据库的查询事务,需要得到如下信息: ? 查询的关系

? 查询条件所涉及到的属性
? 连接条件所涉及到的属性 ? 查询的投影属性
2015/9/23 第六章 数据库设计 335

对于数据更新事务,需要得到如下信息: ? 被更新的关系 ? 每个关系上的更新操作条件所涉及到的属性 ? 修改操作要改变的属性值

二、关系模式的存取方法选择
常用的存取方法:
? ? ? ?
2015/9/23

索引方法 B+树方法 聚蔟(Cluster)方法

HASH方法
第六章 数据库设计 336

三、确定数据库的存储结构
?

确定数据的存放位置

?

确定系统的配置

2015/9/23

第六章 数据库设计

337

四、评价物理结构
评价物理数据库的方法完全依赖于所选用的DBMS, 主要是从定量估算

推荐相关:

数据库原理大作业

吉林财经大学 数据库原理与应用 大作业医院门诊系统的数据库设计 专业班级: 学号姓名: 信息管理与信息系统 1402145042 慕园园 1402145034 牟晓春 1402145009 王思宇 ...


西南交大数据库原理复习资料

西南交大数据库原理复习资料_工学_高等教育_教育专区。数据库原理部分第一章 数据库系统概述 1.数据:是记录下来的可以鉴别的符号。描述事物的符号记录称为数据。 ...


数据库原理第二章作业

数据库原理第二章作业_工学_高等教育_教育专区。第二章 高级数据模型一. 简答题 1. ERM 属于哪个层次的数据模型?关系模型又是哪个层次的数据模型? 答:EMR ...


数据库原理及应用历年考题_答案

数据库原理及应用》试题 1 一、选择题 1、数据库系统的基本特征是___。 A、数据的统一控制 C、数据共享性、独立性和冗余度小 B、数据共享性和统一控制 ...


数据库原理与应用教程期末考试试题与答案1

数据库原理与应用教程―SQL Server 期末测试题与答案(一)一、填空题(每空 1 分,共 10 分) 1.数据库系统的核心是___ __。 2.在关系模型中,实体以及实体...


数据库原理课程教学大纲

数据库原理课程教学大纲 【课程编号】 01048 Principles of Database System 【学时学分】 【课程性质】 【先修课程】 【开课单位】 网络工程专业 【考核方式】 ...


数据库原理与应用试题--含答案

数据库原理与应用试题--含答案_工学_高等教育_教育专区。一、判断题 [数据库系统概论]2 (F)与用文件系统来管理数据相比,用数据库管理数据增加了数据冗余度。 ...


数据库原理期末考试复习题及答案

数据库原理期末考试复习题及答案_计算机软件及应用_IT/计算机_专业资料。十套题库 试题一 一、单项选择题 (本大题共 20 小题,每小题 2 分,共 40 分) 在...


数据库原理

数据库原理_理学_高等教育_教育专区。一、填空题 1、关系代数运算中,专门的关系运算有、和连接。 2、消除了非主属性对候选码的部分函数依赖的关系模式,称为;...


数据库原理复习资料(带答案)

数据库原理与应用》课程复习资料【考试形式】笔试,闭卷,120 分钟 【题型】选择、填空与应用 【复习内容】一、 基本概念的掌握。 1. 信息是现实世界客观事物在...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com