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

Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation.

Ke Wang: Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation. SIGMOD Conference 1990: 74-83
@inproceedings{DBLP:conf/sigmod/Wang90,
  author    = {Ke Wang},
  editor    = {Hector Garcia-Molina and
               H. V. Jagadish},
  title     = {Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation},
  booktitle = {Proceedings of the 1990 ACM SIGMOD International Conference on
               Management of Data, Atlantic City, NJ, May 23-25, 1990},
  publisher = {ACM Press},
  year      = {1990},
  pages     = {74-83},
  ee        = {http://doi.acm.org/10.1145/93597.93624, db/conf/sigmod/Wang90.html},
  crossref  = {DBLP:conf/sigmod/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We define the independence-reducibility based on a modification of key dependencies, which has better computational properties and is more practically useful than the original one based on key dependencies. Using this modification as a tool, we design BCNF databases that are highly desirable with respect to updates and/or query answering. In particular, given a set U of attributes and a set F of functional dependencies over U, we characterize when F can be embedded in a database scheme over U that is independent and is BCNF with respect to F, a polynomial tune algorithm that tests this characterization and produces such a database scheme whenever possible is presented. The produced database scheme contains the fewest possible number of relation schemes. Then we show that designs of embedding constant-time-maintainable BCNF schemes and of embedding independence-reducible schemes share exactly the same method with the above design. Finally, a simple modification of this method yields a polynomial time algorithm for designing embedding separable BCNF schemes.

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.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Hector Garcia-Molina, H. V. Jagadish (Eds.): Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990. ACM Press 1990 BibTeX , SIGMOD Record 19(2), June 1990
Contents

Online Edition: ACM Digital Library


References

[A]
William Ward Armstrong: Dependency Structures of Data Base Relationships. IFIP Congress 1974: 580-583 BibTeX
[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
[AC]
Paolo Atzeni, Edward P. F. Chan: Efficient Query Answering in the Representative Instance Approach. PODS 1985: 181-188 BibTeX
[B]
Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX
[BB]
Catriel Beeri, Philip A. Bernstein: Computational Problems Related to the Design of Normal Form Relational Schemas. ACM Trans. Database Syst. 4(1): 30-59(1979) BibTeX
[BBG]
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX
[BH]
Catriel Beeri, Peter Honeyman: Preserving Functional Dependencies. SIAM J. Comput. 10(3): 647-656(1981) BibTeX
[BS]
François Bancilhon, Nicolas Spyratos: Independent Components of Databases. VLDB 1981: 398-408 BibTeX
[CH]
Edward P. F. Chan, Héctor J. Hernández: Independence-reducible Database Schemes. PODS 1988: 163-173 BibTeX
[CM]
Edward P. F. Chan, Alberto O. Mendelzon: Independent and Separable Database Schemes. SIAM J. Comput. 16(5): 841-851(1987) BibTeX
[Co]
...
[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
[HC]
Héctor J. Hernández, Edward P. F. Chan: A Characterization of Constant-time-mainteinability for BCNF Database Schemes. SIGMOD Conference 1988: 209-217 BibTeX
[HW]
Héctor J. Hernández, Ke Wang: On the Boundedness of Constant-Time-Maintainable Database Schemes. SIAM J. Comput. 22(1): 29-45(1993) 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
[Ma]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
[MMS]
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) 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]
...
[W]
Ke Wang: Can Constant-time Maintainability Be More Practical? PODS 1989: 120-127 BibTeX
[WG]
Ke Wang, Marc H. Graham: Constant-Time Maintainability: A Generalization of Independence. ACM Trans. Database Syst. 17(2): 201-246(1992) BibTeX
[Y]
Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 BibTeX
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:40:01 2009