首页|期刊导航|东华大学学报(英文版)|基于F-based推导树的主属性识别算法

基于F-based推导树的主属性识别算法OA

Recognizing Prime Attributes Based on F-based Derivation Tree

中文摘要英文摘要

尽管主属性问题是非确定性多项式时间完全(nondeterministic polynomial-time,NP-complete)问题,但判断一个属性是否为主属性的难度与该属性在函数依赖集中的出现方式密切相关.本文根据属性在函数依赖集中出现的特征对主属性问题进行深入研究.首先,在关系模式 R(U,F)中,根据属性在函数依赖集 F 中的出现情况,将属性集 U 划分为四个子集:U1(仅出现在 F 左部的属性)、U2(仅出现在 F 右部的属性)、U3(同时出现在 F 左右部的属性)和 U4(在 F 中未出现的属性).其次,将属性在函数依赖集中的出现情况映射到基于函数依赖的推导树(F-based derivation tree,F-based DT)森林,在 F-based DT森林展示出在 U1、U2、U3 或 U4 中属性的特征.再次,提出了一种基于 F-based DT 的主属性识别算法.最后,得出以下结论:当属性属于U3 时,主属性判定问题是NP 完全;当属性属于U1、U2 或U4 时,该问题属于多项式时间类(polynomial-time complexity class,P-class),即可以在多项式时间内高效求解.相较于传统方法,本文提出的算法能够显著地简化主属性的识别过程,并促进数据库规范化.

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.

于晓雪;刘国华;徐雨露;刘长奇;张丽萌;朱东燕;何松达

东华大学 信息与智能科学学院,上海 201620东华大学 信息与智能科学学院,上海 201620东华大学 信息与智能科学学院,上海 201620东华大学 信息与智能科学学院,上海 201620东华大学 信息与智能科学学院,上海 201620东华大学 信息与智能科学学院,上海 201620东华大学 信息与智能科学学院,上海 201620

信息技术与安全科学

F-based推导树主属性NP完全规范化

F-based derivation treeprime attributeNP-completenormalization

《东华大学学报(英文版)》 2026 (4)

92-101,10

10.19884/j.1672-5220.202504018

评论