数据库系统模式的概念#

• 模式schema
  • 数据库中全体数据的逻辑结构和特征的描述
  • 仅仅是型的描述，与具体的值无关
  • 反应的是数据的结构及其联系
  • 模式是相对稳定的
• 实例Instance
  • 模式的一个具体值；反应数据库某一时刻的状态
  • 同一个模式可以有很多实例
  • 实例随数据库中数据的更新而变动

数据库系统的三级模式#

模式、外模式、内模式，三级模式之间有两级映像

提高了数据的逻辑独立性和物理独立性

• 模式（逻辑模式）(schema)
  • 数据库中全体数据的逻辑结构和特征的描述
  • 所有用户的公共数据视图——全局逻辑视图，综合了所有用户的需求
  • 一个数据库只有一个模式
  • 模式的地位：是数据库模式结构的中间层，独立于数据库的其它层次
  • 定义：
    • 数据的逻辑结构（数据项的名字、类型、取值范围等）
    • 数据之间的联系
    • 数据有关的安全性、完整性要求
  • 模式一般由多个“记录”组成，包含数据库的所有信息
  • 设计数据库模式结构应该首先确定数据库的逻辑模式
  • 模式的作用是为了支持数据的少冗余共享
• 外模式（子模式subschema、用户模式）
  • 数据库用户使用的局部数据的逻辑结构和特征的描述
  • 数据库用户的数据视图，面向具体的应用程序，是与某一应用有关的数据的逻辑标识
  • 定义再逻辑模式之上
  • 独立于存储模式和存储设备
  • 当应用需求发生较大变化，相应外模式不能满足视图要求时，该外模式就得做相应改动
  • 设计外模式时应充分考虑到应用的扩充性
  • 地位：介于模式与应用之间
    • 模式与外模式的关系：一对多
      • 外模式通常是模式的子集
      • 一个数据库可以由多个外模式。
      • 对模式中同一数据，再外模式中的结构、类型、长度、保密级别等都可以不同
    • 外模式与应用的关系：一对多
      • 同一外模式页可以为某一用户的多个应用系统锁时使用
      • 但一个引用程序只能使用一个外模式
  • 用途：
    • 支持不同用户建立适应局部应用特征的结构，每个用户只能看见和访问锁对应的外模式中的数据
    • 简化应用处理
    • 提高安全性，保证数据库安全性的一个有力措施
• 内模式（internal schema，存储模式storage schema，物理模式）
  • 是数据物理结构和存储方式的描述
  • 是数据在数据库内部的标识方式
  • 一个数据库只有一个内模式

数据库的二级映像与数据独立性#

二级映像在DBMS内部实现这三个抽象层次的联系和转换

• 外模式/模式映像：定义某一个外模式和模式之间的对应关系

  • 作用：保证数据的逻辑独立性
    • 当模式改变时，数据库管理员修改有关的外模式/模式影响，使外模式保持不变
    • 应用程序使依赖数据的外模式编写的，所以应用程序不必修改，保证了数据与程序的逻辑都要理性，简称数据的逻辑独立性

• 模式/内模式映像：定义了数据全局逻辑结构与存储结构之间的对应关系

  • 数据库中模式/内模式映像使唯一的
  • 该映像定义通常包含在模式描述中
  • 保证数据的物理独立性：
    • 当数据库的存储结构改变了，数据库管理员修改模式/内模式映像，使模式保持不变
    • 存储结构变化的映像被限制在模式之下，这使数据的存储结构和存储方法独立于应用程序而不受影响。保证了数据与程序的物理独立性，简称数据的物理独立性。

• 三级模式结构的优点

  • 保证数据的独立性（物理独立性&逻辑独立性）
  • 简化了用户接口：
    • 按照外模式编写应用系统或敲入命令，不需要了解数据库内部的存储结构，
  • 有利于数据共享
    • 在不同的外模式下可由多个用户共享系统中数据，减少了数据冗余
  • 利于数据安全保密
    • 在外模式下根据要求操作，不能对限定的数据操作，保证了其它数据的安全

关系#

• 单一的数据结构——关系

  • 显示世界的实体以及实体间的各种联系均用关系来标识

• 逻辑结构——二维表

  • 从用户角度，关系模型中数据的逻辑结构是一张二维表

• 关系模型建立在集合代数的基础上

  • 域(domain)
  • 笛卡尔积
  • 关系

• 域：是一组具有相同数据类型的值的集合

  • 域中锁包含的值的个数称为域的基数
  • 关系中用域标识属性的取值范围

• 笛卡尔积

  • 给定一组域$D_1,D_2,...,D_n$，这些域中可以有相同的，则$D_1,D_2,...,D_n$的笛卡尔积为
  • $D_1 \times D_2 \times ... \times D_n = \{(d_1,d_2,...,d_n) | d_i \in D_i, i=1,2,...,n \}$
  • 笛卡尔积中每一个元素$(d_1,...,d_n)$叫做一个n元组
  • 笛卡尔积元素$(d_1,...,d_n)$中的每一个值$d_i$叫做一个分量
  • 若$D_i$为有限集，基数$m_i$，则$D_1 \times D_2 \times ... \times D_n$的基数M为$M=\Pi _{i=1}^{n}m_i$
  • 笛卡尔积是一个集合；是所有域的所有取值的一个组合
  • 不能重复

• 关系

  • 笛卡尔积的自己叫做在域$D_1,D_2,...,D_n$上的关系，用$R(D_1,...,D_n)$表示
  • R是关系的名字，n是关系的度或目(Degree)
  • 关系中的每个元素称为元组
  • 关系中不同列可以对应相同的域，为了加以区分，必须对每列其一个名字，称为属性
  • n目关系必有n个属性
  • 候选码：
    • 若关系中的某一属性组的值能唯一地表示一个元组，若从属性组中去掉任意属性，它就不再具有这一性质，则称该属性组为候选码
    • 主码：若有一个关系又多个候选码，则选定其中一个为主码
      • 每个关系又且仅有一个主码
    • 主属性：候选码的诸属性
    • 非主属性或非码属性：不包含在任何候选码中的属性
  • 三类关系：
    • 基本关系（基本表或基表）
      • 实际存在的表，是实际存储数据的逻辑表示
    • 查询表
      • 查询结果对应的表
    • 视图表
      • 由基本表或其它视图表到处的表，是虚表，不对应实际存储的数据
  • 关系与二维表的区别：关系是规范化了的二维表中行的集合，为了使相应的数据操作简化，在关系模型中对关系做了限制
  • 基本关系的6大特性
    • 列是同质的(Homogeneous)
    • 不同的列可出自同一个域，其中的每一列称为一个属性，不同的属性要基于不同的属性名
    • 列的顺序无所谓，列的次序可以任意交换
    • 任意两个元组的候选码不能相同
    • 行的顺序无所谓，行的次序可以任意交换
    • 分量必须取原子值，即每个分量是都不可分的数据项

关系模式#

• 关系模式是型，相对静态，稳定
• 关系是值，是关系模式在某一时刻的状态或内容，是动态的、随时间不断变化的
• 关系模式是对关系的描述
  • 元组集合的结构：
    • 属性构成
    • 属性来自的域
    • 属性与域之间的映像关系
  • 元组语义以及完整性约束条件
  • 属性间的数据依赖关系集合
• 关系模式，记作R(U,D,DOM,F)
  • R:关系名
  • U中的属性名集合
  • D:属性组U中属性锁来自的域（取值范围）
  • DOM:属性到域的映像集（属性类型、长度）
  • F：属性间数据的依赖关系集合

实体完整性#

• 在关系中的所有元组在码上的取值满足
  • 主属性非空
  • 主码各不相同

参照完整性#

• 若属性（组）F是基本关系R的外码，它域基本关系S的主码Ks相对应（R和S不一定是不同的关系），则uiyuR中每个元组在F上的值必须为
  • 空值（F的每个属性值均为空）
  • S中某个元组的主码值

用户定义的完整性#

传统的集合运算#

除笛卡尔积外，要求参加运算的关系必须具备相容性

• 相容性

  • 具有相同的度n
  • R中的第i个属性和S中的第i个属性来自同一个域

• 并

• 差

• 交

• 笛卡尔积

专门的关系运算#

• 选择
  • $\sigma _F(R) = \{t|t\in R \cap F(t)=true \}$
  • 其中，$\sigma$为选择运算符，F为条件表达式。$\sigma _F(R)$表示从R中挑选满足公式F的元组所构成的关系
• 投影
  • 从R中选择处若干属性列组成新的关系
  • $\pi _{A(R)}=\{t[A]|t \in R \}$
  • 投影的结果要去掉相同的行（避免重复行）
    • 投影之后不仅取消了原关系中的某些列，还可能取消某些元组
• 连接：从两个关系的笛卡尔积中选取满足连接条件的元组
  • 等值连接：从关系R域S的广义笛卡尔积中选取A、B属性值相等的哪些元素
  • 自然连接：特殊的等值连接
    • 两个关系中进行比较的分量必须是相同的属性组
    • 在结果中把重复的属性列去掉
    • 当R和S无相同属性时，自然连接就是做笛卡尔积
    • 本质是将两张由关联的表，按照元组之间在属性B（外码）上的等值关系，合并为一张表
    • 问题：会丢失信息，如丢失一个未选课的学生
  • 外连接：把舍弃的元组页保存在结果关系中，而在其它属性上填空值null
  • 左外连接：只把左边关系R中要舍弃的元组保留(left join)
  • 右外连接：只把右边关系S中要舍弃的元组保留(right join)
• 除 $R\div S$
  • $T=\pi _{1,...,r-s}(R)$
  • $W=(T\times S)-R$
  • $V=\pi_{1,..,r-s}(W)$
  • $R\div S=T-V$
  • 即$R\div S=\pi_{1,...,r-s}(R)-\pi _{1,...,r-s}((\pi _{1,...,r-s}(R)\times S)-R)$

SQL的基本概念#

• 基本表(base table)

  • 独立存在的表,SQL中一个关系就对应一个基本表
  • 一个(或多个)基本表对应一个存储文件
  • 一个表可以带若干索引,索引也放在存储文件中

• 存储文件(stored file)

  • 逻辑结构组成了关系数据库的内模式
  • 无力结构是任意的,对用户透明

• 视图(view)

  • 从一个或几个基本表导出的表
  • 数据库中之存放视图的定义而不存放视图对应的数据,视图是一个虚表
  • 用户可以在视图上再定义视图

• 在一个目录下可以建立多个模式

• 在一个模式下可以建立多个关系表

模式的定义与删除#

• 定义模式
  • 语句

1
create schema <模式名> authorization <用户名>
2
    [<表定义子句>|<视图定义子句>|<授权定义子句>];

• 语义:为某用户创建一个模式.定义模式实际上定义了一个命名空间,其中可以定义该模式包含的数据库对象,例如基本表、视图、索引等
• 在create schema中可以接受create table, create view和grant子句
• 删除模式

1
drop schema <模式名><cascade|restrict>

• cascade(级联):删除模式等同事把该模式中所有的数据库对象全部删除
• restrict(限制):如果该模式中定义了下属的数据库对象(如表,视图等),则拒绝该删除语句的执行.当该模式中没有任何下属的对象时才能执行

基本表的定义、删除与修改#

• 定义基本表 DDL不仅运行定义一组关系,也要说明每个关系的信息
  • 每个关系的模式
  • 每个属性的值域
  • 完整性约束
  • 每个关系的安全性和权限
  • 每个关系需要的索引集合
  • 每个关系在磁盘上的无力存储结构
• 基本表的定义(创建)

1
create table <表名> (
2
  <列名><数据类型>[列级完整性约束条件]
3
  [,<列名>,<数据类型>[列级完整性约束条件]]
4
  ...
5
  [,<表级完整性约束条件>]
6
)

• <表名>:所要定义的基本表的名字
• <列名>:组成该表的各个属性(列)
• <列级完整性约束条件>:设计相应属性列的完整性约束条件
• <表级完整性约束条件>:设计一个活多个属性列的完整性约束条件
• 创建基本表

1
create table 表名(
2
  列名 数据类型 [default 缺省值] [not null]
3
  [,列名 数据类型 [default 缺省值][not null]...]
4
  [, primary key(列名[,列名]...)]
5
  [foreign key(列名[,列名]...) references 表名(列名[,列名]...)]
6
  [, check (条件表达式)]
7
);

• 常用的完整性约束
  • 主码: primary key
  • 唯一性约束: unique
  • 非空值约束: not null
  • 参照完整性约束: foreign key
  • 自定义的完整性约束: check(逻辑表达式)

1
alter table <表名>
2
  [add <新列名><数据类型>[完整性约束]]
3
  [add <表级完整性约束>]
4
  [drop [column]<列名>[cascade|restrict]]
5
  [drop constraint <完整性约束名>[cascade|restrict]]
6
  [alter column <列名><数据类型>];

1
drop table <表名>[restrict|cascade];

索引的建立与删除#

• 建立索引的目的:加快查询速度
• 谁建立索引
  • DBA或表的属主
  • DBMS一般会自动为主码和uniqe属性的列创建索引
• 谁维护索引自动完成
• 谁使用索引用户不直接使用索引. DBMS自动选择是否使用索引以及使用哪些索引

1
create [unique][cluster] index <索引名>
2
  on <表名>(<列名>[<次序>][,<列名>[<次序>]]...);
3
  -- 其中,<次序>指升序或降序,缺省为升序

1
alter index <旧索引名> rename to <新索引名>

1
drop index <索引名>
2
-- 或
3
drop index <索引名> on <表名>

数据字典#

数据字典:关系 DBMS内部的一组系统表,记录数据库中所有的定义信息

单表查询#

• 字符匹配
  • 通配符
    • 百分号% 代表任意长度的字符串
    • 下划线_ 代表任意一个字符
    • escape” 表示""是一个换码字符
• 对于空值的时候,只能是is null,不能用等号
• 聚集函数
  • 计数
    • count([distinct|all]*):统计元祖个数
    • count([distinct|all]<列名>):统计一列中值的个数
  • 计算总和
    • sum([distinct|all]<列名>)
  • 计算平均值
    • avg([distinct|all]<列名>)
  • 最大值最小值
    • max([distinct|all]<列名>)
    • min([distinct|all]<列名>)
  • 集函数只能用于select子句和having子句中
  • 当集函数遇到null的时候,除了count(*),都跳过空值
• where子句域having子句的区别：作用对象不同
  • where子句作用域于基本表或视图，从中选择满足条件的元组
  • having短语作用于组，从中选择满足条件的组

连接查询#

嵌套查询#

• 子查询不能使用order by子句

• 反应了SQL语言的结构化

• 有些嵌套查询可以用连接运算代替

• 应用场景：

  • 属于运算：该成员t是否属于某个select结果集合R；in谓词
  • 比较运算：该成员是否比某个select即中所有成员或至少一个成员大或小；
  • 逻辑运算：该成员是否能使得集合逻辑式成立；

• 当子查询的返回值只有一个的时候，可以使用比较运算符将父查询和子查询连接起来

集合查询#

• 并操作union
• 交操作intersect
• 差操作except

插入数据#

1
insert into 基本表[(列名[,列名]...)]values(元组值);

1
insert into <基本表名> [(<列名表>)] 子查询;

删除数据#

1
delete from <表名>[where 条件表达式]

作用:从表中删除符合where子句中删除条件的元组;若where子句缺省,啧阐述表中所有元组

• 不带条件的delete语句和drop table语句的区别
  • drop table语句删除表和表中的所有数据
  • delete语句指删除表中的数据,表仍然保留

带子查询的删除语句:

1
delete from sc
2
where sno in (
3
  select sno
4
  from student
5
  where sdept='CS'
6
);

更新数据#

1
update <基本表名>
2
  set <列名>=值表达式[,<列名>=值表达式...]
3
  [where 条件表达式]

作用:对表中满足where条件的远足,按set子句修改相应列的值

也可以带字查询,语法和上面类似

视图的定义#

1
create view 视图名[(列名,[列名]...)]
2
as 子查询
3
[with check option]

1
drop view <视图名> [cascade];

查询视图#

• 用户角度:查询视图与查询基本表相同
• DBMS执行对视图的查询时
  • 首先进行有效性检查,检查查询设计的表、视图等是否在数据库中存在
  • 如果存在,则从数据字典中取出查询设计的视图的定义
  • 把定义中的子查询和用户对视图的查询结合起来,转换成等价的基本表的查询
  • 然后再执行这个经过修正的查询
• 将对视图的查询转换为对基本表的查询的过程称为视图的消解

更新视图#

• 视图的更新操作包括插入、修改和删除数据,语法格式同基本表的更新

• 因为视图是一张虚表,所以对视图的更新,最终实际上是转换成对基本表的更新

• 一些视图是不可更新的,因为这些视图的更新不能唯一地有意义地转换成对应基本表的更新

  • 字段由表达式或常数组哼,不允许执行insert和该字段上dupdate,但可以执行delete
  • 字段由机函数组成,不允许更新
  • 视图定义含有group by或distinct,不允许更新
  • 有潜逃查询,且内外查询使用相同表时,不允许更新
  • 定义中有多表链接时,不允许更新
  • 由不允许更新的视图导出的视图,不允许更新

• 视图的作用

  • 简化用户的操作
  • 使用户能以多种角度看待同一数据
  • 对重构数据库提供一定程度的逻辑独立性
  • 是数据共享与保密的一种安全机制
  • 适当的利用视图可以更清晰的查询表达

数据库的不安全因素#

• 非授权用户对数据库的恶意存取和破坏
  • 安全措施:用户身份鉴别、存取控制和视图等
• 数据库中重要或敏感数据被泄漏
  • 安全措施:审计、日志、入侵检测等
• 安全环境的脆弱性

用户身份鉴别#

• 系统提供的最外层安全保护措施
• 系统提供一定的方式让用户标识自己的名字和身份,系统进行核实,通过鉴定后才提供系统使用权

存取控制#

• 对于获得上机权的用户还要根据系统预先定义好的外模式(视图)或用户权限进行存取控制,保证用户只能存取他有权存取的数据
• 方法
  • 定义用户权限,登记到DD中
  • 合法权限检查
• 常用存取控制方法
  • 自主存取控制(Discretionary Access Control, DAC),C2级,灵活
    • 用户或DBA定义存取权限的一种控制策略,通过SQL的grant语句和revoce语句实现
    • 访问权限由两个要素组成:数据对象和操作.类型系统通过控制数据对象的访问权限防止非授权访问
    • 缺点:
      • 可能存在数据的“无意泄漏”
      • DAC容易受到特洛伊木马攻击
      • 原因:这种机制仅仅通过对数据的存取权限来进行安全控制,而数据本身并没无安全性标记
      • 解决:对系统控制下的所有主客体实施强制存取控制策略
  • 强制存取控制(Mandatory Access Control, MAC),B1级,严格

授权与回收#

1
grant <权限>[,<权限>]...
2
  [on <对象类型><对象名>]
3
  to <用户>[,<用户>]...
4
  [with grant option]

1
revoke <权限>[,<权限>]...
2
  [on <对象类型><对象名>]
3
  from <用户>[,<用户>]...
4
  [cascade|restrict]

1
create user <username>
2
  [with][dba|resource|connect];

数据库角色#

• 角色:被命名的一组与数据库操作相关的权限
• 角色是权限的集合
• 可以为一组具有相同权限的用户创建一个角色,简化授权的过程

角色的创建

1
create role <角色名>

给角色授权

1
grant <权限>[,<权限>]...
2
  on <对象类型>对象名
3
  to <角色>[,<角色>]...

将一个角色授予其他的角色或用户

1
grant <角色1>[,<角色2>]...
2
  to <角色3>[,<用户1>]...
3
  [with admin option]

角色权限的收回

1
revoke <权限>[,<权限>]...
2
  on <对象类型><对象名>
3
  from <角色>[,<角色>]...

强制存取控制#

管理员管理访问控制、制定策略,用户不能直接感知或进行控制

• 实体类别
  • 主体:系统中的活动实体,包括用户和用户的进程
  • 客体:系统中的被动实体,受主体操纵的基表、索引、视图等
• 敏感度标记(label):
  • 绝密
  • 机密
  • 可信
  • 公开
• 强制存取控制规则:
  • 仅当主体的许可证级别大于或等于客体的密级时,该主体才能读相应的客体
  • 仅当主体的许可证级别等于或小于客体的密级时,该主体才能写相应的客体
• 优点
  • 禁止拥有高许可证级别的主体更新低密级的数据对象,从而保证了敏感数据的可靠性
  • 禁止低许可证级别的主体浏览高密级的数据,避免了敏感数据的泄漏
  • MAC对数据本身进行密级标记,无论数据如何复制,标记与数据是不可分割的整体.只有符合密级标记的要求的用户才可以操作响应数据,提高了安全性级别
• 兼容关系
  • 安全级别之间具有篇序乡下兼容关系,较高安全性级别的安全保护措施要包含较低安全级别的所有保护措施,同时应提供更多完善的保护能力.因此实现MAC必须先实现DAC,DAC和MAC共同构成DBMS的安全机制

定义触发器#

1
create trigger <触发器名>
2
  [before|after]<触发事件>on<表名>
3
  for each {row|statement}
4
  [when <触发条件>]
5
  <触发动作体>;

• 说明：
  • <触发事件>:可以是insert,delete,update，或者这些事件的组合，update后面可以带of<触发列,…>，指明只当哪些列被修改时才激活触发器。before和after表示触发器是在触发事件之前还是之后被激活
  • for each row表示该触发器为行级触发器，触发事件没映像一条元组都将激活一次触发器
  • for each statement表示该触发器为语句级触发器，触发事件只激活一次触发器
• DBMS如何执行触发器
  • 触发器被激活后，先检查<触发条件>，当其值为真时，<触发动作体>才执行；如果没有指定<触发条件>，则<触发动作体>在触发器被激活后立即执行
  • <触发动作体>是一段程序，如果触发器是行级触发器，则这段程序中还可以使用new和old分别引用触发事件发生前后的元组值

激活触发器#

• 触发器的执行，是由触发事件激活的，并由数据库服务器自动执行
• 一个数据表上可能定义了多个触发器，同一个表上的多个触发器激活时遵循以下顺序
  • 执行该表上的before触发器
  • 激活触发器的sql语句
  • 执行该表上的after触发器
• 多个触发器执行时，这些触发器按创建事件顺序依次执行
• 任意触发器的执行失败都将中止整个操作

触发器的撤销#

1
drop trigger <触发器名> on <表名>

说明：触发器必须是一个已创建的触发器，并且只能由具有相应权限的用户删除

注：触发器是与表相关联的，因此，表的撤销将引起该表上的所有触发器同时被撤销

触发器的作用#

• 强制实现由逐渐和外键所不能保证的参照完整性和数据的一致性
• 实现比check语句更复杂的约束（涉及多表）
• 找到数据修改前后表状态的差异，并基于此差异采取行动
• 级联运行修改数据库中相关表，自动触发相关操作
• 跟踪变化，禁止/回滚不合规则的操作，防止非法修改数据
• 返回自定义的错误消息（约束做不到）
• 自动调用存储过程

函数依赖#

定义：设R(U)是一个属性集U上的关系模式，$X,Y\subseteq U$,r是R(U)上的任意一个关系，如果成立 $\forall t,s \in r, if t[X]=s[X], then y[Y]=s[Y]$ 则称“X函数确定Y”或“Y函数依赖于X”，记作X->Y。X称为这个函数依赖的决定属性集。

• 说明
  • 函数依赖不是指关系模式R的某个或某些关系实力满足的约束条件，而是指R的所有瓜西实力均要满足的约束条件
  • 函数依赖是语义范畴的概念，只能根据语义来确定一个函数依赖，而不能按照其形式定义来证明一个函数依赖是否成立
  • 函数依赖关系的存在于时间无关
  • 属性间联系于函数依赖的对应关系
    • 1:1联系：存在函数依赖X->Y,且Y->X,即X<—>Y
    • 1联系：存在函数依赖X->Y，但不存在Y->X
    • m联系：不存在函数依赖
• 平凡函数依赖与非平凡函数依赖
  • 平凡函数依赖
    • 设有关系模式R(U,F)，X,Y都是U的子集，若X->Y,$Y \subseteq X$，则称X->Y是平凡函数依赖
  • 非平凡函数依赖
    • 设有关系模式R(U,F),X,Y都是U的自己，若X->Y,$Y \subsetneq X$,则称X->Y是非平凡函数依赖
  • 说明：对于任何R，平凡函数依赖总是成立的。
• 完全函数依赖于部分函数依赖
  • 定义：设关系模式R(U)，U是属性全集，X和Y是U的子集
    • 如果X->Y，并且对于X的任何一个真子集X’，都有X’!->Y，则称Y完全函数依赖于X，记作X-F>T
    • 如果对于X的某个真子集X’，有X’->Y，则称Y部分函数依赖于X，记作X-P>Y
• 传递函数依赖
  • 定义：再关系模式R(U)中，如果X->Y,Y->Z，且$Y \subsetneq X,Y \subsetneq X, Z \subsetneq Y$,则称Z传递函数依赖于X，记作X-T>Z
  • 注：如果还有Y->X,即X<—>Y,则Y直接依赖于X

码#

• 设K为关系模式R<U,F>中的属性或属性组合，若K-F>U，则K称为R的一个候选码。若关系模式R有多个候选码，则选定其中的一个作为主码
  • 主码：任意候选码之一
  • 主属性：包含在任何一个候选码中的属性。
  • 超码：若K-P>U,则K称为超码
• 关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码，也称外码
• 主码和外码一起提供了表示关系间联系的手段

范式#

• 范式：关系数据库的规范化过程中为不同程度的规范化要求设立的不同标准
• 通过模式分解将一个低级范式转换为若干个高级范式的过程陈佐规范化

多值依赖#

• 设R(U)是一个属性集U上的一个关系模式，X,Y,Z是U上的子集，并且Z=U-X-Y，多值依赖X->->Y成立，当且仅当

  • 对R的任一关系r，r在(X,Z)上的每个值对应一组Y的值
  • 这组值仅仅决定于X而于Z值无关

• 多值依赖 VS 函数依赖

  • 函数依赖是多汁依赖的特里，若X->Y,则X->->Y

• 区别

  • 函数依赖规定某些元组不能出现在关系中
  • 多值依赖要求某种形式的其它元组必须在关系中
  • 有效性与属性集的范围不同
    • X->Y的有效性仅决定于X,Y属性集上的值
    • X->->Y不仅涉及属性组X和Y，而且涉及U中其余属性Z
    • 若X->Y在R(U)上成立，则对于任何$Y' \subseteq Y$,均有X->Y’成立
    • 多值依赖X->->Y若在R(U)上成立，不能断言对于任何$Y' \subseteqq Y$有X->->Y’成立

4NF#

• 定义：关系模式$R<U,F> \in 1NF$,如果对于R的每个非平凡多值依赖X->->Y($y \subsetneq X$),X都含有候选码，则$R \in 4NF$
• 含义：不允许同一表内有多对多关系
• 如果$R \in 4NF$,则$R \in BCNF$

结论#

• 3NF必定为2NF和1NF，反之不一定
• 4NF必定为BCNF,BCNF一定为3NF,反之不一定
• 3NF已在很大程度上控制了数据容易、很大程度上消去了插入和删除操作异常；但3NF分解仍不够彻底（可能存在主属性对候选码的部分fd和传递fd）
• 在fd范围内，BCNF下已完全消去了插入删除异常
• 4NF是多值依赖范畴内最高程度的规范化
• 范式并非越高约好。理论上数据库涉及一般硬规范到3NF，但实际应用中为减少连接运算，提高查询效率，不一定都达到3NF
• 适可而止（垃圾，连接运算）
• 分解不唯一

函数依赖的等价和覆盖#

• 等价：若F和G是R的两个函数依赖集，如果$F^+=G^+$，则称F等价于G
• 覆盖：若F和G是两个等价的函数依赖集$F^+=G^+$,则称F覆盖G，同时G也覆盖F
• 引理：设F和G是R的两个函数依赖集，则F和G等价的充分必要条件是$F \subseteq G^+$且$G \subseteq F^+$

最小函数依赖集#

• 若函数依赖F满足下列条件，则F为一个最小函数依赖集记作$F_m$
  • F中每个函数依赖的右部都是单属性
  • 对于F中的任一函数依赖X->A，F-{X->A}与F是不等价的（即F中不存在多余的依赖）
  • 对于F中的任一函数依赖X->A，不存在X的子集Z，使得F与$(F-{X->A}) \cup {Z->A}$等价（即左部无多余属性）
• F的最小依赖集求解算法
  • 用分解规则将F中所有函数依赖的右部分解为单属性的函数依赖，去掉重复依赖
  • 去掉多余依赖：对每个依赖X->Y，令G=F-{X->Y},求$X_{G^+}$,若$Y \subseteq X_{G^+}$,则X->Y为多余依赖，将其从F中去掉
  • 去掉依赖左部的多余属性：对每个左部为多属性的依赖，如果X->A，设X=B1…BM,逐一考察Bi，若$A \in (X-B_i)_{F^+}$,则Bi是多余属性，用X-Bi代替X
  • 重复2，3，直到Fm不再改变
• 注：F的最小函数依赖集不是唯一的，与计算顺序有关

分解的正确性标准#

• 无损连接性:分解所得到的各个关系模式经过自然链接可以还原成被分解的关系模式,既不增加原来没有的元组也不丢失原有的元组
• 依赖保持性:分解所得到的哥哥关系模式上的函数依赖的集合与被分解关系模式原油的函数依赖集等价,没有被丢失的现象

分解的无损连接性和保持函数依赖性#

• 任何关系模式R(U,F),$\rho={R_1,...,R_n}$是R的一个分解.若对R的任意关系r都有 $\rho = \Pi _{R_1}(r) ⋈ \Pi _{R_2}(r) ... ⋈ \Pi _{R_n}(r)$ 则称分解$\rho$是一个无损分解
• 即:无损分解可通过自然连接运算还原
• 定义:任给定R(U,F),$\rho={R_1,...,R_n}$是R的一个分解,若 $F \leftrightarrow \Pi _{R_1}(F_1) \cup \Pi _{R_2}(F_2)\cup ... \cup \Pi _{R_n}(F_n)$ ,则称$\rho$具有函数依赖保持性

模式分解算法#

• 要求分解保持函数依赖,模式分离总可以达到3NF, 不一定能达到BCNF

• 要求分解既保持函数依赖又具有无损连接性,可以达到3NF,不一定能达到BCNF

• 要求分解具有无损连接性,一定可以达到4NF

• 算法(合成法)达到3NF且保持函数依赖的分解算法

  • 输入:给定关系模式R<U,F>
  • 输出:$\rho=\{R_1,...,R_k\},R_i \in 3NF, i=1,...,k$
  • 步骤:
    • 求R的最小函数依赖集F’
    • 找出不在F’中出现的属性$U_0$,将他们构成一个关系模式$R_0<U_0,F_0>$,并从U中去掉它们(剩余属性仍记为U)
    • 若有X->A,且AX=U,则$\rho=\{R\}$,算法终止
    • 否则,对于F’中的每个X->A,构成一个关系模式XA.如果F’中有(左部相同)A->A1,X->A2,…,X->An,则可以用XA1…An代替掉n个模式XA1,…,XAn,$U_i=\{XA_1...A_n\}$;如果发现某个$U_i \subseteq U_j$,则应将$U_i$去掉
    • $\rho = \{R_1<U_1,F_1>,...,R_k<U_k,F_k>\} \cup R_0<U_0,F_0>$

• 算法：达到3NF既保持函数依赖又无损连接的分解

  • 设$\rho=\{R_1<U_1,F_1>,...,R_k<U_k,F_k>\}$是R<U,F>的一个保持函数依赖的3NF分解（由上面一个算法获得）
  • 设X为R<U,F>的码，
    • 若有某个$U_i, X \subseteq U_i$，则$\rho$即为所求
    • 否则令$\tau=\rho \cup \{R^*<X,F_x>\}$,$\tau$即为所求
    • 如果发现某个$U_i \subseteq X$,则应将$U_i$去掉

关系模式存取方法#

确定数据库存储结构#

• 确定数据的存放位置
  • 为了提高系统性能，应该根据应用情况将数据的易变部分、稳定部分、经常存取部分和存取频率较低部分分开存放
• 确定系统配置

评价物理结构#

• 存储空间
• 存取时间
• 维护代价

数据存储概述#

面向内存 VS 面向磁盘

• 数据库存储管理目标
  • 允许DBMS管理可超过内存大小的数据库
  • 由于读写磁盘代价很高，存储管理要能够避免大的延时和性能下降
  • 由于磁盘随机访问比顺序访问慢很多，DBMS希望能最大化顺序访问
• 磁盘块访问的优化
  • 缓冲
  • 预读取
  • 调度
  • 文件组织
  • 非易失写缓冲区
  • 日志磁盘
• 面向磁盘的DBMS
  • 特征：
    • 数据库文件存储在磁盘上，数据被组织成”页“，第一页是目录页
    • 缓冲池管理和磁盘的内存间数据交换：磁盘I/O对性能影响巨大

数据库存储结构#

• 文件存储
  • DBMS通常按一定的自有、专有格式组织并将数据库存储在一个或多个磁盘文件中。OS并不知晓这些文件的组织形式和内容。
  • DBMS的存储管理器：负责数据库文件的管理，将文件组织为”页“的集合，追踪页面数据的读写操作，追踪可用的存储空间
• 页设计
  • 数据库的页是一个固定大小的数据块
  • 页可以容纳
    • 不同类型数据：元组、元数据、索引、日志记录等
    • 数据一般不能混合存放，即一个页只存放一类信息（比如元组）。
    • 一些DBMS要求页面是“自包含”的
  • 页ID：每个页具备唯一ID
    • 当数据库只有单文件时，页面ID可以就是文件中的偏移地址
    • 当有多个文件时，大部分DBMS会有个间接层来映射页面ID到文件的路径和偏移地址，系统访问页面号时，存储管理器将其转换为文件路径和偏移地址
• 页的堆文件组织方式
  • 关系是记录的集合，这些记录在数据库文件中可以有3中组织方式
    • 堆文件组织
    • 顺序文件组织
    • 散列文件组织
  • Heap文件是一个无序的page集合，其中的元组可按随机顺序存放
    • 支持page的创建、读、写和删除操作
    • 支持遍历所有pages的操作
  • 堆文件的2种表示方式
    • 链表
      • 以链表的形式将文件中的空闲页和数据页分别勾连起来
      • 堆文件头部设立一个header page,并存放俩个指针，分别指向
        • 空页列表头部
        • 数据页列表头部
      • 每个page均记录当前空闲的空槽slot
    • 页目录
      • 维护一种特殊的页面（页目录），用于记录所有的数据页的存放位置
      • 该目录页同时记录每个页面的空槽信息
      • 页目录将页面的状态信息集中u村南方在一起，可提高查找特定页面的速度
      • DBMS必须保持目录页于所有页的<page_id, relative_offset, free_space_size>同步
• 页的组织结构
  • 页头：包含有关页内容的元数据信息
    • 页大小 校验 DBMS版本 事务可见性 压缩信息
    • 有些系统要求页面是自包含的
  • 数据区：存放数据的区域，其存放方式：
    • 面向元组型
      • strawman idea
        • 记录页内的元组数，类似数组的方式进行存储
        • 每次添加的元组放在已有元组的后面
        • 存在问题：
          • 删除元组时会产生碎片
          • 变长元组可能产生其它更多问题，比如元组的查询开销
      • 槽页：slot数组将槽位映射到元组开始的位置的偏移量
        • Header记录已经占用的槽位 和 最后一次使用的槽的起始位置偏移
        • 元组：在页内倒序存放
        • 元组在内部的唯一标识符：page_id+offset/flot，页可包含文件位置信息
        • 定长和变长元组都可处理
      • 元组设计
        • 一个元组在页中本质上是一个“字节序列”
        • DBMS负责将这些字节解释为各个属性的类型和值
        • 记录包括：记录头、记录数据
        • tuple header:每个元组有一个前缀为header的元数据
          • 页中无需存放关系模式信息，专门的catalog page可有效减少重复信息
        • tuple data:实际数据，基本上按属性顺序存放
        • 定长记录：全部由定长字段组成
          • 定长记录的插入和删除容易实现
          • 注意内存对齐问题
        • 变长记录：允许记录中存在一个或多个变长字段。变长字段在记录中的偏移位置不确定
          • 将所有定长字段放在边长字段之前，记录头增加：记录长度+非第一个变长字段的offset
          • 保持记录定长，变长部分放在另一个溢出页
        • 物理上非规范化元组设计：（预连接）将相关的元组存放在一个页或相邻页中
          • 可以有效减少相应查询的I/O次数
          • 也可能带来额外的数据维护开销
    • 日志结构型
      • DBMS不存储元组，值存储日志记录
      • 系统添加日志记录来反应数据库更新的结果
        • 插入：存放整个元组
        • 删除：标记该元组被删除
        • 更新：记录被修改的属性的变化
      • 当需要读取日志记录，DBMS可以反向扫描日志，重新创建元组，还可以“回滚”
      • 日志可定期压缩（通过删除不必要的记录来合并日志文件）
      • 日志文件组织
        • 不同数据通常可能在不同的page，如果将更新信息写到数据页，需要访问多个page
        • 将数据更新信息写道一个或者连续页效率更高
        • 可建立“日志索引”，方便查找相关的日志记录
        • 定期压缩日志，取出不必要的记录

系统目录#

• DBMS将数据库的元数据（描述信息）存放在内部的目录（数据字典）中
  • 表、列、索引、视图
  • 用户、权限
  • 数据的统计信息
  • 存储过程、触发器等

存储模型#

• 联机事务处理OLTP —> 行存储
• 联机分析处理OLAP —> 列存储
• 复合事务分析处理HTAP 为了适应OLTP或OLAP不同的工作负载，DBMS可采用不同方式进行元组存储
• NSM 行存储
  • 行存储模型非常适合OLTP
  • 单个元组读所有属性连续分布在一个page中，查询往往涉及单个实体（工作量较烧），并能够适应较为繁重的“更新”工作量
• DSM 列存储
  • DBMS将单个属性的值连续组织在一个page中，按列存储
  • 更是个OLAP ，可以很好的适应大数据量、复杂查询语义、高负载查询
    • 如何进行“元组标识”
    • 选择1：固定长度偏移，对某个属性每个值具备相同宽度
    • 元组ID嵌入，每个值于其元组ID一起存放
  • 优点：
    • 由于只读取需要的数据，减少了对无用数据的I/O
    • 更便捷的查询处理
    • 有利于数据压缩的实现
  • 缺点：
    • 数据被拆分，有些查询需要缝合，影响查询速度，也同时影响增删改效率

工作原理#

• 执行引擎在语句处理过程中需要使用某个数据页时，会像缓冲池提出请求
• 缓冲池管理器负责将该页面从磁盘读入内存，并向执行引擎提供该页面在内存中的指针
• 当执行引擎操作那部分内存时，缓冲池管理器必须确保该页面始终在内存区域中

本节重点：DBMS如何管理数据在磁盘和缓存之间的交互，缩小CPU速度与磁盘速度之间的鸿沟

• 缓冲池的作用
  • 减少磁盘I/O，提升页面读写效率
    • 读操作时，若所需页面已加载到缓冲池，就不需要从磁盘读了
    • 写操作时，如果多次修改了同一页面，只需要写一次磁盘
  • 缓冲池管理目标：尽可能减少磁盘I/O带来的延时

缓冲池结构#

• 缓冲池是在DBMS内部分配的一大片内存区域，用于存储从磁盘获取的页面

• 用于缓存页面的内存空间被粗制为一个数组，其中每个数组向被称为一个帧，一个真正好能放置一个页面

• 页表是缓冲池管理器用于维护缓冲池元数据的数据结构

• 缓冲池页表：

  • 页表：是一个内存散列表，用于等级当前已加载到缓冲池中的页面的信息

• 页表为缓冲池中每个页面维护以下信息：

  • 位置信息：页面在缓冲池中对应帧的位置
  • 脏标志：页面被修改过的标志。如果一个页面被设置了脏标志，则缓冲池管理器必须确保将其写回磁盘
  • 引用计数：当前正在访问该页的线程数量。如果某页的引用计数大于零，则不允许淘汰该页(pin)

缓冲池管理策略#

• 锁lock vs 闩 latch

• 锁和闩分别用于DBMS中两个级别的并发控制

• 锁：事务级

  • 保护的是数据库中的逻辑对象，如表、元组等
  • 持锁时间较长，一般直到事务提交才释放
  • 上锁期间对上锁对象的修改可以回滚

• 闩：（进程）线程级

  • 保护的是DBMS中多线程/进程共享的内部数据结构（临界资源），如帧
  • 一般用OS的同步机制（如信号量）实现，加闩时间短，操作完立刻释放
  • 加闩期间的修改无需考虑回滚

• 分配策略：关于缓冲池中的内存空间如何分配的问题，缓冲池管理器采取2中策略：

  • 全局策略
  • 局部策略

缓冲池替换算法#

• LRU算法：为每个页面维护其最后一次被访问的时间戳，需要淘汰页面时，DBMS总是选择淘汰时间戳最早的页面

  • 把入缓冲池的页放在LRU的头部，作为最近访问的元素，从而最晚被淘汰。为了减少数据移动，一般用链表实现
    • 页已经在缓冲池里：只把页面移动至LRU头部的动作，没有页面被淘汰
    • 页不在缓冲池里：除了放入LRU头部的动作，还要淘汰LRU尾部页的动作

• CLOCL算法：页称为近似LRU算法，为每个页面维护一个引用位，当某个页面被访问时，就将其引用位置为1。需要淘汰页面时候，循环扫描缓冲池中的页面检查各页面的引用位是否为1.如果是，则将引用位置为0并移动指针到下一个页面；否则淘汰当前页。

• LRU算法和CLOCK算法的缺点：

  • 预读失效：由于预读，提前把页放入了缓冲池，但最终DBMS并没有从页中读取数据
  • 顺序洪泛：因一次顺序扫描需要将表的所有页面读入缓存，导致缓存污染

• LRU-K算法

  • 核心思想：将淘汰页面时锁考察的最近访问次数由1提升为K
  • 维护两个队列：
    • 历史队列：保存着新进入内存的页面及其访问次数，还有每一次的访问时间，当一个页面的访问次数达到K此，则将该页面保存至缓存队列；若历史队列满了，则根据一定的淘汰策略淘汰
    • 缓存队列：保存着已经访问过K此的页面，当该队列满了之后，则根据LRU策略淘汰倒数第K次访问距离现在最久的那个页面

• 要优化预读失效

  • 让预读失败的页，停留在缓冲池LRU里时间尽可能短
  • 让真正被读取的页，才挪到缓冲池LRU的头部

• 具体方法：

  • 将LRU分为新生代、老生代
  • 新老生代首尾相连
  • 新页加入缓冲池时，只加入到老生代头部
  • 若数据真正被读取（预读成功），才会加入新生代头部

• 脏页的处理：

  • 快速：优先淘汰非脏的页（可能留着用不到的脏页）
  • 慢速：写回磁盘再淘汰
  • 后台写：定时写

缓冲池的优化#

• 多缓冲池
  • DBMS维护多个用于不同目的的缓冲池
  • 可以是多个缓冲池实力，每个数据库使用一个缓冲池每种页面类型使用一个缓冲池
  • 各缓冲池可以采用量身定制的管理策略
• 预取
  • 再处理第一组页面时，DBMS优先将第二组页面读取到缓冲池中
  • 顺序访问的时候使用该方法
• 扫描共享：某些查询结果可以公用
  • 将多个查询附加到一个游标上，查询游标可以重用从磁盘读入的数据或操作符的计算结果，减少重复访问的次数
• 缓冲池旁路
  • 为避免开销，顺序扫描操作符不会将获取的页存储再缓冲池中，而是使用正在运行的查询的本地内存
  • 如果操作符需要读取磁盘上连续的大量页序列，那么这种方法可以很好的工作
  • 缓冲池旁路页可以用于临时数据，入排序、连接

查询处理步骤#

• 查询分析

• 查询检查

• 查询优化

• 查询执行

• 查询计划：

  • 操作算子以树的形式进行组织
  • 数据流从叶子节点流向根节点
  • 根节点的输出是查询的结果

查询处理模型#

处理模型定义系统如何执行一个查询计划，不同的任务负载对应不同的权衡结果

• 迭代模型：每个查询计划的算子执行一个next函数

  • 也称作火山模型/流水线模型
  • 该计算模型将关系代数中的每一个操作抽象为一个operator，将整个SQL构建成一个operator树，查询树子顶向下的调用next()接口，数据则自底向上的被拉取处理
  • 每次调用next得到一个元组，或者一个空值标记
  • 算子通过循环调用它的子节点的next函数用于获取元组进行，当处理完成后再通过next函数获取下一个元组处理组进行处理，直到得到一个null
  • 获取磁盘数据代价太大，需要它在内存中做足够多的操作
  • 特点
    • 几乎所有的DBMS都采用该模型，允许元组流水线
    • 流水线的好处
      • 消除读和写临时关系的代价，从而减少查询计算代价
      • 流水线产生查询结果，边生成边输出给用户，提高相应时间。很容易控制输出，如limit操作
    • 有些算子会阻塞数据的流动，直到其子节点发送所有的元组，如join操作，子查询操作，排序操作

• 物化模型

  • 算子一次性获取它所有的输入，当处理完成后再返回给它的父节点
  • 算子能物化其输出作为一整个结果
  • 为了避免下层算子返回的数据量过大，上层算子可以尽可能提供多的过滤条件.DBMS会将一些参数传递到操作符中，防止处理过多的数据
  • 输出可以是整个元组(NSM存储模式)，或属性自己(DSM存储模式)
  • 特点：
    • 适合OLTP，一次处理少量数据
    • 相对火山模型，较少的函数调用，能减少不必要的执行、调度成本
    • 不适合OLAP，AP查询可能产生较大的中间结果

• 向量/批量模型

  • 执行框架同火山模型
  • 不同之处是每次调用Next函数，返回的是一批batch元组而不是一个元组。操作符内部的循环每次也是一批一批的处理
  • 特点：
  • 介于火山模型和物化模型之间
  • 适用于OLAP
  • 允许用户适用向量化的SIMD指令处理批量元组

• 查询树处理的方向

  • 自顶而下：从根节点开始不断的向子节点拉去数据，元组通过函数调用传递
  • 自底向上：从叶子系欸但开始获取数据不断的向父节点推送数据

数据存取#

• 数据存取方法：访问存储在表中的数据的方法。并没有在关系代数中被定义

• 顺序扫描

  • 对于表的每一个page
    • 加载到bufferpool中
    • 对bufferpool的page中符合条件的tuple依次进行处理
    • DBMS内部维持一个游标指向上次访问的page/slot
  • 优化
    • zone map：预先计算一个页中的属性统计值（最大值，最小值，平均值），并存入zonema品种，在顺序扫描中根据zonemap来决定是否读取该页
    • late materialization：延迟缝合元组，直到查询计划的上层才缝合

• 索引扫描：通过索引来访问查询所需要的数据页

• 多索引扫描（位图扫描）

  • 对每个索引进行扫描，获取哪些指向满足单个条件的元组ID（或元组指针）
  • 根据谓词求取这些元组ID集合的交集或并集
  • 根据剩余的谓词（没有索引）过滤这些元组

• 连接操作典型实现方法

  • 嵌套循环方法
    • 对外层循环的每一个元组，检索内存循环中的每一个元组sc
    • 检查这连个元组在连接属性上是否先庚
    • 如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止
  • 排序-合并方法
    • 适合连接的诸表已经排好序的情况
    • 如果已经有序，O(m+n)
    • 否则O(mlog(m)+nlog(n))
  • 索引连接方法
    • 在内关系上建立连接属性的索引（如果原来没有）
    • 对外关系中每个元组，由连接属性的值通过内关系的索引查找相应的内关系元组
    • 把这些内关系元组和外关系元组连接起来，循环执行上一条和本条语句，直到外关系的元组处理完为止
    • 若I/O开销为C，则总开销M+(m*C)
    • 如果两个关系上均由索引时，一般把元组较少的关系作外关系效果比较好
  • hash join方法
    • 把连接属性作为hash码，用同一个hash函数把R和S中的元组散列到同一个hash文件中
    • 步骤
      • 划分阶段
      • 试探阶段，也称为连接阶段
    • 设内关系被划分成X个散列桶，$创建散列表的成本(m)+散列函数的计算开销*n+(m/X)*n$

• 连接算法的选择

  • 空闲内存：内存不够则无法适用内存中的hash连接
  • 连个数据集的大小
    • 若一个大表连接一个很小的表，则嵌套循环连接就比散列连接快
    • 若两个表都很大，则嵌套循环连接的CPU成本就比较搞
  • 是否由索引：单一有，选择索引连接。若连接属性上有两个B+树的索引的话，合并连接是好选择
  • 关系是否已经排序：有则选用合并连接
  • 结果是否需要排序：即使参与连接的是未排序的数据集，也可以考虑适用成本较高的合并连接
  • 连接的类型：等值？内连接？外连接？笛卡尔积？子连接？有些连接算法在某些情况下是不适用的
  • 数据的分布：若连接条件的数据是倾斜的，hash连接不是好选择
  • 多表连接：连接顺序的选择很重要

关系代数表达式等价转换规则#

• 笛卡尔积、自然连接的交换律和结合律
  • $E_1 \times E_2 \equiv E_2 \times E_1; \quad (R\times S)\times T \equiv R \times (S\times T)$
  • $E_1 ⟗ E_2 \equiv E_2 ⟗ E_1; \quad (R ⟗ S) ⟗ T \equiv R ⟗ (S ⟗ T)$
• 投影的串接律
  • $\pi_{A1,A2,...,An}(\pi_{B1,B2,...,Bm}(E)) \equiv \pi_{A1,...,An}(E)$
  • 在同一个关系上，只需要做依次投影运算，且一次投影时选择多列同时完成
• 选择的串接律
  • $\sigma_{F1}(\sigma_{F2}(E)) \equiv \sigma_{F1 \land F2}(E)$
  • 选择条件可以合并，使得一次选择运算就可检查全部条件，而不必多次过滤元组
• 选择与投影的交换律
  • 假设：选择条件F只设计属性A1,…,An —> 先选择，后投影
  • $\sigma_F (\pi_{A1,...,An}(E)) \equiv \pi_{A1,...,An}(\sigma_F(E))$
  • 假设：F中有不属于A1,…,An的属性B1,…,Bm —> 先做带选择条件中的列投影，然后选择，再完成最外层投影
  • $\pi_{A1,...,An}(\sigma_F (E)) \equiv \pi_{A1,...,An}(\sigma_F(\pi_{A1,...,An,B1,...,Bm}(E)))$
• 选择与笛卡尔积的交换律
  • 若F中设计的属性都是$E1$中的属性
  • $\sigma_F (E_1 \times E_2) \equiv \sigma_F(E_1) \times E_2$
  • 若$F=F_1 \land F_2$,并且$F_1$只涉及$E_1$中的属性，$F_2$中只涉及$E_2$中的属性，则：
  • $\sigma_F(E_1 \times E_2) \equiv \sigma_{F_1}(E_1) \times \sigma_{F_2}(E_2)$
  • 若$F=F_1 \land F_2$,$F_1$只涉及$E_1$中的属性，$F_2$涉及$E_1$和$E_2$的属性，则：
  • $\sigma_F(E_1 \times E_2) \equiv \sigma_{F_2}(\sigma_{F_1}(E_1)\times E_2)$
  • 部分选择再笛卡尔积之前先做
  • 条件下推到相关的关系上，先做选择后做笛卡尔积运算，这样可以减小中间结果的大小
• 选择与并的分配律
  • 假设：$E= E_1 \cup E_2$,$E_1,E_2$有相同的属性名，
  • $\sigma_F(E_1 \cup E_2) \equiv \sigma_F(E_1) \cup \sigma_F (E_2)$
  • 条件下推到相关的关系上，先选择后做并运算，可以减小每个关系输出结果的大小
• 选择与差的分配律
  • 假设$E_1,E_2$有相同的属性名
  • $\sigma_F(E_1-E_2) \equiv \sigma_F(E_1)-\sigma_F(E_)2$
  • 先选择后做差运算
• 选择与自然连接的分配律
  • 假设：$E_1,E_2$使两个关系表达式
  • $\sigma_F(E_1 ⟗ E_2) \equiv \sigma_F(E_1) ⟗ \sigma_F(E_2)$
  • 先选择后做自然连接运算
• 投影与笛卡尔积的分配律
  • 设$E_1,E_2$是两个关系表达式，$A_1,...A_n$是$E_1$的属性，$B_1,...,B_m$是$E_2$的属性，则
  • $\pi_{A_1,...,A_n,B_1,...,B_m}(E_1 \times E_2) \equiv \pi_{A_1,...,A_n}(E_1) \times \pi_{B_1,...,B_m}(E_2)$
  • 先投影后做笛卡尔积
• 投影与并的分配律
  • 设$E_1,E_2$有相同的属性名
  • $\pi_{A_1,...,A_n}(E_1 \cup E_2) \equiv \pi_{A_1,...,A_n}(E_1) \cup \pi_{A_1,...,A_n}(E_2)$
  • 先投影后做并操作

查询树的启发式规则#

• 转换的最终目的

  • 减少查询的开销（I/O次数）

• 转换的直接目的

  • 减少中间关系的元组数、元组大小

• 规则1：选择运算尽早执行（减小中间结果的规模）

• 规则2：将选择、投影运算同时进行（避免重复扫描）

• 规则3：把投影同其前或其后的双目运算结合（避免重复扫描次数）

• 规则4：把选择运算与其前面的笛卡尔积运算结合起来一起计算（避免重复扫描并减小中间结果集的规模）

• 规则5：把公共子表达式的运算结果存放在外存，作中间结果，使用时读入主存。如：视图表达式（避免重复计算）

• 关系表达式代数优化算法

  • 运用选择的串接定律，得到选择运算“串”
  • 对每个选择运算符，利用等价变换尽量将其移至树的叶端
  • 对每个投影运算符，利用等价变换尽量将其移至树的叶端
  • 尝试将选择和投影串接合并成单个选择或投影，或选择后跟一个投影
  • 上述得到的语法树内节点分组：双目运算和它的父节点为一组。若其后代直至叶节点全部是单目运算，也合并为一组。笛卡尔积的子节点如果不能组合成等值的连接的选择，则二者不合并

基于启发式规则的优化#

• 选择操作的启发式规则：
  • 对于小关系，使用全表扫描了，即 使选择列上有索引
  • 对大关系
    • 如果是主码值上的等值查询“主码=值”，使用主码索引
    • 如果是非主码值上的等值查询，在选择比例<10%的情况下，使用索引（如果有）；否则使用全表扫描
    • 如果非等值或范围查询，在选择比例<10%的情况下是，使用索引（如果有）；否则使用全表扫描
    • 对于用AND连接的合取选择条件，如果有涉及折写属性的组合索引，优先采用组合索引扫描方法；如果某些属性上有一般索引，则可以用索引扫描方法；否则使用全表顺序扫描
    • 对于用OR连接的析取选择条件，一般使用全表顺序扫描
• 连接操作的启发式规则
  • 如果2个表都已经按照连接属性排序，使用选择-合并方法
  • 如果一个表在连接属性上有索引，选择索引连接方法
  • 如果上面两个规则都不使用，其中一个表较小，使用hash join方法
  • 可以选用嵌套循环方法，并选择其中占用块较小的表，作为外表（外循环的表）

基于代价的优化#

• 为什么采用启发式规则

  • 可能造成查询优化过程的开销大于获得的查询开销的大小，得不偿失

• 查询代价估算

• 查询代价估算基于CPU代价和I/O代价，

  • $总代价=I/O代价+CPU代价$
  • $COST = P * a\_page\_cpu\_time + W * T$
  • P是计划运行时访问的页面数，a_page_cpu_time是每个页面读取的时间开销，其成绩反应了I/O开销
  • T为访问的元组数量，如果是索引扫描，还要考虑索引读取的开销，反应了数据读取到内存的CPU开销
  • W为权重因子，表明I/O到CPU的相关性，有称选择率

数据转储#

• 静态转储与动态转储
  • 静态：
    • 在系统无运行事务时进行的转储操作
    • 转储开始时数据库处于一致性状态
    • 转储期间不允许对数据库的任何存取、修改活动
    • 得到的一定是一个数据一致性的副本
    • 优点：实现简单
    • 缺点：停止了一切事务运行，降低了数据库的可用性
      • 转储必须等待正在运行的用户事务结束
      • 新的事务必须等待转储结束
  • 动态：转储操作与用户事务并发进行，转储期间允许对数据库进行存取或修改
    • 优点：不用等待正在运行的用户事务结束，不会影响新事务的运行
    • 缺点：不能保证副本中的数据正确有效
    • 解决：需要把动态转储期间各事务对数据库的修改活动等级下来，建立日志文件
    • 后备副本加上日志文件才能把数据库恢复到某一时刻的正确状态。
• 海量转储与增量转储
  • 海量转储：定期或不定期将DB全部数据转储
    • 优点：简单
    • 缺点：重复转储，转储量大；停止运行（多为静态转储）
  • 增量转储：只转储上次转储后更新过的数据：
    • 优点：备份量小
    • 缺点：恢复过程比较复杂

日志#

• 先写日志后写数据规则
• 对日志文件中的记录进行REDO的时候，要按照日志序号递增的顺序进行，即正向扫描日志文件进行REDO
• 对日志文件中的记录进行UNDO的时候，要按照日志序号递减的顺序进行，即反向扫描日志文件进行UNDO

多粒度封锁#

• 允许多粒度树中的每个节点被独立的加锁
• 对一个节点加锁以为着这个节点所有后裔节点页被加同样类型的锁