摘要
传统的关系模式的BCNF分解算法必须判断“一个关系模式是否为BCNF”,该判断是一个NP-完全问题,因此传统算法缺乏实用性.本文避免这一判断,给出一个关系模式的BCNF分解的新算法,它的时间复杂性是O(kn^2)级的,其中n为模式中的属性个数,K为产生的模式个数.
The traditional algorithm for decomposing a relation scheme into BCNF with a lossless join must determine whether a relation scheme is in BCNF. Unfortunately, it has been proved that the determination is NP-complete. In the present paper this determination is evaded and an algorithm of transforming a relation scheme into BCNF with a lossless join is given. The algorithm can be computed in O ( kn2) where n is the number of attributes in the relation scheme and k is the number of relation schemes which are yielded in the decomposition.
出处
《云南大学学报（自然科学版）》
CAS
CSCD
1990年第2期133-139,共7页
Journal of Yunnan University(Natural Sciences Edition)
