-
Notifications
You must be signed in to change notification settings - Fork 32
/
3、函数依赖.md
191 lines (104 loc) · 8.08 KB
/
3、函数依赖.md
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
### 函数依赖
#### 概述
函数依赖
* 设R(U)是属性集合U={A1,A2,...,An}上的一个关系模式，X, Y是U上的两个子集，若对R(U)的任意一个可能的关系r, r中不可能有两个元组满足在X中的属性值相等而在Y中的属性值不等，则称“X函数决定Y”或“Y函数依赖于X”, 记作X $\rightarrow$Y。
* 示例：
* U={学号，姓名，年龄，班号，班长，课号，成绩}
* 学号$\rightarrow${姓名，年龄}
* 班号$\rightarrow$班长
* {学号，课号}$\rightarrow$成绩
* 通过表格来看
* 注：函数依赖的分析取决于对问题领域的限定和分析，取决于对业务规则的正确理解。
* 例如：问题领域中，学生是没有重名的，则有：“年龄”和“家庭住址”都函数依赖于 “姓名”。而在另一个问题领域中，学生是有重名的，则上述函数依赖是不成立的。
函数依赖的特性
* 对X$\rightarrow$Y，但Y $\notin$X, 则称X$\rightarrow$Y为非平凡的函数依赖；
* 若X$\rightarrow$Y，则任意两个元组，若X上值相等，则Y上值必然相等,则称X为决定因素；
* 若X$\rightarrow$Y ，Y$\rightarrow$X, 则记作X$\leftrightarrow$Y；
* 若Y不函数依赖于X，则记作X $\nrightarrow$ Y；
* X$\rightarrow$Y，有基于模式R的，则要求对任意的关系r成立；有基于具体关系r的，则要求对某一关系r成立；
* 如一关系r的某属性集X, r中根本没有X上相等的两个元组存在，则X$\rightarrow$Y恒成立；
#### 完全与传递
部分或完全函数依赖
* 在R(U)中，若X$\rightarrow$Y并且对于X的任何真子集X'都有X不依赖：X$\nrightarrow$ Y, 则称Y完全函数依赖于X, 记为：X完全依赖：X $\rightarrow^f$ Y, 否则称Y部分函数依赖于X, 记为：X$\rightarrow^p$ Y
* 示例：
* U={学号，姓名，年龄，班号，班长，课号，成绩}
* {学号，课号}$\rightarrow^f$ U
* {学号，课号}$\rightarrow^p$姓名
* {学号，课号}$\rightarrow^f$成绩
* 员工(员工码,姓名,出生日期,联系电话, 最后学历,毕业学校,培训日期,培训内容)
* {员工码,培训日期}$\rightarrow^f$U;
* {员工码,培训日期}$\rightarrow^p$ {姓名,出生日期}；
传递函数依赖
* 在R(U)中，若X$\rightarrow$Y，Y$\rightarrow$Z 且Y$\notin$X, Z$\notin$Y,Z$\notin$X, Y$\nrightarrow$X, 则称Z传递函数依赖于X。
* 示例
* U={学号，姓名，年龄，班号，班长，课号，成绩}
* 学号$\rightarrow$班号 ；班号$\rightarrow$班长
* 即：学号$\rightarrow$班长
* 注：“班长”是传递依赖于“学号”的。
* 学生(学号，姓名，系号，系主任)
* 学号$\rightarrow$系号； 系号$\rightarrow$系主任
* 即：学号$\rightarrow$系主任
* 注：“系主任”是传递依赖于“学号”的。
#### 其余概念
候选键
* 设K为R(U)中的属性或属性组合，若K $\rightarrow^f$ U, 则称K为R(U)上的候选键(Candidate Key)。
* 说明：
* 可任选一候选键作为R的主键(Primary Key)；
* 包含在任一候选键中的属性称主属性(Prime Attribute),其他属性称非主属性；
* 若K是R的一个候选键，K$\in$S, 则称S为R的一个超键(Super Key)。
外来键
* 若R(U)中的属性或属性组合X并非R的候选键，但X却是另一关系的候选键，则称X为R的外来键(Foreign Key)，简称外键。
* 示例：R={合同号，合同名，签订日期，`供应商名`}、S={`供应商名`，地址，执照号，法人代表}
* 合同号 $\rightarrow^f$ {合同号，合同名，签订日期，`供应商名`}
* 供应商名 $\rightarrow^f$ {`供应商名`，地址，执照号，法人代表}
逻辑蕴涵
* 设F是关系模式R(U)中的一个函数依赖集合，X, Y是R的属性子集，如果从F中的函数依赖能够推导出X $\rightarrow$Y，则称F逻辑蕴涵X $\rightarrow$Y, 或称X $\rightarrow$Y是F的逻辑蕴涵。记作F $\vDash$ X $\rightarrow$Y。
* 说明：
* 设F是关系模式R(U)的函数依赖集, X $\rightarrow$Y是一个函数依赖，若对R中的每个满足F的关系r, 能够用形式逻辑推理的方法推出r也满足X $\rightarrow$Y，则称F $\vDash$ X $\rightarrow$Y。
* 若满足F的每个关系均满足X $\rightarrow$Y，则说F逻辑蕴涵X $\rightarrow$Y；
闭包
* 被F逻辑蕴涵的所有函数依赖集合称为F的闭包(Closure)，记作$F^+$。
* 说明：
* 若$F^+$=F, 则说F是一个全函数依赖族(函数依赖完备集)。
* 示例：设R=ABC,F={AB,BC},则F+的组成如下（即还可推出如下依赖关系）
* (1) X包含A,而Y任意：如ABC$\rightarrow$AB,A$\rightarrow$C,AB$\rightarrow$BC,...
* (2) X包含B,但不含A, 且Y不含A：如BC$\rightarrow$B,B$\rightarrow$C,B$\rightarrow$ $\emptyset$ ,...
* (3)X $\rightarrow$ Y是C $\rightarrow$ C或C$\rightarrow$$\emptyset$
#### 公理和定理
[Armstrong公理] 设R(U)是属性集U={A1,A2,...,An}上的一个关系模式，F为R(U)的一组函数依赖，记为R(U, F), 则有如下规则成立：
* [A1]自反律(Reflexivity rule)：若Y$\subseteqq$X$\subseteqq$U, 则X$\rightarrow$Y被F逻辑蕴涵。
* [A2]增广律(Augmentation rule)：若X$\rightarrow$Y$\in$F, 且Z$\subseteqq$U, 则XZ $\rightarrow$YZ被F逻辑蕴涵。
* [A3]传递律(Transtivity rule)：若X$\rightarrow$Y$\in$F, 且Y $\rightarrow$Z, 则X $\rightarrow$Z被F逻辑蕴涵
[引理] 还可推出如下结论：
* (a) 合并律(Union Rule)：若X $\rightarrow$Y且X $\rightarrow$Z, 则X $\rightarrow$YZ。
* (b) 伪传递律(Pseudo Transitivity)：若X $\rightarrow$Y且WY $\rightarrow$Z, 则XW $\rightarrow$Z。
* (c) 分解律(Decomposition Rule)：若X $\rightarrow$Y且Z$\subseteqq$Y, 则X$\rightarrow$Z。
属性(集)闭包
* 对R(U, F), X$\subseteqq$U, U = { A1,A2,...,An}, 令：$X^+_F$= { Ai | 用 A1,A2,A3可从F导出X$\rightarrow$Ai} 称$X^+_F$为X关于F的属性(集)闭包。
* 注：显然X$\subseteqq$$X^+_F$。
计算一属性集关于一组函数依赖的属性闭包。
* Input：有限属性集合U, U上的函数依赖集合F, 及U的子集X
* Output：X关于F的属性闭包X+, 记为$X^+_F$。
* Method：按下列规则递归计算属性序列X(0), X(1),...
1. 令X(0)=X, i=0
2. B = {A | ($\exists$V)($\exists$W)(V$\rightarrow$W$\in$F $\wedge$ V$\subseteqq$X(i) $\wedge$ A$\subseteqq$W)}
3. X(i+1)=B$\bigcup$X(i)
4. If X(i+1) $\neq$X(i) then i=i+1;goto 2.
5. $X^+_F$= X(i), 算法终止。
* 示例：已知 R(U, F), U={A, B, C, D, E}, F={AB$\rightarrow$C, B$\rightarrow$D, C$\rightarrow$E, EC$\rightarrow$B, AC$\rightarrow$B}。 求：$(AB)^+_F$
* (1) X(0) ={A, B}
* (2) 由AB$\rightarrow$C, B$\rightarrow$D：X(1) = X(0) $\bigcup$ {C, D} = {A, B, C, D}
* (3) 由C$\rightarrow$E, AC$\rightarrow$B：X(2) = X(1) $\bigcup$ { E }= {A, B, C, D, E}
* (4) 由EC$\rightarrow$B：X(3) = X(2) $\bigcup$ $\emptyset$= {A, B, C, D, E}
* (5) 因为X(3) = X(2)，所以$(AB)^+_F$ = {A, B, C, D, E}。
#### 最小覆盖
覆盖(Cover)
* 对R(U)上的两个函数依赖集合F、G, 如果$F^+$= $G^+$，则称F和G是等价的，也称F覆盖G或者G覆盖F。
* [引理]：$F^+$= $G^+$ $\leftrightarrow$ F$\subseteqq$ $G^+$ $\wedge$ G$\subseteqq$$F^+$
[定理]：每个函数依赖集F可被一个其右端至多有一个属性的函数依赖之集G覆盖。
[引理]：最小覆盖若F满足以下条件，则称F为最小覆盖(minimal Cover)或最小依赖集(minimal set of Functional Depandency)：
* 1) F中每个函数依赖的右部是单个属性；
* 2) 对任何X $\rightarrow$A$\in$F, 有F $-${ X $\rightarrow$A }不等价于F；
* 3) 对任何X $\rightarrow$A$\in$F, Z$\subset$X, ( F$-${ X $\rightarrow$A }) $\bigcup$ {Z $\rightarrow$A}不等价于F。
[定理]：每个函数依赖集F都有等价的最小覆盖F'。