东华大学学报（英文版）2026，Vol.43Issue(4)：92-101,10.DOI:10.19884/j.1672-5220.202504018
基于F-based推导树的主属性识别算法
Recognizing Prime Attributes Based on F-based Derivation Tree
于晓雪 1刘国华 1徐雨露 1刘长奇 1张丽萌 1朱东燕 1何松达1
作者信息
- 1. 东华大学 信息与智能科学学院,上海 201620
- 折叠
摘要
Abstract
Although the prime attribute problem is nondeterministic polynomial-time complete(NP-complete),the difficulty of determining whether an attribute is prime is related to how the attribute appears in the set of functional dependencies(FDs).The prime attribute problem is extensively studied based on the occurrence of an attribute in the set of FDs.First,in a relation scheme R(U,F),the attribute set U is partitioned into four distinct subsets according to where attributes in U appear in F:U1(attributes appearing exclusively on the left-hand sides of FDs in F),U2(attributes appearing exclusively on the right-hand sides of FDs in F),U3(attributes appearing on both sides of FDs in F),and U4(attributes not appearing in any FD in F).Second,the occurrence patterns of attributes in the set of FDs are mapped to an F-based derivation tree(F-based DT)forest,and the features of attributes in U1,U2,U3 or U4 are shown in the F-based DT forest.Then,an algorithm for recognizing prime attributes based on F-based DT is proposed.Finally,the following conclusions are obtained:when an attribute belongs to U3,the prime attribute problem is NP-complete;when an attribute belongs to U1,U2,or U4,the problem is in polynomial-time complexity class(P-class),meaning it can be efficiently solved in polynomial time.Compared with traditional methods,the proposed algorithm can simplify the process for recognizing prime attributes significantly,and improve database normalization.关键词
F-based推导树/主属性/NP完全/规范化Key words
F-based derivation tree/prime attribute/NP-complete/normalization分类
信息技术与安全科学引用本文复制引用
于晓雪,刘国华,徐雨露,刘长奇,张丽萌,朱东燕,何松达..基于F-based推导树的主属性识别算法[J].东华大学学报（英文版）,2026,43(4):92-101,10.
