数据库系统引论

数据管理系统的发展

数据管理：对数据分类、组织、编码、存储、检索、维护

发展：人工管理、文件系统、数据库系统

• 40-50年代 人工管理 数据不保存，没有专门软件管理数据，应用程序完全依赖于数据，数据不能共享
• 50年代末-60年代中 文件系统阶段 硬件有磁盘磁鼓，数据可以长期保存，数据面向应用，数据冗余度大，缺乏统一控制
• 60年代末 数据库系统阶段 有大容量磁盘和数据库管理系统
  • 1968 IBM研究世界上第一个商品化数据库管理系统IMS
  • 1969 网状数据模型报告DBTG
  • 1970 关系模型的论文提出
  • 主要特征：数据结构化；独立性高：独立性体现在物理独立性和逻辑独立性，通过数据库系统所提供的二级映像的实现；减少数据冗余：数据面向系统，集中管理；数据共享；统一的数据保护功能

数据库

• 存放数据的仓库。
• 存放在介质上的相关数据的集合
• 长期存储在计算机内、有组织的、可共享的大量数据集合
• 数据库是长期存储在计算机内，有组织的数据集合，根据数据间的联系组织在一起，具有较高的数据独立性，减少数据冗余，能够为各种用户共享。

数据库管理系统

数据库需要一个软件系统统一管理，这个软件系统是数据库管理系统（DBMS）

• 统一管理数据库的软件系统
• 位于用户与操作系统之间的一层数据管理软件
• 赋值数据库的管理和维护，具有数据定义、数据操纵、运行管理和维护等功能
• 是数据库系统的核心

其功能有

• 定义功能。包括模式定义、外模式定义、内模式定义。
• 操纵功能。
• 保护功能。包括安全性、完整性、并发控制、恢复。
• 维护功能。包括转储、数据装入、统计、存储等。

DBMS提供数据定义语言（DDL），定义数据库的数据结构，包括模式定义语言、外模式定义语言和内模式定义语言。

DBMS一般提供一种或两种DDL

数据定义语言描述的模式成为源模式，需要借助编译程序翻译成机器代码形式的目标模式，供DBMS使用。

数据模型

模型方法是一种抽象表示，把表示事物的主要特征抽象的用一种形式化的描述反映。数据模型是将事物之间的联系，转化为数据和数据间的联系。

数据模型是****，包含三个要素：

• 数据结构，对数据静态特征的描述
• 数据操作，对数据动态特性的描述
• 数据的完整性约束，数据间的制约和依存关系

概念模型不涉及信息在计算机的表示，面向用户，只要用户需求不变，概念模型也不变。狭义的数据模型是按照计算机系统的观点建模，又包含两个部分

• 逻辑数据模型：用户看到的数据模型，用于数据库设计，如E-R模型
• 物理数据模型：数据存储结构和存取方法，用于DBMS实现，包括网状模型、层次模型、关系模型等等

数据模型是对数据最底层的抽象。

数据结构是最重要的部分，不同数据模型由数据结构来表征。

数据库系统结构

数据库系统中，用户可以逻辑地、抽象地处理数据，而不必考虑数据在计算机中如何组织、存放。

数据库系统结构是一个多级结构，方便用户存取数据，同时高效地组织数据，以最佳形式在物理存储器存放。

特点：

• 数据结构化

• 数据的共享性高，冗余度低且容易扩充

• 数据独立性高(

  物理独立性：应用程序与物理存储相互独立，数据的物理存储改变，应用程序不改变；

  逻辑独立性：应用程序与逻辑结构相互独立，数据的逻辑结构改变，应用程序不改变。)

数据库系统分成三个层次，称为三级结构：

• 模式，Schema，也叫（逻辑模式）， 是全体数据的逻辑结构和特征的描述
• 外模式（子模式、用户模式），SubSchema，是数据库用户能看见的最终表示。外模式是模式的子集，一个数据库可以有多个外模式，不同用户有不同外模式。外模式与应用也是一对多的关系。外模式是保护数据库安全的措施，用户只能看见或访问外模式的数据。
• 内模式（存储模型），也称存储模式，是数据物理结构和存储方式的描述，一个数据库只有一个内模式。

总的来说，三级模式是对数据的视图级、概念级、物理级的抽象级别。

三级模式之中有两级映像。这种映像目的是数据库内部实现三个抽象层级的联系和转化。

• 外模式与模式之间的映像，定义局部数据逻辑结构和全局逻辑结构的对应关系。当模式结构改变，只需要修改外模式与模式的对应关系，不必修改外模式的局部逻辑结构，实现数据逻辑独立性；

• 模式与内模式之间的映像，定义全局数据逻辑结构和物理数据存储间的对应关系。当物理存储结构改变的时候，仅需要修改模式与内模式间的影响关系，而使模式保持不变，实现数据的物理独立性。

数据库系统的不同使用者

其人员分成四类：数据库管理员、系统分析员、应用程序员、用户。

不同人员设计数据抽象级别不同。

• 数据库管理员，决定数据库存储结构和策略
• 系统分析员，涉及需求分析
• 设计人员，确定数据库的数据和各级模式
• 应用程序有，编码实现
• 用户，使用系统

数据库技术的发展

• 第一代60年代末研制的层次、网状数据库系统
• 第二代关系数据库系统，现在仍占据主流
• 围绕面向对象数据模型的研究，OODBMS

数据模型

数据模型是对现实世界数据信息的抽象和表示，分成概念模型和数据模型，对应用户观点的数据模型和狭义的物理存储上的数据模型。

本章主要介绍概念模型和逻辑数据模型，核心是E-R概念模型。对四种逻辑模型只做简单介绍，在第三章重点介绍关系模型。

数据模型的组成要素：

• 数据结构：描述系统的静态特性 → 描述数据库的组成对象以及对象之间的联系
• 数据操作：描述系统的动态特性 → 是对数据库中的各种对象的实例所允许的操作的集合，其类型有查询和更新（增删改查）
• 数据完整性约束：用以限定数据模型的数据库状态以及状态的变化，以保证数据的正确、有效与相容，完整性约束条件是一组完整性规则的集合。

E-R概念模型

概念模型是对信息世界的建模，是数据库设计的有力工具。它需要较强的语义表达能力，简单清晰、易于理解。

一、E-R模型中的基本概念

实体：客观存在并可相互区别的事物实体可以是具体对象，比如一个学生，一本书；也可以是抽象的概念或联系，比如一堂课。

属性：实体所具有的某一特征。一个实体可以由若干属性刻画，有类型和值的区分。类型是属性名，值是属性的具体内容。

联系：在现实世界中，事物内部以及事物之间是有联系的。在信息世界中，常被抽象为实体内部的联系和实体之间的联系。内部的联系是组成实体各属性的联系；之间的联系是不同实体集之间的联系。

实体之间的联系最简单的是两个实体之间的联系：

一对一联系：A中的一个实体至多与B的一个实体相对应

一对多联系：A中的一个实体与B中的多个实体相对应，反之B的一个实体至多与A的一个实体相对应

多对多联系：A、B中一个实体与另一个实体集多个实体联系

多个实体间也可以存在联系，称为 多元联系。例如

这样的联系称为m:n:p。

两两之间多对多的联系和三个实体的多对多的联系，语义有何不同呢？

两两之间的多对多仅能表示一个工程需要哪些零件、由哪些供应商提供。

但是多对多联系可以描述一个工程所用的零件具体由哪个供应商供应。

实体集内部不同实体间的联系也存在一对一、一对多、多对多。比如，一个领导领导多个职工。

二、E-R模型

E-R（Entity-Relationship Approach）是最著名的概念模型，用矩形表示实体，椭圆表示属性，菱形框表示联系。

联系有比较多的语义

• 基数比约束，比如二元联系中1：1、1：n的联系
• 参与约束，根据实体是否全部参与联系描述
• 实体参与度，实体参与联系的最小和最大的次数
• 弱实体，实体存在依赖于其它实体存在
• 子类实体，根据不同特性分成多个子集

一个物资管理需求如下

最后，得到

用关系模型来表示学校

层次模型

层次模型是数据库系统最早出现的数据模型，用树形结构表示各类实体和实体间联系。

层次模型满足两个条件：

• 有且只有一个节点没有双亲结点，为根节点；
• 根以外节点有且只有一个双亲结点。

比如下面一个层次：

其特点是，数据结构简单清晰，查询效率高，提供了良好的数据完整性支持。

但这种模型不能表示两个以上实体间复杂联系和实体间多对多联系，只能通过引入冗余数据或虚拟节点来解决。对数据插入和删除涉及树的操作，所以工作量比较大，查询子女节点需要通过双亲结点。由于结构严密，层次命令趋于程序化。

网状模型

现实世界的联系很多的非层次的，所以用层次模型表达有非直观性。网状模型满足下面的条件：允许一个以上节点无双亲，一个节点可以有多于一个双亲。

网状模型能更直接的描述现实世界，如一个节点可以有多个双亲；同时它性能尚可。但是，它结构非常复杂，不利于用户掌握；DDL、DML语言复杂，不容易使用。

关系模型

1970年，E.F.Codd提出了关系数据模型，1977年出现了第一个关系数据库，而80年代依赖关系数据就占据主流。

（1）基本概念和结构

关系是一张二维表，一个关系描述一个实体集。实体有属性，二维表的列就是属性。一个属性对应的一个集合是域。

关系是元组的集合，一个元组对应实体集中的一个个体。一个元组由若干分量组成，一个分量对应一个属性值。

键是一个或多个属性构成的，能够唯一标识一个元组。一个关系中可能有多组属性都能起到标识元组的作用，所以一个关系可能有多个键。选择其中一个作为主键，其余为候选键。

（2）关系模式

对关系结构的描述称为关系模式。关系模式可表示为：

关系名(属性1,属性2,...,属性n)

（3）ER模式向关系数据模式的映射

关系数据模型中，基本的数据结构是关系。现实世界中，实体和实体间的联系都用关系表示。

联系可以用表来描述。比如，选课联系 -> 选课表。表中有来自学生和课程两个实体的属性，成绩是选课关联自身的描述属性。

关系必须是规范化的，关系的每一个分量必须不可分。也就是，不能存在表中表。

（4）完整性约束

关系数据需要有实体完整性、参照完整性、用户自定义完整性。

（5）数据操纵

允许进行增删改查。

这种关系运算都可以归结为关系代数和关系演算两类。

总的来说，关系数据模型可以表示为下表：

关系模型有下面的优点

• 数据结构简单
• 一体化数据子语言
• 数据独立性高
• 面向集合的存取方式
• 坚实的理论基础
• 有利于开展其他应用

面向对象数据模型

对象关系数据系统是面向对象数据模型和关系数据模型相结合的产物。一般来说，面向对象有两条路线，一条是建立新的数据库系统，另一种是走结合路径。

但缺乏通用数据模型、理论基础、查询优化，导致面向对象数据库理论技术没有成熟，关系数据库仍处于统治地位。

关系数据库

主要讨论基本概念和各种运算。

按照静态数据结构、动态数据操作、完整性约束来介绍。

关系模型基本概念

一、基本概念

域是一组具有相同数据类型的值的集合。

笛卡尔积：给定一组集合$D_1,D_2,\cdots D_n$，那么笛卡尔积$D_1\times D_2\cdots D_n$就是所有域的所有组合。

笛卡尔积的每个元素叫做一个元组$(d_1,d_2,\cdots ,d_n)$，每一个值$d_i$叫做一个分量。

$D_1\times \cdots \times D_n$上任一个子集称为$D_1,\cdots ,D_n$上一个关系，$N$叫做关系的目或度。关系的每一行对应一个元组，用$t$表示，每一列对应一个域，列称为属性，$t[A_i]$表示$t$在$A_i$上的值。

按照定义，关系可以是一个无限集合。并且，笛卡尔积不满足交换律。但是无限的集合在数据库中是无意义的，所以 关系是规范化的二维表中行的集合 ，关系必须是有限集合。

规范化关系有如下性质：

• 列是同质的，每一列的分量来自同一个域
• 不同列可出自一个域，每一列称为一个属性，不同属性给予不同属性名
• 列的顺序无所谓，次序可以交换
• 各个元组是不同的，不允许出现重复元组。（因为实体不能相同）
• 行的次序可以任意交换
• 分量必须为原子值，每一个分量都是不可分的数据项

二、关系模式和关系数据库

关系模式是对关系的描述。该描述包括关系名、属性名、属性的类型和长度、属性间固有的数据关联关系，记为R(A₁,A₂,…,A_n)。

关系模式的集合是关系数据库模式，是对所有数据逻辑结构的描述，表示为R={R1,R2,…,Rp}。

三、键

为了区分不同元组，用一个或多个属性值标识，能够唯一标识元组属性或属性组称为关系的键。其标识作用的键是候选键，多个候选键其中之一为主键。如果关系的键由多个属性组成，则称为联合键。关系所有属性构成关系的键，称为全键。

四、完整性约束

为了保证数据域一致性，需要

• 实体完整性，一般自动支持

  • 主键的值不能为空或部分为空。
  • 实体完整性是针对基本关系而言的，基本表对应现实世界一个实体集。现实世界实体和实体是可区分的，而关系模型中主键是唯一性标识。主键的属性不能取空值。

• 参照完整性，一般自动支持

  • 如果$R_1$中A是$R_2$的主键，那么R₁中让你一个元组在A上的值或者为空，或者为R₂中某个元组主键的值。

  • 比如学生和专业信息，二者是参照关系和被参照关系。学生的专业信息要么是空，要么是专业信息中的某个数据项。这个时候，其取值局限在专业代码中。

  • 这个时候，外键参考主键信息。

    

    比如这个图中，班长的取值一定是学号之中。

• 用户定义完整性，用户定义后系统支持

  • 用户定义完整性是针对某一具体关系数据库的约束条件。比如，成绩不能为负数、性别的输入条件。
  • 也叫做预定义完整性。

关系代数

一、关系代数概述

关系代数是抽象的查询语言，用对关系的运算表达查询。

它有三个要素：

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

按照运算符不同，关系代数分成两类：传统的集合运算和专门的关系运算。

二、集合运算

（1）并

假如R、S有相同的目，属性取自同一域，那么
KaTeX parse error: Undefined control sequence: \or at position 24: …S = \{t|r\in R \̲o̲r̲ ̲t \in S\}

（2）差

假如R、S有相同的目，属性取自同一域，那么
KaTeX parse error: Undefined control sequence: \and at position 22: … \{t | t \in R \̲a̲n̲d̲ ̲t \not \in S\}
所以差可以代表删除。

（3）交

假如R、S有相同的目，属性取自同一域，那么
KaTeX parse error: Undefined control sequence: \and at position 26: … \{t | t \in R \̲a̲n̲d̲ ̲t \in S\}
（4）笛卡尔积

R是n目关系，有k₁个元组，S是m目关系，有k₂个元组，那么
KaTeX parse error: Undefined control sequence: \and at position 36: …_s | t_r \in R \̲a̲n̲d̲ ̲t_s \in S\}

三、关系运算

先引入记号

$R$ 表示关系，$t$表示元组，$t[A_i]$表示分量，$t[A]$表示诸分量的集合，$\overline{A}$表示 { A 1 ⋯ A n } \{A_1\cdots A_n\} {A1​⋯An​}去掉 { A i 1 ⋯ A i n } \{A_{i1}\cdots A_{in}\} {Ai1​⋯Ain​}的属性组，$t_r{t}_s$表示元组连接

（1）选择
σ F ( R ) = { t ∣ t ∈ R ∧ t ( F ) } \sigma_F(R) = \{t|t\in R \land t(F)\} σF​(R)={t∣t∈R∧t(F)}
其中$F$是布尔表达式，其含义是选$t(F)$为真的所有元组，从行的角度进行运算。

（2）投影
Π x ( R ) { t [ X ] ∣ t ∈ R } \Pi_x(R)\{t[X]|t\in R\} Πx​(R){t[X]∣t∈R}
从列的角度运算，选出若干属性列组成新的关系

（3）连接

条件连接和自然连接

条件连接：
R ⋈ A θ B S = { t ∣ t = t r t s , t r ∈ R ∧ t s ∈ S ∧ t r [ A ] θ t s [ B ] } R\underset{A \theta B}{\large \Join}S = \{t|t=t_rt_s, t_r\in R \land t_s \in S \land t_r[A]\ \ \theta\ \ t_s[B]\} RAθB⋈​S={t∣t=tr​ts​,tr​∈R∧ts​∈S∧tr​[A]  θ  ts​[B]}
$\theta$为条件。

所以，条件连接相当于
$$R\underset{A\theta B}{\bowtie }S={\sigma }_{A\theta B}(R\times S)$$
若$\theta$表示=，则称为等值连接。

自然连接是特殊的等值连接，要求两个关系中比较的分量是相同的属性组，并在结果集中把重复的属性列去掉。
R ⋈ S = { t ∣ t = t r t s [ A ‾ ] , t r ∈ R ∧ t s ∈ S ∧ t r [ A ] = t s [ A ] } R \Join S = \{t|t=t_rt_s[\overline A], t_r\in R \land t_s \in S \land t_r[A] = t_s[A]\} R⋈S={t∣t=tr​ts​[A],tr​∈R∧ts​∈S∧tr​[A]=ts​[A]}
比如下例

如果有多列，也遵循相同规则

所有重复字段都必须严格相同。

（4）除

如果R、S有同一域上的属性或属性组，$R÷S$结果生成新关系$R^{\prime }$。

设$R(X,Y),S(Y),R^{\prime }(X)$，则
R ÷ S = { t ∣ t ∈ R ′ ∧ t r ∈ R ∧ t s ∈ S ∧ t r [ R ′ ] = t ∧ t ⋈ S ⊆ R } R \div S = \{t|t\in R' \land tr \in R \land ts \in S \land tr[R']=t \land t \Join S \subseteq R\} R÷S={t∣t∈R′∧tr∈R∧ts∈S∧tr[R′]=t∧t⋈S⊆R}
也就是R的属性中去掉与S具有公共域属性的其他属性。

也可以这么表示除运算
$$R÷S={\Pi }_x(R)-{\Pi }_x({\Pi }_x(R)\bowtie S-R)$$
其中$X$为$R$中除去$S$属性相同的其余属性。

接下来，我们更进一步解释除运算。首先引入象集$Z_X$：给定关系R(X,Z)，X、Z为属性组，当$t[X]=x$时，定义
Z x = { t [ Z ] ∣ t ∈ R , t [ X ] = x } Z_x = \{t[Z]|t\in R, t[X]=x\} Zx​={t[Z]∣t∈R,t[X]=x}
表示R中属性组X上值为x的诸元组在Z上分量的集合。比如

这样，我们定义除运算

给定关系R(X,Y)和S(Y,Z)，X、Y、Z为属性组，那么除运算得到的P(X)是满足下列条件的元组在X属性列上的投影：元组在X上的分量值x的象集Y_x包含S在Y上投影的集合。再从上面的例子来看：

四、扩充关系运算

下面介绍几个扩充运算。

（1）属性重命名

r是R上一个关系，A是R的一个属性，B是属性名，那么
$$r^{\prime }(R^{\prime })={\delta }_{A\to B}(r)$$
记为属性重命名。可以同时对一组属性操作，可以在同一个关系上做自然连接运算、做同一个关系的笛卡尔积、将两个关系的等值连接表示为自然连接。

（2）外连接

外连接是对自然连接的扩展，包含除了满足连接条件元组外包含未被连接的元组。

外连接包括左外连接、右外连接、全连接。

左外连接：关系R中不满足连接条件的元组，记为$R{\bowtie }_{L}S$

此时，比起自然连接，拓展了左面关系不满足条件的2号，并添加了NULL。

右外连接：关系S中不满足连接条件的元组，这些关系补空值，记为$R{\bowtie }_{R}S$

全外连接：关系R、S都进行考虑，记为$R{\bowtie }_{F}S$

实例

（1）检索计算机系学生的学号和姓名
$${\Pi }_{id,name}({\sigma }_{pro{=}^{\prime }计算{机}^{\prime }}(Student))$$
（2）查询选修2号课程学生学号
$${\Pi }_{id}({\sigma }_{课程号{=}^{\prime }{2}^{\prime }}(SC))$$
（3）查询选修1号课程的学生姓名（数据表为Student和SC）

$$ \Pi_{sname}(\sigma_{Cno='1'}(\sigma_{sc.sno=student.sno}(SC \times Student))) $$ 也可以直接自然连接 $$ \Pi_{sname}(\sigma_{Cno='1'}(SC \Join Student)) $$ 或 $$ \Pi_{sname}(\sigma_{Cno='1'}(SC) \Join Student) $$ （4） $$ Student - (\Pi_{Sno}(\sigma_{Cno='C1'}(SC)) \Join Student) $$ （5） $$ \Pi_{Cname}(\sigma_{Sname='刘明亮'} (Course \Join SC \Join Student)) $$ （6） $$ \Pi_{Sname}(\sigma_{Cpno='5'} (Course \Join SC \Join Student)) $$ 也可以写成 $$ \Pi_{Sname}(\sigma_{Cpno='5'}(Course) \Join SC \Join \Pi_{Sno, Sname}(Student)) $$ 等。

（7）

$$ \Pi_{Sno,Cno}(SC) \div \Pi_{Cno}(Course) \Join \Pi_{Sno,Sname}(Student) $$ （8）查询选修1号课程和3号课程的学生的学号

首先建立临时关系$K$，Cno列为$1,3$。则答案为
$${\Pi }_{Sno,Cno}(SC)÷K$$
（9）

$$ SC \cup \{'200504','C4',88\} $$ （10）删除学生刘明亮选修的英语课 $$ SC - (\Pi_{Sno}(\sigma_{Sname='刘明亮'}(Student))\Join SC \Join \Pi_{Cno}(\sigma_{Cname='英语'}(Course))) $$ （11） $$ \Pi_{Sname}( Student \div \Pi_{Sdept}(\sigma_{Sname='李勇'}(Student))) $$

$${\sigma }_{Sname{=}^{\prime }李{勇}^{\prime }}({\Pi }_{Sname,Sn{o}^{\prime },Snam{e}^{\prime }}(Student\bowtie {\delta }_{Sno,Sname,Sage,Ssex\to Sn{o}^{\prime },Snam{e}^{\prime },Sag{e}^{\prime },Sse{x}^{\prime }}(Student)))$$

用关系代数可以完成数据的检索、插入、删除，一次一集合。交并差笛卡尔积，选择投影连交除。

元组关系演算

关系代数是用关系运算来表达查询，关系演算是用谓词来表达查询要求。进一步分为元组演算和域演算。

元组语言的语句格式是 操作语句 <工作空间名> (表达式) : 条件

• 检索语句Get
  • GET W (SC.Cno)
  • GET W (Student)
  • GET W (Student.Cno, Student.Sage) : Student.Sdept = ‘IS’
• 更新操作
  • HOLD 将修改元组读到空间中
    • HOLD W (Student.Sno, Student.Sdetp) : Student.Sno = ‘95007’
  • MOVE 用宿主语言修改
    • MOVE ‘IS’ TO W.Sdept
  • UPDATE 将修改后元组送回
    • UPDATE W
  • PUT 插入操作
    • MOVE ‘8’ TO W.Cno
    • MOVE ‘机组’ To W.Cname
    • PUT W (Course)
  • DELETE 删除操作
    • HOLD W …
    • DELETE W

域关系语言

域关系语言是基于屏幕表格的查询语言。

了解其特点即可。

关系数据语言

关系数据语言集关系代数和关系演算为一体。

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

这里有三种关系运算的等价性。

关系数据库中，关系是有限的。关系代数运算是安全的，但关系演算不一定安全。当对安全性进行限制注资后，三种演算是完全等价的。