函数依赖理论
逻辑蕴涵
函数依赖集的闭包
- 令 F 为一个函数依赖集。则 F的闭包 是 被 F 逻辑蕴涵的所有函数依赖的集合
- 记作：F+
Armstrong公理（Armstrong’s axiom）
公理是科学的客观规律，不需要自己证明，直接用就行
Armstrong 公理
- 自反律（reflexivity rule）。若α为一个属性集，且β⊆α， 则α→β
- 举个栗子：(A, B)→A
- 增补律（augmentation rule）。若α→β成立且γ为一属性集，则γα→γβ
- 举个栗子：(A, B)→C ==> (A, B, D, E)→(C, D, E)
- 传递律（transitivity rule）。若α→β和β→γ成立，则 α→γ 成立
- 举个栗子：A→B, B→C ==> A→C
- 自反律（reflexivity rule）。若α为一个属性集，且β⊆α， 则α→β
Armstrong公理是完备的，对于一个给定的函数依赖集F，通过Armstrong公理可以产生全部的F+
Armstrong公理的一些推论
可由Armstrong公理直接推得，也可以当做公理使用
- 合并律（union rule）。若α→β和α→γ成立，则α→βγ
- 举个栗子：A→B, A→C ==> A→(B, C)
- 分解律（decomposition rule）。若α→βγ成立，则α→β和α→γ成立
- 举个栗子：A→(B, C) ==> A→B, A→C
- 伪传递律（pseudotransitivity rule）。若α→β和γβ→δ成立，则αγ→δ成立
- 举个栗子：A→B, (B, C)→D ==> (A, C)→D
- 合并律（union rule）。若α→β和α→γ成立，则α→βγ
属性集的闭包
- 令α为一个属性集，我们将函数依赖集 F 下被α集合所函数确定的所有属性的集合为称为F下α的闭包
- 记作：α+
- 伪代码如下：
1
2
3
4
5
6
7result := α
repeat
for each 函数依赖 β→γ in F do
begin
if β ⊆ result then result := result ∪ γ
end
until(result 不变)
正则覆盖（极小函数依赖集）
- 如果去除函数依赖中的一个属性不改变函数依赖集的闭包，则称该属性是无关的
- F的正则覆盖 Fc 是一个依赖集，使得F逻辑蕴涵Fc 中的所有依赖，并且Fc 逻辑蕴涵F中的所有依赖。此外，Fc 必须具有如下性质 ：
- Fc 中任何函数依赖都不含无关属性
- Fc 中函数依赖的左半部都是唯一的。即Fc 中不存在两个依赖α1→β1和α2→β2， 满足α1=α2
无损分解
- 如果用两个关系模式r1(R)和r2(R)替代r(R)时没有信息损失，则我们称该分解时无损分解（lossless decomposition）
SQL 表示
1
2
3-- 下面查询的结果与r具有相同结果的元组集
SELECT *
FROM r1 natural join r2关系代数表示：
- ∏R1(r) ⋈ ∏R2(r) = r
分解算法（下回分解）
