📚 读书笔记 | 数据库管理系统 - 原理与设计

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

大二下学期课程，记录一下学习的重点和笔记。🐷

《数据库管理系统 - 原理与设计》

本文内容包括书中的五个部分：数据库基础、存储与索引、查询评估、事务管理和数据库设计与调整

最后一部分只写了一部分的内容，因为上课也是只讲了这一部分的第一章的部分内容，以后有时间再继续读这本书，写的的确是很深入，对于数据库的理解很有帮助。

其实还有第二部分 应用程序开发的，只是这个部分理论的不多，大多是实际项目做法，就跳过了。

第一部分 数据库基础

概述

数据库是数据的集合，用于描述一个或多个相关组织的活动。

一个数据库包括：

  • 实体
  • 实体间的联系

数据库管理系统（Database management system, DBMS）

管理数据

  • 数据库设计和应用程序开发
  • 数据分析
  • 并发性和稳健性
  • 有效性和可伸缩性

文件系统和数据库管理系统

DBMS 对于文件系统的优势：

  • 可以直接操作大数据
  • 不同用户并发存取数据，保护数据的一致性
  • 系统崩溃时，确保数据恢复到一致的状态
  • 允许不同用户有存取不同数据子集的权限的安全策略

DBMS 的优点

  • 数据独立性
    • 把应用代码与数据细节分开
  • 有效的数据存取
  • 数据完整性和安全性
  • 数据管理
  • 并发存储和故障恢复
  • 减少应用程序开发时间

对于严格实时约束的应用程序以及灵活的文本数据分析就不太适合使用 DBMS

数据的描述和储存

数据模型（data model）是隐藏了许多低级存取细节的高级数据描述结构的集合。

语义数据模型（semantic data model）是一种更抽象的高级数据模型。

实体-联系（ER）模型是一个广泛使用的予以数据模型。

关系模型

关系模型的核心数据描述结构是关系（relation），可以被认为是 记录（record）的集合。

基于数据模型的数据描述称为模式（schema）

关系模型中一个搞关系的模式需要说明这个关系的名字， 每个字段（属性 attribute 或列）的名字及每个字段的类型

完整性约束是关系中的记录必须满足的条件。

其他数据模型：

  • 层次模型
  • 网状模型
  • 面向对象模型
  • 对象 - 关系模型

数据库管理系统的抽象级别

数据库由以下三种抽象模式组成

磁盘 物理模式 ←→ 概念模式 ←→ 外模式

数据定义语言(data definition language, DDL) 用于定义外模式和概念模式

  • 概念模式，Conceptual Schema(又称逻辑模式)
    • 以 DBMS 数据模型的形式描述存储的数据
    • 获得好的概念模式的过程称为概念数据库设计(conceptual database design)
  • 物理模式， Physical Schema
    • 描述存储细节， 概念模式中关系在二级存储设备上实际是如何存储的
    • 物理模式基于数据存取特点的
    • 获得好的物理模式的过程称为物理数据库设计
  • 外模式， External Schema
    • DBMS 的数据模型， 为单个用户和用户组定制(和授权)数据存取
    • 任何给定的数据库拥有一个概念模式和一个物理模式，但是可以有多个外模式
    • 外模式的记录可以在必要的时候计算出来

数据独立性

Data Independence

当数据的结构和存储方式发生变化时，应用程序不受影响。

如果概念模式发生变化，外模式可以重新设计保证可以计算出相同的关系

  • 逻辑数据独立性： 用户能够免于因数据逻辑结构变化或关系的存储的选择变化的影响(外模式 ←→ 概念模式)
  • 物理数据独立性： 概念模式把用户与数据物理存储的变化分开(概念模式 ←→ 物理模式)

数据库管理系统中的查询

查询(queries)： 针对 DBMS 中存储的数据的提问

查询语言(query language)： 一种 DBMS 提供的专门的语言

关系演算(Relational calculus)： 基于数理逻辑形式的查询语言

关系代数(Relational algebra)： 基于能操纵关系的操作集合的查询语言

数据操纵语言(data manipulation language， DML) 可以创建， 修改和查询数据，插入，删除和修改数据的结构。查询语言只是 DML 的一部分。

DML 和 DDL 嵌入到宿主语言(C 或者 COBOL)， 称为数据子语言(data sublanguage)

Non-Procedural Query Language:

SQL(structured Query Language)

事务管理

Transaction Management

  • 当很多用户并发存取， DBMS 必须能处理这些请求以避免冲突，如果不允许用户并发存取数据库会降低数据库的性能
  • DBMS 必须保护用户免于系统故障的影响。当系统崩溃后重新启动，所有数据能恢复到一致的状态

事务(transaction)： DBMS 中用户程序的任何一次执行，时 DBMS 的基本修改单元。

事务的并发执行

DBMS 的一个重要任务就是进行数据的并发存取调度

加锁协议 (locking protocol)是每一个事务需要遵循的规则集合。

锁是一种用来控制对数据库对象进行存取的机制：

  • 共享锁(shared lock)[读取]：可以由不同事务同时获取
  • 互斥锁(exclusive lock)[修改]：确保没有其他事务能获取该对象上的任何锁

未完成的事务和系统崩溃

DBMS 必须将那些由未完成事务产生的数据修改重数据库删除。

DBMS 要维护一个记录所有数据库写操作的日志。

先写日志(Write-Ahead Log， WAL)： 每个写操作必须在进行之前先记录在日志上。

因此 DBMS 必须能够有选择性地强制将内存中的一页写入磁盘上。

日志也可以用来确保一个成功完成的事务所发生的数据库的改变不会因为系统的崩溃而丢失。

DBMS 必须确保所有先于崩溃前完成的事务结果能够得到恢复，所有未完成事务的结果需消除。

因此可以通过周期地，强制地将一些信息写进磁盘，可以减少系统崩溃恢复所要的时间，这个周期性的操作称为检查点(checkpoint) ， 这个周期需要平衡，因为过于频繁会影响系统的正常执行速度。

数据库管理系统的结构

查询 ->查询优化器(query optimizer) -> 执行计划(execution plan)

关系操作的实现代码位于文件和存取方法层(file and access methods layer)之上，这一层支持文件存储结构

文件和存取方法代码位于缓冲区管理器(buffer manager)之上，缓冲区管理区负责把页从磁盘取入主存以响应读请求。

最底层处理存储着数据和磁盘空间管理，称为磁盘空间管理器(disk space manager)

与并发控制和恢复有关的构件：

  • 事务管理程序：加锁与释放锁， 调度事务的执行
  • 锁管理器： 跟踪对锁的请求
  • 恢复管理程序： 维护日志

与数据库打交道的人

终端用户：

  • 使用由数据库应用开发者开发的应用程序

数据库应用开发者：

  • 通过外模式存取数据

数据库管理员(DBA)：

  • 概念和物理模式的设计
  • 安全性和授权
  • 数据可用性和故障恢复
  • 数据库调优

实体联系模型

实体-联系(ER)数据模型

数据库设计与 ER 图

数据库设计过程：

  • 需求分析
    • 哪些数据需要存储
    • 哪些应用建立在上面
    • 哪些操作是频繁的
    • 性能要求
  • 概念数据库设计
  • 逻辑数据库设计
  • 模型的细化
  • 物理数据库设计
  • 应用与安全设计

ER 图

  • 实体集：矩形
  • 属性：椭圆
  • 主码：下划线
  • 部分码：虚线
  • 值域：列在属性名的旁边
  • 联系集： 菱形
  • 码约束（映射约束）：箭头
  • 参与约束：粗细线条
  • 子类：三角形
  • 聚合：虚线框
  • 弱实体：粗线矩形
    • 识别联系集：粗线菱形
    • 之间的联系：粗线箭头

实体、属性和实体集

实体(Entity)： 客观世界的一个对象，可以区别与其他对象

实体集(Entity Set)：实体的集合

属性：实体通过一组属性来描述的，一个实体集的所有实体具有相同的属性。每个相关的属性都必须确定值域。

码(Key)：一组最小的属性的集合，可以唯一确定实体集中的每个实体。

候选码(Candidate key)

主码(Primary Key)：可能存在多个候选码， 指定一个作为主码

联系和联系集

  • 联系是两个或多个实体之间的一种关联，相似的联系在一起，组成联系集。
  • 联系集也可以具有描述性属性

联系集可以是二元、三元或是多元的

参与一个联系集的实体集可以是不同也可以是相同的。

一般同一个实体的联系集具有角色（role）属性（写在连线的旁边）

ER 模型的其他特征

码约束

Key Constraints

也称映射约束，在 ER 图中用箭头表示，方向由 N 指向 1，表示每个实体只对应一个的关系

表明一个1 to N 的关系，比如每个部门只有一个经理，但是一个雇员可以作为多个部门的经理。

如果加上“每个雇员最多只能管理一个部门”，那就形成了1 to 1的联系集

参与约束

Participation Constraints

“每个部门都要求有一个经理”就是一个参与约束，ER 图中用粗线表示

那么这个联系集就成为 完全的 ，否则就是部分的（partial）

通俗来说，就是是否实体集中每一个对象都有一个对应的联系。

弱实体

Weak Entities

没有可区分的属性（主码）的实体，必须依赖与另一实体集（识别属主， identifying owner）的关联。只有（部分码）

限制：

  • 识别属主和弱实体集必须参与一个“一对多”的联系集，这个联系集成为这个弱实体的识别联系集， identifying relationship（箭头表示）
  • 弱实体集在联系集中必须是全部参与的（粗线表示）

而且关系集和实体集都要要粗线的菱形和矩形。

类层次

Class Hierarchies

对实体集中的实体进行分类，分类后继承父实体集的属性，另外也有自己的属性

  • 将父实体集进行细化（Specialization）成子类，细化就是一个标识某个实体集（超类）的子集的过程
    • 先定义超类，接着定义子类，同时加上子类的属性和相应的联系
  • 将子实体集进一步泛化（Generalization）为父类，泛化的过程一般是：先标出实体型之间的公共特征，然后生产一个新的具有这些公共特征的实体集。
    • 先定义子类，接着定义超类，包括定义超类的相应联系

根据 ISA(is a, 表示父子关系的类层次)的结构可以指定两种约束，即交迭（overlap）约束和覆盖（covering）约束。

交迭约束：决定是否允许两个子类含有相同的实体。默认实体集之间不存在交迭。

覆盖约束：决定了子类中的实体是否包括超类中的所有实体，默认情况下是不包括的。

标识子类有两个基本原因（通过特殊化和泛化）：

  • 想要键入一个描述属性，只对于实体中一个子集有意义。
  • 想要标识参与一些联系的实体集

聚合

Aggregation

聚合允许一个联系集（用一个虚线框标识）参与另一个联系集。

当需要在几个联系中表达一个联系时，就需要使用聚合。

有时候聚合可以用三元联系替代，需要一定的完整性约束来指导。

用 ER 模型进行概念数据库设计

设计 ER 图关注的问题：

  • 应该将概念模型化为实体还是属性？
    • 一般来说可以再分的作为实体，不可再分的作为属性。
  • 应该将概念模型化为实体还是联系？
    • 一般动词作为联系，名词作为实体
  • 联系集及其参与的实体集有哪些？应该使用二元联系还是三元联系？
  • 是否使用聚合

实体与属性

需要建立一个实体集而不是属性的情况：

  • 每个记录对应多个记录（需要用实体）（原子性原则）
  • 需要捕捉实体信息的结构，即需要从实体来查询对应的记录的时候。这个东西需要细分，提供细节的查询，则需要使用实体（因为属性的不可分的）

在一些模型的版本中，属性的值可以为集合，但是关系模型不支持这种具有集合取值的属性，当我们将这种集合属性转化为关系模型的时候，与把这个属性看作一个实体比较类似。

实体与联系

  • 如果联系中标识的信息比较复杂，则需要使用实体来表示
  • 一个联系中的某个属性如果需要累计计算的话，则需要使用实体来表示这个联系。
    • 这个实体作为本身关系的中间者，使用两个联系连着本来的两个实体

ER 模型的不精确性可能会导致某些潜在的实体能以被识别，而且，我们可能将属性与联系相关联，而不是与适当的实体相关联。这样的错误通常就会导致数据冗余。

二元与三元联系

二元联系：

  • 对于一些具有一对多的约束，需要使用二元联系来表示。
  • 如果存在弱实体集，那么需要使用二元联系来表示。

三元联系：

  • 例如供应商、部门、零件之间的联系（合同）， 需要一个三元联系才能准确表示
  • 需要清楚描述联系（合同）之间的属性

聚合与三元联系

主要看是否存在一个使联系集和实体集（或另一个联系集）相关联的联系。

当联系和实体之间存在某些一对多的约束，那就需要使用聚合来表示。

大型企业的概念数据库设计

  • 考虑各种用户的需求，解决那些有冲突的需求，并在最后需求分析阶段生成一个全局需求集
  • 对于不同的用户群生成不同的概念模式，然后在集成这些概念模式

统一建模语言

UML， unified modeling language

包含了更广泛的软件设计过程：

  • 业务建模
  • 系统建模
  • 概念数据库建模
  • 物理数据库建模
  • 硬件系统建模

图表：

  • 用例图， Use case：描述用户相应用户请求的系统行为，以及该行为中涉及的人。描述期望系统支持的外部功能。
  • 活动图， Activity： 显示业务处理过程中的行为流。
  • Statechart 图： 描述系统对象之间的动态交互
  • 类图， Class：类似 ER 图，不过更一般化。

关系模型

SQL(Sequel), Standard language

关系模型简介

Table： Relation

Row: Tuple

Column: Attribute

数据库由一个或多个关系共同组成， 每个关系是行和列组成的表。

关系：用于描述数据的主要结构

关系数据库：关系的集合。

构成：

  • Relation Schema 关系模式： 关系名， 每个字段(列或属性)的名字，每个字段的域。
  • Relation Instance 关系实例
    • #rows：Cardinality 基：该关系实例具有记录的数目
    • #fields : arity 源(or degree 度) ：字段的数目

关系数据库：具有不同关系名的关系 的集合

关系数据库模式：数据库中关系模式的集合

域约束：

一个关系模式可以表述成R(f1:d1,...,fn:dn)， Domi表示域di相应的取值集合

${<f_1,d_1,…,f_n:d_n>|d_i\in Dom_i,…,d_n\in Dom_n}$

  • <...>给出记录的字段
    • 例如<sid:5000,name:Dave,login:dave@cs, age:19, gpa:3.3>
  • {..} 代表一个集合
  • | 表示需要满足， 右边的表达式是每条记录的字段值必须满足的要求
  • $\in$ 表示属于

使用 SQL 创建和修改关系

数据定义语言（Data Definition Language， DDL）：支持创建，删除，修改关系表的 SQL 子集

创建一个关系表

1
2
3
4
5
CREATE TABLE Students(sid	CHAR(20),
                      name	CHAR(30),
                      login	CHAR(20),
                      age	INTEGER,
                      gpa	REAL)

插入记录

1
2
3
INSERT
INTO 	Students(sid, name, login, age, gpa)
VALUES	(53688, 'Smith', 'smith@ee', 18, 3.2)

删除记录, S 为 Students 的别名

1
2
3
DELETE
FROM 	Students S
WHERE	S.name = 'Smith'

更新已有数据的字段值

1
2
3
4
5
6
7
UPDATE	Students S
SET		S.age = S.age + 1, S.gpa = S.gpa - 1
WHERE	S.sid = 53688

UPDATE	Students S
SET		S.gpa = S.gpa - 0.1
WHERE	S.gpa >= 3.3

关系的完整性约束

Integrity Constraint， IC ，完整性约束：数据模型的重要组成部分。

码约束

用UNIQUE语句将关系表的某些字段集合声明为候选码，最多一个可以通过PRIMARY KEY声明为主码

CONSTRAINT 命名一个约束，当违反约束时，会返回约束名，用于定位错误。

1
2
3
4
5
6
7
CREATE TABLE Students ( sid		CHAR(20),
                      	name	CHAR(30),
                      	login	CHAR(20),
                      	age		INTEGER,
                      	gpa		REAL,
                      	UNIQUE	(name, age),
                      	CONSTRAINT	StudentsKey PRIMARY KEY(sid))

外码约束

一个表的外码必须指定另一个表的主码

外码也可以指向本关系。

也可以用特殊值null处理

1
FOREIGN KEY(sid) REFERENCES Students

一般约束

  • 取值范围约束
  • 主码约束
  • 外码约束

一般约束由数据库系统以表约束或者断言的形式支持的，当一个表修改时，需要检查其他表是否违反约束。

完整性约束的强制执行

ON DELETE/UPDATE:(在删除/更新时)

  • ON ACTION: 违反约束时操作被拒绝执行
  • CASCADE: 当外键绑定的记录被删除，那么对应的记录也会被删除。当外键绑定的记录的主键被修改，那么对应的外键也会被修改
  • SET DEFAULT: 当外键绑定的记录被删除，相应的记录会重新指向一个默认的记录
  • SET NULL: 同上，被设置为 NULL

例如：

1
2
3
FOREIGN KEY (sid) REFERENCES Students,
			ON DELETE CASCADE,
			ON UPDATE NO ACTION

事务与约束

约束可以在事务执行时检查约束，也可以在事务执行完才检测。

1
SET CONSTRAINT ConstraintFoo DEFERRED
  • DEFERRED: 推迟 :alarm_clock:
  • IMMEDIATE: 立即执行 :ok_hand:

查询关系数据

数据访问、存取机制、 查询语言

1
2
3
SELECT	*
FROM	Students S
WHERE	S.age < 18

S 为 Students 的重命名

1
2
3
SELECT	S.name, S.login
FROM	Students S
WHERE	S.age < 18

通过 Select 可以选取记录的部分字段值。

1
2
3
SELECT	S.name, E.cid
FROM	Students S, Enrolled E
WHERE	S.sid = E.sid AND E.grade = 'A'

可以将两个表组合起来查询。

逻辑数据库设计：从 ER 模型到关系模型

从实体集到关系表

1
PRIMARY KEY (ssn)

说明主码

从联系集（不包括约束）到关系表

  • 参与实体的主码属性，作为外码字段
  • 联系集的描述属性作为一个属性
  • 联系集中的非描述属性集可以作为关系的超码，如果联系集没有码约束，那么这个属性集就成为一个候选码。
  • 当外码的字段名和被应用的字段名称不同时，需要明确给出被引用字段名
1
FOREIGN KEY(supervisor_ssn) REFERENCES Employees(ssn)

转换带码约束的联系集

在具有一对多关系中，可以用“一”的实体作为联系集的主码。

也可以把该实体集与联系集都写入一个关系表中。

转换带有参与约束的联系集

带有参与约束的联系集，一般外码都是NOT NULL

如果不使用 SQL 提供的表约束和断言功能，许多参与约束都无法表达。

一般为保证参与约束，我们可以通过将某个值设为指向另一个表的外码来得到，但是这个外码如果不是那个表的候选码，那么就不是一个合法车外码约束。

因此我们需要使用断言，要求某一个表的某个值必须都出现在另一个表的某个记录中，并且另一个表的这个值不允许为空。

转换弱实体集

一般与联系集联合成一个关系表

转换类层次

有两种方法：

  • 映射成不同的关系，子关系包含父类关系的主码
  • 只为子类创建不同的关系

转换带聚合的 ER 图

创建一个关于聚合和联系的关系，包含三者的主码和联系的属性。

视图简介

生成一个视图：

1
2
3
4
CREATE VIEW B-Students (name, login, course) -- 如果忽略括号里的就继承字段名
		AS	SELECT	S.sname, S.sid, E.cid
			FROM	Students S, Enrolled E
			WHERE	S.sid = E.sid AND E.grade = 'B'

视图、数据独立性和安全

通过使用视图定义外部模式中的关系，可以对应用隐藏数据库概念模式的变化

为用户提供某些定义视图，可以隐藏某些信息

视图的更新

视图可以适应用户对数据库的不同需求。

通过修改原来的关系的数据来修改视图

删除/ 修改 关系表和视图

向关系Students添加一个字段maiden-name ：

1
2
ALTER TABLE Students
		ADD COLUMN maiden-name CHAR(10)

添加后其值为null

通过ALTER TABLE 也可以向删除字段，添加或删除该表上的完整性约束。

关系代数和演算

SQL 语言：parse（编译）-> 关系代数

利用关系演算，查询只需要描述说要的答案而不需要指出答案是如何找出来，这种非过程化的形式是说明性的（declarative）。是形式化的查询语言。

预备知识

查询的输入和输出都是关系，对输入的实例进行求值，同时产生出输出关系的一个实例。

  • 使用字段名指示字段（更加易读）
  • 按照统一的循序列出给定关系的所有字段，通过相对位置引用字段（更加方便，不必为所有中间关系实例指定名字）

关系代数

关系的本质就是集合。

关系代数是与关系模型相关的两种形式化查询语言之一。

代数的过程化特性使得能够将关系代数表达式看成是查询求值的处方或计划

关系系统就是使用代数表达式来表示查询求值计划的。

五大基本操作符

  • Selection： 选择行的一个子集（水平）
  • Projection： 投影列（垂直）
  • Cross-product： 把两个关系进行组合
  • Set-difference：集合的差，Tuples in r1， but not in r2
  • Union：Tuples in r1 or in r2.

选择与投影

$\sigma _{rating>8} (S2)$

选择条件是项的布尔组合， 通常为 属性 op 常量 或 属性1 op 属性2 ， 对属性的引用可以通过位置或名字。

$\pi _{sname, rating} (S2)$

$\pi$ 是默认去重的（集合里面没有重复元素），可以使用扩展关系代数保留重复

可以混合使用$\pi _{sname, rating} （\sigma _{rating>8}(S2))$

集合操作

两个关系要相容：

  • Same number of fields。 相同的字段数
  • ‘Corresponding’ fields have the same type. ，从左到右，相应的字段取值范围相同

上面的定义并没有使用字段名，如果是$R \bigcup S $ 默认从 R 继承名字

集合标准操作：

  • 并（union）$\bigcup$
    • $R \bigcup S$返回一个包含关系实例 R 或者 S 中的所有元组的关系实例.
  • 交（intersection）$\bigcap$
    • $R \bigcap S = R - (R-S)$
  • 差（set-difference）$-$
  • 叉积，笛卡儿积（ross-product）$\times$

重命名

$\rho (R(\overline {F}),E)$ ， 可以将任意一个关系代数表达式E变成一个新的关系实例R

$\overline {F}$ 是项的列表，其形式为 $oldname \rightarrow newname$ 或 $position \rightarrow newname$

连接

合并两个或多个关系是信息。可以定义为先叉积，在进行选择和投影。

条件连接

$S1 \bowtie _{S1.sid < R1.sid} R1$

相等连接

$S1 \bowtie _{S1.sid = R1.sid} R1$

自然连接

$S1\bowtie R1$

规定 R 和 S 的所有同名字段都相等，省略连接条件，如果没有想吐的属性，就相当于叉积。实际上是一个相等连接

除

$A/B = \pi _x (A)-\pi _x ((\pi _x (A) \times B) - A)$

关系 A 只有字段 x 和 y，B 只有字段 y

除操作定义为如下所有 x 的集合：对面 B 中每个元组 y，在 A 中都有一个<x,y>与之对应

优化

原则：总是先做选择。

Query
Find the names of sailors who have reserved a red or green boats / or 在选择过程中使用 sid 而不是 sname，因为 sname 不是主码
Find the names of sailors who have reserved at least two boats 需要使用重命名，然后通过叉乘并选出相同 sid 不同 bid 的元组
Find the names of sailors who have reserved all boats 使用除法 sid/bid 实现 all

关系演算

关系代数是过程化的，关系演算是非过程化的或是说明性的。

关系演算的变形

  • 元组关系运算 （Tuple Relational Calculus， TRC）， 变量以关系的元组为值。
  • 域关系演算 （Domain Relational Calculus， DRC）， 变量以关系中的字段取值范围为值。

元组关系演算

TRC

${T \ |\ p(T)}$

T: 元组变量

p(T): 描述 T 的公式

TRC 查询的语法

原子公式：

  • $R \in Rel$
  • $R.a \ op \ S.b$
  • $R.a \ op \ constant, or \ constant \ op \ R.a$

递归定义为以下形式：

  • 任何原子公式
  • $\overline{p}, p \bigvee q, p \bigwedge q, p \Rightarrow q$
  • $\exists R(p(R)), R是元组变量$
  • $\forall R(p(R)), R是元组变量$

如果公式没有被一个量词限定，那么该变量是自由的。

${T \ |\ p(T)}$， 其中 T 就是公式 p 中唯一的自由变量

  • $\exists R \in Rel(p(R))$ 表示 $\exists R (R\in Rel \bigwedge p(R))$
  • $\forall R \in Rel(p(R))$ 表示 $\forall R (R \in Rel \Rightarrow p(R))$

域关系演算

DRC

一个域变量的取值范围就是某个属性的取值范围。

形式：

${<x_1, x_2,…,x_n> |\ p(<x_1, x_2,…,x_n>)}$

类似 TRC, 把集合换成具体的字段名字，属性用对应的名字代替。

代数与演算的表达能力

表达能力是相同的

Unsafe queries

注意区分：

找出所有预定红色船只的水手->连接 / 找出预定所有红色船只的水手 ->除法

SQL： 查询、约束与触发器

概述

两种子语言

  • DML， 数据操作语言：数据查询，插入，删除，修改
  • DDL， 数据定义语言：表和视图的创建、删除、修改，权限

特性：

  • 触发器
  • 高级完整性约束
  • 嵌入式：从宿主语言调用 SQL 代码
  • 动态 SQL：允许在运行时构建查询
  • 客户-服务器执行和远程数据库存取
  • 事务管理
  • 安全保证
  • 高级特性：面向对象特性、递归查询、决策支持查询。

Query Semantics

  • FROM: computes cross products of tables
  • WHERE: check condisitions, discard tuples that fail
  • SELECT: delete unwanted fields
  • DISTINCT(optional):eliminate duplicate rows
  • Prbably the least efficient way to compute a query
    • Query optimizer(优化) will find more efficient ways to get the same answer

基本 SQL 查询形式

基本查询形式

1
2
3
4
5
6
7
SELECT [DISTINCT] select-list
FROM	from-list
WHERE	qualification

SELECT	S.sname
FROM 	Sailors S, Reserves R
WHERE	S.sid = R.sid

DISTINCT: 结果不包含重复的行

Select 命令中的表达式和字符串

1
2
3
4
5
6
7
8
9
10
11
SELECT 	S.age-5 AS age1, S.age*2 AS age2 -- 计算列
FROM	Sailors S
WHERE	S.sname='dutin'

SELECT 	S1.sname AS name1, S2.sname AS name2
FROM	Sailors S1, Sailors S2
WHERE	2*S1.rating = S2.rating - 1

SELECT 	S.age
FROM	Sailoors S
WHERE	S.sname LIKE 'B_%B'

%: 代表 0 个或多个字符

_: 只代表任意一个字符

LIKE： 对于空格敏感

collation（整序）：针对字符集，用户可以指定哪个字符比其他字符小，提供灵活的字符串操作

UNION、INTERSECT 和 EXCEPT

三种集合操作符（大多数系统只支持 UNION）

  • UNION：并集
  • INTERSECT：交集
  • EXCEPT：减

其他集合操作符：

  • IN: 检查一个元素是否在给定的集合中。
  • op ANY
  • op ALL: 将一个值与给定集合中的元素用比较操作符 op 进行比较
  • EXISTS： 检查一个集合是否为空
  • NOT: 取反

UNION 默认去掉重复行，使用UNION ALL保留重复行

INTERSECT 默认保留重复行

EXCEPT 默认保留重复行

查找预定了红色或绿色船只的水手

1
2
3
4
5
6
7
SELECT S.sname
FROM Sailor S, Reserve R, Boats B
WHERE S.sid = R.sid AND R.bid = B.bid AND B.color = 'red'
UNION
SELECT Sailor S
FROM Sailor s, Reserve R, Boats B
WHERE S.sid = R.sid AND R.bid = B.bid AND B.color = 'green'

查找预定了红色和绿色船只的水手（注意 intersection 的问题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
SELECT S.sname
FROM Sailor S, Reserve R, Boats B
WHERE S.sid = R.sid AND R.bid = B.bid AND B.color = 'red'
INTERSECT
SELECT S.sname
FROM Sailor S, Reverse R, Boats B
WHERE S.sid = R.sid AND R.bid = B,bid AND B.coclor = 'green'
-- 出现问题：因为sname不是主码，所以可能出现其中一个人预定红色船只，另一个预定绿色船只，结果名字出现在其中

-- 正确应该采用嵌套查询
SELECT S.sname
FROM Sailors S, Reserves R, Boats B
WHERE S.sid = R.sid AND R.bid = B.bid AND B.color = 'red' AND S.sid IN(
	SELECT S2.sid
    FROM Sailors S2,Boats B2, Reserves R2
    WHERE S2.sid = R2.sid AND R2.bid = B2.bid AND B2.color = 'green'
)

-- self join
SELECT R1.sid
FROM Reserve R1, Boat B1,
	Reserve R2, Boat B2
WHERE R1.sid = R2.sid AND R1.bid = B1.bid AND B1.color = 'red'
		AND R2.bid = B2.bid AND B2.color = 'green'

找出没有预定船只的水手

1
2
3
4
5
6
SELECT S.sid  //sid!!
FROM Sailor S
EXCEPT
SELECT S.sid
FROM Sailor S, Reserve R
WHERE S.sid = R.sid

嵌套查询

找出预定 103 船的水手名字

1
2
3
4
5
SELECT 	S.sanme
FROM	Sailors S
WHERE 	S.sid IN (SELECT 	R.sid
                  FROM		Reserves R
                  WHERE		R.bid = 103)

相关嵌套查询

Correlated Nested Queries

ANY / ALL

1
2
3
4
5
6
SELECT 	S.sname
FROM	Sailors S
WHERE	EXISTS(SELECT	*
               FROM		Reserves R
               WHERE	R.bid=103
              			AND R.sid = S.sid)

子查询依赖于当前行 S。对于前行 S 都需要重新进行子查询

内外行不独立

集合比较操作

Set-Comparison Operators

找出等级比某个Horatio 还高的水手

1
2
3
4
5
SELECT	S.sid
FROM	Sailors S
WHERE 	S.rating > ANY (SELECT 	S2.raing
                        FROM	Sailors S2
                       	WHERE	S2.sname='Horatio')

>= ALL : 表示最高

IN 和 NOT IN 与=ANY 和<>ANY 等价

1
2
3
4
5
6
SELECT S.sid
FROM Sailors s
WHERE S.rating >= ALL(
	SELECT S2.rating
    FROM Sailors S2)
)
Operation Meaning
IN 是否在里面
UNION 并集
INTERSECT 交集
EXCEPT 相当于减
EXIST 集合是否为空
NOT 取反
ANY 某一个
ALL 所有
AS 重命名

NOT EXIST 如果为空则选择 S

1
2
3
4
5
6
7
8
SELECT S.sname
FROM Sailors S
WHERE NOT EXIST((SELECT B.bid
                FROM Boats B)
               EXCEPT
               (SELECT R.bid
               FROM Reserves R
               WHERE R.sid = S.sid))

ORDER BY column [ASC|DESC]: 排序

聚集操作符

Aggregate operations

  • COUNT([DISTINCT] A) : A 列中所有（不同）值的数目
  • SUM([DISTINCT] A) : A 列中所有（不同）值的总和
  • AVG([DISTINCT] A): A 列中所有（不同）值的平均值
  • MAX(A): A 列中的最大值
  • MIN(A): A 列中的最小值

GROUP BY 和 HAVING 子句

1
2
3
4
5
6
7
8
9
10
SELECT [DISTINCT] select-list
FROM from-list
WHERE qualification
GROUP BY grouping-list
HAVING group-qulification

-- 对于每个等级，找出最年轻的水手的年龄
SELECT 		S.rating, MIN(S.age)
FROM		Sailors S
GROUP BY 	S.rating
1
2
3
4
5
SELECT COUNT(*)
FROM Sailors S

SELECT COUNT(DISTINCT S.sname)
FROM Sailors S

group-qualification in the HAVING clause must have a single value per group

Key Word: For Each…

ATTENTION: 只有在 GROUP BY 的列中才能有 HAVING 的内容

HAVING 决定了给定分组是否产生一个结果行

空值

使用空值的比较

比较操作符：

IS NULL

IS NOT NULL

逻辑连接运算 AND、OR 和 NOT

一旦有了空值，那么需要使用 true, false, unknown 表示逻辑连接运算的结果

SQL 构造符的作用

当记录中含有空值的话， 一些数学操作符都将返回空，但是使用一些聚集操作符，空值可能会引起一些预料不到的行为。

COUNT(*) 像其他值一样处理空值

COUNT, SUM, AVG, MIN, MAX, DISTINCT 只是简单地抛弃空值。

禁止使用空值

定义的时候指定NOT NULL

JOIN 连接

1
2
3
4
5
SELECT (column_list)
FROM  table_name
  [NATURAL][INNER | {LEFT |RIGHT | FULL } OUTER] JOIN table_name
    ON qualification_list
WHERE …

自然连接：公共属性相等

Explicit join semantics needed unless it is an INNER join

(INNER is default)

INNER JION

Only rows that match the qualification are returned.

Full JION

LEFT OUTTER JION 左外连接 连接+左未连接

RIGHT OUTTER JION

Full Outer Join returns all (matched or unmatched) rows from the tables on both sides of the join clause

1
2
3
SELECT s.sid, s.name, r.bid
  FROM Sailors s INNER JOIN Reserves r
  ON s.sid = r.sid

Returns only those sailors who have reserved boats.

概念求解

The cross-product of relation-list is computed, tuples that fail qualification are discarded, `unnecessary’ fields are deleted, and the remaining tuples are partitioned into groups by the value of attributes in grouping-list

HAVING 的参数必须为聚合操作的参数或者在分组列表中

视图创建

1
2
3
4
5
6
7
8
CREATE VIEW  view_name
AS select_statement

CREATE VIEW Reds
AS SELECT  B.bid,  COUNT (*) AS scount
     FROM Boats B, Reserves R
     WHERE  R.bid=B.bid AND   B.color=‘red’
      GROUP BY  B.bid

访问控制

Discretionary Access Control

GRANT privileges ON object TO users [WITH GRANT OPTION]

  • Object can be a Table or a View

  • Privileges can be:

  • Select

  • Insert

  • Delete

  • References (cols) – allow to create a foreign key that references the specified column(s)

  • All

  • Can later be REVOKEd

  • Users can be single users or groups

  • See Chapter 17 for more details.

SQL 中的复杂完整性约束

单个表上的约束

CHECK

1
2
3
4
5
6
CREATE TABLE Silors(sid INTEGER,
Sname CHAR(10),
Rating INTEGER,
Agereal,
PRIMARY KEY(sid),
CHECK(rating >= 1 AND rating <= 10))

每次修改都会运行 CHECK 里面的语句检查是否为真

域约束与 DISTINCT 类型

1
2
3
4
CREATE DOMAIN ratingval INTEGER DEFAULT 0
			 CHECK (VALUE > 1 AND VALUE <= 10)

CREATE TYPE ratingtype AS INTEGER

断言： 多个表上的完整性约束

当一个约束涉及到多个表的时候，使用断言就是最适合的方法了。它可以与表分离开来，不会因为表为空而失效。

1
2
3
4
CREATE ASSERTION smallClub
CHECK(( SELECT COUNT (S.sid) FROM Sailors S)
     + (SELECT COUNT(B.bid) FROM Boats B)
     < 100)

触发器和主动数据库

触发器是一个过程，它对数据库的特定改变进行相应，并由 DBMS 自动调用。

一个触发器包括以下三个部分：

  • 事件： 激活触发器的数据库改变
  • 条件：当触发器被激活时运行的查询或检测
  • 动作：当触发器被激活且条件为真时，DBMS 要执行的过程

例子（Oracle Server 语法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
CREATE TRIGGER init_count BEFORE INSERT ON Students /* Event */
	DECLARE
		Count	INTEGER;
	BEGIN			/* Action */
		Count := 0;
	END

CREATE TRIGGER incr_count AFTER INSERT ON Students /* Event */
	WHEN (new.age < 18)
	FOR EACH ROW
	BEGIN	/* Condition; 'new' is just-inserted tuple */
		Count := count + 1;
	END

CREATE TRIGGER set_count AFTER INSTER ON Students	/* Event */
REFERENCING NEW TABLE AS InsertedTuples
FOR EACH STATEMENT
	INSERT
		INTO StatisticsTuple (ModifiedTable, ModificationType, Count)
		SELECT 'Student', 'Insert', COUNT *
		FROM InsertedTuples I
		WHERE I.age < 18

设计主动数据库

为什么触发器难以理解

因为如果一条语句触发多个触发器，那么的触发顺序是不可预测的

约束和触发器

触发器一般用于维护数据库的一致性，应该优先考虑使用完整性约束（如外码约束）

触发器可以更灵活地维护数据的完整性

第三部分 存储与索引

存储与索引概述

文件组织： 单文件存储在磁盘上时，组织文件中记录的方法。每一种文件组织都会使得某些操作的效率很高而另一些操作效率很低。

索引技术可以帮助我们以多种方式来访问一个记录集合，并有效地支持各种类型的数据结构。

外部存储上的数据

页 I/O 的代价代表了典型的数据库操作的代价。

磁盘时最重要的外存设备。按照物理顺序访问可以减少读取时间。

磁带时顺序访问设备。

文件每一个记录都有一个唯一的标识符，记录 id，rid。包含一个包含该记录在磁盘上的地址的属性。

缓冲区管理器负责把数据读入内存和写入磁盘。

磁盘上的空间由磁盘空间管理器来管理。

三种文件类型

Heap files: Suitable when typical access is a file scan retrieving all records.

Sorted Files: Best for retrieval in search key order, or only a “range” of records is needed.

Clustered files

文件组织与索引

最简单的文件结构：无序文件（堆文件）unordered file / heap file

索引是在磁盘上组织支持所有记录的检索。可以有效检索满足索引的搜索码字段上的搜索条件的记录。可以建立多个索引。An index is a data strucvture that organized data records on disk to optimize certain kinds of retrieval operations 数据检索

数据项指代存储在索引文件中的记录

Data entry to refer to the records stored in an index file. With 搜索码值serach value k

索引三种方式：

  • 数据项 k*就是一个真实的数据记录（只允许一个）聚簇索引 索引是聚簇文件 clustered file
  • 数据项是一个<k, rid> 对 数据记录按照搜索码排序时为聚簇
  • 数据项是一个<k, rid-list>对 数据记录按照搜索码排序时为聚簇

For large rid lists, data entry spans multiple blocks!

聚簇索引

clustered index

索引主要分为聚簇索引和非聚簇索引 uncluttered index

聚簇索引（只能有一个）：（表中）数据记录的顺序与这个索引的数据项顺序相同或类似。（第一种方式）

聚簇索引对于搜索的代价有很大的影响

order of data records the same as, or `close to’, order of index data entries

  • A file can be clustered on at most one search key.
  • Cost of retrieving data records through index varies greatly based on whether index is clustered or not!
  • Alternative 1 implies clustered, but not vice-versa.

主索引与次索引

主索引： 建立在包含主码的字段集合上的索引 An index on a set of fields that includes the primary key is called a primary index

如果两个数据项有相同的索引搜索码，它们就称为 重复

Two data entries are said to be duplicateds if they have the same value for the search key fieldassociated with the index

次索引可能会包含重复，Primary index is guaranteed not to contain duplicates but an index on other fields can contain duplicates. Secondary index contains.

索引数据结构

  • 基于哈希的索引

    • The records in a file are grouped in buckets, where a bucket consists of a primary page. 主页
    • The bucket to which a record belongs can be determined by applying a special function. Hash function.
    • two disk I/O
    • If don’t know the search key. We have to scan all pages in the file

  • 基于树的索引

    • 可以用搜索码值有效地定位指定范围内的所有数据项。 The structure allows us to efficiently locate all data entries with search key values in a desired range.
    • 非叶节点的平均孩子数称为树的扇出 （fan-out）The average num of children for a non-leaf node is called the fan-out
    • Fan-out n -> h^n leafs
    • The number of disk I/Os incurred during a search is equal to the length of a path from the root to a leaf, plus the number of leaf pages with qualifying I/O 次数等于从根节点到叶节点的路径长度加上满足条件的数据项的叶子页的个数

不同文件组织的比较

Scan 扫描：取出文件中的所有记录

Search with Equality Selection 等值选择型的搜索：取出满足等值选择型的所有记录

Search with Range Selection 范围选择型的搜索：取出满足一个范围选择的所有记录

Insert / Delete a record ： 插入删除记录

代价模型

  • B：当页中无浪费空间时数据页的数量
  • R：每一页的记录数
  • D：读或写一个磁盘页的平均时间（15ms）主要部分
  • C：处理一个记录的平均时间（100ns）
  • H：将哈希函数应用于一个记录（100ns）

还需考虑 CPU 的代价。还有块式访问（一次性读取连续的页）的问题。

We will ignore:

  • Sequential vs. Random I/O
  • Pre-fetching
  • Any in-memory costs

堆文件

无序的文件

  • 扫描
    • 代价：B(D+RC)
    • 总共检索 B 页，每页需要花费 D 时间来读取，而且每页的 R 个记录需要花费 C 时间来处理。
  • 等值选择型的搜索
    • 代价：0.5B(D+RC)
    • 一般需要扫描文件的一半来找到这个记录。（当不存在这个记录或者这个记录不是候选码就需要扫描全部）
  • 范围选择型的搜索
    • 代价：B(D+RC)
    • 扫描整个文件
  • 插入
    • 代价：2D+C
    • 记录总是插入在文件的末尾。
  • 删除
    • 代价：搜索+C+D
    • 当删除的记录通过 id 指定，搜索大家为 D

排序文件

Sroted file

  • 扫描
    • 代价：B(D+RC)
  • 等值选择型的搜索
    • 如果选择条件指定不是在复合码的一个字段上，那么和堆文件的代价时一样的。
    • 如果是的话，用二分法查找。在$log_2B$ 步内找出包含所要数据的第一页，然后再用二分法。代价为$Clog_2R$, 总代价为$Dlog_2B+Clog_2R$
  • 范围选择型的搜索
    • 代价：搜索代价+检索满足搜索条件的记录集的代价。
  • 插入
    • 代价：搜索代价 + B(D+RC)
  • 删除
    • 代价：搜索代价 + B(D+RC)

聚簇文件

页的占满率 Occupancy 为 67%， 物理数据页大约为 1.5B The number of physical data pages is about 1.5B

  • 扫描

    • 代价：1.5B(D+RC)

  • 等值选择型的搜索

    • 代价：$Dlog_F1.5B+Clog_2R$ (等值选择与搜索码相匹配)

  • 范围选择型的搜索

    • 和上面一样，加多了搜索直到一个不满足范围选择条件的记录的代价

  • 插入

    • 代价：搜索+写一次，$Dlog_F1.5B+Clog_2R+D$

  • 删除

    • 与插入相同

具有非聚簇树索引的堆文件

索引中叶子页的个数依赖于数据项的大小。

  • 扫描

    • 取出所有数据项代价：0.15B(D+6.7RC)
    • 检索雇员记录的代价:BR(D+C) [很高]

  • 等值选择型的搜索

具有非聚簇哈希索引的堆文件

I/O 性能的比较

索引和性能调整

The choice of indexes has a tremendous impact on system performance, and must be made in the context of the expected work land 索引选择对系统性能有很大影响

如何选择索引

  • 基于哈希的索引只对等值搜索具有较好的效果，而范围选择性能很差
  • 树索引和哈希索引都能够十分有效地支持插入删除和更新操作
  • 树索引 vs 排序文件：
    • 有效处理数据项的插入删除
    • 通过搜索吗值查找比二分法查找快 serching for a record // binary search

基于树的索引对于两者都有较好的效果，但是对于删除和插入代价比较大。

聚簇索引组织

Clustered Index Organization

对于给定的一个记录的集合，至多只能有一个聚簇索引，因为维护(maintain)起来代价非常高，而可以建立多个非聚簇索引。

只有当证实频繁的查询能从聚簇中获得好处时，才使用聚簇索引。因此不使用哈希索引为聚簇。

如果搜索码信息足够回答查询，那么就可以避免取出真正的数据记录。

1
2
3
SELECT	E.dno
FROM	Employees E
WHERE	E.age > 40

如果年龄上使用索引，如果索引时非聚簇的，那么搜索代价可能会比顺序扫描的代价还要高，如果时聚簇的，那么只需要对于顺序扫描的 10%的 I/O。

改进：

1
2
3
4
SELECT	E.dno, COUNT(*)
FROM	Employees E
WHERE	E.age > 10
GROUP BY E.dno

如果在age上条件不是很有选择性，那么久应该在dno建立一个聚簇索引， 如果age上的条件非常有选择性，那么就在age上建立一个索引（聚簇/非聚簇）

1
2
3
SELECT	E.dno
FROM	Emplopyees E
WHERE	E.hobbly = "Stamps"

改进：

1
2
3
SELECT	E.dno, COUNT(*)
FROM	Employees E
GROUP BY E.dno

复合搜索码

一个复合码索引可以支持更广范围的查询。

Trade-offs in Choosing Composite Keys

  • 一个复合码的索引可以支持更广范围的查询 range of queries
  • 任何修改了搜索码中的任何字段操作都导致复合索引的更新

Design Examples of Composite Keys

存储数据-磁盘和文件

存储层次

  • 主存储器 Primary storage：高级缓存和主存
  • 二次存储器 secondary storage： 磁盘等较慢的设备
  • 三级存储器 tertiary storage：光盘和磁带（顺序存取设备）
  • There are reasons other than ocst for storing data on secondary and tetiary storage
    • 32-bit addressing ong 2^32 bytes can be directly referenced in main memory 32 位地址寻址系统只能有 2^32 字节能直接存在主存中
    • Nonvolatile 非易失的

磁盘

Magnetic Disk

数据以磁盘块为单位存储在磁盘上 Data is stored on disk in units called disk blocks。

磁盘块是字节的一个连续序列 contiguous sequence of bytes ，是从磁盘读/写数据的单位，分布于一张或多张盘片的同心环性磁盘上。

磁道 tracks 在盘片的单面或双面(盘面 platters)上录制，相应地称盘片为单面或双面。

同一直径的所有磁道的集合称为 柱面 Tracks with the same dimameter is called bylinder （多个盘面组成）

柱面包含每个盘片表面的一个磁道，而磁盘又可以划分为扇区 Each track is divided into arcs called sector扇区

每个记录的表面都有一个磁盘头的阵列（an array of disk headers），所有磁盘头都位于各自盘片的统一位置

目前的系统至多允许一个磁盘头读/写数据，因为并行读取不能保证所有磁盘头都被精确地定位在相应的磁道上，既昂贵又容易出故障。

磁盘结构对性能的影响

Performance Implications of Disk Structure

  • Data must be in memory for the DBMS to operate on it.数据必须在内存中
  • The unit for data transfer between disk and the main memory is a block. If a single item on a block is needed, the entire block is transferred. R or W a disk block is called an I/O operation 磁盘和驻村之间数据传输的单位是块
  • Access time = seek time + rotaional delay + transfer time 存取时间= 寻道时间+旋转延迟+传输时间
  • Blocks in a file should be arranged sequentially on disk (by ‘next’), to minimize seek and rotational delay.

廉价冗余磁盘阵列(RAID)

磁盘阵列是把几个磁盘组织在一起的一种形式，以提高性能和改善存储系统的可靠性 reliability and performance 。

  • 数据划分：把数据分布在多个磁盘上，用于提高性能。
  • 冗余：用于改善可靠性。

实现数据划分和冗余相结合的磁盘阵列称为 独立磁盘冗余阵列（RAID）

// TODO

数据划分

数据划分中，数据被分为相等大小的段，并分布在多个磁盘上。段的大小称为 划分单位

数据段通常使用循环算法分布 $i\ mod\ D$

// TODO

冗余

冗余模式：

  • 汉明码
    • 从单个磁盘故障中恢复
    • 确定哪一个磁盘出现故障
  • Reed-Solomon 码
    • 两个磁盘同时出故障时恢复数据

冗余的层次

  • 0 级：不冗余
    • 最好的性能
    • 使用数据划分增加最大可用带宽 bandwidth，不维护冗余信息
    • 使用数据划分增加最大可用带宽，不维护冗余信息
    • 有效空间利用率：100%
  • 1 级：镜像
    • 最昂贵的方案
    • 在两个不同的磁盘维护数据的两份相同的拷贝
    • 不会同时写入
    • 有效空间利用率： 50%
  • 0+1 级：划分和镜像
    • 称为 10 级 RAID
    • 既划分又镜像
    • 有效空间利用率：50%
    • 读请求与 0 级相似，写请求与 1 级相似
    • 最好的写性能
  • 2 级：错误校验码 Error-Correcting Codes
    • 使用汉明码 Haming
    • 校验盘数量通常随数据盘数量对数级增长，4 个数据盘-3 个校验盘
    • 适合负载侧重与大数量读操作的系统，不适合小数据量读请求。
    • 写操作需要把 D 个块读入主存，修改 D+C 个块，然后写入磁盘，称为读-修改-写周期，比较复杂
    • 4-3 个磁盘有效利用率为 57%，10-4 个为 71%，25-5 个为 83%
  • 3 级：位交叉校验 Bit-Interleaved Parity
    • 不使用多个盘存储汉明码，只用一个校验盘存储校验信息
    • 最低可能的开销，有效利用率高
    • 性能与 2 级相似
    • NewParity = (OldData XOR NewData) XOR OldParity 不需要读 D 个磁盘块
  • 4 级： 块交叉校验 Block-Interleaved Parity
    • 使用磁盘块作为划分单位
    • 4-1，有效利用率为 80%
    • 写操作比 3 级性能有所提升
    • 任何情况下都只需要一块校验盘
  • 5 级： 块交叉分布校验 Block-Interleaved Distributed Parity
    • 把校验块均匀分布
    • 性能提高
    • 最好的冗余方案的性能
  • 6 级：P+Q 冗余
    • 使用 Reed-Solomon 码，可以恢复多个磁盘的故障
    • 需要两块校验盘
    • 读请求与大的写请求性能与 5 级类似
    • 6-2，有效利用率为 66%
    • 最高级别的可靠性

磁盘空间管理

Disk Space Management

数据库管理系统结构的最底层软件， 提供分配和回收 allocate / de-allocate 页及读/写页 read / write 的命令。

通常选择磁盘块大小作为页大小。

磁盘管理器还需提供访问连续的块的接口给较高层软件。Request for a sequence of pages best satisfied by pages stored sequentially on disk

跟踪空闲块

Keep track of free block

  • 维护一个空闲块的列表 a list of free blocks
  • 维护一个位图 maintian a bit map
    • 支持磁盘连续区域的快速识别和分配

使用操作系统的而文件系统来管理磁盘空间

建立在 OS 的文件之上

不足：

  • 失去的 DBMS 的移植性，必须依赖于某个 OS
  • 在 32 位系统中，最大只能支持 4G 的单个文件

缓冲区管理器

BUFFER Management

Buffer pool information table contains:

<frame#, pageid, pin_count, dirty>

负责在必要时把页面从磁盘取到主存的软件层。

pages can be pre-fetched several pages at a time

替换策略：确定哪些页被替代掉的策略。replacement policy

把缓冲区划分为页集a collection of pages 来管理可获得的主存，这些页集通常称为缓冲池 buffer pool 在主存中，主存页称为帧 fames，即存放页（通常驻留在磁盘或其他二级存储上的页）的槽 slot。

缓冲区管理器还维护一些簿记信息和描述帧的两个变量：pin-count和dirty

  • pin-count : 存放在某个帧中的当前页已经被请求 request 但还未释放的次数 release，即该页的当前用户数
  • dirty: 表示页从磁盘读入缓冲池后是否已经被修改 （意味着是否需要被写回）

当页被请求时，缓冲区的操作：

  • 检查缓冲池是否包含被请求的页，如果是，就把该页的pin-count加 1，如果没有，就按接下来的操作把缺页读入缓冲池中
  • 根据替换策略选择替换帧，并增加它的pin-count
  • 如果替换帧的dirty 为真，那么就把这个页写回磁盘
  • 把请求的页读入替换帧中。

最后把替代帧的（主存）地址返回给申请者

增加pin-count 计数通常称为把请求页钉pinning 在他的帧中，当调用缓冲区并申请页的代码随后又调用缓冲区并释放页时，包含请求页的帧的pin-count 将减少，称为解钉unpinning 页

当缓冲区没有空闲帧，将选择替换pin-count为 0 的帧（替换策略采用 LRU）。

如果缓冲池中没有pin-count 为 0 的页，并且需要存取不在缓冲池的页，则缓冲区管理器在对页请求做出答复之前，必须等待一些页被释放，实际上这请求可能会被放弃(abort)。

如果一个页被不同事务同时申请，加锁协议(locking protocol) 将确保每一个事物在请求读一页或修改一页时首先获得一个共享锁 shared lock 或互斥锁 exclusive lock，这样可以阻止出现冲突的修改。

缓冲区替换策略

著名的替换策略是最近最少使用策略 LRU（least recently used）

它通过在缓冲区中管理一个指向pin-count为 0 的帧的指针队列来实现。当一个帧成为替换候选时，他被加入队列尾，替换时总是选择队列头的帧。

时间替换（time replacement）是 LRU 的变体，具有比 LRU 更小的开销。

它使用current变量以环形顺序选择替换页，其中current可以是1~N， N是缓冲帧的个数。可以认为帧以环形安排，就像时钟的钟表面，current像钟臂一样在表面移动。为了近似LRU的行为，每一个帧也有一个相关的referenced位， 他在页的pin-count变为 0 时设为 true。替换时选择current指向的帧，如果帧没有选择被替换，那么current将增加。

替换时：

1
2
3
4
5
if (ping_count == o && ref bit is on){
    turn off ref bit; // 2nd change
} else if (pin_count == 0 && ref bit is off) {
    choose this page for replacement;
}

referenced 使得最近引用页将不可能被替代。

LRU 和时钟策略对于数据库系统有时候时最差的替换策略，比如在连续扩散(sequential flooding)的情况下。比如缓冲池只有 10 个帧，要扫描的文件具有 11 页，那么就需要读取文件的每一页。

其他的替换策略还有： 先入先出(FIFO) , 最近经常使用策略(MRU), 随机策略

数据库管理系统和操作系统的缓冲区管理

操作系统的虚存和数据库管理系统的缓冲区管理很类似

但是 DBMS 更能准确预测页的存取顺序或页的引用模式，而且在写回磁盘的时候需要更多的控制。

DBMS 也需要显式 explicitly 地把一页强制写回磁盘，确保磁盘上的页能够随主存的变化而变化。为了实现故障恢复的WAL协议。

For a sequential scan, pre-fetching several pages at a time is a big win! 预读取能够减少以索引存取方式实现区域扫描时的延迟

记录文件

File Of Records

页如何用于存储记录和如何被组织成逻辑集合或文件

<堆文件名，首页地址>

  • Higher levels of DBMS operate on records, and files of records.
  • FILE: A collection of pages, each containing a collection of records. Must support
    • insert/delete/modify record
    • fetch a particular record (specified using record id)
    • scan all records (possibly with some conditions on the records to be retrieved)

堆文件的实现

数据不以任何顺序排序，只是保证是通过重复请求下一个记录的方式搜索文件中的所有记录。

每个对文件的页都需要被追踪以支持扫描操作，包含空闲空间的页。

需要两个指针（页 id）用于文件簿记(bookkeeping)

页的链表

把堆文件维护成双向链表

DBMS locates the header page <Heap_file_name, Page_1_addr>

  • 删除文件会产生空槽（empty slots created by deleting a record from the heap）
  • 维护有关空槽的信息
    • 追踪空闲空间
    • 追踪空闲页
      • 维护两个双向链表（maintaining a dubly linked list of pages）。
        • A doubly linked list of full pages 满页的链表
        • A doubly linked list of pages with free space 含有空闲空间的页链表
    • 记录为变长记录，则全部在含有空闲空间的页链表上，每一页至少有一些空闲字节
    • DBMS 必须搜索并检查空闲空间链表上的页
页目录

Directory of Pages

一个目录页包含多个目录，每一个目录项指向堆文件的一页，目录项还记录页是否有空闲空间或空闲空间的数量，以确定记录是否适合存放与目录项所指向的页。

页格式

记录由<page id，slot number>标识

定长记录

Fix-Length Records

所有记录长度相同，记录槽可以是统一的，连续存放

管理方法：

  • 选择在前面的 N 个槽存放记录，当记录被删除时，把页上最后的记录移到删除后空下的槽。只需要一个偏移量来定位。如果移动的记录被外部引用那么这个方法就是不可行的（rid 包含槽号）
  • 通过使用一个比特位的数据来处理记录的删除。每个槽对应一个比特位，说明槽是否被使用。

变长记录

Variable-Length Records

最灵活的组织方式是为每一页维护一个槽目录 a dictionary of slots。每个槽由<record offset, record lenght>对组成。record offset 为指向记录的“指针”，表示从页上数据部分开始到记录的开始处的字节偏移量。删除操作就设为 -1，不能删除槽目录中的记录！！ 定位时偏移量加长度
管理空间的一种方法: 维护一个指向空闲空间开始处的指针。当页内空闲空间不够时，就通过移动记录收回之前已被删除的记录释放的空间。

删除的时候，槽不能从槽目录移除。只有当最后一个槽所指向的记录被删除，才可以移除。

因为当一个记录被插入的时候，要首先扫描槽目录是否有目前未指向任何目录的槽，如果没有才向槽目录加入新的槽。

这种方法对于需要频繁移动的定长记录也是很有用的，比如某些排序，可以提高性能。

长度也可以与记录数据保存在一起，那么槽目录只需要维护偏移量。

记录格式

RECORD FORMATS

除了存储单个的记录外，有关给定记录类型的所有公共信息（字段、字段类型）被存储在系统目录 System catalog 中。

定长记录

given address of the record, the address of a particular field can be calculated using info about the lengths of preceding fields

定长记录，地址可以计算

变长记录

两种记录方法：

  • Store fields consecutively, separated by delimiters.连续存放并设置分隔符。
  • reserve some space at the beginning of a record for use as an array of integer offsets.在记录开始处预留一些空间存放整数偏移量。
  • 第二种方法更好，增加偏移量的开销大师可以获得对任何字段的直接存取，同时也获得了处理空值的方法。Deal with null values
  • 遇到空值，字段尾部的指针设为与字段开始的指针相同。
  • 变长字段的问题：
    • 如果记录被修改，需要移动（shift all subsequent fields）所有后续字段，为修改让出空间
    • 被修改的记录可能不适合放在它所在页的剩余空间，如果用于标识记录的 rid 号包含页号，需要在页上留下转发地址(forwarding address)。如果太大需要分裂页。

树结构索引

TREE-STRUCTURE INDEXING

  • ISAM 和 B+树
    • ISAM 树
      • 静态索引结构
      • 适合文件不频繁修改的情况
      • 不适合频繁增长和缩小的数据文件
    • B+树
      • 能适应文件变化的动态结构
      • 适应于插入和删除
    • 索引项、数据项 index entry / data entry 数据项含有搜索码 k 记为 k*
      • 索引项 index entries: <search key value, page id>
      • 数据项
        • <key, record>
        • <key, rid>
        • <key, list of RIDs>
        • RID Physical Record ID = <page# ,slot#>

树索引介绍

Tree structured indexing techniques support both range seletions and equliry selections.

  • ISAM
  • B+ Tree

索引顺序存取方法

INDEXED SEQUENTIAL ACCESS METHOD（ISAM）

每个树节点时一个磁盘页，所有的数据存在叶子页。

如果超过一页，需要分配额外的溢出页

删除
  • 删除数据项 k*只需要简单移走该项，如果在溢出页，溢出页在删除后为空，则移走该页。
  • 如果删除使得主页变空，则保留主页。

插入/删除值影响叶子页。

查找

代价

Cost = log F(N)
  • F = # entries / page = fanout?
  • N = # leaf pgs

溢出页与加锁考虑

Overflow Pages, Lock

解决溢出页过长的问题：在创建时为每一页保留 20%的空闲空间，一旦空闲空间被插入的记录填满，除非再次通过删除而获得释放的空间，否则只有通过完全重组文件才能消除溢出页。

B+树: 一种动态索引结构

静态的 ISAM 索引会随着文件的增长将产生很长的溢出链，从而导致很差的性能。

而 B+树结构需要动态增长和缩小，内节点用于指导搜索，叶节点包含数据项。

主要特征：

  • 树上的操作（插入、删除）能保持树的平衡
  • 特殊的删除算法可以使得除根节点外，每一个节点都将保证最小 50%的占有率 minimum occupancy of 50 percent is guaranteed
  • 搜索记录需要从根开始遍历到合适的叶子。从根到任意叶子的长度(height)都是相同的，因为树的平衡的。

在一般情况下，B+树比 ISAM 优势更明显。

  • The root node contains between 1 and 2d index entries
    • Parameter d is called the order 秩
    • The root is a leaf or has at least two children
  • Each internal node contains m (d <= m <= 2d) index entries
    • has m + 1 children
  • Each leaf node contains m (d <= m <= 2d) data entries

节点格式

有 m 个索引项的非叶子节点包含m+1个指向孩子的指针。指针$P_i$ 指向所有码值满足$K_i \leq K < K_{i+1}$ 的子树。

和 ISAM 一样，叶子节点（只有叶子节点）包含数据项。

叶子页都会以双向链表的形式连接起来，形成一个序列

chained together in a doubly linked list -> answer range queries efficiently。

搜索

  • 搜索、插入和删除算法前提是不重复
    • 不允许两个数据项有相同的码值
    • 10.7 duplicate

找到给定数据所在的叶子页节点

线性搜索 / 二分法搜索

插入

基本算法思想：通过在合适的孩子节点调用插入算法而递归地插入项。

  • 向下遍历直至它所在的叶子节点，把该项放入该叶子节点。
  • 然后返回根节点，当遇到一个节点是满的，那么就必须被分裂(split)。
  • 当节点被分裂时，一个指向分裂产生的节点的项必须插入到他的父节点，指针变量newchildentry指向该项。（copy up the middle key）
  • 如果（原来的）根节点被分裂，将创建一个新的根节点，树的高度增加一。

Copy 发生在叶子节点的分裂， Push 发生在非叶子节点的分裂

理解的分裂

  • 先分裂后插入，之后把原来页的数据项的中间值弹回父节点 （如果是叶节点则复制，否则弹上去）

每一个数据项都必须出现在叶子节点中

重分布

redistribute

在插入的时候搜索兄弟节点是否可以插入，从而在有些情况下并不需要进行分裂。

但是为了确定能否进行重分布，就必须搜索兄弟节点，如果兄弟节点时满的，则不得不进行节点分裂。这样检查会增加索引节点分裂的 I/O， 因此在实际当中不对非叶子级的项进行重分布是合算的

删除

通过项找到要删除的记录所在的叶子节点，然后删除它。

基本算法思想：通过在合适的孩子节点上调用删除算法而递归删除项。

  • 搜索到项所在的叶子节点，从那里移走项后，再原路返回到根节点。
  • 如果一个节点在删除前刚好在最小占用情况，那么删除将引起该节点的占有率降到占有率阈值之下。
  • 当上面情况发生时，或者与邻近兄弟一起重分布项，或者与兄弟合并， 以保证最小的占有率
    • 如果发生了重分布，那就必须修改他们的父节点，指向第二个节点的索引项码值必须变为第二节点的中的最小索引码值。
    • 如果发生了合并，父节点必须删除第二节点的索引项。
  • 当删除调用返回父节点，被删除的索引项将由oldchildentry指针指向。
  • 删除只需要搜索一个兄弟节点，如果该节点提供项，使用重分布，否则进行合并

重复

  • 使用溢出页处理重复
  • 跟处理其他项一样处理重复

实际的 B+树

码压缩

Key Compression

  • 增加扇出，减小高度
  • 搜索数据所需要的磁盘 I/O 次数等于高度。扇出数量最大、高度最小
  • 搜索码过大->一页能放的索引项变小->树高度变大

块加载 B+树

Bulk-Loading of a B+ Tree

重复插入过于缓慢：每一项都需要从根节点开始一直查找到合适的叶子页。叶子页不能按顺序存放。

对于父节点，左子几点的数应该小于父节点的树，右侧是等于或大于，所以应该把右侧的最小的数作为父节点

尽管一页能够放两项但是跟的两个子节点总是均匀分布

创建索引的代价

  • 创建要插入索引的数据项
  • 排序数据项
  • 排序的项建立索引
    • 代价是 R+E 次 I/O R 是记录的页数

秩的概念

在实际中，淡化秩的概念，使用物理空间标准代替

索引项的数量大于叶子页数量

rid 上插入和删除的影响

插入删除重分布影响 RID ->页内移动但不允许跨页移动，所以需要对索引进行补偿修改

基于哈希的索引

哈希是一种对等值选择非常有效的文件组织方式。

基本思想：利用哈希函数。把搜索字段的值映射到桶号，从而找到所要数据项所在的页。

类型:

  • 静态哈希
  • 动态哈希
    • 扩展哈希
    • 线性哈希

哈希索引技术不支持范围搜索，但树索引能有效支持而且等值搜索几乎与哈希一样有效。

但哈希在实现关系操作（连接）是很有用的，尤其是索引嵌套循环连接方法产生很多的等值查询。

静态哈希

包含数据项的页看作是桶的集合，每个桶中有一个主页，还可能有一些溢出页。 把溢出页加到溢出链上

静态哈希文件中的桶数是在文件创建时就已知的，理想情况下搜索需要一次 I/O，插入和删除需要两次 I/O，在有溢出页情况下代价就比较高。

一种补救方法就是阶段性“重新哈希”rehash 文件以恢复理想状态（没有溢出链，每页大概 80%占有率）

可扩展哈希

  • 使用一个指向桶的指针目录，同时仅通过目录加倍和分裂溢出桶来实现桶数的加倍 double the size of the number of buckets by doubling just the directory and splitting only he bucket that over flowed.

    可扩展哈希法的基本技术时使用哈希函数 H 得到二进制数，然后解释后 d 位数作为目录的偏移量(as an offset into the directory)，这里 d 依赖于目录的大小(size of directory)。比如一开始 d 位 2，一共有 4 个桶，当某个桶满了之后，d 位变为 3，一共有 8 个桶，d 称为全局深度(global depth)，而且我们还需要维护一个局部深度来区分是否应该增加全局深度。局部深度为 m，全局深度为 d，一共有 2^(d - m)个目录元素（directory elements）指向它。

    • 初始阶段局部深度 = 全局深度

    桶分裂不一定需要目录加倍

    定位： 计算哈希值， 截取后 d 位，查看该目录指向的桶

    插入：数据项放入所属的桶中，如果需要扩展空间，桶将会分裂，引起局部深度的增加，如果局部深度等于全局深度，并且需要分裂，目录就会加倍，增加全局深度。

    删除：如果删除后桶为空，与分裂映像（slpit image）合并（实际上会忽略）。如果每个目录元素和分裂映像都指向同一个桶，则对目录进行减半。

    问题：

    • 如果目录可以放在主存中（If the directory fits in memory, an equality selefction can be answered in a single disk access），等值选择可以在一次磁盘访问中完成，否则需要两次。
    • 偏斜的数据分布(skewed data distribution)使得目录爆炸式增长(spurts)，但是一个好的哈希函数可以解决
    • 当某些数据项具有相同的哈希值(hash coollisions)，而多个具有相同哈希值的数据项超出一页，就会产生溢出页。
    • 100MB file, 100 bytes/rec, 4K pages contains 1,000,000 records (as data entries) and 25,000 directory elements;

线性哈希

Linear Hash

不需要目录，能自然处理冲突，并对桶的分裂时机提供很多灵活性（允许折衷选择较大的溢出链以获得较高的平均空间利用率）。如果数据分布非常偏斜，溢出链可能使线性哈希性能比可扩展哈希还糟糕。

线性哈希的模式是利用哈希函数(utilizes a family of hash functions)$h_1, h_2, h_3, …$的家族，其特性是每个函数的区间都是他前辈的二倍(each function’s range is twice that of its predecessor)。

一般是通过选择一个哈希函数 h 和桶的初始数 N，然后定义$h_i(value)=h(value)mode(2^iN)$而得到的。

因此，在一个循环和任何给定点，都有已被分裂的桶，将要被分裂的桶以及分裂创建的桶。

不同之处：当插入操作触发分裂时，项插入的桶没有必要是分裂的桶，而是像静态哈希法一样，增加一个溢出页来存储新插入的数据项。

变量说明:

  • 使用Level用于说明当前的循环级， 它初始化为 0。
  • 要分裂的桶用 Next 指示，其初始值也是 0
  • Level 循环开始时候文件的桶数用$N_{Level}$表示， $N_{Lever}=N\times 2^{Level}$
  • N 为循环开始时的桶数
  • Round ends when all NR initial (for round R) buckets are split.
  • Buckets 0 to Next-1 have been split; Next to NR yet to be split.
  • Current round number is Level.
分裂的时机
  • 有新添加的溢出页
  • 当前所指的桶已满

具体过程：

  • 无论何时分裂被触发， Next 指向的桶将被分裂，哈希函数$h_{Level+1}$将在该桶（b）和他的分裂映像（$b+N_{Level}$）之间重新分布项。
  • 分裂完后，Next 加一
    • Next 以上的桶都已经被分裂，文件包含其分裂映像桶
    • Next 到$N_{Level}$之间的桶还没被分裂
  • 只有在插入的桶满了才触发分裂（Next 所在的分裂，不是插入的分裂）
  • 当$Next=N_{Level} -1$并触发分裂， 开始新的循环， Level 加 1， Next 复位 0

等值选择只需要一个磁盘 I/O，除非有溢出页，平均代价为 1.2 个磁盘访问

删除：当文件最后一个桶为空。

  • 移除它，并 Next 递减，如果 Next 为 0，则 Next 指向（当前桶数/2 - 1）的桶，并 Level 减一。
  • 也可以触发合并准则。

可扩展哈希与线性哈希的关系

相似。现行哈希从 hi 到 h(i+1)的转换对应于扩展哈希的目录加倍

  • 扩展哈希的目录加倍是一个简单的步骤，线性哈希从 hi 到 h(i+1)的转换以及桶数量的加倍，逐渐发生在循环过程中。明智次略选择将要分裂的桶，从而避免使用目录。
  • 扩展哈希有较高的桶利用率。
  • 线性哈希在均匀分布的情况下有比较低的平均代价（因为消除了目录级）
    • 偏斜分布，有一些空的或者接近空的桶会导致桶占有率较低，导致较差性能
土豪通道
0%