Improving the Efficiency of Dependency Analysis in Logical Decision Models

To address the problem that existing software dependency extraction methods do not work on higher-level software artifacts, do not express decisions explicitly, and do not reveal implicit or indirect dependencies, our recent work explored the possibility of formally defining and automatically deriving a pairwise dependence relation from an augmented constraint networks (ACN) that models the assumption relation among design decisions. The current approach is difficult to scale, requiring constraint solving and solution enumeration. We observe that the assumption relation among design decisions for most software systems can be abstractly modeled using a special form of ACN. For these more restrictive, but highly representative models, we present an O(n³) algorithm to derive the dependency relation without solving the constraints. We evaluate our approach by computing design structure matrices for existing ACNs that model multiple versions of heterogenous real software designs, often reducing the running time from hours to seconds.