数据库系统概念学习笔记

2022-08-16

计软杂谈学习笔记

引言

数据库-DataBase

一个互相关联的数据的集合
大多数计算机应用程序的核心组件

数据库管理系统-DBMS（DataBase Management System）

一个互相关联的数据集合
访问这些数据的一组程序
提供了一种既方便又高效的存储和检索数据库信息的方法
由多个用户和应用程序访问

数据模型

关系模型
- 用表的集合来表述数据和数据间的联系
实体-联系（E-R）模型
- 使用称作实体的基本对象的集合，以及这些对象间的关系
半结构化数据模型
- 允许在其数据定义中某些相同类型的数据项含有不同的属性集
基于对象的数据模型
- 对关系模型进行扩展，增加了封装、方法和对象标识符等概念
键值对模型，图模型，文件模型等等…

数据抽象

物理层
- 描述数据是怎样存储的
逻辑层
- 描述数据库中存储什么数据以及这些数据建存在什么联系
- 通过少量相对简单的结构描述了整个数据库
视图层
- 只描述整个数据库的某个部分

实例（instance）和模式（schema）

类似于编程语言中的类型和变量

逻辑模式
- 数据库的整体逻辑结构
- 类似于程序中变量的类型信息
物理模式
- 数据库的整体物理结构
实例
- 数据库的实际内容
- 类似于变量的值

数据库语言

数据定义语言（DDL）

用于定义数据库模式的实现细节

数据字典（data dictionary） 包含元数据
- 数据库模式
- 完整性约束
- 授权

数据操纵语言（DML）

访问和更新数据的语言（查询语言）

过程化的 DML
- 要求用户指定需要什么数据以及如何获得这些数据
  - 关系代数（relational algebra）
声明式的（非过程化的）DML
- 要求用户指定需要什么数据，而不必指明如何获得这些数据
  类似于编程语言中的类型和变量
  - 关系演算（relational calculus）
  - SQL

SQL 查询语言

SQL 查询语言是非过程化的
SQL 不是图灵完备的
通常嵌入在一些高级语言中
应用程序通常通过以下方式访问数据库：
- 允许嵌入式 SQL 的语言扩展
- 允许将 SQL 查询发送到数据库的应用程序接口（例如 ODBC/JDBC）

数据库设计

逻辑设计 - 决定数据库模式
- 找到“好”的模式
- 业务决策—应该在数据库中记录哪些属性
- 计算机科学决策——应该拥有哪些关系模式以及属性应该如何在各种关系模式之间分布
物理设计 - 决定数据库的物理布局

数据库引擎

数据库系统被划分为多个模块，每个模块完成整个系统的一个功能
数据库系统的主要组成部分
- 存储管理器
- 查询处理器
- 事务管理

存储管理器

与 OS 文件管理器进行交互
负责数据库中数据的存储、检索和更新
存储管理器部件包括：
- 权限和完整性管理器
  - 检测时候满足完整性约束，并检查试图访问数据的用户权限
- 事务管理器
  - 保证即使系统发生了故障，数据库也保持在一致的状态
- 文件管理器
  - 管理磁盘存储空间的分配和用于表示磁盘上所存储信息的数据结构
- 缓冲区管理器
  - 负责将数据从磁盘上渠道内存中，并决定哪些数据应被缓冲在内存中
存储管理器实现了几种数据结构
- 数据文件
  - 存储数据库自身
- 数据字典
  - 存储关于数据库结构的元数据
- 索引
  - 提供对于数据项的快速访问

查询处理器

查询处理器组件包括：

DDL解释器
- 解释DDL语句并将这些定义记录在数据字典中
DML编译器
- 将查询语言中的DML语句翻译为包括一系列查询执行引擎能理解的低级指令的执行方案
查询执行引擎
- 执行由DML编译器产生的低级指令

事务管理

事务是数据库应用中完成单一逻辑功能的操作集合

关系模型介绍

关系模型

关系（relation）是无序集合，包含表示实体的属性之间的关系
域（domain）是关系的每个属性的允许取值的集合
元组（tuple）是关系中的一组属性值
- 值（通常）是原子/标量
  - 原子：一个域中的元素被认为是不可再分的单位
- 空值是每个域的成员

数据库模式（database schema）

A1, A2, …, An 是属性
R = (A1, A2, …, An ) 是一个关系模式（relation schema）
例：
- instructor = (ID, name, dept_name, salary)
- 在模式 R 上定义的关系实例 r 用 r® 表示
- 关系的当前值由表指定
- 关系 r 的元素 t 称为元组，由表中的一行表示

键

超键（superkey）
- 一个或多个属性的集合
- 将这些属性组合在一起可以在一个关系中唯一地标识出一个元组
候选键（candidate key）
- 最小超键
- 其任意真子集都不是超键
主键（primary key）
- 被数据库设计者选中来作为在一个关系中区分不同元组的主要方式的候选键
- 如果表没有定义一个主键，一些 DBMS 会自动创建一个内部主键
  - SEQUENCE (SQL:2003)
  - AUTO_INCREMENT (MySQL)
外键约束（foreign-key constraint）
- 一个关系中的值必须出现在另一个关系中
  - 引用关系（referencing relation）
  - 被引用关系（referenced relation）
- 被引用属性（集）必须是被引用关系的主键
- 是引用完整性约束的一种特例
引用完整性约束（referential integrity constraint）
- 引用关系中的任意元组在指定属性上出现的取值也必然出现在被引用关系中至少一个元组的指定属性上

关系代数（relational algebra）

检索和操作关系中的元组的基本操作
- 基于集合代数
每个算子将一个或多个关系作为其输入并输出一个新关系
- 可以将运算符链接在一起以创建更复杂的运算

选择运算（select）

从满足选择谓词的关系中选择元组的子集
$\sigma_{dept\_name="Physics"}(instructor)$
$\sigma_{dept\_name="Physics" \lor salary>90000}(instructor)$

投影运算（projection）

使用仅包含指定属性的元组生成关系
$\Pi_{ID,salary/12}(instructor)$

笛卡尔积运算（product）

从输入关系生成一个包含所有可能的元组组合的关系
$instructor \times tearches$

连接运算（join）

生成包含所有元组的关系，这些元组是两个元组（每个输入关系中的一个）与一个或多个属性的公共值的组合
$r\Join_{\theta} s=\sigma_{\theta}(r\times s)$
$instructor\Join_{instructor.ID=teaches.ID}teaches$

集合运算

交（intersection）

生成包含仅出现在一个或两个输入关系中的所有元组的关系
$r\cap s$

并（union）

生成一个只包含出现在两个输入关系中的元组的关系
$r\cup s$

差（difference）

生成一个只包含出现在第一个而不是第二个输入关系中的元组的关系
$r-s$

更名运算（rename）

为关系代数表达式的结果提供名称
$\rho_{i}(instructor)$
$\rho_{i(A_1,A_2,...)}(instructor)$

赋值运算（assignment）

将关系代数表达式分配给临时关系变量
查询可以写成由一系列赋值组成的顺序程序
$Physics \leftarrow \sigma_{dept\_name="Physics"}(instructor)$

聚合运算（aggregation）

允许在查询返回的一组值上计算函数

average, sum, min, max, count, …

$a\_id \gamma min(b\_id),sum(b\_id)(r)$

等价查询

在关系代数中编写查询的方法不止一种
$\sigma_{dept\_name="Physics"\land salary>90000}(instructor)$
$\sigma_{dept\_name="Physics"}(\sigma_{salary>9000}(instructor))$

SQL介绍

SQL组成

数据操作语言 (DML)
数据定义语言 (DDL)
- 完整性约束
- 视图定义
- 授权
数据控制语言 (DCL)
- 事务控制
- 嵌入式 SQL 和动态 SQL

数据定义

char(n)：具有指定长度n的固定长度的字符串
varchar(n)：具有最大长度n的可变长度的字符串
int：整数
smallint：小整数
numeric(p,d)：具有指定精度的定点数，这个数有p位数字（加上一个符号位），且小数点右边有p位中的d位数字
real, double precision：浮点数与双精度浮点数
float(n)：精度至少为n为数字的浮点数

建表

CREATE TABLE relation_name 
    (Attribute1 Domain1, 
    Attribute2 Domain2,
     ..., 
     Attributen Domainn,
     (integrity-constraint1),
     ...,
     (integrity-constraintk)
    );

例：

create table instructor
    (ID        varchar(5),
     name        varchar(20) not null,
     dept_name     varchar(20),
     salary        numeric(8,2),
     primary key(ID),
     foreign key(dept_name) references department
    );

更新表

-- 插入数据
INSERT INTO instructor(ID, name, dept_name, salary) VALUES('10211', 'Smith', 'Biology', 66000);
-- 删除数据，但不删除表
DELETE FROM instructor WHERE ID= '10211';
-- 更新数据
UPDATE instructor SET name='Tom', salary=55000 WHERE ID= '10211';
-- 删除表
DROP TABLE instructor;
-- 改变表结构
ALTER TABLE instructor ADD address varchar(20);
ALTER TABLE instructor DROP address;

查询语句

SELECT FROM

-- 星号查询所有的属性
SELECT * FROM instructor;
-- 使用DISTINCT关键字去重
SELECT DISTINCT name FROM instructor;
-- 使用AS关键字为属性别名
SELECT id, name, salary*1.1 AS new_salary FROM instructor;
-- 常量的使用
SELECT id, name, salary*1.1 new_salary,'Good' FROM instructor;
-- 函数的使用
SELECT id, name, now() FROM instructor;
-- 伪表的使用
SELECT now() FROM DUAL;
-- 伪表的省略
SELECT now();
-- 多表联合查询
SELECT * FROM instructor, section;
-- 使用AS关键字为表创建别名
SELECT * FROM instructor AS t1, instructor t2;
-- 为嵌套子查询表创建别名
SELECT * FROM (select id, name from instructor) t;
-- 使用NATURAL JOIN进行自然连接
SELECT * FROM instructor NATURAL JOIN teaches;

SELECT FROM WHERE

-- WHERE关键字基本使用
SELECT * FROM instructor WHERE salary>50000;
-- 使用逻辑连接词 使用LIKE关键字模糊查询，%表示匹配任意子串，_表示匹配任意单个字符
SELECT * FROM instructor WHERE salary>50000 AND name LIKE '%d_r%';
-- 使用ESCAPE改变转义符号
SELECT * FROM instructor WHERE salary>50000 AND name LIKE '%100\%'
ESCAPE '\ ';
-- 使用字符串运算函数
SELECT * FROM instructor WHERE length(name)>5;
-- 使用||管道符号连接字符串
SELECT * FROM instructor WHERE name='Go'||'ld';
-- 使用BETWEEN AND关键字
SELECT * FROM instructor WHERE salary BETWEEN 90000 AND 100000;
-- 使用元组符号进行比较
SELECT name, course_id FROM instructor, teaches WHERE (instructor.id, dept_name) = (teaches.id, 'Biology');

SELECT FROM GROUP BY HAVING

-- 使用聚集函数max,min,count,avg,sum
SELECT avg(salary) FROM instructor;
-- 使用聚集函数内嵌套DISTINCT关键字去重
SELECT count(DISTINCT id) FROM teaches;
-- 使用GROUP BY关键字分组聚集
SELECT dept_name, avg(salary) FROM instructor GROUP BY dept_name;
-- 错误写法！id既没出现在聚集函数中，也没出现在GROUP BY中
SELECT id, dept_name, avg(salary) FROM instructor GROUP BY dept_name;
-- 在HAVING关键字中可以使用聚集函数
-- 与SELECT关键字相同，出现在HAVING子句中的属性必须要么被聚集，要么出现在GROUP BY子句中
SELECT dept_name, avg(salary) FROM instructor GROUP BY dept_name
HAVING avg(salary)>42000;

SELECT FROM ORDER BY

-- 使用ORDER BY关键字对结果集排序
SELECT * FROM instructor ORDER BY name;
-- 使用DESC,ASC关键字进行降/升排序
SELECT * FROM instructor ORDER BY name DESC, salary ASC;
-- 使用属性别名进行排序
SELECT id, name, salary*1.1 AS new_salary FROM instructor ORDER BY new_salary;
-- 使用属性下标进行排序
SELECT id, name, salary*1.1 AS new_salary FROM instructor ORDER BY 3;

集合运算

-- 集合运算均自动去重，如果需要保留重复项，需要添加ALL关键字
-- 并运算
(SELECT course_id  FROM section WHERE sem = 'FALL' AND year = 2017) 
UNION
(SELECT course_id FROM section WHERE sem = 'Spring' AND year = 2018)
-- 交运算，使用ALL关键字
(SELECT course_id FROM section WHERE sem = 'Fall' AND year = 2017)
INTERSECT ALL
(SELECT course_id FROM section WHERE sem = 'Spring' AND year = 2018)
-- 差运算
(SELECT course_id FROM section WHERE sem = 'Fall' AND year = 2017)
EXCEPT
(SELECT course_id FROM section WHERE sem = 'Spring' AND year = 2018)

空值

任何涉及 null 的算术表达式的结果都是 null
- 5 + null returns null
任何涉及null的比较的结果都是unknown
- 5 < null or null <> null or null = null
unknown有关的布尔运算
- (true AND unknown) = unknwon
- (false AND unknown) = false
- (unknown AND unknown) = unknown
- (true OR unknown) = true
- (false OR unknown) = unknown
- (unknown OR unknown) = unknown
- (NOT unknown) = unknown
如果 where 子句谓词的结果为 unknown，则它的结果被视为 false
谓词IS NULL/IS NOT NULL可用于检查空值
谓词IS UNKNOWN/IS NOT UNKNOWN可用于检测unknown（区别于true和false）

1	SELECT name FROM instructor WHERE salary IS NULL;

聚集函数和空值

除了count(*)之外的所有聚集函数都忽略其输入集合的空值
空集的count运算值为0

子查询

子查询是嵌套在另一个查询中的select-from-where表达式

集合成员资格

-- IN关键字测试成员资格
SELECT DISTINCT course_id FROM section 
WHERE semester = 'Fall' AND year= 2017 AND course_id IN 
(select course_id from section where semester = 'Spring' and year= 2018);

-- NOT IN关键字测试成员资格的缺失
SELECT DISTINCT course_id FROM section 
WHERE semester = 'Fall' AND year= 2017 AND course_id NOT IN 
(select course_id from section where semester = 'Spring' and year= 2018);

-- 用于枚举集合
SELECT DISTINCT name FROM instructor WHERE name NOT IN ('Mozart', 'Einstein');

-- 用于多属性测试成员资格
SELECT count (DISTINCT ID) from takes 
WHERE (course_id, sec_id, semester, year) IN 
(SELECT course_id, sec_id, semester, year FROM teaches where teaches.ID= 10101);

集合比较

-- >,<,>=,<=,<>,= SOME关键字用于表达至少比某一个大/小/相等
SELECT name FROM instructor WHERE salary > SOME 
(select salary from instructor  where dept name = 'Biology');

-- >,<,>=,<=,<>,= ALL关键字用于表达比所有的大/小/相等
SELECT name FROM instructor WHERE salary > ALL 
(select salary from instructor  where dept name = 'Biology');

空关系测试

-- EXISTS作为在参数的子查询非空时返回true值
-- NOT EXISTS在作为参数的子查询为空时返回true值
-- 来自外层查询的相关名称可以用在WHERE子句的查询中，此时该子查询被称为相关子查询（correlated subquery）
-- 关系A包含关系B可以写成not exists(B except A)
SELECT course_id 
FROM section AS S
WHERE semester = 'Fall' AND year = 2017 AND 
EXISTS (select * 
        from section as T 
        where semester = 'Spring' and year= 2018 and S.course_id = T.course_id);

重复元组存在性测试

-- UNIQUE在作为参数的子查询没有重复的元组时返回true值
-- NOT UNIQUE在作为参数的子查询有重复的元组时返回true值
SELECT t.course_id FROM course t 
WHERE UNIQUE (select r.course_id from section r 
              where t.course_id= r.course_id and r.year = 2017);

FROM子句的子查询

-- 使用AS关键字为子查询结果起别名，并对属性进行重命名
SELECT dept_name, avg_salary FROM ( 
    select dept_name, avg (salary) 
    from instructor
    group by dept_name
    ) AS dept_avg (dept_name, avg_salary)
WHERE avg_salary > 42000;
-- 使用LATERAL关键字访问同一个FROM子句中在它前面的表或子查询的属性
SELECT name, salary, avg_salary
FROM instructor I1, LATERAL (select avg(salary) as avg_salary
                             from instructor I2
                             where I2.dept_name = I1.dept_name);

WITH子句

-- 使用WITH关键字定义临时关系
WITH max_budget (value) AS (select max(budget) from department)
SELECT department.name FROM department, max_budget
WHERE department.budget = max_budget.value;

标量子查询（scalar subquery）

SQL允许子查询出现在返回单个值的表达式能够出现的任何地方，只要该子查询只返回一个包含单个属性的元组
标量子查询可以出现在select，where和having子句中

SELECT dept_name,
    (select count(*) from instructor i
    where d.dept_name = i.dept_name)
    AS num_instructors
from department d;

删除语句

1
2
3

-- 注意运行顺序，首先执行avg(salary)并查询到所有的元组后再执行删除
DELETE FROM instructor WHERE 
 salary < (select avg (salary) from instructor);

插入语句

-- 可以在查询结果的基础上插入元组
INSERT INTO instructor
    select ID, name, dept_name, 18000 
    from student
    where dept_name = 'Music' and total_cred > 144;
    
-- 另一种插入方式
SELECT  ID, name, dept_name, 18000
INTO instructor
FROM student
WHERE dept_name = 'Music' AND total_cred > 144;

修改语句

-- 使用CASE以避免更新次序引发问题
UPDATE instructor  
    SET salary = CASE
        WHEN salary <= 100000 THEN salary * 1.05
        ELSE salary * 1.03
    END
-- 使用标量子查询
UPDATE student
    SET tot_cred = (
        select sum(credits)
        from takes, course
        where student.ID = takes.ID and
            takes.course_id = course.course_id and
            takes.grade <> 'F' and
            takes.grade is not null);

中级SQL

连接表达式

内连接（inner join）

不保留未匹配元组

外连接（outer join）

左外连接（left outer join）
- 只保留出现在左外连接运算之前（左边）的关系中的元组
右外连接（right outer join）
- 只保留出现在右外连接运算之后（右边）的关系中的元组
全外连接（full outer join）
- 保留出现在两个关系中的元组

连接条件

natural
- 自然连接
on<predicate>
- 允许在参与连接的关系上设置通用的谓词
using(A1,A2…An)
- 设定指定属性上的取值相匹配

视图

-- 使用VIEW关键字创建视图
CREATE VIEW faculty AS 
    select ID, name, dept_name from instructor;
-- 使用视图
SELECT name FROM faculty WHERE dept_name = 'Biology';
-- 视图嵌套视图
CREATE VIEW physics_fall_2017 AS
    select course.course_id, sec_id, building, room_number
    from course c, section s
    where c.course_id = s.course_id and c.dept_name = 'Physics'
        and s.semester = 'Fall' and s.year = '2017';
CREATE VIEW physics_fall_2017_watson AS
    select course_id, room_number  from physics_fall_2017
    where building= 'Watson';

视图更新

仅允许对简单视图进行更新（update、insert、delete）

from 子句只有一个数据库关系
select 子句仅包含关系的属性名，不包含任何表达式、聚集或distinct声明
任何未在 select 子句中列出的属性都可以取 null 值
查询没有 group by 或 having 子句

可以通过在视图定义的末尾插入with check option子句来防止更新不满足视图的定义

事务

提交事务（commit work）
回滚事务（rollback work）

完整性约束

not null
- 非空约束，不允许存在空值
primary key(A1,A2,…,Am)
- 主键约束，属性A1,A2,…,Am形成主键
unique( A1, A2, …, Am)
- 唯一性约束，属性A1,A2,…,Am形成超键（可以为空）
check (P)
- 指定一个谓词P，关系中的每个元组都必须满足谓词P
foreign key (…) references t(…)
- 外键约束，被指定的属性列表必须声明为被引用关系的超键，即主键约束或唯一性约束

FOREIGN KEY (dept_name) REFERENCES department
ON DELETE CASCADE     -- 级联删除
ON UPDATE CASCADE    -- 级联更新
ON DELETE SET NULL    -- 级联置空
ON DELETE SET DEFAULT    -- 级联置默认值
ON DELETE RESTRICT    -- 禁止级联

assertion
- 断言，即谓词

1 2	CREATE ASSERTION credits CHECK (NOT EXISTS(SELECT ID FROM student))

SQL固有属性

date：日历日期，包括年（四位）、月和日

1	date '2005-7-27'

time：一天中的时间，用时分秒来表示

1	time '09:00:30'

timestamp：date和time的结合

1	timestamp '2005-7-27 09:00:30.75'

interval：区间，允许在日期、时间和时间区间上进行计算

1	interval '1' day

blob/clob：二进制/字符大对象

1 2	book_review clob(10KB) image blob(10MB)

类型转换&缺省值

-- 使用CAST函数将varchar类型的ID强制转换为numeric
SELECT CAST(ID AS numeric(5))AS inst_id
FROM instructor

-- 使用COALESCE函数改变空值显示方式
-- COALESCE函数要求所有参数必须是相同的类型
SELECT ID,COALESCE(salary,0)AS salary
FROM instructor

-- 使用DEFAULT定义缺省值
CREATE TABLE student
(tot_credit NUMERIC(3,0) DEFAULT 0);

用户自定义类型（UDT）&域

-- 使用TYPE关键字自定义类型
CREATE TYPE Dollars AS numeric (12,2) FINAL;
-- 使用自定义类型
CREATE TABLE dept(name varchar (20),building varchar(15),budget Dollars);

-- 使用DOMAIN关键字自定义域，允许添加完整性约束
CREATE DOMAIN person_name char(20) NOT NULL;
-- 域允许使用CONSTRAINT关键字添加约束
CREATE DOMAIN degree_level varchar(10) 
    CONSTRAINT degree_level_test
        CHECK (value in ('Bachelors', 'Masters', 'Doctorate'));

索引

-- 基础建表，ID为主键
CREATE TABLE student (ID varchar (5), 
                      name varchar (20) not null,
                      dept_name varchar (20),
                      tot_cred numeric (3,0) default 0,
                      primary key (ID));
-- UNIQUE INDEX使用候选键作为索引
CREATE UNIQUE INDEX studentName_index ON student(name);
-- INDEX创建一般索引
CREATE INDEX studentDept_index ON student(dept_name);
-- 显示索引
SHOW INDEX ON student;
-- 删除索引
DROP INDEX studentName_index;

授权

权限授予与收回

-- 授予权限
-- GRANT <权限列表> ON <关系名或视图名> TO <用户/角色列表>;
-- WITH GRANT OPTION表示该用户可以将自己拥有的权限授权给别人
GRANT select/insert/delete/update/all privilege ON instructor TO U1, U2, U3/public WITH GRANT OPTION;
-- 表示仅可更新budget属性
GRANT update(budget) ON department TO U1;

-- 回收权限
-- REVOKE <权限列表> ON <关系名或视图名> FROM <用户/角色列表>;
-- CASCADE表示级联收权，RESTRICT表示禁止级联收权
REVOKE select ON student FROM U1, U2, U3 CASCADE/RESTRICT;

角色

-- 创建角色
CREATE ROLE teaching_assistant;
CREATE ROLE instructor;

-- 角色被授予权限
GRANT select ON takes TO teaching_assistant;
-- 角色授予角色
GRANT teaching_assistant TO instructor;
-- 角色授予用户
GRANT instructor TO Satoshi;

高级SQL

使用程序设计语言访问SQL

使用一组函数连接到数据库服务器进行通信
- JDBC
- ODBC
- 本地库
嵌入式 SQL
- SQLJ

例：

import java.sql.*;

public class jdbcSelect {
    public static void main(String[] args) {
        Connection c = null;
        Statement stmt = null;
        try {
            Class.forName("org.postgresql.Driver");
            //Open a connection
            c = DriverManager.getConnection("jdbc:postgresql://d-sketon.top:15432/newdb", "root", "root");
            c.setAutoCommit(false);
            System.out.println("Connect to database gaussdb successfully !");
            //Create a statement object
            stmt = c.createStatement();
            //Execute the statement
            ResultSet rs = stmt.executeQuery("SELECT * FROM employee;");
            while (rs.next()) {
                //Process the result set
                int id = rs.getInt("id");
                String name = rs.getString("name");
                int age = rs.getInt("age");
                String address = rs.getString("address");
                float salary = rs.getFloat("salary");
                System.out.println("ID = " + id);
                System.out.println("NAME = " + name);
                System.out.println("AGE = " + age);
                System.out.println("ADDRESS = " + address);
                System.out.println("SALARY = " + salary);
                System.out.println();
            }
            rs.close();
            stmt.close();
            c.close();
        } catch (Exception e) {
            //Exception mechanism
            System.err.println(e.getClass().getName() + ": " + e.getMessage());
            System.exit(0);
        }
        System.out.println("Operation done successfully !");
    }
}

函数和过程

-- SQL中定义的函数
CREATE FUNCTION dept_count(dept_name varchar(20))
    RETURN INTEGER
    BEGIN
    DECLARE d_count INTEGER;
        SELECT COUNT(*) INTO d_count
        FROM instructor
        WHERE instructor.dept_name = dept_name
    RETURN d_count;
    END
-- 使用函数
SELECT dept_name,budget
FROM department
WHERE dept_count(dept_name)>12;

-- SQL中的表函数
CREATE FUNCTION instructor_of(dept_name varchar(20))
    RETURNS TABLE(
        ID VARCHAR(5),
        name VARCHAR(20)
    )
RETURN TABLE
    (SELECT ID,name
    FROM instructor
    where instructor.dept_name=dept_name);
-- 使用函数
SELECT * FROM TABLE(instructor_of('Finance'));

-- SQL中的过程定义
CREATE PROCEDURE dept_count_proc(IN dept_name VARCHAR(20),out d_count INTEGER)
BEGIN
    SELECT COUNT(*) INTO d_count
    FROM instructor
    WHERE instructor.dept_name=dept_name
END
-- 使用过程
DECLARE d_count INTEGER;
CALL dept_count_proc( 'Physics', d_count);

用于过程和函数的语言结构

-- 基础复合语句
BEGIN
...
END
-- 其中包含的所有语句作为单个事务来执行
BEGIN ATOMIC
...
END

-- while语句
WHILE 布尔表达式 DO
    语句序列;
END WHILE

-- for语句
FOR 布尔表达式 DO
    语句序列;
END FOR

-- repeat语句
REPEAT
    语句序列;
UNTIL 布尔表达式
END REPEAT

-- if-then-else语句
IF 布尔表达式
    THEN 语句或复合语句
ELSEIF 布尔表达式
    THEN 语句或复合语句
ELSE 语句或复合语句
END IF

触发器

-- 操作之后触发update/insert/delete/select
CREATE TRIGGER credits_earned AFTER UPDATE grade ON takes
-- 操作之前触发update/insert/delete/select
CREATE TRIGGER credits_earned BEFORE UPDATE grade ON takes

-- 过渡行
REFERENCING NEW ROW AS nrow
REFERENCING OLD ROW AS orow
-- 过渡表（不能用于before触发器）
REFERENCING NEW TABLE AS ntable
REFERENCING OLD TABLE AS otable

-- 针对每个受影响的行执行一个操作
FOR EACH ROW
-- 正对整条SQL语句执行单个操作
FOR EACH STATEMENT

WHEN nrow.grade <> 'F' AND nrow.grade IS NOT NULL AND (orow.grade = 'F' OR orow.grade IS NULL)
BEGIN ATOMIC
    UPDATE student
        SET tot_cred=tot_cred+
        (SELECT credits
        FROM course
        WHEN course.course_id=nrow.course_id)
    WHEN student.id=nrow.id;
END;

递归查询

-- 使用WITH RECURSIVE建立递归视图
WITH RECURSIVE rec_prereq(course_id, prereq_id) as (
    select course_id, prereq_id from prereq
    union
    select rpr.course_id, pr.prereq_id,
    from rec_prereq rpr, prereq pr where rpr.prereq_id = pr.course_id
)
SELECT ∗ FROM rec_prereq;

排名

-- 使用rank函数进行排名
SELECT ID, rank() over (order by GPA desc) AS s_rank FROM grades;
-- dense_rank函数不会产生空档
SELECT ID, dense_rank() over (order by GPA desc) AS s_rank 
FROM grades;
-- nulls last/nulls first指定空值在排名中的位置
SELECT ID, dense_rank() over (order by GPA desc nulls last) AS s_rank 
FROM grades;
-- 使用partition by关键字选择在不同的分区里进行排名
SELECT ID, dept_name,
    rank() over(partition by dept_name order by GPA desc) as dept_rank
FROM grades
ORDER BY dept_name, dept_rank;

分窗

-- 前一个到后一个之间分窗
SELECT date, sum(value) over 
    (order by date rows between 1 preceding and 1 following)
FROM sales
-- 含当前行
SELECT date, sum(value) over 
    (order by date rows bewtween 1 preceding and current row)
FROM sales
-- 使用partition by关键字选择在不同的分区里分窗
-- unbounded preceding代表前面所有数据分窗
select account, date, sum(value) over
    (partition by account order by date rows unbounded preceding) as bal
FROM transaction ORDER BY account, date

使用E-R模型的数据库设计

实体-联系模型

实体集

是共享相同性质或属性的、具有相同类型的实体的集合
通过一组属性（attribute）来表示
在E-R图中用矩形来表示

联系集

是在n≥2个（可能相同的）实体集上的数学关系
在E-R图中用菱形来表示
联系集可以递归进行
联系可以具有被称作描述性属性的属性
联系集的属性在E-R图中通过未分割的矩形来表示

复杂属性

属性类型
简单和复合属性
- 简单属性不能被划分为子部分，而复合属性可以被划分为子部分
单值和多值属性
- 单值属性对于一个特定实体都只有单独的一个值
派生属性
- 这类属性的值可以从其他相关属性或实体的值派生出来

映射基数

表示一个实体能通过一个联系集关联的另一些实体的数量

一对一：A中的一个实体至多与B中的一个实体相关联，并且B中的一个实体也至多与A中的一个实体相关联
一对多：A中的一个实体可以与B中任意数量的实体相关联，而B中的一个实体至多与A中的一个实体相关联
多对一：A中的一个实体至多与B中的一个实体相关联，而B中的一个实体可以与A中任意数量的实体相关联
多对多：A中的一个实体可以与B中任意数量的实体相关联，并且B中的一个实体也可以与A中任意数量的实体相关联

E-R图中的表示方法：

用双线表示一个实体在联系集中的全部参与：

线段上可以有一个关联的最小和最大基数，用l…h的形式表示

主键

实体集

一个实体的属性取值必须可以唯一表示该实体
键（key）的概念直接适用于实体集

联系集

属性集合
$primary-key(E_1)\cup primary-key(E_2) \cup ... \cup primary-key(E_n)$
构成了联系集的一个超键

二元联系集主键的选择取决于联系集的映射基数
- 对于多对多关系，前述主键的并集是最小的超键，并被选作主键
- 对于多对一和一对多关系，“多”方的主键是最小的超键，并被选作主键
- 对于一对一关系，任意参与实体集的主键都构成最小超键，并可被选作主键

弱实体集

弱实体集的存在依赖于另一个实体集，称其为标识性实体集
使用标识性实体集的主键以及称为分辨符属性的额外属性来唯一地标识弱实体

E-R图中，通过双边框的矩形描述弱实体集，其分辨符被加上需的下划线
关联弱实体集和标识性强实体集的联系集以双边框的菱形表示
通常，弱实体集必须全部参与其标识性联系集，并且该联系是到标识性实体集的多对一联系

扩展的E-R特性

特化（Specialization）/概化（Generalization）

在一个高层实体集与一个或多个低层实体集之间存在的包含关系
重叠特化：允许一个实体属于多个特化实体集（使用两个单独的箭头）
不相交特化：允许一个实体至多属于一个特化实体集（使用单个箭头）

全部特化/概化：每个高层实体必须属于一个低层实体集
部分特化/概化：一些高层实体可以不属于一个低层实体集（默认）

聚集（Aggregation）

一种抽象，通过这种抽象，联系被视为高层实体

将E-R图转换为关系模式

强实体集的表示

强实体集的主键就作为所得到的模式的主键

具有复杂属性的强实体集的表示

复合属性
- 不为复合属性自身创建一个单独的属性
多值属性
- 为多值属性构建一个新的关系模式
派生属性
- 不在关系数据模型中显式地表示出来

弱实体集的表示

对于从弱实体集转换而来的模式，该模式的主键由其强实体集的主键与弱实体集的分辨符组合而成。除了创建主键之外，还需要在关系上建立外键约束，以保证对于表示弱实体的每个元组，都有一个表示相应强实体的元组与之对应

联系集的表示

联系集的主键属性也被用作关系模式的主键属性

模式的冗余

连接弱实体集与之对应的强实体集的联系集的模式是冗余的

模式的合并

对于多对一联系集，联系集的关系模式可以和“多”方的模式进行合并
对于一对一联系集，联系集的关系模式可以和参与联系的任何一个实体集的模式进行合并

实体-联系设计问题

E-R图中的创建错误

使用一个实体集的主键作为另一个实体集的属性
将相关实体集的主键属性作为联系集的属性
在需要多值属性的情况下使用具有单值属性的联系

使用实体集还是属性？

对于这一问题并无简单的答案。区分它们主要依赖于被建模的显示企业的结构，以及与被讨论的属性相关的语义

使用实体集还是联系集？

当描述发生在实体间的行为时建议采用联系集

二元还是n元联系集？

一个非二元的联系集总可以用一组不同的二元联系集来替代

关系数据库设计

分解

避免模式中存在信息重复问题的唯一方式是将其分解为多个模式
并非所有的模式分解都是有益的
分解过程中存在信息丢失的称为有损分解，而没有信息丢失的称为无损分解

无损分解

令R为关系模式，并令R1和R2构成R的分解
若 $\Pi_{R_1}(r) \Join \Pi_{R_2}(r) = r$ ，则说明分解是无损的
若 $r \subset \Pi_{R_1}(r) \Join \Pi_{R_2}(r)$ ，则说明分解是有损的

规范化理论

确定一个给定的关系模式是否为“良构的”
如果一个给定的关系模式不是“良构的”，则需要将其分解为许多较小的关系模式，使得每个模式都满足适当的范式。且分解必须是无损分解

使用函数依赖进行分解

符号惯例

使用希腊字母（例如 $\alpha$ ）来表示属性集
使用大写的罗马字母（例如R）来表示关系模式
使用K来表示属性集的一个超键
符号r®表示具有模式R的关系r

键和函数依赖

考虑一个关系模式r®，并且令 $\alpha \subseteq R \land \beta \subseteq R$

给r®的一个实例，如果对于该实例中的所有元组对 $t_1$ 和 $t_2$ ，使得若 $t_1[\alpha]=t_2[\alpha]$ ，则 $t_1[\beta]=t_2[\beta]$ 也成立，那么实例满足函数依赖 $\alpha \rightarrow \beta$
如果r®的每个合法实例都满足函数依赖 $\alpha \rightarrow \beta$ ，则函数依赖在模式r®上成立

键和函数依赖

如果函数依赖 $K \rightarrow R$ 在r®上成立，则K是r®的一个超键
如果函数依赖 $K \rightarrow R$ 在r®上成立，并且不存在 $\alpha \subset K,\alpha \rightarrow R$ ，则K是r®的一个候选键

平凡函数依赖

如果 $\beta \subseteq \alpha$ ，则形如 $\alpha \rightarrow \beta$ 的函数依赖是平凡的（trivial）

传递依赖

令 $\alpha$ 和 $\beta$ 为属性集，使得 $\alpha \rightarrow \beta$ 成立但 $\beta \rightarrow \alpha$ 不成立。对于 $A \in R,A \notin \alpha, A \notin \beta$ ，如果 $\beta \rightarrow A$ ，则A传递依赖于 $\alpha$

部分依赖

存在 $\alpha$ 的一个真子集 $\gamma$ 使得 $\gamma \rightarrow \beta$ ，则 $\beta$ 部分依赖 $\alpha$

函数依赖集的闭包

$F$ ：函数依赖集
$F^+$ ：能够从集合 $F$ 中推导出的所有函数依赖的集合
阿姆斯特朗公理：

自反律：若 $\alpha$ 为一个属性集且 $\beta \subseteq \alpha$ ，则 $\alpha \rightarrow \beta$ 成立
增补律：若 $\alpha \rightarrow \beta$ 成立且 $\gamma$ 为一个属性集，则 $\gamma\alpha \rightarrow \gamma\beta$ 成立
传递律：若 $\alpha \rightarrow \beta$ 成立且 $\beta \rightarrow \gamma$ 成立，则 $\alpha \rightarrow \gamma$ 成立

附加规则：

合并律：若 $\alpha \rightarrow \beta$ 成立且 $\alpha \rightarrow \gamma$ 成立，则 $\alpha \rightarrow \beta\gamma$ 成立
分解律：若 $\alpha \rightarrow \beta\gamma$ 成立，则 $\alpha \rightarrow \beta$ 成立且 $\alpha \rightarrow \gamma$ 成立
伪传递律： $\alpha \rightarrow \beta$ 成立且 $\gamma\beta \rightarrow \delta$ 成立，则 $\alpha\gamma \rightarrow \delta$ 成立

计算 $F^+$ 的过程：

F+ = F
应用自反律生成所有的平凡依赖
repeat
    for each F+中的函数依赖f
        在f上应用增补律
        将函数依赖的结果加入F+中
    for each F+中的一对函依赖f1和f2
        if f1和f2可以使用传递律进行结合
            将函数依赖的结果加入F+中
until F+不再发生变化

属性集的闭包

$\alpha$ ：属性集
$\alpha^+$ ： $F$ 下 $\alpha$ 的闭包， $F$ 下被 $\alpha$ 决定的属性集

计算 $F$ 下 $\alpha^+$ 的过程：

result := α;
repeat
    for each 函数依赖β→γ in F do
        begin
            if β⊆ result then result := result∪γ;
        end
until(result不再发生改变)

属性闭包算法的用途：

测试 $\alpha$ 是否为超键，可以计算 $\alpha^+$ ，并检查 $\alpha^+$ 是否包含 $R$ 中的所有属性
通过检查 $\beta \subseteq \alpha^+$ ，可以检查一个函数依赖 $\alpha \rightarrow \beta$ 是否成立
另一种 $F^+$ 的可替代方法

保持依赖

验证保持依赖的方式，该方式对 $F$ 中的每个 $\alpha \rightarrow \beta$ 都使用下面的过程：

result = α
repeat 
    for each 分解后的Ri
        t = (result∩Ri)+ ∩ Ri
        result = result ∪ t
until(result没有变化)

如果result包含了 $\beta$ 的所有属性，则函数依赖 $\alpha \rightarrow \beta$ 被保持

正则覆盖

从一个函数依赖的左侧删除一个属性可以使其成为更强的约束
从一个函数依赖的右侧删除一个属性可以使其成为更弱的约束

无关属性

考虑一个函数依赖集 $F$ 以及 $F$ 中的函数依赖 $\alpha \rightarrow \beta$

从左侧移除：如果 $A \in \alpha$ 并且 $F$ 逻辑蕴含 $(F-\{\alpha \rightarrow \beta\}) \cup \{(\alpha -A)\rightarrow \beta\}$ ，则属性 $A$ 在 $\alpha$ 中是无关的
从右侧移除：如果 $A \in \beta$ 并且函数依赖集 $(F-\{\alpha \rightarrow \beta\}) \cup \{\alpha \rightarrow (\beta - A)\}$ 逻辑蕴含 $F$ ，则属性 $A$ 在 $\beta$ 中是无关的

正则覆盖

$F$ 的正则覆盖集 $F_c$ 是这样的一个依赖集：

$F$ 逻辑蕴含 $F_c$ 的所有依赖
$F_c$ 逻辑蕴含 $F$ 的所有依赖
$F_c$ 中任何函数依赖都不包含无关属性
$F_c$ 中每个函数依赖的左侧都是唯一的

Fc=F
repeat
    使用合并律将Fc中任何形如α1→β1和α1→β2的依赖替换为α1→β1β2
    在Fc中寻找一个函数依赖α→β，它要么在α中要么在β中具有一个无关属性
    /*使用Fc而非F来检验无关属性*/
    如果找到一个无关属性，则将它从Fc中的α→β中删除
until(Fc不再改变)

无损分解和函数依赖

$R_1$ 和 $R_2$ 构成 $R$ 的一个无损分解的条件是，以下函数依赖中至少有一个在 $F^+$ 中：

$R_1 \cap R_2 \rightarrow R_1$
$R_1 \cap R_2 \rightarrow R_2$

即，如果 $R_1 \cap R_2$ 要么构成 $R_1$ 的超键要么构成 $R_2$ 的超键，则 $R$ 的分解就是一个无损分解

范式

BCNF范式

对于 $F^+$ 中所有形如 $\alpha \rightarrow \beta$ 的函数依赖（其中 $\alpha \subseteq R$ 且 $\beta \subseteq R$ ），下面至少有一项成立：

$\alpha \rightarrow \beta$ 是平凡函数依赖
$\alpha$ 是模式 $R$ 的一个超键

对于不属于BCNF的模式进行分解的通用规则：
若存在非平凡函数依赖 $\alpha \rightarrow \beta$ ，使得 $\alpha$ 不是模式 $R$ 的一个超键，则使用以下两个模式取代 $R$

$(\alpha \cup \beta)$
$(R-(\beta-\alpha))$

BCNF的检测

为了检查一个非平凡的依赖 $\alpha \rightarrow \beta$ 是否违反BCNF，可以计算 $a^+$ ，并且验证它是否包含了 $R$ 中的所有属性，即验证其是否是 $R$ 的一个超键
为了检查一个关系模式 $R$ 是否属于BCNF，仅需检查给定集合 $F$ 中的依赖是否违反BCNF就足够了，而不必检查 $F^+$ 中的所有依赖
为了检查 $R$ $R$ 分解后的一个关系模式 $R_i$ $R_{i}$ 是否属于BCNF，对于 $R_i$ $R_{i}$ 中属性的每个子集 $\alpha$ $α$ ，检查 $a^+$ $a^{+}$ 要么
- 不包含 $R_i-\alpha$ 的任何属性
- 包含 $R_i$ 的所有属性

BCNF分解算法

该算法所产生的分解不仅满足BCNF，而且还是无损分解：

result :={R};
done := false;
while (not done) do
    if (在result中存在一个模式Ri不属于BCNF) then
        begin
            令α→β为在Ri上成立的一个非平凡函数依赖，使得α+并不包含Ri，且α∩β=∅
            result :=(result-Ri)∪(Ri-β)∪(α,β);
        end
    else done := true;

3NF范式

对于 $F^+$ 中所有形如 $\alpha \rightarrow \beta$ 的函数依赖（其中 $\alpha \subseteq R$ 且 $\beta \subseteq R$ ），下面至少有一项成立：

$\alpha \rightarrow \beta$ 是平凡函数依赖
$\alpha$ 是模式 $R$ 的一个超键
$\beta-\alpha$ 中的每个属性 $A$ 都被包含于 $R$ 的一个候选码中（可能在不同的候选码之中）

任何满足BCNF的模式也满足3NF

3NF分解

令Fc为F的一个正则覆盖;
i := 0;
for each Fc中的函数依赖α→β
    i := i+1;
    Ri:=αβ;
if 没有一个模式Rj(j=1,2,...,i)包含R的一个候选码
    then
        i :=i+1;
        Ri:=R的任一候选码;
/*可选地删除冗余关系*/
repeat
    if 任意模式Rj包含与另一个模式Rk中
        then
        /*删除Rj*/
        Rj:=Ri;
        i :=i-1;
until 不再有可以被删除的Rj
return (R1,R2,...Ri)

1NF范式

关系模式 $R$ 的所有属性的域都是原子的

数据存储结构

文件组织

一个数据库被映射为多个不同的文件
每个文件从逻辑上被分为定长的存储单元，称为块
块是存储分配和数据传输的单位
假定：
- 没有比块更大的记录
- 每条记录被完全包含在单个块中

定长记录

在一个块中只分配它能完整容纳的最多记录的数目
当一条记录被删除时，可以选择把紧跟其后的记录移动到被删记录先前占据的空间中，但这样需要额外的块访问
在文件的开头分配特定数量的字节作为文件头，可以在文件头中存储内容被删除的第一条记录的地址作为链表的头结点，该链表通常被称为自由链表
- 在插入一条新纪录时，使用文件头所指向的记录，并改变文件头的指针以指向下一条可用记录
- 如果没有可用的空间，就把新纪录加到文件末尾

变长记录

具有变长属性的记录的表示通常包含两个部分：
- 带有定长信息的初始部分
  - 固定长度的属性被分配存储它们的值所需的字节数
  - 变长属性在初始部分中被表示为一个（偏移量，长度）对，其偏移量表示在记录中该属性的数据开始的位置，而长度表示变长属性的字节长度
- 变长属性的内容，连续存储
空位图表示记录的哪个属性是空值

分槽的页结构

每个块的开始处有一个块头，其包含以下信息：

块头中记录项的数量
块中自由空间的末尾处
一个由包含每条记录的位置和大小的项组成的数组

分配方式：

记录从块的末尾处开始在块中连续分配空间
块中的自由空间是连续的
如果一条记录被删除，它所占用的空间被释放，并且它的项被置为deleted。此外，块中位于被删除记录之前的记录被移动，使得删除产生的自由空间能被重新使用

大对象存储

大对象可以以文件形式存储在被数据库管理的一个文件系统区域中，或者作为文件结构存储在数据库中并被数据库管理

文件中记录的组织

堆文件组织

记录可存储在对应于一个关系的文件中的任何位置。记录一旦被放在特定位置，通常不会被移动

自由空间图

用于跟踪具有自由空间来存储记录的块

通常被表示成一个数组，对关系的每个块，该数组都包含一个项
每个项表示一个比例f，即在块中至少有比例f的空间是自由的
为了加速定位具有自由空间的块的人物，可以创建二级自由空间图
二级自由空间图的项存储了主自由空间图中相应项的最大值

顺序文件组织

为了高效处理按某个搜索码（任意是属性或属性的集合，无需主键或超键）的顺序排序的记录而设计

通过指针把记录链接起来，每条记录的指针指向按搜索码顺序排列的下一条记录
按搜索码的顺序，或尽可能接近搜索码的顺序物理存储记录
允许记录按排列的顺序读取

插入操作：

在文件中定位按搜索码的顺序位于待插入记录之前的那条记录
如果在这条记录所在块中有一条自由的记录，就在这里插入新的记录。否则，将新纪录插入一个溢出块之中
无论哪种情况都要调整指针，使其能按搜索码顺序吧记录链接在一起
每隔一段时间后，文件应当被重组，使其再次在物理上按顺序存放

多表聚簇文件组织

多个不同关系的记录被存储在相同的文件之中，以便减少特定连接操作的代价

聚簇码定义了哪些记录被存储在一起

B+树文件组织

和B+数索引结构有关，可以提供对记录的高效顺序访问、即使存在大量插入，删除或更新操作

哈希文件组织

在每条记录的某些属性上计算一个散列函数。函数的结果确定了记录存入文件的哪个块中

划分

许多数据库允许将一个关系中的记录划分为更小的关系，这些关系分别进行存储

数据字典存储

关系模式和关于关系的其他元数据存储在数据字典或系统目录中
其中必须存储的信息类型有：

关系的名称
每个关系中属性的名称
属性的域和长度
在数据库上定义的视图的名称，以及视图的定义
完整性约束

可以为用户保存下列信息：

用户的名称、缺省模式、密码或其他信息
关于每个用户的授权信息

可能记录关系的存储组织及每个关系的存储位置：

若关系被存在操作系统文件之中，数据字典将会记录每个关系的单个文件（或多个文件）的名称
若关系被存在单个文件中，数据字典可能将包含每个关系的记录的块记录在诸如链表那样的数据结构中

存储每个关系的每个索引的信息：

索引的名称
被索引的关系的名称
在器上定义索引的数学
构造的索引的类型

数据库缓冲区

缓冲区是主存中用于存储磁盘快递拷贝的那部分
每个块总有一份拷贝存放在磁盘上，但是磁盘上的拷贝可能比缓冲区的版本旧
负责缓冲区空间分配的子系统称为缓冲区管理器

缓冲区管理器

缓冲区管理器和操作系统虚拟存储管理器类似

被钉住的块

在一个进程从缓冲块中读取数据之前，进程在该块上执行钉住操作
缓冲区管理器不会溢出一个被钉住的块

缓冲区上的共享排它锁

数据库缓冲区管理器允许进程获取缓冲区上的共享排它锁
封锁规则：

任意数量的进程可以在一个块上同时拥有共享锁
每次只允许一个进程获得排它锁，并且当一个进程拥有排他锁时，其他进程不能拥有此块上的共享锁。
如果一个进程请求块上的排它锁，但此块已经以共享或者排他模式被封锁，那么在早期封锁被释放之前，该请求一直处于等待状态
如果一个进程请求块上的共享锁，而且此块没有被封锁或者已经被共享锁封锁，则此锁可以被授予；但是，如果另一个进程持有该块的排它锁，则共享锁只有在排他锁被释放后才能授予

获得释放封锁规则：

在一个块上执行任何操作之前，进程必须钉住这个块。随后获得封锁，且必须在对块解除钉住之前释放封锁
在从缓冲块读数据之前，进程必须获取此块上的共享锁。当完成数据读取时，进程必须释放此锁
在更新缓存块内容之前，进程必须获得此块上的排它锁；该锁必须在更新完成后释放

缓冲区替换策略

绝大多数数据库都使用了LRU策略

索引

顺序索引

顺序索引按照排好的顺序存储搜索码的值，并将每个搜索码与包含该搜索码的记录关联起来

聚集索引（主索引）
- 包含记录的文件按顺序排列
- 搜索码定义了文件的排列次序
非聚集索引（辅助索引）
- 搜索码指定的次序与文件的排列次序不同

稠密索引

对于文件中的每个搜索码值都有一个索引项

稠密聚集索引
- 索引记录包括搜索码值以及指向具有该搜索码值的第一条数据记录的指针
- 具有相同搜索码值的其余记录会顺序i存储在第一条记录之后
稠密非聚集索引
- 索引必须存储指向具有相同搜索码值的所有记录的指针列表

稀疏索引

只为某些搜索码值建立索引项

只有当关系按搜索码排列次序存储时才能使用稀疏索引
索引记录包括搜索码值以及指向具有该搜索码值的第一条数据记录的指针

多级索引

使用多级索引提升搜索效率
在原始索引上构造一个稀疏的外层索引

索引更新

插入

稠密索引
- 如果搜索码值不在索引中，则在适当位置插入该搜索码值的索引
- 如果索引项存储所有记录的指针，则在索引项中增加一条指向新记录的指针
- 如果所有向存储第一条记录的指针，则将待插入的记录放到相同搜索码值的其他记录之后
稀疏索引
- 如果插入的记录具有它所在块的最小搜索码值，则更新指向该块的索引

删除

稠密索引
- 如果待删除的记录是该特定搜索码值的唯一记录，则直接删除该索引项
- 如果索引项存储所有记录的指针，则在索引项中删除一条指向新记录的指针
- 如果所有向存储第一条记录的指针，且待删除记录是该搜索码值的第一条，则更新索引项，使其指向下一条记录
稀疏索引
- 如果待删除的记录是该特定搜索码值的唯一记录，则系统用下一个搜索码值的索引记录代替；如果下一个搜索码值已经有了索引项，则删除该该索引项
- 否则，如果该搜索码值的索引项指向待删除的记录，则更新索引项，使其指向具有相同搜索码值的下一条记录

辅助索引

辅助索引必须是稠密的，对每个搜索码值都有一个索引项，并且对文件中的每条记录都有一个指针

B+树索引

B+树索引采用平衡树结构

从树根到树叶的每条路径的长度都是相同的
树中每个非叶节点（除根节点）有⌈n/2⌉到n个孩子
根节点有2到n个孩子

B+树结构

典型的B+树节点最多包含n-1个搜索码值K1,K2,…Kn-1，以及n个指针P1,P2,…,Pn
一个节点内的搜索码值是有序存放的

叶节点

对i=1,2,…,n-1，指针Pi指向具有搜索码值Ki的一条文件记录
指针Pn指向下一个叶节点，用于高效的顺序处理
每个叶节点最多有n-1个值，最少有⌈(n-1)/2⌉个值
如果Li和Lj是叶节点且i<j，则Li中的每个搜索码值vi均小于Lj中的每个搜索码值vj
如果B+树索引比用作稠密索引，每个搜索码值都必须出现在某个叶节点中

B+树的查询

B+树的查询：

function find(v)
    C = 根节点
    while (C不是叶节点) begin
        令i = 满足 v <=C.Ki的最小值
        if 没有这样的i then begin
            令Pm = 该节点中最后一个非空指针
            置C=C.Pm
        end
        else if (v = C.Ki)  then 置C = C.Pi+1  
        else 置C = C.Pi
    end
    if 有某个i,满足 Ki = v  
        then return Pi
    else 
        return null

B+树的插入

在B+树中插入项：

procedure insert(value K, pointer P)
    if (树为空) 创建一个空的叶节点L，同时它也是根节点
    else 找到应该包含码值K的叶节点L
    if (L 具有不到n-1个码值)
        then insert_in_leaf (L, K, P)
        else begin  /* 拆分L */
        创建节点 L'
        把 L.P1 … L.Kn-1 复制到可以容纳n个（指针，码值）对的内存块T中
        insert_in_leaf (T, K, P)
        令 L'.Pn = L.Pn
        令 L.Pn = L'
        从L中删除L.P1 到 L.Kn-1
        把 T.P1 到 T.K⌈n∕2⌉ 从 T 复制到 L 中，L 以 L.P1 作为开始
        把 T.P⌈n∕2⌉+1 到 T.Kn 从 T 复制到 L'中，L'以 L'.P1 作为开始
        令 K'为 L'中的最小码值
        insert_in_parent(L, K', L')
    end

用于往B+树中插入项的辅助过程：

procedure insert_in_leaf (node L, value K, pointer P)
    if (K < L.K1) then 把P、K插入L中，紧接在L.P1前面
    else begin
            令 Ki 表示 L 中小于或等于 K 的最大值
            把P、K插入L中，紧接在L.Ki前面
    end
    
procedure insert_in_parent(node N, value K', node N')
    if (N 是树的根结点)
        then begin
       创建一个新的，包含N、K'、N'的节点R
       令R为树的根节点
       return
        end
    令 P = parent (N)
    if (P有不到n个指针) then 将 (K', N')插入 P 中，紧跟在 N 后面
    else begin   /* 拆分 P */
        将 P 复制到可以容纳 P 和 (K', N') 的内存块 T 中
        将 (K', N') 插入 T 中，紧跟在 N 后面
        删除 P 中所有项 
        创建节点 P'
        把 T.P1…T.P⌈(n+1)∕2⌉ 复制到 P
        令 K'' = T.K⌈(n+1)∕2⌉
        把 T.P⌈(n+1)∕2⌉+1…T.Pn+1 复制到 P'
        Insert_in_parent(P, K'', P')
    end

B+树的删除

procedure delete(value K, pointer P)
    找到包含(K, P)的叶节点 L
    delete_entry(L, K, P)
    
procedure delete_entry(node N, value K, pointer P)
    从 N 中删除 (K, P)
    if (N 是根节点 and N 只剩下一个子节点)
    then 使 N 的子节点成为该树的新的根节点并删除 N
    else if (N 有太少的值/指针) then begin
        令 N' 为 parent(N) 的前一个或后一个孩子节点
        令 K' 为 parent(N) 中指针 N 和 N' 之间的值
        if (N 和 N' 中的项能放入单个节点中)
            then begin /*合并节点*/
                if (N 是 N'的前一个节点) then swap_variables(N, N')
                if (N 不是叶节点)
                    then 将 K'以及 N 中所有的指针和值附加到 N'中
                    else 将 N 中所有 (Ki, Pi) 对附加到 N' 中
                    令 N'.Pn = N.Pn
                    delete_entry(parent(N), K', N);删除节点 N
                end
        else begin/*重新分配，从 N' 借来一个项*/
            if (N' 是 N 的前一个节点) then begin
                if (N 是非叶节点) then begin
                    令 m 满足：N'.Pm 是 N' 中的最后一个指针
                    从 N' 中去除 (N'.Km-1, N'.Pm)
                    插入 (N'.Pm, K') 并通过将其它指针和值右移使之成为 N 中的第一个指针和值
                    用 N'.Km-1 替换 parent(N) 中的 K'
                end
                else begin
                    令 m 满足 (N'.Pm, N'.Km) 是 N' 中的最后一个指针/值对
                    从 N' 中去除 (N'.Pm, N'.Km)
                    插入 (N'.Pm, N'.Km) 并通过将其它指针和值右移使之成为 N 中的第一个指针和值
                    用 N'.Km 替换 parent(N) 中的 K'
                end
            end
            else ...与then的情况对称...
        end
    end

非唯一性搜索码

每个码只在树中存储一次，并维护一个带有搜索码值的记录指针的桶，但会产生复杂问题
每条记录存储一次搜索码的值，但也会产生复杂问题
由于以上两个方法删除效率底下，所以大多数数据库系统中的B+树都只处理唯一性搜索码，并自动添加记录ID或其他属性以使非唯一性搜索码变得唯一

B+树扩展

B+树文件组织

不仅把B+树结构作为索引来使用，而且把它作为一种文件中记录的组织方式来使用
树的叶节点存储的是记录而不是指向记录的指针
B+树文件组织可用于存储大型对象，可将大型对象拆分成更小的记录序列并组织成B+树文件组织的形式进行存储

辅助索引和记录重分配

如果记录的位置发生了改变，存储了指向被重新分配过的记录的指针的所有赋值索引都必须被更新
B+树文件组织中节点拆分的代价及其高昂
解决方法：在辅助索引中存储主索引搜索码属性的值
该方法大大降低了由文件重组导致的索引更新的代价，但也增加了使用辅助索引访问数据的代价

对字符串的索引

可变字符串会导致不同的扇出
节点的合并或者项的重新分配取决于节点中所使用空间的比例，而不是根据节点所能容纳的最大项数
使用前缀压缩的技术可以增加节点的扇出
- 在非叶节点上存储每个搜索码值的一个前缀

B树文件索引

B树只允许搜索码值出现一次（如果它们是唯一的）
可以比相应的B+树索引使用更少的节点
需要在非叶节点中为每个搜索码包含一个额外的指针域

散列索引

桶：可以存储一条或多条记录的存储单元
- 对于内存中的散列索引，桶可以是索引项或记录的链表
- 对于基于磁盘的索引，桶可以是磁盘块的链表
- 在散列文件组织中，桶存储实际的记录
散列函数：从所有搜索码值的集合K到所有桶地址的集合B的函数
- 使用溢出链的散列索引也称为闭寻址

散列索引能高效地支持搜索码上的相等查询，但不支持范围查询

位图索引

为多码上的简单查询设计的一种特殊类型的索引
r关系在A属性上的位图索引是由A能取的每个值所对应的位图构成
每个位图都有和关系中的记录数相等数量的位
如果编号为i的记录在A的属性为vj，则值为vj的位图中第i位为1，其他所有位为0

查询处理

查询处理的基本步骤：

语法分析与翻译
优化
执行

基本概念：

带有“如何执行”注释的关系代数运算称为执行原语
用于执行一个查询的原语操作序列称为查询执行计划
查询执行引擎接收一个查询执行计划，执行该计划并把结果返回给查询

查询代价的度量

对于驻留在磁盘上的大型数据库，从磁盘访问数据I/O代价通常是最主要的的代价
当数据驻留在内存或SSD上时，I/O并不是主要代价，CPU代价也必须考虑
我们使用从存储中传输的块数以及随机I/O访问数作为估计查询执行计划的代价的两个重要因素

选择运算

	算法	代价	原因
A1	线性搜索	ts+br*tT	一次初始搜索加上br次块传输，其中br表示文件中的块数量
A1	线性搜索，码上的等值比较	平均情况ts+(br/2)*tT	因为最多有一条记录满足条件，所以一旦找到所需的记录，扫描就可以终止
A2	B+树聚集索引，码上的等值比较	(hi+1)*(tT+ts)	（hi表示索引的高度）索引搜索遍历树的高度，再加上一次I/O来获取记录；每个这样的I/O操作需要一次寻道和一次块传输
A3	B+树聚集索引，非码上的等值比较	hi(tT+ts)+ts+btT	树的每一层有一次寻道，第一个块有一次寻道。这里b是包含具有指定搜索码记录的块数，所有这些记录都是要读取的。假定这些块是顺序存储（因为是聚集索引）的叶子块并且不需要额外的寻道
A4	B+树辅助索引，码上的等值比较	(hi+1)*(tT+ts)	和聚集索引类似
A4	B+树辅助索引，非码上的等值比较	(hi+n)*(ts+tT)	（其中n是所获取记录的数量）在这里，索引遍历的代价和A3一样，但是每条记录存储在不同的块上，需要对每条记录进行一次寻道。如果n值比较大，代价可能非常昂贵
A5	B+树聚集索引，比较	hi(tT+ts)+ts+btT	和A3、非码上的等值比较的情况一样
A6	B+树辅助索引，比较	(hi+n)*(ts+tT)	和A4、非码上的等值比较的情况一样

A7（使用一个索引的合取选择）
- 用A2-A6的一种算法检索满足其中一个简单条件的记录。然后在内存缓冲区中测试是否满足其余简单条件
A8（使用组合索引的合取选择）
- 如果选择指定的是两个或多个属性上的等值条件，并且在这些属性字段的组合上存在组合索引，则可以直接搜索该索引
A9（使用标识交集的合取选择）
- 要求在各个条件所涉及的字段上都有带记录指针的索引
- 对每个索引进行扫描，以获取那些指向满足单个条件的元组的指针
- 所有检索到的指针的交集就是满足合取条件的元组的指针集合
A10（使用标识并集的析取选择）
- 扫描每个索引以获取满足单个条件的元组的指针
- 检索到的所有指针的并集就产生出指向满足析取条件的所有元组的指针的集合

排序

特指在物理上对记录进行排序

外排序-归并算法

对不能全部放入内存中的关系进行的排序称为外排序
对于外排序最常用的技术是外排序-归并算法
第一阶段，创建多个排好序的归并段

i = 0;
repeat
    读入关系的M个块或者关系的剩余部分，以较小者为准
    对关系在内存中的部分进行排序
    将排好序的数据写到归并段文件Ri中
    i= i+1
until 到达关系末尾

第二阶段，对归并段进行归并

为N个归并段文件Ri各读入一个块到内存缓冲块中
repeat
    从所有缓冲块中（按序）挑选第一个元组
    把该院足协倒数初中，并将其从缓冲块中删除
    if 任何一个归并段Ri的缓冲块为空 and not 到达 Ri 的末尾
        then 将 Ri 的下一块读入缓冲块
until 所有的输入缓冲块均为空

外排序-归并的代价计算

总共需要的归并趟数为 $\lceil log_{\lfloor M/b_b\rfloor-1}(b_r / M) \rceil$
关系外排序的块传输的总数为 $b_r (2 \lceil log_{\lfloor M/b_b\rfloor-1}(b_r / M) \rceil + 1)$
寻道磁盘的代价为 $2\lceil b_r / M \rceil + \lceil b_r / b_b \rceil (2 \lceil log_{\lfloor M/b_b\rfloor-1}(b_r / M) \rceil - 1)$

连接运算

嵌套-循环连接

for each 元组 tr in r do begin
    for each 元组 ts in s do begin
        测试元组对(tr, ts) 是否满足连接条件
        如果满足，把tr·ts加到结果中
    end
end

嵌套-循环连接算法的代价昂贵
如果其中一个关系能完全放入主存中，则应该把这个关系作为内层关系

块嵌套-循环连接

for each 块Br of r do begin
    for each 块Bs of s do begin
        for each 元组 tr in Br do begin
            for each 元组 ts in Bs do begin
                测试元组对(tr, ts) 是否满足连接条件
                如果满足，把tr·ts加到结果中
            end
        end
    end
end

在最坏的情况下，对于外层关系中的每个块，内层关系s的每个块只需读一次

索引嵌套-循环连接

若在内层循环的连接属性上有索引可用，则可以用索引查找来代替文件扫描
代价公式表明：如果两个关系上均有索引可用，通常使用元组较少的关系作为外层关系最为高效

归并-连接

用于计算自然连接和等值连接
两个关系必须均按公共属性排序
排序后连接通过与排序-归并算法中的归并阶段非常相似的处理过程来计算

代价分析

所需的块传输次数等于两个文件的块数之和 $b_r+b_s$ （假设所有Ss集合均可装入内存）
假设每个关系分配 $b_b$ 个缓冲块，则所需的磁盘寻道次数为 $\lceil b_r / b_b \rceil + \lceil b_s / b_b \rceil$

混合归并-连接

把已排序关系与B+树辅助索引的叶子项进行归并
所得到的结果文件包含已排序关系的元组和未排序关系的元组地址
将结果文件按未排序关系的元组地址进行排序，从而能对相关元组按物理存储顺序进行高效的检索

散列-连接

用于计算自然连接和等值连接
相比于归并-连接算法，将排序改为了使用散列函数
- 使用散列函数，获得两个关系对应的散列分区
- 在其中一个分区上构造内存散列索引，并使用索引嵌套-循环连接定位出所有需要连接的元组
- 进行连接

代价分析

不考虑递归分区
- 所需块传输次数 $3(b_r+b_s)+4n_h$ ，通常 $4n_h$ 可以被忽略
- 所需的磁盘寻道次数为 $2(\lceil b_r / b_b \rceil + \lceil b_s / b_b \rceil)+2n_h$ 次寻道
考虑递归分区
- 所需块传输次数 $2(b_r+b_s)\lceil log_{\lfloor M/b_b \rfloor -1}(b_s /M) \rceil +b_r + b_s$
- 所需的磁盘寻道次数为 $2(\lceil b_r / b_b \rceil + \lceil b_s / b_b \rceil) \lceil log_{\lfloor M/b_b \rfloor -1}(b_s /M) \rceil$ 次寻道

其他运算

去重

可以通过排序和散列来实现去重

投影

首先对每个元组执行投影，然后去除重复记录

集合运算

首先对两个关系进行排序，然后对每个已排序的关系扫描一次以产生结果
也可以选择使用散列，然后对每个分区扫描一次以产生结果

外连接

1. 计算相应的连接，然后将适当的元组加入连接结果中以得到外连接结果
1. 对连接算法加以修改

聚集

使用与去重相同的方法来实现

表达式执行

物化

每次将执行的结果物化到一个临时关系中
双缓冲通过并行执行CPU活动与I/O活动，允许算法执行得更快

流水线

通过将多个关系运算组成一个运算的流水线来减少临时文件数，其中一个运算的结果将传送到流水线中的下一个运算
流水线带来的好处：

消除了读和写临时关系的代价，从而减少了查询执行代价
如果一个查询执行计划的根算子及其输入被合并在流水线中，那么就可以迅速开始产生查询结果

流水线的实现

需求驱动流水线
- 系统不停地向位于流水线顶端的运算发出需要元组的请求
- 每当一个运算收到需要元组的请求时，它就计算待返回的下一个元组并返回这些元组
- 需求驱动流水线中的每个运算都可以作为迭代算子来实现，该迭代算子提供以下函数
  - open()
  - next()：每次调用返回运算的下一个输出元组
  - close()：告知迭代算子不需要元组了
生产者驱动流水线
- 各运算并不等待产生元组的请求，而是积极地生产元组
- 对于生产者驱动流水线中的每一对相邻的运算，系统会创建一个缓冲区来保存从一个运算传递给下一个运算的元组

事务

事务是访问并可能更新各种数据项的一个程序执行单元
数据库系统需要维护以下特性：

原子性：事务的所有操作在数据库中要么全部正确反映出来，要么完全不反映
一致性：以隔离的方式执行事务（没有其他事务的并发执行）以保持数据库的一致性
隔离性：尽管多个事务可能并发执行，但系统保证每个事务都感觉不到系统中有其他事务正在并发执行
持久性：在一个事务成功完成后，它对数据库的改变必须是永久的，即使出现系统故障

一个简单的事务模型

忽略插入和删除操作，采用以下两种操作来访问数据：

read(X)：从数据库把数据项X传送给一个也称为X的变量，X位于属于执行read操作的事务的主缓冲区中
write(X)：从执行write的事务的主缓冲区中把变量X的值传送给数据库中的数据项X

事务的原子性和持久性

事务必须处于以下状态之一：

活跃状态：为初始状态，当事务执行时就处于这种状态
部分提交状态：在最后一条语句被执行之后
失效状态：在发现正常执行不能再继续之后
中止状态：在事务已回滚并且数据库已被恢复到它在事务开始前的状态之后
提交状态：在成功完成之后

事务相应的状态图：

成功完成其执行的事务被称为已提交
一旦事务已经提交，撤销已提交事务所造成的影响的唯一方式是执行一个补偿事务
如果一个事务要么是提交的要么是中止的，它就被称为是已经终止的
一旦事务进入了中止状态，系统可以重启事务或杀死事务

事务的隔离性

允许并发的优点：

提高吞吐量和资源利用率
减少等待时间

在并发执行的情况下，调度应该在某种意义上等价于一个串行调度，这种调度被称为可串行化的调度

可串行化

如果I与J是由不同事务在相同数据项上执行的操作，并且其中至少有一条指令是write操作，那么I与J是冲突的
如果调度S可以经过一系列非冲突指令的交换而转换成调度S’，则称S’和S是冲突等价的
若一个调度S与一个串行调度是冲突等价的，则称调度S是冲突可串行化的
如果关于S的优先图中有环，则调度S是非冲突可串行化的；反之则是可冲突串行化的

事务的隔离性和原子性

可恢复调度

对于每对事务Ti和Tj，如果Tj读取了由Ti之前所写过的数据项，则Ti的提交操作应出现在Tj的提交操作之前

无级联调度

级联回滚
- 因单个事务失效而导致一系列事务回滚的现象称为
无级联调度
- 对于每对事务Ti和Tj都满足如果Tj读取了先前由Ti所写的一个数据项，则Ti的提交操作必须出现在Tj的这一读操作之前

事务的隔离性级别

可串行化：通常保证可串行化的执行
可重复读：只允许读取已提交的数据，并进一步要求在一个事务两次读取一个数据项期间，其他事务不得更新该数据项
已提交读：只允许读取已提交的数据，但并不要求可重复读
未提交读：允许读取未提交数据，最低隔离性级别

以上所有的隔离性级别均不允许脏写，即如果一个数据项已被另外尚未提交或中止的事务写过，则不允许再执行写操作

并发控制

基于锁的协议

锁

共享模式锁（S）：可以读但不能写
排他模式锁（X）：既可以读又能写

相容函数：

	S	X
S	true	false
X	false	false

事务通过lock-S(Q)指令来申请数据项Q上的共享锁
事务通过lock-X(Q)指令来申请数据项Q上的排它锁
事务通过unlock(Q)指令来对数据项Q解锁

两阶段封锁协议

该协议要求每个事务分两个阶段提出加锁和解锁请求：

增长阶段：一个事务可以获得锁，但不能释放任何锁
缩减阶段：一个事务可以释放锁，但不能获得任何新锁

两阶段封锁并不保证不会发生死锁，且级联回滚是可能发生的

严格两阶段封锁协议：要求事务所持有的所有排他模式锁必须在事务提交后方可释放（可防止级联回滚）
强两阶段封锁协议：要求在事务提交之前保留所有的项
锁转换
- 升级：从共享锁到排它锁
- 降级：从排它锁到共享锁

封锁的实现

锁管理器维护一个称为锁表的内存数据结构，用于记录已授予的锁和等待的请求
- 事务可以向锁管理器发出锁请求和解锁的请求
- 锁管理器针对封锁请求消息采用锁授予的消息，或采用要求事务回滚的消息来进行应答

基于图的协议

两阶段封锁的替代方案
在数据项的集合上实施一种偏序 $\rightarrow$
树型协议是一种简单的图协议
- 确保冲突可串行化以及无死锁
- 可以在较早的时候释放锁
- 不保证可恢复性和无级联性
  - 需要引入提交依赖
- 一个事务可能必须给它更新不访问的数据项加锁

死锁处理

死锁预防

#1.每个事务在开始执行之前封锁它的所有数据项
#2.对所有数据项施加一种次序，同时要求事务只能按照次序规定的顺序封锁数据项
#3.使用抢占与事务回滚
- 等待-死亡机制：非抢占技术，当Ti申请的数据项被Tj持有，仅当Ti时间戳小于Tj的时间戳，才允许Ti等待
- 伤害-等待机制：抢占技术，当Ti申请的数据项被Tj持有，仅当Ti时间戳大于Tj的时间戳，才允许Ti等待
#4.基于锁超时，申请锁的事务至多等待一段指定时间，否则超时并回滚

死锁检测

使用一种称为等待图的有向图来描述

顶点集由系统中的所有事务组成
$T_i \rightarrow T_j$ 的有向边表示事务 $T_i$ 正等待事务 $T_j$ 释放一个 $T_i$ 所需的数据项
当且仅当等待图中包含环路时，系统中存在死锁

死锁恢复

解除死锁最常用的方法是回滚一个或多个事务

选择牺牲者
- 回滚产生最低代价的事务
回滚
- 完全回滚：中止事务并重新启动
- 部分回滚：将事务回滚到可以接触死锁的地方
饿死
- 必须保证一个事务被选为牺牲者的次数有限

多粒度

如果一个节点加上了意向模式锁，则意味着在树的较低层进行显式加锁
在一个节点被显式加锁之前，该节点的全部祖先节点均要加上意向锁
封锁按自顶向下的次序，而锁的释放按自底向上的次序

	IS	IX	S	SIX	X
IS	true	true	true	true	false
IX	true	true	false	false	false
S	true	false	true	false	false
SIX	true	false	false	false	false
X	false	false	false	false	false

如果一个节点被加上了意向共享模式锁（IS），那么只能在树的较低层显式加共享模式锁
如果一个节点被加上了意向排他模式锁（IX），那么只能在树的较低层显式加共享或排他模式锁
如果一个节点被加上了共享意向排他模式锁（SIX），则以该节点为更的子树以共享模式被显式封锁，并且在树的更低层显式加排他模式锁

基于时间戳的协议

时间戳

对系统中的每个事务，使用一个唯一的、固定的时间戳和它关联起来
时间戳在事务开始执行之前由数据库系统所赋予，其决定了可串行化的次序
- 系统时钟
- 逻辑计数器

时间戳排序协议

其保证任何有冲突的read和write操作按时间戳的次序执行

每个数据项Q与两个时间戳相关联
W-timestamp(Q)表示成功执行write(Q)的任意事务的最大时间戳
R-timestamp(Q)表示成功执行read(Q)的任意事务的最大时间戳

假设事务T发出read(Q)
- 若TS(T) < W-timestamp(Q)，则T需要读取的Q值已被覆盖。T回滚
- 若TS(T) >= W-timestamp(Q)，则执行read操作，且R-timestamp(Q)=max(R-timestamp(Q),TS(T))
假设事务T发出write(Q)
- 若TS(T) < R-timestamp(Q)，则T产生的Q值是先前所需要的，且假定该值永远不会产生了。T回滚
- 若TS(T) < W-timestamp(Q)，则T试图写入的Q值是过时的。T回滚
- 其他情况，执行write操作，且W-timestamp(Q)=TS(T)
事务如果触发了回滚，系统会赋予它一个新的时间戳并重新启动它
该协议保证冲突可串行化和无死锁
可能存在长事务饿死的现象
可能产生不可恢复的调度
- 通过在事务末尾一起执行所有写操作可以保证可恢复性和无级联性

Thomas写规则

假设事务T发出write(Q)
- 若TS(T) < R-timestamp(Q)，则T产生的Q值是先前所需要的，且假定该值永远不会产生了。T回滚
- 若TS(T) < W-timestamp(Q)，则T试图写入的Q值是过时的。write操作被忽略
- 其他情况，执行write操作，且W-timestamp(Q)=TS(T)

基于有效性检查的协议

有效性检查协议要求每个事务在生命周期中按两个或三个不同的阶段执行

读阶段：系统执行事务T，T的所有write操作是对局部的临时变量进行的，但并不对数据库进行真正的更新
有效性检查阶段：对事物T进行有效性检查的测试，如果测试失败则终止该事务
写阶段：如果通过了有效性检查，则保存T所执行的任何write操作结果的临时局部变量被拷贝入数据库

StartTS(Ti)：事务Ti开始执行的时间
ValidationTS(Ti)：事务Ti完成其读阶段并开始其有效性检查阶段的时间
FinishTS(Ti)：事务Ti完成其写阶段的时间

事务T的有效性检查测试要求满足TS(Tk)<TS(Ti)的所有事务Tk必须满足下面两个条件之一：

FinishTS(Tk)<StartTS(Ti)
Tk所写的数据项集合和Ti所读的数据项集合不相交，且Ti开始其有效性检查阶段之前，Tk就完成了其写阶段(StartTS(Ti)<FinishTS(Tk)<ValidationTS(Ti))

多版本机制

多版本时间戳排序

对于每个数据项Q，存在一个版本序列<Q1,Q2,…,Qm>与之关联，每个Qk包含三个数据字段

Content：Qk版本的值
W-timeStamp(Q)：创建Qk版本的事务的时间戳
R-timeStamp(Q)：所有成功读取过Qk版本的任意事务的最大时间戳

多版本时间戳排序机制：（Qk是Q的如下版本：写时间戳是小于或等于TS(Ti)的最大写时间戳）

read(Q)：返回Qk版本的值
write(Q)：
- 若TS(Ti)<R-timeStamp(Qk)，系统回滚事务
- 若TS(Ti)=R-timeStamp(Qk)，系统覆盖Qk的内容
- 若TS(Ti)>R-timeStamp(Qk)，创建Q的一个新版本

不保证可恢复性和无级联性

多版本两阶段封锁

结合多版本并发控制和两阶段封锁
只在只读事务与更新事务之间进行区分
更新事务执行强两阶段封锁

快照隔离

事务被给予两个时间戳
- StartTS(Ti)：事务Ti开始的时间
- CommitTS(Ti)：事务Ti请求有效性检查的时间

更新事务的有效性检查步骤

为了防止更新丢失，快照隔离有两个变种

先提交者胜：第一个进行检查的事务能成功写出更新
先更新者胜：第一个获得锁的事务被运行提交并执行更新

恢复系统

故障分类

事务故障
- 逻辑错误：事务由于某些内部情况而无法继续正常执行
- 系统错误：系统进入一种不良状态
系统崩溃：硬件故障，或数据库或操作系统存在漏洞
磁盘故障：由于磁头损坏或故障造成磁盘块上内容丢失

恢复与原子性

日志记录

更新日志记录<Ti,Xj,V1,V2>
- 事务标识
- 数据项标识
- 旧值
- 新值
事务开始<Ti start>
事务提交<Ti commit>
事务中止<Ti abort>

数据库修改

延迟修改：一个事务直至提交时都没有修改数据库
立即修改：事务仍然活跃时就发生数据库修改
撤销操作：使用一条日志记录，将该日志中指定数据项置为日志记录中包含的旧值
重做操作：使用一条日志记录，将该日志中指定数据项置为日志记录中包含的新值

重做和撤销

redo(Ti)
- 将事务Ti更新过所有数据项的值都置为新值
- 重做的执行顺序很重要
undo(Ti)
- 将事务Ti更新过的所有数据项的值都置为旧值
- 需要写日志记录来记下所执行的更新（read-only日志记录）
- 撤销的执行顺序很重要
- 撤销操作完成后，需要写一条<Ti abort>日志
如果日志中包括<Ti start>，但既不包括<Ti commit>，也不包括<Ti abort>，需要撤销
如果日志中包括<Ti start>，同时包括<Ti commit>或<Ti abort>，需要重做

检查点

检查点的执行过程：
- 将当前位于主存的所有日志记录输出到稳定存储器
- 将所有修改过的缓冲块输出到磁盘
- 将一条形如<checkpoint L>的日志记录输出到稳定存储器，其中L是执行检查点时正活跃的事务的列表
在系统崩溃后，系统检查日志以找到最后一条<checkpoint L>记录
只需对L中的事务，以及<checkpoint L>记录写到日志中之后才开始执行的所有事务进行redo和undo

恢复算法

事务回滚

从后往前扫描日志，对于所发现的Ti的每条形如<Ti,Xj,V1,V2>的日志记录
- 将值V1写到数据项Xj
- 往日志中写一条特殊的read-only日志记录<Ti,Xj,V1>，其中V1是在本次回滚中数据项被恢复的值
一旦发现了<Ti start>日志记录，就停止反向扫描，并往日志中写一条<Ti abort>日志记录

系统崩溃后的恢复

重做阶段
- 将待回滚事务的列表undo-list初始化设定为<checkpoint L>日志记录中的L
- 一旦发现形如<Ti,Xj,V1,V2>或<Ti,Xj,V2>的日志记录，就执行重做
- 一旦发现形如<Ti start>的日志记录，就把Ti加到undo-list中
- 一旦发现形如<Ti abort>或<Ti commit>的日志记录，就把Ti从undo-list中去除
- 在重做阶段的末尾，undo-list中包括了在系统崩溃之前尚未完成的所有事务
撤销阶段
- 一旦发现属于undo-list中事务的记录，就执行撤销
- 当系统发现undo-list中事务Ti的<Ti start>日志记录，就往日志中写一条<Ti abort>日志记录，并把Ti从undo-list中去除
- 一旦发现undo-list变为空，则撤销阶段结束

提交处理的优化

使用组提交技术可以提高事务提交的速率

缓冲区管理

将日志记录写到主存的日志缓冲区中
对恢复技术增加一些额外的要求以保持事务的原子性：
- 在日志记录<Ti commit>输出到稳定存储器后，事务Ti进入提交状态
- 在日志记录<Ti commit>输出到稳定存储器前，与事务Ti有关的所有日志记录必须已经输出到稳定存储器
- 在主存中的数据块输出到数据库（非易失性存储器）前，与该块中数据有关的所有日志记录必须已经输出到稳定存储器
  - 这一条规则被称为先写日志（WAL）
将缓冲的日志写到磁盘有时被称为强制日志

ARIES

使用日志序列号(LSN)来便是日志记录，并将LSN存储在数据库页中
支持物理逻辑重做
使用脏页表来减少恢复时不必要的重做
视同模糊检查点机制

数据结构

日志序列号(LSN)
- 唯一标识该记录
- 日志记录产生约晚，标号的值越大
日志页序列号(PageLSN)
- 每当在页面上执行更新操作时，该操作将其日志记录的LSN存储在该页的PageLSN字段中
- 在恢复的重做阶段，LSN值小于等于该页的PageLSN值的任何日志记录将不在该页上执行
PrevLSN
- 每条日志记录也包含同一事务的前一条日志记录的LSN
补偿日志记录(CLR)
- 与read-only日志记录的作用相同
- 同时起到operation-abort日志记录的作用
脏页表
- 包含一个在数据库缓冲区中已更新过的页面的列表
- 为每一页保存其PageLSN和RecLSN（有助于标识已经实施于该页在磁盘上的版本的日志记录）
- RecLSN反应出当前页面被加到脏页表中时日志末端的LSN，其应该大于或等于稳定存储器上该页的PageLSN
检查点日志记录
- 包含脏页表和活跃事务的列表
- 为每个事务记录其LastLSN（该事务所写的最后一条日志记录的LSN）

恢复算法

分析阶段

分析阶段找到最后、已完成的检查点日志记录，并将该记录读入脏页表
将RedoLSN设置为脏页表中那些页的RecLSN的最小值
- 如果没有脏页，就将RedoLSN设置为检查点日志记录的LSN
从RedoLSN开始扫描日志，将undo-list初始设置为检查点日志记录中的事务列表
- 只要找到一条不在undo-list中的事务的日志记录，就把该事务添加到undo-list
- 只要找到一个事务的end记录，就把该事务从undo-list中删除

重做阶段

从RedoLSN开始正向扫描日志，只要找到一条更新记录，就：

如果该页不在脏页表中，或该更新日志的LSN小于脏页表中该页的RecLSN，则跳过该记录
否则，从磁盘调出该页，如果其PageLSN小于该日志记录的LSN，就重做该记录

撤销阶段

对日志进行反向扫描，对undo-list中的所有事务进行撤销

撤销阶段产生一个包含撤销执行动作的CLR，并将该CLR的UndoNextLSN设定为该更新日志记录的PrevLSN

其他特性

嵌套的顶层动作
恢复独立性
保存点
细粒度封锁
恢复最优化