高级数据库设计模型

一、E-R模型

1.实体-联系模型：称E-R模型，实体由一张实体表以及相应的属性组成（方框表示），联系由一张联系表以及相应的属性组成（用菱形表示），属性由椭圆形表示。

2.一对一联系：如下图，一个A对应一个B，一个B对应一个A。

3.一对多联系：如下图，一个A对应多个B，一个B对应一个A。

4.多对多联系：如下图，一个A对应多个B，一个B对应多个A。

5.多个实体间联系：如下图，一个教师对应一门课程，一本参考书对应一门课程，一门课程对应多个教师，一本参考书对应多个教师，一门课程对应多本参考书，一个教师对应多本参考书。

6.单个实体内部联系：如下图，一个职工领导多个职工。

7.父类-子类联系：如下图，把父实体型中的实体分配到子实体型中，实际上我们不需要建立学生的表，只需要简历研究生、本科生表即可表示这类联系。

8.不相交约束：如下图，标明一个学生不能既是研究生又是本科生，父实体最多只能是子实体中的一种。

9.完备性约束：如下图，学生要么是研究生要么是本科生，二者居其一，父实体必须是子实体中的一种，双线表示。

10.基数约束：限定了对应的最多最少个数，如下图，一个班级对应30~40个学生，一个学生对应一个班级。

11.part-of约束：一个实体型依赖于其他实体型存在，则这个实体型叫做弱实体型，如下图，楼房没了房间自然没了。

12.E-R模型转换为关系模型：

（1）1：1 转换：可合并两实体（包含两实体、联系的属性），也可建立联系表（键包含两实体任意一个候选键）。

（2）1：n 转换：可合并，也可建立联系表（键包含n端的候选键）。

（3）m：n 转换：建立联系表（键包含m、n端各个候选键）。

（4）三个或以上实体转换：建立关系表（键包含各个实体的候选键）。

二、关系代数

1.并（union）：集合运算一种，记号 ∪ 。

2.差（except）：集合运算一种，记号 - 。

3.交（intersection）：集合运算一种，记号 ∩ 。

4.笛卡儿积（cartesian product）：如下图，第一个关系每一行分别与第二个关系的每一行组合。

X=

5.选择（selection）：在关系R中选择出满足F的元组，记号 σF(R) 。

6.投影（projection）：在关系R上投影选出集合A中的属性，记号 ΠA(R) 。

7.连接（join）：在笛卡儿积中选择出满足F的元组，记号 ⋈F 。

8.自然连接（natural join）：如下图，第一个关系中每一行与第二个关系的每一行进行匹配，如果得到有交叉部分则合并，若无交叉部分则舍弃。

⋈=

9.外连接（outer join）：执行自然连接后，将舍弃的部分也加入，并且匹配失败处的属性用NULL代替。

外连接=

10.除法运算（division）：关系R除以关系S的结果为T，则T包含所有在R但不在S中的属性，且T的元组与S的元组的所有组合在R中。下例足以说明，为了得到所有选了数学、英语并且是二年级的学生，我们用到除法运算。

÷=

11.五种基本运算（可组合成其他运算）：并、差、笛卡儿积、选择、投影。

三、代数查询优化

1.查询树的启发式优化（heuristic rules）：

（1）选择运算尽可能先做。

（2）投影运算和选择运算同时进行。

（3）把投影同其前或后的双目运算结合起来。

（4）把某些选择同在它前面要执行的笛卡儿积结合起来成为一个连接运算。

（5）找出公共子表达式。

2.代数查询优化实例：

我们要把以下SQL语句变成查询树并代数优化它：

SELECT Student.Sname FROM Student,SC WHERE Student.Sno=SC.Sno AND SC.Cno='2';

优化前后的查询树如下图：

四、数据恢复

1.事务（transaction）：

数据库操作序列，是不可分割的工作单位。提交事务后数据库一般返回两种结束语句，COMMIT（提交成功）和ROLLBACK（回滚，事务运行期间发生故障，系统将该事务已完成的所有操作撤回，好像什么也没发生）。

2.事务的ACID特性：

（1）原子性（atomicity）：事务为逻辑工作单位。

（2）一致性（consistency）：使数据库处于正确状态。

（3）隔离性（isolation）：一个事务的执行不被其他事务干扰。

（4）持续性（durability）：事务一旦提交，对数据库的改变应该是永久的。

3.故障（crash）：

（1）事务内部故障：如转账时只扣除了一方的钱却未增加另一方的钱，与业务逻辑相关。

（2）系统故障：如宕机

（3）介质故障：磁盘损坏，出现频率极小但是破坏性极大。

（4）计算机病毒：

4.日志文件（log record）：

（1）日志文件格式和内容：

日志文件用来记录事务对数据库的更新操作，需要登记的内容包括：

<1>事务标识

<2>各事务的开始标记（BEGIN TRANSACTION）。

<3>各事务的结束标记（COMMIT或者ROLLBACK）。

<4>各事务的所有更新操作（操作类型、操作对象、旧值、新值）。

（2）登记日志原则：

严格按照并发事务的执行时间次序、先写日志文件后写数据库。

（3）恢复策略：

当事务在运行至正常终点前被终止时的恢复：

<1>反向扫描日志文件，查找该事务的更新操作。

<2>对事物的更新操作执行逆操作（撤销）。

<3>继续反向扫描日志文件，同样处理，直到读到此事务的开始标记，故障恢复完成。

宕机时的恢复：

<1>正向扫描日志文件，找出故障发生前已提交的事务，将其记入重做队列。同时找出故障发生时未完成的事务（如只有BEGIN记录，无相应COMMIT记录），将其记入撤销队列。

<2>对撤销队列中各事务撤销处理。

<3>对重做队列中各事务重做处理。

介质故障的恢复：

重装数据库，重做已完成的全部事务。

5.检查点（checkpoint）：

（1）作用：

解决两个问题：1.搜索整个日志花费大量时间。2.很多需要重做的事务实际上已经将它们的更新操作写到了数据库，然而恢复子系统又重新执行这些操作，浪费了大量时间。

（2）检查点记录及重新开始文件：

检查点记录内容（放在日志文件中）：1.建立检查点时刻所有正在执行的事务清单。2.这些事务最近一个日志记录的地址。

重新开始文件内容：各检查点记录在日志文件中的地址。

（3）动态维护日志文件：

周期性地（如每隔一小时）执行建立检查点、保存数据库状态操作，具体如下：

<1>将当前日志缓冲区中的所有日志记录写入到磁盘日志文件。

<2>在日志文件中写入一个检查点记录。

<3>将当前数据缓冲区的所有数据记录写入磁盘的数据库中。

<4>把检查点记录在日志文件中的地址写入重新开始文件。

（4）检查点故障恢复：

检查点之前已经做完的事务时保证完成的，因此故障发生后的策略如下图：

五、并发控制

1.并发带来的数据不一致性：

（1）丢失修改（lost update）：两事务T1和T2读入同一数据并修改，T2的修改结果破坏了T1的修改结果。

（2）不可重复读（non-repeatable read）：T1读取数据后，T2执行更新操作，使T1无法再现前一次读取结果。

（3）读脏数据（dirty read）：T1修改某数据，T2读取，T1又被撤销数据恢复原值，T2读的数据存在不一致性。

2.封锁协议：

（1）排他锁（exclusive locks，写锁，X锁）：

事务T对数据A加上X锁，只允许T读写A，其他事务不能再对A加任何锁。

（2）共享锁（share locks，读锁，S锁）：

事务T对数据A加上S锁，T只能读A不能写，其他事务能再对A加S锁。

（3）X锁于S锁的相容矩阵：

（4）一级封锁协议：

协议：在写数据之前必须加X锁，事务结束释放。

作用：防止丢失修改。

（5）二级封锁协议：

协议：在写数据之前必须加X锁，事务结束释放。在读数据之前必须加S锁，读完释放。

作用：防止丢失修改，防止读脏数据。

（6）三级封锁协议：

协议：在写数据之前必须加X锁，事务结束释放。在读数据之前必须加S锁，事务结束释放。

作用：防止丢失修改，防止读脏数据，防止不可重复读。

3.死锁：

（1）死锁预防：

<1>一次封锁法：一次性将事务所有需要的数据全部加锁。

<2>顺序封锁法：对数据对象规定一个封锁顺序。

（2）死锁的诊断：

<1>超时法：事务等待时间超过设定值，则判定死锁。

<2>等待图法：如发现存在回路，则判定死锁。等待图如下，T1-->T2表示T1等待T2。

4.可串行化调度（serializable schedule）：

若多事务并发执行的结果与某一顺序执行结果相同，则是可串行化调度，被认为是正确调度。

5.冲突可串行化调度：

（1）定义：

冲突可串行化调度是可串行化调度的充分条件，冲突操作有如下：

Ri(x)与Wj(x)     （事务i读x，事务j写x，i不是j，即不同事务对同一数据的读写）

Wi(x)与Wj(x)     （事务i写x，事务j写x，i不是j，即不同事务对同一数据的写写）

不同事务的冲突操作和同一事物的两个操作是不能交换的，除此之外可交换，若交换后得到串行执行两事务的序列，则认为是冲突可串行化的。

（2）判断可串行化调度示例：

判断操作序列是否可串行化：r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)。

r2(A)w2(A)是同一事物的两个操作，不能交互，但r1(B)与w2(A)不是冲突操作，可交换，同理，r1(B)与r2(A)可交换。

因此得到：r1(A)w1(A)r1(B)r2(A)w2(A)w1(B)r2(B)w2(B)。

w1(B)与r2(A)、w2(A)也都不是冲突操作，因此再移到前面来。

最后得到：r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)，为串行执行两事务的序列，则为冲突可串行，推出可串行。

6.两段锁协议（two-phase locking，2PL）：

（1）定义：事务分为两个阶段，第一阶段获得封锁（只能申请锁），第二阶段释放封锁（只能释放封锁），即上锁的操作全部放在前面解锁的操作全部放在后面。

（2）作用：若并发的所有事务都遵循两段锁协议，则这些事务的任何并发调度策略都是可串行化的（充分条件），由于并不要求事务一次性将所需要的数据全部加锁，也可能发生死锁。

7.多粒度封锁协议（multiple granularity locking）：

（1）定义：多粒度封锁协议允许多粒度树中的每个结点被独立地加锁，对一个结点加锁（显示封锁）意味着这个结点的所有后裔也被加了同类型的锁（隐式封锁），多粒度树如下图所示。

（2）意向锁（intention lock）：如果对一个结点加意向锁，则说明该结点的下层结点正在被加锁，因此对任意结点加锁时必须先对它的所有上层结点加意向锁。

（3）IS锁（intent share lock）：如事务T1要对关系R1中元组加S锁，则首先要对关系R1及所在数据库D1加IS锁。

（4）IX锁（intent exclusive lock）：如事务T1要对关系R1中元组加X锁，则首先要对关系R1及所在数据库D1加IX锁。

（5）SIX锁（share intent exclusive lock）：如对某个表加SIX锁，则先要读表（对表加S锁），同时会写个别元组（对该表加IX锁），即加SIX锁（SIX=S+IX）。

（6）相容性矩阵：

例题1：

For the following schedules of three transactions in concurrency control, the serializable schedules are:

A. r1(A)r1(B)w2(B)w1(A)r3(B)w3(B)r2(B)r2(A)     B. r1(A)w2(B)r1(B)w1(A)r3(B)w3(B)r2(B)r2(A)

C. r3(B)w3(B)r2(B)r2(A)r1(A)w2(B)r1(B)w1(A)     D. r3(B)r1(A)w3(B)r2(B)r2(A)w2(B)r1(B)w1(A)

解答：

对于A：

r1(A)r1(B)w2(B)w1(A)r3(B)w3(B)r2(B)r2(A)，w2(B)与w1(A)可交换

交换后r1(A)r1(B)w1(A)w2(B)r3(B)w3(B)r2(B)r2(A)，w2(B)不可与r3(B)交换，w3(B)不可与r2(B)交换，排除。

对于B：

r1(A)w2(B)r1(B)w1(A)r3(B)w3(B)r2(B)r2(A)，w2(B)只能跟r1(A)交换，但r2(B)不能跟w3(B)交换，排除。

对于C：

r3(B)w3(B)r2(B)r2(A)r1(A)w2(B)r1(B)w1(A)，r1(A)与w2(B)可交换，

交换后r3(B)w3(B)r2(B)r2(A)w2(B)r1(A)r1(B)w1(A)，遵循事务3,2,1串行化调度，C为正确答案。

对于D：

r3(B)r1(A)w3(B)r2(B)r2(A)w2(B)r1(B)w1(A)，r1(A)能与w3(B)、r2(B)交换，

交换后r3(B)w3(B)r2(B)r1(A)r2(A)w2(B)r1(B)w1(A)，r1(A)能与r2(A)、w2(B)交换，

交换后r3(B)w3(B)r2(B)r2(A)w2(B)r1(A)r1(B)w1(A)，遵循事务3,2,1串行化调度，D也为正确答案。

例题2：

For an application on Bookstore Management, there are three entity sets: Book, Bookstore, and Warehouse. The attributes of entity set Bookstore includes: BSname, BSaddress, BStel, BSmanager; and the attributes of Book contains: BookNo, Bname, Bprice, Author, Publisher, PublishYear, Version; and the attributes of Warehouse contains: Wno, Wname, Waddress, Wadministrator. And two relationship sets: Bookstore and Book related through a binary relationship set Sale; and Book and Warehouse related through a binary relationship set Stock. The two relationship sets have the following attributes respectively: Sale has attributes: SaleDate and SaleQuantity; Stock has attributes: InDate, InPrice, and StockQuantity. 

(1) Please give the corresponding ER diagram. Create the corresponding relational schemas, and point out the primary keys and the foreign keys.

(2) Use relational algebra expression and SQL statement for the following query: Find the Bookstore name and quantity of all Books written by "Donald E.Knuth" which are sold within 60 days and the stock in the warehouse is less than 10 items.

(3) Please give a query tree of the above SQL query in (2), and then give an optimized query tree and give a brief explanation on the query process and its optimization.

解答：

有如下实体

Bookstore（BSname，BSaddress，BStel，BSmanager）

Book（BookNo，Bname，Bprice，Author，Publisher，PublishYear，Version）

Warehouse（Wno，Wname，Waddress，Wadministrator）

有如下联系

Sale（Bookstore_key，Book_key1，SaleDate）

Stock（Book_key2，Warehouse_key，InDate，InPrice，StockQuantity）

（1）画出ER图，给出关系模式，指出主键和外键。

（2）用关系代数表达式和SQL表达式表述：Find the Bookstore name and quantity of all Books written by "Donald E.Knuth" which are sold within 60 days and the stock in the warehouse is less than 10 items.

（3）给出(2)中的查询树，再给出查询树的优化，说明原因。

例题3：

(1) What is the Two-Phase Locking Protocol? Will Two-phase locking ensure freedom from deadlocks? How to prevent and deal with deadlocks?

(2) The following partial log records show some transactions executed concurrently under Immediate database modification scheme. At time Tc, a check point is constructed and a log record <checkpoint{T1, T2}> is recorded. And afrer the <T5, D, 10, 20>, at time Tf, a system failure occurred. Please give a figure to illustrate the state and explain the recovery process based on the log.

解答：

（1）何为二段锁协议？ 二段锁协议是否保证无死锁？ 如何避免和处理死锁？

事务分为两个阶段，第一阶段获得封锁（只能申请锁），第二阶段释放封锁（只能释放封锁），即上锁的操作全部放在前面解锁的操作全部放在后面，不能保证无死锁，避免死锁：一次性分配、有序分配，检测死锁：出现等待环。

（2）上图为数据库日志记录，Tc时刻记录检查点<checkpoint{T1, T2}> ，Tf时刻也就是在<T5, D, 10, 20>登记后发生系统错误，请给出出错时的数据状态以及如何恢复。

根据上图，发生故障时，A=20，B=10，C=20，D=20

T1在最近的检查点之前commit了，无需处理。

T2在最近检查点之后commit，重做。

T3在最近检查点之后commit，重做。

T4无commit，撤销，A回10，D回0。

T5无commit，撤销，D回10.

恢复之后，A=10，B=10，C=20，D=0。