A characterization of globally consistent databases and their correct access paths

ABSTRACT

The representative instance is proposed as a representation of the data stored in a database whose relations are not the projections of a universal instance. Database schemes are characterized for which local consistency implies global consistency. (Local consistency means that each relation satisfies its own functional dependencies; global consistency means that the representative instance satisfies all the functional dependencies.) A method of efficiently computing projections of the representative instance is given, provided that local consistency implies global consistency. Throughout, it is assumed that a cover of the functional dependencies is embodied in the database scheme in the form of keys.

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: 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]
• 3: AHO, A.V., SAGIV, Y., AND ULLMAN, J.D. Equivalences among relational expressions. SIAM. J. Comput. 8, 2 (May 1979), 218-246.
• 4: ARMSTRONC, W.W. Dependency structures of database relationships. In Proc. IFIP 74, North Holland, Amsterdam, 1974, pp. 580-583.
• 5: 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]
• 6: Philip A. Bernstein, Synthesizing third normal form relations from functional dependencies, ACM Transactions on Database Systems (TODS), v.1 n.4, p.277-298, Dec. 1976 [doi>10.1145/320493.320489]
• 7: BERNSTEIN, P.A., AND GOODMAN, N. What does Boyce-Codd normal form do? In Proc. Int. Conf. on Very Large Data Bases, Montreal, Canada, 1980, pp. 245-259.
• 8: 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]
• 9: 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]
• 10: E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
• 11: Ronald Fagin , Alberto O. Mendelzon , Jeffrey D. Ullman, A simplied universal relation assumption and its properties, ACM Transactions on Database Systems (TODS), v.7 n.3, p.343-360, Sept. 1982 [doi>10.1145/319732.319735]
• 12: HONEYMAN, P. Extension joins. In Proc. Int. Conf on Very Large Data Bases, Montreal, Canada, 1980, pp. 239-244.
• 13: 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]
• 14: HONEYMAN, P., LADNER, R.E., AND YANNAKAKAIS, M. Testing the universal instance assumption. Inf. Proc. Lett. I0, 1 (Feb. 1980), 14-19.
• 15: KORTH, H.F. A proposal for the SYSTEM/U query language. Unpublished memorandum, Stanford Univ., Stanford, Calif., 1980.
• 16: KORTH, H.F., AND ULLMAN, J.D. System/U: A database system based on the universal relation assumption. In Proc. XP1 Conf., Stony Brook, N.Y., June 1980.
• 17: LIEN, Y.E. Multivalued dependencies with null values in relational data bases. In Proc. 5th Int. Conf on Very Large Data Bases, Rio de Janeiro, Brazil, 1979, pp. 61-66.
• 18: MAIER, D. Discarding the universal instance assumption: Preliminary results. In Proc. XP1 Conf., Stony Brook, N.Y., June 1980.
• 19: David Maier , Alberto O. Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, ACM Transactions on Database Systems (TODS), v.4 n.4, p.455-469, Dec. 1979 [doi>10.1145/320107.320115]
• 20: MAIER, D., AND ULLMAN, J.D. Maximal objects and the semantics of universal relation databases. Tech. Rep. 80-016, Dept. Computer Science, State Univ. New York at Stony Brook, Stony Brook, N.Y., Nov. 1980.
• 21: OSBORN, S.L. Towards a universal relation interface. In Proc 5th Int. Conf. on Very Large Data Bases, Rio de Janeiro, Brazil, 1979, pp. 52-60.
• 22: 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]
• 23: Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
• 24: SCIORE, E. The universal instance and database design. Tech. Rep. TR 271, Dept. Elec. Eng. and Comp. Sci., Princeton Univ., Princeton, N.J., June I980.
• 25: VASSILIOU, Y. A formal treatment of imperfect information in database management. Tech. Rep. CSRG-123, Univ. Toronto, Nov. 1980.
• 26: VASSILIOU, Y. Functional dependencies and incomplete information. In Proc. Int. Conf. on Very Large Data Bases, Montreal, Canada, 1980, pp. 260-269.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Normal forms; Schema and subschema
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Algorithms, Design, Languages, Theory

Keywords:
chase, extension join, functional dependency, null value, relational algebra, relational database, representative instance, universal relation scheme