数据库技术：笔记整理

本文为 SJTU-CS3321 数据库技术课程的笔记整理。

第一章 数据库系统概论

1. 数据库系统概述

• 数据库的发展：
  • 经历了三代演变：层次/网状数据库系统、关系数据库系统、新一代数据库系统
  • 造就了五位图灵奖得主：C.W.Bachman (网状数据库)、E.F.Codd (关系数据库)、James Gray (事务处理)、M.R.Stonebraker (Ingres 等)、Jeffrey D. Ullman (数据依赖)

1.1 四个基本概念

• 数据 (Data)：数据库中存储的基本对象

  • 定义：描述事物的符号记录
  • 种类：数值、文字、图形、图象、声音、视频等
  • 特点：数据与其语义是不可分的

• 数据库 (DataBase, DB)：

  • 定义：长期储存在计算机内、有组织、可共享的大量数据集合
  • 基本特征：
    • 数据按一定的数据模型组织、描述和储存
    • 可为各种用户共享
    • 冗余度较小
    • 数据独立性较高（应用程序与数据库中存储的数据相互独立，即数据结构发生变化，应用程序不必做相应修改）
    • 易扩展

• 数据库管理系统 (DataBase Management System, DBMS)：

  • 定义：位于用户与操作系统之间的一层数据管理软件
  • 用途：科学地组织和存储数据、高效地获取和维护数据
  • 主要功能：
    • 数据定义功能：
      • 提供数据定义语言(Data Definition Language, DDL)
      • 定义数据库中的数据对象的组成与结构
    • 数据组织、存储、管理功能：
      • 文件结构和存取方式
      • 数据如何联系
      • 提高存储空间利用率、方便存取
    • 数据操纵功能：
      • 提供数据操纵语言（Data Manipulation Language, DML）
      • 操纵数据实现基本操作，如查询、插入、删除和修改
    • 数据库的事务管理和运行管理：
      • 保证数据的安全性、完整性
      • 多用户对数据的并发使用
      • 发生故障后的系统恢复
    • 数据库的建立和维护功能：实用程序或管理工具
      • 数据库数据批量装载和转储
      • 介质故障恢复
      • 数据库的重组织
      • 性能监视、分析
    • 其他功能：
      • 数据库管理系统与网络中其它软件系统的通信
      • 数据库管理系统各系统之间的数据转换
      • 异构数据库之间的互访和互操作

• 数据库系统 (DataBase System, DBS)：

  • 定义：在计算机系统中引入数据库和 DBMS 后的系统构成

    • 在不引起混淆的情况下，常常把数据库系统简称为数据库

  • 构成：由数据库、数据库管理系统（及其应用开发工具）、应用系统、数据库管理员（DataBase Administrator, DBA）构成

  • 结构：

    

1.2 数据库管理技术的产生与发展

• 数据管理技术：

  • 定义：对数据进行分类、组织、编码、存储、检索和维护，是数据处理和数据分析的中心问题
  • 发展过程：
    • 人工管理阶段：40 年代 – 50 年代中
    • 文件系统阶段：50 年代末 – 60 年代中
    • 数据库系统阶段：60 年代末 – 现在

• 人工管理阶段：40 年代中 – 50 年代中

  • 背景：

    • 应用背景：计算机主要用于科学计算
    • 硬件背景：外存只有磁带、卡片、纸带，没有直接存储设备
    • 软件背景：没有操作系统、没有管理数据的软件
    • 处理方式：批处理

  • 特点：

    • 数据不保存，没有文件的概念
    • 应用程序管理数据，程序员负担很重
    • 数据面向某个应用程序，无共享，冗余度大
    • 应用程序与数据的关系：一一对应，数据不具有独立性

    

• 文件系统阶段：50 年代末 – 60 年代中

  • 背景：

    • 应用需求：科学计算、管理
    • 硬件水平：磁盘、磁鼓等存储设备
    • 软件水平：有文件系统
    • 处理方式：联机实时处理、批处理

  • 特点

    • 数据的管理者：文件系统，数据可长期保存
    • 数据面向的对象：某一应用程序
    • 数据的共享程度：共享性差、冗余度极大
    • 数据的独立性：独立性差，数据的逻辑结构改变必须修改应用程序
    • 数据的结构化：记录内有结构，整体无结构数据
    • 控制能力：应用程序自己控制

    

• 数据库系统阶段：60 年代末以来

  • 背景：

    • 应用需求：大规模管理
    • 硬件水平：大容量磁盘、磁盘列阵
    • 软件水平：有数据库管理系统
    • 处理方式：联机实时处理、分布处理、批处理

  • 特点：

    • 数据的管理者：DBMS
    • 数据面向的对象：现实世界
    • 数据的共享程度：共享性高，冗余度小
    • 数据的独立性：高度的物理独立性和一定的逻辑独立性
    • 数据的结构化：整体结构化，用数据模型来表示
    • 控制能力：由 DBMS 统一管理和控制

    

1.3 数据库系统的特点

• 数据的结构化：整体数据的结构化是数据库的主要特征之一

  • 数据的结构用数据模型描述，无需程序定义和解释
  • 数据可以变长；数据的最小存取单位是数据项
  • 不再仅仅针对某一应用，而是面向整个企业或组织

• 数据的独立性：

  • 物理独立性：
    • 指用户的应用程序与存储在物理磁盘上的数据库中数据是相互独立的
    • 当数据的物理存储改变了，应用程序不用改变
  • 逻辑独立性：
    • 指用户的应用程序与数据库的逻辑结构是相互独立的
    • 数据的逻辑结构改变了，用户程序也可以不变

• 数据的高共享性：数据面向整个系统，可以被多个用户、多个应用共享使用

  • 好处：
    • 降低数据的冗余度，节省存储空间
    • 避免数据间的不一致性和不相容性
    • 数据库系统弹性大，易于扩充

• 数据由 DBMS 统一管理和控制：

  • 数据的安全性（Security）保护：使每个用户只能按指定方式使用和处理指定数据，保护数据以防止不合法的使用造成的数据的泄密和破坏
  • 数据的完整性（Integrity）检查：保持数据的正确性、有效性、相容性；将数据控制在有效的范围内，保证数据之间满足一定的关系
  • 并发（Concurrency）控制：对多用户的并发操作加以控制和协调，防止相互干扰而得到错误的结果
  • 数据库恢复（Recovery）：将数据库从错误状态恢复到某一已知的正确状态

2. 数据模型

• 作用：抽象、表示和处理现实世界中的数据和信息
  • 数据模型就是现实世界数据特征的抽象
• 要求：
  • 能比较真实地模拟现实世界
  • 容易为人所理解
  • 便于在计算机上实现

2.1 数据建模

• 数据建模：把现实世界的具体事物抽象、组织为某一数据库管理系统支持的数据模型

• 两步抽象：

  • 建立概念模型：将现实世界抽象为信息世界
    • 概念模型：按用户的观点来对数据和信息建模，用于数据库设计
  • 将概念模型转换为数据模型：将信息世界转换为机器世界
    • 数据模型：按计算机系统的观点对数据建模，是 DBMS 支持的，用于 DBMS 的实现

2.2 概念模型

• 概念模型：

  • 用途：
    • 用于信息世界的建模
    • 是现实世界到机器世界的一个中间层次
    • 是数据库设计的有力工具
    • 数据库设计人员和用户之间进行交流的语言
  • 基本要求：
    • 较强的语义表达能力
    • 简单、清晰、易于用户理解
    • 易于更改和扩充
    • 易于向各种数据模型进行转换

• 信息世界的基本概念：

  • 实体（Entity）：客观存在并可相互区别的事物
    • 可以是具体的人、事、物或抽象的概念
  • 属性（Attribute）：实体所具有的某一特性
    • 一个实体可以由若干个属性来刻画
  • 码（Key）：唯一标识实体的属性集
  • 域（Domain）：属性的取值范围
  • 实体型（Entity Type）：用实体名及其属性名集合来抽象和刻画的同类实体
    • 具有相同属性的实体必然具有共同的特征和性质
  • 实体集（Entity Set）：同型实体的集合
  • 联系（Relationship）：现实世界中事物内部以及事物之间的联系，在信息世界中反映为实体内部的联系（组成实体的各属性之间的联系）和实体之间的联系（不同实体集之间的联系）

• 概念模型的表示方法：概念模型的表示方法很多，最常用的是实体－联系模型 (Entity-Relationship model)，简称 E-R 模型

  • 实体-联系模型：

    • 用 E-R 图来描述现实世界的概念模型
    • 提供了表示实体型、属性和联系的方法

  • E-R 图：

    • 实体型：用矩形表示，矩形框内写明实体名
    • 属性：用椭圆形表示，并用无向边将其与相应的实体连接起来
    • 联系：用菱形表示，菱形框内写明联系名，并用无向边分别与有关实体连接起来，同时在无向边旁标上联系的类型（1:1、1:n 或 m:n）
    • 联系的属性：用无向边与该联系连起来
      • 联系本身也是一种实体型，也可以有属性

  • 联系的度：参与联系的实体型的数目

    • 两个实体型之间的联系度为 2，称为二元联系
    • 三个实体型之间的联系度为 3，称为三元联系
    • $N$ 个实体型之间的联系度为 N，称为 $N$ 元联系

  • 两个实体型之间的联系：

    

    • 一对一联系：如果对于实体集 $A$ 中的每一个实体，实体集 $B$ 中至多有一个实体与之联系，反之亦然，则称实体集 $A$ 与实体集 $B$ 具有一对一联系，记为 1:1

      • 例如，班级与班长之间的联系：一个班级只有一个正班长，一个班长只在一个班中任职

    • 一对多联系：如果对于实体集 $A$ 中的每一个实体，实体集 $B$ 中有 $n$ 个实体 $(n\ge 0)$ 与之联系，反之，对于实体集 $B$ 中的每一个实体，实体集 $A$ 中至多只有一个实体与之联系，则称实体集 $A$ 与实体集 $B$ 有一对多联系，记为 1:n

      • 例如，班级与学生之间的联系：一个班级中有若干名学生，每个学生只在一个班级中学习

    • 多对多联系：如果对于实体集 $A$ 中的每一个实体，实体集 $B$ 中有 $n$ 个实体 $(n \ge 0)$ 与之联系，反之，对于实体集 $B$ 中的每一个实体，实体集 $A$ 中也有 $m$ 个实体 $(m \ge 0)$ 与之联系，则称实体集 $A$ 与实体 $B$ 具有多对多联系，记为 $m: n$

      • 例如，课程与学生之间的联系：一门课程同时有若干个同学选修，一个学生可以同时选修多门课程

  • 多个实体型之间的联系：

    • 一对多联系：若实体型 $E_1, E_2, \dots，E_n$ 存在联系，对于实体型 $E_j$（$j=1, 2, \dots, i-1, i+1, \dots, n$）中的给定实体，最多只和 $E_i$ 中的一个实体相联系，则我们说 $E_i$ 与 $E_1, E_2, \dots, E_{i-1}, E_{i+1}, \dots, E_n$ 之间的联系是一对多的
    • 多对多联系
    • 一对一联系

  • 同一实体集内各实体间的联系：

    • 一对多联系：例如，职工实体集内部具有领导与被领导的联系，某一职工（干部）“领导”若干名职工，一个职工仅被另外一个职工直接领导
    • 一对一联系
    • 多对多联系

2.3 数据模型的组成要素

• 数据模型的组成要素：

  • 数据结构：静态特性
  • 数据操作：动态特性
  • 数据的完整性约束条件

• 数据结构：对系统静态特性的描述

  • 作用：
    • 描述数据库的组成对象及对象之间的联系
    • 经常用数据结构的类型来命名数据模型，例如：层次结构—层次模型、关系结构—关系模型
  • 描述的内容：
    • 与对象的类型、内容、性质有关
    • 与数据之间联系有关的对象

• 数据操作：对系统动态特性的描述

  • 内容：对数据库中各种对象（型）的实例（值）允许执行的操作的集合，包括操作及有关的操作规则
  • 类型：
    • 查询
    • 更新（包括插入、删除、修改）

• 数据的完整性约束条件：一组完整性规则的集合

  • 完整性规则：给定的数据模型中数据及其联系所具有的制约和储存规则
    • 作用：可以限定符合数据模型的数据库状态以及状态的变化，以保证数据的正确、有效、相容
  • 约束条件的定义：
    • 反映和规定本数据模型必须遵守的基本的通用的完整性约束
      • 例如：在关系模型中，任何关系必须满足实体完整性和参照完整性两个条件
    • 提供定义完整性约束条件的机制，以反映具体应用所涉及的数据必须遵守的特定的语义约束条件

2.4 常用的数据模型

• 格式化模型：第一代数据库
  • 层次模型 (Hierarchical Model)
  • 网状模型 (Network Model)
  • 数据结构：以基本层次联系为基本单位
• 关系模型 (Relational Model)：第二代数据库
  • 数据结构：表
• 新一代数据库：
  • 面向对象模型 (Object Oriented Data Model)
  • 对象关系模型 (Object Relational Model)
  • 半结构化的 XML 数据模型
  • 新型数据模型：
    • NoSQL：键值数据模型、文档数据模型、图数据模型
    • NewSQL：时序数据模型、时空数据模型、多媒体数据模型

2.5 层次模型

• 数据结构：树形结构
  • 几个术语:
    • 双亲结点，子女结点
    • 根结点，叶结点
    • 兄弟结点
  • 要求：满足下面两个条件的基本层次联系的集合为层次模型：
    • 有且只有一个结点没有双亲结点，这个结点称为根结点
    • 根以外的其它结点有且只有一个双亲结点
  • 表示方法：
    • 实体型：用记录类型描述，每个结点表示一个记录类型
    • 属性：用字段描述，每个记录类型可包含若干个字段
    • 联系：用结点之间的连线（有向边）表示记录（类型）之间的一对多的父子联系
  • 特点：
    • 结点的双亲是唯一的
    • 只能直接处理一对多的实体联系
    • 每个记录类型定义一个排序字段，也称为码字段
    • 任何记录值只有按其路径查看时，才能显出它的全部意义
    • 没有一个子女记录值能够脱离双亲记录值而独立存在
  • 多对多联系的表示：用层次模型间接表示多对多联系
    • 方法：将多对多联系分解成一对多联系
    • 分解方法：冗余结点法、虚拟结点法

• 数据操纵：查询、插入、删除、更新

• 完整性约束：

  • 无相应的双亲结点值就不能插入子女结点值
  • 如果删除双亲结点值，则相应的子女结点值也被同时删除
  • 更新操作时，应更新所有相应记录，以保证数据的一致性

• 存储结构：

  • 邻接法：按照层次树前序遍历的顺序把所有记录值依次邻接存放在物理介质上，即通过物理空间的位置相邻来实现层次顺序
  • 链接法：用指引元来反映数据之间的层次联系，有子女一兄弟链接法、层次序列链接法

• 优点：

  • 层次数据模型简单，对具有一对多的层次关系的部门描述自然、直观，容易理解
  • 查询效率高，性能优于关系模型，不低于网状模型
  • 层次数据模型提供了良好的完整性支持

• 缺点：

  • 多对多联系表示不自然
  • 对插入和删除操作的限制多
  • 查询子女结点必须通过双亲结点
  • 查询及更新操作必须给出完整路径

2.6 网状模型

• 数据结构：图
  • 要求：满足下面两个条件的基本层次联系的集合为网状模型：
    • 允许一个以上的结点无双亲
    • 一个结点可以有多于一个的双亲
  • 表示方法：与层次数据模型相同
    • 实体型：用记录类型描述，每个结点表示一个记录类型
    • 属性：用字段描述，每个记录类型可包含若干个字段
    • 联系：用结点之间的连线表示记录（类）型之间的一对多的父子联系
  • 与层次模型的区别：
    • 网状模型允许多个结点没有双亲结点，允许一个结点有多个双亲结点
    • 网状模型允许两个结点之间有多种联系（复合联系）
    • 网状模型可以更直接地去描述现实世界
    • 层次模型实际上是网状模型的一个特例
  • 多对多联系的表示：用网状模型间接表示多对多联系
    • 方法：将多对多联系直接分解成一对多联系

• 数据操纵：查询、插入、删除、更新

• 完整性约束：网状数据库系统（如 DBTG）对数据操纵加了一些限制，提供了一定的完整性约束

  • 支持记录码的概念
  • 双亲结点与子女结点之间是一对多联系
  • 可以支持属籍类别：
    • 加入类别：双亲记录在，子女记录才可以加入
    • 移出类别：双亲记录删除，子女记录删除

• 存储结构：单向链接、双向链接、环状链接、向首链接

• 优点：

  • 能够更为直接地描述现实世界，如一个结点可以有多个双亲
  • 具有良好的性能，对于预定义的路径，查询存取效率较高

• 缺点：

  • 结构比较复杂，而且随着应用环境的扩大，数据库的结构就变得越来越复杂，不利于最终用户掌握；
  • DDL、DML 语言复杂，用户不容易使用
  • 用户必须了解系统物理结构细节，加重编写和使用应用程序的负担

2.7 关系模型

• 数据结构：在用户观点下，关系模型中数据的逻辑结构是一张二维表，它由行和列组成

  • 基本概念：关系模型建立在集合代数的基础上
    • 关系（Relation）：一个关系对应通常说的一张表
    • 元组（Tuple）：表中的一行即为一个元组
    • 属性（Attribute）：表中的一列即为一个属性，给每一个属性起一个名称即属性名
    • 主码（Key）：表中的某个属性组，它可以唯一确定一个元组
    • 域（Domain）：属性的取值范围来自某个域
    • 分量：元组中的一个属性值
    • 关系模式：对关系的描述
  • 表示方法：
    • 实体型：直接用关系（表）表示
    • 属性：用属性名表示
      • 例：学生（学号，姓名，年龄，性别，系号，年级）
    • 一对一联系：隐含在实体对应的关系中
      • 例：班级（班级号，班级人数，班长学号）
    • 一对多联系：隐含在实体对应的关系中
    • 多对多联系：直接用关系表示
      • 例：选修（学号，课程号，成绩）
  • 规范条件：关系必须是规范化的，满足一定的规范条件
    • 最基本的规范条件：关系的每一个分量必须是一个不可分的数据项，即不允许表中还有表

• 数据操纵：查询、插入、删除、更新

  • 数据操作是集合操作，操作对象和操作结果都是关系，即若干元组的集合
  • 存取路径对用户隐蔽，用户只要指出“干什么”，不必详细说明“怎么干”

• 完整性约束：

  • 实体完整性
  • 参照完整性
  • 用户定义的完整性

• 存储结构：实体及实体间的联系用表来表示，表以文件形式存储

  • 有的 DBMS 一个表对应一个操作系统文件
  • 有的 DBMS 自己设计文件结构

• 优点：

  • 建立在严格的数学概念的基础上
  • 概念单一，数据结构简单、清晰，用户易懂易用
    • 实体和各类联系都用关系来表示
    • 对数据的检索结果也是关系
  • 关系模型的存取路径对用户透明
    • 具有更高的数据独立性，更好的安全保密性
    • 简化了程序员的工作和数据库开发建立的工作

• 缺点：

  • 存取路径对用户隐蔽，导致查询效率往往不如格式化数据模型
  • 为提高性能，必须对用户的查询请求进行优化，增加了开发数据库管理系统的难度

3. 数据库系统结构

• 数据库系统的结构：
  • 从数据库应用开发人员角度：
    • 数据库采用三级模式结构，是数据库系统内部的系统结构
  • 从数据库最终用户角度：
    • 单用户结构
    • 主从式结构
    • 分布式结构
    • 客户—服务器
    • 浏览器—应用服务器/数据库服务器

3.1 数据库系统模式的概念

• “型” 和“值” 的概念：

  • 型（Type）：对某一类数据的结构和属性的说明
  • 值（Value）：型的一个具体赋值

• 模式（Schema）：

  • 数据库全体数据的逻辑结构和特征的描述
  • 是型的描述
  • 反映的是数据的结构及其联系
  • 模式是相对稳定的

• 模式的一个实例（Instance）：

  • 模式的一个具体值
  • 反映数据库某一时刻的状态
  • 同一个模式可以有很多实例
  • 实例随数据库中的数据的更新而变动

3.2 数据库系统的三级模式结构

• 模式（Schema）：也称逻辑模式

  • 数据库中全体数据的逻辑结构和特征的描述
  • 所有用户的公共数据视图，综合了所有用户的需求
  • 特点：一个应用数据库只有一个模式，以数据模型为基础
  • 地位：是数据库系统模式结构的中心（首先确定）
    • 与数据的物理存储细节和硬件环境无关
    • 与具体的应用程序、开发工具及高级程序设计语言无关
  • 定义：模式 DDL，模式描述语言
    • 定义数据的逻辑结构（数据项的名字、类型、取值范围等）
    • 定义数据之间的联系
    • 定义与数据有关的安全性、完整性要求

• 外模式（External Schema）：也称子模式或用户模式

  • 数据库用户（包括应用程序员和最终用户）使用的局部数据的逻辑结构和特征的描述
  • 数据库用户的数据视图，是与某一应用有关的数据的逻辑表示
  • 地位：介于模式与应用之间
    • 模式与外模式的关系：一对多
      • 外模式通常是模式的子集
      • 一个数据库可以有多个外模式，反映了不同的用户的应用需求、看待数据的方式、对数据保密的要求
      • 对模式中同一数据，在外模式中的结构、类型、长度、保密级别等都可以不同
    • 外模式与应用的关系：一对多
      • 同一外模式也可以为某一用户的多个应用系统所使用
      • 但一个应用程序只能使用一个外模式
  • 用途：
    • 保证数据库安全性的一个有力措施
    • 每个用户只能看见和访问所对应的外模式中的数据，简化用户视图

• 内模式（Internal Schema）：也称存储模式

  • 是数据物理结构和存储方式的描述
  • 是数据在数据库内部的表示方式
    • 记录的存储方式（堆存储，聚簇存储，属性升降存储）
    • 索引的组织方式（按照 B+ 树索引，按 hash 索引）
    • 数据是否压缩存储
    • 数据是否加密
    • 数据存储记录结构的规定（定长，变长）
  • 一个数据库只有一个内模式

3.3 数据库的二级映像功能与数据独立性

• 三级模式与二级映象：

  • 三级模式：对数据的三个抽象级别
  • 二级映象：在 DBMS 内部实现这三个抽象层次的联系和转换
    • 外模式/模式映像
    • 模式/内模式映像

• 外模式／模式映象：定义外模式（局部逻辑结构）与模式（全局逻辑结构）之间的对应关系

  • 每一个外模式都对应一个外模式／模式映象
  • 映象定义通常包含在各自外模式的描述中
  • 用途：保证数据的逻辑独立性
    • 当模式改变时，数据库管理员修改有关的外模式／模式映象，使外模式保持不变
    • 应用程序是依据数据的外模式编写的，从而应用程序不必修改，保证了数据与程序的逻辑独立性，简称数据的逻辑独立性

• 模式／内模式映象：定义数据全局逻辑结构与存储结构之间的对应
  关系（例如，说明某个逻辑记录和字段在内部是如何表示的）

  • 数据库中模式／内模式映象是唯一的
  • 该映象定义通常包含在模式描述中
  • 用途：保证数据的物理独立性
    • 当数据库的存储结构改变了（例如选用了另一种存储结构），数据库管理员修改模式／内模式映象，使模式保持不变
    • 应用程序不受影响，保证了数据与程序的物理独立性，简称数据的物理独立性

• 总结：

  • 模式：
    • 描述数据的全局逻辑结构，是数据库的中心与关键
    • 独立于数据库的其它层次
    • 设计数据库模式结构时应首先确定数据库的逻辑模型
  • 内模式：
    • 依赖于全局逻辑结构，但独立于数据库的用户视图即外模式，也独立于具体的存储设备
    • 它将全局逻辑结构中所定义的数据结构及其联系，按照一定的物理存储策略进行组织，以达到较好的时间与空间效率
  • 外模式：
    • 描述的是数据的局部逻辑结构
    • 面向具体的应用程序，定义在逻辑模式之上，但独立于存储模式和存储设备
    • 设计外模式时应充分考虑到应用的扩充性，当应用需求发生较大变化，相应外模式不能满足其视图要求时，该外模式就得做相应改动
  • 应用程序：
    • 在外模式描述的数据结构上编制的，它依赖于特定的外模式，与数据库的模式和存储结构独立
    • 不同的应用程序有时可以共用同一个外模式
  • 二级映象：
    • 保证了数据库外模式的稳定性，从而从底层保证了应用程序的稳定性，除非应用需求本身发生变化，否则应用程序一般不需要修改
    • 保证了数据与程序之间的独立性，使得数据的定义和描述可以从应用程序中分离出去

4. 数据库系统的组成

• 数据库系统的组成：数据库、数据库管理系统（及其开发工具）、应用系统、数据库管理员、（用户）

• 硬件平台：

  • 数据库管理系统建立在计算机硬件平台和操作系统之上，数据库存放在计算机存储设备中
  • 硬件平台中存储器与处理器技术的升级推动了数据库技术从磁盘数据库到内存数据库的技术升级
  • 海量存储设备与高速处理器的硬件特性成为新型数据库存储引擎和查询处理引擎设计的重要因素

• 软件平台：

  • DBMS（数据库管理系统）
  • 操作系统
  • 与数据库接口的高级语言及其编译系统
  • 以 DBMS 为核心的应用开发工具
  • 为特定应用环境开发的数据库应用系统

• 人员：

  • 数据库管理员 (DBA)：

    • 设计与定义数据库：
      • 参与数据库设计的全过程
      • 与用户、应用开发人员、系统分析员密切结合
      • 设计概念模式、数据库模式以及各个应用的外模式
      • 熟悉 DBMS 产品，决定数据库的存储结构和存取策略，设计数据库的内模式
    • 帮助最终用户使用数据库系统
    • 负责数据库系统的运维工作：
      • 负责监视数据库系统的运行情况
      • 及时处理运行过程中出现的问题
      • 控制不同用户访问数据库的权限
      • 收集数据库的审计信息，保证数据库的安全性和完整性
    • 改进和重组数据库系统，调优数据库系统的性能：
      • 负责监视、分析数据库系统的性能，包括空间利用率和处理效率；根据实际应用环境不断改进数据库设计
      • 数据库运行过程中不断地插入、删除、修改数据，DBA 要定期地或按一定的策略对数据库进行重组织
    • 转储与恢复数据库：
      • 为减少硬件、软件或人为故障对数据库系统的破坏，DBA 必须定义和实施适当的后援和恢复策略
      • 一旦系统故障，DBA 必须能够在最短时间内把数据库恢复到某一正确状态
    • 重构数据库：
      • 用户应用需求改变时，DBA 需要重新构造数据库，包括修改内模式或模式

  • 系统分析员：

    • 负责应用系统的需求分析和规范说明
    • 与用户及 DBA 协商，确定系统的硬软件配置
    • 参与数据库系统的概要设计

  • 数据库设计人员：

    • 参加用户需求调查和系统分析
    • 确定数据库中的数据
    • 设计数据库各级模式

  • 应用程序员：

    • 设计和编写应用系统的程序模块
    • 进行调试和安装

  • 用户：

    • 偶然用户：
      • 不经常访问数据库，每次访问需要不同数据库信息
      • 企业或组织机构的高中级管理人员
    • 简单用户：
      • 主要工作是查询和更新数据库
      • 银行的职员、机票预定人员、旅馆总台服务员
    • 复杂用户：
      • 工程师、科学家、经济学家、科技工作者等
      • 直接使用数据库语言访问数据库，甚至能够基于数据库管理系统的 API 编制自己的应用程序

5. 数据库的现状与展望

• 数据库系统的体系结构：集中式数据库系统、客户-服务器数据库系统、并行数据库系统、分布式数据库系统、云数据库系统

第二章 关系模型和关系运算理论

1. 关系模型概述

• 关系数据库简介：

  • 系统而严格地提出关系模型的是美国 IBM 公司的 E.F.Codd
  • 关系数据库应用数学方法来处理数据库中的数据
  • 80 年代后，关系数据库系统成为最重要、最流行的数据库系统
  • 典型实验系统：System R、INGRES
  • 典型商用系统：ORACLE、SYBASE、INFORMIX、DB2、INGRES

• 关系模型概述：

  • 关系数据库系统：支持关系模型的数据库系统
  • 关系模型的组成：关系数据结构、关系操作集合、关系完整性约束

• 关系数据结构：

  • 单一的数据结构：现实世界的实体以及实体间的各种联系均用关系来表示
  • 数据的逻辑结构：从用户角度，关系模型中数据的逻辑结构是一张二维表

• 关系操作集合：

  • 常用的关系操作：
    • 查询：选择、投影、连接、除、并、交、差
    • 数据更新：插入、删除、修改
  • 查询的表达能力是其中最主要的部分

• 关系的三类完整性约束：

  • 实体完整性：通常由关系系统自动支持
  • 参照完整性：早期系统不支持，目前大型系统能自动支持
  • 用户定义的完整性：
    • 反映应用领域需要遵循的约束条件，体现了具体领域中的语义约束
    • 用户定义后由系统支持

2. 关系数据结构

关系模型建立在集合代数的基础上.

2.1 关系

• 域（Domain）：一组具有相同数据类型的值的集合

  • 整数、实数、介于某个取值范围的整数
  • 长度指定长度的字符串集合、{‘男’，‘女’}、介于某个取值范围的日期

• 笛卡儿积（Cartesian Product）：域上的一种集合运算

  • 笛卡儿积：给定一组域 $D_1, D_2, \cdots, D_n$（这些域中可以有相同的），其笛卡儿积为：

    $$D_1 \times D_2 \times \cdots \times D_n=\left\{\left(d_1, d_2, \ldots, d_n\right) | d_i \in D_i, i=1,2, \ldots, n\right\}$$

    • 含义：所有域的所有取值的一个组合，不能重复
  • 基数（Cardinal number）：一个域允许的不同取值个数，若 $D_i(i=1,2, \cdots, n)$ 为有限集，其基数为 $m_i(i=1,2, \cdots, n)$，则 $D_1 \times D_2 \times \ldots \times D_n$ 的基数 $M$ 为：

    $$M=\prod_{i=1}^n m_i$$

  • 笛卡儿积的表示方法：可表示为一个二维表，表中的每行对应一个元组，表中的每列对应一个域

• 关系（Relation）：

  • 关系：$D_1 \times D_2 \times \cdots \times D_n$ 的子集叫作在域 $D_1, D_2, \cdots, D_n$ 上的关系，表示为 $R\left(D_1, D_2, \cdots, D_n\right)$

    • $R$：关系名；$n$：关系的目或度（Degree）

  • 元组：关系中的每个元素是关系中的元组，通常用 $t$ 表示

  • 单元关系与二元关系：

    • 当 $n = 1$ 时，称该关系为单元关系（Unary relation）
    • 当 $n = 2$ 时，称该关系为二元关系（Binary relation）

  • 关系的表示：也是一个二维表，表的每行对应一个元组，表的每列对应一个域

  • 属性：关系中不同列可以对应相同的域，为了加以区分，必须对每列起一个名字，称为属性（Attribute）

    • $n$ 目关系必有 $n$ 个属性

  • 码：

    • 候选码（Candidate key）：若关系中的某一属性组的值能唯一地标识一个元组，而其子集不能，则称该属性组为候选码；在最简单的情况下，候选码只包含一个属性
    • 全码（All-key）：在最极端的情况下，关系模式的所有属性组是这个关系模式的候选码，称为全码（All-key）
    • 主码（Primary key）：
      • 若一个关系有多个候选码，则选定其中一个为主码
      • 候选码的诸属性称为主属性（Prime attribute）
      • 不包含在任何侯选码中的属性称为非主属性（Non-key attribute）

  • 三类关系：

    • 基本关系（基本表或基表）：实际存在的表，是实际存储数据的逻辑表示
    • 查询表：查询结果对应的表
    • 视图表：由基本表或其他视图表导出的表，是虚表，不对应实际存储的数据

  • 注意：

    • 关系是笛卡儿积的有限子集，无限关系在数据库系统中是无意义的
    • 笛卡儿积不满足交换律，但关系作为关系数据模型的数据结构，满足交换律，因为为关系的每个列附加一个属性名取消了关系属性的有序性

  • 基本关系的性质：

    • 列是同质的（Homogeneous）：每一列中的分量是同一类型的数据，来自同一个域
    • 不同的列可出自同一个域：其中的每一列称为一个属性不同的属性要给予不同的属性名
    • 列的顺序无所谓：列的次序可以任意交换
    • 任意两个元组的候选码不能完全相同：由笛卡儿积的性质决定
    • 行的顺序无所谓：行的次序可以任意交换
    • 分量必须取原子值：每一个分量都必须是不可分的数据项，这是规范条件中最基本的一条

2.2 关系模式

• 关系模式（Relation Schema）：

  • 关系模式是型，关系是值
  • 关系模式是对关系的描述
    • 元组集合的结构：属性构成、属性来自的域、属性与域之间的映象关系
    • 元组语义以及完整性约束条件
    • 属性间的数据依赖关系集合

• 定义关系模式：

  • 关系模式可以形式化地表示为 $R(U, D, dom, F)$
    • $R$：关系名
    • $U$：组成该关系的属性名集合
    • $D$：属性组 $U$ 中属性所来自的域
    • $dom$：属性向域的映象集合
    • $F$：属性间的数据依赖关系集合
  • 通常可以简记为 $R(U)$ 或 $R\left(A_1, A_2, \cdots, A_n\right)$
    • $R$：关系名
    • $A_1, A_2, \cdots, A_n$：属性名
    • 域名及属性向域的映象常常直接说明为属性的类型、长度

• 关系模式与关系：

  • 关系模式：
    • 对关系的描述
    • 静态的、稳定的
  • 关系：
    • 关系模式在某一时刻的状态或内容
    • 动态的、随时间不断变化的
  • 关系模式和关系往往统称为关系，通过上下文加以区别

2.3 关系数据库

• 关系数据库系统：支持关系模型的数据库系统

  • 关系模型中，实体以及实体间的联系都用关系表示
  • 在一个关系数据库中，某一时刻所有关系模式对应的关系的集合构成一个关系数据库

• 关系数据库的型与值：关系数据库也有型和值之分

  • 关系数据库的型：关系数据库中所有关系模式的集合，是对关系数据库的描述
    • 若干域的定义
    • 在这些域上定义的若干关系模式
  • 关系数据库的值：是这些关系模式在某一时刻对应的关系的集合，通常简称为关系数据库

• 关系模型的存储结构：

  • 关系数据库管理系统以一定的组织方式来存储和管理数据，即设计和实现关系模型的存储结构
  • 有的关系数据库管理系统中一个表对应一个操作系统文件，将物理数据组织的任务交给操作系统完成
  • 有的关系数据库管理系统从操作系统那里申请若干个大的文件，自己划分文件空间，组织表、索引等存储结构，并进行存储管理

3. 关系操作

• 常用的关系操作：

  • 查询的表达能力是其中最主要的部分
  • 查询：选择、投影、连接、除、交、并、差、笛卡儿积（加粗的是 5 种基本运算）
  • 数据更新：插入、删除、修改

• 关系操作的特点：集合操作方式，即操作的对象和结果都是集合

  • 非关系数据模型的数据操作方式：一次一记录
  • 关系数据模型的数据操作方式：一次一集合

• 关系数据语言的种类：

  • 关系演算（逻辑方式）：用谓词来表达查询要求
    • 元组关系演算语言：
      • 谓词变元的基本对象是元组变量
      • 典型代表：APLHA, QUEL
    • 域关系演算语言：
      • 谓词变元的基本对象是域变量
      • 典型代表：QBE
  • 关系代数（代数方式）：用对关系的运算来表达查询要求
    • 典型代表：ISBL
  • 结构化查询语言：具有关系代数和关系演算双重特点
    • 集合了 DQL、DDL、DML、DCL
    • 典型代表：SQL

• 关系数据语言的特点：

  • SQL 语言是一种高度非过程化的集合操作语言：
    • 存取路径的选择由 DBMS 的优化机制来完成
    • 用户不必用循环结构就可以完成数据操作
  • 能够嵌入高级语言中使用；
  • 关系代数、元组关系演算和域关系演算三种语言在表达能力上完全等价，具有完备的表达能力（关系完备性）

4. 关系的完整性

• 关系的完整性：关系模型的完整性规则是对关系的某种约束条件

  • 关系模型中三类完整性约束：实体完整性、参照完整性、用户定义的完整性
  • 注意：实体完整性和参照完整性是关系模型必须满足的完整性约束条件，被称作是关系的两个不变性，应该由关系系统自动支持

• 实体完整性：

  • 实体完整性规则（Entity Integrity）：若属性（指一个或一组属性）$A$ 是基本关系 $R$ 的主属性，则属性 $A$ 不能取空值

    • 空值就是“不存在”或“无意义”的值

  • 关系模型必须遵守实体完整性规则的原因：

    • 实体完整性规则是针对基本关系而言的，一个基本表通常对应现实世界的一个实体集或多对多联系
    • 现实世界中的实体和实体间的联系都是可区分的，即它们具有某种唯一性标识，关系模型中以主码作为唯一性标识

• 参照完整性：

  • 关系间的引用：在关系模型中实体及实体间的联系都是用关系来描述的，因此可能存在着关系与关系间的引用

  • 外码：设 $F$ 是基本关系 $R$ 的一个或一组属性，但不是关系 $R$ 的码，如果 $F$ 与基本关系 $S$ 的主码 $K_s$ 相对应，则称 $F$ 是基本关系 $R$ 的外码（Foreign Key）

    • 基本关系 $R$ 称为参照关系（Referencing Relation）
    • 基本关系 $S$ 称为被参照关系（Referenced Relation）或目标关系（Target Relation）
    • 当外码与相应的主码属于不同关系时，往往取相同的名字，以便于识别
    • 目标关系 $S$ 的主码 $K_s$ 和参照关系的外码 $F$ 必须定义在同一个（或一组）域上
    • 关系 $R$ 和 $S$ 不一定是不同的关系
    • 外码并不一定要与相应的主码同名

  • 参照完整性规则：若属性（或属性组）$F$ 是基本关系 $R$ 的外码，它与基本关系 $S$ 的主码 $K_s$ 相对应（基本关系 $R$ 和 $S$ 不一定是不同的关系），则对于 $R$ 中每个元组在 $F$ 上的值必须为：

    • 或者取空值（$F$ 的每个属性值均为空值）
    • 或者等于 $S$ 中某个元组的主码值

  • 可能破坏参照完整性的情况：

    被参照表	参照表	速约处理
    可能破坏参照完整性	插入元组	拒绝
    可能破坏参照完整性	修改外码值	拒绝
    删除元组	可能破坏参照完整性	拒绝／级联删除／设置为空值
    修改主码值	可能破坏参照完整性	拒绝／级联删除／设置为空值

• 用户定义的完整性：

  • 用户定义的完整性是针对某一具体关系数据库的约束条件，反映某一具体应用所涉及的数据必须满足的语义要求
  • 关系模型应提供定义和检验这类完整性的机制，以便用统一的系统的方法处理它们，而不要由应用程序承担这一功能

• DBMS 的完整性控制机制：

  • 定义完整性约束条件的机制：完整性约束命名子句、断言、触发器等
  • 提供完整性检查的方法：一般在 INSERT、UPDATE、DELETE 语句执行后开始检查，也可在事务提交时检查
  • 进行违约处理

5. 关系代数

• 关系代数：一种抽象的查询语言，用对关系的运算来表达查询，包含三个要素：

  • 运算对象：关系
  • 运算结果：关系
  • 运算符：四类

• 关系代数的四类运算符：

  • 集合运算符：$\cup$（并）、$- $（**差**）、$\cap$（交）、$\times$（笛卡儿积）
    • 将关系看成元组的集合
    • 运算是从关系的“水平”方向即行的角度来进行
  • 比较运算符：$＞$（大于）、$\ge$（大于等于）、$<$（小于）、$\le$（小于等于）、$=$（等于）、$<>$（不等于）
    • 辅助专门的关系运算符进行操作
  • 专门的关系运算符：$\sigma$（选择）、$\pi$（投影）、$\bowtie$（连接）、$\div$（除）
    • 不仅涉及行而且涉及列
  • 逻辑运算符：$\lnot$（非）、$\land$（与）、$\lor$（或）
    • 辅助专门的关系运算符进行操作

关系代数的表示记号

• $R$，$t\in R$，$t[A_i]$

  • 设关系模式为 $R(A_1, A_2, \ldots, A_n)$
  • 它的一个关系设为 $R$
  • $t \in R$ 表示 $t$ 是 $R$ 的一个元组
  • $t[A_i]$ 则表示元组 $t$ 中相应于属性 $A_i$ 的一个分量

• $A$，$t[A]$，$\bar{A}$

  • 若 $A=\left\{A_{i 1}, A_{i 2}, \ldots, A_{i k}\right\}$ ，其中 $A_{i 1}, A_{i 2}, \ldots, A_{i k}$ 是 $A_1, A_2, \ldots, A_n$ 中的一部分，则 $A$ 称为属性列或属性组
  • $t[A]=\left(t\left[A_{i 1}\right], t\left[A_{i 2}\right], \ldots, t\left[A_{i k}\right]\right)$，表示元组 $t$ 在属性列 $A$ 上诸分量的集合
  • $\bar{A}$ 则表示 $\left\{A_1, A_2, \ldots, A_n\right\}$ 中去掉 $\left\{A_{i 1}, A_{i 2}, \ldots, A_{i k}\right\}$ 后剩余的属性组

• $\overset{\frown}{t_r t_s}$

  • $R$ 为 $n$ 目关系，$S$ 为 $m$ 目关系，$t_r \in R$，$t_s \in S$，$\overset{\frown}{t_r t_s}$ 称为元组的连接（元组的串接）
  • 它是一个 $n+m$ 列的元组，前 $n$ 个分量为 $R$ 中的一个 $n$ 元组，后 $m$ 个分量为 $S$ 中的一个 $m$ 元组

• 象集 $Z_x$

  • 给定一个关系 $R(X, Z)$，$X$ 和 $Z$ 为属性组
  • 当 $t[X]=x$ 时，$x$ 在 $R$ 中的象集（Images Set） 为

  $$Z_x=\{t[Z] \mid t \in R, t[X]=x \}$$

  • 它表示 $R$ 中属性组 $X$ 上值为 $x$ 的诸元组在 $Z$ 上分量的集合

传统的集合运算

• 并（Union）：

  • $R$ 和 $S$ 具有相同的目 $n$（即两个关系都有 $n$ 个属性），相应的属性取自同一个域
  • $R \cup S$ 仍为 $n$ 目关系，由属于 $R$ 或属于 $S$ 的元组组成：

    $$R \cup S=\{t \mid t \in R \vee t \in S\}$$

  • $R \cup S = S \cup R$

• 差（Difference）:

  • $R$ 和 $S$ 具有相同的目 $n$，相应的属性取自同一个域
  • $R - S$ 仍为 $n$ 目关系，由属于 $R$ 而不属于 $S$ 的所有元组组成：

    $$R-S=\{t \mid t \in R \wedge t \notin S\}$$

  • $R - S \neq S - R$

• 交（Intersection）：

  • $R$ 和 $S$ 具有相同的目 $n$，相应的属性取自同一个域
  • $R \cap S$ 仍为 $n$ 目关系，由既属于 $R$ 又属于 $S$ 的元组组成：

    $$R \cap S=\{t \mid t \in R \wedge t \in S\}$$

  • $R \cap S = S \cap R$

• 广义笛卡儿积（Extended Cartesian Product）：

  • $R$，$n$ 目关系，$k_1$ 个元组；$S$，$m$ 目关系，$k_2$ 个元组

  • $$R \times S=\{\overset{\frown}{t_r t_s} \mid t_{\mathrm{r}} \in R \wedge t_{\mathrm{s}} \in S\}$$

    • 列：$(n+m)$ 列的元组的集合，元组的前 $n$ 列是关系 $R$ 的一个元组，后 $m$ 列是关系 $S$ 的一个元组
    • 行：$k_1\times k_2$ 个元组

专门的关系运算

• 选择（Selection）：对关系进行水平分割，又称为限制（Restriction）

  • 含义：在关系 $R$ 中选择满足给定条件的诸元组

    $$\sigma_{\mathrm{F}}(R)=\left\{t \mid t \in R \wedge F(t)= \text { '真' }\right\}$$

    • $F$：选择条件，是一个逻辑表达式，基本形式为：

      $$\left[\neg(] X_1 \theta Y_1[)\right]\left[\varphi\left[\neg(] X_2 \theta Y_2[)\right]\right] \ldots$$

      • $\theta$ ：比较运算符 $(>, \geqslant,<, \leqslant,=$ 或 $<>)$
      • $\mathrm{X}_1, \mathrm{Y}_1$ 等：属性名、常量、简单函数，属性名也可以用它的序号来代替
      • $\varphi$ ：逻辑运算符（$\neg$、 $\wedge$ 或 $\vee$ ）
      • $[]$：表示任选项
      • $\ldots$：表示上述格式可以重复下去
  • 选择运算是从行的角度进行的运算，选出那些满足条件的元组

• 投影（Projection）：对关系进行垂直分割

  • 含义：从 $R$ 中选择出若干属性列组成新的关系：

    $$\pi_A(R)=\{t[A] \mid t \in R\}$$

    • $A$：$R$ 中的属性列
  • 投影操作主要是从列的角度进行运算，但投影之后不仅取消了原关系中的某些列，而且还可能取消某些元组（避免重复行）

• 连接（Join）：关系的合并，也称为 $\theta$ 连接

  • 含义：从两个关系的笛卡儿积中选取属性间满足一定条件的元组

    $$R \underset{A\theta B}{\bowtie} S = \{ \overset{\frown}{t_r t_s} \mid t_r \in R \land t_s \in S \land t_r[A] \theta t_s[B] \}$$

    • $A$ 和 $B$：分别为 $R$ 和 $S$ 上度数相等且可比的属性组
    • $\theta$：比较运算符
  • 常用连接运算：
    • 等值连接（equijoin）：$\theta$ 为 “$＝$” 的连接运算称为等值连接
      • 含义：从关系 $R$ 与 $S$ 的广义笛卡儿积中选取 $A$、$B$ 属性值相等的那些元组，即：

        $$R \underset{A = B}{\bowtie} S = \{ \overset{\frown}{t_r t_s} \mid t_r \in R \land t_s \in S \land t_r[A] = t_s[B] \}$$

    • 自然连接（Natural join）：自然连接是一种特殊的等值连接
      • 两个关系中进行比较的分量必须是相同的属性组，在结果中把重复的属性列去掉
      • 含义：$R$ 和 $S$ 具有相同的属性组 $B$，$U$ 为 $R$ 和 $S$ 的全体属性集合

        $$R \bowtie S = \{ \overset{\frown}{t_r t_s}[U-B] \mid t_r \in R \land t_s \in S \land t_r[B] = t_s[B] \}$$

    • 外连接（Outer Join）：如果把舍弃的元组也保存在结果关系中，而在其他属性上填空值(Null)，这种连接就叫做外连接(OUTER JOIN)
    • 左外连接（LEFT OUTER JOIN 或 LEFT JOIN）：如果只把左边关系 $R$ 中要舍弃的元组（即悬浮元组）保留就叫做左外连接
    • 右外连接（RIGHT OUTER JOIN 或 RIGHT JOIN）：如果只把右边关系 $S$ 中要舍弃的元组（即悬浮元组）保留就叫做右外连接
  • 注意：
    • 选择和投影运算的时间复杂度为 $n$ 数量级（$n$ 为元组个数）
    • 连接运算的时间复杂度为 $n \times m$ 数量级（$n$ 和 $m$ 分别是两个关系中的元组个数）
    • 为了减少关系运算的时间复杂度，从而提高效率，通常先做选择运算，再做投影运算，最后做连接运算

• 除（Division）：

  • 含义：
    • 给定关系 $R (X,Y)$ 和 $S (Y,Z)$，其中 $X, Y, Z$ 为属性组- $R$ 中的 $Y$ 与 $S$ 中的 $Y$ 可以有不同的属性名，但必须出自相同的域集
    • $R$ 与 $S$ 的除运算得到一个新的关系 $P(X)$，$P$ 是 $R$ 中满足下列条件的元组在 $X$ 属性列上的投影：元组在 $X$ 上分量值 $x$ 的象集 $Y_x$ 包含 $S$ 在 $Y$ 上投影的集合

      $$R \div S=\left\{t_r[X] \mid t_r \in R \wedge \pi_Y(S) \subseteq Y_x\right\}$$

      其中 $Y_x$ 是 $x$ 在 $R$ 中的象集，即 $x=t_r[X]$
  • 除操作是同时从行和列角度进行运算

第三章 关系规范化基础

1. 问题的提出

• 关系数据库逻辑设计：
  • 针对一个具体应用问题，如何构造一个适合于它的数据模式？
    • 应该构造几个关系，每个关系由哪些属性组成？
    • 如何判断这个模式是好的，也就是设计标准如何？
  • 数据库逻辑设计的工具：关系数据库的规范化理论
    • 给出判断数据库逻辑设计“好坏程度”的准则
    • 如果逻辑设计中存在“不好”的关系模式，如何将其修改为“好”的关系模式

概念回顾

• 关系：描述实体、属性、实体间的联系
  • 从形式上看，它是一张二维表，是所涉及属性的笛卡尔积的一个子集
• 关系模式：用来定义关系
• 关系数据库：基于关系模型的数据库，利用关系来描述现实世界
  • 从形式上看，它由一组关系组成
• 关系数据库的模式：定义这组关系的关系模式的全体

关系模式的形式化定义

• 形式化定义：关系模式由五部分组成，即它是一个五元组：

  $$\mathrm{R}(\mathrm{U}, \mathrm{D}, \mathrm{DOM}, \mathrm{F})$$

  • $\mathrm{R}$：关系名
  • $\mathrm{U}$： 组成该关系的属性名集合
  • $\mathrm{D}$： 属性组 $\mathrm{U}$ 中属性所来自的域
  • $\mathrm{DOM}$： 属性向域的映象集合
  • $\mathrm{F}$： 属性间数据的依赖关系集合

• 简化表示：$\mathrm{R}(\mathrm{U}, \mathrm{D}, \mathrm{DOM}, \mathrm{F})$ 可以简化为一个三元组：

  $$\mathrm{R}(\mathrm{U}, \mathrm{F})$$

  • 当且仅当 $\mathrm{U}$ 上的一个关系 $\mathrm{r}$ 满足 $\mathrm{F}$ 时，$\mathrm{r}$ 称为关系模式 $\mathrm{R}(\mathrm{U}, \mathrm{F})$的一个关系

什么是数据依赖

• 数据依赖：
  • 是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系
  • 是现实世界属性间相互联系的抽象，是数据内在的性质，是语义的体现
  • 常见的数据依赖：函数依赖(FunctionalDependency, FD)、多值依赖(Multivalue Dependency, MVD)、联结依赖等
    • 例如，“学号”函数决定“姓名”和“所在系”，或者说“姓名”和“所在系”函数依赖于“学号”

数据依赖对关系模式的影响

• 关系模式 Student<U, F> 中存在的问题：

  • 数据冗余太大(Data redundancy)：浪费大量的存储空间
    • 例：每一个系主任的姓名重复出现
  • 更新异常(Update anomaly)：数据冗余，更新数据时，维护数据完整性代价大
    • 例：某系更换系主任后，系统必须修改与该系学生有关的每一个元组
  • 插入异常(Insert anomaly)：该插的数据插不进去
    • 例：如果一个系刚成立，尚无学生，我们就无法把这个系及其系主任的信息存入数据库
  • 删除异常(Deletion anomaly)：不该删除的数据不得不删
    • 例：如果某个系的学生全部毕业了，我们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了

• 结论：Student 关系模式不是一个好的模式

  • “好”的模式：
    • 不会发生插入异常、删除异常、更新异常
    • 数据冗余应尽可能少
  • 原因：由存在于模式中的某些数据依赖引起的
  • 解决方法：通过规范化理论改造关系模式，消除其中不合适的数据依赖

2. 数据依赖

规范化理论正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题.

函数依赖

• 定义：设 $R(U,F)$ 是一个属性集 $U$ 上的关系模式，$X$ 和 $Y$ 是 $U$ 的子集

  • 若对于 $R(U,F)$ 的任意一个可能的关系 $r$，$r$ 中不可能存在两个元组在 $X$ 上的属性值相等，而在 $Y$ 上的属性值不等，则称 “$X$ 函数确定 $Y$” 或 “$Y$ 函数依赖于 $X$”，记作 $X \to Y$
  • $X$ 称为这个函数依赖的决定属性组，又称决定因素(Determinant)
  • 若 $X \to Y$，并且 $Y \to X$，则记为 $X \leftrightarrow Y$
  • 若 $Y$ 不函数依赖于 $X$，则记为 $X \nrightarrow Y$

• 说明：

  • 函数依赖不是指关系模式 $R$ 的某个或某些关系实例满足的约束条件，而是指关系模型 $R$ 在任何时刻的关系实例均要满足的约束条件
  • 函数依赖是语义范畴的概念，只能根据数据的语义来确定函数依赖
    • 例如，“姓名→年龄”这个函数依赖只有在不允许有同名人的条件下成立
  • 数据库设计者可以对现实世界作强制的规定
    • 例如，规定不允许同名人出现，函数依赖“姓名→年龄”成立，所插入的元组必须满足规定的函数依赖，若发现有同名人存在，则拒绝装入该元组

平凡函数依赖与非平凡函数依赖

• 定义：在关系模式 $R(U,F)$ 中，对于 $U$ 的子集 $X$ 和 $Y$

  • 如果 $X \rightarrow Y$ ，但 $Y \nsubseteq X$ ，则称 $X \rightarrow Y$ 是非平凡的函数依赖
  • 若 $\mathrm{X} \rightarrow \mathrm{Y}$ ，但 $\mathrm{Y} \subseteq \mathrm{X}$ ，则称 $\mathrm{X} \rightarrow \mathrm{Y}$ 是平凡的函数依赖，平凡函数依赖都是必然成立的

• 说明：于任一关系模式，平凡函数依赖都是必然成立的，它不反映新
  的语义，因此若不特别声明，我们总是讨论非平凡函数依赖

完全函数依赖与部分函数依赖

• 定义：在关系模式 $R(U,F)$ 中，
  • 如果 $X \rightarrow Y$ ，并且对于 $X$ 的任何一个真子集 $\mathrm{X}^{\prime}$ ，都有 $\mathrm{X}^{\prime} \nrightarrow Y$ ，则称 $Y$ 完全函数依赖于 $X$，记作 $X \xrightarrow{F} Y$
  • 如果 $X \rightarrow Y$ ，但 $Y$ 不完全函数依赖于 $X$，则称 $Y$ 部分函数依赖于 $X$，记作 $X \xrightarrow{P} Y$

传递函数依赖

• 定义：在关系模式 $R(U,F)$ 中，如果 $X \rightarrow Y(Y \preceq X), Y \rightarrow X, Y \rightarrow Z (Z \preceq Y)$ ，则称 $Z$ 对 $X$ 传递函数依赖，记为 $X \xrightarrow{T} Z$
  • 如果 $Y \rightarrow X$ ，即 $X \leftrightarrow Y$ ，则 $X \xrightarrow{\text {直接}} Z$

码

• 候选码的定义：设 $K$ 为关系模式 $R<U,F>$ 中的属性或属性组合

  • 若 $K \xrightarrow{F} U$，则 $K$ 称为 $R$ 的一个候选码（Candidate Key）
  • 若关系模式 $R$ 有多个候选码，则选定其中的一个做为主码（Primary key）
  • 若 $K \xrightarrow{P} U$，则 $K$ 为 $R$ 的超码，候选码是最小的超码

• 码的属性：

  • 包含在任何一个候选码的诸属性称为主属性
  • 不包含在任何侯选码中的属性称为非主属性
  • 在最极端的情况下，关系模式的所有属性组是这个关系模式的候选码，称为全码（All-key）

• 外部码：关系模式 $R$ 中属性或属性组 $X$ 并非 $R$ 的码，但 $X$ 是另一个关系模式的码，则称 $X$ 是 $R$ 的外码（Foreign key）

  • 主码和外部码一起提供了表示关系间联系的手段

3. 关系规范化

• 范式的概念：范式是符合某一种级别的关系模式的集合

  • 关系数据库中的关系必须满足一定的要求，满足不同程度要求的为不同范式
  • 范式的种类：从低到高
    • 第一范式(1NF)
    • 第二范式(2NF)
    • 第三范式(3NF)
    • BC 范式(BCNF)
    • 第四范式(4NF)
    • 第五范式(5NF)
  • 范式之间的联系：

    $$1 N F \supset 2 N F \supset 3 N F \supset B C N F \supset 4 N F \supset 5 N F$$

  • 某一关系模式 $R$ 为第 $n$ 范式，可简记为 $R \in nNF$

• 规范化：

  • 规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题
  • 一个低一级范式的关系模式，通过模式分解(schema decomposition) 可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化(normalization)

• 1NF（第一范式）：

  • 定义：如果一个关系模式 $R$ 的所有属性都是不可分的基本数据项，则 $R \in 1NF$
  • 第一范式是对关系模式的最起码的要求，不满足第一范式的数据库模式不能称为关系数据库，但是满足第一范式的关系模式并不一定是一个好的关系模式
  • 问题：插入异常、删除异常、数据冗余度大、修改复杂，本质是存在部分函数依赖
  • 解决方法：分解为两个关系模式，以消除这些部分函数依赖

• 2NF (第二范式)：消除非主属性对码的部分函数依赖

  • 定义：若关系模式 $R \in 1NF$，并且每一个非主属性都完全函数依赖于 $R$ 的任何一个候选码，则 $R \in 2NF$
  • 采用投影分解法将一个 $1NF$ 的关系分解为多个 $2NF$ 的关系，可以在一定程度上减轻原 $1NF$ 关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题
  • 问题：存在非主属性对码的传递函数依赖，会出现插入、删除、修改、冗余问题
  • 解决方法：采用关系分解法，将具有传递函数依赖关系的属性（组）逐层提取出来

• 3NF (第三范式)：消除非主属性对码的传递函数依赖

  • 定义：关系模式 $R\langle U, F\rangle \in 1NF$，若不存在这样的码 $X$、属性组 $Y$及非主属性 $Z(Z \nsubseteq X, Z \nsubseteq Y)$ ，使得 $X \rightarrow Y, Y \nrightarrow X, Y \rightarrow Z$ 成立，则称 $R\langle U, F\rangle \in 3 N F$
  • 若 $R \in 3NF$，则 $R$ 的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码；如果$R \in 3NF$，则 $R$ 也是 $2NF$
  • 采用投影分解法将一个 $2NF$ 的关系分解为多个 $3NF$ 的关系，可以在一定程度上解决原 $2NF$ 关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题
  • 将一个 $2NF$ 关系分解为多个 $3NF$ 的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余

• BCNF (BC 范式, Boyce Codd Normal Form)：消除主属性对码的部分和传递函数依赖

  • 定义：设关系模式 $R\langle U, F\rangle \in 1 N F$，如果对于 $R$ 的每个函数依赖 $X \rightarrow Y$，若 $Y \nsubseteq X$，则 $X$ 必含有码，那么 $R \in B C N F$
  • 若 $R \in B C N F$：
    • 每一个决定属性集（因素）都包含（候选）码
    • $R$ 中的所有属性（主，非主属性）都完全函数依赖于码
    • 没有任何属性完全函数依赖于非码的任何一组属性
  • 若 $R \in B C N F$ ，则 $R \in 3 N F$ ；若 $R \in 3 N F$ ，则 $R$ 不一定 $\in B C N F$；如果 $R \in 3NF$，且 $R$ 只有一个候选码，则 $R$ 必属于 $BCNF$

• 关系模式规范化的基本步骤：

• 规范化的基本思想：
  • 消除不合适的数据依赖，各关系模式达到某种程度的“分离”
  • 采用“一事一地”的模式设计原则：让一个关系描述一个概念、一个实体或者实体间的一种联系；若多于一个概念就把它“分离”出去
  • 所谓规范化实质上是概念的单一化
  • 不能说规范化程度越高的关系模式就越好
    • 在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式
    • 上面的规范化步骤可以在其中任何一步终止

4. 数据依赖的公理系统

• 数据依赖的公理系统：

  • 数据依赖的公理系统是模式分解算法的理论基础
  • 函数依赖的一个有效而完备的公理系统——Armstrong公理系统，是一套推理规则，是模式分解算法的理论基础
  • 用途：
    • 求给定关系模式的码
    • 从一组函数依赖求得蕴含的函数依赖

• 逻辑蕴含的定义：对于满足一组函数依赖 $F$ 的关系模式 $R\langle U, F\rangle$，其任何一个关系 $r$，若函数依赖 $X \rightarrow Y$ 都成立，则称 $F$ 逻辑蕴含 $X \rightarrow Y$

• Armstrong 公理系统：关系模式 $R\langle U, F\rangle$ 来说有以下的推理规则：

  • A1. 自反律（Reflexivity Rule）：若 $Y \subseteq X \subseteq U$，则 $X \rightarrow Y$ 为 $F$ 所蕴含（平凡函数依赖）
  • A2. 增广律（Augmentation Rule）：若 $X \rightarrow Y$ 为 $F$ 所蕴含，且 $Z \subseteq U$，则 $X Z \rightarrow Y Z$ 为 $F$ 所蕴含
  • A3. 传递律（Transitivity Rule）：若 $X \rightarrow Y$ 及 $Y \rightarrow Z$ 为 $F$ 所蕴含，则 $X \rightarrow Z$ 为 $F$ 所蕴含

• 导出规则：根据 A1、A2、A3 这三条推理规则可以得到下面三条推理规则：

  • 合并规则（Union Rule）：由 $X \rightarrow Y$，$X \rightarrow Z$，有 $X \rightarrow Y Z$
  • 伪传递规则（Pseudo Transitivity Rule）：由 $X \rightarrow Y$，$W Y \rightarrow Z$，有 $X W \rightarrow Z$
  • 分解规则（Decomposition Rule）：由 $X \rightarrow Y$ 及 $Z \subseteq Y$，有 $X \rightarrow Z$

• 函数依赖闭包：

  • 闭包的定义：在关系模式 $R(U, F)$ 中为 $F$ 所逻辑蕴含的函数依赖的全体，叫作 $F$ 的闭包，记为 $F^+$
    • 若 $F^+ = F$，则说 $F$ 是一个全函数依赖族（函数依赖完备集）
  • 属性（集）闭包的定义：设 $F$ 为属性集 $U$ 上的一组函数依赖，$X$ 为 $U$ 的子集，$\mathrm{X} \subseteq \mathrm{U}$，$\mathrm{X}_{\mathrm{F}}{ }^{+} =\{\mathrm{A} \mid \mathrm{X} \rightarrow \mathrm{A}$ 能由 $F$ 根据 Armstrong 公理导出 $\}$，$\mathrm{X}_{\mathrm{F}}{ }^{+}$ 称为属性集 $X$ 关于函数依赖集 $F$ 的闭包，显然 $X \subseteq X_{F^+}$
  • 关于闭包的引理： $F$ 为属性组 $U$ 上的一组函数依赖，$X, Y \subseteq U$，$X \rightarrow Y$ 能由 $F$ 根据 Armstrong公理导出的充分必要条件是 $Y \subseteq X_F{ }^{+}$
    • 用途：将判定 $X \rightarrow Y$ 是否能由 $F$ 根据 Armstrong 公理导出的问题，就转化为求出 $X_F{ }^{+}$，判定 $Y$ 是否为 $X_F{ }^{+}$的子集的问题
  • 求闭包的算法：求属性集 $X(X \subseteq U)$ 关于 $U$ 上的函数依赖集 $F$ 的闭包 $X_F{ }^{+}$
    • 输入：$X, F$
    • 输出：$X_F{ }^{+}$
    • 步骤：
      • 令 $X^{(0)}=X, i=0$
      • 求 $B = \{A \mid(\exists V)(\exists W)(V \rightarrow W \in F \left.\left.\wedge V \subseteq X^{(\mathrm{i})} \wedge A \in W\right)\right\}$，即对 $X^{(i)}$ 中的每个元素，依次检查相应的函数依赖，将依赖它的属性加入B
      • $X^{(\mathrm{i}+1)}=B \cup X^{(\mathrm{i})}$
      • 判断 $X^{(i+1)}=X{ }^{(i)}$
      • 若 $X^{(i+1)}$ 与 $X{ }^{(i)}$ 相等或 $X^{(i)}=U$，则 $X^{(i)}$ 就是 $X_F{ }^{+}$，算法终止
      • 若否，则 $i=i+1$，返回第（2）步

• Armstrong 公理系统的有效性与完备性：

  • 有效性：由 $F$ 出发根据 Armstrong 公理推导出来的每一个函数依赖一定在 $F^{+}$中
  • 完备性：$F^{+}$ 中的每一个函数依赖，必定可以由 $F$ 出发根据 Armstrong 公理推导出来

• 函数依赖集等价：

  • 函数依赖集等价的定义：如果 $G^{+}=F^{+}$，就说函数依赖集 $F$ 覆盖 $G$，或者 $F$ 与 $G$ 等价
    • 两个函数依赖集等价是指它们的闭包等价
  • 引理：$F^{+}=G^{+}$的充分必要条件是 $F^{+} \subseteq G^{+}$ 和 $G^{+} \subseteq F^{+}$

• 最小依赖集：

  • 定义：如果函数依赖集 $F$ 满足下列条件，则称 $F$ 为一个极小函数依赖集，亦称为最小依赖集或最小覆盖
  • $F$ 中任一函数依赖的右部仅含有一个属性
  • $F$ 中不存在这样的函数依赖 $X \rightarrow A$，使得 $F$ 与 $F-\{X \rightarrow A\}$ 等价
  • $F$ 中不存在这样的函数依赖 $X \rightarrow A$，$X$ 有真子集 $Z$ 使得 $F-\{X \rightarrow A\} \cup\{Z \rightarrow A\}$与 $F$ 等价

• 关系模式分解的标准：

  • 无损连接性：进行关系分解后得到的关系按照外码自然连接能够得到原来的关系
  • 函数依赖性：关系分解后每个关系的最小函数依赖集是原关系的最小函数依赖集的子集，并且所有子集的并等于原关系的最小函数依赖集

• 三种模式分解的等价定义：

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

第四章 结构查询语言 SQL

1. SQL 概述

• SQL（Structured Query Language）：

  • 结构化查询语言，是关系数据库的标准语言
  • 是一个通用的、功能极强的关系数据库语言
  • SQL 语言的功能包括查询、操纵、定义和控制，是一个综合的、通用的关系数据库语言，也是一种高度非过程化语言，只要求用户指出做什么而不需要指出怎么做
  • SQL 集成实现了数据库生命周期的全部操作

• SQL 语言的特点：

  • 综合统一：集数据定义语言 (DDL)、数据操纵语言 (DML)、数据控制语言 (DCL) 功能于一体
    • 可以独立完成数据库生命周期中的全部活动
      • 定义关系模式，插入数据，建立数据库；
      • 对数据库中的数据进行查询和更新；
      • 数据库重构和维护；
      • 数据库安全性、完整性控制等；
    • 用户数据库投入运行后，可根据需要随时逐步修改模式，不影响数据的运行
    • 数据操作符统一
  • 高度非过程化：
    • 非关系数据模型的数据操纵语言“面向过程”，必须制定存取路径
    • SQL 只要提出＂做什么＂，无须了解存取路径
    • 存取路径的选择以及 SQL 的操作过程由系统自动完成
  • 面向集合的操作方式：
    • 非关系数据模型采用面向记录的操作方式，操作对象是一条记录
    • SQL 采用集合操作方式：
      • 操作对象、查找结果可以是元组的集合
      • 一次插入、删除、更新操作的对象可以是元组的集合
  • 以同一种语法结构提供两种使用方法：
    • SQL 是独立的语言：能够独立地用于联机交互的使用方式
    • SQL 又是嵌入式语言：能够嵌入到高级语言（例如 C，C++，Java）程序中，供程序员设计程序时使用
  • 语言简洁，易学易用：

    SQL 功 能	动 词
    数 据 定 义	CREATE，DROP，ALTER
    数 据 查 询	SELECT
    数 据 操 纵	INSERT，UPDATE，DELETE
    数 据 控 制	GRANT，REVOKE

• SQL 的基本概念：

  • 基本表：
    • 本身独立存在的表
    • SQL 中一个关系就对应一个基本表
    • 一个（或多个）基本表对应一个存储文件
    • 一个表可以带若干索引
  • 存储文件：
    • 逻辑结构组成了关系数据库的内模式
    • 物理结构是任意的，对用户透明
  • 视图：
    • 从一个或几个基本表导出的表
    • 数据库中只存放视图的定义而不存放视图对应的数据
    • 视图是一个虚表
    • 用户可以在视图上再定义视图

2. 数据定义

• SQL 的数据定义功能：模式定义、表定义、视图定义和索引定义

2.1 模式的定义与删除

• 定义数据库模式：

  • 基本语法：CREATE SCHEMA <模式名> AUTHORIZATION <用户名>

    CREATE SCHEMA “S-T” AUTHORIZATION WANG;

  • 如果没有指定<模式名>，那么<模式名>隐含为<用户名>

    CREATE SCHEMA AUTHORIZATION WANG;

  • 定义模式实际上定义了一个命名空间，在这个空间中可以定义该模式包含的数据库对象，例如基本表、视图、索引等
  • 在 CREATE SCHEMA 中可以接受 CREATE TABLE，CREATE VIEW 和 GRANT 子句，即 CREATE SCHEMA <模式名> AUTHORIZATION <用户名>[<表定义子句>|<视图定义子句>|<授权定义子句>]

    CREATE SCHEMA TEST AUTHORIZATION ZHANG
    CREATE TABLE TAB1(COL1 SMALLINT,
                      COL2 INT,
                      COL3 CHAR(20),
                      COL4 NUMERIC(10，3),
                      COL5 DECIMAL(5，2)
                      );

• 删除数据库模式：

  • 基本语法：DROP SCHEMA <模式名><CASCADE|RESTRICT>
    • CASCADE(级联)：删除模式的同时把该模式中所有的数据库对象全部删除
    • RESTRICT(限制)：如果该模式中定义了下属的数据库对象（如表、视图等），则拒绝该删除语句的执行，没有任何下属的对象时才能执行

    DROP SCHEMA ZHANG CASCADE;

2.2 基本表的定义、删除与修改

• 定义基本表：

  • 基本语法：

    CREATE TABLE <表名>
            (<列名> <数据类型>[<列级完整性约束条件>]
            [, <列名> <数据类型>[<列级完整性约束条件>]] 
            ...
            [, <表级完整性约束条件>]);

    • <表名>：所要定义的基本表的名字
    • <列名>：组成该表的各个属性（列）
    • <列级完整性约束条件>：涉及相应属性列的完整性约束条件
    • <表级完整性约束条件>：涉及一个或多个属性列的完整性约束条件

    CREATE TABLE Student
    (Sno CHAR(9) PRIMARY KEY, /* 列级完整性约束条件，主码*/ 
    Sname CHAR(20) UNIQUE, /* Sname取唯一值*/ 
    Ssex CHAR(2),
    Sage SMALLINT,
    Sdept CHAR(20)
    );
    
    CREATE TABLE Course
    (Cno CHAR(4) PRIMARY KEY, /* 列级完整性约束条件，主码*/ 
    Cname CHAR(40) NOT NULL, /* Cname不能取空值*/ 
    Cpno CHAR(4),
    Ccredit SMALLINT,
    FOREIGN KEY (Cpno) REFERENCES Course(Cno)
    );
    
    CREATE TABLE SC
    (Sno CHAR(9),
    Cno CHAR(4),
    Grade SMALLINT CHECK (Grade>=0 and Grade<=100),
    PRIMARY KEY (Sno，Cno),
    /* 主码由两个属性构成，必须作为表级完整性进行定义*/ 
    FOREIGN KEY (Sno) REFERENCES Student(Sno),
    /* 表级完整性约束条件，Sno是外码，被参照表是Student */ 
    FOREIGN KEY (Cno) REFERENCES Course(Cno)
    /* 表级完整性约束条件，Cno是外码，被参照表是Course*/
    );

• 数据类型：

  • SQL 中域的概念用数据类型来实现
  • 定义表的属性时需要指明其数据类型及长度
  • 选用哪种数据类型：取值范围、要做哪些运算

• 模式与表：

  • 每一个基本表都属于某一个模式，一个模式包含多个基本表
  • 定义基本表所属模式：
    • 方法一：在表名中明显地给出模式名：

      Create TABLE “S-T”.Student（......）; /*模式名为S-T*/

    • 方法二：在创建模式语句中同时创建表
    • 方法三：设置所属的模式
  • 创建基本表（其他数据库对象也一样）时，若没有指定模式，系统根据搜索路径来确定该对象所属的模式；RDBMS 会使用模式列表中第一个存在的模式作为数据库对象的模式名
  • DBA 用户可以设置搜索路径，然后定义基本表

• 修改基本表：

  • 基本语法：

    ALTER TABLE <表名>
    [ ADD [ COLUMN ] <新列名> <数据类型> [完整性约束] ]
    [ ADD <表级完整性约束>]
    [ DROP [ COLUMN ] <列名> [CASCADE|RESTRICT] ]
    [ DROP CONSTRAINT <完整性约束名> [CASCADE|RESTRICT] ]
    [ ALTER COLUMN <列名> <数据类型> ];

    • <表名>：要修改的基本表
    • ADD 子句：增加新列、新的列完整性约束条件、新的表完整性约束条件
    • DROP CONSTRAINT 子句：删除指定的完整性约束条件
    • ALTER COLUMN 子句：用于修改列名和数据类型

    ALTER TABLE Student ADD S_entrance DATE;
    
    ALTER TABLE Student ALTER COLUMN Sage INT;
    
    ALTER TABLE Course ADD UNIQUE(Cname);

• 删除基本表：

  • 基本语法：DROP TABLE <表名> [RESTRICT|CASCADE];
    • RESTRICT：删除表是有限制的（默认）
      • 欲删除的基本表不能被其它表的约束所引用
      • 如果存在依赖该表的对象，则此表不能被删除
    • CASCADE：删除该表没有限制
      • 在删除基本表的同时，相关的依赖对象一起删除

    DROP TABLE Student CASCADE;

2.3 索引的建立与删除

• 建立与删除索引：

  • 建立索引是加快查询速度的有效手段（内模式的范畴）
    • 顺序文件上的索引、B+树索引、hash索引、位图索引，等等
  • 建立索引：
    • DBA 或表的属主（即建立表的人）根据需要建立
    • 有些 DBMS 自动建立以下列上的索引：PRIMARY KEY、UNIQUE
  • 使用索引：DBMS 自动选择是否使用索引以及使用哪些索引

• 建立索引：

  • 基本语法：

    CREATE [UNIQUE] [CLUSTER] INDEX <索引名> 
    ON <表名>(<列名>[<次序>][,<列名>[<次序>] ]...);

    • 用<表名>指定要建索引的基本表名字
    • 索引可以建立在该表的一列或多列上，各列名之间用逗号分隔
    • 用<次序>指定索引值的排列次序，升序：ASC，降序：DESC（缺省值：ASC）
    • UNIQUE 表明此索引的每一个索引值只对应唯一的数据记录
    • CLUSTER 表示要建立的索引是聚簇索引
  • 聚簇索引：建立聚簇索引后，基表中数据也需要按指定的聚簇属性值的升序或降序存放，也即聚簇索引的索引项顺序与表中记录的物理顺序一致

    CREATE CLUSTER INDEX Stusname ON Student(Sname);

    • 在最经常查询的列上建立聚簇索引以提高查询效率
    • 一个基本表上最多只能建立一个聚簇索引
    • 经常更新的列不宜建立聚簇索引
  • 唯一值索引：
    • 对于已含重复值的属性列不能建 UNIQUE 索引
    • 对某个列建立 UNIQUE 索引后，插入新记录时 DBMS 会自动检查新记录在该列上是否取了重复值（这相当于增加了一个 UNIQUE 约束）

    CREATE UNIQUE INDEX Stusno ON Student(Sno);
    CREATE UNIQUE INDEX Coucno ON Course(Cno);
    CREATE UNIQUE INDEX SCno ON SC(Sno ASC，Cno DESC);

• 修改索引:

  • 基本语法：ALTER INDEX <旧索引名> RENAME TO <新索引名>;

    ALTER INDEX Scno RENAME TO SCSno;

• 删除索引：

  • 基本语法：DROP INDEX <索引名>;

    DROP INDEX Stusname;

  • 删除索引时，系统会从数据字典中删去有关该索引的描述

3. 数据查询

• 基本语法：

  SELECT [ALL|DISTINCT] <目标列表达式>[,<目标列表达式>] ...
  FROM <表名或视图名>[,<表名或视图名>...]|(<SELECT语句>)[AS] <别名>
  [WHERE <条件表达式>]
  [GROUP BY <列名1> [HAVING <条件表达式>]]
  [ORDER BY <列名2> [ASC|DESC]];

3.1 单表查询

• 选择表中的若干列：

  • 查询指定列：
    • 例：查询全体学生的学号与姓名

      SELECT Sno, Sname
      FROM Student;

    • 例：查询全体学生的姓名、学号、所在系

      SELECT Sname, Sno, Sdept
      FROM Student;

  • 查询全部列：
    • 例：查询全体学生的详细记录

      SELECT *
      FROM Student;

  • 查询经过计算的值：SELECT 子句的<目标列表达式>为表达式（算术表达式、字符串常量、函数、列别名）
    • 例：查全体学生的姓名及其出生年份

      SELECT Sname, 2014-Sage
      FROM Student;

    • 例：查询全体学生的姓名、出生年份和所有系，要求用小写字母表示所有系名

      SELECT Sname, 'Year of Birth: ', 2014-Sage LOWER(Sdept) 
      FROM Student;

    • 例：使用列别名改变查询结果的列标题

      SELECT Sname NAME, 'Year of Birth: ' BIRTH, 2014-Sage BIRTHDAY, ISLOWER(Sdept) DEPARTMENT 
      FROM Student;

• 选择表中的若干元组：

  • 消除取值重复的行：在 SELECT 子句中使用 DISTINCT 短语，缺省为 ALL

    • 例：查询选修了课程的学生学号

      SELECT DISTINCT Sno
      FROM SC;

  • 查询满足条件的元组：

    

    • 比较大小：

      • 例：查询计算机科学系全体学生的名单

        SELECT Sname
        FROM Student
        WHERE Sdept=‘CS’;

      • 例：查询所有年龄在 20 岁以下的学生姓名及其年龄

        SELECT Sname，Sage
        FROM Student
        WHERE Sage < 20;

      • 例：查询考试成绩有不及格的学生的学号

        SELECT DISTINCT Sno
        FROM SC
        WHERE Grade<60;

    • 确定范围：使用谓词 BETWEEN ... AND ...

      • 例：查询年龄在 20-23 岁（包括 20 岁和 23 岁）之间的学生的姓名、系别和年龄

        SELECT Sname，Sdept，Sage
        FROM Student
        WHERE Sage BETWEEN 20 AND 23;

      • 例：查询年龄不在 20-23 岁之间的学生姓名、系别和年龄

        SELECT Sname，Sdept，Sage
        FROM Student
        WHERE Sage NOT BETWEEN 20 AND 23;

    • 确定集合：使用谓词 IN <值表>

      • 例：查询信息系（IS）、数学系（MA）和计算机科学系（CS）学生的姓名和性别

        SELECT Sname，Ssex
        FROM Student
        WHERE Sdept IN ('IS', 'MA', 'CS');

      • 例：查询既不是信息系、数学系，也不是计算机科学系的学生的姓名和性别

        SELECT Sname，Ssex
        FROM Student WHERE Sdept NOT IN ('IS', 'MA', 'CS');

    • 字符串匹配：

      • 语法：[NOT] LIKE ‘<匹配串>’ [ESCAPE ‘ <换码字符>’]
        • 查找指定的属性值与 <匹配串> 相匹配的元组
        • 匹配串：固定字符串或含通配符的字符串
        • 当匹配模板为固定字符串时，用 = 运算符取代 LIKE 谓词；用 != 或 <> 运算符取代 NOT LIKE 谓词
      • 匹配串为固定字符串：
        • 例：查询学号为 201215121 的学生的详细情况

          SELECT *
          FROM Student
          WHERE Sno LIKE ‘201215121’;

          SELECT *
          FROM Student
          WHERE Sno = ‘201215121’;

      • 通配符：
        • % (百分号)：代表任意长度（长度可以为0）的字符串
          • 例：a%b 表示以 a 开头，以 b 结尾的任意长度的字符串；如 acb，addgb，ab 等都满足该匹配串
        • _ (下横线)：代表任意单个字符
          • 例：a_b 表示以 a 开头，以 b 结尾的长度为 3 的任意字符串；如 acb，afb 等都满足该匹配串
      • 匹配串为含通配符的字符串：
        • 例：查询所有姓刘学生的姓名、学号和性别

          SELECT Sname, Sno, Ssex
          FROM Student
          WHERE Sname LIKE ‘刘%’; /*%表示任意长度*/

        • 例：查询姓"欧阳"且全名为三个汉字的学生的姓名

          SELECT Sname
          FROM Student
          WHERE Sname LIKE ‘欧阳_ _’; /*__代表任意单个字符*/

        • 例：查询名字中第2个字为"阳"字的学生的姓名和学号

          SELECT Sname, Sno
          FROM Student
          WHERE Sname LIKE ‘_ _阳%’;

        • 例：查询所有不姓刘的学生姓名

          SELECT Sname，Sno，Ssex
          FROM Student
          WHERE Sname NOT LIKE '刘%';

      • 使用换码字符将通配符转义为普通字符：
        • 例：查询 DB_Design 课程的课程号和学分

          SELECT Cno, Ccredit
          FROM Course
          WHERE Cname LIKE 'DB\_Design' ESCAPE '\';

        • 例：查询以 “DB_” 开头，且倒数第 3 个字符为 i 的课程情况

          SELECT *
          FROM Course
          WHERE Cname LIKE 'DB\_%i_ _' ESCAPE '\';

    • 涉及空值的查询：使用谓词 IS NULL 或 IS NOT NULL；“IS NULL” 不能用 “= NULL” 代替

      • 例：某些学生选修课程后没有参加考试，所以有选课记录，但没有考试成绩查询缺少成绩的学生学号和相应课程号

        SELECT Sno，Cno
        FROM SC
        WHERE Grade IS NULL;

      • 例：查所有有成绩的学生学号和课程号

        SELECT Sno，Cno
        FROM SC
        WHERE Grade IS NOT NULL;

    • 多重条件查询：用逻辑运算符 AND 和 OR 来联结多个查询条件，AND 的优先级高于 OR，可以用括号改变优先级

      • 例：查询计算机系年龄在 20 岁以下的学生姓名

        SELECT Sname
        FROM Student
        WHERE Sdept= 'CS' AND Sage<20;

      • 例：查询信息系（IS）、数学系（MA）和计算机科学系（CS）学生的姓名和性别

        SELECT Sname，Ssex
        FROM Student
        WHERE Sdept= 'IS' OR Sdept= 'MA' OR Sdept= 'CS';

• 对查询结果排序：

  • 语法：使用 ORDER BY子句
    • 可以按一个或多个属性列排序
    • 升序：ASC；降序：DESC；缺省值为升序
    • 当排序列含空值时
      • ASC：排序列为空值的元组最后显示
      • DESC：排序列为空值的元组最先显示
  • 例：查询选修了 3 号课程的学生的学号及其成绩，查询结果按分数降序排列

    SELECT Sno, Grade
    FROM SC
    WHERE Cno= '3'
    ORDER BY Grade DESC;

  • 例：查询全体学生情况，查询结果按所在系的系号升序排列，同一系中的学生按年龄降序排列

    SELECT *
    FROM Student
    ORDER BY Sdept，Sage DESC;

• 使用聚集函数：

  • 5 类主要聚集函数：
    • 计数：
      • COUNT ([DISTINCT|ALL] *) （统计元组个数）
      • COUNT ([DISTINCT|ALL] <列名>) （统计一列中值的个数）
    • 计算一列值的总和：
      • SUM ([DISTINCT|ALL] <列名>)
    • 计算一列值的平均值：
      • AVG ([DISTINCT|ALL] <列名>)
    • 求一列值中的最大最小值：
      • MAX ([DISTINCT|ALL] <列名>)
      • MIN ([DISTINCT|ALL] <列名>)
  • 例：查询学生总人数

    SELECT COUNT(*)
    FROM Student;

  • 例：查询选修了课程的学生人数

    SELECT COUNT(DISTINCT Sno)
    FROM SC;

  • 例：计算 1 号课程的学生平均成绩

    SELECT AVG(Grade)
    FROM SC
    WHERE Cno= '1';

  • 例：查询选修 1 号课程的学生最高分数

    SELECT MAX(Grade)
    FROM SC
    WHERE Cno= ‘1’;

  • 例：查询学生 201215012 选修课程的总学分数

    SELECT SUM(Ccredit)
    FROM SC, Course
    WHERE Sno='201215012' AND SC.Cno=Course.Cno;

  • 注意：WHERE 子句中不能用聚集函数作为条件表达式

• 对查询结果分组：使用 GROUP BY 子句分组，按某一列或多列的值分组，值相等的为一组

  • 细化聚集函数的作用对象:
    • 未对查询结果分组，聚集函数将作用于整个查询结果
    • 对查询结果分组后，聚集函数将分别作用于每个组
  • 使用 GROUP BY 子句分组：
    • 例：求各个课程号及相应的选课人数

      SELECT Cno, COUNT(Sno)
      FROM SC
      GROUP BY Cno;

  • 使用 HAVING 短语筛选最终输出结果：
    • 例：查询选修了 3 门以上课程的学生学号

      SELECT Sno
      FROM SC
      GROUP BY Sno
      HAVING COUNT(*) >3;

    • 例：查询平均成绩大于等于 90 分的学生学号和平均成绩

      SELECT Sno, AVG(Grade)
      FROM SC
      GROUP BY Sno
      HAVING AVG(Grade)>=90;

  • 注意：
    • 聚集函数只能用于 SELECT 子句和 GROUP BY 中的 HAVING 子句
    • WHERE 子句作用于基本表或视图，选择满足条件的元组
    • HAVING 短语作用于组，从分好的组中选择满足条件的组

3.2 连接查询

• 连接查询：同时涉及多个表的查询

  • 用来连接两个表的条件称为连接条件或连接谓词
    • 连接谓词中的列名称为连接字段
    • 连接条件中的各连接字段类型必须是可比的，但不必相同！
  • 一般格式：
    • [<表名1>.]<列名1> <比较运算符> [<表名2>.]<列名2>，其中比较运算符：=、>、<、>=、<=、!=（或<>）等
    • [<表名1>.]<列名1> BETWEEN [<表名2>.]<列名2> AND [<表名2>.]<列名3>
  • SQL 中连接查询的主要类型：
    • 等值连接（含自然连接）
    • 非等值连接查询
    • 自身连接查询
    • 外连接查询
    • 复合条件连接查询

• 等值与非等值连接查询：

  • 等值连接：连接运算符为 =
    • 例：查询每个学生及其选修课程的情况

      SELECT Student.*, SC.*
      FROM Student，SC
      WHERE Student.Sno = SC.Sno;

• 连接操作的执行过程：

  • 嵌套循环连接算法(NESTED-LOOP)：
    • 首先在表1中找到第一个元组，然后从头开始扫描表2，逐一查找满足连接件的元组，找到后就将表1中的第一个元组与该元组拼接起来，形成结果表中一个元组
    • 表2全部查找完后，再找表1中第二个元组，然后再从头开始扫描表2，逐一查找满足连接条件的元组，找到后就将表1中的第二个元组与该元组拼接起来，形成结果表中一个元组
    • 重复上述操作，直到表1中的全部元组都处理完毕
  • 索引连接(INDEX-JOIN)：
    • 对表2按连接字段 Sno 建立索引
    • 对表1中的每个元组，依次根据其连接字段值查询表2的索引，从中找到满足条件的元组，找到后就将表1中的第一个元组与该元组拼接起来，形成结果表中一个元组

• 自然连接：等值连接的一种特殊情况，把目标列中重复的属性列去掉

  • 例：查询每个学生及其选修课程的情况

    SELECT Student.Sno, Sname, Ssex, Sage, Sdept, Cno, Grade
    FROM Student，SC
    WHERE Student.Sno = SC.Sno；

• 自身连接：一个表与其自己进行连接

  • 需要给表起别名以示区别；由于所有属性名都是同名属性，因此必须使用别名前缀
  • 例：查询每一门课的间接先修课（即先修课的先修课）

    SELECT FIRST.Cno, SECOND.Cpno
    FROM Course FIRST，Course SECOND
    WHERE FIRST.Cpno = SECOND.Cno;

• 外连接（Outer Join）：

  • 外连接与普通连接的区别：
    • 普通连接操作只输出满足连接条件的元组；
    • 外连接操作以指定表为连接主体，将主体表中不满足连接条件的悬浮元组一并输出；
  • 例：查询每个学生及其选修课程的情况，包括没有选修课程的学生

    SELECT Student.Sno, Sname, Ssex, Sage, Sdept, Cno, Grade
    FROM Student LEFT OUTER JOIN SC ON
    (Student.Sno = SC.Sno);

  • 左外连接：列出左边关系中所有元组
  • 右外连接：列出右边关系中所有元组

• 复合条件连接：WHERE 子句中含多个连接条件

  • 例：查询选修 2 号课程且成绩在 90 分以上的所有学生的学号和姓名

    SELECT Student.Sno, Student.Sname
    FROM Student, SC
    WHERE Student.Sno = SC.Sno AND /* 连接谓词 */
    SC.Cno= ' 2 ' AND /* 其他限定条件 */
    SC.Grade > 90;  /* 其他限定条件 */

  • 例：查询每个学生的学号、姓名、选修的课程名及成绩

    SELECT Student.Sno, Sname, Cname, Grade
    FROM Student, SC, Course
    WHERE Student.Sno = SC.Sno 
    AND SC.Cno = Course.Cno;

3.3 嵌套查询

• 嵌套查询：将一个查询块嵌套在另一个查询块的 WHERE 子句或 HAVING 短语的条件中的查询（一个 SELECT-FROM-WHERE 语句称为一个查询块）

  • 允许多层嵌套，但子查询有限制，即 SELECT 语句中不能使用 ORDER BY 子句，因为 ORDER BY 子句只能对最终查询结果排序
  • 层层嵌套方式反映了 SQL 语言的结构化
  • 有些嵌套查询可以用连接运算替代

• 嵌套查询分类：

  • 不相关子查询：子查询的查询条件不依赖于父查询
    • 处理过程：由里向外逐层处理，即每个子查询在上一级查询处理之前求解，子查询的结果用于建立其父查询的查找条件
  • 相关子查询：子查询的查询条件依赖于父查询
    • 处理过程：
      • 首先取外层查询中表的第一个元组，根据它与内层查询相关的属性值处理内层查询，若 WHERE 子句返回值为真，则取此元组放入结果表
      • 然后再取外层表的下一个元组
      • 重复这一过程，直至外层表全部检查完为止

• 带有 IN 谓词的子查询：

  • 例：查询与“刘晨”在同一个系学习的学生

    SELECT Sno, Sname, Sdept
    FROM Student
    WHERE Sdept IN
      (SELECT Sdept
      FROM Student
      WHERE Sname= ‘刘晨’);

  • 例：查询选修了课程名为“信息系统”的学生学号和姓名

    SELECT Sno, Sname FROM Student 
    WHERE Sno IN
      (SELECT Sno FROM SC 
      WHERE Cno IN
        (SELECT Cno FROM Course 
        WHERE Cname= ‘信息系统’));

• 带有比较运算符的子查询：当能确切知道内层查询返回单值时，可用比较运算符（>，<，=，>=，<=，!=或< >）；与 ANY 或 ALL 谓词配合使用

  • 注意：子查询一定要跟在比较符之后
  • 例：查询与“刘晨”在同一个系学习的学生

    SELECT Sno, Sname, Sdept
    FROM Student
    WHERE Sdept =
      (SELECT Sdept
      FROM Student
      WHERE Sname= ‘刘晨’);

  • 例：找出每个学生超过他选修课程平均成绩的课程号

    SELECT Sno, Cno
    FROM SC x
    WHERE Grade >= (SELECT AVG(Grade)
                    FROM SC y
                    WHERE y.Sno=x.Sno);

• 带有 ANY 或 ALL 谓词的子查询：

  • 谓词语义：
    • ANY：某一个值
    • ALL：所有值
  • ANY 和 ALL 谓词有时可以用聚集函数实现
  • 例：查询其他系中比计算机系某一个 (任意一个)学生年龄小的学生姓名和年龄

    SELECT Sname, Sage
    FROM Student
    WHERE Sage < ANY (SELECT Sage
                      FROM Student
                      WHERE Sdept= ' CS ')
          AND Sdept <> ' CS ';

    SELECT Sname, Sage
    FROM Student
    WHERE Sage < (SELECT MAX(Sage)
                  FROM Student
                  WHERE Sdept= ' CS ')
          AND Sdept <> ' CS ';

  • 例：查询其他系中比计算机系所有学生年龄都小的学生姓名及年龄

    SELECT Sname, Sage
    FROM Student
    WHERE Sage < ALL (SELECT Sage
                      FROM Student
                      WHERE Sdept= ' CS ')
          AND Sdept <> ' CS ';

    SELECT Sname, Sage
    FROM Student
    WHERE Sage < (SELECT MIN(Sage)
                  FROM Student
                  WHERE Sdept= ' CS ')
          AND Sdept <> ' CS ';

• 带有 EXISTS 谓词的子查询：

  • EXISTS 谓词：存在量词 $\exists$

    • 带有 EXISTS 谓词的子查询不返回任何数据，只产生逻辑真值“true”或逻辑假值“false”
      • 若内层查询结果非空，则返回真值
      • 若内层查询结果为空，则返回假值
    • 由 EXISTS 引出的子查询，其目标列表达式通常都用 *，因为带 EXISTS 的子查询只返回真值或假值，给出列名无实际意义
    • 例：查询所有选修了 1 号课程的学生姓名

      SELECT Sname
      FROM Student
      WHERE EXISTS
            (SELECT *
            FROM SC 
            WHERE Sno=Student.Sno 
            AND Cno= '1');

      SELECT Sname
      FROM Student, SC
      WHERE Student.Sno=SC.Sno AND 
            SC.Cno= '1';

  • NOT EXISTS 谓词

    • 例：查询没有选修 1 号课程的学生姓名

      SELECT Sname
      FROM Student
      WHERE NOT EXISTS
              (SELECT *
              FROM SC
              WHERE Sno = Student.Sno 
              AND Cno= '1');

  • 不同形式的查询间的替换：

    • 一些带 EXISTS 或 NOT EXISTS 谓词的子查询不能被其他形式的子查询等价替换
    • 所有带 IN 谓词、比较运算符、ANY 和 ALL 谓词的子查询都能用带 EXISTS 谓词的子查询等价替换
    • 例：查询与“刘晨”在同一个系学习的学生，可以用带 EXISTS 谓词的子查询替换

      SELECT Sno，Sname，Sdept
      FROM Student S1
      WHERE EXISTS
          　(SELECT *
              FROM Student S2
              WHERE S2.Sdept = S1.Sdept AND
              S2.Sname = '刘晨');

  • 用 EXISTS/NOT EXISTS 实现全称量词：

    • SQL语言中没有全称量词 $\forall$
    • 可以把带有全称量词的谓词转换为等价的带有存在量词的谓词

      $$(\forall \mathrm{x}) \mathrm{P} \equiv \neg(\exists \mathrm{x}(\neg \mathrm{P}))$$

    • 例：查询选修了全部课程的学生姓名

      SELECT Sname
      FROM Student
      WHERE NOT EXISTS
          (SELECT *
          FROM Course
          WHERE NOT EXISTS
                (SELECT *
                FROM SC
                WHERE Sno= Student.Sno
                AND Cno= Course.Cno));

  • 用 EXISTS/NOT EXISTS 实现逻辑蕴函：

    • SQL 语言中没有蕴函逻辑运算
    • 可以利用谓词演算将逻辑蕴函谓词等价转换为

      $$\mathrm{p} \rightarrow \mathrm{q} \equiv \neg \mathrm{p} \vee \mathrm{q}$$

    • 例：查询至少选修了学生 201215122 选修的全部课程的学生号码

      SELECT DISTINCT Sno
      FROM SC SCX
      WHERE NOT EXISTS
          (SELECT *
          FROM SC SCY
          WHERE SCY.Sno = '201215122' AND
          NOT EXISTS
              (SELECT *
              FROM SC SCZ
              WHERE SCZ.Sno=SCX.Sno AND
              SCZ.Cno=SCY.Cno));

3.4 集合查询

• 集合查询：

  • 集合操作种类：
    • 并操作(UNION)
    • 交操作(INTERSECT)
    • 差操作(EXCEPT)
  • 参加集合操作的各查询结果的列数必须相同；对应项的数据类型也必须相同

• 并操作：

  • UNION：将多个查询结果合并起来时，系统自动去掉重复元组
  • UNION ALL：将多个查询结果合并起来时，保留重复元组
  • 例：查询计算机科学系的学生或年龄不大于 19 岁的学生

    SELECT *
    FROM Student
    WHERE Sdept= 'CS'
    UNION
    SELECT *
    FROM Student
    WHERE Sage<=19;

    SELECT DISTINCT *
    FROM Student
    WHERE Sdept= 'CS' OR Sage<=19;

• 交操作：

  • 例：查询选修课程 1 的学生集合与选修课程 2 的学生集合的交集

    SELECT Sno
    FROM SC
    WHERE Cno='1'
    INTERSECT
    SELECT Sno
    FROM SC
    WHERE Cno='2';

    SELECT Sno
    FROM SC
    WHERE Cno='1' AND Sno IN
                      (SELECT Sno
                      FROM SC
                      WHERE Cno='2');

• 差操作：

  • 例：查询计算机科学系的学生与年龄不大于 19 岁的学生的差集

    SELECT *
    FROM Student
    WHERE Sdept='CS'
    EXCEPT
    SELECT *
    FROM Student
    WHERE Sage <=19;

    SELECT *
    FROM Student
    WHERE Sdept= 'CS' AND Sage>19;

3.5 派生查询

• 派生查询：

  • 子查询不仅可以出现在 WHERE 子句中，还可以出现在 FROM 子句中
  • 子查询生成的临时派生表（derived table）成为主查询的查询对象

• 基于派生表的查询：

  • 例：找出每个学生超过自己选修课程平均成绩的课程号

    SELECT Sno, Cno
    FROM SC, (SELECT Sno, Avg(Grade) FROM SC GROUP BY Sno)
              AS Avg_sc (avg_sno, avg_grade)
    WHERE SC.Sno=Avg_sc.avg_sno and SC.Grade>=Avg_sc.avg_grade

  • 例：查询所有选修了 1 号课程的学生姓名

    SELECT Sname
    FROM Student, (SELECT Sno FROM SC WHERE Cno='1')
                  AS SC1 
    WHERE Student.Sno = SC1.Sno

  • 如果子查询没有聚集函数，派生表可以不指定属性列，子查询 SELECT 子句后面的列名为其默认属性

4. 数据更新

• 插入数据：

  • 插入单个元组：

    • 基本语法：

      INSERT
      INTO <表名> [(<属性列1>[, <属性列2>...)]
      VALUES (<常量1>[, <常量2>] ...)

    • 功能：将新元组插入指定表中
    • 例：将一个新学生记录（学号：201215128；姓名：陈冬；性别：男；所在系：IS；年龄：18岁）插入到 Student 表中

      INSERT
      INTO Student (Sno, Sname, Ssex, Sdept, Sage)
      VALUES ('201215128', '陈冬', '男', 'IS', 18);

    • 如果不指定任何属性列，则新插入的元组必须在每个属性列上均有值
    • 属性列的顺序可与表定义中的顺序不一致
    • 如果仅指定部分属性列，则新元组在没有出现的属性列上取空值
    • VALUES 子句提供的值必须与 INTO 子句匹配（值的个数、值的类型）

  • 插入子查询结果：可以一次插入多个元组

    • 基本语法：

      INSERT 
      INTO <表名> [(<属性列1> [，<属性列2>… )]
      子查询;

    • 功能：将子查询结果插入指定表中
    • 例：对每一个系，求学生的平均年龄，并把结果存入数据库

      /* 第一步：建表 */
      CREATE TABLE Deptage
            (Sdept CHAR(15)
            Avgage SMALLINT);
      
      /* 第二步：建表 */
      INSERT
        INTO Deptage(Sdept，Avgage)
        SELECT Sdept, AVG(Sage)
        FROM Student
        GROUP BY Sdept;

    • INTO 子句：
      • 指定要插入数据的表名及属性列
      • 属性列的顺序可与表定义中的顺序不一致
      • 没有指定属性列：表示要插入的是一条完整的元组
      • 指定部分属性列：插入的元组在其余属性列上取空值
    • 子查询：
      • SELECT 子句目标列必须与 INTO 子句匹配（值的个数、值的类型）
    • DBMS 在执行插入语句时会检查所插元组是否破坏表上已定义的完整性规则
      • 实体完整性
      • 参照完整性
      • 用户定义的完整性
        • 对于有 NOT NULL 约束的属性列是否提供了非空值
        • 对于有 UNIQUE 约束的属性列是否提供了非重复值
        • 对于有值域约束的属性列所提供的属性值是否在值域范围内

• 修改数据：

  • 基本语法：

    UPDATE <表名>
    SET <列名>=<表达式>[, <列名>=<表达式>]...
    [WHERE <条件>];

  • 功能：修改指定表中满足 WHERE 子句条件的元组
  • SET 子句：指定修改方式、要修改的列、修改后取值
  • WHERE 子句：指定要修改的元组，缺省表示要修改表中的所有元组
  • 修改元组的值：
    • 例：将学生 201215121 的年龄改为 22 岁

      UPDATE Student
      SET Sage=22
      WHERE Sno= '201215121';

    • 例：将所有学生的年龄增加 1 岁

      UPDATE Student
      SET Sage= Sage+1;

  • 带子查询的修改语句：
    • 例：将计算机科学系全体学生的成绩置零

      UPDATE SC
      SET Grade=0
      WHERE sno IN
            (SELETE Sno
            FROM Student
            WHERE Sdept= 'CS');

• 删除数据：

  • 基本语法：

    DELETE
    FROM <表名>
    [WHERE <条件>]

  • 功能：删除指定表中满足 WHERE 子句条件的元组
  • WHERE 子句：指定要删除的元组，缺省表示要删除表中的所有元组（表的定义仍在数据字典中）
  • 删除元组的值：
    • 例：删除学号为 201215128 的学生记录

      DELETE
      FROM Student
      WHERE Sno='201215128';

    • 例：删除 2 号课程的所有选课记录

      DELETE
      FROM SC
      WHERE Cno='2';

    • 例：删除所有的学生选课记录

      DELETE
      FROM SC;

  • 带子查询的删除语句：
    • 例：删除计算机科学系所有学生的选课记录

      DELETE
      FROM SC
      WHERE Sno IN
          (SELETE Sno
          FROM Student
          WHERE Sdept= 'CS');

  • DBMS 在执行插入语句时会检查所插元组是否破坏表上已定义
    的完整性规则
    • 参照完整性（不允许删除、级联删除）

5. 空值

• 空值的概念：

  • 空值就是“不知道”或“不存在”或“无意义”的值
  • SQL 语言允许某些元组的某些属性在一定情况下取空值：
    • 该属性应该有一个值，但目前不知道它的具体值
    • 该属性不应该有值
    • 某种原因不便于填写

• 空值的产生：

  • 例：向 SC 表中插入一个元组，学号是“201215126”，课程号是“1”，成绩为空

    INSERT INTO SC(Sno, Cno, Grade)
    VALUES('201215126', '1', NULL);
    /*在插入时该学生还没有考试成绩，取空值*/

    INSERT INTO SC(Sno, Cno)
    VALUES('201215126', '1');
    /*在插入语句中没有赋值的属性，取空值*/

  • 例：将 Student 表中学号是“201215200”的学生所属的系改为空值

    UPDATE Student 
    SET Sdept = NULL
    WHERE Sno = '201215200';

  • 外连接会产生空值；空值的关系运算也会产生空值

• 空值的判断：判断一个属性的值是否为空值，用 IS NULL 或 IS NOT NULL

  • 例：从 Student 表中找出漏填了数据的学生信息

    SELECT *
    FROM Student
    WHERE Sname IS NULL OR Ssex IS NULL OR 
    Sage IS NULL OR Sdept IS NULL;

• 空值的约束条件：

  • 属性定义（或域定义）中有 NOT NULL 约束条件的不能取空值
  • 加了 UNIQUE 限制的属性不能取空值
  • 码属性不能取空值

• 空值的算术运算、比较运算和逻辑运算：

  • 空值与另一个值（包括另一个空值）的算术运算结果为空值
  • 空值与另一个值（包括另一个空值）的比较运算结果为 UNKNOWN
  • 三值逻辑的概念：T、F、U

    x y	x AND y	x OR y	NOT x
    T T	T	T	F
    T U	U	T	F
    T F	F	T	F
    U T	U	T	U
    U U	U	U	U
    U F	F	U	U
    F T	F	T	T
    F U	F	U	T
    F F	F	F	T

  • 例：找出选修 1 号课程的不及格的学生

    SELECT Sno
    FROM SC
    WHERE Grade<60 AND Cno= '1';
    /* 选出了参加考试不及格的学生，不包括缺考的学生 */

  • 例：找出选修 1 号课程的不及格的学生及缺考的学生

    SELECT Sno
    FROM SC
    WHERE Grade < 60 AND Cno = '1'
    UNION
    SELECT Sno
    FROM SC
    WHERE Grade IS NULL AND Cno= '1';

    SELECT Sno
    FROM SC
    WHERE Cno='1' AND (Grade<60 OR Grade IS NULL);

6. 视图

• 视图的特点：

  • 虚表，是从一个或几个基本表（或视图）导出的表
  • 只存放视图的定义，不会出现数据冗余
  • 基表中的数据发生变化，从视图中查询出的数据也随之改变

• 基于视图的操作：

  • 查询
  • 删除（只影响视图本身）
  • 受限更新（直接影响基本表）
  • 定义基于该视图的新视图

• 建立视图：

  • 基本语法：

    CREATE VIEW <视图名> [(<列名> [, <列名>]...)]
    AS <子查询>
    [WITH CHECK OPTION];

    • 子查询可以是任意的 SELECT 语句，是否含有 ORDER BY 子句和 DISTINCT 短语，取决于具体系统的实现
    • WITH CHECK OPTION 表示对视图进行更新、插入或删除操作时，要保证满足视图定义中的谓词条件（子查询条件表达式）
    • 组成视图的属性列名：全部省略或全部指定，但在下面三种情况必须明确指定组成视图的所有列名：
      • 某个目标列不是单纯的属性名，而是聚集函数或列表达式
      • 多表连接时选出了几个同名列作为视图的字段
      • 需要在视图中为某个列启用新的更合适的名字
    • DBMS 执行 CREATE VIEW 语句时只是把视图的定义存入数据字典，并不执行其中的 SELECT 语句
  • 行列子集视图：若一个视图由单个基本表导出，只是去掉某些行列，但保留主码，这类视图称为行列子集视图
    • 例：建立信息系学生的视图，并要求透过该视图进行的更新操作只涉及信息系学生

      CREATE VIEW IS_Student
            AS 
            SELECT Sno, Sname, Sage
            FROM Student
            WHERE Sdept= 'IS'
            WITH CHECK OPTION;

  • 基于多个基表的视图：
    • 例：建立信息系选修了 1 号课程的学生视图

      CREATE VIEW IS_S1(Sno, Sname, Grade)
            AS 
            SELECT Student.Sno, Sname, Grade
            FROM Student, SC
            WHERE Sdept= 'IS' AND
                  Student.Sno=SC.Sno AND
                  SC.Cno= '1';

  • 基于视图的视图：
    • 例：建立信息系选修了 1 号课程且成绩在 90 分以上的学生的视图

      CREATE VIEW IS_S2
            AS
            SELECT Sno, Sname, Grade
            FROM IS_S1
            WHERE Grade>=90;

  • 带表达式的视图：
    • 例：定义一个反映学生出生年份的视图

      CREATE VIEW BT_S(Sno, Sname, Sbirth)
      AS 
      SELECT Sno, Sname, 2014-Sage
      FROM Student

    • 设置一些派生属性列，也称为虚拟列，例如 Sbirth
    • 带表达式的视图必须明确定义组成视图的各个属性列名
  • 建立分组视图：
    • 例：将学生的学号及他的平均成绩定义为一个视图，假设 SC 表中“成绩”列 Grade 为数字型

      CREATE VIEW S_G(Sno，Gavg)
            AS 
            SELECT Sno，AVG(Grade)
            FROM SC
            GROUP BY Sno;

  • 不指定属性列：
    • 例：将 Student 表中所有女生记录定义为一个视图

      CREATE VIEW F_Student1(F_sno，name，sex，age，dept)
            AS 
            SELECT *
            FROM Student
            WHERE Ssex='女';

      • 缺点：修改基表 Student 的结构后，Student 表与 F_Student1 视图的映象关系被破坏，导致该视图不能正确工作

• 删除视图：

  • 基本语法：DROP VIEW <视图名>[CASCADE];
    • 该语句从数据字典中删除指定的视图定义
    • 由该视图导出的其他视图定义仍在数据字典中，但已不能使用，必须显式删除
    • 删除基表时，由该基表导出的所有视图定义都必须显式删除
  • 例：
    • 删除视图 BT_S：DROP VIEW BT_S;
    • 删除视图 IS_S1：DROP VIEW IS_S1; 拒绝执行
    • 级联删除：DROP VIEW IS_S1 CASCADE;

• 查询视图：

  • 用户角度：查询视图与查询基本表相同
  • DBMS 实现视图查询的方法：
    • 实体化视图（View Materialization）：
      • 有效性检查：检查所查询的视图是否存在
      • 执行视图定义，将视图临时实体化，生成临时表
      • 查询视图转换为查询临时表
      • 查询完毕删除被实体化的视图(临时表)
    • 视图消解法（View Resolution）：
      • 进行有效性检查，检查查询的表、视图等是否存在；如果存在，则从数据字典中取出视图的定义
      • 把视图定义中的子查询与用户的查询结合起来，转换成等价的对基本表的查询
      • 执行修正后的查询
  • 例：在信息系学生的视图中找出年龄小于 20 岁的学生

    SELECT Sno，Sage
    FROM IS_Student
    WHERE Sage<20;

    /* 转换后的查询语句 */
    SELECT Sno，Sage 
    FROM Student
    WHERE Sdept= 'IS' AND Sage<20;

  • 例（多表查询）：查询信息系选修了 1 号课程的学生

    SELECT IS_Student.Sno，Sname
    FROM IS_Student，SC
    WHERE IS_Student.Sno = SC.Sno AND SC.Cno= '1';

  • 例：在S_G视图中查询平均成绩在90分以上的学生学号和平均成绩

    SELECT *
    FROM S_G
    WHERE Gavg>=90;

    /* 转换后的查询语句 */
    SELECT Sno，AVG(Grade)
    FROM SC
    WHERE AVG(Grade)>=90 /* 查询出现语法错误 */
    GROUP BY Sno；

  • 视图消解法的局限：有些情况下，视图消解法不能生成正确查询，DBMS 会限制这类查询

• 更新视图：

  • 用户角度：更新视图与更新基本表相同
  • DBMS 实现视图更新的方法：
    • 视图实体化法（View Materialization）
    • 视图消解法（View Resolution）
  • 指定 WITH CHECK OPTION 子句后，DBMS 在更新视图时会进行检查，防止用户通过视图对不属于视图范围内的基本表数据进行更新
  • 例：将信息系学生视图 IS_Student 中学号 201215122 的学生姓名改为“刘辰”

    UPDATE IS_Student
    SET Sname= '刘辰'
    WHERE Sno= '201215122';

    /* 转换后的语句 */
    UPDATE Student
    SET Sname= '刘辰'
    WHERE Sno= '201215122' AND Sdept= 'IS';

  • 例：向信息系学生视图 IS_S 中插入一个新的学生记录：201215129，赵新，20岁

    INSERT
    INTO IS_Student
    VALUES('201215129'，'赵新'，20);

    /* 转换为对基本表的更新 */
    INSERT
    INTO Student(Sno，Sname，Sage，Sdept)
    VALUES('201215129'，'赵新'，20，'IS');

  • 例：删除视图 CS_S 中学号为 201215129 的记录

    DELETE
    FROM IS_Student
    WHERE Sno= '201215129';

    /* 转换为对基本表的更新 */
    DELETE
    FROM Student
    WHERE Sno= '201215129' AND Sdept= 'IS';

  • 更新视图的限制：一些视图是不可更新的，因为对这些视图的更新不能唯一地有意义地转换成对相应基本表的更新(对两类方法均如此)
    • 例：视图 S_G 为不可更新视图

      UPDATE S_G
      SET Gavg=90
      WHERE Sno= '95001';

  • 实际系统对视图更新的限制：
    • 允许对行列子集视图进行更新
    • 对其他类型视图的更新不同系统有不同限制

• 视图的作用：

  • 视图能够简化用户的操作：当视图中数据不是直接来自基本表时，定义视图能够简化用户的操作
    • 基于多张表连接形成的视图
    • 基于复杂嵌套查询的视图
    • 含导出属性的视图
  • 视图使用户能以多种角度看待同一数据：视图机制能使不同用户以不同方式看待同一数据，适应不同种类的用户数据库共享的需要
  • 视图对重构数据库提供了一定程度的逻辑独立性
  • 视图能够对机密数据提供安全保护：
    • 对不同用户定义不同视图，使每个用户只能看到他有权看到的数据
    • 通过 WITH CHECK OPTION 对关键数据定义操作时间限制
  • 适当的视图能够更清晰表达查询

第五章 数据库设计

1. 数据库设计概述

• 数据库设计：

  • 数据库设计是指对于一个给定的应用环境，构造（设计）优化的数据库逻辑模式和物理结构，并据此建立数据库及其应用系统，使之能够有效地存储和管理数据，满足各种用户的应用需求，包括信息管理要求和数据操作要求
  • 目标：为用户和各种应用系统提供一个信息基础设施和高效率的运行环境

• 数据库设计的特点：

  • 数据库建设是硬件、软件和干件的结合
    • 三分技术，七分管理，十二分基础数据
    • 技术与管理的界面称之为“干件”
  • 数据库设计应该与应用系统设计相结合
    • 结构（数据）设计：设计数据库框架或数据库结构
    • 行为（处理）设计：设计应用程序、事务处理等

• 数据库设计的基本步骤：

  • 数据库设计分 6 个阶段：
    • 需求分析
    • 概念结构设计
    • 逻辑结构设计
    • 物理结构设计
    • 数据库实施
    • 数据库运行和维护
  • 需求分析和概念设计独立于任何数据库管理系统
  • 逻辑设计和物理设计与选用的 DBMS 密切相关

2. 需求分析

• 需求分析：

  • 需求分析就是分析用户的需要与要求
  • 需求分析是设计数据库的起点
  • 需求分析的结果是否准确地反映了用户的实际要求，将直接影响到后面各个阶段的设计，并影响到设计结果是否合理和实用

• 需求分析的任务：

  • 详细调查现实世界要处理的对象（组织、部门、企业等）
  • 充分了解原系统（手工系统或计算机系统）工作概况
  • 明确用户的各种需求
  • 在此基础上确定新系统的功能
  • 充分考虑今后可能的扩充和改变，不能仅仅按当前应用需求来设计数据库

• 需求分析的重点：是“数据”和“处理”，调查、收集与分析用户在数据管理中：

  • 信息要求（查询内容与性质）
  • 处理要求（功能、响应时间、方式）
  • 安全性与完整性要求

• 需求分析的难点：

  • 确定用户最终需求的难点：
    • 用户缺少计算机知识，无法一下子准确地表达自己的需求，他们所提出的需求往往不断地变化
    • 设计人员缺少用户的专业知识，不易理解用户的真正需求，甚至误解用户的需求
    • 新的硬件、软件技术的出现也会使用户需求发生变化
  • 解决方法：
    • 设计人员必须采用有效的方法，与用户不断深入地进行交流，才能逐步得以确定用户的实际需求

• 需求分析的方法：

  • 调查清楚用户的实际需求并进行初步分析
  • 与用户达成共识
  • 进一步分析与表达这些需求：
    • 分析和表达用户的需求的常用方法：结构化分析方法（Structured Analysis，SA 方法）
      • 从最上层的系统组织机构入手
      • 自顶向下、逐层分解
      • 用数据流图和数据字典描述系统
    • 首先把任何一个系统都抽象为信息要求、处理要求
    • 分解处理功能和数据：
      • 分解处理功能：将处理功能的具体内容分解为若干子功能
      • 分解数据：处理功能逐步分解同时，逐级分解所用数据，形成若干层次的数据流图
      • 表达方法：
        • 处理逻辑：用判定表或判定树来描述
        • 数据：用数据字典来描述
    • 将分析结果再次提交给用户，征得用户的认可

• 数据字典的用途：

  • 数据字典是各类数据描述的集合
  • 数据字典是进行详细的数据收集和数据分析所获得的主要结果
  • 数据字典在数据库设计中占有很重要的地位

• 数据字典的内容：

  • 数据字典的内容：数据项、数据结构、数据流、数据存储、处理过程
    • 数据项是数据的最小组成单位
    • 若干个数据项可以组成一个数据结构
    • 数据字典通过对数据项和数据结构的定义来描述数据流、数据存储的逻辑内容
  • 数据项：
    • 数据项是不可再分的数据单位
    • 对数据项的描述：数据项描述＝｛数据项名，数据项含义说明，别名，数据类型，长度，取值范围，取值含义，与其他数据项的逻辑关系，数据项之间的联系｝
    • 取值范围、与其他数据项的逻辑关系定义了数据的完整性约束条件
  • 数据结构：
    • 数据结构反映了数据之间的组合关系
    • 一个数据结构可以由若干个数据项组成，也可以由若干个数据结构组成，或由若干个数据项和数据结构混合组成
    • 对数据结构的描述：数据结构描述＝｛数据结构名，含义说明，组成:｛数据项或数据结构｝｝
  • 数据流：
    • 数据流是数据结构在系统内传输的路径
    • 对数据流的描述：数据流描述＝｛数据流名，说明，数据流来源，数据流去向，组成:｛数据结构｝，平均流量，高峰期流量｝
      • 数据流来源是说明该数据流来自哪个过程
      • 数据流去向是说明该数据流将到哪个过程去
      • 平均流量是指在单位时间（每天、每周、每月等）里的传输次数
      • 高峰期流量则是指在高峰时期的数据流量
  • 数据存储：
    • 数据存储是数据结构停留或保存的地方，也是数据流的来源和去向之一
    • 对数据存储的描述：数据存储描述＝｛数据存储名，说明，编号，输入的数据流，输出的数据流，组成:｛数据结构｝，数据量，存取频度，存取方式｝
      • 输入的数据流：指出数据来源
      • 输出的数据流：指出数据去向
      • 存取频度：每次存取多少数据，每天（或每小时、每周等）存取几次等信息
      • 存取方法：批处理/联机处理；检索/更新；顺序检索/随机检索
  • 处理过程：
    • 处理过程的具体处理逻辑一般用判定表或判定树来描述，数据字典中只需要描述处理过程的说明性信息
    • 处理过程说明信息的描述：处理过程描述＝｛处理过程名，说明，输入:｛数据流｝，输出:｛数据流｝，处理:｛简要说明｝｝

• 数据字典：

  • 数据字典是关于数据库中数据的描述，是元数据，而不是数据本身
  • 数据字典在需求分析阶段建立，在数据库设计过程中不断修改、充实、完善

3. 概念结构设计

• 概念结构：

  • 什么是概念结构设计：
    • 需求分析阶段描述的用户应用需求是现实世界的具体需求
    • 将需求分析得到的用户需求抽象为信息结构即概念模型的过程就是概念结构设计
    • 概念结构是各种数据模型的共同基础，它比数据模型更独立于机器，更抽象，从而更加稳定
    • 概念结构设计是整个数据库设计的关键
  • 概念结构设计的特点：
    • 能真实、充分地反映现实世界，包括事物和事物之间的联系，能满足用户对数据的处理要求
    • 易于理解，从而可以用它和不熟悉计算机的用户交换意见
    • 易于更改，当应用环境和应用要求改变时，容易对概念模型修改和扩充
    • 易于向关系、网状、层次等各种数据模型转换
  • 描述概念模型的工具：E-R 模型

• 两个实体之间的联系：1:1 联系、1:n 联系、m:n 联系

• 概念结构设计的四类方法：

  • 自顶向下：首先定义全局概念结构的框架，然后逐步细化
  • 自底向上：首先定义各局部应用的概念结构，然后将它们集成起来，得到全局概念结构
  • 逐步扩张：首先定义最重要的核心概念结构，然后向外扩充，以滚雪球的方式逐步生成其他概念结构，直至总体概念结构
  • 混合策略：将自顶向下和自底向上相结合，用自顶向下策略设计一个全局概念结构的框架，以它为骨架集成由自底向上策略中设计的各局部概念结构

• 概念结构设计的方法与步骤：

  • 常用策略：自顶向下地进行需求分析，自底向上地设计概念结构
  • 自底向上设计概念结构的步骤：
    • 第 1 步：抽象数据并设计局部视图
    • 第 2 步：集成局部视图，得到全局概念结构
    • 第 3 步：验证整体概念结构

• 数据抽象：

  • 数据抽象的主要功能：
    • 对需求分析阶段收集到的数据进行分类、组织（聚集），形成
      • 实体
      • 实体的属性、标识实体的码
      • 确定实体之间的联系类型（1:1，1:n，m:n）

• 局部视图设计：

  • 选择局部应用：在多层的数据流图中选择一个适当层次的数据流图，作为设计分 E-R 图的出发点
    • 通常以中层数据流图作为设计分 E-R 图的依据
  • 逐一设计分 E-R 图：
    • 任务：
      • 将各局部应用涉及的数据分别从数据字典中抽取出来
      • 参照数据流图，标定各局部应用中的实体、实体的属性、标识实体的码
      • 确定实体之间的联系及其类型（1:1，1:n，m:n）
    • 区分实体和属性：为了简化 E-R 图的处置，现实世界中的事物凡能够作为属性对待的，应尽量作为属性
      • 属性不能再具有需要描述的性质，即属性必须是不可分的数据项，不能再由另一些属性组成
      • 属性不能与其他实体具有联系，联系只发生在实体之间
      • 符合上述两条特性的事物一般作为属性对待

• 视图的集成：

  • 各个局部视图即分 E-R 图建立好后，还需要对它们进行合并，集成为一个整体的数据概念结构，即总 E-R 图
  • 视图集成的两种方式：
    • 多个分 E-R 图一次集成：一次集成多个分 E-R 图，通常用于局部视图比较简单时
    • 逐步累积式：首先集成两个局部视图（通常是比较关键的两个），以后每次将一个新的局部视图集成进来
  • 各分 E-R 图存在冲突：属性冲突、命名冲突、结构冲突
    • 合并分 E-R 图的主要工作与关键：合理消除各分 E-R 图的冲突
    • 属性冲突：
      • 属性域冲突：属性值的类型、取值范围或取值集合不同
        • 例：某些部门（即局部应用）以出生日期形式表示学生的年龄，而另一些部门（即局部应用）用整数形式表示学生的年龄
      • 属性取值单位冲突：
        • 例：学生的身高，有的以米为单位，有的以厘米为单位，有的以尺为单位
    • 命名冲突：
      • 同名异义：不同意义的对象在不同的局部应用中具有相同的名字
        • 例：局部应用 A 中将教室称为房间，局部应用 B 中将学生宿舍称为房间
      • 异名同义（一义多名）：同一意义的对象在不同的局部应用中具有不同的名字
        • 例：有的部门把教科书称为课本，有的部门则把教科书称为教材
    • 结构冲突：
      • 同一对象在不同应用中具有不同的抽象
      • 同一实体在不同分 E-R 图中所包含的属性个数和属性排列次序不完全相同
      • 实体之间的联系在不同局部视图中呈现不同的类型

• 修改与重构：

  • 基本任务：消除不必要的冗余，设计生成基本 E-R 图
    • 分 E-R 图 $\xrightarrow{\text{合并}}$ 初步 E-R 图 $\xrightarrow{\text{消除不必要的冗余}}$ 基本 E-R 图
  • 冗余：
    • 冗余的数据是指可由基本数据导出的数据；冗余的联系是指可由其他联系导出的联系
    • 冗余数据和冗余联系容易破坏数据库的完整性，给数据库维护增加困难
    • 并不是所有的冗余数据与冗余联系都必须加以消除，有时为了提高某些应用的效率，不得不以冗余信息作为代价
  • 消除冗余的方法：
    • 分析方法：以数据字典和数据流图为依据，根据数据字典中关于数据项之间逻辑关系的说明来消除冗余
    • 效率 VS 冗余信息：需要根据用户的整体需求来确定
      • 若人为地保留了一些冗余数据，则应把数据字典中数据关联的说明作为完整性约束条件
    • 规范化理论：函数依赖的概念提供了消除冗余联系的形式化工具
      • 方法：
        1. 确定分 E-R 图实体之间的数据依赖 $F_L$
        2. 求 $F_L$ 的最小覆盖 $G_L$，差集为 $D = F_L-G_L$，逐一考察 $D$ 中的函数依赖，确定是否是冗余的联系，若是，就把它去掉
      • 冗余的联系一定在 $D$ 中，而 $D$ 中的联系不一定是冗余的
      • 当实体之间存在多种联系时，要将实体之间的联系在形式上加以区分

• 验证整体概念结构：视图集成后形成一个整体的数据库概念结构，对该整体概念结构还必须进行进一步验证，确保它能够满足下列条件：

  • 整体概念结构内部必须具有一致性，不存在互相矛盾的表达
  • 整体概念结构能准确地反映原来的每个视图结构，包括属性、实体及实体间的联系
  • 整体概念结构能满足需要分析阶段所确定的所有要求

4. 逻辑结构设计

• 逻辑结构设计：

  • 逻辑结构设计的任务：把概念结构设计阶段设计好的基本 E-R 图转换为与选用 DBMS 产品所支持的数据模型相符合的逻辑结构

  • 逻辑结构设计的步骤：

    

• E-R 图向关系模型的转换：

  • 转换内容：
    • E-R 图由实体、实体的属性和实体之间的联系三个要素组成
    • 关系模型的逻辑结构是一组关系模式的集合
    • 将 E-R 图转换为关系模型：将实体、实体的属性和实体之间的联系转化为关系模式
  • 一个实体型转换为一个关系模式
    • 关系的属性：实体型的属性
    • 关系的码：实体型的码
  • 一个 m:n 联系转换为一个关系模式
    • 关系的属性：与该联系相连的各实体的码以及联系本身的属性
    • 关系的码：各实体码的组合
  • 一个 1:n 联系可以转换为一个独立的关系模式，也可以与 n 端对应的关系模式合并
    • 转换为一个独立的关系模式
      • 关系的属性：与该联系相连的各实体的码以及联系本身的属性
      • 关系的码：n 端实体的码
    • 与 n 端对应的关系模式合并
      • 合并后关系的属性：在 n 端关系中加入 1 端关系的码和联系本身的属性
      • 合并后关系的码：不变
      • 可以减少系统中的关系个数，一般情况下更倾向于采用这种方法
  • 一个 1:1 联系可以转换为一个独立的关系模式，也可以与任意一端对应的关系模式合并
    • 转换为一个独立的关系模式
      • 关系的属性：与该联系相连的各实体的码以及联系本身的属性
      • 关系的候选码：每个实体的码均是该关系的候选码
    • 与某一端对应的关系模式合并
      • 合并后关系的属性：加入对应关系的码和联系本身的属性
      • 合并后关系的码：不变
    • 注意：
      • 从理论上讲，1:1 联系可以与任意一端对应的关系模式合并
      • 但在一些情况下，与不同的关系模式合并效率会大不一样，因此究竟应该与哪端的关系模式合并需要依应用的具体情况而定
      • 由于连接操作是最费时的操作，所以一般应以尽量减少连接操作为目标
  • 三个或三个以上实体间的一个多元联系转换为一个关系模式
    • 关系的属性：与该多元联系相连的各实体的码以及联系本身的属性
    • 关系的码：各实体码的组合
  • 具有相同码的关系模式可合并：
    • 目的：减少系统中的关系个数
    • 合并方法：将其中一个关系模式的全部属性加入到另一个关系模式中，然后去掉其中的同义属性（可能同名也 可能不同名），并适当调整属性的次序

• 数据模型的优化：

  • 数据库逻辑设计的结果不是唯一的
  • 得到初步数据模型后，还应该适当地修改、调整数据模型的结构，以进一步提高数据库应用系统的性能，这就是数据模型的优化
  • 关系数据模型的优化通常以规范化理论为指导
  • 优化数据模型的方法：
    • 确定数据依赖：按需求分析阶段所得到的语义，分别写出每个关系模式内部各属性之间的数据依赖以及不同关系模式属性之间数据的依赖
    • 消除冗余的联系：对于各个关系模式之间的数据依赖进行极小化处理，消除冗余的联系
    • 确定所属范式：
      • 按照数据依赖的理论对关系模式逐一进行分析
      • 考查是否存在部分函数依赖、传递函数依赖、多值依赖等
      • 确定各关系模式分别属于第几范式
    • 按照需求分析阶段得到的各种应用对数据处理的要求，分析对于这样的应用环境这些模式是否合适，确定是否要对它们进行合并或分解
      • 并不是规范化程度越高的关系就越优，一般说来，第三范式就足够了
    • 按照需求分析阶段得到的各种应用对数据处理的要求，对关系模式进行必要的分解，以提高数据操作的效率和存储空间的利用率
      • 水平分解：
        • 把(基本)关系的元组分为若干子集合，定义每个子集合为一个子关系，以提高系统的效率
        • 水平分解的适用范围：满足“80/20原则”的应用；并发事务经常存取不相交的数据
      • 垂直分解：
        • 把关系模式 $R$ 的属性分解为若干子集合，形成若干子关系模式
        • 垂直分解的原则：取决于分解后 $R$ 上的所有事务的总效率是否得到了提高

• 设计用户子模式：

  • 定义数据库全局模式主要是从系统的时间效率、空间效率、易维护等角度出发
  • 定义用户外模式时应注重考虑用户的习惯与方便，包括：
    • 使用更符合用户习惯的别名
    • 针对不同级别的用户定义不同的 View，以满足系统对安全性的要求
    • 简化用户对系统的使用

5. 数据库物理设计

• 数据库的物理设计：

  • 数据库在物理设备上的存储结构与存取方法称为数据库的物理结构，它依赖于选定的数据库管理系统

  • 为一个给定的逻辑数据模型选取一个最适合应用环境的物理结构的过程，就是数据库的物理设计

  • 数据库物理设计的步骤：

    

• 数据库物理设计的内容和方法：

  • 设计物理数据库结构的准备工作：
    • 对要运行的事务进行详细分析，获得选择物理数据库设计所需参数
    • 充分了解所用 RDBMS 的内部特征，特别是系统提供的存取方法和存储结构
  • 选择物理数据库设计所需参数：
    • 数据库查询事务：查询的关系、查询条件所涉及的属性、连接条件所涉及的属性、查询的投影属性、被更新的关系、每个关系上的更新操作条件所涉及的属性、修改操作要改变的属性值
    • 每个事务在各关系上运行的频率和性能要求
  • 关系数据库物理设计的内容：
    • 为关系模式选择存取方法(建立存取路径)
    • 设计关系、索引等数据库文件的物理存储结构
  • 关系模式存取方法选择：
    • 数据库系统是多用户共享的系统，对同一个关系要建立多条存取路径才能满足多用户的多种应用要求
    • 物理设计的第一个任务就是要确定选择哪些存取方法，即建立哪些存取路径
    • DBMS 常用存取方法：
      • 索引方法：B+ 树索引、Hash 索引
      • 聚簇（Cluster）方法
    • 选择索引存取方法的主要内容：根据应用要求确定
      • 对哪些属性列建立索引
      • 对哪些属性列建立组合索引
      • 哪些索引要设计为唯一索引
    • 索引存取方法的选择：
      • 选择索引存取方法的一般规则：
        • 如果一个(或一组)属性经常在查询条件中出现，则考虑在这个(或这组)属性上建立索引(或组合索引)
        • 如果一个属性经常作为最大值和最小值等聚集函数的参数，则考虑在这个属性上建立索引
        • 如果一个(或一组)属性经常在连接操作的连接条件中出现，则考虑在这个(或这组)属性上建立索引
      • 关系上定义的索引数过多会带来较多的额外开销
        • 维护索引的开销
        • 查找索引的开销
      • 若一个关系更新频率很高，这个关系上不能定义太多索引
  • 确定数据库的存储结构：
    • 确定数据库物理结构的内容：
      • 确定数据的存放位置和存储结构：关系、索引、聚簇、日志、备份
      • 确定系统配置
    • 确定数据的存放位置：
      • 影响数据存放位置和存储结构的因素：
        • 硬件环境
        • 应用需求：存取时间、存储空间利用率、维护代价
          • 这三个方面常常是相互矛盾的
      • 基本原则：根据应用情况将数据分开存放，以提高系统性能
        • 易变部分与稳定部分
        • 存取频率较高部分与存取频率较低部分
    • 确定系统配置：DBMS 产品一般都提供了一些存储分配参数
      • 同时使用数据库的用户数
      • 同时打开的数据库对象数
      • 使用的缓冲区长度、个数
      • 时间片大小
      • 数据库的大小
      • 装填因子
      • 锁的数目
      • 等等

• 评价物理结构：

  • 评价内容：对数据库物理设计过程中产生的多种方案进行细致的评价，从中选择一个较优的方案作为数据库的物理结构
  • 评价方法：
    • 定量估算各种方案：存取时间（时间效率）、存储空间（空间效率）、维护代价、用户要求
    • 对估算结果进行权衡、比较，选择出一个较优的合理的物理结构
    • 如果该结构不符合用户需求，则需要修改设计

6. 数据库实施与维护

• 数据库实施的工作内容：

  • 用 DDL 定义数据库结构
  • 数据载入，组织数据入库
  • 编制与调试应用程序
  • 数据库试运行

• 数据装载：

  • 数据库结构建立好后，就可以向数据库中装载数据；组织数据入库是数据库实施阶段最主要的工作
  • 数据装载方法：人工方法、计算机辅助数据入库

• 编制与调试应用程序：

  • 数据库应用程序的设计应该与数据库设计并行进行
  • 在数据库实施阶段，当数据库结构建立好后，就可以开始编制与调试数据库的应用程序；调试应用程序时由于数据入库尚未完成，可先使用模拟数据

• 数据库试运行：

  • 应用程序调试完成，并且已有一小部分数据入库后，就可以开始数据库的试运行
  • 数据库试运行也称为联合调试，其主要工作包括：
    • 功能测试：实际运行应用程序，执行对数据库的各种操作，测试应用程序的各种功能
    • 性能测试：测量系统的性能指标，分析是否符合设计目标
  • 数据的分期入库：
    • 重新设计物理结构甚至逻辑结构，会导致数据重新入库
    • 由于数据入库工作量实在太大，所以可以采用分期输入数据的方法：
      • 先输入小批量数据供先期联合调试使用
      • 待试运行基本合格后再输入大批量数据
      • 逐步增加数据量，逐步完成运行评价
  • 数据库的转储和恢复：
    • 在数据库试运行阶段，系统还不稳定，硬、软件故障随时都可能发生
    • 系统的操作人员对新系统还不熟悉，误操作也不可避免
    • 必须做好数据库的转储和恢复工作，尽量减少对数据库的破坏

• 数据库运行与维护：

  • 数据库试运行结果符合设计目标后，数据库就可以真正投入运行了
  • 数据库投入运行标着开发任务的基本完成和维护工作的开始
  • 对数据库设计进行评价、调整、修改等维护工作是一个长期的任务，也是设计工作的继续和提高
    • 应用环境在不断变化
    • 数据库运行过程中物理存储会不断变化
  • 在数据库运行阶段，对数据库经常性的维护工作主要是由 DBA 完成的，包括：
    • 数据库的转储和恢复
    • 数据库的安全性、完整性控制
    • 数据库性能的监督、分析和改进
    • 数据库的重组织和重构造

• 数据库的重组织和重构造：

  • 重组织的形式：全部重组织；部分重组织（只对频繁增、删的表进行重组织）
  • 重组织的目标：提高系统性能
  • 重组织的工作：
    • 按原设计要求：重新安排存储位置、回收垃圾、减少指针链重组织的目标
    • 数据库的重组织不会改变原设计的数据逻辑结构和物理结构
  • 数据库重构造：根据新环境调整数据库的模式和内模式、增加新的数据项、改变数据项的类型、改变数据库的容量、增加或删除索引、修改完整性约束条件

第六章 数据库编程

1. 概述

• SQL 语言：高度非过程化查询语言
  • 缺少流程控制能力
  • 难以实现业务中的逻辑控制

1.1 SQL 表达能力的限制

• SQL 语言表达能力的限制：
  • 无法表达递归等复杂操作（例如间接先修课的查询）
  • 无法对数据进行复杂操作（查询一周内将过生日的同学）
  • 无法自主设计业务处理逻辑（计算学生平均学分绩点）
  • 无法进行交互式操作（教学评价与反馈）

1.2 扩展 SQL 的功能

• 引入新的 SQL 子句：

  • WITH 子句：
    • 格式：

      WITH RS1［(<目标列>,<目标列>)］AS /* RS1为临时结果集的命名*/
      (SELECT 语句1) [, /* RS1对应SELECT 语句的执行结果*/
      /*SELECT语句1中的目标列与RS1中的目标列必须保持一致*/
      RS2［(<目标列>,<目标列>)］AS /* RS2为临时结果集的命名*/
      (SELECT 语句2),...] /* RS2对应SELECT 语句的执行结果*/
      /*SELECT语句2中的目标列与RS2中的目标列必须保持一致*/
      SQL语句; /* 执行与RS1，RS2,…,相关的查询*/

    • 例：求 81001-01 和 81001-02 两个教学班之间学生选课
      平均成绩的差异

      WITH
      RS1(Grade)
            AS
            (SELECT AVG(Grade) FROM SC
            WHERE Teachingclass = '81001-01'),
      RS2(Grade)
            AS
            (SELECT AVG(Grade) FROM SC
            WHERE Teachingclass = '81001-02')
      SELECT RS1.Grade-RS2.Grade from RS1,RS2;

  • WITH RECURSIVE 子句：
    • 格式：

      WITH RECURSIVE RS AS
        (
          SEED QUERY /*初始化查询的临时结果集，记为L[1]*/
          UNION [ALL] /*是否需要保留重复记录，加ALL为保留*/
          RECURSIVE QUERY
          /*执行递归查询，得到全部临时结果集，即L[2]∪…∪L[i]*/
        )
        SQL语句 /*执行与RS相关的查询*/

    • 例：打印“数据库系统概论”课程的所有先修课信息

      WITH RECURSIVE RS AS (
      /*初始化RS，假设结果集为L[1]，即“数据库系统概论”的所有直接先修课*/
      SELECT Cpno FROM Course WHERE Cname = '数据库系统概论'
      UNION
      /*递归查询第i层(i>=1)的数据，即第i-1层数据的直接先修课课程号，并更新RS*/
      SELECT Course.Cpno FROM Course,RS WHERE RS.Cpno = Course.Cno )
      /*根据RS中记录的所有先修课程号，通过查找课程表，输出课程号与课程名*/
      SELECT Cno, Cname FROM Course WHERE Cno IN (SELECT Cpno FROM RS);

• 引入新的内置函数：

  • SQL 常用的内置函数：
    • 数学函数（如绝对值函数等）
    • 聚合函数（如求和、求平均函数等）
    • 字符串函数（如求字符串长度、求子串函数等）
    • 日期和时间函数（如返回当前日期函数等）
    • 格式化函数（如字符串转IP地址函数等）
    • 控制流函数（如逻辑判断函数等）
    • 加密函数（如使用密钥对字符串加密函数等）
    • 系统信息函数（如返回当前数据库名、服务器版本函数等）
  • 例：打印一周内将过生日的学生信息

    SELECT Sno, Sname, Ssex, Sbirthdate, Smajor
    FROM Student
    WHERE to_date(to_char(current_date,
    'yyyy') || '-' ||
    to_char(Sbirthdate,
    'mm-dd'))
    BETWEEN CURRENT_DATE AND CURRENT_DATE + INTERVAL '7' DAY;

• 引入 PL/SQL 与存储过程/存储函数：

  • 关系数据库管理系统中引入 PL/SQL、存储过程和自定义函数等方法，使得用户可以自定义程序逻辑，开发完成业务逻辑复杂的应用系统

1.3 通过高级语言实现复杂应用

• 通过动态链接库调用的方式：关系数据库管理系统的功能被包装成一个子程序，由应用程序通过动态链接库调用来获得数据管理的功能
• 基于嵌入式 SQL 的方式：将 SQL 嵌入到高级语言中混合编程，SQL 语句负责操纵数据库，高级语言语句负责控制逻辑流程
• 基于 ODBC/JDBC 的中间件方式：建立了连接不同数据库的一组规范；无论使用什么数据库，都采用同样的一组 API 来访问数据库

2. 过程化 SQL

• 过程化 SQL 的块结构：

  • 过程化 SQL：SQL 的扩展，增加了过程化语句功能
    • 基本结构是块
    • 块之间可以互相嵌套
    • 每个块完成一个逻辑操作
  • 过程化 SQL 块的基本结构：
    • 定义部分：DECLARE 变量、常量、游标、异常等
      • 定义的变量、常量等只能在该基本块中使用
      • 当基本块执行结束时，定义就不再存在
    • 执行部分：

      BEGIN
        SQL 语句、过程化 SQL 的流程控制语句
      EXCEPTION
        异常处理部分 
      END;

• 变量和常量的定义：

  • 变量定义：
    • 变量名 数据类型 [[NOT NULL]:=初值表达式]
    • 变量名 数据类型 [[NOT NULL] 初值表达式]
  • 常量定义：
    • 常量名 数据类型 CONSTANT :=常量表达式
    • 常量必须要赋予一个值，并且该值在存在期间或常量的作用域内不能改变（如果试图修改它，过程化 SQL 将返回一个异常）
  • 赋值语句：变量名称 :=表达式

• 流程控制：过程化 SQL 功能

  • 条件控制语句：IF-THEN，IF-THEN-ELSE 和嵌套的 IF 语句
    • （1）

      IF condition THEN
      Sequence_of_statements;
      END IF;

    • （2）

      IF condition THEN
      Sequence_of_statements1;
      ELSE
      Sequence_of_statements2;
      END IF;

    • （3）在 THEN 和 ELSE 子句中还可以再包含 IF 语句，即 IF 语句可以嵌套
  • 循环控制语句：LOOP，WHILE-LOOP 和 FOR-LOOP
    • （1）简单的循环语句 LOOP

      LOOP
      Sequence_of_statements;
      END LOOP;

      • 多数数据库服务器的过程化 SQL 都提供 EXIT、BREAK 或 LEAVE 等循环结束语句，保证 LOOP 语句块能够在适当的条件下提前结束
    • （2）WHILE-LOOP

      WHILE condition LOOP
      Sequence_of_statements;
      END LOOP;

      • 每次执行循环体语句之前，首先对条件进行求值
      • 如果条件为真，则执行循环体内的语句序列
      • 如果条件为假，则跳过循环并把控制传递给下一个语句
    • （3）FOR-LOOP

      FOR count IN [REVERSE] bound1 … bound2 LOOP
      Sequence_of_statements;
      END LOOP;

  • 错误处理：
    • 如果过程化 SQL 在执行时出现异常，则应该让程序在产生异常的语句处停下来，根据异常的类型去执行异常处理语句
    • SQL 标准对数据库服务器提供什么样的异常处理做出了建议，要求过程化 SQL 管理器提供完善的异常处理机制

• 游标的定义与使用：

  • 游标：
    • 在过程化 SQL 中，如果 SELECT 语句只返回一条记录，可以将该结果存放到变量中
    • 当查询返回多条记录时，就要使用游标对结果集进行处理，一个游标与一个 SQL 语句相关联
  • 游标的用户接口：
    • 声明游标：

      DECLARE 游标名 [(参数1 数据类型, 参数2 数据类型, ...)] 
      CURSOR FOR 
      SELECT语句;

      • 定义游标仅仅是一条说明性语句，这时关系数据库管理系统并不执行 SELECT 语句
    • 打开游标：

      OPEN 游标名[(参数1 数据类型, 参数2 数据类型, ...)];

      • 打开游标实际上是执行相应的 SELECT 语句，把查询结果取到缓冲区中
      • 这时游标处于活动状态，指针指向查询结果集中的第一条记录
    • 使用游标：

      FETCH 游标名 INTO 变量1[, 变量2, ...];

      • 变量必须与 SELECT 语句中的目标列表达式一一对应
      • 用 FETCH 语句把游标指针向前推进一条记录，同时将缓冲区中的当前记录取出来送至变量供过程化 SQL 进一步处理
      • 循环执行 FETCH 语句，逐条取出结果集中的行进行处理
    • 关闭游标：

      CLOSE 游标名;

      • 游标被关闭后就不再和原来的查询结果集相联系
      • 但被关闭的游标可以再次被打开，与新的查询结果相联系
  • 例：根据给定学号 20180001，使用游标输出该学生的全部选课记录

    DECLARE
      CnoOfStudent CHAR(10);
      GradeOfStudent INT;
      mycursor CURSOR FOR
        SELECT Cno,Grade FROM SC WHERE Sno = ‘20180001’;
    
    BEGIN
    OPEN mycursor; /*打开游标*/
      LOOP /*循环遍历游标*/
        FETCH mycursor INTO CnoOfStudent, GradeOfStudent; /*检索游标*/
        EXIT WHEN mycursor%NOTFOUND;
        RAISE NOTICE 'Sno:20180001, Cno:%, Grade:%', CnoOfStudent, GradeOfStudent;
      END LOOP;
      CLOSE mycursor; /*关闭游标*/
    END;

• 存储过程：

  • 存储过程：
    • 类似于高级语言程序，过程化 SQL 程序也可以被命名和编译，并保存在数据库中，称为存储过程（stored procedure）或存储函数（stored function），供其他过程化 SQL 调用
    • 存储过程或存储函数也是一类数据库的对象，需要有创建、删除等语句，这里的存储函数指自定义函数
  • 存储过程的用户接口：
    • 创建存储过程：
      • 语法：

        CREATE OR REPLACE PROCEDURE 过程名(
          [[IN|OUT|INOUT] 参数1 数据类型,
          [IN|OUT|INOUT] 参数2 数据类型, ...]
        ) /*存储过程首部*/
        AS <过程化SQL块>; /*存储过程体，描述该存储过程的操作*/

        • 过程名：数据库服务器合法的对象标识
        • 参数列表：存储过程提供了 IN、OUT、INOUT 三种参数模式，分别对应输入、输出、输入输出三种语义，不声明参数模式时，缺省为 IN 类型；输入参数在被调用时需要指定参数值，输出参数调用时不传入参数值，而是作为返回值返回；输入输出参数调用时需要传入初始值，并会返回操作后的最终值；参数列表中需要指定参数模式、参数名、以及参数的数据类型
        • 过程体：是一个<过程化SQL块>，包括声明部分和可执行语句部分
      • 例：给定学生学号，计算学生的平均学分绩点 GPA

        CREATE OR REPLACE PROCEDURE compGPA( /*定义存储过compGPA*/
          IN inSno CHAR(10), /*输入参数：学生学号inSno*/
          OUT outGPA FLOAT) /*输出参数：平均学分绩outGPA*/
        AS
        DECLARE
          courseGPA INT; /*声明变量courseGPA，临时存储课程学分绩 */
          totalGPA INT; /*声明变量totalGPA，临时存储总学分绩 */
          totalCredit INT; /*声明变量totalCredit，临时存储总学分*/
          grade INT; /*声明变量grade，临时存储学生成绩 */
          credit INT; /*声明变量credit ，临时存储课程学分 */
          mycursor CURSOR FOR /*声明游标mycursor */
          SELECT Ccredit, grade FROM SC, Course
          WHERE Sno = inSno and SC.Cno = Course.Cno;
          BEGIN
            totalGPA := 0;
            totalCredit := 0;
            OPEN mycursor; /*打开游标mycursor */
            LOOP /*循环遍历游标*/
              FETCH mycursor INTO credit, grade; /*检索游标*/
              EXIT WHEN mycursor%NOTFOUND;
              IF grade BETWEEN 90 AND 100 THEN courseGPA := 4.0;
              ELSIF grade BETWEEN 80 AND 89 THEN courseGPA := 3.0;
              ELSIF grade BETWEEN 70 AND 72 THEN courseGPA := 2.0;
              ELSIF grade BETWEEN 60 AND 69 THEN courseGPA := 1.0;
              ELSE courseGPA := 0;
              END IF; /*参照表6.2，根据成绩找出某门课程对应的学分绩点*/
              totalGPA := totalGPA + courseGPA * credit;
              totalCredit := totalCredit + credit;
            END LOOP;
            CLOSE mycursor; /*关闭游标mycursor */
            outGPA := 1.0 * totalGPA / totalCredit;
          END;

    • 执行存储过程：
      • 语法：

        CALL/PERFORM [PROCEDURE] 过程名([参数1,参数2,...]);

        • 使用 CALL 或者 PERFORM 等方式激活存储过程的执行
        • 在过程化 SQL 中，数据库服务器支持在过程体中调用其他存储过程
      • 例：查询学号为“20180001”学生的课程 GPA

        DECLARE outGPA FLOAT;
        BEGIN
          CALL compGPA(‘20180001’, outGPA);
          RAISE NOTICE ‘GPA: %’, outGPA;
        END;

        • 在调用含有输入参数和输入输出参数的存储过程时，需要指定具体的参数值
        • 在调用含有输出参数的存储过程时，对应位置不需要传入参数值，但需要事先定义输出变量
    • 修改存储过程：
      • 重命名：

        ALTER PROCEDURE 过程名1 RENAME TO 过程名2;

      • 重新编译：

        ALTER PROCEDURE 过程名 COMPILE;

    • 删除存储过程：

      DROP PROCEDURE 过程名;

  • 存储过程的优点：
    • 运行效率高
    • 降低了客户机和服务器之间的通信量
    • 方便实施企业规则

• 存储函数：

  • 存储函数和存储过程的异同：
    • 同：都是持久性存储模块
    • 异：函数必须指定返回的类型
  • 函数的定义语句格式：

    CREATE OR REPLACE FUNCTION 函数名([参数1 数据类型, 参数2数据类型, ...])
    RETURNS <类型>
    AS <过程化SQL块>;

  • 函数的执行语句格式：

    CALL/SELECT 函数名 ([参数1,参数2,...]);

  • 修改函数：
    • 重命名：

      ALTER FUNCTION 函数名1 RENAME TO 函数名2;

    • 重新编译：

      ALTER FUNCTION 函数名 COMPILE;

3. JDBC 编程

• JDBC 工作原理概述：

  • JDBC (Java Database Connection)：
    • 由于不同的数据库管理系统的存在，在某个关系数据库管理系统下编写的应用程序就不能在另一个关系数据库管理系统下运行
    • 许多应用程序需要共享多个部门的数据资源，访问不同的关系数据库管理系统
    • 是面向 Java 语言的软件开发工具包（Java Development Kit，JDK）中有关数据库的一个组成部分
    • 提供了一组访问数据库的应用程序编程接口（Application Programming Interface，API）
  • JDBC 约束力：规范应用开发、规范关系数据库管理系统应用接口
  • JDBC 应用系统的体系结构：用户应用程序、JDBC 驱动程序管理器、数据源

• JDBC API 基础：

  • JDBC 中的常用类：JDBC 进行应用程序开发涉及到的所有类都包含在 java.sql 包中，不同的 JDBC 版本接口名和使用略有差异

    类名	路径	备注
    驱动程序类	java.sql.Driver	由各数据库厂商提供
    驱动程序管理类	java.sql.DriverManager	作用于应用程序与驱动程序之间
    数据库连接类	java.sql.Connection	用于建立与指定数据库的连接
    静态 SQL 语句执行类	java.sql.Statement	用于执行静态 SQL 语句并返回结果
    动态 SQL 语句执行类	java.sql.PreparedStatement	用于执行含参 SQL 语句并返回结果
    存储过程语句执行类	java.sql.CallableStatement	用于执行存储过程语句并返回结果
    结果集处理类	java.sql.ResultSet	用于检索结果集中的数据

  • 数据类型：

    • SQL 数据类型：用于数据源，VARCHAR、CHAR、BIT、NUMERIC、DATE 等
    • Java 数据类型：用于应用程序的 Java 代码，String、boolean、BigDecimal、byte、short、int 等
    • 由数据库管理系统的驱动程序完成自身数据类型和 JDBC 标准数据类型的映射

• 使用 JDBC 操纵数据库的工作流程：

  • 步骤 1：加载驱动程序
    • 驱动程序在 JDBC API 中实现定义数据交互的接口
  • 步骤 2：设置待连接数据库的 URL，并建立与数据库连接
    • 加载驱动后，可以通过 URL 地址与数据库建立连接
    • URL 包含了连接数据库所需的协议、子协议和数据库名称，定义格式为：<协议名>:<子协议名>:<数据库名称>
  • 步骤 3：执行SQL语句
    • 静态语句执行类对象(Statement)
    • 派生执行类对象：
      • 动态语句执行类(PreparedStatement)：执行动态的 SQL 语句
      • 存储过程执行类(CallableStatement)：执行数据库存储过程
    • 执行方法：
      • ResultSet executeQuery(): 执行数据库查询语句
      • int executeUpdate(): 处理增、删、改以及定义语句
      • boolean execute(): 处理存储过程或动态 SQL 语句
    • SQL 注入防御：预编译；正则过滤，输入验证，框架
  • 步骤 4：处理结果集，并处理用户逻辑
    • ResultSet: 结果集合类对象
      • .GetXXX(参数)：获取元组的属性值，XXX 代表某种数据类型；可以指定参数为列号（JDBC 的列从 1 开始）或列名
      • 游标(cursor)：JDBC 处理结果集的机制
  • 步骤 5：释放资源
    • 执行结束后，将与数据库进行交互的对象释放
    • 释放资源有标准的顺序：
      • 关闭结果集：ResultSet.close()
      • 关闭语句执行类对象：Statement.close()
      • 释放数据库连接对象：Connection.close()
    • 释放资源的 Coding Tips：
      • Connection 对象在应用程序中较为稀有，尽量做到晚创建，早释放
      • 推荐在 finally 代码块中释放资源，以满足异常处理机制（finally 语句在什么情况下都会执行,确保一定会释放资源）

第七章 数据库安全

1. 计算机安全性概述

• 问题的提出：

  • 数据库的一大特点是数据可以共享
  • 但数据共享必然带来数据库的安全性问题
  • 数据库系统中的数据共享不能是无条件的共享

• 数据库的不安全因素：

  • 数据库的安全性，是指保护数据库以防止不合法使用所造成的数据泄漏、更改或破坏
  • 产生威胁的因素：
    • 非授权用户对数据库的恶意存取和破坏
    • 数据库中重要或敏感的数据被泄露
    • 安全环境的脆弱性

• 计算机系统的三类安全性问题：

  • 计算机系统安全性：为计算机系统建立和采取的各种安全保护措施，以保护计算机系统中的硬件、软件及数据，防止其因偶然或恶意的原因使系统遭到破坏，数据遭到更改或泄露等
  • 三类计算机系统安全性问题：
    • 技术安全类
    • 管理安全类
    • 政策法律类

• 可信计算机系统评测标准：

  • 为降低进而消除对系统的安全攻击，各国引用或制定了一系列安全标准

  • 1985 年美国国防部（DoD）正式颁布《DoD可信计算机系统评估标准》（简称 TCSEC 或 DoD85），又称桔皮书

    • TCSEC 标准的目的：
      • 提供一种标准，使用户可以对其计算机系统内敏感信息安全操作的可信程度做评估
      • 给计算机行业的制造商提供一种可循的指导规则，使其产品能够更好地满足敏感应用的安全需求

  • 1991 年 4 月美国 NCSC（国家计算机安全中心）颁布了《可信计算机系统评估标准关于可信数据库系统的解释》（TCSEC/ Trusted Database Interpretation 简称 TCSEC/TDI）

    • TDI 又称紫皮书，它将 TCSEC 扩展到数据库管理系统
    • TDI 中定义了数据库管理系统的设计与实现中需满足和用以进行安全性级别评估的标准

  • TCSEC/TDI 安全级别划分：

    类别	级别	名称	主要特征
    D	D	最小保护	没有安全保护，如 ms－dos
    C	C1	自主安全保护	实现自主存取控制 DAC，具有识别与授权的责任，如早期 UNIX 系统
    	C2	受控存储控制	安全产品的最低档，提供受控的存取保护，将 C1 的 DAC 进一步细化，实施审计和资源隔离，如 windows 2000 和 Oracle 7
    B	B1	标识安全保护	对系统数据加以标记，实施强制存取控制 MAC 和审计，如 Oracle 公司的 Trusted Oracle 7，Sybase 公司的 Secure SQL Server version 11.0.6，Informix公司的 Incorporated INFORMIX Secure 5.0
    	B2	结构化保护	除满足 B1 要求外，要实行强制性的控制并进行严格的保护，如操作系统 Trusted Xenix 系统
    	B3	安全域	提供可信设备的管理和恢复，即使计算机崩溃也不会泄露系统信息，如 Honeywell Federal Systems XTS－200
    A	A	验证设计	形式化的最高级描述和验证

  • CC 标准：提出国际公认的表述信息技术安全性的结构

    • 把信息产品的安全要求分为：
      • 安全功能要求：规范产品和系统的安全行为
      • 安全保证要求：解决如何正确有效地实施这些功能

  • CC 评估保证级划分：

  评估保证级	定义	TCSEC安全级别（近似）
  EAL 1	功能测试（functionally tested）
  EAL 2	结构测试（structurally tested）	C1
  EAL 3	系统地测试和检查（methodically tested and checked）	C2
  EAL 4	系统地设计、测试和复查（methodically designed，tested and reviewed）	B1
  EAL 5	半形式化设计和测试（semiformally designed and tested）	B2
  EAL 6	半形式化验证的设计和测试（semiformally verified design and tested）	B3
  EAL 7	形式化验证的设计和测试（formally verified design and tested）	A1

• 数据库安全的定义：我国在《计算机信息系统安全保护等级划分准则》中对数据库安全的定义

  • 保密性：保护数据库中的数据不被泄露和未授权的获取
  • 完整性：保护数据库中的数据不被破坏和删除
  • 可用性：确保数据库中的数据不因人为的和自然的原因对授权用户不可用
  • 一致性：确保数据库中的数据满足实体完整性、参照完整性和用户定义完整性要求

2. 数据库安全性控制

• 非法使用数据库的情况：

  • 用户编写一段合法的程序绕过 DBMS 及其授权机制，通过操作系统直接存取、修改或备份数据库中的数据
  • 直接或编写应用程序执行非授权操作
  • 通过多次合法查询数据库从中推导出一些保密数据
  • 破坏安全性的行为可能是无意的，故意的，恶意的

• 数据库的安全需求：

  • 防止非法数据访问：数据库安全最关键的需求之一，仅允许授权的合法用户访问数据库
  • 数据的分级保护：依据数据敏感级别进行多级保护，严格控制对敏感数据的访问请求；
  • 防止推断性攻击：防止用户通过授权访问的低安全级数据，推导出敏感数据
  • 数据库的完整性：数据库完整性是指数据库内容的正确性、有效性和一致性；防止更改数据内容的非授权访问，以及病毒、蓄意破坏，或是系统级错误及物理故障（物理完整性）等，由 DBMS 通过访问控制以及备份、恢复机制等完成保护工作
  • 数据的操作完整性：在并行事务的模式下，保持数据的逻辑一致性，通常采用并行管理器和加锁机制完成
  • 数据的语义完整性：确保对数据在允许范围内修改，以保持数据的一致完整性
  • 审计功能：提供数据的物理完整性，并记录下对数据的所有存取访问，根据结果进行分析和追踪

• 数据库安全性控制的层次：用户标识和鉴定（应用）；存取控制、审计、视图（DBMS）；操作系统安全保护（OS）；密码存储（DB）

• 用户标识与鉴别：系统提供的最外层安全保护措施

  • 主要方法：
    • 静态口令鉴别：用户自己设定，口令静态不变
    • 动态口令鉴别：口令动态变化，一次一密
    • 生物特征鉴别：生物特征进行认证
      • 生物认证：指纹识别、人脸识别、虹膜识别、声纹识别、笔迹识别等
      • 图像哈希生物认证算法
    • 智能卡鉴别：不可复制的硬件，内置基层电路芯片，具有硬件加密功能

• 存取控制：

  • 存取控制机制的组成：用户权限定义和合法权检查机制一起组成了 DBMS 的存取控制子系统
    • 定义用户存取权限：
      • 用户对某一数据对象的操作权力，称为权限
      • DBMS 提供适当的语言来定义用户权限，存放在数据字典中，称作安全规则或授权规则
    • 合法存取权限检查：
      • 用户发出存取数据库操作请求
      • DBMS 查找数据字典，进行合法权限检查
  • 常用存取控制方法：
    • 自主存取控制（Discretionary Access Control，简称DAC）：
      • 用户对不同的数据对象有不同的存取权限，不同的用户对同一对象也有不同的权限，用户还可将其拥有的存取权限转授给其他用户
      • C2 级，灵活
    • 强制存取控制（Mandatory Access Control，简称 MAC）：
      • 每一个数据对象被标以一定的密级，每一个用户也被授予某一个级别的许可证；对任意一个对象，只有具有合法许可证的用户才可以存取
      • B1 级，严格

• 自主存取控制：

  • 通过 SQL 的 GRANT 语句和 REVOKE 语句实现

  • 用户权限组成：数据对象、操作类型

  • 定义用户存取权限：定义用户可以在哪些数据库对象上进行哪些类型的操作，定义存取权限称为授权

  • 自主存取控制的对象和权限：

    

• 授权与回收：

  • GRANT：
    • 一般格式：

      GRANT <权限>[,<权限>]...
      [ON <对象类型> <对象名>]
      TO <用户>[,<用户>]...
      [WITH GRANT OPTION];

    • 语义：将对指定操作对象的指定操作权限授予指定的用户
    • 发出 GRANT：DBA；数据库对象创建者（即属主 Owner）；拥有该权限的用户
    • 接受权限的用户：一个或多个具体用户；PUBLIC（全体用户）
    • WITH GRANT OPTION 子句：
      • 指定：可以再授予
      • 没有指定：不能传播
    • 不允许循环授权
    • 例：把查询 Student 表的权限授给用户 U1

      GRANT SELECT
      ON TABLE Student
      TO U1;

    • 例：把对 Student 表和 Course 表的全部操作权限授予用户 U2 和 U3

      GRANT ALL PRIVILIGES
      ON TABLE Student, Course
      TO U2, U3;

    • 例：把对表 SC 的查询权限授予所有用户

      GRANT SELECT
      ON TABLE SC
      TO PUBLIC;

    • 例：把查询 Student 表和修改学生学号的权限授给用户 U4

      GRANT UPDATE(Sno), SELECT
      ON TABLE Student
      TO U4;

      • 对属性列的授权时必须明确指出相应属性列名
    • 例：把对表 SC 的 INSERT 权限授予 U5 用户，并允许他再将此权限授予其他用户

      GRANT INSERT
      ON TABLE SC
      TO U5
      WITH GRANT OPTION;

  • REVOKE：
    • 一般格式：

      REVOKE <权限>[,<权限>]...
      ON <对象类型> <对象名>
      FROM <用户>[,<用户>]...;

    • 语义：授予的权限可以由 DBA 或其他授权者用 REVOKE 语句收回
    • 例：把用户 U4 修改学生学号的权限收回

      REVOKE UPDATE(Sno)
      ON TABLE Student
      FROM U4;

    • 例：收回所有用户对表 SC 的查询权限

      REVOKE SELECT
      ON TABLE SC
      FROM PUBLIC;

    • 例：把用户 U5 对 SC 表的 INSERT 权限收回

      REVOKE INSERT
      ON TABLE SC
      FROM U5 CASCADE;

      • 将用户 U5 的 INSERT 权限收回的时候必须级联（CASCADE）收回，不然系统将拒绝执行该命令
  • 小结：SQL 灵活的授权机制
    • DBA：拥有所有对象的所有权限
      • 不同的权限授予不同的用户
    • 用户：拥有自己建立的对象的全部的操作权限
      • GRANT：授予其他用户
    • 被授权的用户：
      • “继续授权”许可：再授予
    • 所有授予出去的权力在必要时又都可用 REVOKE 语句收回
  • 创建数据库模式的权限：DBA 在创建用户时实现

    • CREATE USER 语句格式：

      CREATE USER <username>
      [WITH] [DBA | RESOURCE | CONNECT]

    • 权限与可执行的操作：

      拥有的权限	CREATE USER	CREATE SCHEMA	CREATE TABLE	登陆数据库，执行数据查询和操纵
      DBA	可以	可以	可以	可以
      RESOURCE	不可以	不可以	可以	可以
      CONNECT	不可以	不可以	不可以	可以，须有相应权限

• 数据库角色：

  • 数据库角色：被命名的一组与数据库操作相关的权限
    • 角色是权限的集合
    • 可以为一组具有相同权限的用户创建一个角色
    • 简化授权的过程
  • 角色的创建：

    CREATE ROLE <角色名>

  • 给角色授权：

    GRANT <权限> [,<权限>] ...
    ON <对象类型>对象名
    TO <角色> [,<角色>] ...

  • 将一个角色授予其他的角色或用户：

    GRANT <角色1> [,<角色2>] ...
    TO <角色3> [,<用户1>] ...
    [WITH ADMIN OPTION]

  • 角色权限的收回：

    REVOKE <权限> [,<权限>] ...
    ON <对象类型> <对象名>
    FROM <角色> [,<角色>] ...

  • 例：通过角色来实现将一组权限授予一个用户，步骤如下：
    • 首先创建一个角色 R1

      CREATE ROLE R1;

    • 然后使用 GRANT 语句，使角色 R1 拥有 Student 表的 SELECT、UPDATE、INSERT 权限

      GRANT SELECT, UPDATE, INSERT
      ON TABLE Student
      TO R1;

    • 将这个角色授予王平、张明、赵玲，使他们具有角色 R1 所包含的全部权限

      GRANT R1
      TO 王平, 张明, 赵玲;

    • 可以一次性通过 R1 来回收王平的这 3 个权限

      REVOKE R1
      FROM 王平;

  • 例：角色的权限修改

    GRANT DELETE
    ON TABLE Student
    TO R1;

  • 例：角色的权限修改

    REVOKE SELECT
    ON TABLE Student
    FROM R1;

• 自主存取控制方法：

  • 检查存取权限：对于获得上机权后又进一步发出存取数据库操作的用户
    • DBMS 查找数据字典，根据其存取权限对操作的合法性进行检查
    • 若用户的操作请求超出了定义的权限，系统将拒绝执行此操作
  • 授权粒度：指可以定义的数据对象的范围
    • 它是衡量授权机制是否灵活的一个重要指标
    • 授权定义中数据对象的粒度越细，即可以定义的数据对象的范围越小，授权子系统就越灵活
    • 关系数据库中授权的数据对象粒度：数据库、表、属性列、行
  • 缺点：可能存在数据的“无意泄露”
    • 原因：这种机制仅仅通过对数据的存取权限来进行安全控制，而数据本身并无安全性标记
    • 解决：对系统控制下的所有主客体实施强制存取控制策略

• 强制存取控制方法：

  • 强制存取控制：指系统为保证更高程度的安全性，按照 TDI/TCSEC 标准中安全策略的要求，所采取的强制存取检查手段
    • MAC 不是用户能直接感知或进行控制的
    • MAC 适用于对数据有严格而固定密级分类的部门（军事部门、政府部门）
  • 主体与客体：在 MAC 中，DBMS 所管理的全部实体被分为主体和客体两大类
    • 主体：系统中的活动实体，包括：DBMS 所管理的实际用户、代表用户的各进程
    • 客体：系统中的被动实体，是受主体操纵的，包括：文件、基表、索引、视图
  • 敏感度标记：对于主体和客体，DBMS 为它们每个实例（值）指派一个敏感度标记（Label）
    • 敏感度标记分成若干级别：绝密（Top Secret，TS）、机密（Secret，S）、可信（Confidential，C）、公开（Public，P）
    • 主体的敏感度标记称为许可证级别（Clearance Level）
    • 客体的敏感度标记称为密级（Classification Level）
    • MAC 机制就是通过对比主体的 Label 和客体的 Label，最终确定主体是否能够存取客体
  • 强制存取控制规则：当某一用户（或某一主体）以标记 label 注册入系统时，系统要求他对任何客体的存取必须遵循下面两条规则：
    • 仅当主体的许可证级别大于或等于客体的密级时，该主体才能读取相应的客体
    • 仅当主体的许可证级别小于或等于客体的密级时，该主体才能写相应的客体
  • 强制存取控制的特点：
    • MAC 是对数据本身进行密级标记
    • 无论数据如何复制，标记与数据是一个不可分的整体
    • 只有符合密级标记要求的用户才可以操纵数据，从而提供了更高级别的安全性

• MAC 与 DAC：DAC 与 MAC 共同构成 DBMS 的安全机制

  • 实现 MAC 时要首先实现 DAC，原因是：较高安全性级别提供的安全保护要包含较低级别的所有保护
  • 先进行 DAC 检查，通过 DAC 检查的数据对象再由系统进行 MAC 检查，只有通过 MAC 检查的数据对象方可存取

3. 视图机制

• 视图机制：
  • 视图机制把要保密的数据对无权存取这些数据的用户隐藏起来，对数据提供一定程度的安全保护
    • 视图机制更主要的功能在于提供数据独立性，其安全保护功能太不精细，往往远不能达到应用系统的要求
  • 间接实现了支持存取谓词的用户权限定义
  • 视图机制与授权机制配合使用：先用视图机制屏蔽掉一部分保密数据，再在视图上进一步定义存取权限
  • 例：建立计算机系学生的视图，把对该视图的 SELECT 权限授于王平，把该视图上的所有操作权限授于张明
    • 先建立计算机系学生的视图 CS_Student

      CREATE VIEW CS_Student
      AS
      SELECT *
      FROM Student
      WHERE Sdept='CS';

    • 在视图上进一步定义存取权限

      GRANT SELECT
      ON CS_Student
      TO 王平;
      
      GRANT ALL PRIVILIGES
      ON CS_Student
      TO 张明;

4. 审计

• 数据库安全性控制措施：

  • 预防性措施：用户身份鉴别、自主存取控制、强制存取控制、视图
  • 监控措施：审计

• 审计：

  • 启用一个专用的审计日志（Audit Log），将用户对数据库的所有操作记录在上面
  • DBA 可以利用审计日志中的追踪信息，找出非法存取数据的人、时间和内容
  • C2 以上安全级别的 DBMS 必须具有审计功能

• 可审计事件：

  • 服务器事件：审计数据库服务器发生的事件，包括数据库服务器的启动、停止、数据库服务器配置文件的重新加载
  • 系统权限：对系统拥有的结构或模式对象进行操作的审计，要求该操作权限是通过系统权限获得
  • 语句事件：对 SQL 语句，如 DDL、DML、DQL 以及 DCL 语句的审计
  • 模式对象事件：对特定模式对象上进行的 SELECT 或 DML 操作的审计，模式对象包括表、视图、存储过程、函数等，模式对象不包括依附于表的索引、约束、触发器、分区表等

• 审计功能：

  • 基本功能，提供多种审计查阅方式：基本的、可选的、有限的等等
  • 提供多套审计规则，审计规则一般在数据库初始化时设定，方便审计员管理
  • 提供审计分析和报表功能
  • 审计日志管理功能，包括为防止审计员误删除审计记录，审计日志必须先转储后删除；对转储的审计记录文件提供完整性和保密性保护；只允许审计员查阅和转储审计记录，不允许任何用户新增和修改审计记录
  • 系统提供查询审计设置及审计记录信息的专门视图

• 审计的分类：

  • 用户级审计：
    • 针对自己创建的数据库表或视图进行审计
    • 记录所有用户对这些表或视图的一切成功和（或）不成功的访问要求，以及各种类型的 SQL 操作
  • 系统级审计：
    • DBA 设置
    • 监测成功或失败的登录要求
    • 监测 GRANT 和 REVOKE 操作以及其他数据库级权限下的操作

• 审计：

  • AUDIT 语句：设置审计功能
    • 例：对修改 SC 表结构或修改 SC 表数据的操作进行审计

      AUDIT ALTER，UPDATE
      ON SC;

  • NOAUDIT 语句：取消审计功能
    • 例：取消对 SC 表的一切审计

      NOAUDIT ALTER，UPDATE
      ON SC;

  • 审计功能的可选性：
    • 审计很费时间和空间
    • DBA 可以根据应用对安全性的要求，灵活地打开或关闭审计功能

5. 数据加密

• 数据库加密系统的要求：

  • 与通信加密相比，其信息保存时间长，不可能采用一次一密的方法进行加密
  • 实际加密后，存储空间不应明显增大
  • 加密和解密速度要快，尤其是解密速度要快，使用户感觉不到解密带来系统性能的变化
  • 对数据库的加密不应影响系统原有功能，应保持对数据库操作（如查询、检索、修改、更新）的灵活性和简便性
  • 加密后的数据库仍能允许用户以不同的粒度对之进行访问
  • 灵活的密钥管理机制，加解密密钥存储安全，使用方便可靠

• 数据库加密的实现机制：可考虑在三个不同层次实现对数据库数据的加密，这三个层次分别是 OS、DBMS 内核层和 DBMS 外层

  • OS 层加密：在 OS 层无法辨认数据库文件中的数据关系，从而无法产生合理的密钥，对密钥合理的管理和使用也很难；大型数据库很难实现在 OS 层对数据文件进行加密
  • DBMS 内核层加密：在 DBMS 内核层实现加密，是指数据在物理存/取之前完成加/脱密工作，DBMS 和加密器（硬件或软件）之间的接口需要 DBMS 开发商支持
  • DBMS 外层加密：将数据库加密系统做成 DBMS 的一个外层工具，加解密过程发生在 DBMS 之外，DBMS 管理的是密文；加解密过程可在客户端实现，也可由专门的加密服务器或硬件完成

• 数据库加密的粒度：

  • 表级加密：
    • 加密对象是数据库文件，类似于操作系统文件加密的方法
    • 数据的共享，通过用户对整个数据库文件进行解密来实现，即使用户只需要查看或修改某一记录，也需要将整个数据库文件解密，不仅增加了系统的时空开销，也无法控制用户对未授权信息的访问
  • 属性级加密：又称为“域加密”
    • 以表中的列为单位进行加密，一般来说，属性的个数少于记录的条数，而且需要的密钥数相对较少，适合于只有少数属性需要加密的场合
  • 记录级加密：
    • 一般而言，数据库系统中每条记录所包含的信息具有一定的封闭性，它独立完整存储了一个实体的数据，因此基于记录的加密技术最常用，每条记录在各自密钥作用下加密成密文信息
    • 查找记录时，可以通过将需要查找的值加密成密文后进行
    • 缺点是在解密一个记录数据时，无法实现对在这个记录中不需要的数据项不解密
  • 数据项加密：
    • 数据项加密是以记录中每个字段的值为单位进行加密，数据项是数据库中最小的加密粒度
    • 优点：系统的安全性与灵活性最高，实现技术也最为复杂，不同数据项使用不同密钥，相同明文生成不同密文，抗攻击能力得到提高
    • 缺点：需要引入大量的密钥，一般要周密设计自动生成密钥的算法，密钥管理的复杂度大大增加，系统效率受到影响

• 数据库密钥管理：一般有集中密钥管理和多级密钥管理

  • 集中密钥管理：
    • 设立密钥管理中心，负责产生密钥并对数据加密，形成一张密钥表
    • 用户访问数据库时，密钥管理机构审核用户标识和用户密钥，并找出或计算出相应的数据密钥
    • 便于用户使用和管理，但密钥一般由数据库管理人员控制，权限过于集中
  • 多级密钥管理：
    • 加密粒度为数据项的三级密钥管理体制中，整个系统使用一个主密钥 MK、每个表上的表密钥 TK 以及各个数据项上的数据密钥等三级密钥结构
    • 表密钥被主密钥加密后，以密文的形式保存在数据字典中
    • 数据元素密钥由表密钥及数据项所在行列，通过某种函数自动生成，一般不需保存
    • 在多级密钥体制中，主密钥是加密子系统的关键，多级密钥管理体制的安全性，很大程度依赖于主密钥的安全性

• 数据库加密：

  • 存储加密：一般提供透明和非透明两种存储加密方式；
    • 透明存储加密：
      • 内核级加密保护方式，对用户完全透明
      • 数据写到磁盘时对数据进行加密，授权用户读取数据时解密
      • 应用程序不需要修改，只需在创建表语句中说明需加密字段
      • 性能较好，安全完备性较高
    • 非透明存储加密：通过多个加密函数实现
  • 传输加密：帮助数据库用户和服务器之间进行安全数据交换
    • 链路加密：
      • 对传输数据在链路层加密
      • 传输信息由报头和报文两部分组成
      • 报头和报文均加密
    • 端到端加密：
      • 对传输数据在发送端加密，接收端解密
      • 只加密报文，不加密报头
      • 所需密码设备数量相对较少，但易被监听者获得敏感信息

• 数据库管理系统可信传输：

  • 步骤：
    • 第一步：创建可信连接
    • 第二步：确认通信双方端点的可靠性
    • 第三步：协商加密算法和密钥
    • 第四步：可靠传输数据
    • 第五步：关闭可信连接

• 数据库加密总结：数据加密功能通常也作为可选特征，允许用户自由选择

  • 数据加密与解密是比较费时的操作
  • 数据加密与解密程序会占用大量系统资源
  • 应该只对高度机密的数据加密

6. 其他安全性保护

• 推理控制：一种访问控制机制，处理强制存取控制未解决的问题，主要用于防止推理攻击

  • 推理攻击：是指低权限用户利用合法的查询结果，结合数据之间的逻辑或统计关系，间接推导出本无权查看的敏感信息
  • 常用方法：基于函数依赖的推理控制、基于敏感关联的推理控制
  • 统计数据库安全性：
    • 统计数据库的特点：
      • 允许用户查询聚集类型的信息（例如合计、平均值等）
      • 不允许查询单个记录信息
    • 统计数据库中特殊的安全性问题：
      • 隐蔽的信息通道
      • 从合法的查询中推导出不合法的信息
    • 规则 1：任何查询至少要涉及 $N$ ($N$ 足够大) 个以上的记录
    • 规则 2：任意两个查询的相交数据项不能超过 $M$ 个
    • 规则 3：任一用户的查询次数不能超过 $1+(N-2)/M$
    • 数据库安全机制的设计目标：试图破坏安全的人所花费的代价 $\gg$ 得到的利益

• 隐蔽信道：利用系统原本不用于通信的资源或机制，在高安全级主体与低安全级主体之间间接传输信息的通道

  • 它与传统的数据库攻击不同一一攻击者不直接查询敏感数据，而是通过观察数据库系统的内部状态变化(如锁等待时间、资源消耗、错误信息差异、执行时间等)来编码和传递敏感信息
  • 例：
    • 高权限用户(如机密级)修改某个非敏感的系统状态(如:插入一条数据、更新一行、持有锁)
    • 低权限用户(如内部级)可以观察这个状态的变化(例如:查询被阻塞的时间、发现错误代码、感知响应延迟)
    • 通过事先约定的编码方案，高低权限用户之间就能传递比特信息(0/1)，从而泄露敏感数据

第八章 数据库完整性

1. 数据库完整性概述

• 数据库的完整性：数据库的完整性（integrity）是指数据的正确性（correctness）和相容性（compatability）

  • 数据的正确性：是指数据符合现实世界语义、反映当前实际状况
  • 数据的相容性：是指数据库同一对象在不同关系表中的数据是符合逻辑的

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

  • 数据库完整性：
    • 防止数据库中存在不符合语义的数据和不正确的数据；
    • 检查和控制的防范对象：不合语义的、不正确的数据，防止它们进入数据库
  • 数据库安全性：
    • 保护数据库，防止恶意破坏和非法存取
    • 检查和控制的防范对象：非法用户和非法操作，防止他们对数据库数据的非法存取

• DBMS 的完整性控制机制：

  • 定义完整性约束条件的机制
  • 提供完整性检查的方法
  • 进行违约处理

• 完整性约束条件的定义：完整性约束条件，又称为完整性规则，是数据库中数据必须满足的语义约束条件

  • 表达了给定数据模型中数据及其联系所具有的制约和依存规则，用以限定符合数据模型的数据库状态及状态变化，保证数据的正确、有效和相容
  • DBMS 应提供定义数据库完整性约束条件的机制，包括实体完整性、参照完整性、用户定义完整性，并把它们作为模式的一部分，存入数据字典中

• 完整性检查的方法：完整性检查，是指在 DBMS 中，检查数据是否满足完整性约束条件的机制

  • 一般在 INSERT、UPDATE、DELETE 语句执行后开始检查，也可在事务提交时检查
  • 检查用户发出的操作请求，是否违背了完整性约束条件

• 违约反应：DBMS 如果发现用户的操作请求使数据违背了完整性约束条件，则采取一定的动作来保证数据的完整性

  • 例如拒绝（NO ACTION）执行该操作，或级联（CASCADE）执行其他操作，进行违约处理以保证数据的完整性

• 完整性约束条件：

  • 静态约束：对静态对象的约束是反映数据库状态合理性的约束
  • 动态约束：对动态对象的约束是反映数据库状态变迁的约束

  粒度/状态	列 级	元 组 级	关 系 级
  静 态	列定义（类型、格式、值域、空值）	元组的属性之间应满足的条件	实体完整性约束参照完整性约束函数依赖约束统计约束
  动 态	改变列定义或列值	元组新旧值之间应满足的约束条件	关系新旧状态间应满足的约束条件

• DBMS 的完整性控制机制：

  • 完整性规则五元组表示：(D，O，A，C，P)
    • D（Data）：约束作用的数据对象
    • O（Operation）：触发完整性检查的数据库操作
      • 当用户发出什么操作请求时需要检查该完整性规则，是立即检查还是延迟检查
    • A（Assertion）：数据对象必须满足的断言或语义约束，是规则的主体
    • C（Condition）：选择 A 作用的数据对象值的谓词
    • P（Procedure）：违反完整性规则时触发的过程
  • 例：在“教授工资不得低于 1000 元”的约束中
    • D（Data）：约束作用的对象为工资 Sal 属性
    • O（Operation）：插入或修改职工元组时
    • A（Assertion）：Sal 不能小于 1000
    • C（Condition）：职称=‘教授’(A 仅作用于职称=‘教授’的记录)
    • P（Procedure）：拒绝执行该操作

2. 实体完整性

• 数据库完整性：

  • 完整性定义和检查控制由关系数据库管理系统实现，不必由应用程序来完成
  • 关系数据库管理系统，使得完整性控制成为其核心支持功能，从而为所有用户和应用提供一致的数据库完整性

• 实体完整性的定义：

  • CREATE TABLE 语句中提供了 PRIMARY KEY 子句，供用户在建表时指定关系的主码列
  • 单属性构成的码有两种说明方法：定义为列级约束条件、定义为表级约束条件
  • 对多个属性构成的码只有一种说明方法：定义为表级约束条件
  • 例：在学生选课数据库中，要定义 Student 表的 Sno 属性为主码

    CREATE TABLE Student
      (Sno NUMBER(8),
      Sname VARCHAR(20) NOT NULL,
      Sage NUMBER(20),
      PRIMARY KEY (Sno)); 　/* 在表级定义主码 */

    CREATE TABLE Student
      (Sno NUMBER(8) PRIMARY KEY ,　/* 在列级定义主码 */
      Sname VARCHAR(20) NOT NULL,
      Sage NUMBER(20));

  • 例：要在 SC 表中定义 (Sno, Cno) 为主码

    CREATE TABLE SC
      (Sno NUMBER(8) NOT NULL,
      Cno NUMBER(2) NOT NULL,
      Grade NUMBER(2),
      PRIMARY KEY (Sno, Cno)　/* 只能在表级定义主码 */
      FOREIGN KEY (Sno) REFERENCES Student(Sno) /* 在表级定义参照完整性 */
      FOREIGN KEY (Cno) REFERENCES Course(Cno) /* 在表级定义参照完整性 */
      );

• 实体完整性检查和违约处理：

  • 用户程序对主码列进行更新操作时，系统自动进行实体完整性检查
  • 实体完整性检查：
    • 检查主码值是否唯一，否则拒绝插入或修改
    • 检查主码的各个属性是否为空，否则拒绝插入或修改
  • 违约反应：系统拒绝此操作，从而保证了实体完整性
  • 检查记录中主码值是否唯一的方法是进行全表扫描
    • 依次判断表中每一条记录的主码值与将插入记录上的主码值（或者修改的新主码值）是否相同
    • 全表扫描十分耗时，可以使用 B+ 树索引

3. 参照完整性

• 参照完整性的定义：

  • 定义参照完整性：
    • FOREIGN KEY 子句：定义外码列
    • REFERENCES 子句：外码相应于哪个表的主码
    • 级联（CASCADE）操作：在删除或修改被参照关系的元组时，同时删除或修改参照关系所有导致不一致的元组
  • 例：建立表 SC

    CREATE TABLE SC
      (Sno CHAR(9)　NOT NULL,
      Cno CHAR(4) NOT NULL,
      Grade SMALLINT,
      PRIMARY KEY (Sno, Cno), /* 表级定义实体完整性 */ FOREIGN KEY (Sno) REFERENCES Student(Sno) /* 在表级定义参照完整性 */
      FOREIGN KEY (Cno) REFERENCES Course(Cno) /* 在表级定义参照完整性 */
      );

• 参照完整性检查和违约处理：

  • 一个参照完整性将两个表中的相应元组联系起来
  • 对被参照表和参照表进行增删改操作时有可能破坏参照完整性，必须进行检查
    • 在参照关系中插入元组
    • 在参照关系中修改外码值
    • 在被参照关系中删除元组
    • 在被参照关系中修改主码
  • 违约处理：
    • 拒绝 (NO ACTION)：不允许该操作执行（默认策略）
    • 级联 (CASCADE)：当删除或修改被参照表的一个元组导致与参照表不一致时，删除或修改参照表中所有导致不一致的元组
    • 设置为空值 (SET NULL)：当删除或修改被参照表的一个元组导致与参照表不一致时，将参照表中所有造成不一致的元组的对应属性设置为空值
      • 外码是否可以接受空值的问题：依赖于应用环境的语义（系统提供定义外码的机制，定义外码列是否允许空值的机制）
  • 例：建立表 SC

    CREATE TABLE SC
      (Sno CHAR(9)　NOT NULL,
      Cno CHAR(4) NOT NULL,
      Grade SMALLINT,
      PRIMARY KEY (Sno, Cno), /*表级定义实体完整性，Sno、Con 都不能取空值 */ 
      FOREIGN KEY (Sno) REFERENCES Student(Sno) /* 在表级定义参照完整性 */
        ON DELETE CASCADE 　 /* 删除 Student 元组时，级联删除 SC 中相应元组 */
        ON UPDATE CASCADE, 　/* 更新 Student 表中 Sno 时，级联更新 SC 中相应元组 */
      FOREIGN KEY (Cno) REFERENCES Course(Cno) /* 在表级定义参照完整性 */
        ON DELETE NO ACTION /* 删除 Course 元组造成与 SC 表不一致时，拒绝删除 */
        ON UPDATE CASCADE, 　 /* 更新 Course 表中 Cno 时，级联更新 SC 中相应元组 */
      );

4. 用户定义的完整性

• 用户定义的完整性：针对某一具体应用的数据必须满足的语义要求

  • 用户定义的完整性的两类方法：
    • 用 CREATE TABLE 语句在建表时定义用户完整性约束
    • 通过触发器来定义用户的完整性规则

• 属性上的约束条件：用 CREATE TABLE 语句在建表时定义用户完整性约束，可定义三类属性上的完整性约束：

  • 列值非空（NOT NULL 短语）：
    • 例：建立表 SC，说明 Sno、Con、Grade 属性不允许取空值

      CREATE TABLE SC
        (Sno CHAR(9)　NOT NULL,　/* Sno 属性不允许取空值 */
        Cno CHAR(4) NOT NULL,　/* Cno 属性不允许取空值 */
        Grade SMALLINT NOT NULL,　/* Grade 属性不允许取空值 */
        PRIMARY KEY (Sno, Cno), /* 表级定义实体完整性 */ FOREIGN KEY (Sno) REFERENCES Student(Sno) /* 在表级定义参照完整性 */
        FOREIGN KEY (Cno) REFERENCES Course(Cno) /* 在表级定义参照完整性 */
        );

  • 列值唯一（UNIQUE 短语）：
    • 例：建立部门表 DEPT，要求部门名称 Dname 列取值唯一，部门编号 Deptno 列为主码

      CREATE TABLE DEPT 
        (Deptno NUMERIC(2), 　　 
        Dname CHAR(9) UNIQUE NOT NULL, /* 要求 Dname 列值唯一，且不能取空值 */ 　　 
        Loc VARCHAR(10), 　　 
        PRIMARY KEY (Deptno)
        );

  • 检查列值是否满足一个条件表达式（CHECK 短语）：
    • 例： 建立学生登记表 Student，要求年龄 <29，性别只能是‘男’或‘女’，姓名非空

      CREATE TABLE Student 　　 
        (Sno NUMBER(5) PRIMARY KEY, 　/* 在列级定义主码 */
        Sname CHAR(20) NOT NULL,　/* Sname 属性不允许取空值 */
        Sage SMALLINT CHECK (Sage < 29),　/* Sage属性小于 29 */
        Ssex CHAR(2) CHECK (Ssex IN (‘男’,‘女’)) /* Ssex 属性只允许取‘男’或‘女’ */
        );

    • 例：建立表SC，Grade的值在 0 和 100 之间

      CREATE TABLE SC
        (Sno CHAR(9),　　　　　　　　　
        Cno CHAR(4),　　　　　　　　　　
        Grade SMALLINT CHECK(Grade>=0 AND Grade <=100),　/* Grade取值范围 0-100 */
        PRIMARY KEY (Sno, Cno), 　
        FOREIGN KEY (Sno) REFERENCES Student(Sno),
        FOREIGN KEY (Cno) REFERENCES Course(Cno));

• 元组上的约束条件：

  • 用 CREATE TABLE 语句在建表时定义用户完整性约束，可定义元组上的完整性约束
    • 设置不同属性之间取值的相互约束条件（CHECK 短语）
  • 例：当学生的性别是男时，其名字不能以 Ms. 打头

    CREATE TABLE Student
      (Sno CHAR(9), 
      Sname CHAR(20) NOT NULL， /* Sname 非空值 */
      Ssex CHAR(2),
      Sage SMALLINT，
      Sdept CHAR(20),
      PRIMARY KEY (Sno),
      CHECK (Ssex=‘女’OR Sname NOT LIKE‘MS.%’)
      );

• 完整性小结：

  • 提供定义完整性约束条件
    • CREATE TABLE 语句
    • CREATE TRIGGER 语句
    • 可以定义很复杂的完整性约束条件
  • 自动执行相应的完整性检查：
    • 对于违反完整性约束条件的操作：拒绝执行或者执行事先定义的操作

5. 完整性约束命名子句

• 完整性约束命名子句：

  • SQL 在 CREATE TABLE 语句中提供了 CONSTRAINT 子句，用来对完整性约束条件命名
    • 可以灵活增加、删除一个完整性约束条件
  • 完整性约束命名子句：CONSTRAINT <完整性约束条件名> <完整性约束条件>
    • <完整性约束条件> 包括 NOT NULL、UNIQUE、PRIMARY KEY、FOREIGN KEY、CHECK 短语等
  • 例：建立学生登记表 Student，要求学号在 90000～99999 之间，年龄 < 30，性别只能是‘男’或‘女’，姓名非空

    CREATE TABLE Student
      (Sno NUMERIC(6)
        CONSTRAINT C1 CHECK (Sno BETWEEN 90000 AND 99999),
      Sname CHAR(20) 
        CONSTRAINT C2 NOT NULL,
      Sage NUMERIC(3) 
        CONSTRAINT C3 CHECK (Sage < 30),
      Ssex CHAR(2)
        CONSTRAINT C4 CHECK (Ssex IN ('男', '女')),
        CONSTRAINT StudentKey PRIMARY KEY(Sno));

  • 例：建立职工表 EMP，要求每个职工的应发工资不低于 3000 元，应发工资实际上就是实发工资列 Sal 与扣除项 Deduct 之和

    CREATE TABLE EMP
      (Eno NUMERIC(4) PRIMARY KEY, /* 在列级定义主码 */
      Ename CHAR(10),
      Job CHAR(8),
      Sal NUMERIC(7,2),
      Deduct NUMERIC(7,2)
      Deptno NUMERIC(2),
      CONSTRAINT TeacherKey FOREIGN KEY (Deptno) REFERENCES DEPT(Deptno),
      CONSTRAINT C1 CHECK (Sal + Deduct >=3000));

• 修改表中的完整性限制：SQL 提供了 ALTER TABLE 子句，用来修改表中的完整性限制

  • 例：去掉 Student 表中对性别的限制

    ALTER TABLE Student
    DROP CONSTRAINT C4;

  • 例：修改 Student 表中的约束条件，要求学号改为 900000～999999之间，年龄由小于 30 改为小于 40

    ALTER TABLE Student
      DROP CONSTRAINT C1;
    ALTER TABLE Student
      ADD CONSTRAINT C1 CHECK(Sno BETWEEN 900000 AND 999999);
    ALTER TABLE Student
      DROP CONSTRAINT C3;
    ALTER TABLE Student
      ADD CONSTRAINT C3 CHECK(Sage < 40);

6. 断言

• 创建断言的语句格式：

  • SQL 提供了 CREATE ASSERTION 语句，通过声明性断言(declarative assertions) 来指定更具一般性的约束
    • 可以定义涉及多个表或聚集操作比较复杂的完整性约束
    • 断言创建后，任何对断言中所涉及关系的操作都会触发 RDBMS 对断言的检查，任何使断言不为真值的操作都会被拒绝执行
  • 一般格式：CREATE ASSERTION <断言名> <CHECK 子句>
    • 每个断言都被赋予一个名字，<CHECK 子句> 中的约束条件与 WHERE 子句的条件表达式类似
  • 例：限制数据库课程最多 60 名学生选修

    CREATE ASSERTION ASSE_SC_DB_NUM
      CHECK (60 >= (SELECT count (*) /* 此断言的谓词涉及聚集操作count*/
        FROM Course, SC
        WHERE SC.CNO=COURSE.CNO AND COURSE.CNAME =‘数据库’));

  • 例：限制每一门课程最多 60 名学生选修

    CREATE ASSERTION ASSE_SC_CNUM1
      CHECK (60 >= ALL(SELECT count (*) /* 此断言的谓词涉及聚集操作 count */
        FROM SC /* 和分组函数group by 的 SQL 语句 */
        GROUP by Cno));

  • 例：限制每个学期每一门课程最多 60 名学生选修
    • 首先修改 SC 表的模式,增加一个‘学期(TERM)’的属性

      ALTER TABLE SC /* 先修改SC表，增加 TERM 属性，类型是DATE*/ 
        ADD TERM DATE;

    • 然后定义断言

      CREATE ASSERTION ASSE_SC_CNUM2
        CHECK (60 >= ALL(SELECT count (*) /* 此断言的谓词涉及聚集操作count*/
          FROM SC /* 和分组函数group by的 SQL 语句*/
          GROUP by Cno, TERM));

• 删除断言的语句格式：

  • 一般格式：DROP ASSERTION <断言名>
  • 如果断言很复杂，系统在检测和维护断言上开销很高

7. 触发器

• 触发器：

  • 触发器（trigger）是用户定义在关系表上的一类由事件驱动的特殊过程
  • 通过触发器来定义用户的完整性规则：
    • 定义其它的完整性约束时，需要用数据库触发器（Trigger）来实现
    • 一旦由某个用户定义，触发器将被保存在数据库服务器中
    • 任何用户对该数据的增、删、改操作均由服务器自动激活相应的触发器，在 DBMS 核心层进行集中的完整性控制
    • 触发器类似于约束，但比约束更灵活，可以实施更为复杂的检查和操作，具有更精细和更强大的数据控制能力

• 定义触发器：触发器又叫做事件-条件-动作（event-condition-action）规则

  • SQL 使用 CREATE TRIGGER 命令建立触发器
  • 一般格式：

    CREATE TRIGGER <触发器名> /* 每当触发事件发生时，该触发器被激活 */
    {BEFORE | AFTER} <触发事件> ON <表名> 　/* 指明触发器激活时间是在执行触发事件前或后 */
    REFERENCING NEW | OLD ROW AS <变量> 　/* REFERENCING 指出引用的变量 */
    FOR EACH {ROW | STATEMENT} 　/* 定义触发器的类型，指明动作体执行的频率 */
    [WHEN <触发条件>] <触发动作> 　/* 仅当触发条件为真时，才执行触发动作体 */

    • 创建触发器：
      • 只有表的拥有者，即创建表的用户，才可以在表上创建触发器
      • 一个表上只能创建一定数量的触发器
    • 触发器名：
      • 触发器名可以包含模式名，也可以不包含模式名；
      • 同一模式下，触发器名必须是唯一的，而且触发器名和表名必须在同一模式下
    • 表名：
      • 触发器只能定义在基本表上，不能定义在视图上
      • 基本表数据发生变化，将激活触发器，该表称为触发器的目标表
    • 触发事件：
      • 触发事件可以是 INSERT、DELETE、UPDATE
      • 也可以是几个事件的组合，如 INSERT OR DELETE，或UPDATE OF <触发列,…>，进一步指明修改哪些列时激活触发器
      • AFTER/BEFORE 是触发时机，AFTER 表示在触发事件的操作执行后激活触发器，BEFORE 表示在触发事件的操作执行之前激活触发器
    • 触发器类型：
      • 触发器按照所触发动作的间隔尺寸可分为行级触发器（FOR EACH ROW）和语句触发器（FOR EACH STATEMENT）；
      • 默认的触发器是语句级触发器
    • 触发条件：
      • 触发器被激活时，只有当触发条件为真时，触发动作体才执行，否则触发动作体不执行
      • 如果省略 WHEN 触发条件，则触发动作体在触发器激活后立即执行
    • 触发动作体：
      • 触发动作体即可以是一个匿名 PL/SQL（Procedural Language/SQL，过程化 SQL 语言）过程块，也可以是对已创建存储过程的调用
      • 如果是行级触发器，用户可在过程体中使用 NEW 和 OLD 引用 UPDATE/INSERT 事件之后的新值和 UPDATE/DELETE 事件之前的旧值
      • 如果是语句级触发器，则不能在触发动作体中使用 NEW 或 OLD 进行引用
  • 例：当对表 SC 的 Grade 属性进行修改时，若分数增加了 10%，则将此次操作记录到另一个表 SC_U (Sno、Cno、Oldgrade、Newgrade) 中，其中 Oldgrade 是修改前的分数，Newgrade 是修改后的分数

    CREATE TRIGGER SC_T /* SC_T 是触发器的名字 */
    AFTER UPDATE OF Grade ON SC 　　/* UPDATE OF Grade ON SC 是触发事件 */
      /* AFTER 是触发的时机，表示当对 SC 的 Grade 属性修改完后再触发下面的规则 */
    REFERENCING 　　　
      OLDROW AS OldTuple
      NEWROW AS NewTuple
    FOR EACH ROW /* 行级触发器，每执行一次 Grade 更新，下面的规则就执行一次 */
    WHEN (NewTuple.Grade>=1.1*OldTuple.Grade) /* 触发条件，只有该条件为真时才执行 */
    BEGIN
      INSERT INTO SC_U (Sno, Cno, OldGrade, NewGrade) /* 下面的 insert 操作 */
      VALUES(OldTuple.Sno, OldTuple.Cno, OldTuple.Grade, NewTuple.Grade)
    END

  • 例：将每次对表 Student 的插入操作所增加的学生个数记录到表 StudentInsertLog 中

    CREATE TRIGGER Student_Count /* Student_Count 是触发器的名字 */
    AFTER INSERT ON Student /* 指明触发器激活的时间是在执行 INSERT 之后*/
    REFERENCING 　　　
      NEW TABLE AS DELTA
    FOR EACH STATEMENT
      /* 语句级触发器，即执行完 INSERT 语句后下面的触发动作体才执行一次*/
    BEGIN
      INSERT INTO StudentInsertLog (Numbers)
      SELECT COUNT(*) FROM DELTA
    END

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

    CREATE TRIGGER Insert_OR_Update_Sal /* 对教师表插入或更新时激活触发器 */
    BEFORE INSERT OR UPDATE ON Teacher /* BEFORE 触发事件 */
    REFERENCING
      NEW row AS newtuple
    FOR EACH ROW /* 行级触发器 */
    BEGIN /* 定义触发动作，这是一个 PL/SQL 过程块 */
      IF (newtuple.Job = ‘教授’ AND (newtuple.Sal < 4000))
        THEN newtuple.Sal = 4000;
        /* 因为是行级触发器，可在过程体使用插入或更新操作后的新值 */
      END IF;
    END; /* 触发动作体结束 */

• 执行触发器：

  • 触发器的执行是由触发事件激活,并由数据库服务器自动执行
  • 一个数据表上可能定义了多个触发器，如多个 BEFORE、AFTER 触发器
  • 同一个表上的多个触发器激活时遵循如下执行顺序：
    • 执行该表上的 BEFORE 触发器
    • 激活触发器的 SQL 语句
    • 执行该表上的 AFTER 触发器
  • 同一个表上的多个 BEFORE(AFTER) 触发器，遵循“谁先创建谁先执行”的原则，即按触发器创建的时间先后顺序执行

• 删除触发器：

  • 一般格式：DROP TRIGGER <触发器> ON <表名>;
  • 触发器必须是一个已经创建的触发器，只能由具有相应权限的用户删除

• 数据库完整性小结：

  • 完整性机制的实施会极大地影响系统性能；
  • 不同的数据库产品对完整性的支持策略和支持程度是不同的
    • 许多数据库管理系统对完整性机制的支持比对安全性的支持要晚得多
      也弱得多
    • 数据库厂商对完整性的支持越来越好，不仅在能保证实体完整性和参照完整性，而且能在 DBMS 核心定义、检查和保证用户定义的完整性约束条件

第九章 数据库存储管理

1. 数据组织

• 数据组织：
  • 以最优的形式在外存上组织、存放庞大数据集
    • 存储效率高，节省存储空间
    • 存取效率高，访问速度快，代价小

1.1 数据库的逻辑组织方式与物理组织方式

• 数据存储的管理方式：

  • 方式一：每个 DB 对象（基本表、索引）对应一个操作系统文件
    • 例如，PostgreSQL、Kingbase ES
  • 方式二：整个 DB 对应一个或若干个文件（段页式存储）
    • 例如，Oracle、SQL Server

• 数据库的逻辑组织：表空间 – 段 – 分区 – 数据块，方便数据管理

  

  • 表空间（Tablespace）：磁盘上的一个或多个物理文件，一个物理文件只能属于一个表空间；一个数据库可以有多个表空间，从逻辑上组织数据库的数据存储
    • 例如，系统表空间、联机表空间、临时表空间
  • 数据段（Segment）：一个表空间逻辑上由多个段组成，每个段可以逻辑上组织不同类型的数据
    • 例如，数据段、索引段、临时段
  • 分区（Extent）：一个段逻辑上由多个分区组成，每个分区由一组连续数据块组成
  • 数据块（Block）：数据库的磁盘存取单元，大小为操作系统块的整数倍

• 数据库的物理组织：文件 – 块 – 记录

  • 文件：操作系统文件
  • 块：每个文件物理上分成定长的存储单元，即操作系统的物理块；存储分配和 I/O 的基本单位
  • 记录：物理块中存放的多条元组

• 逻辑组织与物理组织的对应关系：

  

1.2 记录表示

• 元组存储：

  • 形式一：定长记录存储
  • 形式二：变长记录存储

• 定长记录存储：

  • 关系表中的每条记录占据相同大小的空间
  • 变长字段以定长形式存储，预留最大长度空间
  • 有些硬件系统对内存数据的起始地址有要求（4 或 8 的倍数）
  • 优势：快速定位到记录及其属性的物理位置；增删改比较方便快捷
  • 劣势：浪费存储空间

• 变长记录存储：

  • 存储要求：
    • 能快速访问一条记录
    • 能快速访问记录中所有属性（包括定长和变长属性）
  • 三种存放方式：
    • 方式一：
      • 在每条记录的头部记录该条记录的长度
      • 在记录的每个变长字段前记录该字段的长度
    • 方式二：
      • 先存放定长字段，再存放变长字段
      • 第一个变长字段紧随定长字段，从第二个变长字段开始，在记录首部用指针（偏移量）指向变长字段
    • 方式三：
      • 将定长字段与变长字段分开存储在不同的块中
      • 多用于 BLOB（Binary Large Object）等类型数据存储
      • 若经常访问定长字段，可减少数据存取时的 I/O 数量

1.3 块的组织

• 定长记录存储的块组织：

  • 块组织：
    • 表中元组依次存放在块中
    • 首部+记录+空闲空间
    • 首部：块头信息、块 ID、最后一次修改和访问该块的时间戳、每条记录在块内的偏移量、空闲空间头指针
  • 块维护：
    • 增：在空闲空间直接插入新元组
    • 改：直接在原位置修改
    • 删：回收空间，将空闲空间加入空闲空间链表，不需要移动

• 变长记录存储的块组织：

  • 块组织：
    • 表中元组从块的尾部连续存放
    • 首部+空闲空间+记录
    • 首部：各记录的指针（块内偏移量）、空闲空间尾指针（块内偏移量）
  • 块维护：
    • 增：从空闲空间尾部分配空间；在偏移量表中记录该元组的起始位置；调整空闲空间尾指针
    • 删：在偏移量表中为该元组指针置删除标记；释放元组空间，移动物理位置在其前面的元组（保证空闲空间连续）；修改被移动元组在偏移量表中的指针；修改空闲空间尾指针
    • 改：在原位置修改；若修改后记录在原位置放不下，会带来记录的迁移

1.4 关系表的组织

• 关系表的存放方式：

  • 堆存储
  • 顺序存储
  • 多表聚簇存储
  • B+ 树存储
  • 哈希存储

• 堆存储：

  • 表中的一条记录可以存放在该表的任何块中，没有顺序要求
  • 插入元组时，在该表的块中找到合适的空闲空间即可
  • 如果没有足够的空闲空间，就为该表申请新的块

• 顺序存储：

  • 一个表中的各条记录根据指定的属性或属性组的取值大小顺序的存放
  • 同一个表的不同块之间通过指针链接实现有序
  • 优势：可以高效地处理按排序属性（组）进行查询的请求
  • 劣势：维护代价较高（在增改时需要移动已有的记录以保序）

• 多表聚簇存储：

  • 不同表的元组聚簇存放在同一组块中，减少连接操作
  • 优势：可以减少连接操作带来的开销，快速回答某些查询
  • 劣势：
    • 降低某些查询的查询效率（同一表中的元组会分散在更多块中）
    • 在更新操作时会带来更频繁的数据迁移

• B+ 树存储：

  • 以 B+ 树索引的方式确定记录存放在哪个数据块中
  • 保持较高的访问效率的同时，降低数据维护开销

• 哈希存储：

  • 用哈希函数计算表中指定属性的哈希值，以此确定相应记录放在哪个块中
    • 哈希表：由 B 个哈希桶（bucket）组成，每个桶编号 0 到 B-1，对应一个或多个物理块，存放一条或多条记录
    • 哈希函数：输入为记录的哈希属性，输出为介于 0 到 B-1 之间的整数，对应哈希桶号
  • 将记录的存储位置与其指定属性的哈希值之间建立一个对应关系，查找记录时可快速定位这条记录

2. 索引结构

• 索引：类似图书目录的附加结构，提高查询处理效率
  • 优势：
    • 表的索引块数量通常比数据块数量少得多
    • 可以用高效的方法快速查找索引块
    • 若索引文件足够小，可长期驻留内存缓冲区，减少 I/O 操作
  • 劣势：索引会带来额外的开销
    • 存储索引开销
    • 建立索引开销
    • 维护索引开销

2.1 顺序表索引

• 顺序表索引：在顺序表的排序属性（组）上建立索引，也称作主索引（Primary Index）或聚簇索引（Clustering Index）

  • 稠密索引
  • 稀疏索引
  • 多级索引

• 稠密索引（Dense Index）：索引块中存放每条记录的索引属性值以及指向相应记录的指针

  • 有序索引，索引较大时，可利用二分查找法在稠密索引查找指定索引项
  • 利用索引查询可减少 I/O

• 稀疏索引（Sparse Index）：基本表的每个物理存储块只对应一个索引项，每个索引项存放每个物理块的第一条记录的索引属性值及指向该物理块的指针

  • 尺寸小于稠密索引
  • 索引维护代价较小：对基本表进行增删改时，只要不是存储块第一条记录的索引属性，稀疏索引就不需要维护

• 多多级索引（Multilevel Index）：解决索引尺寸大问题

  • 索引建立：
    • 第一级索引是稠密或稀疏索引
    • 第二级及以上为建立在上一级索引上的稀疏索引
    • 重复直到尺寸合适
  • 利用多级索引查找：从高级索引逐层向下，直到定位到记录所在的物理块

2.2 辅助索引

• 辅助索引（Secondary Index）：建立在表的非排序属性上的索引
  • 一个表最多只能建立一个主索引，但可以在不同属性上建立多个辅助索引
  • 辅助索引必须是稠密索引
  • 辅助索引的属性往往会取重复值，去掉可减小索引大小与查找开销
  • 引入指针桶去除重复索引项：索引项指针 $\to$ 指针桶相应位置 $\to$ 相应的元组
  • 当在关系表上建立了多个辅助索引时，可以利用指针桶回答涉及多个属性的查询

2.3 B+ 树索引

• 稠密索引与稀疏索引的问题：随着数据量增大

  • 索引本身庞大，查找效率不能令人满意
  • 按同一属性的不同值查找，时间效率可能相差大
  • 为保持索引项和元组有序，维护代价高

• 多级索引：

  • 缓解前两个问题
  • 加剧索引维护代价

• B+ 树索引：

  • 解决大型索引的组织和维护
  • 查找效率高、按不同值查找性能平衡、易于维护等

• B+ 树索引的结构：本质上是一个多级索引，将索引块组织成一棵平衡树，从树根到树叶的所有路径一样长

  • B+ 树的三类结点：根结点（只有一个）、中间结点、叶结点
  • B+ 树的秩（order）：一个索引块最多能存放的指针的个数，对于一棵秩为 $n$ 的 B+ 树索引：
    • 每个结点最多包含 $n-1$ 个属性值 key
    • 除了根结点外，每个结点最少包含 $\lceil (n−1)/2 \rceil$ 个属性值 key（根结点最少含有一项）
    • 含有 $j-1$ 项的非叶结点，有 $j$ 个指针，分别指向其 $j$ 个孩子（叶结点除外，它没有孩子）
    • 所有的叶结点都在同一级上；含有 $j-1$ 项的叶结点，有 $j$ 个指针，前 $j-1$ 个指针指向相应的关系表元组，第 $j$ 个指针指向兄弟叶结点
  • B+ 树索引的典型结点：
    • 包含了 $n−1$ 个属性值 $K_1, K_2, \dots, K_{n−1}$
    • $n$ 个指针 $P_1, P_2, \dots, P_{n}$
    • 结点中的属性值按序存放，如果 $i<j$，则 $K_i < K_j$
  • B+ 树索引的叶结点：
  • 指针 $P_i$ 指向关系表中属性值为 $K_i$ 的元组$(i = 1, 2, \dots, n-1)$
  • 指针 $P_n$ 指向其兄弟叶结点，最后一个叶结点的 $P_n$ 为空
  • B+ 树索引的非叶结点：
    • $P_i$ 指向其下层的孩子结点 $(i = 1, 2, \dots, n)$
    • $P_1$ 指向的子树，其所有属性值 Key 均满足 $\mathrm{Key} < K_1$
    • $P_i (i = 1, 2, \dots, n)$ 指向的子树，其所有属性值 Key 均满足 $K_{i-1} \le \mathrm{Key} < K_i$
    • $P_n$ 指向的子树，其所有属性值 Key 均满足 $\mathrm{Key} \ge K_{n-1}$

• B+ 树索引的查询：高效地完成随机查找和范围查询

  • 随机查找：按照索引属性的取值进行查找
    • 从根结点开始
    • 沿父子结点指针逐层向下搜索
    • 直到叶结点（匹配则返回结果，否则没有满足条件的元组）
  • 范围查找：between … and …
    • 用随机查找的方法分别找到范围条件的入口点和结束点
    • 对入口点和结束点之间的属性值进行顺序搜索

• B+ 树索引的维护：

  • 插入元组：
    • 叶结点有空闲空间（Key 值个数小于 $n-1$）
      • 直接插入
    • 叶结点达到最大充满度（key 值个数等于 $n-1$）
      • 当前叶结点分裂成 2 个叶结点
      • 父结点插入
      • 维护父结点
      • 逐层向上，直到插入完成（若根结点分裂会导致树的高度增加一层）
  • 删除元组：
    • 用随机搜索算法找到要删除的索引项
    • 删除后叶结点仍能满足最小充满度（Key 值个数大于 $\lceil (n−1)/2 \rceil$）
      • 直接删除
    • 删除后叶结点不能满足最小充满度（Key 值个数小于等于 $\lceil (n−1)/2 \rceil$）
      • 删除当前索引项
      • 合并叶结点
      • 删除父结点索引项
      • 维护父结点
      • 逐层向上，直到删除完成（若合并传递至根结点会导致树的高度降低一层）

2.4 哈希索引

• 两个关键要素：

  • 哈希表：$B$ 个哈希桶
  • 哈希函数：
    • 将记录的索引属性值影射到哈希桶
    • 每个桶存放放一条或多条哈希值相同的索引项
    • 每个索引项包括属性值和指向相应记录的指针

• 静态哈希索引：

  • 哈希函数的设计原则：尽量保证函数的取值随机和均匀；不会出现某个桶的索引项远远超过其他桶
  • 哈希表的构成：
    • 由一组桶组成，一个桶对应一个或多个物理块
    • 桶中存放被映射到该桶的哈希索引项
    • 每条索引项包括索引属性值和指向相应记录的指针
  • 桶溢出：某个桶的存储空间不足
    • 三类主要原因：
      • 哈希桶数量不足，不能存放所有的索引项
      • 属性存在偏斜，某些属性值过多
      • 哈希函数设计不合理，无法将索引均匀地映射到每个桶，导致某个桶的数据过多
    • 减少桶溢出的措施：
      • 预留一定百分比的空间：溢出仍不可避免
      • 分配溢出桶：当溢出桶空间充满时，追加新的溢出桶；用溢出链将一个桶及其溢出桶链接在一起
  • 哈希索引的查找：擅长做等值查找
    • 根据属性值计算出哈希函数值，得到桶号
    • 到相应的桶中搜索相应的索引项
    • 若桶中没有找到，但存在溢出桶，继续搜索溢出桶
  • 哈希索引的维护：
    • 插入元组时，需向哈希索引中插入相应的索引项
      • 哈希函数计算桶号：若桶中有空间，直接插入；若桶中空间已满，申请溢出桶并插入
    • 删除元组时，需删除相应的索引项
      • 哈希函数计算桶号：若没有溢出块，直接删除；若有溢出块，判断是否有空间合并溢出块

• 动态哈希索引：

  • 静态哈希索引的问题：桶的个数事先确定且不再改变
    • 桶溢出不可避免，影响查找效率
    • 两种解决方法：
      • 适当预留桶空间：表数据量难以估算
      • 随着关系表的增大，周期性地增加哈希桶数目，并重组索引：耗时，影响正在进行的查询
  • 动态哈希索引：随着关系表的增大，逐渐扩大桶的数目
    • 两类动态哈希索引：可扩展哈希索引、线性哈希索引

2.5 位图索引

• 位图索引：

  • 长度为 $n$ 的位向量集合，其中 $n$ 是索引属性的基数（可能取值的个数），每一个位向量对应于索引属性的一个可能的取值
  • 如果第 $i$ 条记录的索引属性值为 $v$，那么对应于值 $v$ 的位向量在位置 $i$ 上取值为 $1$，其他的位向量在位置 $i$ 上取值为 $0$

• 位图索引的优劣：

  • 优势：有效处理多值查询
    • 使用位操作来快速回答用户查询或快速定位满足条件的元组集合，减少对基本表的全表扫描，提高查询效率
  • 劣势：
    • 位图索引的大小与列的基数成正比，基数大的列其位图索引会非常庞大，因此它只适用于基数小的属性列

• 编码位图索引（Encoded Bitmap Index）：

  • 改进标准位图索引：通过对属性值编码，减少索引位向量的个数，从而能够应对有较高基数的列
  • 优势：减少索引位个数
    • 如果索引属性列的基数为 $K$，标准位图索引所需要的位向量个数为 $K$ 个，而编码位图索引所需要的位向量个数仅为 $\log_2 K$ 个
  • 劣势：查询时需要访问所有位向量才能完成

第十章 查询处理和优化

1. RDBMS 的查询处理

1.1 查询处理步骤

• 查询处理阶段：查询分析、查询检查、查询优化、查询执行

• 查询分析：

  • 查询分析的任务：对查询语句进行扫描、词法分析和语法分析
  • 词法分析：从查询语句中识别出正确的语言符号
  • 语法分析：进行语法检查，判断查询语句是否符合 SQL 语法规则

• 查询检查：

  • 查询检查的任务：语义检查和分析、安全性检查、完整性初步检查
  • 根据数据字典中有关的模式定义检查语句中的数据库对象，如关系名、属性名是否存在和有效
  • 如果是对视图的操作，则要用视图消解方法把对视图的操作转换成对基本表的操作
  • 根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查
  • 检查通过后把 SQL 查询语句转换成内部表示，即等价的关系代数表达式
  • 关系数据库管理系统一般都用语法树来表示扩展的关系代数表达式

• 查询优化：选择一个高效执行的查询处理策略

  • 查询优化分类：
    • 代数优化：指关系代数表达式的优化
    • 物理优化：指存取路径和底层操作算法的选择
  • 查询优化的选择依据：
    • 基于规则(rule based)
    • 基于代价(cost based)
    • 基于语义(semantic based)

• 查询执行：

  • 依据优化器得到的执行策略生成查询执行计划
  • 代码生成器(code generator) 生成执行查询计划的代码

1.2 实现查询操作的算法

• 选择操作典型实现方法：

  • 全表扫描算法（full table scan）：
    • 对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出
    • 适合小表，不适合大表
  • 索引扫描算法（index scan）：
    • 适合于选择条件中的属性上有索引（例如 B+ 树索引或 Hash 索引）
    • 通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组

• 连接操作的实现：连接操作是查询处理中最耗时的操作之一；本节只讨论等值连接(或自然连接)最常用的实现算法

  • 嵌套循环算法(nested loop join)：
    • 由两层循环组成，其基本思想：对外层循环(Student 表)的每一个元组(s)，检索内层循环(SC 表)中的每一个元组(sc)
    • 检查这两个元组在连接属性(Sno)上是否相等
    • 如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止
  • 排序-合并算法(sort-merge join 或 merge join)：
    • 步骤：
      • 如果连接的表没有排好序，先对 Student 表和 SC 表按连接属性 Sno 排序
      • 将排好序的 Student 表和 SC 表中的数据块读到内存中
      • 依次扫描 SC 表中与 Student 表具有相同 Sno 值的元组，把它们连接起来
      • 当扫描到 Sno 不相同的第一个 SC 元组时，返回 Student 表扫描它的下一个元组，再扫描 SC 表中具有相同 Sno 的元组，把它们连接起来
      • 在内存中的 Student 表或 SC 表扫描完后，继续将相应表余下的数据块读入内存，重复前两步，直到 Student 表或 SC 表全部扫描完
    • Student 表和 SC 表都只要扫描一遍
    • 如果两个表原来无序，执行时间要加上对两个表的排序时间
    • 对于大表，即使加上排序后使用排序-合并连接算法的总执行时间一般仍会减少
  • 索引连接算法(index join)：
    • 在 SC 表上建立属性 Sno 的索引，若已有 Sno 上的索引，则跳过该步骤
    • 对 Student 中每一个元组，由 Sno 值通过 SC 的索引查找相应的 SC 元组
    • 把这些 SC 元组和 Student 元组连接起来
    • 循环执行前两步，直到 Student 表中的元组处理完为止
  • 哈希连接算法 (hash join)：
    • 把连接属性作为 hash 码，用同一个 hash 函数把 Student 表和 SC 表中的元组散列到 hash 表中
    • 划分阶段(building phase)：
      • 对包含较少元组的表(如 Student 表)进行一遍处理
      • 把它的元组按 hash 函数分散到 hash 表的桶中
    • 试探阶段(probing phase)：
      • 对另一个表(SC 表)进行一遍处理
      • 把 SC 表的元组也按同一个 hash 函数（hash 码是连接属性）进行散列，映射到相应的 Student 表哈希桶
      • 把 SC 元组与桶中来自 Student 表并与之相匹配的元组连接起来
    • 前提：假设两个表中较小的表在第一阶段后可以完全放入内存的 hash 桶中

2. RDBMS 的查询优化

• 关系数据库系统的查询优化：
  • 查询优化在关系数据库系统中有着非常重要的地位
  • 关系查询优化是影响关系数据库管理系统性能的主要因素
  • 由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性

2.1 查询优化概述

• 关系系统的查询优化：

  • 关系数据库管理系统实现的关键技术
  • 关系系统的优点所在
  • 减轻了用户选择存取路径的负担

• 非关系系统：

  • 用户使用过程化的语言表达查询要求，执行何种记录级的操作，以及操作的序列是由用户来决定的
  • 用户必须了解存取路径，系统要提供用户选择存取路径的手段，查询效率由用户的存取策略决定
  • 如果用户做了不当的选择，系统是无法对此加以改进的

• 查询优化的优点：

  • 用户不必考虑如何最好地表达查询以获得较好的效率
  • 系统可以比用户程序的“优化”做得更好
    • 优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息
    • 如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划；在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的
    • 优化器可以考虑成百上千种不同的执行计划，程序员一般只能考虑有限的几种可能性
    • 优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握；系统的自动优化相当于使得所有人都拥有这些优化技术

• 查询代价：关系数据库管理系统通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案

  • 集中式数据库：
    • 执行开销主要包括：磁盘存取块数(I/O 代价)、处理机时间(CPU 代价)、查询的内存开销
    • I/O 代价是最主要的
  • 分布式数据库：
    • 总代价 = I/O 代价 + CPU 代价 + 内存代价 + 通信代价

• 查询优化的总目标：

  • 选择有效的策略
  • 求得给定关系表达式的值
  • 尽量降低查询代价

3. 代数优化

3.1 关系代数表达式等价变换规则

• 关系代数表达式等价变换规则：

  • 代数优化策略：通过对关系代数表达式的等价变换来提高查询效率
  • 关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的
    • 两个关系表达式 $E_1$ 和 $E_2$ 是等价的，可记为 $E_1 \equiv E_2$

• 常用的等价变换规则：

  • 1. 连接运算、笛卡儿积运算交换律：设 $E_1$ 和 $E_2$ 是关系代数表达式，$F$ 是连接运算的条件，则有

    $$\begin{aligned} & E_1 \times E_2 \equiv E_2 \times E_1 \\ & E_1 \bowtie E_2 \equiv E_2 \bowtie E_1 \\ & E_1 \underset{F}{\bowtie} E_2 \equiv E_2 \underset{F}{\bowtie} E_1 \end{aligned}$$

  • 2. 连接运算、笛卡儿积运算的结合律：设 $E_1, E_2, E_3$ 是关系代数表达式，$F_1$ 和 $F_2$ 是连接运算的条件

    $$\begin{aligned} & \left(E_1 \times E_2\right) \times E_3 \equiv E_1 \times\left(E_2 \times E_3\right) \\ & \left(E_1 \bowtie E_2\right) \bowtie E_3 \equiv E_1 \bowtie\left(E_2 \bowtie E_3\right) \\ & (E_1 \underset{F_1}{\bowtie} E_2) \underset{F_2}{\bowtie} E_3 \equiv E_1 \underset{F_1}{\bowtie} (E_2 \underset{F_2}{\bowtie} E_3) \end{aligned}$$

  • 3. 投影运算的串接律：

    $$\pi_{A_1, A_2, \cdots A_n}\left(\pi_{B_1, B_2, \cdots B_m}(E)\right) \equiv \pi_{A_1, A_2, \cdots A_n}(E)$$

    • $E$ 是关系代数表达式
    • $A_i (i=1,2,\dots,n)$，$B_j (j=1,2,\dots,m)$ 是属性名
    • $\{A_1,A_2,\dots,A_n\}$ 是 $\{B_1,B_2,\dots,B_m\}$ 的子集
  • 4. 选择运算的串接律：

    $$\sigma_{F_1}\left(\sigma_{F_2}(E)\right) \equiv \sigma_{F_1 \wedge F_2} (E)$$

    • $E$ 是关系代数表达式，$F_1$、$F_2$ 是选择条件
    • 选择的串接律说明选择条件可以合并，这样一次就可检查全部条件
  • 5. 选择运算与投影运算的交换律：

    $$\sigma_{F}\left(\pi_{A_1, A_2, \cdots A_n}(E)\right) \equiv \pi_{A_1, A_2, \cdots A_n}\left(\sigma_{F}(E)\right)$$

    • 选择条件 $F$ 只涉及属性 $A_1, \dots, A_n$
    • 若 $F$ 中有不属于 $A_1, \dots, A_n$ 的属性 $B_1, \dots, B_m$ 有更一般规则

      $$\pi_{A_1, A_2, \cdots A_n}\left(\sigma_{F}(E)\right) \equiv \pi_{A_1, A_2, \cdots A_n}\left(\sigma_{F}\left(\pi_{A_1, A_2, \cdots A_n, B_1, B_2, \cdots B_m}(E)\right)\right)$$

  • 6. 选择运算与笛卡儿积运算的交换律：
    • 如果 $F$ 中涉及的属性都是 $E_1$ 中的属性，则

      $$\sigma_F\left(E_1 \times E_2\right) \equiv \sigma_F\left(E_1\right) \times E_2$$

    • 如果 $F=F_1 \land F_2$，并且 $F_1$ 只涉及 $E_1$ 中的属性，$F_2$ 只涉及 $E_2$ 中的属性，则由上面的等价变换规则可推出

      $$\sigma_{F}\left(E_1 \times E_2\right) \equiv \sigma_{F_1}\left(E_1\right) \times \sigma_{F_2}\left(E_2\right)$$

    • 若 $F_1$ 只涉及 $E_1$ 中的属性，$F_2$ 涉及 $E_1$ 和 $E_2$ 两者的属性，则仍有

      $$\sigma_{F}\left(E_1 \times E_2\right) \equiv \sigma_{F_2}\left(\sigma_{F_1}\left(E_1\right) \times E_2\right)$$

      它使部分选择在笛卡儿积前先做
  • 7. 选择与并的分配律：设 $E_1, E_2$ 有相同的属性名，则

    $$\sigma_F\left(E_1 \cup E_2\right) \equiv \sigma_F\left(E_1\right) \cup \sigma_F\left(E_2\right)$$

  • 8. 选择与差运算的分配律：若 $E_1$ 与 $E_2$ 有相同的属性名，则

    $$\sigma_F\left(E_1-E_2\right) \equiv \sigma_F\left(E_1\right)-\sigma_F\left(E_2\right)$$

  • 9. 选择对自然连接的分配：

    $$\sigma_{\mathrm{F}}\left(E_1 \bowtie E_2\right) \equiv \sigma_{\mathrm{F}}\left(E_1\right) \bowtie \sigma_{\mathrm{F}}(E)$$

    • $F$ 只涉及 $E_1$ 与 $E_2$ 的公共属性
  • 10. 投影运算与笛卡儿积运算的分配律：设 $E_1$ 和 $E_2$ 是两个关系表达式，$A_1, \ldots, A_n$ 是 $E_1$ 的属性，$B_1, \ldots, B_m$ 是 $E_2$ 的属性，则

    $$\pi_{A_1, A_2, \cdots A_n, B_1, B_2, \cdots B_m}\left(E_1 \times E_2\right) \equiv \pi_{A_1, A_2, \cdots A_n}\left(E_1\right) \times \pi_{B_1, B_2, \cdots B_m}\left(E_2\right)$$

  • 11. 投影运算与并运算的分配律：设 $E_1$ 和 $E_2$ 有相同的属性名，则

    $$\pi_{A_1, A_2, \cdots A_n}\left(E_1 \cup E_2\right) \equiv \pi_{A_1, A_2, \cdots A_n}\left(E_1\right) \cup \pi_{A_1, A_2, \cdots A_n}\left(E_2\right)$$

3.2 语法树的启发式优化

• 典型的启发式规则：

  • 选择运算应尽可能先做：在优化策略中这是最重要、最基本的一条
  • 把投影运算和选择运算同时进行：如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系
  • 把投影同其前或其后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系
  • 把某些选择同在它前面要执行的笛卡儿积结合起来成为一个连接运算，连接特别是等值连接运算要比同样关系上的笛卡儿积省很多时间
  • 找出公共子表达式：如果这种重复出现的子表达式的结果不是很大的关系，并且从外存中读入这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算的
    • 当查询的是视图时，定义视图的表达式就是一种公共子表达式

• 语法树的启发式优化：

  • 算法：关系表达式的优化
  • 输入：一个关系表达式的查询树
  • 输出：优化的查询树
  • 方法：
    • 利用等价变换规则 4 把形如 $\sigma_{F_1 \wedge F_2 \wedge \ldots \wedge F_n}(E)$ 变换为

      $$\sigma_{F_1}\left(\sigma_{F_2}\left(\ldots\left(\sigma_{F_ n}(E)\right) \ldots\right)\right)$$

    • 对每一个选择，利用等价变换规则 4 ~ 9 尽可能把它移到树的叶端
    • 对每一个投影利用等价变换规则 3，5，10，11 中的一般形式尽可能把它移向树的叶端
      • 等价变换规则 3 使一些投影消失或使一些投影出现
      • 规则 5 把一个投影分裂为两个，其中一个有可能被移向树的叶端
    • 利用等价变换规则 3 ~ 5，把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影，使多个选择或投影能同时执行，或在一次扫描中全部完成
    • 把经过上述变换得到的语法树的内节点分组
      • 每一双目运算($\times, \bowtie, \cup, -$) 和它所有的直接祖先为一组，这些直接祖先是($\sigma, \pi$ 运算)
      • 如果其后代直到叶子全是单目运算，则也将它们并入该组
      • 但当双目运算是笛卡儿积($\times$)，而且后面不是与它组成等值连接的选择时，则不能把选择与这个双目运算组成同一组
  • 例：下面给出 SQL 语句的代数优化示例

    SELECT  Student.Sname
    FROM    Student, SC
    WHERE   Student.Sno=SC.Sno AND
            SC.Cno='81003'

    • 把 SQL 语句转换成查询树

      

    • 为了使用关系代数表达式的优化法，假设内部表示是关系代数语法树

      

    • 对语法树进行优化，利用规则 4、6 把选择 $\sigma_\text{SC.Cno=‘81003’}$ 移到叶端

      

4. 物理优化

• 物理优化：

  • 代数优化改变查询语句中操作的次序和组合，不涉及底层存取路径
  • 对于一个查询语句有许多存取方案，它们的执行效率不同，仅仅进行代数优化是不够的
  • 物理优化就是要选择高效合理的操作算法或存取路径，求得优化查询计划

• 物理优化方法：

  • 基于启发式规则的启发式优化：启发式规则是指那些在大多数情况下都适用，但不是在每种情况下都是适用的规则
  • 基于代价估算的优化：优化器估算不同执行策略的代价，并选出具有最小代价的执行计划
  • 两者结合的优化方法：常常先使用启发式规则，选取若干较优的候选方案，减少代价估算的工作量；然后分别计算这些候选方案的执行代价，较快地选出最终的优化方案

• 基于启发式规则的存取路径选择优化：

  • 选择操作的启发式规则：对于小关系，使用全表顺序扫描，即使选择列上有索引；对于大关系，启发式规则有：
    • 对于选择条件是“主码＝值”的查询
      • 查询结果最多是一个元组，可以选择主码索引扫描
      • 一般的关系数据库管理系统会自动建立主码索引
    • 对于选择条件是“非主属性＝值”的查询，并且选择列上有索引
      • 要估算查询结果的元组数目
      • 如果比例较小(<10%)，可以使用索引扫描方法
      • 否则还是使用全表顺序扫描
    • 对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引
      • 要估算查询结果的元组数目
      • 如果比例较小(<10%)可以使用索引扫描方法
      • 否则还是使用全表顺序扫描
    • 对于用 AND 连接的合取选择条件
      • 如果有涉及这些属性的组合索引
        • 优先采用组合索引扫描方法
      • 如果某些属性上有单属性索引，可以用索引扫描方法
        • 通过分别查找满足每个条件的指针，求指针的交集
        • 通过索引查找满足部分条件的元组，然后在扫描这些元组时判断是否满足剩余条件
      • 其他情况：使用全表顺序扫描
    • 对于用 OR 连接的析取选择条件，一般使用全表顺序扫描
  • 连接操作的启发式规则：
    • 如果两个表都已经按照连接属性排序
      • 选用排序-合并算法
    • 如果一个表在连接属性上有索引
      • 选用索引连接算法
    • 如果上面2个规则都不适用，其中一个表较小
      • 选用哈希连接算法
    • 可以选用嵌套循环方法，并选择其中较小的表，即占用的块数(B)较少的表，作为外表(外循环的表)
    • 设连接表 R 与 S 占用的块数分别为 Br 与 Bs；连接操作使用的内存缓冲区块数为 K，分配K-1块给外表；如果 R 为外表，则嵌套循环法存取的块数为 Br+BrBs/(K-1)；显然应该选块数小的表作为外表

• 基于代价的优化：

  • 启发式规则优化是定性的选择，适合解释执行的系统
    • 解释执行的系统，优化开销包含在查询总开销之中
  • 编译执行的系统中查询优化和查询执行是分开的
    • 可以采用精细复杂一些的基于代价的优化方法
  • 统计信息：基于代价的优化方法要计算查询的各种不同执行方案的执行代价，它与数据库的状态密切相关，为此在数据字典中存储了优化器需要的数据库统计信息（database statistics information），优化器需要的统计信息
    • 对每个基本表：该表的元组总数(N)、元组长度(l)、占用的块数(B)、占用的溢出块数(BO)
    • 对基表的每个列：该列不同值的个数(m)、列最大值、最小值、列上是否已经建立了索引、哪种索引(B+ 树索引、Hash 索引、聚集索引)、可以计算选择率(f)：如果不同值的分布是均匀的，f＝1/m；如果不同值的分布不均匀，则要计算每个值的选择率，f＝具有该值的元组数/N
    • 对索引：索引的层数(L)、不同索引值的个数、索引的选择基数 S(有 S 个元组具有某个索引值)、索引的叶结点数(Y)
  • 代价估算示例：
    • 全表扫描算法的代价估算公式：
      • 如果基本表大小为 B 块，全表扫描算法的代价 cost＝B
      • 如果选择条件是“码＝值”，那么平均搜索代价 cost＝B/2
    • 索引扫描算法的代价估算公式：
      • 如果选择条件是“码＝值”：采用该表的主索引，若为 B+ 树，层数为 L，需要存取 B+ 树中从根结点到叶结点 L 块，再加上基本表中该元组所在的那一块，所以 cost=L+1
      • 如果选择条件涉及非码属性：若为 B+ 树索引，选择条件是相等比较，N/m 是索引的选择基数(有 N/m 个元组满足条件)，满足条件的元组可能会保存在不同的块上，所以(最坏的情况) cost=L+ N/m
      • 如果比较条件是＞，＞＝，＜，＜＝操作：假设有一半的元组满足条件，就要存取一半的叶结点，通过索引访问一半的表存储块 cost=L+Y/2+B/2；如果可以获得更准确的选择基数，可以进一步修正 Y/2 与 B/2
    • 嵌套循环连接算法的代价估算公式：
      • 嵌套循环连接算法的代价：cost＝Br+BrBs/(K-1)
      • 如果需要把连接结果写回磁盘：cost＝Br+Br Bs/(K-1)+(FrsNrNs)/Mrs，其中 Frs 为连接选择性(join selectivity)，表示连接结果元组数的比例；Mrs 是存放连接结果的块因子，表示每块中可以存放的结果元组数目
    • 排序-合并连接算法的代价估算公式：
      • 如果连接表已经按照连接属性排好序：cost＝Br+Bs+(FrsNrNs)/Mrs
      • 如果必须对文件排序，还需要在代价函数中加上排序的代价，对于包含 B 个块的文件排序的代价大约是 4B

5. 查询计划的执行

• 自顶向下：

  • 系统反复向查询计划顶端的操作符发出需要查询结果元组的请求，操作符收到请求后，就试图计算下一个（几个）元组并返回这些元组
  • 在计算时，如果操作符的输入缓冲区为空，它就会向其孩子操作符发送需求元组的请求
  • 这种需求元组的请求一直传到叶子节点，启动叶子操作符运行，并返回其父操作符一个（几个）元组
  • 父操作符再计算自己的输入返回给上层操作符，直至顶端操作符
  • 重复这一过程，直到处理完整个关系

• 自底向上：

  • 查询计划从叶子节点开始执行，叶节点操作符不断地产生元组并将它们放入其输出缓冲区中，直到缓冲区填满为止，这时它必须等待其父操作符将元组从该缓冲区取走才能继续执行
  • 然后其父节点操作符开始执行，利用下层的输入元组来产生它自己的输出元组，直到输出缓冲区满为止
  • 这个过程不断重复，直到产生所有的输出元组

• 查询计划的执行：

  • 自顶向下的执行方式是一种被动的、需求驱动的执行方式
  • 自底向上的执行方式是一种主动的执行方式

第十一章 数据库恢复技术

1. 事务的基本概念

• 数据库恢复概述：
  • 故障是不可避免的：计算机硬件故障、系统软件和应用软件的错误、操作员的失误、恶意的破坏
  • 故障的影响：运行事务非正常中断（影响数据正确性）、破坏数据库（数据丢失）
  • 数据库管理系统对故障的对策：
    • DBMS 提供恢复子系统
    • 保证故障发生后，能把数据库从错误状态恢复到某种逻辑一致的状态（某一已知的正确状态）
    • 保证事务 ACID；
  • 恢复技术是衡量系统性能优劣的重要指标

1.1 什么是事务

• 事务(Transaction)：用户定义的一个数据库操作序列，这些操作要么全做，要么全不做，是一个不可分割的工作单位
  • 事务和程序是两个概念：在关系数据库中，一个事务可以是一条 SQL 语句，一组 SQL 语句或整个程序；一个应用程序通常包含多个事务
  • 事务是恢复和并发控制的基本单位

1.2 如何定义事务

• 定义事务：

  • 显式定义方式：

    BEGIN TRANSACTION
    SQL 语句1
    SQL 语句2
    ...
    COMMIT （提交）

    BEGIN TRANSACTION
    SQL 语句1
    SQL 语句2
    ...
    ROLLBACK （回滚）

  • 隐式方式：当用户没有显式地定义事务时，DBMS 按缺省规定自动划分事务

• 事务结束：

  • COMMIT (提交)：
    • 提交事务的所有操作（读+更新），事务正常结束
    • 将事务中所有对数据库的更新写回到磁盘上的物理数据库中
    • 事务中所有对数据库的更新永久生效
  • ROLLBACK (回滚)：
    • 事务异常终止，事务运行的过程中发生了某种故障，不能继续执行
    • 系统将事务中对数据库的所有已完成操作全部撤销，事务滚回到开始时的状态

参考资料

本文参考上海交通大学《数据库技术》课程 CS3321 郭捷老师的 PPT 课件整理。