先吐槽一下,,最近上数据库的课,属于是越来越懵了。尤其是范式理论这章我属实是懵了。课本排版好乱,属实是很难蚌得住。

好了,吐槽完毕,开始正文。

无损分解和有损分解

无损分解的定义是,将关系模式R分解为R1和R2,用R1和R2去替代R的时候没有信息的丢失,那么这个分解就是无损分解。

这个定义说了和没说一样,下面这样理解会好很多:

对于关系r,把关系模式R分解之后,如果把r投影到R1和R2上,然后把结果进行自然连接,就能得到一模一样的r,那么分解就是无损的。如果得到的结果不一样了,是r的超集,那就是有损分解了。

换个角度来看,如果以下SQL语句

select *
from (select R1 from r)
natural join
(select R2 from r);

的结果和

select * from (select R from r);

的结果相同,那么这个分解就是无损分解。

用关系代数表示则是:

无损分解的充分条件

补充资料:超码是能够唯一标识整个元组的属性集。

无损分解的充分条件是:

对于关系R、分解后的R1和R2,以及关系满足的函数依赖F,如果R1∩R2要么是R1的超码,要么是R2的超码,那么这个分解就是无损分解。

换句话说,如果以下关系至少一个在F的闭包F+中,那么这个分解就是无损分解:

  • R1∩R2 -> R1
  • R1∩R2 -> R2

函数依赖理论

基本概念

对于r(R)的一个实例,如果对于该实例中的所有元组对t1、t2,使得如果t1[α]=t2[α],t1[β]=t2[β]也成立,那么就称这个实例满足函数依赖α -> β

接着,如r(R)的每个实例都满足函数依赖α -> β,那么就称函数依赖在模式r(R)上成立。

什么叫做“平凡的”函数依赖?

平凡的函数依赖被所有关系满足,比如,关系 A->A 被包含属性A的所有关系满足。

一般地说,如果β是α的子集,那么形如α->β的函数依赖就是平凡的。

函数依赖集的闭包

用F+表示函数依赖F的闭包,也就是从给定的函数依赖集合F能推导出的所有函数依赖的集合。

F+是被F所逻辑蕴涵的所有函数依赖的集合。

一些公理

阿姆斯特朗公理

除了阿姆斯特朗公理以外,还有3条附加的规则,也是有效的

属性集的闭包

如果α -> B 那么就称属性B被α函数决定(functionally determine).

它的用处有:

无关属性

无关属性的定义是:如果去除函数依赖的一个属性而不改变函数依赖集的闭包,那么这个属性就是无关的。

无关属性的形式化的定义大概是下面这样

我尝试计算之后发现,上面的通俗的讲就是,如果把属性从函数依赖的右侧移除,那么就要证明F逻辑蕴含了F’。

换句话说,对于a->bc,从右侧移除b后,要证明b是无关属性,也就是要证明F里面的函数依赖能推出a->c

同样的,对于左侧移除,就是要证明F’逻辑蕴含了F。

正则覆盖

F的正则覆盖Fc是这样的一个依赖集:F蕴涵了Fc中的所有依赖,反之也是一样。

此外,Fc必须具有以下性质:

  • Fc中任何函数依赖都不包含无关属性
  • Fc中每个函数依赖的左侧都是唯一的。

计算正则覆盖

BC范式

BC范式是很严格的一种范式,它的定义如下:

对于F+中的所有形如α->β的函数依赖,至少有下面一项成立:

BC范式消除了基于函数依赖能够发现的所有的冗余

BCNF分解

对于不属于BCNF的模式R,至少存在一个非平凡的函数依赖α->β使得α不是R的超码。

分解的方法就是,用下面这两个模式去取代R

不断重复直到最终得到的所有模式都满足BCNF就行了。

怎么检测一个模式是不是BCNF?

对于非平凡的函数依赖α->β,计算α是不是R的超码,如果是,就不违反BCNF,否则违反BCNF

第三范式

第三范式比BCNF要宽松一点。对于F+中的所有形如α->β的函数依赖,至少有下面一项成立:

其实就是比BCNF多了一条规则而已。

这里第三个条件的意思是,β-α中的每个属性A可能包含于不同的候选码中

3NF分解算法

3NF的分解算法有点复杂而且计算量比较大。整合起来就是这样子的:

总的来说可以分为两个大部分:

  1. 计算正则覆盖
  2. 计算候选码

在做作业题目的时候,要求做3NF分解,可是发现计算量太大了,很难顶。于是想到一个取巧的办法:

先计算BCNF,然后把一些冗余的依赖加到模式之中,就成为了3NF的分解了…感觉这个方法有点取巧,不是很推荐使用。

转载请注明原文:https://longjin666.cn/?p=1429

欢迎关注我的公众号“灯珑”,让我们一起了解更多的事物~

你也可能喜欢

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注