Authors: Daniel J. Rosenkrantz, Lin Yu
Tags: 1993, conceptual modeling
A paradigm is proposed for representing hierarchically specified design data in CAD database systems where there are to be alternate expansions of hierarchically specified modules. The paradigm uses an ancestor-based scheme to control which instances of submodules are to be placed in the expansion of each instance of a given module, and is formalized via a model that we call a versioned directed acyclic multigraph (VDAG). The approach is aimed at reducing storage space in engineering design database systems, and providing a means for designers to specify alternate expansions of a module. The VDAG model is defined, and a mechanism whereby a VDAG generates an exploded forest of design trees is described. Algorithms are provided which generate a design forest from a given VDAG, determine whether one module is contained by a larger module, extract a version from a VDAG, test whether two VDAG’s are equivalent, and try to reduce the size of a VDAG. The problems of module containment and VDAG inequivalence are shown to be NPcomplete; and the problem of finding a minimum sized VDAG equivalent to a given VDAG is shown to be NP-hard.Read the full paper here: https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=219741
