This article does not have a corresponding language version

数据库系统

一、相关

基本概念：

数据（Data）是描述事物的符号记录，是对客观事物的属性的度量或表达，是可以鉴别的、可以被计算机处理的符号，只有数据没有用，要有解释，此时就形成了 信息。 数据库（Database, DB）是长期存储在计算机内、有组织的、可共享的大量数据的集合。数据库中的数据按一定的数据模型组织、描述和存储，具有较小的冗余度、较高的数据独立性和易扩展性，并可为各种用户共享。

数据库系统（Database System, DBS）是由数据库、数据库管理系统（及其应用开发工具）、应用程序和数据库管理员（DBA）组成的存储、管理、处理和维护数据的系统。

数据库管理系统（Database Management System, DBMS）位于用户与操作系统之间，是一层数据管理软件，是基础软件，也是一个大型复杂的软件系统。DBMS 的主要功能包括：

  1. 数据定义功能：提供数据定义语言（DDL），定义数据库中的数据对象。
  2. 数据操纵功能：提供数据操纵语言（DML），实现对数据库的基本操作。
  3. 数据控制功能：实现数据的安全性、完整性控制，以及并发控制。
  4. 数据组织、存储和管理：提供多种存取方法，提高存储效率和存取速度。
  5. 数据库的建立和维护功能：提供数据库初始数据的转入、转储、恢复、重组和性能监视等工具。
  6. 其他功能：如通信、网络功能等。

数据管理的目标：课支持人民高校获取和维护可共享、安全的、可靠的数据

文件系统管理的问题：数据冗余和不一致、数据访问困难、数据孤立、完整性问题、原子性问题、并发访问异常、安全性问题

元组：一行

属性：一列

关系：指表，包含所有具体的行数据

模式：数据库的总体设计，类似于变量的定义声明，只有列名、类型和约束

实例：一个使用中的数据库在某个时刻的数据，类似于变量某时刻的值

关系的完整性：是指数据库中数据应满足的约束条件，用以保证数据的正确性、有效性和一致性。三类完整性约束：

  • 实体完整性：关系的主码不能取空值（因为主码用于唯一标识一个元组）
  • 参照完整性：如果关系 R 的外码 FK 是关系 S 的主码 PK，则 R 中任何元组在 FK 上的值要么取空值，要么等于 S 中某个元组在 PK 上的值。（要确保引用的实体必须存在。）
  • 用户定义的完整性：针对特定应用环境的约束条件，由用户自定义。例如年龄区间、工资区间
image-20260619150703229

发展阶段

数据库技术的发展大致经历了以下几个阶段：

  1. 人工管理阶段（20 世纪 50 年代中期以前）：
    • 数据不保存。
    • 数据不共享。
    • 数据不独立。
    • 应用程序管理数据。
  2. 文件系统阶段（20 世纪 50 年代中期至 60 年代中期）：
    • 数据可长期保存。
    • 文件记录的概念。
    • 记录格式化和文件结构化。
    • 缺点：数据冗余、不一致性、应用程序依赖于文件、数据间联系弱、安全性差。
  3. 数据库系统阶段（20 世纪 60 年代末至今）：
    • 早期数据库系统：层次模型和网状模型数据库系统（如 IMS、IDMS）。
    • 关系数据库系统（20 世纪 70 年代）：基于关系模型，具有坚实的数学基础和简单的用户抽象（如 System R、Oracle、DB2、SQL Server）。
    • 新一代数据库系统（20 世纪 80 年代中期以后）：面向对象数据库、对象关系数据库、XML 数据库、NoSQL 数据库、NewSQL 数据库等。

管理和设计

要高效存取数据，使用复杂的数据结构的同时为用户提供容易使用的数据存储方式

核心思路：使用多层抽象因此内部实现的复杂性

数据模型

数据模型是对现实世界数据特征的抽象，是数据库系统的核心和基础。一个数据模型通常由数据结构、数据操作和数据完整性约束三部分组成。

数据库用于描述以下对象的概念工具集合： 数据、数据联系、数据语义、一致性约束（表示模型用来描述什么对象）

模型三要素

  • 数据结构：描述组成对象和对象之间的联系，对模型的静态特征的描述
  • 数据操作：操作的集合、操作的语言，是对模型的动态特性的描述
  • 数据的完整性约束

结构 + 完整性约束 = 模式

三级模式架构

外模式、概念模式、内模式，分别对应外部层、概念层、内部层

模式：对应子模式、逻辑模式、物理模式

设计流程

概念模型：

  • 按用户的观点对数据和信息建模，主要用于数据库设计的概念级，与具体的 DBMS 无关。
  • 最常用的概念模型是实体-联系模型（E-R 模型）。

逻辑模型：

  • 按计算机系统的观点对数据建模，主要用于数据库设计的逻辑级，与具体的 DBMS 有关。
  • 主要包括：层次模型、网状模型、关系模型、面向对象模型等。

物理模型：

  • 对数据最底层的抽象，描述数据在存储介质上的存储结构和存取方法，是面向计算机系统的。

常见的数据模型

层次模型：
  • 数据结构呈树形结构，有且仅有一个结点没有父结点，称为根结点。
  • 除根结点外，其他结点有且仅有一个父结点，可以有零个或多个子结点。
  • 结点之间是 1:n（一对多）的联系。
网状模型：
  • 数据结构是有向图结构，允许多个结点没有父结点。
  • 一个结点可以有多个父结点和多个子结点。
  • 结点之间可以是 m:n（多对多）的联系。
关系模型：

是目前最主要的数据库模型

  • 数据结构是一张二维表，称为关系。（此时行叫做元组，列叫做属性）
  • 关系是一组具有相同属性的元组（tuple）的集合。
  • 关系模型建立在严格的数学基础上。

两级映像：

外模式/模式的映像在外模式中定义

内模式/模式的映像在模式中定义

  • 三级：外（用户看）、概（全局看）、内（机器存）。
  • 两级映射：外/概（保证改表不重写程序——逻辑独立）；概/内（保证改存储不改表结构——物理独立）。

这么分就是为了实现数据独立性

数据独立性：

数据独立性是指数据与程序的相互独立性，是数据库系统的重要特征，分为两类：

  1. 物理数据独立性：

    • 指应用程序和数据库逻辑结构独立于数据的物理存储结构。
    • 内模式改变，模式不变，应用程序不受影响。
    • 由模式/内模式映射来实现。

    当存储的物理结构变化（如不是顺序存放时），让模式保持不变，保证数据和程序的物理独立性

  2. 逻辑数据独立性：

    • 指用户的应用程序独立于数据库的逻辑结构。
    • 模式改变，外模式不变，应用程序不受影响。
    • 由外模式/模式映射来实现。

    人话：模式改变的时候，数据库管理员对外模式/模式的映像作改变，让外模式保持不变，让基于外模式的应用程序几乎不受影响

综上，三级模式、二级映像简化了应用程序的编制，提高了应用的开发效率和维护成本

E-R图

image-20260622103710987
基本概念：
  • 实体：客观存在并可相互区别的事物称为实体。实体集是具有相同属性的实体的集合。
  • 属性：实体所具有的某一特性称为属性。一个实体可以由多个属性来描述。
  • 码：能唯一标识实体的属性或属性集称为码。
  • 联系：表示实体之间的关联，是现实世界中事物内部以及事物之间的联系在数据模型中的反映 联系的类型包括：1:1（一对一）、1:n（一对多）、m:n（多对多）
ER图符号：
  • 矩形：表示实体集。
  • 椭圆：表示属性。（此处不用）
  • 菱形：表示联系（关系）集。
  • 线段：连接属性与实体集、实体集与联系集。
画图：

一对一：两个表与关系的接触部分画朝向表的箭头

image-20260621191054905

一对多：1的一方画箭头

image-20260621191146073

多对多：无箭头，并在中间建立关联表

image-20260621191215472

另外，ER图中不需要把联系的属性画在两边的表中（ER图不需要画出外键）

双线：

也叫存在依赖（Existence Dependency）。

用一句人话翻译就是：“这边的实体，必须至少有一个‘身份’挂在这个关系上，没有例外 如：如果员工端画双线：意味着每个员工必须属于至少一个部门（公司不允许无部门人员）

虚线：

不常用

当线段画成虚线时，表示弱实体（Weak Entity）与其所依赖的“所有者实体（Owner Entity）”之间的联系。

具体场景：子实体（弱实体）没有自己的主键，必须依赖于父实体的主键才能唯一标识。

例如订单（父）和 订单明细（子）。

  • 一条“订单明细”离开了“订单”就毫无意义（它的主键是 订单号 + 行号）

关系模型

  1. 将实体的各个名字转换为各个关系的模式的名字
  2. 实体的属性就是关系的属性，码就是关系的码
  3. 联系的转换：
    • 1对1：任意一方加入对方的主码并设为外码，并加入联系本身的属性（如果有的话）
    • 1对n：将1方的主码加入n方作为外码，并同时将联系的属性加入n方
    • n对m：将联系本身转换为一个关系模式（新作一张表）：将联系双方的主码加入其中设为码，并将联系的属性也加入其中

三级模式结构：

三级模式结构是 ANSI/SPARC（美国国家标准协会/系统规划与需求委员会）于 1975 年提出的，包括外模式、模式和内模式三个层次。

还包括两个映像：外模式/模式的映像和内模式/模式的映像

外模式（External Schema）：
  • 也称为子模式或用户模式。
  • 描述了数据库中与特定用户组相关的局部数据视图。
  • 一个数据库可以有多个外模式。
  • 同一模式可以导出多个外模式。
模式（Schema）：
  • 也称为概念模式或逻辑模式。
  • 描述了数据库中全局的逻辑结构和特征。
  • 对数据的逻辑结构、联系、约束等进行定义。
  • 一个数据库只有一个模式。
内模式（Internal Schema）：
  • 也称为存储模式。
  • 描述了数据库的物理存储结构和存取方法。
  • 一个数据库只有一个内模式。

两级映像：

外模式/模式的映像在外模式中定义

内模式/模式的映像在模式中定义

  • 三级：外（用户看）、概（全局看）、内（机器存）。
  • 两级映射：外/概（保证改表不重写程序——逻辑独立）；概/内（保证改存储不改表结构——物理独立）。

这么分就是为了实现数据独立性

二、关系数据库

关系数据库是建立在关系模型基础上的数据库，是目前最主要的数据库类型。

基本概念

  1. 关系：对应一张二维表，由行和列组成。
  2. 元组：对应表中的一行，表示一个实体或一个联系的实例。
  3. 属性：对应表中的一列，表示实体或联系的一个特性。
  4. 码：可以唯一标识一个元组的属性集称为候选码，从中选定一个作为主码。
  5. 域：属性的取值范围，即一组相同数据类型的值的集合。
  6. 分量：元组中的一个属性值。
  7. 关系模式：对关系的描述，一般表示为 R(A₁, A₂, …, Aₙ)，其中 R 为关系名，A₁, A₂, …, Aₙ 为属性名。

关系的性质

  1. 列同质性：每一列中的数据类型相同。
  2. 不同列可允许不同的数据类型。
  3. 列的顺序无关紧要：列的次序可以任意交换，不影响关系的实际含义。
  4. 行的顺序无关紧要：行的次序可以任意交换，不影响关系的实际含义。
  5. 行列交叉处的每个值都是不可分的原子值。
  6. 不允许表中有完全相同的元组：每个元组都是唯一的。

关系代数

关系代数是一种抽象的查询语言，是一种过程化的语言，用对关系的运算来表达查询。

投影运算的结果是一个集合（Set）。在数学集合中，重复的元组（行）会被自动合并（去重）。也就是说，如果两个老师的工资和名字完全一样，在关系代数的结果里只会出现一次。

课件的六个基本： image-20260620161714398

选择：

选取满足给定谓词的元组，形成r(R)的一个子集

image-20260620204138924

σ条件(R)={t∣t∈R∧F(t)=true}

条件是选择谓词，可以用连词将多个谓词合并为一个大谓词

image-20260620204156513
投影：

投影是一元运算，返回作为参数的关系，但把某些属性排除在外，但由于关系是一个集合，所以所有重复的行均被去除

image-20260620204356528

也就是，并非相当于 SELECT A,C FROM r

而是SELECT DISTINCT A,C FROM r

组合：

多个关系代数运算可以组合，形成关系代数表达式

位置表记法：用$n表示第n各属性

并：

满足以下条件才有效：

  • r，s必须属性数目相同
  • 对应的属性域必须相同
image-20260620204646142
差：
image-20260620204713711

有效的要求和并相同

笛卡尔积：
image-20260620204756464
更名：

用于为关系代数表达式附上名字以引用

image-20260620204901134
自然连接：

将两张表自动按照所有同名的列进行等值连接，并只保留一份同名列，去掉另一份重复的列，其他的列正常存在。然后对所有的列检查匹配，自然连接的结果行数 = 匹配上的行数。

image-20260620210226617
θ 连接
$$ R \bowtie_{\text{条件}} S = \{ t_r \bowtie t_s \mid t_r \in R \land t_s \in S \land t_r.A \theta t_s.B \} $$image-20260620210530290
聚集运算
image-20260620214052325 $$ \text{Retailer} \bowtie(rID \, \mathcal{F}_{\operatorname{SUM}(itemPrice)}(\text{OdrDetail})) $$ 先对 `OdrDetail` 按 `rID` 分组求和，再把结果连接回 `Retailer` 表以获得零售商名字。

关系操作：

关系操作是对关系进行查询和修改的操作，基本操作包括

对元组进行：查询、删除、插入、修改

三、关系理论

函数依赖

指一个属性集可以推出另一个属性集

函数集

多个函数依赖的集合

  • 非平凡的函数依赖： X -> Y 且 Y 不是 X 的子集

  • 平凡的函数依赖： X -> Y 且 Y 是 X 的子集(废话)

无特殊说明的情况下，均讨论非平凡的函数依赖。

非平凡函数需要被主键或唯一约束强制锁定 比如 学号 → 姓名（右边没有包含在左边）。为了让这个依赖成立（即确保一个学号只能有一个姓名），数据库必须在 学号 列上建立主键索引或唯一索引

完全函数依赖：

X -> Y 并且对于 X 的任意真子集 X’ 都推不出 Y ，则称 Y 完全函数依赖于 X ，记作：x -> Y ，箭头上有个F

部分函数依赖：

设 X→Y是一个函数依赖，如果存在 X 的一个真子集 X’（X′⊂X），使得 X′→Y 也成立，那么称 Y部分函数依赖于 X。

当 Y 不完全函数依赖于X，记作 X -> Y，箭头上是P，例如 A -> C 又有 AB -> C，那么C就是部分函数依赖于AB的，这种情况会造成 数据冗余

数据冗余会造成三大异常：更新异常、插入异常、删除异常

码

候选码

是一个属性组（或者属性），通过该属性组能推出所有的属性，并且该属性组的任意子集都不能再推出所有属性了，即在满足完全函数依赖的前提下，还将是最小的属性组（但是注意，不同订单候选码依旧可能长短不一）。答题时将这些候选码构成集合。

人话就是，一些属性组可以推出整个表的属性值，如学号可以推出姓名，但是没了学号只有课程号不能推出姓名，并且这个组最小

找候选码：
1.先判断

在函数依赖集中会有一些关系

一定属于候选码：只出现在左边或者左右都没出现

可能属于候选码：左右都出现

不属于候选码：只在右边出现

2.对确定的属性求闭包

先对确定的属性求闭包，若不能构成闭包，再将确定的属性和待定的属性进行组合，做闭包运算，直到遇到的属性组能够推出全部的属性

所谓求闭包，就是根据现有的函数依赖集和属性求出可推出的最大属性集。给了起点后，顺着依赖关系“箭头”一路走下去，最终能到达的所有属性的总集。

过程：

首先设有集合X ，X = { 该属性组 }

X^(0) = 自身

X^(1) = X^(0)中所能推出的

X^(i + 1) = X^(i)中所能推出的

以此类推直到 X ^ (i+1) = X ^ (i) 或 X ^ (i) = U，就求得了属性组的闭包

闭包运算还可以用于判断 X -> Y 是否成立 ，当 Y 属于 {(X)_F}^+时，有X -> Y

闭包运算结果用{(X)_F}^+表示：

$$ (X)_F^+ $$

候选码写法可为：{（ABD）、（BCD）、（BDE） }

超码：

能推出所有属性的属性组的集合，感觉概念可知，候选码是极小的超码集，是超码的子集

主码：

当有多个候选码时，挑出一个作为主码，简称码

主属性：

包含在任何一个候选码中的属性，如例子候选码中的B、D都是主属性

非主属性：

不包含在任何一个候选码中的属性，如例子中的 G

外码：

关系模式R中，若有一个属性或者属性组X，他不是R的码，但X是另一个关系模式S中的码，称X是R的外码

全码：

最极端情况下，整个属性组都是码，则称为全码

范式

第一范式（1NF）

所有属性都是不可分割的数据项

第二范式（2NF）

满足1NF前提下，不包含非主属性对码的部分的函数依赖（每一个非主属性都完全函数依赖于码）

第三范式（3NF）

满足2NF前提下，不包含非主属性对码的传递函数依赖，即码应该直接决定非主属性，不能间接决定

BCNF：

消除任何属性对候选码的传递依赖，即每一个决定因素都包含码（具体表现为：在函数依赖集中，左边的都包含候选码）

分解：

将导致不符合要求的关系的左右部分单独提出来

第四范式

最小函数依赖集

最小函数依赖集可能有多个，存在多个时任选一个即可

求法：
  1. 拆分右侧，例如将 A -> BC 分成 A -> B 和 A -> C
  2. 去除自身求闭包 若有AB -> C，BC -> E，AE -> G，在去除AB自身能推出的C（去除AB -> C条件）的前提下，基于剩余的依赖关系求AB的闭包，若AB通过剩余的关系也能求出C，那么可以删除AB -> C
  3. 左侧最小化：ABC -> D 若C能被AB推出则删除C

模式分解

模式分解有两个准则：无损连接和保持函数依赖

3NF

先求最小函数依赖集，然后候选码只出现在左边（注意左边也可以出现非候选码），然后看是否有一个关系包含候选码，没有就新建一个。

BCNF

所有依赖项的决定因素都是候选码，也就是左边应该全是候选码

依旧先拿到最小依赖集，把这些关系（X -> Y）中找到的不满足左边是超键的部分（X），将依赖“分组”成关系：

将关系 R 分解为：

  • R1=XY把决定因素和它决定的属性放一起）
  • 将最小依赖集被分出去的非主码部分用主码表示
  • 循环递归直到结束

无损连接：分解后再次自然连接，与分解前相同

判断无损连接/分解的方法： 把一个表 R 拆成 R1 和 R2 两个表，当以后再把 R1 和 R2 自然连接（⋈） 回去时，数据一条不多、一条不少，完全复原成原来的 R

四、查询处理和查询优化

查询处理指的是从数据库中提取数据所设1计的一系列活动

查询 -> 查询分析 -> 查询检查 -> 查询优化 -> 查询执行

工作方式：

  1. 词法分析、语法分析
  2. 查询检查，使用数据字典检查查询的语义信息，检查权限、完整性约束
  3. 然后将查询语句转化为等价的关系代数表达式

查询优化：

指从多种可能的查询执行计划中选择最有效的执行计划

  • 代数优化：在等价的关系代数表达式中选择最有效的表达式。

  • 物理优化：为关系代数表达式选择详细的执行策略，包括可用的算法、索引等。

查询执行：

指根据最优的执行计划生成查询执行代码，并执行代码以获取所需的记录。

  • 在执行查询之前，还会进行安全检查，以确保执行查询的用户具有相应的访问权限。
  • 对于数据库更新操作，还会检查完整性约束。

查询处理：

  • 表扫描：顺序扫描
  • 索引扫描：使用索引结构或哈希函数找到满足条件的数据之战，并通过指针直接访问学生表中的数据

查询优化

从多种可能的查询执行计划中选择最有效的执行计划

开销主要包括I/O操作、CPU执行、RAM操作何通信。通常使用IO世界来评估执行成本

代数优化策略通过关系代数表达式的等价变换来提高查询效率

例如：

image-20260619184310479

物理优化指选择最有效的操作算法或存取路径来执行关系代数表达式

包括：

  • 基于规则的启发式优化
  • 基于代价估算的优化，需要计算每个操作算法的执行成本
  • 混合优化方法

例如：SELECT操作的启发式优化规则

  • 当选择条件是主键时，可以使用主键上的索引。通常关系数据库管理系统会自动在主键上建立索引。

  • 当选择条件是对普通属性的索引时，应估计返回的行数多少。如果大小小于整体10%，则可以使用索引。

五、恢复系统/事务调度

事务

事务：事务时程序的执行单元，将访问或更新(R和W)部分数据项

需要满足的特性：

为了保障数据一致性，数据库系统中运行的事务必须遵守：

  • 原子性要求、持久性要求、

  • 一致性要求：事务不能破坏数据库中预定义的完整性约束和业务逻辑规则，数据必须始终是合法、有效的。）

  • 隔离性要求：一个事务的内部操作和数据状态，在提交之前，对其他并发事务是不可见的。 最终效果必须与这些事务按某种顺序串行执行（一个接一个地跑）的结果完全一致。

事务的状态：
image-20260619190306128

故障

故障的分类：
  • 事务
  • 系统
  • 介质
image-20260619190529914

故障恢复：

数据转储，登记日志文件

image-20260619190657997
恢复算法：
image-20260619190712577
转存：
image-20260619190729883
日志：
image-20260619190745572
撤销和重做：
image-20260619190812056

基于日志的数据恢复：

image-20260619190841515
检查点：

在磁盘写日志记录< checkpoint N >，其中N代表当前正在活动状态的事务集合

添加检查点的过程中，所有事务的数据更新操作被禁止

基于检查的的数据恢复：image-20260619191123943

数据恢复：

  • 从事务故障中恢复

基于日志的恢复（带检查点）

  • 从系统崩溃中恢复

基于日志的恢复（带检查点）

  • 从介质故障中恢复

转储+基于日志的恢复（带检查点）

事务调度准则：

1.一组事务必须保证：

包含了所有事务的操作指令：一个事务内部的指令顺序必须保持不变

2.并行事务调度必须保证：

可串行化：将所有可能的串行调度结果推演一遍，对于某个具体的串行调度执行一遍，看是否结果相同

判断可串行化的充分条件：

冲突可串行化 => 可串行化

冲突操作：不同事务对同一数据分别进行读和写；不同事务对同一数据分别进行写和写

冲突可串行化调度，即不交换不同事务的冲突操作次序，也不交换同一事务的两个操作次序，但可以交换不同事物对不同数据各种操作次序，也可以交换不同事务对同一数据的读取操作次序

六、并发控制

主要技术：封锁、时间戳、乐观控制阀、多版本并发控制

并发带来的数据不一致性：

丢失修改、不可重复读、读脏数据

封锁：

X锁

写锁，某事物上锁后可以读取和修改，其他事务不可添加锁

S锁

读锁，某事务对数据对象上锁后，可读取但不可修改，其他事务可以对该数据对象添加S锁，但不可添加X锁

其他

“事务结束”特指提交（COMMIT）或回滚（ROLLBACK）的那一刻。

封锁协议

封锁协议规定了何时以及如何对数据对象加锁和解锁，以避免并发问题

一级封锁协议：

写前加写锁，事务结束释放写锁；可防止丢失修改

二级：

写前加写锁，读前加读锁，读完释放读锁，事务结束释放各锁；可防止丢失修改和读脏数据

三级：

写前加写锁，读前加读锁，事务结束释放各锁；可防止丢失修改、读脏数据和不可重复读

三级相比二级，就是为了在本事务不读的时候数据被修改，再次读入的时候读了脏数据。当事务结束即可释放锁。

如果所有事务都遵循三级封锁协议，由于其隔离级别高，那么这些事务无论怎么样交叉并行，都是可串行化的阅读

两段锁协议：
image-20260619180836643

两段锁协议要求每个事务分为两个阶段：

  1. 扩展阶段：事务只能获得锁，不能释放锁。
  2. 收缩阶段：事务只能释放锁，不能获得锁。

两段锁协议能够保证调度的冲突可串行性，从而维护事务的隔离性

活锁死锁

  • 活锁：事务无法获得某些数据项的锁，因此该事务永远无法继续执行 用先到先服务可以避免
  • 死锁：系统中存在一组事务，每个事务都在等待组中的另一个事务释放锁
死锁处理：
  • 死锁预防：一次性封锁，事务在执行前锁定所以会操作的数据项；顺序封锁：对所有数据进行排序，并要求事务按该顺序加锁
  • 死锁诊断与解除：用等待图进行建模