Constant-Time-Maintainable BCNF Database Schemes.

@article{DBLP:journals/tods/HernandezC91,
  author    = {H{\'e}ctor J. Hern{\'a}ndez and
               Edward P. F. Chan},
  title     = {Constant-Time-Maintainable BCNF Database Schemes},
  journal   = {ACM Trans. Database Syst.},
  volume    = {16},
  number    = {4},
  year      = {1991},
  pages     = {571-599},
  ee        = {http://doi.acm.org/10.1145/115302.115301, db/journals/tods/HernandezC91.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The maintenance problem (for database states) of a database scheme R with respect to a set of functional dependencies F is the following decision problem. Let r be a consistent state of R with respect to F and assume we insert a tuple t into r_P in r. Is r union {t} a consistent state of R with respect to F? R is said to be constant-time-maintainable with respect to F if there is an algorithm that solves the maintenance problem of R with respect to F in time independent of the state size.

A characterization of constant-time-maintainability for the class of BCNF database schemes is given. An efficient algorithm that tests this characterization is shown, as well as an algorithm for solving the maintenance problem in time independent of the state size. It is also shown that total projections of the representative instance can be computed via unions of projections of sequential extension joins. Throughout we assume that database schemes are dependency preserving and BCNF, and that functional dependencies are given in the form of key dependencies.

Copyright © 1991 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-2 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

Online Edition: ACM Digital Library

References

[1]

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

[2]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX

[3]

Paolo Atzeni, Edward P. F. Chan: Efficient Query Answering in the Representative Instance Approach. PODS 1985: 181-188 BibTeX

[4]

Paolo Atzeni, Edward P. F. Chan: Independent Database Schemes under Functional and Inclusion Dependencies. VLDB 1987: 159-166 BibTeX

[5]

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

[6]

Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX

[7]

Philip A. Bernstein, Nathan Goodman: What does Boyce-Codd Normal Form Do? VLDB 1980: 245-259 BibTeX

[8]

Volkert Brosda, Gottfried Vossen: Updating a Relational Database through a Universal Schema Interface. PODS 1985: 66-75 BibTeX

[9]

Edward P. F. Chan: Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions. SIGMOD Conference 1984: 149-163 BibTeX

[10]

Edward P. F. Chan, Paolo Atzeni: Connection-Trap-Free Database Schemes. J. Comput. Syst. Sci. 44(1): 1-22(1992) BibTeX

[11]

Edward P. F. Chan, Héctor J. Hernández: Independence-reducible Database Schemes. PODS 1988: 163-173 BibTeX

[12]

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

[13]

Edward P. F. Chan, Héctor J. Hernández: On the Desirability of gamma-Acyclic BCNF Database Schemes. Theor. Comput. Sci. 62(1-2): 67-104(1988) BibTeX

[14]

Edward P. F. Chan, Héctor J. Hernández: On Generating Database Schemes Bounded or Constant-time-maintainable by Extensibility. Acta Inf. 25(5): 475-496(1988) BibTeX

[15]

Edward P. F. Chan, Alberto O. Mendelzon: Answering queries on embedded-complete database schemes. J. ACM 34(2): 349-375(1987) BibTeX

[16]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[17]

Ronald Fagin: Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. J. ACM 30(3): 514-550(1983) BibTeX

[18]

...

[19]

Marc H. Graham, Alberto O. Mendelzon, Moshe Y. Vardi: Notions of dependency satisfaction. J. ACM 33(1): 105-129(1986) BibTeX

[20]

Marc H. Graham, Ke Wang: Constant Time Maintenance or The Triumph of the fd. PODS 1986: 202-216 BibTeX

[21]

Marc H. Graham, Mihalis Yannakakis: Independent Database Schemas. J. Comput. Syst. Sci. 28(1): 121-141(1984) BibTeX

[22]

Peter Honeyman: Extension Joins. VLDB 1980: 239-244 BibTeX

[23]

Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982) BibTeX

[24]

Minoru Ito, Motoaki Iwasaki, Tadao Kasami: Some Results on the Representative Instance in Relational Databases. SIAM J. Comput. 14(2): 334-354(1985) BibTeX

[25]

Carol Helfgott LeDoux, Douglas Stott Parker Jr.: Reflections on Boyce-Codd Normal Form. VLDB 1982: 131-141 BibTeX

[26]

Claudio L. Lucchesi, Sylvia L. Osborn: Candidate Keys for Relations. J. Comput. Syst. Sci. 17(2): 270-279(1978) BibTeX

[27]

Alberto O. Mendelzon: Database States and Their Tableaux. ACM Trans. Database Syst. 9(2): 264-282(1984) BibTeX

[28]

David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX

[29]

David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX

[30]

David Maier, David Rozenshtein, David Scott Warren: Window Functions. Advances in Computing Research 3: 213-246(1986) BibTeX

[31]

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

[32]

Sylvia L. Osborn: Testing for Existence of a Covering Boyce-Codd normal Form. Inf. Process. Lett. 8(1): 11-14(1979) BibTeX

[33]

Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120 BibTeX

[34]

Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983) BibTeX

[35]

Yehoshua Sagiv: Evaluation of Queries in Independent Database Schemes. J. ACM 38(1): 120-161(1991) BibTeX

[36]

Yehoshua Sagiv: On Bounded Database Schemes and Bounded Horn-Clause Programs. SIAM J. Comput. 17(1): 1-22(1988) BibTeX

[37]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

[38]

...

[39]

Ke Wang: Can Constant-time Maintainability Be More Practical? PODS 1989: 120-127 BibTeX

[40]

Ke Wang, Marc H. Graham: Constant-Time Maintainability: A Generalization of Independence. ACM Trans. Database Syst. 17(2): 201-246(1992) BibTeX

[41]

Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 BibTeX