Equivalence of relational database schemes

ABSTRACT

We investigate the question of when two database schemes embody the same information. We argue that this question reduces to the equivalence of the sets of fixed points of the project-join mappings associated with the two database schemes in question. When data dependencies are given, we need only consider those fixed points that satisfy the dependencies. A polynomial algorithm to test the equivalence of database schemes, when there are no dependencies, is given. We also provide an exponential algorithm to handle the case where there are functional and/or multivalued dependencies. Furthermore, we give a polynomial time test to determine whether a project-join mapping preserves a set of functional dependencies, and a polynomial time algorithm for equivalence of database schemes whose project-join mappings do preserve the given set of functional dependencies. Lastly, we introduce the “update sets” approach to database design as an application of these results.

REFERENCES

• 1: Aho, A.V., Beeri, C. and Ullman, J.D., The Theory of Joins in Relational Databases, Proc. 18th. Symp. on Foundations of Computer Science, 1977.
• 2: ANSI/X3/SPARC, The ANSI/X3/SPARC Framework, Tsichritzis, D. and Klug, A. (eds.), AFIPS Press, 1978.
• 3: Armstrong, W.W. Dependency Structures of Data Base Relationships, Proc. IFIP '74, North-Holland, 1974, pp. 580-583.
• 4: Aho, A.V., Sagiv, Y. and Ullman, J.D., Equivalence of Relational Expressions,. To appear in SIAM J. Computing.
• 5: 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]
• 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., Bernstein, P. and Goodman, N., A Sophisticate's Introduction to Database Normalization Theory, Proc. 4th. Int'l. Conf. on Very Large Data Bases, West Berlin, 1978, pp. 113-124.
• 8: 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]
• 9: Beeri, C., Mendelzon, A.O., Sagiv, Y. and Ullman, J.D., Equivalence of Relational Database Schemes, Technical Report #252, Dept. of EECS, Princeton Univ., Dec. 1978.
• 10: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 11: 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]
• 12: Codd, E.F., Further Normalization of the Data Base Relational Model, in Data Base Systems (Courant Computer Science Symp. 6, R. Rustin ed.), Prentice-Hall, 1972, pp. 33-64.
• 13: Codd, E.F., Understanding Relations, FDT (ACM SIGMOD Bull.) 7:3-4 (1975), pp. 23-28.
• 14: Delobel, C., Contributions Theoretiques a la Conception et a l'Evaluation d'un Systeme d'Informations Applique a la Gestion, These d'Etat, Univ. de Grenoble, October 1973.
• 15: Ronald Fagin, Multivalued dependencies and a new normal form for relational databases, ACM Transactions on Database Systems (TODS), v.2 n.3, p.262-278, Sept. 1977 [doi>10.1145/320557.320571]
• 16: Hall, P., Owlett, T., Todd, S., Relations and Entities, in Modelling in Data Base Management Systems, G.M. Nijssen (ed.), North Holland, 1976.
• 17: M. Lacroix , A. Pirotte, Generalized joins, ACM SIGMOD Record, v.8 n.3, p.14-15, September 1976 [doi>10.1145/984378.984379]
• 18: Maier, D., Mendelzon, A.O. and Sagiv, Y., Testing Implications of Data Dependencies, Computer Science TR #84, SUNY at Stony Brook, 1978.
• 19: Nijssen, G. M., On the Gross Architecture for the Next Generation Database Management Systems, Information Processing '77, B. Gilchrist (ed.), North-Holland, 1977.
• 20: Jorma Rissanen, Independent components of relations, ACM Transactions on Database Systems (TODS), v.2 n.4, p.317-325, Dec. 1977 [doi>10.1145/320576.320580]
• 21: Rissanen, J., Theory of Relations for Databases - A Tutorial Survey, in Mathematical Foundations of Computer Science 1978, Springer-Verlag, 1978, pp.536-551.
• 22: Carlo Antonio Zaniolo, Analysis and design of relational schemata for database systems., 1976

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Computability theory

General Terms:
Algorithms, Management, Theory