Representability of Design Objects by Ancestor-Controlled Hierarchical Specifications.
Lin Yu, Daniel J. Rosenkrantz:
Representability of Design Objects by Ancestor-Controlled Hierarchical Specifications.
PODS 1990: 28-39@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}
}
BibTeX
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.
Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98.
and ...
Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings.
and ...
BibTeX
Printed Edition
Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee.
ACM Press 1990, ISBN 0-89791-352-3
Contents BibTeX
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
- Lin Yu, Daniel J. Rosenkrantz:
Ancestor Controlled Submodule Inclusion in Design Databases.
IEEE Trans. Knowl. Data Eng. 5(2): 352-362(1993)
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:58 2009