Representability of Design Objects by Ancestor-Controlled Hierarchical Specifications.

@inproceedings{DBLP:conf/pods/YuR90,
  author    = {Lin Yu and
               Daniel J. Rosenkrantz},
  title     = {Representability of Design Objects by Ancestor-Controlled Hierarchical
               Specifications},
  booktitle = {Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee},
  publisher = {ACM Press},
  year      = {1990},
  isbn      = {0-89791-352-3},
  pages     = {28-39},
  ee        = {http://doi.acm.org/10.1145/298514.298539, db/conf/pods/YuR90.html},
  crossref  = {DBLP:conf/pods/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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.

Copyright © 1990 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[BK]

Don S. Batory, Won Kim: Modeling Concepts for VLSI CAD Objects. ACM Trans. Database Syst. 10(3): 322-346(1985) BibTeX

[DL]

Klaus R. Dittrich, Raymond A. Lorie: Version Support for Engineering Database Systems. IEEE Trans. Software Eng. 14(4): 429-437(1988) BibTeX

[FM]

Christopher W. Fraser, Eugene W. Myers: An Editor for Revision Control. ACM Trans. Program. Lang. Syst. 9(2): 277-295(1987) BibTeX

[GJ]

M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX

[Hec]

Paul Heckel: A Technique for Isolating Differences Between Files. Commun. ACM 21(4): 264-268(1978) BibTeX

[HM]

...

[Kat]

...

[KB]

...

[KL]

Randy H. Katz, Tobin J. Lehman: Database Support for Versions and Alternatives of Large Design Files. IEEE Trans. Software Eng. 10(2): 191-200(1984) BibTeX

[Knu]

Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
BibTeX

[Roc]

Marc J. Rochkind: The Source Code Control System. IEEE Trans. Software Eng. 1(4): 364-370(1975) BibTeX

[SL]

Dennis G. Severance, Guy M. Lohman: Differential Files: Their Application to the Maintenance of Large Databases. ACM Trans. Database Syst. 1(3): 256-267(1976) BibTeX

[Tic]

Walter F. Tichy: RCS - A System for Version Control. Softw., Pract. Exper. 15(7): 637-654(1985) BibTeX

[U]

...

[VHDL]

...

[YR1]

Lin Yu, Daniel J. Rosenkrantz: Minimizing Time-Space Cost For Database Version Control. PODS 1988: 294-301 BibTeX

[YR2]

...

Referenced by

1. Lin Yu, Daniel J. Rosenkrantz: Ancestor Controlled Submodule Inclusion in Design Databases. IEEE Trans. Knowl. Data Eng. 5(2): 352-362(1993)