关系模式分解算法与数据库索引设计优化

前面已经讨论了函数依赖、多值依赖、无损连接与函数依赖保持性等基本理论，现在讨论关系范式规范化方法，即对一个关系模式如何进行分解并应该达到什么样的范式要求？

在对关系模式进行规范之前，需要对该模式进行分类。在分析用户要求之后，根据需求分析的结果将关系模式一共分为两类：一类为静态关系模式，在这类关系模式中，在数据加载的过程中，用户只能进行查询操作，而不能进行其他的操作；另一类为动态关系模式，在这类关系模式中，需要不断地进行插入操作、删除操作与更新操作。

在静态关系模式中，存在第一范式即可，也可以用更高的范式；但是在动态关系模式中，要想保证数据在操作过程中不会出现异常，最少要有第三范式。因此，我们只对3NF及之上的范式分解算法进行研究。

（一）分解的基本要求

分解后的关系模式与分解前的关系模式相等，即分解必须具有无损连接性和函数依赖保持性。

（二）目前分解算法的研究结论

1.若要求分解具有无损连接性，那么分解一定可以达到BCNF。

2.若要求分解具有函数依赖保持性，那么分解可以达到3 N F，但不一定能达到BCNF。

3.若要求分解既具有函数依赖保持性，又具有无损连接性，那么分解可以达到3NF，但不一定能达到BCNF。

（三）面向3NF且具有函数依赖保持性的分解

1.3NF的函数依赖保持性分解算法

输入：关系模式R∈1NF，R的属性集合U，F是R的函数依赖集，G是F的最小函数依赖集。

输出：R的函数依赖保持性的分解中，每一个关系模式是关于F在其上投影的3NF。

算法实现如下。

（1）对不出现在F中的任何一个函数依赖的属性A，构造一个关系模式R（A），并将属性A从关系模式R中消去。

（2）如果F中有一个函数依赖X→A，且X∪A＝U，则关系模式R不用分解，算法终止。

（3）对F中的每一个函数依赖X→A，构造一个关系模式R（X，A）。如果X→A1，X→A2，…，X→An均属于F，则构造一个关系模式R（X，A1，A2，…，An）。

2.3NF分解算法

输入：关系模式R，R的属性集合U和最小函数依赖集F。

输出：具有函数依赖保持性和无损连接性的解，r中所有关系模式都是3NF。(www.xing528.com)

算法实现如下。

（1）调用算法产生R的分解ρ＝｛R1，R2，…，Rn｝。

（2）构造分解T＝｛R1，R2，…，Rn，Rk｝，其中，R是由R的一个候选键K构成的关系。

（四）面向BCNF且具有无损连接性的分解

目前尚没有具有函数依赖保持性的BCNF分解算法，下面仅给出具有无损连接性的分解算法。

1.具有无损连接性的BCNF分解

输入：关系模式R及其函数依赖集F输出，R的一个无损连接分解，其中每一个子关系模式都满足F在其上投影的BCNF。

算法实现如下。

反复运用逐步分解定理，逐步分解关系模式R，使得每次分解都具有无损连接性，而且每次分解出来的子关系模式至少有一个是属于BCNF的。

（1）置初值ρ＝{R}。

（2）检查ρ中的关系模式，如果均属于BCNF，则转到步骤（4）。

（3）在ρ中找出不属于BCNF的关系模式S，那么必有X→A∈F+，A不包含于X，且X不是S的关键字。因此，XA必不包含S的全部属性。把S分解为｛S1，S2}，其中，S1＝XA，S2＝（S-A）X，并以｛S1，S2｝代替ρ中的S，返回到步骤（2）。

（4）终止分解，输出ρ。

2.存在两个问题算法

（1）分解结果不唯一。

分解要结合语义和实际应用来考虑。

（2）分解不保证具有函数依赖保持性。

在分解后，各模式的函数依赖的并集中没有逻辑蕴涵。