Representability of design objects by ancestor-controlled hierarchical specifications

ABSTRACT

A simple model, called a VDAG, is proposed for representing hierarchically specified design data in CAD database systems where there are to be alternate expansions of hierarchically specified modules. The model uses an ancestor-based expansion scheme to control which instances of submodules are to be placed within each instance of a given module. 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 expressive power of the VDAG model is investigated, and the set of design forests which are VDAG-generable is characterized. The problem of determining whether a given design forest is VDAG-generable is shown to be NP-complete, even when the height of the forest is bounded. However, it is shown that determining whether a given forest is VDAG-generable and producing such a VDAG if it exists, can be partitioned into a number of simpler subproblems, each of which may not be too computationally difficult in practice. Furthermore, for forests in a special natural class that has broad applicability, a polynomial time algorithm is provided that determines whether a given forest is VDAG-generable, and produces such a VDAG if it exists. However, we show that it is NP-hard to produce a minimum-sized such VDAG for forests in this special class, even when the height of the forest is bounded.

REFERENCES

• BK: D. S. Batory , Won Kim, Modeling concepts for VLSI CAD objects, ACM Transactions on Database Systems (TODS), v.10 n.3, p.322-346, Sept. 1985 [doi>10.1145/3979.4018]
• DL: Klaus R. Dittrich , Raymond A. Lorie, Version Support for Engineering Database Systems, IEEE Transactions on Software Engineering, v.14 n.4, p.429-437, April 1988 [doi>10.1109/32.4664]
• FM: Christipher W. Fraser , Eugene W. Myers, An editor for revision control, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.2, p.277-295, April 1987 [doi>10.1145/22719.22948]
• GJ: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• Hec: Paul Heckel, A technique for isolating differences between files, Communications of the ACM, v.21 n.4, p.264-268, April 1978 [doi>10.1145/359460.359467]
• HM: Hunt, J.W., and Mellroy, M.D., "An Algorithm for Differential File Comparison," Computer Science Technical Report 41, AT&T Bell Laboratories, Murray Hill, NJ, 1976
• Kat: Randy H. Katz, A database approach for managing VLSI design data, Proceedings of the 19th conference on Design automation, p.274-282, January 1982
• KB: Katz, R.H., Bhateja, R., Chang, E.E.L., Gedge, D., and Trijanto, V., "Design Version Management," IEEE Design & Test, Vol.4(1), pp. 12-22, Feb. 1987
• KL: Katz, R.H., and Lehman, T.J., "Database Support for Versions and Alternatives of Large Design Files," 1EEE Trans. on Software Engineering, Vol.SE-IO(2), pp.191- 200, March 1984
• Knu: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• Roc: Rochkind, M.J., "The Source Code Control System," 1EEE Trans. on Software Engineering, Vol.Se-l(4), pp.364-370, Dec. 1975
• SL: Dennis G. Severance , Guy M. Lohman, Differential files: their application to the maintenance of large databases, ACM Transactions on Database Systems (TODS), v.1 n.3, p.256-267, Sept. 1976 [doi>10.1145/320473.320484]
• Tic: Walter F. Tichy, RCS—a system for version control, Software—Practice & Experience, v.15 n.7, p.637-654, July 1985 [doi>10.1002/spe.4380150703]
• U: Unix User's Reference Manual, Dept. E.E. & Comp. Sei., UC Berkeley, CA, April 1986
• VHDL: VHDL Language Reference Manual, Draft Standard 1076/B, IEEE, May 1987
• YR1: Lin Yu , Daniel J. Rosenkrantz, Minimizing time-space cost for database version control, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.294-301, March 1988, Austin, Texas, United States [doi>10.1145/308386.308460]
• YR2: Yu, L., and Rosenkrantz, D.J., "Ancestor- Controlled Submodule Inclusion in Design Databases," Proc. Second International Conference on Data and Knowledge Systems for Manufacturing and Engineering, pp.28-37, Gaithersburg, MD, IEEE, Oct. 1989

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Design, Management, Performance, Theory, Verification