第七章：数据库设计理论基础.

Presentation on theme: "第七章：数据库设计理论基础."— Presentation transcript:

1 第七章：数据库设计理论基础

2 银行数据库模式 branch = (branch_name, branch_city, assets)
customer = (customer_id, customer_name, customer_street, customer_city) loan = (loan_number, amount) account = (account_number, balance) employee = (employee_id. employee_name, telephone_number, start_date) dependent_name = (employee_id, dname) account_branch = (account_number, branch_name) loan_branch = (loan_number, branch_name) borrower = (customer_id, loan_number) depositor = (customer_id, account_number) cust_banker = (customer_id, employee_id, type) works_for = (worker_employee_id, manager_employee_id) payment = (loan_number, payment_number, payment_date, payment_amount) savings_account = (account_number, interest_rate) checking_account = (account_number, overdraft_amount)

3 有损分解

4 函数依赖 函数依赖（Functional Dependency，FD）是数据依赖的一种，它反映属性或属性组之间互相依存、互相制约的关系。

5 bor_loan = (customer_id, loan_number, amount ).
函数依赖的定义 定义 设R(U)是属性集U上的一个关系模式，X和Y均为U＝{A1，A2，…，An}的子集，r为R的任一个关系。如果对于r中的任意两个元组u、v，只要有u[X]＝v[X ]，就有u[Y]＝v[Y]，则称X 函数决定Y或称Y函数依赖于X，记为X →Y。其中X 称为决定因素（Determinant）。 bor_loan = (customer_id, loan_number, amount ). 函数依赖成立: loan_number  amount

6 函数依赖的定义 在R(U)中，如果X→Y，并且对于X的任何真子集X ‘都有X ’ Y，则称Y完全函数依赖于X，记作 （简记为X→Y ）；如果X→Y，且X中存在一个真子集X ‘，使得X ’ → Y成立，则称Y部分函数依赖于X，记作 。

7 函数依赖的逻辑蕴涵 设有关系模式R(U)及其函数依赖集F，如果对于R的任一个满足F的关系r函数依赖X→Y都成立，则称F逻辑蕴涵X→Y ，或称X→Y 可由F推出。 所有被F逻辑蕴涵的函数依赖的集合，称为F的闭包（closure），记为F+。在一般情况下F F+，如果F＝F+，则称F为一个函数依赖的完备集。

8 函数依赖的逻辑蕴涵 设R＝ABC，F＝{A→B，B→C}，则F+由所有这样的函数依赖X→Y组成：
（1）X含有A。如ABC→AB，AB→BC，A→A，A→C。 （2）X含有B但不含A，且Y也不含A。如BC→B，B→C，B→φ。 （3）X→Y是C→C和C→φ。

9 函数依赖的逻辑蕴涵 设R＝ABC，F＝{A→B，B→C}，则F+由所有这样的函数依赖X→Y组成：
（1）X含有A。如ABC→AB，AB→BC，A→A，A→C。 （2）X含有B但不含A，且Y也不含A。如BC→B，B→C，B→φ。 （3）X→Y是C→C和C→φ。

10 Armstrong公理 设U为关系模式R的属性全集，F为U上的一组函数依赖，对R (U，F)有以下推理规则。
A1：自反律（Reflexivity） 如果Y XU，则X→Y为F所蕴涵。 A2：增广律（Augmentation） 如果X→Y为F所蕴涵，且ZU，则XZ→YZ为F所蕴涵。 A3：传递律（Transitivity） 如果X→Y和Y→Z为F所蕴涵，则X→Z为F所蕴涵。

11 Armstrong公理 定理 Armstrong公理是正确的，即由F出发根据 Armstrong公理推导出来的每一个函数依赖必定为F所逻辑蕴涵。 根据Armstrong公理可以得到下面三条推论，它们也是很有用的推理规则。 （1）合并规则（Union Rule） 如果X→Y，X→Z，则X→YZ。 （2）伪传递规则（Pseudotransivity Rule） 如果X→Y、WY→Z，则XW→Z。 （3）分解规则（Decomposition Rule） 如果X→Y ，且ZY，则X→Z。

12 Armstrong公理的完备性 定义 设F是属性集U上的函数依赖集，X是U的子集，则由Armstrong公理可从F推导出的所有X→Ai所形成的属性集{Ai｜i＝1,2,…}称为X对于F的闭包，记为X+。 例 设R＝ABC，F＝｛A→B，B→C｝，则 ① 当X＝A时，X+＝ABC； ② 当X＝B时，X+＝BC； ③ 当X＝C时，X+＝C。 引理 当且仅当Y  X+时，X→Y 能根据Armstrong公理由F导出。

13 闭包计算 由函数依赖集F计算F+是一件相当费时的事。即使F很小，F+却可能很大。
但幸运的是计算F+的目的往往是为了判断函数依赖X→Y 是否为F所蕴涵，而根据引理5.1，只要知道Y  X+，就可以断定X→Y 为F所蕴涵。因此，可以用计算X+代替计算F+，通过判断是否满足Y  X+来判定X→Y 是否为F所蕴涵。 算法 求属性集X关于函数依赖集F的闭包X+。 输入：关系模式R的属性全集U，在U上的函数依赖集F，以及U的子集X。 输出：属性集X关于F的闭包X+。

14 闭包计算 方法： （1）令X(0)＝X，i=0； （2）计算B＝{A｜(V)( W)(V→W∈F∧V X（i）∧A∈W}；
（3）X (i+1)＝B∪X (i)； （4）如果X (i+1)≠X (i)，则令i＝i+1，返回（2）； （5）输出X (i)，它就是X+。

15 闭包计算 例 已知关系模式R中U＝{A，B，C，D，E，G}，F＝{AB→C，C→A，BC→D，ACD→B，D→EG，BE→C，CG→BD，CE→AG｝，求(BD)+。 解：设X＝BD （1）令X(0)＝BD。 （2）计算X(1)：在F中找左边为X(0)子集即B、D或BD的函数依赖，结果有D→EG，所以X(1)＝X(0)∪EG＝BDEG。 （3）计算X(2)：在F中找尚未使用过的、左边为X(1)子集的函数依赖，得BE→C，所以X(2)＝X(1)∪C＝BCDEG。 （4）计算X(3)：在F中找尚未用过且左边为X(2)子集的函数依赖，得C→A、BC→D、CG→BD、CE→AG，所以X(3)＝X(2)∪ABDG＝ABCDEG。 由于X(3)已包含全部属性，显然X(4)＝X(3)，算法终止，得(BD)+＝ABCDEG。

16 函数依赖集的等价和最小集 定义 设F和G是两个函数依赖集，如果F+＝G+，则称F和G等价，也称F覆盖G，或G覆盖F。
（2）对于F中的任一函数依赖X→A，集F－{ X→A }不等价于F； （3）对于F中的任一函数依赖X→A和X的任何真子集Z，集(F－{ X→A })∪{Z→A}不等价于F，则称F为最小函数依赖集或称最小覆盖。

17 函数依赖集的等价和最小集 定理 每个函数依赖集F都等价于一个最小函数依赖集。
（1）为了满足条件（1），只要根据分解规则把右侧是属性组的函数依赖分解为单属性的多个函数依赖即可。例如A→BC可分解为A→B和A→C，从而满足条件（1）。 （2）逐一考察F中的函数依赖X→Y，令G＝F－{ X→Y }，且对G求X+，因为F与G等价的充要条件是Y X+，所以如果Y X+，则X→Y 冗余，可以删去。 （3）逐一考察F中留下的函数依赖，消去左侧冗余的属性。为了判断函数依赖XY→A中Y是否冗余，可在F 中求X+，若AX+，则Y是冗余属性。 经过上述三步处理之后剩下的F一定是最小函数依赖集，并且与原来的F等价。F的最小函数依赖集不一定是唯一的。

18 函数依赖集的等价和最小集 例 求给出的F的最小函数依赖集。 解：按最小函数依赖集的定义分别考虑3个条件。
（1）根据分解规则分解右部为属性组的函数依赖，得：

19 函数依赖集的等价和最小集 （2）消去F1中多余的函数依赖。因为由C→A可导出CE→A，又由CG→D、C→A、ACD→B可导出CG→B，所以从F1中删去冗余函数依赖CE→A和CG→B，得：

20 函数依赖集的等价和最小集 （3）消去F2中左边多余的属性。因为由C→A、CD→B可导出ACD→B，所以可去掉ACD→B中左侧A属性，从而求得F的最小函数依赖集：

21 关系模式的分解 定义 关系模式R〈U, F〉的分解是指R为它的一组子集ρ＝{R1〈U1, F1〉, R2〈U2, F2〉，…，Rk〈Uk, Fk〉}所代替的过程。 分解的无损连接性（Lossless join）。分解的函数依赖保持性（Preserve dependency）。 分解具有“无损连接性” 分解要“保持函数依赖” 分解既要“保持函数依赖”，又要具有“无损连接性”。

22 分解的无损连接性

23 分解的无损连接性 例 已知关系模式R(ABCDE) 及其函数依赖集F＝{A→C，B→C，C→D，DE→C，CE→A}。试检验分解ρ＝{R1 (AD)，R2 (AB)，R3 (BE)，R4 (CDE)，R5 (AE)}的无损连接性。

24 分解的无损连接性 定理 如果ρ＝{R1，R2}是关系模式R的一个分解，F为R所满足的函数依赖集，则分解ρ具有无损连接性的充分必要条件为：
R1∩R2→R1－R2∈F+或 R1∩R2→R2－R1∈F+。 其中R1∩R2表示模式的交，结果为公共属性；R1－R2或R2－R1表示模式的差集，R1－R2的结果由属于R1但不属于R2的属性组成。

25 分解的函数依赖保持性 定义 设F是关系模式R的函数依赖集，ρ＝{R1,R2,…,Rk}为R的一个分解，如果 (F) 的并集（i=1,2,…,k）逻辑蕴涵F中的全部函数依赖，则称分解ρ具有函数依赖保持性。 一个无损连接的分解不一定具有函数依赖保持性；同样，一个保持函数依赖的分解也不一定具有无损连接性。而且有些实用的分解算法也往往顾此失彼，难以兼顾。

26 分解的函数依赖保持性 例 设关系模式R＝{CITY，ST，ZIP}表示各城市街道的邮政编码，其中属性分别表示城市、街道名和邮政编码，F＝{(CITY，ST)→ZIP，ZIP→CITY}。如果将R分解为ρ＝{R1，R2}，其中R1＝{ST，ZIP}，R2＝{CITY,ZIP}，由于 R1∩R2＝ZIP， R2－R1＝CITY， ZIP→CITY∈F

27 第一范式（1NF） 定义 如果关系模式R的所有的域为简单域，其元素不可再分，则称R为第一范式的关系，简记为R∈1NF。
部门(部门号，名称，经理(正经理，副经理)) 雇员(雇员号，姓名，工资(基本工资，补贴，奖金)) 可以转化为如下1NF的关系： 部门(部门号，名称，正经理，副经理)。 雇员(雇员号，姓名，基本工资，补贴，奖金)。

28 BCNF 设R是一个关系模式，如果对于每一个函数依赖对X→Y，其中的决定因素X都含有键，则称关系模式R满足Boyce-Codd范式，简称BC范式，记为R∈BCNF。 BC范式的本质意义在于，其中的每一个决定因素都是一个超键。或者说，在BCNF中，除了键决定其所有属性和超键决定其所有属性之外，绝不会有其他的非平凡函数依赖。 由以上定义可以得出关于BCNF关系模式的以下结论： （1）非主属性对关键字完全函数依赖； （2）主属性对不包含它的关键字完全函数依赖； （3）没有属性完全函数依赖于一组非主属性。

29 BCNF 例 在关系模式STJ(S，T，J)中，S、T、J分别表示学生、教师和课程。假设每位教师只教授一门课程，每门课程可有若干教师担任；此外对每门课程，一个学生只能听一位教师的讲义。由语义可得如下函数依赖集： T→J S,T→J S,J→T

30 分解算法 人们不得不接受这样的事实。 （1）若要求分解具有无损连接性，那么分解一定可以达到BCNF。
（2）若要求分解保持函数依赖，那么分解可以达到3NF，但不一定能达到BCNF。 （3）若要求分解既保持函数依赖，又具有无损连接性，那么分解也可以达到3NF，但不一定能达到BCNF。

31 分解算法 例 无损连接地将CTHRSG分解为一组BCNF的关系模式。其中C表示课程，T表示教师，H表示时间，R表示教室，S表示学生，G表示成绩。函数依赖集F及其所反映的语义分别为： C→T 每门课程仅有一位教师担任 HT→R 在任一时间，一个教师只能在一个教室上课 HR→C 在任一时间，每个教室只能上一门课 HS→R 在任一时间，每个学生只能在一个教室听课 CS→G 每个学生学习一门课程只有一个成绩

32 分解算法

33 对于给定的函数依赖集F ，如果对F+中所有形如 的函数依赖，其中  R ，   R。下面至少有一个成立:
   is trivial (i.e.,   )  is a superkey for R 则具有函数依赖集F的关系模式R属于BCN下。此外，如果关系模式集中的每个模式都属于BCNF，则这个数据库设计属于BCNF., Example 不属于BCNF的关系模式: bor_loan = ( customer_id, loan_number, amount ) 由于 loan_number  amount 成立 bor_loan 而 loan_number 不是超键

34 实例 R = (A, B, C ) F = {A  B B  C} Key = {A} R 不满足BCNF
分解 R1 = (A, B), R2 = (B, C) R1 and R2 满足BCNF 无损连接分解 依赖保持

35 BCNF 分解算法 result := {R }; done := false; compute F +; while (not done) do if (there is a schema Ri in result that is not in BCNF) then begin let    be a nontrivial functional dependency that holds on Ri such that   Ri is not in F +, and    = ; result := (result – Ri )  (Ri – )  (,  ); end else done := true;

36 BCNF 分解实例 R = (A, B, C ) F = {A  B B  C} Key = {A}
R 不满足BCNF (B  C but B 不是超键) 分解 R1 = (B, C) R2 = (A,B)

37 BCNF 分解实例 初始关系模式R 和函数依赖F 分解 最终分解结果 R1, R3, R4
R = (branch_name, branch_city, assets, customer_name, loan_number, amount ) F = {branch_name  assets branch_city loan_number  amount branch_name } Key = {loan_number, customer_name} 分解 R1 = (branch_name, branch_city, assets ) R2 = (branch_name, customer_name, loan_number, amount ) R3 = (branch_name, loan_number, amount ) R4 = (customer_name, loan_number ) 最终分解结果 R1, R3, R4

38 将关系模式分解为BCNF 给定关系模式R 和非平凡函数依赖  违背BCNF. 将R 分解为: 例如, (U  )
 = loan_number  = amount and bor_loan 分解为 (U  ) = ( loan_number, amount ) ( R - (  -  ) ) = ( customer_id, loan_number )

39 BCNF 和依赖保持 不是每个BCNF分解都是保持依赖的，同时它也说明我们不是总能满足 所有以下几个设计目标: 1) BCNF
2)无损连接。 3)保持函数依赖。

40 第三范式 如果关系模式R中的每一个非主属性既不部分依赖也不传递依赖于键，则称这个关系模式属于第三范式，记为R∈3NF。
设F是关系模式R的FD集，如果对于F中每一个非平凡的FD X→Y，都有X是R的超键，或者Y的每个属性都是主属性，那么称R是3NF的模式。 设关系模式R，当R上每一个FD X->A满足下列条件之一时： 即X→A 是一个平凡的FD X是R的超键 A是主属性 关系模式R就是3NF模式。

41 函数依赖的闭包 给定函数依赖集F，可以证明其他某些函数依赖也成立，我们称这些函数依赖被F 逻辑蕴涵.
例如: 如果 A  B and B  C, 则可以推理得出 A  C 令F为一个函数依赖集。F 的闭包是指F逻辑蕴涵的所有函数依赖的集合。. F 的闭包表示为 F+. 根据 Armstrong定理计算F+ : if   , then    (自反律) if   , then      (增补律) if   , and   , then    (传递律)

42 函数依赖的闭包 根据以下规则简化 F+ 的计算.
If    holds and    holds, then     holds (合并律) If     holds, then    holds and    holds (分解律) If    holds and     holds, then     holds (伪传递律)

43 属性集的闭包 令a为一属性集。我们称在函数依赖集F下被a函数确定的所有属性为F+下a的闭包， 计算在函数依赖集F下a+ 的算法
result := a; while (changes to result) do for each    in F do begin if   result then result := result   end

44 属性集的闭包示例 R = (A, B, C, G, H, I) F = {A  B A  C CG  H CG  I B  H}
(AG)+ 1. result = AG 2. result = ABCG (A  C and A  B) 3. result = ABCGH (CG  H and CG  AGBC) 4. result = ABCGHI (CG  I and CG  AGBCH) Is AG a candidate key? Is AG a super key? Does AG  R? == Is (AG)+  R Is any subset of AG a superkey? Does A  R? == Is (A)+  R Does G  R? == Is (G)+  R

45 正则覆盖 假设在关系模式上有函数依赖集F，那么在该关系上做任何更新时，数据库系统都要保证F中所有函数依赖在新数据库状态下仍然满足，否则就回滚该更新操作。 For example: A  C 是冗余的, in: {A  B, B  C} Parts of a functional dependency may be redundant E.g.: on RHS: {A  B, B  C, A  CD} can be simplified to {A  B, B  C, A  D} E.g.: on LHS: {A  B, B  C, AC  D} can be simplified to {A  B, B  C, A  D} F的正则覆盖FC是一个依赖集, 意指F逻辑蕴涵FC中的所有依赖，并且FC 逻辑蕴涵F中的所有依赖。

46 正则覆盖计算 R = (A, B, C) F = {A  BC B  C A  B AB  C}
Combine A  BC and A  B into A  BC Set is now {A  BC, B  C, AB  C} A is extraneous in AB  C Check if the result of deleting A from AB  C is implied by the other dependencies Yes: in fact, B  C is already present! Set is now {A  BC, B  C} C is extraneous in A  BC Check if A  C is logically implied by A  B and the other dependencies Yes: using transitivity on A  B and B  C. Can use attribute closure of A in more complex cases The canonical cover is: A  B B  C

47 无损连接分解 对于关系模式R = (R1, R2),在关系模式R上建立的任何关系 r均满足 r = R1 (r ) R2 (r )
将R 无损分解为 R1 和 R2 必须至少满足F+函数依赖中的一个 : R1  R2  R1 R1  R2  R2

48 实例 R = (A, B, C) F = {A  B, B  C) 可以用两种方法分解 R1 = (A, B), R2 = (B, C)
无损分解: R1  R2 = {B} and B  BC 依赖保持 R1 = (A, B), R2 = (A, C) R1  R2 = {A} and A  AB 依赖不保持 (cannot check B  C without computing R1 R2)

49 依赖保持 令 Fi 为F + 中仅包含Ri中属性的函数依赖集 分解为无损的, 如果 (F1  F2  …  Fn )+ = F +

50 依赖保持测试 将R 分解为 R1, R2, …, Rn测试函数依赖   是否保持。应用以下算法
result =  while (changes to result) do for each Ri in the decomposition t = (result  Ri)+  Ri result = result  t 如果结果包含中所有属性, 则函数依赖   保持.

51 BCNF 和依赖保持 在BCNF 分解过程中， 并不总能实现依赖保持
R = (J, K, L ) F = {JK  L L  K } 两个候选键= JK and JL R 不满足BCNF R 任何分解不保持 JK  L 这意味着对依赖JK  L 的测试需要连接。

52 3NF 实例 关系模式 R: R = (J, K, L ) F = {JK  L, L  K } 两个候选键: JK and JL
R 满足3NF JK  L JK 是超键 L  K K 包含在候选键中

53 3NF中的冗余 关系模式中存在冗余 3NF中冗余导致的问题实例 R = (J, K, L) F = {JK  L, L  K } J L
null l1 l2 k1 k2 repetition of information (e.g., the relationship l1, k1) need to use null values (e.g., to represent the relationship l2, k2 where there is no corresponding value for J).

54 3NF 分解算法 Let Fc be a canonical cover for F; i := 0; for each functional dependency    in Fc do if none of the schemas Rj, 1  j  i contains   then begin i := i + 1; Ri :=   end if none of the schemas Rj, 1  j  i contains a candidate key for R then begin i := i + 1; Ri := any candidate key for R; end return (R1, R2, ..., Ri)

55 3NF 分解算法 (Cont.) 以上算法保证: 每个关系模式Ri 满足3NF 分解是依赖保持的和无损连接的

56 3NF 分解实例 关系模式: cust_banker_branch = (customer_id, employee_id, branch_name, type ) 关系模式中的函数依赖是: customer_id, employee_id  branch_name, type employee_id  branch_name customer_id, branch_name  employee_id 首先计算正则覆盖 branch_name 是冗余的 其他属性不冗余，得到FC = customer_id, employee_id  type employee_id  branch_name customer_id, branch_name  employee_id

57 BCNF和3NF的比较 3NF优点: 即总可以在满足无损连接并保持依赖的前提下得到3NF设计。
关系数据库设计的次要三个目标: 1)3NF。 2)无损连接。 3)保持依赖。

58 设计目标 关系数据库的设计目标: BCNF. 无损连接. 依赖保持. 如果无法实现, 退而求其次 缺失依赖保持 3NF
SQL 除了超键以外，不提供其他指定函数依赖的方法.