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 acyclicity correspondence.

一个识别四种非环数据库模式的算法

将数据库模式与线图的对应关系用于识别四种非环数据库模式，给出一个新的识别算法，该算法的特点是将数据库模式所对应的线图分解成若干个子线图，在每个子线图上同时执行非环性的识别运算，如果在其中某个子线图上算法失败，则数据库是环的，否则数据库是非环的．文中还将对算法进行可行性等理论分析．这里提出的方法的解决分布式环境中类似问题时有非常好的效果．

基于超图和线图的β环与其它环的关系

通过大量图例，以β环为中心，系统地讨论了基于超图的β环与纯环、β环与弱环、弱β环与γ环、β环与γ环的关系，以及基于线图的无β环与无α环、无β环与无α环之间的关系。

基于线图的无β环混合依赖分解条件及算法

无β环数据库模式具有很多优良的特性 ,以往的研究都局限在图论的范畴内 ,而没有考虑数据库的其他规范化特性 .在混合依赖基概念的基础上 ,定义了严格无冲突、扩展严格无冲突等概念 ,并证明了在混合环境下得出的无损联接、保持依赖、无 β环且满足 4 N F的分解的充要条件是 ,混合依赖集是扩展严格无冲突的 .据此 ,给出了判断严格无冲突及混合环境下无β环分解算法 ,并分析了算法时间的复杂度是线性的 .最后 ,给出基于线图的实例验证 .

决定非环性数据库模式的最小覆盖的算法

本文给出一个决定非环性数据库模式在某个指定的属性子集上的边最小覆盖算法，叫做ＭＣ－ＡＣＹＣＬＩＣ．该算法的时间复杂性为，其中｜Ｎ｜是给定的数据库模式中属性的个数和｜Ｅ｜是关系模式的个数．