基于多重依赖关系的传递闭包研究及应用

Research and Application of Transitive Closure Based on Multi-Dependency Relationship

文中通过改进Warshall Folyd的算法,提出了一种依赖传递闭包算法和相应的动态闭包算法,其核心思想是依据依赖关系的分类和性质,定义关系矩阵和运算算子,使算法能解决选择依赖关系,并能表达直接、间接和选择三种依赖关系;同时,所提出动态算法能够运行时根据问题规模动态添加关系元素和依赖关系,解决在基本关系原则和部分关系集上求取闭包的问题。结合安全通用标准CC中关于组件间依赖关系的规定,给出了本文所提出算法的一个实际应用,表明算法取得了很好的效果。

A dependency transitive closure algorithm and the corresponding dynamic algorithm of it are proposed in this paper based on Warshall-Folyd algorithm. The core ideas of those algorithms can be described as follows. Above all,according to the classification and character of dependency relationship,matrix and operators of relationship are defined,which can clarify selective dependency relationship and also give a clear description to direct,indirect and selective dependency relationship. Moreover,dynamic closure algorithm represented in this paper can dynamically insert relationship elements and dependency relationships corresponding to problem scale during runtime,and resolve the transitive closure problem in the relationship principles and partial relationship aggregate. Finally,on the basis of component dependency relationship in the security Common Criteria (CC),an example of proposed algorithm is presented in this paper,which proves the algorithm feasible.