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

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 acyc…