DBS知识整理(冶旭).doc

数据库系统概念知识点整理

冶旭 华东师范大学 10计算机科学技术系

Chapter 1 引言
数据库管理系统（DBMS）：由一个互相关联的数据的集合和一组用以访问这些数据的程序组成，数据描述某特定的企业。
DBMS的主要目标是为人们提供方便高效的环境来存储和检索数据。
数据不一致性：即同一数据的不同副本不一致。
模式分为数据库模式，物理模式和逻辑模式。
物理数据独立性：应用程序如果不依赖于物理模式，它们就被称为是具有物理数据独立性，因此即使物理模式改变了它们也无须重写。
数据模型：是数据库结构的基础，是一个用于描述数据、数据联系、数据语义和数据约束的概念工具的集合。
数据操纵语言（DML）：是使得用户可以访问和操纵数据的语言。分为过程化和非过程DML（即声明式DML）。
过程化DML：要求用户指定需要什么数据以及如何获得这些数据。
非过程化DML：只要求用户指定需要什么数据，而不指明如何获得这些数据。
事务：是数据库应用中完成单一逻辑功能的操作集合，是一个既具有原子性又具有一致性的单元。
事务管理：负责保证不管是否有故障发生，数据库都要处于一致的（正确的）状态。事务管理器还保证并发事务的执行互不冲突。
数据库管理员（DBA）:对系统进行集中控制的人。

Chapter 2 关系模型
关系数据模型(relational data model): 建立在表的集合的基础上。数据库系统的用户可以对这些表进行查询，可以插入新元组、删除元组以及更新(修改)元组。
关系代数：定义了一套在表上运算，且输出结果也是表的代数运算。这些运算可以混合使用以得到表达所希望查询的表达式。关系代数定义了关系查询语言中使用的基本运算。
关系代数运算可分为：基本运算（选择，投影，并，集合差，笛卡尔积，更名）；附加运算（集合交，自然连接，除，赋值），扩展的运算（广义投影，聚集函数，外连接）。
码：是整个关系的性质，而不是一个个元组的性质。关系中的任意两个元组都不允许同时在码属性上具有相同的值。
超码：是一个或多个属性的集合，这些属性的组合可以使我们在一个关系中唯一地标识一个元组。
候选码：它的任意真子集都不能成为超码，即最小超码称为候选码。
主码：用来代表被数据库设计者选中的、用来在同一关系中区分不同元组的候选码。
外码：一个关系模式（如r1）可能在它的属性中包括另一个关系模式（如r2）的主码。这个属性叫做r1的参照r2的外码。关系r1也称为外码依赖的参照关系，r2叫做外码的被参照关系。
模式图：一个含有主码和外码依赖的数据库模式可以用模式图来表示。关系用一个矩形来表示，矩形内列出属性，矩形上面是关系的名字。如果有主码属性，用一条横线将主码属性分隔在方框上不。外码依赖用从参照关系的外码属性到被参照关系的主码属性之间的一个箭头来表示。
外连接运算：是连接运算的扩展，可以处理缺失的信息。

Chapter 3~5 略

Chapter 6 数据库设计和E-R模型
1. 实体是实际存在的并且可以区别于其他对象的对象，我们通过把每个实体同描述该实体的一组属性相关联来将它与其他对象区分开。
2. 联系是多个实体间的相互关联。相同类型的所有实体的集合构成实体集，相同类型的所有联系的集合构成联系集。
3. 实体在联系中的作用称为实体的角色。
4. 参与联系集的实体集的数目也称为联系集的度。
5. 属性是实体集中每个成员所拥有的描述性性质。
6. 每个属性都有一个可取值的集合，称为该属性的域。
7. 简单属性就是不能在划分为更小部分的属性。
复合属性就是可以再划分为更小的部分的属性，是有层次的。
单值属性就是对一个特定实体只有一个单独的值的属性。
多值属性就是对一个特定实体对应一组值的属性。
派生属性就是这类属性的值可以从别的相关属性或实体派生出来。
8. 空值——当实体存在某个属性上没有值时使用null值。Null值可以表示“不可用”，即该实体的这个属性不存在值。
9. 超码是一个或多个属性的集合，这些属性的组合可以使我们在一个实体集中唯一标识一个实体。我们为每个实体集在其所有的超码中选择一个最小的超码，将它称作实体集的主码。
10. 如果一个实体集没有足够形成主码的属性集合，我们就称其为弱实体集。而有主码的实体集称为强实体集。
11. 特殊化和一般化定义了高层实体集和一个或多个低层实体集之间的包含关系。特殊化是取出高层实体集的一个子集来形成一个低实体集。一般化是用两个或多个不相交的低层实体集的并集来形成一个高层实体集。高层实体集的属性被低层实体集继承。

Chapter 7 关系数据库设计
1. 无损分解的判定：令R为一关系模式，F为R上的函数依赖集。令R1和R2为R的分解，令r（R）是模式R上的一个关系。如果我们把r投影到R1和R2上，然后计算投影结果的自然连接，得到的结果和r一模一样，则说明该分解是无损分解。
2. BCNF：具有函数依赖集F的关系模式R属于ΒCNF的条件是，对所有F的闭包中形如α->β的函数依赖（α是R的子集，β是R的子集），下面至少有一个成立：
α->β是平凡的函数依赖（即，β是α的子集）
α是模式R的一个超码。
3. 3NF：所有F的闭包中形如α->β的函数依赖（α是R的子集，β是R的子集），下面至少有一个成立：
α->β是平凡的函数依赖（即，β是α的子集）
α是模式R的一个超码。
β-α中的每一个属性Α都包含在R的一个候选码中。
4. Armstrong公理：
1、自反律：若α为一个属性集并且β是α的子集，则有α->β
2、增补律：若有α->β且γ为一属性集，则有γα->γβ
3、传递律：若有α->β及β->γ，则有α->γ
5. 最小函数依赖集 ：如果函数依赖集F满足下列条件，则称F为最小函数依赖集或最小覆盖。 ① F中的任何一个函数依赖的右部仅含有一个属性； ② F中不存在这样一个函数依赖X→A，使得F与F-{X→A}等价； ③ F中不存在这样一个函数依赖X→A，X有真子集Z使得F-{X→A}∪{Z→A}与F等价。
6. F闭包：由F中的所有FD可以推导出所有FD的集合，记为F+ 。

Chapter 11 存储和文件结构
说明：如何构造稳定的存储器，具体有作业，可参考。也可部分参考17章。
1.什么是RAID？
为了提高性能和可靠性，人们提出了多种磁盘组织技术，统称为冗余独立磁盘阵列（Redundant Arrays of Independent Disks，RAID）。RAID是一种把多块独立的硬盘按不同的方式组合起来形成一个硬盘组（逻辑硬盘），从而提供比单个硬盘更高的存储性能和提供数据备份技术。组成磁盘阵列的不同方式称为RAID级别。
RAID 0 级，无冗余拆分，指的是在块级拆分且没有任何冗余（例如镜像或奇偶校验位）的磁盘阵列。
RAID 1 级，指的是使用块级拆分的磁盘镜像。
RAID 2 级，也称为内存风格的纠错码（ECC）组织结构，使用奇偶校验位。
RAID 3 级，也称为位交叉的奇偶校验组织结构。如果一个扇区被破坏，系统能准确地知道是哪个扇区坏了，并且对扇区的每一位，系统可以通过计算其他磁盘上对应扇区的对应位的奇偶值来推断出该位是1还是0，如果其余位的奇偶校验值等于存储的奇偶校验值，则丢失的位是0，反之为1。
RAID 4 级，也称为块交叉的奇偶校验组织结构。它像RAID 0级一样使用块级拆分，此外在一个独立的磁盘上为其他N 个磁盘上对应的块保留一个奇偶校验块。如果一个磁盘发生故障，可以使用奇偶校验块和其他磁盘上对应的块来恢复发生故障的磁盘上的块。
RAID 5 级，也称为块交叉的分布奇偶校验。RAID 5级将数据和奇偶校验位都分布到所有的N+ 1个磁盘中，而不是在N 个磁盘上存储数据而在一个磁盘上存储奇偶校验位。
RAID 6 级，也称为P + Q冗余方案。它和RAID 5级非常相似，但是存储了额外的冗余信息，以防止多个磁盘发生故障。
2. 列出常用无力存储介质并比较其优劣
1）高速缓冲存储器（cache）：
速度最快，价格最贵，为易失性存储。
2）主存（main memory）：
速度快，价格贵，易失性存储
3）快速闪存储器（flash memory ）：
速度快，价格适中，非易失性存储。
4）磁盘存储器（Megnetic-disk storage ）：
速度适中，价格便宜，非易失性存储
5）光存储器（optical storage ）：
速度较慢，价格较便宜，非易失性存储。
√ 只读光盘( CD-ROM )或者只读数字视频磁盘( DVD-ROM ) 是不可写的。
√ 可以“写一次”的光盘（称为CD-R）和DVD盘（称为DVD- R）。
√ 可以多次写的光盘（称为CD-RW）和DVD盘（DVD-RW和DVD-RAM）。
6）磁带存储器（tape storage ）：
速度很慢，价格很便宜，非易失性存储。

存储介质层次结构通常划分为如下三类：
1.基本存储（primary storage） ：如高速缓冲存储器和主存。
2.辅助存储（secondary storage）或联机存储（online storage）：如磁盘 、快速闪存储器。
3.第三级存储（tertiary storage），或脱机存储（offline storage）：如磁带机和自动光盘机。

Chapter 15 事务
说明：并发执行具体有作业，可参考。也可部分参考16章。
1. ACID特性：
1）原子性（atomicity）：事务的所有操作在数据库中要么全部正确反映出来要么全部不反映。由完整性约束确保原子性。
2）一致性（consistency）：事务隔离执行时（即在没有其他事务并发执行的情况下）保持数据库的一致性。确保一致性由事务管理部件处理。
3）隔离性（isolation）：尽管多个事务可以并发执行，但系统保证，对于任何一对事务Ti和Tj，在Ti 看来，Tj 或者在Ti 开始之前已经停止执行，或者在Ti 完成之后开始执行。这样，每个事务都感觉不到系统中有其他事务在并发地执行。确保隔离性是并发控制部件的责任。
4）持久性（durability）：一个事务成功完成后，它对数据库的改变必须是永久的，即使是系统出现故障时也是如此。确保持久性恢复管理部件实现。
原子性和持久性的实现：
数据库系统的恢复管理部件通过不同的方案实现对原子性和持久性的支持。
一个简单但效率极低的方案，名叫影子拷贝（shadow copy）方案。（自己看书 15.3）
2.事务状态
1）活动状态（active）：初始状态，事务执行时处于这个状态。
2）部分提交状态（partially committed）：最后一条语句被执行后。
3）失败状态（failed）：发现正常的执行不能继续后。
4）中止状态（aborted）：事务回滚并且数据库已被恢复到事务开始执行前的状态后。
5）提交状态（committed）：成功完成后。

3. 级联回滚：因一个事务故障导致一系列事务回滚的现象称为级联回滚。（书P414）

Chapter 16 并发控制
1. 锁的概念：
当一个事务访问某个数据项时，其他任何事务都不能修改该数据项。实现该需求最常用的方法是只允许事务访问当前该事务持有锁的数据项。
给数据项加锁的方式主要有2类：(1) 如果事务Ti获得了数据项Q的共享型锁S，则Ti可读但不能写Q；(2) 如果事务Ti获得了数据项Q的排他型锁X，则Ti既可读又可写Q。
每个事物都需根据将对数据项Q进行的操作类型向并发控制器申请适当的锁，只有在并发控制器授予所需锁后，事务才能继续其操作。
2. 相容性及相容矩阵：
相容性：令A和B为任意锁类型，假设事务Ti请求为数据项Q加A类型锁，Tj当前拥有Q的B类型锁(Ti≠Tj)。若在Q有B类型锁的情况下，事务Ti仍可以立即获得Q上的锁，则称A与B两者类型锁相容。
表示这种相容关系的矩阵称为相容矩阵。S锁和X锁的相容矩阵如下：

S
X
S
True
False
X
False
False
说明：S型与S型相容，而与X型不相容。任何时候，一个数据项可同时有多个被不同事务拥有的S锁，而此后的X锁请求必须一直等到所有的S锁被释放才获得授予。
3. 死锁：如果进入了一种哪个事务都不能继续执行的状态，则称这种情形为死锁。当死锁发生时，系统必须回滚两个事务中的一个。一旦回滚，锁住的数据项就被解锁，即可解决。
4. 饿死：如果一个事务序列，其中每个事务都申请对数据项加S锁，每个事务在授权加锁后一小段时间内释放锁，而事务T则总不能对其加X锁。这种T可能永远不能取得进展的现象称为饿死。
5. 封锁协议：即指要求在系统中的每一个事务都遵从的一组规则。这些规则规定事务何时对各数据项进行加锁和解锁。一个封锁协议当且仅当其所有合法的调度为冲突可串行化时，即称其保证冲突可串行性。
6. 两阶段封锁协议：其保证可串行性。要求每个事务分2个阶段提出加锁和解锁申请：
增长阶段：事务可以获得锁，但不能释放锁。
缩减阶段：事务可以释放锁，但不能获得新锁。
事务一旦释放锁，就进入缩减阶段，不能再发出加锁请求。
在调度中事务获得其最后加锁的位置(即增长阶段结束点)称为事务的封锁点。
解决的问题有：避免数据库操作时引起的数据不一致；保证了并发调度的正确性。但仍存在的问题有：不能保证不发生死锁；可能会发生级联回滚。
7. 严格两阶段封锁协议：可以避免两阶段封锁的级联回滚问题。其不仅要求封锁是两阶段的，还要求事务持有的所有排他锁必须在事务提交后方可释放。
8. 锁转换：是一种将共享锁提升为排他锁以及将排他锁降级为共享锁的机制。用upgrade表示从共享锁提升为排他锁，用downgrade表示从排他锁降级为共享锁。锁提升只能发生在增长阶段，而锁降级只能发生在缩减阶段。
9. 时间戳：对于系统中每个事务Ti，把一个唯一的固定时间戳和它联系起来，此时间戳即为TS(Ti)。改时间戳是在事务Ti开始执行前由数据库系统赋予的。事务的时间戳决定了串行化顺序。
10. Thomas写规则：假设事务Ti发出write(Q)，(1) 如果TS(Ti)< R-timestamp(Q)，则Ti产生的Q值是先前所需要的值，且系统以假定该值不会产生。因此，系统拒绝write操作，Ti回滚。(2) 如果TS(Ti)< W-timestamp(Q)，则Ti试图写入的Q值已过时。因此，这个write操作可忽略。(3) 否则，系统执行write操作，将W-timestamp(Q)设为TS(Ti)。

Chapter 17 恢复系统
1. 故障分类：事务故障(逻辑错误和系统错误可能造成事务执行失败)；系统崩溃；磁盘故障。其中最致命的故障为磁盘故障，即非易失性存储器故障。其恢复策略为：利用其他磁盘上的数据副本，或三级介质(如磁带)上的归档备份重新做数据库操作以完成故障恢复。
2. 稳定存储器：即指在其中的信息永不丢失的存储器。
实现：RAID系统保证了单个磁盘的故障（即使发生在数据传送过程中）不会导致数据丢失。最简单并且最快的RAID形式是磁盘镜像，即在不同的磁盘上为每个磁盘块保存两个副本。RAID系统不能防止由于自然灾难而导致的数据丢失。许多系统通过将归档备份存储在磁带上并转移到其他地方来防止这种灾难。更安全的系统在远程站点为稳定存储器的每一个块保存一个副本，除在本地磁盘系统进行存储外，还通过网络存储到远程站点。
3. 基于日志的恢复：
每次事务执行写操作之前，必须在数据库被修改前建立该次写操作的日志记录。一旦日志记录已存在，如果需要，我们就可以输出对数据库的修改，并且，我们能够通过搜索、利用日志记录中的旧值字段来撤消(undo)已经对数据库的修改，甚至是重做(redo)数据库操作。为了从系统故障和磁盘故障中恢复时能使用日志记录，日志必须放在稳定存储器上。
4. 基于checkpoint的log恢复实现过程：
在做完维护日志操作后，将一个日志记录<checkpoint>输出到稳定存储器。
故障发生后，恢复机制检查日志来确定最近的检查点发生前开始执行的最近的一个事务Ti。要找到这个事务只需从日志的尾部由后至前搜索日志，直到找到第一个<checkpoint>记录(理论上日志的最后一个检查点记录)，然后继续向前搜索直至发现下一个<Ti start>记录。一旦系统确定后，则只需对事务Ti及其之后开始执行的所有事务Tj执行redo和undo操作。用T代表这些事务。而日志的剩余部分可以忽略，并且可以根据需要随时删除。恢复操作：(1) 对T中所有事务Tk，若日志中没有记录<Tk commit>，则执行undo(Tk)；(2) 对T中所有事务Tk，若日志中有记录<Tk commit>，则执行redo(Tk)。
5. 远程备份系统：具有远程备份功能的事务处理系统可以称为远程备份系统。
在一个站点（主站点）执行事务处理，使用一个远程备份站点(从站点)，在这里所有主站点的数据都被复制。随着更新在主站点上执行，远程站点必须保持与主站点同步——通过发送所有主站点的日志记录来实现。远程备份站点必须物理地与主站点分开。当主站点发生故障时，远程备份站点就接管处理：使用源于主站点的数据副本以及收到的来自主站点的日志记录执行恢复。一旦恢复执行完成，远程备份站点就开始处理事务。大大提高了系统的可用性，远程备份站点系统的性能比一个具有两阶段提交的分布式系统的性能好。
设计远程备份系统时有几个问题必须考虑：故障检测；控制权移交；恢复时间；提交时间。