ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

On Designing Database Schemes Bounded or Constant-time-maintainable with respect to Functional Dependencies.

Edward P. F. Chan, Héctor J. Hernández: On Designing Database Schemes Bounded or Constant-time-maintainable with respect to Functional Dependencies. PODS 1987: 48-57
@inproceedings{DBLP:conf/pods/ChanH87,
  author    = {Edward P. F. Chan and
               H{\'e}ctor J. Hern{\'a}ndez},
  title     = {On Designing Database Schemes Bounded or Constant-time-maintainable
               with respect to Functional Dependencies},
  booktitle = {Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, March 23-25, 1987, San Diego,
               California},
  publisher = {ACM},
  year      = {1987},
  isbn      = {0-89791-223-3},
  pages     = {48-57},
  ee        = {http://doi.acm.org/10.1145/28659.28664, db/conf/pods/ChanH87.html},
  crossref  = {DBLP:conf/pods/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Under the weak instance model, to determine if a class of database schemes is bounded with respect to dependencies is fundamental for the analysis of the behavior of the class of database schemes with respect to query processing and updates. However, proving that a class of database schemes is bounded with respect to dependencies seems to be very difficult even for restricted cases. To resolve this problem, we need to develop techniques for characterizing bounded database schemes. In this paper, we give a formal methodology for designing database schemes bounded with respect to functional dependencies using a new technique called extensibility. This methodology can also be used to design constant-time-maintainable database schemes.

Copyright © 1987 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 Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 23-25, 1987, San Diego, California. ACM 1987, ISBN 0-89791-223-3
Contents BibTeX

Online Edition: ACM Digital Library

References

[ABU]
Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Databases. ACM Trans. Database Syst. 4(3): 297-314(1979) BibTeX
[AtC]
Paolo Atzeni, Edward P. F. Chan: Efficient Query Answering in the Representative Instance Approach. PODS 1985: 181-188 BibTeX
[BV]
Catriel Beeri, Moshe Y. Vardi: A Proof Procedure for Data Dependencies. J. ACM 31(4): 718-741(1984) BibTeX
[C]
Edward P. F. Chan: Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions. SIGMOD Conference 1984: 149-163 BibTeX
[CH1]
Edward P. F. Chan, Héctor J. Hernández: On the Desirability of gamma-Acyclic BCNF Database Schemes. ICDT 1986: 105-122 BibTeX
[CH2]
Edward P. F. Chan, Héctor J. Hernández: Testing Unboundedness of Database Schemes and Functional Dependencies. Inf. Process. Lett. 28(6): 317-326(1988) BibTeX
[DM]
...
[GM]
...
[GMV]
Marc H. Graham, Alberto O. Mendelzon, Moshe Y. Vardi: Notions of dependency satisfaction. J. ACM 33(1): 105-129(1986) BibTeX
[GW]
Marc H. Graham, Ke Wang: Constant Time Maintenance or The Triumph of the fd. PODS 1986: 202-216 BibTeX
[GY]
Marc H. Graham, Mihalis Yannakakis: Independent Database Schemas. J. Comput. Syst. Sci. 28(1): 121-141(1984) BibTeX
[H]
Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982) BibTeX
[IIK]
Minoru Ito, Motoaki Iwasaki, Tadao Kasami: Some Results on the Representative Instance in Relational Databases. SIAM J. Comput. 14(2): 334-354(1985) BibTeX
[M]
Alberto O. Mendelzon: Database States and Their Tableaux. ACM Trans. Database Syst. 9(2): 264-282(1984) BibTeX
[MMS]
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX
[MRW]
David Maier, David Rozenshtein, David Scott Warren: Windows on the World. SIGMOD Conference 1983: 68-78 BibTeX
[MUV]
David Maier, Jeffrey D. Ullman, Moshe Y. Vardi: On the Foundations of the Universal Relation Model. ACM Trans. Database Syst. 9(2): 283-308(1984) BibTeX
[S1]
Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120 BibTeX
[S2]
Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983) BibTeX
[S3]
Yehoshua Sagiv: Evaluation of Queries in Independent Database Schemes. J. ACM 38(1): 120-161(1991) BibTeX
[U]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[V]
...
[Y]
Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 BibTeX

Referenced by

  1. Edward P. F. Chan, Héctor J. Hernández: Independence-reducible Database Schemes. PODS 1988: 163-173
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:50 2009