Constant-Time-Maintainable BCNF Database Schemes.

Héctor J. Hernández, Edward P. F. Chan: Constant-Time-Maintainable BCNF Database Schemes. ACM Trans. Database Syst. 16(4): 571-599(1991)
  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        = {, db/journals/tods/HernandezC91.html},
  bibsource = {DBLP,}


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 rP 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

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Index Terms and Review]
[Full Text in PDF Format, 2036 KB]


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
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX
Paolo Atzeni, Edward P. F. Chan: Efficient Query Answering in the Representative Instance Approach. PODS 1985: 181-188 BibTeX
Paolo Atzeni, Edward P. F. Chan: Independent Database Schemes under Functional and Inclusion Dependencies. VLDB 1987: 159-166 BibTeX
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
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX
Philip A. Bernstein, Nathan Goodman: What does Boyce-Codd Normal Form Do? VLDB 1980: 245-259 BibTeX
Volkert Brosda, Gottfried Vossen: Updating a Relational Database through a Universal Schema Interface. PODS 1985: 66-75 BibTeX
Edward P. F. Chan: Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions. SIGMOD Conference 1984: 149-163 BibTeX
Edward P. F. Chan, Paolo Atzeni: Connection-Trap-Free Database Schemes. J. Comput. Syst. Sci. 44(1): 1-22(1992) BibTeX
Edward P. F. Chan, Héctor J. Hernández: Independence-reducible Database Schemes. PODS 1988: 163-173 BibTeX
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
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
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
Edward P. F. Chan, Alberto O. Mendelzon: Answering queries on embedded-complete database schemes. J. ACM 34(2): 349-375(1987) BibTeX
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
Ronald Fagin: Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. J. ACM 30(3): 514-550(1983) BibTeX
Marc H. Graham, Alberto O. Mendelzon, Moshe Y. Vardi: Notions of dependency satisfaction. J. ACM 33(1): 105-129(1986) BibTeX
Marc H. Graham, Ke Wang: Constant Time Maintenance or The Triumph of the fd. PODS 1986: 202-216 BibTeX
Marc H. Graham, Mihalis Yannakakis: Independent Database Schemas. J. Comput. Syst. Sci. 28(1): 121-141(1984) BibTeX
Peter Honeyman: Extension Joins. VLDB 1980: 239-244 BibTeX
Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982) BibTeX
Minoru Ito, Motoaki Iwasaki, Tadao Kasami: Some Results on the Representative Instance in Relational Databases. SIAM J. Comput. 14(2): 334-354(1985) BibTeX
Carol Helfgott LeDoux, Douglas Stott Parker Jr.: Reflections on Boyce-Codd Normal Form. VLDB 1982: 131-141 BibTeX
Claudio L. Lucchesi, Sylvia L. Osborn: Candidate Keys for Relations. J. Comput. Syst. Sci. 17(2): 270-279(1978) BibTeX
Alberto O. Mendelzon: Database States and Their Tableaux. ACM Trans. Database Syst. 9(2): 264-282(1984) BibTeX
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX
David Maier, David Rozenshtein, David Scott Warren: Window Functions. Advances in Computing Research 3: 213-246(1986) BibTeX
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
Sylvia L. Osborn: Testing for Existence of a Covering Boyce-Codd normal Form. Inf. Process. Lett. 8(1): 11-14(1979) BibTeX
Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120 BibTeX
Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983) BibTeX
Yehoshua Sagiv: Evaluation of Queries in Independent Database Schemes. J. ACM 38(1): 120-161(1991) BibTeX
Yehoshua Sagiv: On Bounded Database Schemes and Bounded Horn-Clause Programs. SIAM J. Comput. 17(1): 1-22(1988) BibTeX
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
Ke Wang: Can Constant-time Maintainability Be More Practical? PODS 1989: 120-127 BibTeX
Ke Wang, Marc H. Graham: Constant-Time Maintainability: A Generalization of Independence. ACM Trans. Database Syst. 17(2): 201-246(1992) BibTeX
Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:39:11 2008