数据库系统概念 学习笔记

# 引言

# 数据库 - 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) 表示
  • 关系的当前值由表指定
  • 关系 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）

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;

# 删除语句

-- 注意运行顺序，首先执行 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
  • 断言，即谓词

CREATE ASSERTION credits CHECK

(NOT EXISTS(SELECT ID FROM student))

# SQL 固有属性

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

date '2005-7-27'

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

time '09:00:30'

• timestamp：date 和 time 的结合

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

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

interval '1' day

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

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

# 键和函数依赖

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

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

# 键和函数依赖

• 如果函数依赖$K \rightarrow R$ 在 r (R) 上成立，则 K 是 r (R) 的一个超键
• 如果函数依赖$K \rightarrow R$ 在 r (R) 上成立，并且不存在$\alpha \subset K,\alpha \rightarrow R$，则 K 是 r (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_i$ 是否属于 BCNF，对于$R_i$ 中属性的每个子集$\alpha$，检查$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 访问数作为估计查询执行计划的代价的两个重要因素

# 选择运算

• 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. 计算相应的连接，然后将适当的元组加入连接结果中以得到外连接结果
• 2. 对连接算法加以修改

# 聚集

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

# 表达式执行

# 物化

• 每次将执行的结果物化到一个临时关系中
• 双缓冲通过并行执行 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 是非冲突可串行化的；反之则是可冲突串行化的