An Algorithm for Determining Minimal Reduced-Coverings of Acyclic Database Schemes  

作　　者：刘铁英 叶新铭 

机构地区：[1]DepartmentofComputerScience,InnerMongoliaUniverisyt,InnerMongolia010021 [2]DepartmentofComputerScience,I

出　　处：《Journal of Computer Science & Technology》1996年第4期347-355,共9页计算机科学技术学报（英文版）

摘　　要：This paper reports an algorithm (DTV) for deterdring the minimal reducedcovering of an acyclic database scheme over a specified subset of attributes. The output of this algorithm contains not only minimum number of attributes but also minimum number of partial relation schemes. The algorithm has complexity O(|N|·|E|2), where |N| is the number of attributes and |E| the number of relation schemes- It is also proved that for Berge, γ orβ acyclic database schemes, the output of algorithm DTV maintains the acyclicity correspondence.This paper reports an algorithm (DTV) for deterdring the minimal reducedcovering of an acyclic database scheme over a specified subset of attributes. The output of this algorithm contains not only minimum number of attributes but also minimum number of partial relation schemes. The algorithm has complexity O(|N|·|E|2), where |N| is the number of attributes and |E| the number of relation schemes- It is also proved that for Berge, γ orβ acyclic database schemes, the output of algorithm DTV maintains the acyclicity correspondence.

关 键 词：Acyclic database scheme minimal  reduced-covering HYPERGRAPH 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]