DBMS (Database Management System)

A software package designed to store and manage databases. Often loosely called
a database.

传统的数据管理, 往往是结合 csv
格式文件来将数据存储起来, 并且允许通过各种约束条件查找,
但是假设存在一个学生数据库系统, 包括 姓名, 年龄, id,
成绩等字段, 如果原始数据的存储方式是分成两个 文件, 一个存储 姓名到 id
的映射, 另一个存储 id 到成绩的映射, 那么采用传统的 c++ 等语言来查找数据,
会存在很多问题, 例如, atomic 的操作, 很难在确保 performance 的前提下能保证
consistency

因此, 为了避免上述问题,
需要一个软件系统来管理数据的存储和访问,确保有以下设计目标:

  1. Data Independence: 即客户端需要看到的只是数据的逻辑结构而非实际存储结构
  2. Efficiency
  3. Centralized Management
  4. Security adn integrity
  5. Concurrent Access and Crash Recovery
  6. Reduced Application Development Time

Data Model

数据模型是 collection of concepts for describing data, 直接地说, 就是利用
关系网络或者 attributes 属性来构建数据的逻辑结构
举例说明, 比如一个地球显示系统, 我们可以用投影描述, 也可以用立体球体地球仪描述, 这就是两种不同的数据模型;

Schema: a description of a particular collection of data, using a given data
model
用常见的二位数据表的例子来说, 可以理解为数据库中每个数据表和其字段的关系定义, 比如在
UMDB 中有一个 Student 数据表, 那么这里的 schema 描述的就是 表名 和各个 attribute 的组合

最常见的数据模型有2种:

  1. Relational Model: 数据以二维表格的形式存储, 每一行代表一个记录 record/tuple, 每一列代表一个属性 (attribute)/field
  2. Entity-Relationship Model: 用实体 (entity) 和实体之间的关系 (relationship) 来描述数据, 实体可以有属性, 实体和实体之间可以有多种关系

多层抽象 Abstraction

一般数据库系统会有三层抽象:

  1. Physical Schema: 描述数据的实际存储方式, 例如数据是存储在硬盘上还是内存中, 数据是如何组织的 (例如 B-tree, Hash table), 记录 index - file 的映射关系
  2. Conceptual Schema: 描述数据的逻辑结构, 例如数据表的 schema, 数据之间的关系
  • 这一层是全局的, 即描述了整个数据库的数据及其之间的关系
  • 不包含 index, view 等信息
  • 往往被做成 ER 图来描述之间的关系
  1. External Schema (可以有多个): 描述用户视图 (View), 即用户能看到的数据和数据的组织方式
  • 定义 schema 的语言叫做 Data Definition Language (DDL), 例如 SQL 中的 CREATE, ALTER, DROP 等命令
  • 数据通过 Data Manipulation Language (DML) 来进行操作, 例如 SQL 中的 SELECT, INSERT, UPDATE, DELETE 等命令

两层映像 (Mapping))

通过分层设计, 实现了数据独立性

  • Physical Data Independence: 物理层的变化不会影响到概念层, 例如改变数据的存储方式, 不会影响到数据的逻辑结构
  • Logical Data Independence: 概念层的变化不会影响到外部层, 例如增加一个新的数据表, 不会影响到用户视图
    • App 是基于 external schema 来设计的, 因此只要不改变 external schema, 就不会影响到 app 的设计 (改变的是 Conceptual-External 的映射关系)

Entity-Relationship Model

这是一个语义层次的数据模型, 用实体 (entity) 和实体之间的关系 (relationship) 来描述数据, 实体可以有属性, 实体和实体之间可以有多种关系

总结来说, ER 模型由 实体(entity), 属性(attribute), 关系(relationship) 三个基本概念组成;
举例说明, 在表达式 “Movies are directed by Directors” 中, “Movies” 和 “Directors” 是实体, “are directed by” 这个谓词是关系;

关系从左右联系数量上可以分为 Many-to-Many, One-to-Many (Many-to-One), One-to-One 三种;

关系约束

而关系是收到 Constraints 约束的, 主要有以下几种:

  • Key Constraint (AT MOST ONE): 比如在上述例子中, 我们令 “Movies can be directed by at most one Director”, 这就是一个 key constraint, 即 movies 只能对应 1 个 director, 或者我们用二维表的角度来说, 当 movie 作为索引其对应的 director attributes 是能唯一确定的, 我们可以称这一项为 键约束
    • 在画图中, key constraint 被画为箭头形
  • Participation Constraint (AT LEAST ONE): 参与约束, 即一个实体是否必须参与到某个关系中, 例如 “Every Movie must be directed by at least one Director”, 这就是一个 participation constraint, 即每个 movie 必须至少有一个 director
    • 当 movie 作为索引的时候, 其至少由一个 record
    • 在画图中, participation constraint 被画为粗线

在一个数据表中, 一般会维护关系数据表, 比如 Student-from-School, 其中 Student 和 School 都是实体, 而 from 是关系, 从常识上知道 这里是 N-to-1 的关系 (一个学生最多只能有一个学校, 而一个学校可以有多个学生); 如果要维护 from 数据表并且尽可能减少重复冗余, 我们可以直接将 from 关系表放到 Student 表中从而减少重复量, 注意看这里的 Student 关系表就会出现多个重复的 School attribute

实体关系到数据表关系总结

  1. 1-to-N 关系中, 将 1 端的主键放到 N 端(伸出箭头)数据表中, 就可以替代关系表了 (从箭头方向来看这属于是 逆流而上)
  2. N-to-N 关系中, 必须保留关系表, 不能将任何一端的主键放到另一端的数据表中 (因为会有重复), 在关系表中的主键是 (key1, key2) 这样的 tuple
  3. 1-to-1 关系中, 可以将任意一端的主键放到另一端的数据表中 (从箭头方向来看这属于是 顺流而下), 也可以保留关系表; 注意这里的 1-to-1 关系指的是两边都有一个箭头指向中间的菱形

Keys

键指的是一个或者多个属性对每一个 record 有唯一值的最小集合, 一个实体可以有多个键
(potential key/candidate key), 但是只能有一个主键 (primary key),
在图中表示为下划线; 设计数据库的时候, 往往会将多个表共同的 potential key 选择为 primary key 从而更好展示关系

属性 attributes

一个对象实体是具有属性的, 默认来说entity的属性是唯一的, 例如 student 的 birthday
属性不能有两个

Descriptive Attributes 描述属性

在关系图中用于描述关系的属性, 例如 “Citizen vote Candidate on Monday”, 这里的 Monday 就是描述属性, 因为 Citizen 实例 和 Candidate 只有在构成 vote 关系的时候才会存在这个 when 的描述属性, 而单独作为 Citizen 实体的时候同一个人可能会多次给不同人投票, 这里默认属性对用户唯一, 因此给 citizen 当属性非法

换言之, 描述属性是一种弱化的实体, 比如上述这个 when 其实也可以作为一个实体来描述, 其具有两个属性 from 和 to 这样变成一个完整的实体了

Weak Entity 弱实体

自身没有足够的属性来形成主键, 不能独立被唯一标识
必须依赖于某个 强实体 (Owner / Identifying Entity) 的主键, 再结合自己的 部分键 (Partial Key), 才能唯一标识
弱实体存在如下两个 rule:

  1. 每个弱实体必须有唯一一个强实体与之关联 (强对弱有 one-to-many relationship),
    也就是它一定有一个粗箭头指向关系菱形
  2. 每个弱实体必须全部参与到与强实体的关系中 (total participation)

在强弱实体的关系中往往称强实体为 Owner

例如在上述 Citizen vote Candidate 的例子中, 如果我们加入一个新的关系 Candidate helped by Experts 但是这里 Expert 实体不存在 eid 之类的唯一标识符, 而只能用 name (不唯一, 不能做主键) 来标识, 就称这个 name 为 部分键, 如果要唯一标识 Expert 就需要向外调用 Candidate 来辅助定位, 即 使用 (eid, name) 这一 tuple 来做识别

最经典的例子是在一个 Department 中所有员工的名字是唯一的

从数据表视图来看 weak entity

由于弱实体的主键是依赖于强实体的, 因此主键是 (strong_entity_key, weak_entity_partial_key) 这样的 tuple
并且由于弱实体如果删除了主键, 其本身是无法继续存在的, 因此会额外添加一个 ON DELETE CASCADE 的约束`, 即当强实体被删除的时候, 其对应的弱实体 record 也会被删除

ISA hierarchy 继承关系

如果 A ISA B, 表示 A 是 B 的一种特殊化 (specialization), 或者说 B 是 A 的泛化 (generalization)
继承机制: 子类(下层)继承父类(上层)的所有属性

overlap 一个父类实体能否同时属于多个子类?

某个公民既是 Candidate, 又是 President
如果一个实体只能属于一个子类, 那么称为 disjoint (互斥的)

covering 父类实体是否必须属于某个子类?

有些 Citizen 既不是 PR-Cand, 也不是 President
如果一个实体可以不属于任何子类, 那么称为 partial (部分的)

ISA 继承关系关系表

由于继承实际上也是种关系, 因此也可以用关系表来表示,
但是并不是维护关系表, 而是维护三个 (父类, 子类1, 子类2) 三个表
不过查询里面最难处理的就是容斥问题了

Entity vs Attribute: 唯一性差异

考虑关系: Dept. manages Employee, 如果我们要插入一个新的关系逻辑: Each manager (also an employee) manages the budget of each Dept. 也就是每个 employee 对不同的 dept 都有不同的 budget attribute 值 (无论是管理还是被管理), 即不会重复, 那么这里就可以作为 descriptive attribute 来描述, 而不需要单独作为一个实体

但是如果我们改成 Manager (also an employee) manages the budget covering all Dept., 那么当给定 Manager 的时候, 对应的所有 Dept. 的 budget 都是同一个数值 (即总账单量), 这种 Redundancy 其实是浪费, 同时这种关系表明 budget 是和 manages 这个关系绑定而非 manager 的属性 (manage 本身不应该存在总账单量的属性因为这是全局属性), 存在概念 Misleading, 因此应当将这个 Manager 作为 Entity 独立出来

Participation Constraint in Ternary Relationship 三元参与约束

考虑关系: A citizen votes at most once and only at one polling station for a candidate.

三元关系很多时候很难想到, 比如很容易直接地根据描述写成两个二元关系:

假设有一个 message 和 user 实体, 其中 message 数据表会记录一则消息的发送者和接受者, 那么直接看我们就会写成 Message - has receiver - User 和 Message - has sender - User 两个二元关系, 但是从设计表的角度来看, 这样分两个表设计会非常浪费 record 数量 (因为存在大量重复), 所以从表设计的角度来看, 最合适的做法是将 Sender (User) - Message - Receiver (User) 设计成一个三元关系;