Boyce-Codd范式的判定与分解

Decision and Decomposition of Boyce-Codd Normal Form

给定关系模式R和函数依赖集F，当X为R的一个真子集时，判定X关于F是否为Boyce－Codd范式（以下简记为BCNF）是NP完全的．这一问题的难点在于F在X上投影的计算，本文给出了计算函数依赖集投影的一个实用算法，将其用于BCNF的判定，并在此基础上建立了BCNF的一个无损分解算法．

Given a relation scheme R with function dependencies F, and X is a subset of R,it is NP-hard to decide whether X is in BCNF or not with respect to F. The reason is that we can not compute the F's project to X in polynomial-time. In this paper, a practical algorithm to compute the F's project to X is presented. Then it is employed to the decision of BCNF.Finally, based on the efficient computation of the project of functional dependencies, a practical algorithm of the lossless-join decomposition into BCNF is presented.