Title :
Ancestor controlled submodule inclusion in design databases
Author :
Yu, Lin ; Rosenkrantz, Daniel J.
Author_Institution :
Dept. of Comput. Sci., State Univ. of New York, Albany, NY, USA
fDate :
4/1/1993 12:00:00 AM
Abstract :
A paradigm is proposed for representing hierarchically specified design data in CAD database systems in which there are 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 using a versioned directed acyclic multigraph (VDAG). The approach is aimed at reducing storage space in engineering design database systems and at providing a means for designers to specify alternate expansions of a module. The VDAG model is defined, and a mechanism by which a VDAG generates an exploded forest of design trees is described. Algorithms are provided to 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 VDAGs are equivalent, and try to reduce the size of a VDAG. The problems of module containment and VDAG inequivalence are shown to be NP-complete, and the problem of finding a minimum sized VDAG equivalent to a given VDAG is shown to be NP-hard
Keywords :
CAD; database management systems; graph theory; CAD database systems; NP-complete; VDAG; VDAG inequivalence; ancestor-based scheme; design trees; engineering design database systems; exploded forest; hierarchically specified design data; hierarchically specified modules; minimum sized VDAG; versioned directed acyclic multigraph; Algorithm design and analysis; Data engineering; Database systems; Design automation; Design engineering; Maintenance engineering; Spatial databases; Systems engineering and theory; Testing; Very large scale integration;
Journal_Title :
Knowledge and Data Engineering, IEEE Transactions on