Constant-time maintainability: a generalization of independence

ABSTRACT

The maintenance problem of a database scheme is the following decision problem: Given a consistent database state &rgr; and a new tuple u over some relation scheme of &rgr;, is the modified state &rgr; ∪ {u} still consistent? A database scheme is said to be constant-time-maintainable(ctm) if there exists an algorithm that solves its maintenance problem by making a fixed number of tuple retrievals. We present a practically useful algorithm, called the canonical maintenance algorithm, that solves the maintenance problem of all ctm database schemes within a "not too large" bound. A number of interesting properties are shown for ctm database schemes, among them that non-ctm database schemes are not maintainable in less than a linear time in the state size. A test method is given when only cover embedded functional dependencies (fds) appear. When the given dependencies consist of fds and the join dependency (jd) ⋈ R of the database scheme, testing whether a database scheme is ctm is reduced to the case of cover embedded fds. When dependency-preserving database schemes with only equality-generating dependencies (egds) are considered, it is shown that every ctm database scheme has a set of dependencies that is equivalent to a set of embedded fds, and thus, our test method for the case of embedded fds can be applied. In particular, this includes the important case of lossless database schemes with only egds.

REFERENCES

• 1: A. V. Aho , C. Beeri , J. D. Ullman, The theory of joins in relational databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.297-314, Sept. 1979 [doi>10.1145/320083.320091]
• 2: AHO, A. V., SAGIV, Y., AND ULLMAN, J. D. Equivalence among relational expressions. SIAM J. Comput. 8, 2 (1979), 218-246.
• 3: A. V. Aho , Y. Sagiv , J. D. Ullman, Efficient optimization of a class of relational expressions, ACM Transactions on Database Systems (TODS), v.4 n.4, p.435-454, Dec. 1979 [doi>10.1145/320107.320112]
• 4: ARMSTRONg, W.W. Dependency structures of data base relationships. In Proceedings of the IFIP Congress, 1974. North-Holland, Amsterdam, 1974, pp. 580-583.
• 5: Paolo Atzeni , Edward P. F. Chan, Efficient query answering in the representative instance approach, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.181-188, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325429]
• 6: Catriel Beeri , Philip A. Bernstein, Computational problems related to the design of normal form relational schemas, ACM Transactions on Database Systems (TODS), v.4 n.1, p.30-59, March 1979 [doi>10.1145/320064.320066]
• 7: BEERI, C., AND HONEYMAN, P. Preserving functional dependencies. SIAM J. Comput. 10, 3 (1981), 647-656.
• 8: BEERI, C., ANn VARDI, M.Y. Formal systems for tuple and equality generating dependencies. SIAM J. Comput. 13, i (Feb. 1984), 76-98.
• 9: Catriel Beeri , Moshe Y. Vardi, A Proof Procedure for Data Dependencies, Journal of the ACM (JACM), v.31 n.4, p.718-741, Oct. 1984 [doi>10.1145/1634.1636]
• 10: Joachim Biskup , Umeshwar Dayal , Philip A. Bernstein, Synthesizing independent database schemas, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582118]
• 11: Volkert Brosda , Gottfried Vossen, Updating a relational database through a universal schema interface, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.66-75, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325414]
• 12: Edward P. F. Chan , Hector J. Hernandez, Independence-reducible database schemes, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.163-173, March 1988, Austin, Texas, United States [doi>10.1145/308386.308431]
• 13: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 14: Ronald Fagin, Horn clauses and database dependencies, Journal of the ACM (JACM), v.29 n.4, p.952-985, Oct. 1982 [doi>10.1145/322344.322347]
• 15: G. Gottlob, Computing covers for embedded functional dependencies, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.58-69, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28665]
• 16: GRAHAM, M. H., AND MENDELZON, A. O. On the power of canonical queries. Unpublished manuscript, 1983.
• 17: Marc H. Graham , Moshe Y. Vardi, On the complexity and axiomatizability of consistent database states, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588052]
• 18: Marc H. Graham , Ke Wang, Constant time maintenance or the triumph of the FD., Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.202-216, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.6017]
• 19: GRAHAM, M. H., AND YANNAKAKIS, M. Independent database schemes, J. Comput. Syst. Sci. 28, I (Feb. 1984), 121-141.
• 20: Marc H. Graham , Alberto O. Mendelzon , Moshe Y. Vardi, Notions of dependency satisfaction, Journal of the ACM (JACM), v.33 n.1, p.105-129, Jan. 1986 [doi>10.1145/4904.4798]
• 21: Héctor J. Hernández , Edward P. F. Chan, A characterization of constant-time maintainability for BCNF database schemes, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.209-217, June 01-03, 1988, Chicago, Illinois, United States
• 22: Héctor J. Hernández , Ke Wang, On the boundedness of constant-time-maintainable database schemes, SIAM Journal on Computing, v.22 n.1, p.29-45, Feb. 1993 [doi>10.1137/0222003]
• 23: Peter Honeyman, Testing satisfaction of functional dependencies, Journal of the ACM (JACM), v.29 n.3, p.668-677, July 1982 [doi>10.1145/322326.322330]
• 24: ITO, M., IWASAKI, M., AND KASAM, T. Some results on the representative instances in relational databases. SlAM J. Comput. 14, 2 (May 1985), 334-353.
• 25: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 26: MAmR, D., ULLMAN, J. D., AND VARm, M.Y. On the foundations of the universal relational model. ACM Trans. Database Syst. 4, 4 (Dec. 1979), 455-469.
• 27: David Maier , Jeffrey D. Ullman , Moshe Y. Vardi, On the foundations of the universal relation model, ACM Transactions on Database Systems (TODS), v.9 n.2, p.283-308, June 1984 [doi>10.1145/329.318580]
• 28: Heikki Mannila , Kari-Jouko Räihä, Dependency Inference, Proceedings of the 13th International Conference on Very Large Data Bases, p.155-158, September 01-04, 1987
• 29: Alberto O. Mendelzon, Database states and their tableaux, ACM Transactions on Database Systems (TODS), v.9 n.2, p.264-282, June 1984 [doi>10.1145/329.318579]
• 30: Yehoshua Sagiv, Can we use the universal instance assumption without using nulls?, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582336]
• 31: Yehoshua Sagiv, A characterization of globally consistent databases and their correct access paths, ACM Transactions on Database Systems (TODS), v.8 n.2, p.266-286, June 1983 [doi>10.1145/319983.319988]
• 32: Yehoshua Sagiv, On computing restricted projections of representative instances, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.171-180, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325427]
• 33: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 34: Yannis Vassiliou, A formal treatment of imperfect information in database management, 1980
• 35: Ke Wang, Constant time maintenance for consistent database state, 1986
• 36: K. Wang, Can constant-time-maintainability be more practical?, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.120-127, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73733]
• 37: YANr~AKAKIS, M. Algorithms for acyclic database schemes. In Proceedings of Very Large Databases, 1981 (Cannes, France, Sept 9-11, 1981) ACM, New York, 1981, pp. 82-94.
• 38: YANNAKAKIS, M., AND PAPADIMITROU, C.H. Algebraic dependencies J Comput Syst. Scl 25, 1 (Aug. 1982), 2-41.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Mechanical theorem proving

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General
          Subjects: Security, integrity, and protection**
      H.2.1 Logical Design
          Subjects: Normal forms

General Terms:
Algorithms, Design, Theory

Keywords:
chase, constraint enforcement, functional dependency, independent database schemes, join dependency, lossless join, relational database, representative instance, tableau