数据库系统学习笔记

第1讲数据库的基本知识与关系模型#

什么是数据库#

数据库是电子化信息的集合。
数据库起源于规范化表的处理
数据库是相互之间有关联关系的Table的集合

什么是数据库系统#

数据库系统分为数据库、数据库管理系统、数据库应用、数据库管理员
数据库管理系统
- 数据库定义: 定义数据库中Table的名称、标题
- 数据库操纵: 向数据库的Table中增加/删除/更新数据及对数据进行查询、检索、统计等
- 数据库控制: 控制数据库中数据的使用
- 数据库维护: 转储/恢复/重组/性能监测/分析…
数据库语言
- 数据定义语言 DDL
- 数据操纵语言 DML
- 数据控制语言 DCL
DBMS的功能
- 语言编译器、查询优化与查询实现、数据存取与索引、通信控制
- 事务管理、故障恢复、安全性控制、完整性控制、数据字典管理、应用程序接口、数据库数据装载、重组等实用程序、数据库性能分析

第2讲数据库系统的结构抽象与演变#

数据与模式#

模式: 对数据库中数据所进行的一种结构性的描述/所观察到的数据的结构信息, 是对视图的抽象。
视图/数据: 某一种表现形式下表现出来的数据库中的数据。
数据库的标准结构: 三级模式、两层映像

三级模式#

外模式: 对用户所看到的局部的数据的一种描述。
概念模式: 数据之间内在的本质的联系(全局性的)。
内模式(物理模式): 存储在介质上的数据的结构描述。

两层映像#

E-C映像: 外模式映射为概念模式的映像, 实现转换, 便于用户观察和使用。
C-I映像: 概念模式映射为内模式的映像, 便于计算机存储和数据的处理。

两个独立性(三级模式、两层映像所实现)#

避免应用程序在开发时不断修改

逻辑数据独立性: 概念模式变化时, 可以不改变外部模式(只改变E-C Mapping), 从而无需改变应用程序。
物理数据独立性: 内部模式变化时, 可以不改变概念模式(只改变C-I Mapping), 从而不改变外部模式。

数据模型#

数据模型: 规定模式统一描述方式的模型, 包括: 数据结构、操作和约束, 是对模式本身结构的抽象(而模式是对数据本身结构形式的抽象)。
ep. 关系模型: 所有模式都可为抽象表的形式[数据结构], 而每一个具体的模式都是拥有不同列名的具体的表。对这些表形式的数据有哪些[操作]和[约束]。
ep. 理解: 模式指代一定数据结构组成的抽象表(是对于数据的结构的抽象), 数据模型则定义了其统一描述的方式(是对模式的结构的抽象)。
图例理解

三大经典数据模型#

关系模型: 表的形式组织数据(传统模式)
层次模型: 树的形式组织数据(实体型-系型,即节点-线, 以指针指向记录)

PS: 模式可以理解为表头?
网状模型: 图的形式组织数据(实体型-系型,即节点-线, 与层次模型类似, 如今使用不多)

PS: 网状模型中指针需要用户建立。

发展史 30:00#

数据库技术的简要发展史#

数据库技术探索阶段(59-65/67): 正式提出Database概念
数据库技术确立阶段(65/68-75): 研究形成关系数据库理论基础, 开始商用
数据库技术成熟阶段(76-80s前期): 提出标准化数据库系统结构模型, 关系理论日益完善, 应用普及
数据库技术深化发展阶段(85年以来): 数据库方法逐步理论化, 设计理论不断完善, 出现面向各行各业的专用数据库

演变与发展#

文件系统(存储基本以记录为单位, 用户无需考虑存储的物理细节。但数据与程序紧密结合, 共享性差、冗余度大)
层次、网状模型数据库(DBMS调用操作系统的函数对数据库存储和处理, 整体数据结构化, 多个应用程序可共享数据及数据结构的操作, 方便了应用程序的编写和使用。数据共享程度高、数据冗余度小、有统一的数据控制功能。但数据之间由复杂的指针系统维系, 结构描述复杂, 不能有效支持记录集合的操作)
关系模型数据库(不需要用户建立指针, 结构表征简单: 由属性的值表征, 不依赖于路径信息或过程信息, 支持非过程化的数据操作, 有效支持记录集合的操作。但必须按行列组织数据即1NF, 数据项不可再分)
对象关系数据库、面向对象数据库(引入了对象概念 - 行对象和列对象: 聚集对象与结构对象, 有效支持不满足1NF的数据项, 支持面向对象的特性: 类、继承、封装、多态)

XML数据库: 数据库的另一种形式, 被称为半结构化数据库, 封装在文件当中。数据与数据的语义合并在一起进行存储和处理。(类似HTML)
由多种多样的数据库到多数据库(ODBC\JDBC | Oracle\Java)开放式互连。
由普通数据库到与各种先进技术结合所形成的新型数据库。

总结#

第2讲课程的图总结

第3讲关系模型之基本概念#

关系模型的概述#

关系模型的三要素:

基本结构: Table
基本操作: 并、差、广义积、选择、投影、交、连接、除
完整性约束: 实体完整性、参照完整性、用户定义完整性
关系代数: 基于集合的运算, 是一次一集合的操作, 是一种数学语言

关系运算 -> 关系数据库语言 -> DBMS的实现

什么是关系#

“表”的严格定义

首先定义列的取值范围域(一组值的集合), 集合中元素的个数称为域的基数。
定义元组及所有可能组合成的元组: 笛卡尔积(根据N个域形成的所有可能的n-元组的集合)。笛卡尔积的每个元素(d1,d2,…,dn)称为一个n-元组, 每个值di叫做一个分量。
关系: 一组域的笛卡尔积的子集(笛卡尔积中抽出来的有意义的组合), 此时列名(对关系当中这一列的含义取名)称为属性名。

关系模式是稳定的(结构), 而关系是某一时刻的值, 是随时间可能发生变化的。
关系的特性

列是同质: 每一列中的分量来自同一域, 是同一类型的数据(即每一列的数据类型必须相同)
不同列可来自同一个域: 每一列为一个属性, 不同的属性要给不同的属性名
列位置互换性、行位置互换性: 区分列靠列名、区分行靠某一或几列的值(关键字)
理论上, 关系的任意两个元组不能完全相同。(但Table不完全遵守这个特性)
属性不可再分特性: 又称为关系第一范式, 不能存在复合属性或属性再分的情况。

关系中的概念

候选码: 关系中的一个属性组, 其值能唯一标识一个元组。(从该属性组中去掉任何一个属性都不再具有这个特性)这样的属性组称为候选码。有时关系中有很多组候选码。
主码(主键): 从若干候选码中选定一个作为主码, DBMS以主码为主要线索管理关系中的元组。
主属性与非主属性: 包含在任何一个候选码中的属性称为主属性。
全码: 所有属性构成这个关系的候选码(最极端的情况)。
外码(外键): 是关系R中的属性组但不是候选码, 但其与另一个关系S的候选码相对应。两个关系之间通常靠外码连接。外码是连接两个或多个关系的纽带。

关系是严格的数学的定义, 没有重复的原则, 但表是可以的。

关系模型中的完整性约束#

完整性约束规则

实体完整性: 关系的主码中的属性值不能为空值(不知道或无意义的值)。
参照完整性: 外码可以为空值, 但不为空值时必须为外表的主码(例如分配学生所在的系)。
用户自定义完整性: 用户针对具体的应用环境定义的完整性约束(例如年龄在多少之间\性别等)。此定义机制通常由DBMS提供使得用户可以自行定义、由DBMS检验操作的正确性。

总结#

第3讲课程的图总结

第4讲关系模型之关系代数#

关系代数之基本操作#

关系代数运算的特点

基于集合, 提供了一系列的关系代数操作。
关系代数以一个或多个关系作为输入, 结果是一个新的关系。
具有一定过程性, 用对关系的运算来表达查询。
是一种抽象的语言, 是学习其它数据库语言的基础。

基本操作
关系代数的基本操作

并(*并相容) R∪S = S∪R: 将两个关系的元组合并成一个关系, 在合并时去重。用于查询XXX、XXX中至少参加了一个的信息。
差(*并相容) R-S / S-R: 是…但不含…, 用于查询只参加XXX而未参加XXX的信息。
广义笛卡尔积 R×S = S×R: 关系R中的元组与关系S中的元组进行所有可能的组合拼接构成。拼接后元组数目相乘, 度数相加。用于检索涉及多个表时串接的运算。是后续学习各种连接运算的基础。
选择 σcon(R): 从关系R中选择出满足给定条件condition的元组构成。
投影 ΠA(R): 从关系R中选出属性包含在A中的列构成, 在合并时去重(因为对于关系来讲是集合, 在实际运用时默认不去重)。

关系代数运算的约束

某些操作, 如并、差、交等, 需满足并相容性 -> 关系R和关系S的属性数目相同, 且第i个属性的域(domain, 在table中表现为type)相同

关系代数之扩展操作#

扩展操作

交(*并相容) R∩S = S∩R = R-(R-S) = S-(S-R): 由同时出现在关系R和关系S中的元组构成, 用于查询既参加XXX又参加XXX的信息。
θ-连接(theta-join): R与S的θ连接运算结果也是一个关系, 记作。(可以理解为对笛卡尔积添加筛选条件)
更名 ρSC1(SC): 对表格进行更名以作为筛选条件的辅助操作。
等值连接(equi-join): θ-连接的特殊情况, 筛选条件中采用等值。
自然连接(natural-join): 等值连接的特殊情况, 要求关系R和关系S必须有相同的属性组B。R,S属性相同, 值必须相等才能连接。要在结果中去除重复的属性列。(实际上是最普遍使用的连接)

关系代数之组合与应用训练#

练习章节, 略过。主要要求根据表达特别注意语义和顺序。
书写关系代数表达式的基本思路

关系代数之复杂扩展操作#

除 R÷S: 查询…全部的/所有的…, 要求除属性集S是被除属性集R的真子集。结果的度数k=n-m。
验证方法: (R÷S)×S的元组都在R的元组中。
ep: 查询选修了全部课程的学生的学号。
外连接(outer-join): 与θ-连接相比, 连接时不会丢失元素(失配信息记为空值)。又进一步细分为左外连接、右外连接、全外连接。

总结#

章节重难点
关系代数的基本书写思路

选出将用到的关系/表
做积运算(可用连接运算替换)
做选择运算保留所需的行/元组
做投影运算保留所需的列/属性

章节回顾

关系模型的作用思想

第5讲关系模型之关系演算#

关系演算之关系元组演算#

按照谓词变量的不同, 可分为关系元组演算(以元组变量作为谓词变量的基本对象)和关系域演算(域变量)
基本形式: {t|P(t)} 表示所有使谓词P为真的元组t的集合

公式形式的完整定义
注意运算符优先次序(括弧;θ;全称量词;取反;and;or)导致的结果差异！

被存在量词或全称量词限定的元组变量被称为约束变量, 否则被称为自由变量。
存在量词: 全假则假, 一真则真; 全称量词: 全真则真, 一假则假

这一段的训练题非常多, 涉及到离散数学/概率论中的逻辑。可以看原视频深入了解。
四个最复杂的例子

“全都学过”: 视频44:09
“全没学过”: 视频49:32
“至少有一学过” 视频52:40
“至少有一没学过” 视频53:50

元组演算公式与关系代数的等价性

关系演算之关系域演算#

关系域演算公式
基本形式: {<x1,x2,…,xn>|P(x1,x2,…,xn)}
其中xi代表域变量或常量, P为以xi为变量的公式
构造示例
基于关系域演算的QBE语言

特点: 操作独特, 基于屏幕表格的查询语言, 只需将条件填在表格中
是一种高度非过程化的查询语言
适合终端用户的使用
操作框架由四个部分构成: 关系名区, 属性名区, 操作命令区, 查询条件区
操作命令: P.(Print), D.(Delete), I.(Insert), U.(Update)
查询条件形式为 θ 参量(省略θ则默认为=)
示例元素与投影:
- 用任何一个值带有下划线表示, 被称为示例元素
- 只用于占位(通过表格反映查询条件)
- 符号也可写在操作区, 表示对整行生效
- 可利用同一连接条件使用相同的示例元素, 实现多个表的连接
PS: 视频1:23:00有误, 满足例子条件的应该放在同一行。视频中的表格实现的是年龄大于19岁或男同学。

关系演算之安全性#

不产生无限关系和无穷验证的运算被称为是安全的

关系代数是一种集合运算, 是安全的(集合本身是有限的)
关系演算不一定是安全的(R(t)是有限的, 但不在R(t)中的元素可能是无限的)

所以需要对关系演算施加约束条件, 即安全约束有限集合DOM: 其为一个有限集合, 其中的每个符号要么是公式中明显出现的符号, 要么是出现在公式中的某个关系R的某元组的分量。
安全元组演算表达式
安全表达式解释
安全域演算表达式
同理。课程视频中未介绍。

关于三种关系运算的观点#

关系运算有三种: 关系代数、关系元组演算和关系域演算
三种关系运算都是抽象的数学运算, 体现了三种不同思维(以元组、集合、域变量为对象)
三种运算之间是(有条件: 即安全的元组/域演算表达式)等价的
三种运算都可以说是非过程性的: 域演算>元组演算>关系代数
三种关系运算虽然是抽象的, 但是是衡量数据库语言完备性的基础
数据库语言可以基于这三种抽象运算来设计

总结#

章节重难点
本讲主要是基于逻辑的思维, 讨论从关系演算->元组演算/域演算, 涉及到与、或、非、存在量词、全称量词。

第6讲 SQL语言之概述#

SQL语言概述#

SQL语言的发展历史

1974年由Boyce和Chamber提出
1975-1979年由San Jose研究室在System R首次实现, 称为Sequel -> SQL
1986年ANSI/ISO推出SQL-86标准
1989年ANSI/ISO推出SQL-89标准
1992年进一步提出SQL标准: SQL-92, 也称SQL2(标准关系数据库语言)
1999年进一步提出SQL标准: SQL-99, 也称SQL3(面向对象数据库/对象关系数据库)
SQL 2003/2006/2008(对数据库应用程序进行规范)
另有SQL X/Open标准, 强调各厂商产品的可移植性, 只包含被各厂商广泛认可的操作 -> 标准使得用户可以学习标准规定的语言, 而无需关注具体的软件产品(具体应用依然略有差异)

SQL语言的功能概述

SQL语言是集DDL、DML、DCL于一体的数据库语言
SQL语言主要由9个单词引导的操作语句构成:
- DDL: Create, Alter, Drop - 模式的定义和删除
- DML: Insert, Delete, Update, Select - 各种方式的更新与检索操作
- DCL: Grant, Revoke - 安全性控制
课程逐步递进: 交互式SQL -> 嵌入式SQL -> 动态SQL
课程要求: 理解查询(增删改查)需求、用SQL精确表达

SQL语言之DDL-定义数据库#

建立数据库: 包括定义数据库和表(使用DDL), 向表中追加元组(使用DML)
创建数据库的简单语法形式: create database 数据库名;
创建Table的简单语法形式: create table 表名( 列名数据类型 [Primary key|Unique] [Not null] [,列名数据类型 [Not null],…])

Primary key: 主键约束, 每张表只能创建一个。
Unique: 唯一性约束(即候选键), 每张表可以有多个。
Not null: 非空约束, 指该列不允许有空值出现。
语法中的数据类型在SQL-92标准中被定义。
- char(n): 固定长度字符串
- varchar(n): 可变长度字符串
- int: 整数, 有时不同系统为integer
- numeric(p,q): 固定精度数字, 小数点左边p位, 右边p-q位
- real: 浮点精度数字, 有时不同系统为float(n)
- date: 日期 (ep. 2003-09-12)
- time: 时间 (ep. 23:15:15:003)
和高级语言的数据类型总体一致, 但也有些差异

向表中追加元组的简单语法形式: insert into 表名[(列名[,列名]…)] values (值 [,值], …);

若列名未省略, 需与语句中列名的顺序一致; 若省略, 需与定义的列名顺序一致

修正数据库: alter table 表名 [add {列名数据类型,…}] [drop {完整性约束名}] [modify {列名数据类型,…]

add: 增加新列, drop: 删除完整性约束, modify: 修改列定义
注意: 现在一般不再使用modify, 转而使用column修改。视频使用的SQL版本较老, 现今可能有部分语法更新, 以最新语法为准

撤销基本表: drop table 表名;
撤销数据库: drop database 数据库名;
有些数据库有操作多个数据库的能力, 对此可以以以下命令做切换:
指定当前数据库: use 数据库名;
关闭当前数据库: close 数据库名;

SQL语言之DML-操纵数据库#

检索语句的简单语法形式: select 列名[[,列名]…] from 表名 [where 检索条件];

在检索结果中可能有重复元组, 若要求无重复则需使用DISTINCT保留字。
结果排序: order by 列名 [asc|desc] - asc或省略为升序, desc为降序
模糊查询: 列名[not] like “字符串”
- % 匹配零个或多个字符
- _ 匹配任意单个字符
- \ 转义字符

检索语句的多表联合查询: select 列名 [[,列名]…] from 表名1,表名2,… where 检索条件;

检索条件要包含连接的条件
如两个表的属性名相同, 则需采用表名.属性名的方式来限定该属性名属于哪一张表
如有表格重名/列名特别长的情况, 则需要用as设定别名以便区分(PS: 实际上在SQL中可以不添加as, 直接在空格后设定别名)

增、删、改、查

Insert: insert into 表名 (属性名[, 属性名, …]) (值[, 值, …])
Insert内可以嵌套Select语句
Delete: delete from 表名 [where 条件表达式]
不添加条件表达式则会删除表中所有元组
Update: update 表名 set 列名=表达式 | (子查询) [[,列名=表达式|(子查询)]] [where 条件表达式];
不添加where条件则会更新表中所有元组

创建表(T-SQL语句): create table [数据库名.所有者名.]表名 ({<列名数据类型>} [缺省值][约束][是否为空]);
创建、删除、修改约束: 在第9讲中详细介绍

典型DBMS交互环境 SQL Server介绍#

SQL Server是Microsoft提供的一款关系数据库管理系统。
系统数据库(SQL Server自带,自动安装)

Master: 存储SQL Server中的元数据
Model: 模板数据库, 在创建新数据库时会复制此数据库作为基础
Msdb: 代理服务数据库
Tempdb: 临时数据库, 为临时数据提供存储空间

SQL Server数据库

文件: 三种扩展名: 主数据库文件.mdf/辅助数据库文件.ndf/日志.ldf - 启动信息/所定义数据库的其它数据/事务日志文件
页面: SQL Server存储的最小单位, 一页为8KB
空间: 8个连续的页面即64KB数据, 是分配数据表存储空间的一种单位

数据库授权: grant 权限 on 表名 to 用户名

权限: select, update, insert, delete, exec, dri

总结#

章节重点与难点
SQL: 结构化查询语言

第7讲 SQL语言之复杂查询与视图#

子查询运用#

为什么需要子查询

集合成员资格判断
集合之间的比较
集合基数的测试(是否为空, 是否存在重复元组)

(NOT) IN子查询

基本语法: 表达式 [not] in (子查询)
语义: 判断某一表达式的值是否在子查询的结果中。
带有子查询的selcet语句区分为内层和外层
非相关子查询: 内层查询独立进行, 没有涉及任何外层查询相关信息的子查询
相关子查询: 内层查询需要依靠外层查询的某些参量作为限定条件才能进行的子查询, 外层向内层传递的参量需要使用外层的表名或表别名来限定
- (只能由外层向内层传递参数, 而不能反之, 也称为变量的作用域原则)

θ Some与θ All子查询

基本语法: 表达式 θ some/all(子查询) - θ是比较运算符
语义: 将表达式的值与子查询的结果进行比较
曾经有θany, 之后由于容易引起歧义, 改为了θsome
in 和 = some 等价, not in 和 <> all等价

(NOT) EXISTS子查询

基本语法: [not] exists (子查询)
语义: 子查询结果中有无元组存在

结果计算与聚集函数#

结果计算

select子句后面可以是一些计算表达式或聚集函数, 表明在投影的同时进行计算
内置的聚集函数: count(); sum(); avg(); max(); min()

分组查询与分组过滤#

分组查询与过滤

将检索到的元组按照某一条件进行分类, 同时处理多个组或集合的聚集运算
基本语法: select … from … [where …] group by 分组条件 [having 过滤条件]
聚集函数不允许用于where语句中!

利用SQL语言实现关系代数操作#

并-交-差处理

基本语法: 子查询 {Union [ALL] | Intersect [ALL] | Except [ALL] 子查询}
不带ALL则默认自动删除重复元组, 若要保留则需要带有ALL
交运算符intersect并没有增强sql的表达能力, 只是其增加了sql语言的不唯一性
这些运算都在SQL-99中, 但有些DBMS不支持这些运算, 要注意。

空值的处理

空值检测语法: is [not] null - 测试指定列的值是否为空值
现行DBMS的空值处理
- 除了is [not] null外不满足任何查找条件
- 若参与算术运算, 则该算术表达式的值为null
- 若参与比较运算, 则结果视为false
- 若参与聚集运算, 则除了count(*)之外都忽略null

内连接、外连接

基本语法: select 列名 from 表名1 [NATURAL] [INNER|{LEFT|RIGHT|FULL}[OUTER]] JOIN 表名2
连接类型和连接条件

部分总结
SQL-SELECT完整语法

视图及其应用#

视图在SQL中只存储其由基本表导出视图所需要的公式, 其数据并不存储, 而是在运行过程中动态产生与维护的
对视图数据的更改最终要反映在对基本表的更改上, 而有时视图定义的映射不可逆, 故视图的更新是比较复杂的问题
定义视图: create view 视图名 [(列名[, 列名] …)] as 子查询 [with check option]
若属性名缺省, 则默认为子查询结果中的属性名
with check option指明当视图进行增改删时, 要检查是否满足视图定义中子查询中定义的条件表达式

SQL视图更新的可执行性
SQL更新的可执行性

撤销视图: drop view 视图名

总结#

章节重难点
SQL: 结构化查询语言

第8讲 SQL语言与数据库完整性和安全性#

数据库完整性的概念及分类#

概念

数据库完整性指的是DBMS应保证的DB的一种特性——在任何情况下的正确性、有效性和一致性
广义: 语义完整性、并发控制、安全空值、DB故障恢复
狭义: 专指语义完整性, DBMS通常有专门的完整性管理机制与程序来处理语义完整性问题(本讲专指此)
不正当的数据库操作引发数据库完整性问题

数据库完整性管理的作用

防止和避免数据库中不合理数据的出现
DBMS应尽可能地自动防止DB中语义不合理现象的出现

怎样保证完整性

允许用户(DBA)定义一些完整性约束规则
当有DB更新操作时, DBMS自动按照完整性约束条件进行检查以确保更新操作符合语义完整性

完整性规则 ::=(O,P,A,R)

O: 数据集合: 约束的对象
P: 谓词条件: 什么样的约束
A: 触发条件: 什么时候检查
R: 响应动作: 不满足时怎么办

完整性的分类

按约束对象分类
- 域完整性约束条件: 施加于某一列上(仅涉及到一列)
- 关系完整性约束条件: 施加于关系/table上(可能涉及到多列)
按约束来源分类
- 结构约束: 来自模型的约束, 例如函数依赖约束、主键约束、外键约束
- 内容约束: 来自用户的约束, 例如用户自定义完整性
按约束状态分类
- 静态约束: DB在任一时候均应满足的约束
- 动态约束: 要求DB从一状态变为另一状态时应满足的约束

SQL语言之列约束与表约束——静态约束#

SQL语言支持的约束类别

静态约束: 列完整性、表完整性
动态约束: 触发器

实现约束的方法——Create Table

表约束通过逗号区分开这一列, 列约束则是随每一列而定义
Col_constr列约束
table_constr表约束
撤销/追加约束(不同系统可能有差异)

实现约束的方法——断言

就是一个谓词表达式, 表达了希望数据库总能表达的体哦阿健
表约束和列约束就是特殊的断言
SQL还提供了复杂条件表达的断言: CREATE ASSERTION <断言名> CHECK <条件>
断言测试会增加数据库维护的负担, 要小心使用复杂的断言

SQL语言之触发器——动态约束#

trigger是一种过程完整性约束, 可以在特定的时刻被自动触发执行
基本语法
新旧值用old_row_corr_name/new_row_corr_name/old_table_corr_name/new_table_corr_name区分
referencing new x, old y

阶段性总结#

数据库安全性的概念及分类#

概念: 数据库安全性是DBMS应该保证的数据库的一种特性: 免受非法、非授权用户的使用、泄漏、更改、破坏

DBMS的安全机制

自主安全性控制: 存取控制: 通过权限在用户之间的传递使得用户自主管理数据库安全性
强制安全性控制: 通过对数据和用户强制分类, 使得不同类别用户能访问不同类别的数据
推断控制机制: 防止通过历史信息推断出不该被其知道的信息；防止通过一些信息推断出私密信息
数据加密存储机制: 通过加密、解密保护数据

DBA的责任和义务

划分好数据的安全级别以及用户的安全级别, 实施安全性控制

数据库自主安全性机制的实现

DBMS允许用户定义一些安全性控制规则(用SQL-DCL定义)
安全性访问规则: AccessRule ::=(S,O,t,P)
- S: 请求主体(用户)
- O: 访问对象
- t: 访问权利
- P: 谓词
AccessRule通常存放在数据字典或系统目录中, 构成了所有用户对DB的访问权利
用户多时, 可以按用户组建立访问规则

example
example_2

亦可使用视图(view)进行安全性控制
用户定义视图后，其便成为一个新的数据对象，参与到存储矩阵与能力表中描述

SQL语言之安全性实现#

SQL语言的用户与权利

SQL-DCL的命令及其应用
grant

授予视图权利不代表授予基本表权利
授权者授予的权利必须是授权者已有的权利

(public为授权给所有用户)
revoke

授权的传播范围

当一个用户的权利被收回时, 通过其传播给其它用户的权利也将被收回

强制安全性机制

通过对数据对象进行安全性分级: Top Secret/Secret/Confidential/Unclassified
同时对用户也进行上述的安全性分级
强制实现不同级别用户访问不同级别数据的一种机制
但是高级别用户不允许写低级别数据
DBMS引入强制安全性机制, 可以通过扩展关系模式来实现, 使得关系中的每个元组扩展为带有安全分级的元组

阶段性总结#

总结#

章节重难点

第9讲嵌入式SQL语言之基本技巧#

嵌入式SQL语言概述#

交互式SQL语言的局限

大部分普通用户难以使用
特别复杂的检索结果难以用一条交互式SQL语句完成

高级语言 + SQL语言

既继承高级语言的过程控制性
又结合SQL语言的复杂结果集操作的非过程性
同时又为数据库操作者提供安全可靠的操作方式: 通过应用程序进行操作

典型特点(以宿主语言C语言为例)

exec sql引导SQL语句
增加into子句: 指出接收SQL语句检索结果的程序变量
由冒号引导的程序变量

高级语言中使用嵌入式SQL语言需要解决的问题

如何与数据库连接和断开连接
如何将宿主程序的变量传递给SQL语句
SQL语句如何执行
如何将SQL检索到的结果传递回宿主程序进行处理
静态SQL, SQL语句中的常量更换为变量
宿主程序如何知道SQL语句的执行状态, 是否发生错误
动态SQL, 依据条件动态构造SQL语句, 但欲访问的表名和字段名对编程者是已知的
动态SQL, 依据条件动态构造SQL语句, 但欲访问的表名和字段名对编程者是未知的

变量声明与数据库连接#

变量赋值时需要注意

宿主程序的字符串变量长度应比字符串字段的长度多1个(终止符\0)
宿主程序变量类型与数据库字段类型之间有些是有差异的, 有些DBMS可以支持自动转换, 有些不能
声明的变量可以在宿主程序中赋值, 然后传递给SQL语句

程序与数据库的连接和断开

在嵌入式SQL程序执行前要先连接数据库
连接语法(SQL标准中所建议的)
- exec sql connect to target-server as connect-name user user-name;
- exec sql connec to default;
断开连接语法(SQL标准中所建议的)
- exec sql disconnect connect-name;
- exec sql disconnect current;

SQL语句的执行和撤销

在执行过程中必须有提交和撤销语句才能确认其操作结果
SQL执行的提交: exec sql commit work;
SQL执行的撤销: exec sql rollback work;

事务的概念与特性

概念: (管理员角度)是一个存取或改变数据库内容的程序的一次执行(可以是一条或多条SQL语句)
概念: (DBMS角度)是数据库管理员提供的控制数据操作的一种手段, 以便数据库管理系统能提供一致性状态转换的保证
(要保证一组操作或者全都执行, 或者都不执行)
任何一条数据库操纵语句都会引发一个新事务的开始, 而事务的结束需要通过commit或rollback确认
特性(ACID)
- A原子性(保证事务的一组更新操作原子不可分)
- C一致性(保证事务的操作状态正确)
- I隔离性(保证并发执行的多个事务之间互相不受影响)
- D持久性(保证已提交事务的影响是持久的, 被撤销事务的影响是可恢复的)
具有ACID特性的若干数据库基本操作的组合体被称为事务
事务处理是DBMS的核心技术
示例
- 引入SQLCA
- 设置声明变量
- 设置SQL错误捕获语句
- 连接数据库
- 设置SQL语句, 进行提交
- 断开连接

数据集与游标#

检索单行结果, 可将结果之间传送到宿主语言的变量中
检索多行结果, 则需使用游标(cursor)
- 游标是指向某检索记录集的指针
- 通过这个指针的移动, 每次读一行, 处理一行, 再读一行,…,直至处理完毕
- 读一行操作是通过fetch…into语句实现的
- 记录集有结束标识EOF, 用来标记后面已没有记录了
游标的使用需要先定义, 再打开, 再处理数据, 最后关闭
游标可以定义一次, 多次打开, 多次关闭
cursor的定义: exec sql declare cursor_name cursor for …;
cursor的打开和关闭: exec sql open/close cursor_name;
cursor的数据读取: exec sql fetch cursor_name into host-variable, [host-variable,…];

可滚动游标与数据库的增删改#

标准的游标始终是自开始向结束方向移动的; 一条记录只能被访问一次; 再次访问该记录只能关闭游标后重新打开
ODBC提供了可滚动cursor的解决方案。许多DBMS不支持可滚动游标, 但是通过ODBC可以使用该功能
新增[SCROLL]选项
- NEXT向结束方向移动一条
- PRIOR向开始方向移动一条
- FIRST回到第一条
- LAST移动到最后一条
- ABSOLUT value_spec 定向检索指定位置的行
可滚动游标移动时需要判断是否到结束或起始位置(EOF/BOF, 不需区分则可通过whenever not found语句设置来检测)

数据的删除与更新#

查找删除: 与交互式delete语句相同
定位删除: 删除游标位置的数据(where current of delcust)
查找更新: 与交互式update语句相同
定位更新: 更新游标位置的数据(where current of declust)
插入: 与交互式insert into语句相同

状态捕获及错误处理机制#

状态: 是嵌入式SQL语句的执行状态, 尤其指一些出错状态
在嵌入SQL中, 状态捕获与处理的构成
- 设置SQL通信区(exec sql include sqlca;)
- 设置状态捕获语句(exec sql whenever sqlerror goto report_error;)
- 状态处理语句(report_error: exec sql rollback;)
SQLCA是一个已被声明果的具C语言的结构形式的内存信息区, 是DBMS与宿主程序之间交流的桥梁
状态捕获语句: exec sql whenever condition action; 设立条件陷阱
- SQLERROR: 检测是否有SQL语句出错, 具体意义依赖于DBMS
- NOT FOUND: 没有相应的结果记录
- SQLWARNING: 不是错误, 但是应当引起注意的条件
- CONTINUE: 忽略条件或错误, 继续执行
- GOTO 标号: 转移到标号所指示的语句
- STOP: 终止程序运行、撤销当前工作、断开数据库连接
- DO/CALL: 调用宿主程序的函数进行处理, 函数返回后从引发该condition的SQL语句之后的语句继续执行
状态捕获语句whenever的使用容易引发无限循环, 在处理函数中忽略其中的错误可避免无限循环
状态记录方法
- sqlcode: >0:warning;<0:error;==0:successful
- sqlca.sqlcode
- sqlstate

总结#

重难点
基本问题
本讲讲解了问题1-6。
嵌入式SQL

第10讲嵌入式SQL语言之动态SQL#

动态SQL的概念和作用#

静态SQL: SQL语句在程序中已经按要求写好, 只需要把一些参数通过变量传递给嵌入式SQL语句
动态SQL: SQL语句可以在程序中动态构造, 形成一个字符串再交给DBMS执行

SQL语句的动态构造#

动态SQL语句的执行方式#

立即执行语句: 运行时编译并执行
Prepaer-Execute-Using: 先编译, 编译后的SQL语句允许动态参数, 用USING语句将动态参数值传送给编译好的语句

数据字典与SQLDA#

数据字典(系统目录): 是系统维护的一些表或视图的集合, 存储了数据库中各类对象的定义信息, 这些信息又称为数据的元数据
- 包含与关系相关的信息
- 包含用户与账户信息, 包括密码
- 统计与描述性数据
- 物理文件组织信息
- 索引相关的信息
数据字典也是存储在磁盘上的关系, 但是专为内存高效访问而设计的特定的数据结构
模式是指某一用户所设计和使用的表、索引及其它与数据库有关的对象的集合, 完整名应是: 模式名.表名
SQLDA: SQL描述符区域, 是一个内存数据结构, 装载关系模式的定义信息

ODBC/JDBC简介#

ODBC是一种标准————不同语言的应用程序与不同数据库服务器之间通讯的标准
当应用程序调用ODBC API时, ODBC API会调用具体DBMS Driver库函数, 库函数则与数据库服务器进行通讯, 执行相应请求并返回结果
- 应用程序通过SQLExecDirect()向数据库发送SQL命令
- 使用SQLFetch()获取产生的结果元组
- 使用SQLBindCol()绑定C语言变量与结果中的属性
JDBC是Java版的应用程序接口API, 提供了Java应用程序与数据库服务器的连接和通讯能力
JDBC分成两个程序包: Java.sql 核心API/Javax.sql 可选扩展API

嵌入式SQL的思维模式: 建立数据库连接->声明一个游标->打开游标->获取一条记录->关闭游标->断开数据库连接

总结#

章节重难点
嵌入式SQL

第11讲数据建模: 思想与方法(数据库设计的抽象与表达方法)#

为什么要数据建模和数据库设计#

需求的理解和表达是很重要的
表达计算机世界的模型称数据模型; 表达信息世界的模型称概念数据模型, 简称概念模型
信息世界是对现实世界的理解与抽象
数据建模 -> 数据库设计
数据建模是抽象, 抽象是理解-区分-命名-表达

ER模型-数据建模之基本思想#

Entity-Relationship Model 实体联系模型
基本观点: 世界是由一组称作实体的基本对象和这些对象之间的联系构成的
基本概念: 实体、属性、联系、关键字/码

实体: 客观存在并可相互区分的事务
实体有类(实体, 实体的型)和个体(实体的实例, 实体的值)的概念
实体用属性来刻画: 属性是实体所具有的某一方面的特性
- 属性分为单一属性和复合属性, 在关系模型中复合属性一定要转化为单一属性(1NF)
- 属性还分为单值属性和多值属性, 比如一个人可能有多个电话号码。在关系模型中同样需要转化为单值属性。
- 属性分为可空值属性和非空值属性
- 属性分为原始属性和导出属性(由其它属性计算而得的)
实体中的特殊属性: 关键字/码, 实体中能用其值唯一区分开每一实例的属性或属性组合
实体之间是有联系的: 指一个实体的实例和其它实体实例之间所可能发生的联系
参与发生联系的实体的数目, 称为联系的度或元。联系有一元联系、二元联系和多元联系 | 实体是相对稳定的, 但联系是多样化的
角色: 实体在联系中的作用称为实体的角色。显式指明其角色以在同一实体的不同实例参与一个联系时区分各实例参与联系的方式
实体之间的二元联系有一对一、一对多、多对多的联系
联系的基数: 实体实例之间的联系的数量, 即一个实体的实例通过一个联系能与另一实体中相关联的实例的数目(关系到怎么保存)
联系的基数还要区分对每个实体的实例而言是否必须存在(完全参与联系: 最小基数1开始/部分参与联系: 最小基数0开始)(关系到空值的处理)

ER模型-表达方法之Chen方法#

实体: 矩形框
属性: 椭圆(用于刻画实体的)
- 多值属性: 双线椭圆
- 导出属性: 虚线椭圆
关键字/码: 下划线
连接实体和属性: 直线
联系: 菱形框
连接实体与联系: 直线
连接联系与属性: 直线
复合关键字: 标有相同数字
多组关键字: 标有不同数字
可采用的方法1
一对一的联系: 用联系指向两个实体
一对多的联系: 指向1端为箭头直线, 指向多端为直线
多对多的联系: 无箭头直线
完全参与联系: 双直线
部分参与联系: 单直线
可采用的方法2
1端实体-直线旁标1
多端实体-直线旁标m或n

联系也需要命名和表达, 联系也可能需要属性来刻画

运用ER模型理解需求并建模

理解需求, 寻找实体: 能用一个个、一件件等重叠量词形容的称为实体
用属性刻画每一个实体
确定每一个实体的关键字/码
数据建模的重点是分析实体之间的联系
检查ER图是否覆盖了需求(对需求的理解和表达, ER图的绘制要符合规范)

ER模型-表达方法之Crow’s foot方法#

实体: 矩形框, 实体的名称写在横线上面
属性: 实体框横线的下面
关键词: 属性下加下划线

联系用一个菱形框表示, 也可以将菱形框省略而直接以联系名替代
联系的基数表示方法
一种图形表示着一类业务规则

数据建模之案例讲解#

数据库设计中的抽象#

抽象与具体化: 考虑信息的取舍
- 数据库设计往往因为忽视了信息的细致分析而造成设计失误
- 数据库设计能力的高低往往体现在信息的正确分析上, 体现在理解现实世界能力的高低
现实世界->(抽象、概括为)信息世界->(抽象、概括为)计算机世界
将可无限扩展的内容或内容无法枚举的情况, 抽象为可有限描述的概念
越抽象, 语义信息越少, 概括性越高, 越反映共性信息, 表征的范围越大
检验抽象正确性的方法: 能抽象化, 也能还原为具体化
现实的抽象与描述需要遵循统一的数据模型(为了信息交流、信息共享)
- 统一的概念与统一的表达方法
数据模型是一组相互关联且已严格定义的概念集合, 是用于刻画或描述现实世界、信息世界或计算机世界的模型
数据模型: 表达计算机世界的模型; 概念模型: 表达信息世界的模型
建模的不同层次: 模型与元模型, 模型与实例

总结#

章节重难点

本讲内容

第12讲数据建模: 工程化方法及案例分析#

IDEF1x是将E-R模型扩充语义含义而形成的(是E-R图的细化), 是一种进行数据建模或数据库工程化的方法

IDEF1x两种实体的区分#

独立标识符实体/独立实体——强实体: 一个实体的实例都被唯一标识而不决定于它与其它实体的联系
从属标识符实体/从属实体——弱实体: 一个实体的实例的唯一标识需要依赖于该实体与其它实体的联系(ep. 一份合同中的一项项条目)
从属实体需要从其它实体继承属性作为关键字的一部分, 主关键字包含了外来属性的实体为从属实体
独立实体用直角方形框, 从属实体用圆角方形框
独立实体的主关键字没有外键, 从属实体的主关键字含有外键
关于属性的工程化要求
关于关键字的工程化要求
外来关键字: (FK) 是其它实体的关键字, 工程化要求

IDEF1x的标定联系与非标定联系#

联系: 实体之间的一种连接关系
标定联系: 子实体的实例都是由它与父实体的联系而确定。父实体的主关键字是子实体主关键字的一部分。
非标定联系: 子实体的实例能够被唯一标识而无需依赖与其实体的联系, 父实体的主关键字不是子实体的主关键字。
标定联系用实直线表示, 非标定联系用虚直线表示。在子实体一侧有圆圈, 联系名标注在直线旁
工程化要求

IDEF1x的非确定联系#

实体之间多对多的联系, 必须分解为若干个一对多的联系来表达
非确定联系通过引入相交实体(相关实体)来分解为若干个一对多的联系来表达
工程化要求

IDEF1x的分类联系#

一个一般实体实例及多个分类实体实例构成的联系
用于区分不同分类的属性, 称为鉴别器属性
具体化: (自顶向下)实体的实例集中, 某些实例子集具有区别于该实例集内其它实例的特性, 可以根据这些差异特性对该实例集进行分组/分类, 这一过程称为具体化
泛化: (自底向上)若干个实体集根据共有的性质, 可以合成较高层的实体。泛化是一个高层实体与若干个低层实体之间的包含关系
在E-R图中用标记为ISA的倒三角形表示。
高层实体的属性被低层实体自动继承, 低层实体特有的性质仅适用于某个特定的低层实例。

完全分类联系: 分类完全集, 使用一圆圈带两个横线来刻画。
非完全分类联系: 分类非完全集, 使用一圆圈带一个横线来刻画。
分类实体必须具有特有的属性, 否则分类没有意义

规则

IDEF1x建模之案例讲解#

作用/角色: 当一个实体与其父实体有多种联系时, 需使用”作用/角色”来区分每一种联系
仔细分析信息源, 源可能是由若干实体合并后形成的, 实体是从源中按实体规则提取出来的
仓储系统的数据模型

IDEF1x建模之案例作业点评#

通过IDEF1x图理解需求
读图
- 检查每个实体能否用重叠量词形容
- 检查实体的关键字能否唯一确定每个实例
- 检查实体之间联系绘制及命名的正确性
- 检查属性继承的正确性
不要把IDEF1x图当作流程图

总结#

章节重难点
本讲学习内容

第13讲数据库设计过程#

数据库设计过程与设计方法#

设计过程:
- 需求分析(收集需求和理解需求, “源”)
- 概念数据库设计(建立概念模型, “E-R图/IDEF1x图的绘制”)
- 逻辑数据库设计(建立逻辑模型, “关系模式”, 包含全局模式和用户模式)
- 物理数据库设计(建立物理模型, “Create Table”, 包含物理数据组织等, 依赖于具体的DBMS)

需求分析
- 目标: 理解企业、企业业务过程与数据处理流程、理解数据处理的性能需求, 形成”源”清单和”属性”清单以及相关的详细描述
- 对属性的命名要规范且含义明确, 尤其要注意多含义属性
- 了解不同岗位划分->收集源形成源表->理解每一个源->形成并提交需求分析报告
概念数据库设计
- 目标: 进一步深入理解企业, 对信息源进行抽象, 发现信息之间的内在本质联系
- 设计思路: 先局部后全局/先全局后局部 - 需求调研/合并局部需求/设计概念数据库模式/设计外部模式或视图
- 局部E-R模式设计: 确定范围->实体定义->联系定义->属性分配->全局E-R模式设计
- 全局E-R模式设计: 确定公共实体类型->合并两个局部E-R模式->检查并消除冲突->全局E-R模式优化
- 消除冲突: (属性) 属性域的冲突/属性取值单位的冲突 (结构) 同一对象在不同应用中的抽象不同/同一实体在不同E-R图中的属性组成不同/实体之间的联系在不同E-R图中呈现不同类型 (命名)同名异义/异名同义
- 全局E-R模式优化: 合并实体类型->消除冗余属性->消除冗余联系
- 依据需求分析报告->识别实体与联系->绘制E-R图/IDEF1x图用图表达业务规则->定义实体、联系及实体的属性构成->形成并提交概念数据库设计报告
逻辑数据库设计
- 目标: 用指定DBMS要求的模式描述方法, 给出概念数据库的逻辑模式描述
- 依据概念数据库设计报告->转换成关系模型->检查逻辑数据库设计的正确性->定义全局模式和外模式->形成并提交逻辑数据库设计报告
物理数据库设计
- 目标: 结合指定DBMS物理数据库管理方法, 给出概念数据库的物理模式描述
- 设计用户视图及访问控制规则, 以进行安全性控制->建立索引->设计使数据库运行达到最佳效率的措施->设计备份和恢复的步骤
- 依据逻辑数据库设计报告->利用具体DBMS创建数据库/表->确定物理存储方式与存储空间->创建索引、视图->形成并提交物理数据库设计报告

E-R图/IDEF1X向关系模式的转换#

转换的基本规则(E-R)

实体-属性-关键字的转换
复合属性的转换: 将每个分量属性作为复合属性所在实体的属性/将复合属性本身作为所在实体的属性二选一
多值属性的转换: 将多值属性与所在实体的关键字一起组成一个新的关系
联系的转换
- 一对一联系: (双方均部分参与)将联系定义为一个新的关系, 属性为参与双方的关键字属性; (一方全部参与)将联系另一方的关键字作为全部参与一方关系的属性
- 一对多联系: 将单方参与实体的关键字作为多方参与实体对应关系的属性
- 多对多联系: 将联系定义为新的关系, 属性为参与双方实体的关键字
弱实体的转换: 所对应关系的关键字由弱实体本身的区分属性再加上所依赖的强实体的关键字构成
泛化与具体化实体的转换: 高层实体和低层实体分别转为不同关系, 低层实体所对应的关系包括高层实体的关键字
- 如果泛化实体实例是具体化实体实例的全部, 则可以不为高层实体建立关系, 低层实体所对应的关系包括上层实体的所有属性
多元联系的转换
- 多元联系可以通过继承参与联系的各个实体的关键字而形成新的关系, 这些继承过来的关键字可以作为新关系的关键字, 也可以新增一个区分属性作为关键字

转换的基本规则(IDEF1x)

只需要关注实体转换成关系, 而联系无需关注(联系的信息以及融入相关实体的关系描述中)

不正确数据库设计引发的问题及其解决#

不正确设计数据库引发的问题
- 冗余: 数据库中存在大量冗余
  - 受控冗余: 实际上是联系的一个属性
  - 非受控冗余: 当数据发生改变时, 冗余数据同步更新困难
- 插入异常: 插入数据时因为信息不完整而无法录入
- 删除异常: 删除数据时关系到其它数据 ep. 某系所有同学被删除后该系的数据随之消失
如何避免问题
- 设计满足规范性, 由DBMS或数据库本身来保证
- 设计不满足规范性, 由使用者或应用程序员使用过程中加以注意
什么是规范的数据库设计
- 需要分析数据库中的属性在取值方面的依存关系
- 数据库设计理论: 数据依赖理论、关系范式理论、模式分解理论

总结#

章节重难点
本讲学习内容

第14讲函数依赖及其公理/定理#

函数依赖#

设R(U)是属性集合U={A1,A2,…,An}上的一个关系模式, X,Y是U上的两个子集。若对R(U)的任意一个可能的关系r, r中不可能有两个元组满足在X中的属性值相等而在Y中的属性值不等, 则称为”X函数决定Y”或”Y函数依赖于X”, 记作$X \to Y$

函数依赖的分析取决于对问题领域的限定和分析, 取决于对业务规则的正确理解
设计关系模式时, 除了给出属性全集之外, 还需给出数据依赖集合
函数依赖的特性
- 对$X \to Y$ , 但 $X \notin Y$ , 则称$X \to Y$ 为非平凡的函数依赖
- 若$X \to Y$ , 则任意两个元组, 若X上值相等, 则Y上值必然相等, 则称X为决定因素
- 若$X \to Y$ , $Y \to X$ , 则记作 $X \leftrightarrow Y$
- 若Y不函数依赖于X, 则记作$X \nrightarrow Y$
- $X \to Y$ , 有基于模式R的, 则要求对任意的关系r成立; 有基于具体关系r的, 则要求对某一关系r成立
- 如一关系r的某属性集X, r中根本没用X上相等的两个元组存在, 则$X \to Y$ 恒成立
重要的概念
- 候选键: 设K为R(U)中的属性或属性组合, 若K能够完全决定U, 则称K为R(U)上的候选键
  - 可任选一候选键作为R的主键
  - 包含在任一候选键中的属性称为主属性, 其它属性称为非主属性
  - 若K是R的一个候选键, $S \supset K$, 则称S为R的一个超键(没有最小性要求)
- 外来键: R(U)中的属性或属性组合X并非R的候选键, 但X是另一关系的候选键, 则X为R的外来键(外键)
- 逻辑蕴涵: 设F是关系模式R(U)中的一个函数依赖集合, 若满足F的每个关系均满足$X \to Y$ ,则说F逻辑蕴涵$X \to Y$
- 函数依赖闭包: 被F逻辑蕴涵的所有函数依赖集合称为F的闭包(Closure), 记作$F^+$ 。若$F^+=f$ , 则说F是一个全函数依赖族

完全函数依赖与传递函数依赖#

部分(p)或完全(f)函数依赖
传递函数依赖: $X \to Y, Y \to Z, Y \notin X, Z \notin Y, Z \notin X, Y \nrightarrow X$ , 则称Z传递函数依赖于X

关于函数依赖的公理和定理#

Armstrong公理
- 设R(U)是属性集U={A1,A2,…,An}上的一个关系模式, F为R(U)的一组函数依赖, 记为R(U,F)。则有以下规则成立
  - 自反律: 若Y包含于X包含于U, 则X决定Y被F逻辑蕴涵
  - 增广律: 若X决定Y且非包含于F, 且Z包含于U, 则XZ决定YZ被F逻辑蕴涵
  - 传递律: 若X决定Y且Y决定Z, 则X决定Z被F逻辑蕴涵
- 推论
  - 合并律: 若X决定Y且X决定Z, 则XZ决定YZ被F逻辑蕴涵
  - 伪传递律: 若X决定Y且WY决定Z, 则XW决定Z
  - 分解律: 若X决定Y且Z包含于Y, 则X决定Z
  - X决定Y可从F由公理导出, 当且仅当Y包含于属性闭包
  - F+ = G+ 等效于 F包含于G+ 且 G包含于F+
  - 每个函数依赖集F可被一个其右端至多有一个属性的函数依赖之集G覆盖
属性(集)闭包

函数依赖集的最小覆盖#

覆盖: 对R(U)上的两个函数依赖集合F、G, 若$F^+=g^+$ , 则称F和G是等价的, 也称F覆盖G或者G覆盖F
属性闭包的计算算法
最小覆盖: 满足以下条件
- F中的每个函数依赖的右部是单个属性
- 对任何X决定A属于F, 有F-{X决定A}不等价于F
- 对任何X决定A属于F, Z包含于X, (F-{X决定A})∪{Z决定A}不等价于F
每个函数依赖集F都有等价的最小覆盖$F^+$

总结#

章节重难点
本讲学习内容

第15讲关系模式设计之规范形式#

关系的第1NF和第2NF#

若关系模式R(U)中关系的每个分量都是不可分的数据项, 则称R(U)属于第一范式, 记为$R(U) \in 1NF$
即所有分量都不可再分(1NF要求属性中不能有复合属性和多值属性及其组合)
处理方法
- 将非1NF转换为1NF: 将复合属性处理为简单属性; 将多值属性与关键字单独组成新的关系
- 引入新的数据模型处理: Object-Oriented Data Model

若$R(U) \in 1NF$ 且U中的每一非主属性完全函数依赖于候选键, 则称R(U)属于第二范式, 记为$R(U) \in 2NF$ 。
第二范式消除了非主属性对候选键的部分依赖, 能够消除非受控的冗余。
处理方法
- 分解关系模式

关系的第3NF和Boyce-Codd NF#

若$R(U,F) \in 2NF$ 且R中不存在这样的情况: 候选键X, 属性组$Y \subseteq U$ 和非主属性A, $A \notin X, A \notin Y, Y \nsubseteq X, Y \nrightarrow X$ , 使得$X \rightarrow Y, Y \rightarrow A$ 成立。满足以上条件则称R(U)属于第三范式, 记为: $R(U) \in 3NF$
即第三范式是没有传递函数依赖的(可以简单理解为是否有冗余属性)。
A和B决定C, A和C决定D, 所以A和B能决定C从而决定D, 此为有传递依赖, 不属于3NF。
第三范式消除了非主属性对候选键的传递依赖。

若$R(U,F) \in 1NF$ , 若对于任何$X \rightarrow Y \in F$ (或$X \rightarrow A \in F$ ), 当$Y \notin X$ (或$A \notin X$ )时, X必含有候选键, 则称R(U)属于Boyce-Codd范式, 记为: $R(U) \in BCNF$ 。
如果一个关系模式上面的每一个函数依赖都依赖于X且X包含于候选键, 则其满足Boyce-Codd范式。
即Boyce-Codd范式是没有不依赖于候选键的函数依赖存在的。
关系模式分解成BCNF
- 将左侧不含候选键的函数依赖单独组成一个关系, 将包含候选键的组成一个关系

多值依赖及其公理定理#

多值依赖的定义
多值依赖的特性
- 直观地, 对于X给定值, Y有一组值与之对应(0或n个)且这组Y值不以任何方式与U-X-Y中属性值相联系, 有$X \rightarrow \rightarrow Y$ 。
- 若交换t, s的Y值而得到的新元组仍在r中, 则$X \rightarrow \rightarrow Y$ 。
- X,Y不必不相交, u,v可以与t,s相同
- 函数依赖是多值依赖的特例
- 令$Z=U-X-Y$, 有$X \rightarrow \rightarrow Z$, 若$Z=\phi$ ,则必有$X \rightarrow \rightarrow Y$ 。(互补性)

多值依赖的Armstrong公理(了解)
- 多值依赖互补律/对称性: 若$X \rightarrow \rightarrow Y$ , 则$X \rightarrow \rightarrow U-X-Y$
- 多值依赖增广律: 若$X \rightarrow \rightarrow Y$ 且$V \subset W$ , 则$WX \rightarrow \rightarrow VY$
- 多值依赖传递律: 若$X \rightarrow \rightarrow Y$ , $Y \rightarrow \rightarrow Z$ , 则$X \rightarrow \rightarrow Z-Y$
- 若$X \rightarrow Y$ , 则$X \rightarrow \rightarrow Y$
- 若$X \rightarrow \rightarrow Y$ , $Z \subseteq Y$ 且对于某个与Y不相交的W有$W \rightarrow Z, W \cap Y=\phi$ , 则有$X \rightarrow Z$
引理(了解)
- 多值依赖合并律: 若$X \rightarrow \rightarrow Y$ 且$X \rightarrow \rightarrow Z$ , 则$X \rightarrow \rightarrow YZ$
- 多值依赖伪传递律: 若$X \rightarrow \rightarrow Y$ 且$WY \rightarrow \rightarrow Z$ , 则$X \rightarrow \rightarrow Z-WY$
- 混合伪传递律: 若$X \rightarrow \rightarrow Y, XY \rightarrow Z, $ 则$X \rightarrow \rightarrow Z-Y$
- 多值依赖分解率: 若$X \rightarrow \rightarrow Y, X \rightarrow \rightarrow Z$ 则$X \rightarrow \rightarrow Y-Z, X \rightarrow \rightarrow Z-Y, X \rightarrow \rightarrow Y \cap Z$

关系的第4NF(了解)#

设$R(U) \in 1NF$ , D是其上的一组依赖(函数依赖或多值依赖), 对任意$X \rightarrow \rightarrow Y \in D$ , 若$Y \neq \phi, Y \nsubseteq X, XY \neq U$ , 必有X为超键, 则称R(U)满足第四范式, 记为: $R(U) \in 4NF$ 。
第四范式消除了非主属性对候选键以外属性的多值依赖。如果有多值依赖, 则一定依赖于候选键。
若R上仅存在函数依赖, 则若有R属于BCNF, 即有R属于4NF
若R属于4NF, 则有R属于BCNF

W4NF 弱第四范式(W4NF不一定是BCNF)

总结#

章节重难点
章节学习内容

第16讲模式分解存在什么问题(模式分解理论)#

模式分解存在什么问题#

模式分解的概念

模式分解需要关注
需要关注的内容
特性

拆分后再投影回去可能增加信息, 但投影后再连接起来同样等价
模式分解后可能有约束丢失

无损连接分解及其检验算法#

检验算法视频12:00
示例视频16:20
简单判断无损连接: 对两个关系时, R1∩R2决定R1-R2 或 R1∩R2决定R2-R1 时为无损连接
性质

无损连接的无损连接, 整体上依然是无损连接

保持依赖分解及其检验算法#

即分解后原有的依赖依然全部保持着(哪怕分散在各个新关系中)
保持依赖的分解可能不是无损连接的
无损连接的分解可能不是保持依赖的

关系模式无损连接或保持依赖的分解算法#

连接依赖与第5NF(了解)#

连接依赖(JD)

按照这样依赖的方式进行分解, 分解的结果始终保持无损连接性

5NF

当且仅当关系模式R的每个连接依赖均按其候选键进行连接运算时, 则称R是第五范式的
第五范式消除了不按候选键连接的连接依赖, 但是目前的语义背景抽象
第五范式也称投影连接范式, 即PJNF

数据库设计需要知道的#

保证数据库设计的正确性(应用数据库设计理论)
数据依赖理论: 用于判断是不是符合关系范式
关系范式理论: 有哪些关系范式
模式分解理论: 不满足关系范式时如何分解, 分解时会存在什么问题

哪些属性被组织成一个关系?
是一个大关系模式呢, 还是若干小关系模式?
大关系模式/小关系模式存在什么问题?
-> 关系模式设计需要折中: 时间与空间的效率平衡
-> 通常建议关系模式符合BCNF即可。

总结#

章节重难点
章节学习内容

第17讲数据库物理存储#

基础回顾-计算机系统的存储体系#

KB - MB - GB - TB - PB - EB - ZB - YB - BB
两个基本问题如何解决

如何高效率存储? -数据组织与索引
如何快速检索? -查询实现与查询优化

磁盘的结构与特性#

磁盘数据读写时间: 寻道(1-20ms); 旋转(0-10ms); 传输(每4KB页<1ms)
物理存取算法考虑的关键: 降低IO次数/降低排队等待时间/降低寻道or旋转延迟时间
RAID技术: 并行处理/可靠性
- raid0: 块级拆分但无冗余
- raid1: 镜像处理-每一个磁盘都有一个镜像磁盘
- raid2: 位交叉纠错处理
- raid3: 位交叉校验
- raid4: 块交叉校验
- raid5: 块交叉分布式校验
- raid6

DBMS数据存储与查询实现的基本思想#

数据库之表和记录与磁盘块的映射#

记录非跨块存储/跨块存储(指针连接)
表所占磁盘块的分配方法: 连续分配(扩展困难)/链接分配(访问速度问题)/按簇分配/索引分配

数据库之文件组织方法#

数据组织要考虑更新和检索需求
- 更新涉及数据存储空间的扩展与回收问题
- 检索将涉及扫描整个数据库的问题、大批量处理数据问题
- 不同的需求要求不同的数据组织方法和存取方法
- 一种文件组织可以采取多种存取方法进行访问

无序记录文件(堆文件)
- 更新效率高, 检索效率低
- 数据库重组: 移走被删除的记录使有效数据记录连续存放, 回收未利用的空间
有序记录文件(排序文件)
- 按某属性或属性组值的顺序插入, 磁盘上存储的记录是有序的, 检索效率高
- 用于排序的属性称为排序字段, 通常使用关系中的主码, 称为排序码
- 更新效率可能很低
- 改进措施: 为将来可能插入的元组预留空间或使用临时的无序文件(称为溢出文件)保留新增的记录
散列文件(Hash file)
- 依据散列函数计算桶号(bucket), 检索效率和更新效率都有所提高
- 用于进行散列函数计算的属性称为散列字段(hash field), 散列字段通常也采用关系中的主码: 散列码(hash key)
- 不同记录可能被hash到同一个bucket, 此时还需要在bucket中顺序检索出某记录
- 链接法: 以指针设置溢出桶以处理溢出
聚簇文件(clustering file)
- 将具有相同或相似属性值的记录存放于连续的磁盘簇块中

总结#

章节重难点
章节学习内容

第18讲数据库索引技术#

为什么需要索引与什么是索引#

索引是定义在存储表基础上, 有助于快速定位所需记录的辅助存储结构, 由一系列存储在磁盘上的索引项构成, 每一索引项又由两部分构成(索引字段, 行指针)
存储索引项的文件为索引文件, 相对应, 存储表又称为主文件
索引文件存在与否不改变存储表的物理存储结构, 但是其存在可以明显提高存储表的访问速度
索引文件的组织方式
- 排序索引文件
- 散列索引文件
索引的一般特点
- 在一个表上可以针对不同的属性或属性组合建立不同的索引文件
- 通过检索一个小的索引文件, 再有针对的读取非常大的主文件中的相关记录
- 有索引时, 更新操作必须同步更新索引文件和主文件
衡量索引性能的好坏
- 访问时间
- 插入时间
- 删除时间
- 空间负载
- 支持存取的有效性
基本知识
- 定义Table后, 若定义了主键, 系统会自动创建主索引
- 索引可以由用户创建, 也可以由用户撤销
- DBMS自动维护所有的索引, 使其与Table保持一致
- Table被删除后, 定义在Table上的所有索引将自动被撤销
创建索引的语句
对经常出现在索引条件、连接条件、分组计算条件中的属性可建立索引
建立索引还需要考虑索引的类型: 索引如何支持存取的有效性

索引的简单分类#

稠密索引: 对于主文件中的每一个记录, 都有一个索引项和它对应, 这样的索引称为稠密索引(dense index)
稀疏索引: 对于主文件中的部分记录, 有索引项和它对应, 称为非稠密索引或稀疏索引(sparse index)

稀疏索引如何定位记录
- 找相邻的小于K的最大索引字段值所对应的索引项
- 从该索引项所对应的记录开始顺序进行Table的检索
稀疏索引的使用要求主文件必须是按对应索引字段属性排序存储
相比于稠密索引: 空间占用更少, 维护任务更轻, 但速度更慢
平衡: 索引项不指向记录指针, 而是指向记录所在存储块的指针——主索引

主索引: 对每一存储块有一索引项与其对应, 又称为锚记录(anchor record)。主索引通常建立在有序主文件基于主码的排序字段上。主索引是稀疏索引。
辅助索引: 定义在主文件的任一或多个非排序字段上的辅助存储结构。辅助索引是稠密索引, 其检索效率有时相当高。
区别
- 一个主文件仅可以有一个主索引, 但是可以有多个辅助索引。
- 主索引通常建立于主码/排序码上面; 辅助索引建立于其它属性上面
- 可以利用主索引重新组织主文件数据, 但辅助索引不能改变主文件数据
- 主索引是稀疏索引, 辅助索引是稠密索引

聚簇索引: 索引中邻近的记录在主文件中也是临近存储的
非聚簇索引: 索引中邻近的记录在主文件中不一定是邻近存储的
如果主文件的某一排序字段不是主码, 则该字段上每个记录的取值不唯一, 此时该字段称为聚簇字段; 聚簇索引通常定义在聚簇字段上
一个主文件只能有一个聚簇索引文件, 但可以有多个非聚簇索引文件
主索引通常是聚簇索引, 辅助索引通常是非聚簇索引
主索引/聚簇索引是能够决定记录存储位置的索引; 非聚簇索引则只能用于查询

倒排索引: 以关键词为单位建立的广泛用于文本查询的索引
多级索引: 索引较多时, 可以对索引再建立索引, 以此类推
多属性索引: 索引字段由Table的多个属性值组合在一起形成的索引
散列索引: 使用散列技术组织的索引
网格索引: 使用多索引字段进行交叉联合定位与检索

B+树索引#

B+树索引是一种多级索引, 一种以树型数据结构来组织索引项的多级索引
一块中索引项的组织
- 一块中有n-1个索引项和1个指针
- Ki——索引字段值
- Pj——指针, 指向索引块或数据块或数据块中记录的指针
B+树的特性
- 能够自动保持与主文件大小相适应的树的层次
- 每个索引块的指针利用率都在50%-100%之间
非叶结点指针指向索引块, 叶结点指针指向主文件的数据块或数据记录
一个索引块实际使用的索引指针数d满足(根节点除外): n/2<=d<=n
根节点至少2个指针被使用

索引字段值重复出现于叶结点和非叶结点
指向主文件的指针仅出现于叶结点
所有叶结点即可覆盖所有键值的索引
索引字段值在叶结点中按顺序排列
仅叶结点块的集合就是主文件的完整的索引
保证结点的平衡性(级数相同)
- 插入/删除记录时, 伴随着结点的分裂与合并, 调整部分结点块中的索引项

算法
- 如何利用B+树进行检索
- 如何利用B+树进行增加和删除操作
- B+树的增加和删除操作时如何进行分裂和合并
- 什么条件下分裂与合并
- 分裂与合并时如何调整B+树的指针
方式
- 用B+树建立稠密索引
- 用B+树建立稀疏索引
- 用B+树建立非键属性稀疏索引(主文件按非键属性排序, 索引字段无重复)
- 用B+树建立非键属性稠密索引(索引字段是主文件的非键属性, 索引字段值有重复)

B Tree
- 不同
  - 索引字段值仅出现一次(出现在叶结点或非叶结点中)
  - 指向主文件的指针出现于叶结点或非叶结点
  - 所有结点才能覆盖所有键值的索引
- 相同
  - 插入记录时, 伴随着结点的分裂与合并
  - 层数相同, 平衡

插入过程
- 寻找保存键值记录的叶子结点
- 应插入结点已满, 则申请新结点
- 同时调整应插入但未插入结点中的键值记录, 使其均衡存放在两个叶结点中(分裂)
- 调整指针使其指向新的结点
- 寻找指向新叶子结点的非叶结点
- 应插入结点已满, 则申请新结点
- 同时调整应插入但未插入结点的键值记录, 使其均衡存放于两个非叶结点中(分裂)
- 调整各结点指针使其指向正确
- 注意事项
  - 每一个结点全满的时候进行分裂
  - 由叶结点向根结点逐层处理
- 指针调整
删除与合并过程
- 叶子结点中寻找等于键值的记录, 删除相应的指针及主文件中对应的记录
- 调整其左侧(或右侧)结点及本结点中的键值记录, 使其均衡存放于两个叶结点中
- 如有调整, 则进一步调整其上层非叶结点, 重新确定其键值, 以满足大于等于其键值的都在右侧
- 注意事项
  - 合并(当指针数目少于规定数目时)
  - 由叶结点向根结点逐层处理
  - 指针调整
要点概括
- 插入记录时
  - 可能需要分裂: 当索引块充满时, 需要分裂
  - 分裂可能引发连锁反应, 由叶结点直至根结点
  - 分裂后需要仔细调整索引键值及指针
  - 注意叶子结点之间链接关系的调整
- 删除记录时
  - 可能需要合并: 从相邻结点中转移索引项
  - 可能需要合并: 两个结点块合并成一个结点块
  - 合并可能引发连锁反应, 由叶结点至根结点
  - 合并后需要仔细调整索引值及指针
  - 注意叶子结点之间链接关系的调整

散列索引#

有M个桶, 每个桶是有相同容量的存储地
散列函数将键值k进行映射
将具有键值k的记录Record(k)存储在对应h(k)编号的桶中
目标: 选择一个合适的散列函数, 将一个Record集合均匀地映射到M个桶中
散列索引
- 内存数据可采用散列确定存储页, 主文件可采用散列确定存储块, 索引亦可采用散列确定索引项的存储块
- 一个桶可以是一个存储块, 也可以是若干个连续存储块
- 目标: 最好没有溢出桶, 每一个散列值仅有一个桶, 读写每一个键值都只读写一个存储块
期望将所有数据分布均匀地存储于M个桶中, 使每个桶的数据成为具有某种特征值h(k)的数据集合
桶的数目的确定: 在键值几倍于桶的数目时, 每一个散列值都可能多于一个桶, 形成一个主桶和多个溢出桶的列表, 需要二次检索
散列
- 桶的数目M是固定值——静态散列索引
  - M过大则浪费; M过小则产生更多溢出桶, 增加检索时间
- 桶的数目随键值增多而动态增加——动态散列索引
  - M的变化是否影响原有内容; 是否需要重新进行散列存储
可扩展散列索引
- 取前i位确定索引块
- 如未满, 则存入; 如已满, 则需要扩展散列桶, 进行分裂
- 不增加; i增加1
- 重新散列该块的数据到两个块中, 其它不变
- 存在的问题
  - 当桶数组需要翻倍时, 要做大量的工作
  - 桶数翻倍时, 可能装不下或要占用更大的空间
  - 如果每块的记录数很少, 那么可能某一块的分裂比在逻辑上需要的分裂时间提前很多
线性散列索引
- 使得桶数n的选择总是使存储块的平均记录数保持与存储块所能容纳的记录总数成固定的比例, 超过比例则桶数增长1块, 分裂
- 存储块并不总是可以分裂, 允许有溢出块
- 用来做桶数组项序号的二进制位数是[log2n], 其中n为当前的桶数。

总结#

章节重难点
章节回顾

第19讲数据库查询实现算法-I(一趟扫描算法)#

数据库查询实现算法概述#

物理查询优化
- 获取数据库的相关信息(定期统计)
- 选择相应操作的例行程序
- 依据相关信息进行代价估算, 选择代价最少的例行程序及确定相应的参数
- 形成查询计划: 以基本的例行程序为基本步, 确定这些例行程序的执行顺序
数据库的三大类操作
- 一次单一元组的一元操作(选择, 投影)
- 整个关系的一元操作(去重, 分组, 排序) -> 一趟扫描算法、两趟扫描算法、多趟扫描算法 -> 基于排序的算法、基于散列的算法、基于索引的算法
- 整个关系的二元操作(并, 交, 叉, 乘积, 连接等)

以连接操作为例看逻辑实现算法与物理实现算法#

物理算法需要考虑
- 关系是存储在磁盘上的, 磁盘是以磁盘块为操作单位, 首先要被装载进内存, 再进行元组的处理
算法
- 表空间扫描法
  - 基本实现算法: 适用于任何情况, 3块内存即可, 但复杂性高: BR+BR*BS
  - 全主存实现算法: 要求内存能够完全装载两个关系, 算法复杂性低: BR+BS
  - 半主存实现算法: 要求内存能够完全装载一个关系, 算法复杂性低: BR+BS
  - 大关系实现算法: 适用于任何情况, 尤其是大关系情况下比基本实现算法好, 算法复杂性低: BR(BS/(M-2))+BS
- 归并排序连接算法
- 散列连接算法
- 索引连接算法

利用迭代器构造查询实现算法#

迭代器指迭代的读取一个集合中的每一个元素, 而封装其读取细节

几个关系操作的一趟扫描算法#

关系/表数据的读取
- 聚簇关系——关系的元组集中存放(一个块中仅是一个关系中的元组)
  - TableScan(R)——表空间扫描算法: 扫描结果未排序 B(R)
  - SortTableScan(R): 扫描结果排序 3B(R)
  - IndexScan(R)——索引扫描算法: 扫描结果未排序 B(R)
  - SortIndexScan(R): 扫描结果排序 B(R) or 3B(R)
- 非聚簇关系——关系的元组不一定集中存放
  - 扫描结果未排序: T(R)
  - 扫描结果排序: T(R) + 2B(R)
去重复: &(R)
- 需要在内存中保存已处理过的元组
- 当新元组到达时, 与之前处理过的元组进行比较
- 建立不同的内存数据结构, 来保存之前处理过的数据, 以便快速处理整个关系上的操作
- 算法复杂性: B(R)
- 应用条件: B(&(R))<=M
分组聚集: yL(R)
- 需要在内存中保存所有的分组
- 保存每个分组上的聚集信息
- 建立不同的内存数据结构, 来保存之前处理过的数据, 以便快速处理整个关系上的操作
- 算法复杂性: B(R)
- 应用条件: 所有分组的数量应能在内存中完整保存
集合/包上的操作: 并交叉
- 集合的操作需要去重, 包的操作需要计数
- 算法复杂性: B(R)+B(S)
- 应用条件: min(B(R),B(S))<=M

基于索引的查询实现算法#

基于索引的选择算法
- 选择条件中有涉及到索引属性时, 可以使用索引辅助快速检索
- 在某些属性上存在着索引, 可能在多个属性上都存在着索引
- 索引应用分析
基于有序索引的连接算法 - Zig-Zag连接算法

总结#

章节重难点
章节总结

第20讲数据库查询实现算法-II(两趟扫描算法)#

为什么需要两趟扫描算法&两趟算法的基本思想#

理论上一个元组需要与所有元组进行比较, 才能确定是否重复, 而这些需要内存
基本思路
- 第一趟: 划分子集, 并使子集具有某种特性, 如有序或相同散列值等
- 第二趟: 处理全局性内容单独操作, 形成结果关系。比如多子集间的归并排序, 相同散列值子集的操作等

两阶段多路归并排序(TPMMS)算法#

内排序问题: 待排序的数据可一次性装入内存中, 排序者可以随意选择算法进行排序(插入/选择/冒泡)
外排序问题: 排序者需要将数据分批装入内存分批处理
外排序问题基本排序策略
- 将数据划分为N个子集合, 使得每个子集合的块数小于内存可用块数(BP/N), 每个子集合都可装入内存并采用内排序算法排好后重新写回磁盘。
- 问题转化为 N个已排序的子集合数据怎样应用内存进行总排序? -TPMMS
- 第一趟: 划分子集并子集排序 - 内存所有块用于处理一个子集合
- 第二趟: 各子集间的归并排序
- 算法效率: IO数4BP, 子集合排序阶段读写2BP, 归并阶段读写2BP ——3B(R) 不考虑结果写回;4B(R) 考虑结果写回
- 算法应用条件: 子集合数<\BM; 子集合块数<\BM; 大数据集块数<\BM^2

基于排序的两趟扫描算法#

去重复操作
- 第一趟: 划分子表, 进行子表排序
- 第二趟: 归并阶段, 在排序的基础上直接剔除重复的记录
- 算法复杂性同TPMMS 3B(R) 不考虑输出; 4B(R) 考虑输出
分组聚集操作
- 第一趟: 划分子表, 进行子表排序
- 第二趟: 归并阶段, 在排序基础上, 将不重复的记录作为新分组输出, 将重复记录进行分组聚集计算
- 算法复杂性同TPMMS 3B(R) 不考虑输出; 4B(R) 考虑输出
并、交、叉操作
- 包并: 直接两个关系合并即可
- 集合并: 需要两趟, 去重复
- 交: 需要两趟, 需要处理出现次数或去重复(集合交: t在R和S中都出现就输出; 包交: 输出t的次数是min(tR,tS) )
- 叉: 需要两趟, 需要处理出现次数或去重复(集合差: 当且仅当t出现在R中但不出现在S中输出; 包差: 输出t的次数是tR-tS )
连接运算
- 第一趟: 划分R和S的子表并进行子表排序, 排序均基于Y属性排序
- 第二趟: 归并时注意是R的输入还是S的输入, R和S的两路输入之间进行连接检查并连接后输出
- 也称”排序-连接 SORT-JOIN”算法、”归并-连接 MERGE-JOIN”算法、”排序-归并-连接 SORT-MERGE-JOIN”算法

基于散列的两趟扫描算法#

基本思想
- 将大数据集上的操作转换为某个子集上的操作
- 第一趟: 散列子表, 用散列函数将原始关系划分为M-1个子表, 并存储
- 第二趟: 处理每个子表, 用另一散列函数将子表读入内存并建立内存结构, 进行不同操作的处理
去重复操作
- 第一趟: 将原始关系通过hp散列成M-1个子表, 并存储
- 第二趟: 处理每个子表。将每个子表读入内存, 并用另一函数hr形成散列数据结构, 进行去重复操作
- 算法复杂性同TPMMS 3B(R) 不考虑输出; 4B(R) 考虑输出
- 元组在子表上不重复, 则在大关系中亦不重复(MOD M)
分组聚集操作
- 第一趟: 将原始关系通过hp散列成M-1个子表, 并存储
- 第二趟: 处理每个子表。将每个子表读入内存, 并用另一函数hr形成散列数据结构, 进行分组聚集操作
- 算法复杂性同TPMMS 3B(R) 不考虑输出; 4B(R) 考虑输出
- hp = 计算分组属性的值 MOD M
- hr = 以分组属性的二进制位串重新计算值 MOD M
并、交、叉操作
- 使用相同的散列函数散列两个操作对象R和S
- 包并: 无需两趟, 直接合并
- 集合并: 需两趟, 需要去重复
- 交、叉: 类似方法处理
连接操作
- 以连接属性Y作为散列关键字, 设计散列函数
- 第一趟: 使用相同的散列函数散列两个操作对象R和S
- 第二趟: 将Si整体散列读入到内存中, 再依次处理Ri的每一块。进行连接。
- 称为”散列连接”算法

总结#

章节重难点

第21讲数据库查询优化技术#

为什么要以及什么是查询优化#

语义优化: 利用模型的语义及完整性规则, 优化查询
语法优化(逻辑层优化): 利用语法结构, 优化操作执行顺序
执行优化(物理层优化): 存取路径和执行算法的选择与执行次序优化

查询优化的基本思路#

语义优化——内容等价性
- 优化: 去掉无关的表、去掉无关的属性、改写成等价的效果更好的语句..
语义优化(逻辑层优化)——语法等价性
- 逻辑优化/语法优化: 尽可能早做选择运算、尽可能早做投影运算、改写成等价的效果更好的语句
- 基本思想: 改变关系代数的操作次序; 尽可能早做选择和投影运算
- 【关系代数表达式的等价变化定理及其证明】
执行优化(物理层优化)
- 物理优化/执行优化: 为每一个关系代数操作选取优化的执行层例行程序, 基于不同算法的实现程序构造
- 获取数据库的相关信息(定期统计)
- 为每一个关系代数操作选择相应的执行层例行程序
- 依据相关信息进行代价估算, 选择代价最少的例行程序及确定相应的参数
- 形成查询计划: 以基本的例行程序为基本, 确定这些例行程序的执行顺序

逻辑查询优化(关系代数操作优化)#

通过语法树表达关系代数表达式
逻辑层优化策略
- 尽可能地早做选择和投影: 可使中间结果变小, 节省几个数量级的执行时间
- 把选择与投影串接起来: 一元运算序列可一起执行, 只需对整个关系扫描一遍
- 把投影与其前或后的二元运算结合起来: 在第一次用关系时可以去掉一些无关属性
- 把某些选择与其前的笛卡尔积合并成一个连接
- 执行连接运算前对关系做适当预处理
- 找出表达式里的公共子表达式: 可以预先计算, 节省时间
关系代数操作次序交换的等价性
- 两两交换, 若交换前后等价即说明可交换 —— 关系代数交换定理
- 定理L1: 连接与连接、积与积的交换律
- 定理L2: 连接与连接、积和积的结合律(先后连接等价)
- 定理L3: 投影串接律(对E做大的投影再做小的投影等价于直接做小的投影)
  - 两遍扫描变为一遍扫描; 属性扩展便于投影操作的移动
- 定理L4: 选择串接律(对E做关于F2的选择再做关于F1的选择等价于对E做F1与F2的选择操作)
  - 两遍扫描变为一遍扫描; 分解复杂操作便于选择操作的移动
- 定理L5: 选择和投影交换律: 设条件F只涉及属性{A1,…,An}, E是关系表达式, 则先选择再投影等价于先投影再选择
- 定理L6: 选择和积的交换律
  - 若条件F只涉及E1中的属性, 则 E1×E2的选择等于对E1选择×E2
  - 若F = F1并F2, F1,F2分别只涉及E1,E2中的属性, 则有 E1×E2的选择等于对E1选择×对E2选择
  - 若F = F1并F2, F1只涉及E1中属, F2涉及E1,E2中属性, 则有 E1×E2的选择等于对(对E1选择×E2)选择
- 定理L7: 投影和积的交换律
- 定理L8: 选择和并的交换律 - 降低中间结果
- 定理L9: 选择和差的交换律 - 降低中间结果
- 定理L10: 投影和并的交换律
算法表达优化

物理查询优化(物理实现算法选择与次序优化)#

总体思路
- 获取数据库的相关信息(定期统计)
- 选取相应的执行层例行程序
- 依据相关信息进行代价估算, 并选择代价最少的例行程序及确定相应的参数
- 形成查询计划: 以基本的例行程序为基本, 确定这些例行程序的执行顺序
如何衡量物理查询计划的好坏
- I/O访问次数
- CPU的占用时间
- 内存使用代价(与缓冲区数目与大小的匹配)
- 中间结果存储代价
- 计算量
- 网络通信量
代价估算

总结#

章节重难点
本讲学习内容

第22讲数据库事务处理技术之并发控制#

为什么需要并发控制#

数据库可能存在不一致
- 丢失修改
- 不能重复读(重复读错误)
- 脏读
并发控制方法
- 基于封锁法
- 基于撤回方法
并发控制及相应的事务处理技术是数据库管理系统的核心技术
事务
- 是数据库管理系统提供的控制数据操作的一种手段, 以此保障数据库的正确性、一致性
- 事务的宏观性: 一个存取或改变数据库内容的程序的一次执行被看作一个事务
- 循环多少次, 则将产生多少个事务
- 事务的微观性: 对数据库的一系列基本操作的一个整体性执行
- 宏观独立完整、微观交错执行
并发控制就是通过事务微观交错执行次序的正确安排, 保证事务宏观的独立性、完整性、准确性
事务的特性: ACID(原子性/一致性/隔离性/持久性), 具有ACID特性的若干数据库基本操作的组合体称为事务
事务管理器
- 产生事务
- 管理事务的时间戳
- 管理事务的一系列操作
事务调度器
- 对所有事务的操作产生一个读写操作序列
- 保证事务的一致性
- 锁表

事务调度及可串行性#

事务调度
- 一组事务的基本步的一种执行顺序称为对这组事务的一个调度
- 并发调度的正确性: 当且仅当在这个并发调度下所得到的新数据库结果与分别串行运行这些事务所得的数据库完全一致, 则说调度是正确的
- 可串行性: 不管数据库初始状态如何, 一个调度对数据库状态的影响都和某个串行调度相同, 则说这个调度是可串行化的
- 并行调度的正确性指的是内容上结果的正确性、可串行性指的是形式上结果正确性
- 可串行化调度一定是正确的并行调度, 但正确的并行调度未必是可串行化调度
- 可串行化调度的等效串行序列不一定唯一
冲突: 调度中一对连续的动作, 它们满足: 如果它们的顺序交换, 那么涉及的事务中至少有一个事务的行为会改变
- 有冲突的两个操作是不能交换次序的, 没有冲突的两个事务是可交换的
- 冲突的情况
  - 同一事务的任何两个操作都是冲突的
  - 不同事务对同一元素的两个写操作是冲突的
  - 不同事务对同一元素的一读一写操作是冲突的
- 冲突可串行性: 一个调度, 如果通过交换相邻两个无冲突的操作能够转换到某一个串行的调度, 则称此调度为冲突可串行化的调度

基于封锁的并发控制方法#

“锁”是控制并发的一种手段
- 每一数据元素都有一唯一的锁
- 每一事务读写数据元素前, 要获得锁
- 如果被其它事务持有该元素的锁, 则要等待
- 事务处理完成后要释放锁
锁本身并不能保证冲突可串行性, 只是为调度提供了控制的手段, 但如何用锁仍需说明
锁的类型 -> 提高并发度, 保证正确性
- 排他锁X/写锁(只有一个事务能读、写, 其它任何事务都不能读、写)
- 共享锁S/读锁(所有事务都可以读, 但任何事务都不能写)
- 更新锁U(初始读, 以后可升级为写)
- 增量锁I(区分增量更新和其它类型的更新)
相容性矩阵: 当某事务对一数据对象持有一种锁时, 另一事务再申请对该对象加某一类型的锁, 是否允许
加锁/解锁的时机
SQL之隔离性级别
- 读未提交——相当于0级协议
- 读已提交——相当于1级协议
- 可重复读——相当于2级协议
- 可串行化——相当于3级协议
- 幻读指的是事务不是串行发生时的一种现象, 事务A读取了事务B已提交的新增数据
  - 解决幻读的方法是增加范围锁或表锁
封锁粒度: 封锁数据对象的大小
- 单位: 属性值->元组->元组集合->整个关系->整个DB某索引项->整个索引
- 由前往后, 并发度小到大, 封锁开销小到大
两段封锁协议是一种基于锁的并发控制方法
- 读写数据之前要先获得锁, 每个事务中所有封锁请求先于任何一个解锁请求
- 分为加锁段和解锁段, 加锁段不能解锁, 解锁段不能加锁
- 两段封锁协议可以保证冲突可串行性, 但是可能产生死锁

基于时间戳的并发控制方法#

时间戳: 一种基于时间的标志, 将某一时刻转换成的一个数值, 具有唯一性和递增性
事务的时间戳
- 事务T启动时, 事务将该时刻赋予T
- 时间戳可以表征一系列事务执行的先后次序, 时间戳小的先执行
- 借助时间戳, 强制使一组并发事务的交叉执行, 等价于一个特定顺序的串行执行
- 强制: 执行时判断冲突
  - 无冲突, 予以执行
  - 有冲突, 撤销事务并重启事务, 重启后该事务获得一个更大的时间戳, 表明是后执行的事务
- 冲突
  - 读-读无冲突
  - 读-写或写-读冲突
  - 写-写冲突
一种简单的调度规则
- 对DB上的每个数据元素X, 系统保留其上的最大时间戳
  - RT(x) 读最大时间戳; WT(x) 写最大时间戳
  - 先执行的先操作, 后执行的后操作
- 放行一些事实上可实现的冲突——托马斯写规则
  - 过时的写操作可直接被忽略, 而无需撤销过时的事务
另一种调度规则
- 增加C(x): x的提交位
- 该位为真当且仅当最近写x的事务已经提交
- 目的是避免出现事务读另一事务U所写数据然后U终止的情况

基于有效性确认的并发控制方法#

事务在启动时刻被赋予唯一的时间戳, 以示其启动顺序
为每一活跃事务保存其读写数据的集合, 通过对多个事务的读写集合判断是否有冲突, 来完成事务提交与回滚
分为三个阶段: 读阶段/有效性确认阶段/写阶段
每个成功确认的事务是在有效性确认的瞬间执行的
调度器维护三个集合
- START 已经开始但尚未完成有效性确认的事务集合, 维护START(T)即事务T开始的时间
- VAL 已经确认有效性但尚未完成写的事务, 维护START(T)和VAL(T)即事务T确认的时间
- FIN 已经完成第三阶段的事务, 记录START(T), VAL(T)和FIN(T)即事务T完成的时间
有效性确认规则

总结#

章节重难点
章节回顾

第23讲数据库事务处理技术之故障恢复#

数据库的故障#

故障恢复涉及到如何保证事务的原子性和持久性
数据库的故障及其影响
- 事务故障: 某一个程序(事务)自身运行错误所引起的故障, 只影响该程序本身
- 系统故障: 由于掉电、非正常关机等所引起的故障, 影响正在运行的事务及数据库缓冲区(可能涉及已经运行的事务)
- 介质故障: 由于介质损坏等引起的故障, 影响是全面的, 既影响内存中的数据, 又影响介质中存储的数据

数据库故障恢复的宏观思路#

数据库故障恢复: 把DB由当前不正确状态恢复到已知为正确的某一状态
- 事务故障的恢复: 可通过重做事务和撤销事务来恢复, 前者保证已提交事务的持久性, 后者消除未提交事务对系统的影响
- 系统故障的恢复: 通过运行日志(DBMS维护的记录操作的文件)来恢复, 按照运行日志记录的事务操作顺序重做事务
  - DBMS在运行日志中定期设置和更新检查点, 在该时刻DBMS强制使内存DB Buffer中的内容与介质DB中的内容保持一致, 即将DB Buffer更新的所有内容写回DB中, 说明在检查点之前内存中数据与介质中数据保持一致
  - 检查点之前结束的事务不需要恢复, 检查点之后结束或发生的事务需要依据运行日志进行恢复
- 介质故障的恢复: 通过副本(在某一时刻对数据库在其它介质存储上产生的另一份等同记录)替换被损坏的数据库
  - 由于介质故障影响全面, 在用副本恢复后还需要依据运行日志进行恢复
  - 问题: 如何确定备份的时刻-转储点: 过频影响系统工作效率, 过疏造成运行日志过大, 影响系统运行性能
  - 备份转储周期与运行日志的大小密切相关, 应注意防止衔接不畅而引起的漏洞

运行日志及其检查点#

事务涉及到的
缓冲区处理策略
- Force: 内存中的数据最晚在commit的时候写入磁盘
- No steal: 不允许事务commit之前把内存中的数据写入磁盘
- No force: 内存中的数据可以一直保留, 在commit之后过一段时间再写入磁盘(在系统崩溃时可能还没写入磁盘, 需要redo)
- Steal: 允许在事务commit之前把内存中的数据写入磁盘(若系统崩溃, 要恢复到崩溃前的状态需要undo)
- 当前最常用的 Steal + No force
日志
- 一个包含日志记录的只能追加的顺序文件, 按发生时间存储
- 发生系统故障时, 使用日志进行恢复
- 三种日志: Undo型日志、Redo型日志、Undo/Redo型日志
缓冲区处理策略与日志/恢复策略的关系

三种类型的运行日志&运用运行日志进行故障恢复#

Undo型日志及其故障恢复
- 利用undo型日志进行恢复
- 检查点
  - 静止检查点: 周期性地对日志设置检查点
    - 停止接受新的事务, 等到所有当前活跃事务提交或终止后
    - 将日志刷新到磁盘, 写入日志记录<CKPT>, 再次刷新日志
  - 非静止检查点: 在设置检查点时不必关闭系统, 允许新事务进入
    - 写入<START CKPT(T1,…,TK)> 为所有活跃的未结束的事务
    - 继续正常操作, 直到这些事务都完成, 写入<END CKPT>
  - 故障需恢复到所遇到的第一个检查点
Redo型日志及其故障恢复
- 利用redo型日志进行恢复
- 检查点
  - 非静止检查点: 在设置检查点时不必关闭系统, 允许新事务进入
    - 写入<START CKPT(T1,…,TK)> 为所有活跃的未结束的事务
    - 继续正常操作, 直到这些事务都完成, 写入<END CKPT>
  - 故障需恢复要寻找到最后的<END CKPT>, 从其内容的最早开始处恢复起, 忽略更早提交的事务
Undo/Redo结合型日志及其故障恢复
- 利用undo/redo型日志进行恢复
- 既需要做撤销的工作, 又需要做重做的工作

总结#

章节重难点
本讲学习内容

学习笔记

#数据库系统

数据库系统学习笔记

第1讲 数据库的基本知识与关系模型#

什么是数据库#

什么是数据库系统#

第2讲 数据库系统的结构抽象与演变#

数据与模式#

三级模式#

两层映像#

两个独立性(三级模式、两层映像所实现)#

数据模型#

三大经典数据模型#

发展史 30:00#

数据库技术的简要发展史#

演变与发展#

总结#

第3讲 关系模型之基本概念#

关系模型的概述#

什么是关系#

关系模型中的完整性约束#

总结#

第4讲 关系模型之关系代数#

关系代数之基本操作#

关系代数之扩展操作#

关系代数之组合与应用训练#

关系代数之复杂扩展操作#

总结#

第5讲 关系模型之关系演算#

关系演算之关系元组演算#

关系演算之关系域演算#

关系演算之安全性#

关于三种关系运算的观点#

总结#

第6讲 SQL语言之概述#

SQL语言概述#

SQL语言之DDL-定义数据库#

SQL语言之DML-操纵数据库#

典型DBMS交互环境 SQL Server介绍#

总结#

第7讲 SQL语言之复杂查询与视图#

子查询运用#

结果计算与聚集函数#

分组查询与分组过滤#

利用SQL语言实现关系代数操作#

视图及其应用#

总结#

第8讲 SQL语言与数据库完整性和安全性#

数据库完整性的概念及分类#

SQL语言之列约束与表约束——静态约束#

SQL语言之触发器——动态约束#

阶段性总结#

数据库安全性的概念及分类#

SQL语言之安全性实现#

阶段性总结#

总结#

第9讲 嵌入式SQL语言之基本技巧#

嵌入式SQL语言概述#

变量声明与数据库连接#

数据集与游标#

可滚动游标与数据库的增删改#

数据的删除与更新#

状态捕获及错误处理机制#

总结#

第10讲 嵌入式SQL语言之动态SQL#

动态SQL的概念和作用#

SQL语句的动态构造#

动态SQL语句的执行方式#

数据字典与SQLDA#

ODBC/JDBC简介#

总结#

第11讲 数据建模: 思想与方法(数据库设计的抽象与表达方法)#

为什么要数据建模和数据库设计#

ER模型-数据建模之基本思想#

ER模型-表达方法之Chen方法#

ER模型-表达方法之Crow’s foot方法#

数据建模之案例讲解#

数据库设计中的抽象#

总结#

第12讲 数据建模: 工程化方法及案例分析#

IDEF1x两种实体的区分#

IDEF1x的标定联系与非标定联系#

第1讲数据库的基本知识与关系模型#

第2讲数据库系统的结构抽象与演变#

第3讲关系模型之基本概念#

第4讲关系模型之关系代数#

第5讲关系模型之关系演算#

第9讲嵌入式SQL语言之基本技巧#

第10讲嵌入式SQL语言之动态SQL#

第11讲数据建模: 思想与方法(数据库设计的抽象与表达方法)#

第12讲数据建模: 工程化方法及案例分析#

第13讲数据库设计过程#

第14讲函数依赖及其公理/定理#

第15讲关系模式设计之规范形式#

第16讲模式分解存在什么问题(模式分解理论)#

第17讲数据库物理存储#

第18讲数据库索引技术#

第19讲数据库查询实现算法-I(一趟扫描算法)#

第20讲数据库查询实现算法-II(两趟扫描算法)#

第21讲数据库查询优化技术#

第22讲数据库事务处理技术之并发控制#

第23讲数据库事务处理技术之故障恢复#