空值环境下关系模式无损连接分解为(N)BCNF的必要条件和算法

Necessary Conditions and Algorithm for Decompositing Relational Schema under Null Value Circumstances into BCNF Without Loss Joins

对文献［１］提出的空值环境下关系模式无损连接分解为（Ｎ）ＢＣＮＦ的必要条件，给出二个反例，证明它是不正确的；并分别从关系模式的函数依赖集Ｆ的最小依赖集Ｆ′和闭包Ｆ＋ 出发，重新给出二个必要条件．另外，还给出二个空值环境下关系模式无损连接分解为（Ｎ）ＢＣＮＦ的算法．这二种算法均是进行二叉树搜索的算法．每次分解均是对非（Ｎ）ＢＣＮＦ的子式进行一分为二且无损连接的分解，由一个父结点得到二个子结点．若可能，就一层层分解下去，当不可能进行这样的分解时，就退回到它的父结点，然后尝试新的分解，如此反复进行，直到得到符合要求的结果（所有叶结点均为（Ｎ）ＢＣＮＦ）或输出无法分解的信息．其中一个算法较简便易行，但不能得到全部符合要求的分解，另一算法较复杂，但能得到全部符合要求的分解．

The necessary condition of decompositons for relational scheme under null value circumstances into BCNF without loss joins, which was presented in Ref.[1],is proved to be wrong. Two new necessary conditions are presented. They are given separately from the minimal set F′ and the Closure F + of the functional dependencies F of the relational scheme. Two algorithms for decomposing relational scheme under null value circumstances into BCNF without loss joins are given. These algorithms use binary tree for search. The scheme which is not in BCNF is decomposed into two subschemes without loss joins, and one can get one predecessor node and two successor nodes. If possible, one can construct the same decomposition again and again; Otherwise, one must back into its predeccessor node and try new decomposition. In the end, one can get the result that fits into the demand(all leaf nodes are (N)BCNF), or else, the information which showed that impossible to be decomposed is output. One algorithm is simple, yet it cannot get all possible decompositions which satisfy the demand. The other algorithm is more complex, but it can get all possible decompositions satisfying the demand.