| Boyce—Codd范式的判定与分解 |
| |
| 引用本文： | 朱扬勇,朱静.Boyce—Codd范式的判定与分解[J].复旦学报(自然科学版),1998,37(5):674-680. |
| |
| 作者姓名： | 朱扬勇 朱静 |
| |
| 作者单位： | [1]复旦大学 [2]同济大学 |
| |
| 摘 要： | 给定关系模式Ｒ和函数依赖集Ｆ，当Ｘ为Ｒ的一个真子集时，判定Ｘ关于Ｆ是否为Ｂｏｙｃｅ－Ｃｏｄｄ范式（以下简记为ＢＣＮＦ）是ＮＰ完全的，这一问题的难点在于Ｆ在Ｘ上投影的计算，本文给出了计算函数依赖集投影的一个实用算法，将其用于ＢＣＮＦ的判定，并在此基础上建立了ＢＣＮＦ的一个无损分解算法。
|
| 关 键 词： | 关系数据库 规范化 B－C范式 |
Decision and Decomposition of Boyce-Codd Normal Form |
| |
| Zhu Yangyong, Zhu Jing.Decision and Decomposition of Boyce-Codd Normal Form[J].Journal of Fudan University(Natural Science),1998,37(5):674-680. |
| |
| Authors: | Zhu Yangyong Zhu Jing |
| |
| Institution: | Zhu Yangyong; Zhu Jing(Fudan University ) (Tongji University) |
| |
| Abstract: | 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. |
| |
| Keywords: | relational database normalization Boyce-Codd normal form |
| 本文献已被 CNKI 维普 等数据库收录！ |
