关系分解的无损连接性与教师关系优化

（一）进行关系分解的必要性

一个关系模式分解后，可以存放原来所不能存放的信息，通常称为悬挂元组。这是实际所需要的，也是分解的优点。在做自然连接时，这类悬挂元组自然丢失了，但不是信息的丢失，而是在合理范围内的丢失。例如下面的选课关系r分解成班级关系和教师关系后，教师关系可以存放其他信息，但进行连接后，mp（r）仍保持无损连接性。

（二）判别一个分解的无损连接性的算法

设关系模式R（A1，A2，…，An），F为它的函数依赖集，P＝（R1，R2， …，Rn）为R的一个分解。

判别一个分解的无损连接性的算法如下。(www.xing528.com)

1.构造初始表：构造一个k行n列的初始表，其中每列对应于R的一个属性，每行用于表示分解后的一个模式组成。如果属性A属于关系模式Ri，则在表的第i行第j列置符号aj，否则置符号bij。

2.根据F中的函数依赖修改表内容：考察表中的每个函数依赖X→Y，在属性组X所在的那些列上寻找具有相同符号的行，如果看到这样的两行或更多的行，就修改这些行，使这些行上属性组Y所在的列上元素相同。修改规则：如果属性组Y所在的要修改的行中有一个为aj，则这些元素均变成aj，否则改动为bmj（其中，m为这些行的最小行号）。

注意：若某个bij被改动，则该列中凡是与b相同的符号均做相同的改动。我们将循环地对F中的函数依赖逐个进行处理，直到发现表中有一行变为a1，a2，…，an或不能再被修改为止。

3.判断分解是否为无损连接的：如果通过修改，发现表中有一行变为a1，a2，…，an则分解是无损连接的，否则此分解不具有无损连接性。