A simplied universal relation assumption and its properties

ABSTRACT

One problem concerning the universal relation assumption is the inability of known methods to obtain a database scheme design in the general case, where the real-world constraints are given by a set of dependencies that includes embedded multivalued dependencies. We propose a simpler method of describing the real world, where constraints are given by functional dependencies and a single join dependency. The relationship between this method of defining the real world and the classical methods is exposed. We characterize in terms of hypergraphs those multivalued dependencies that are the consequence of a given join dependency. Also characterized in terms of hypergraphs are those join dependencies that are equivalent to a set of multivalued dependencies.

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: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 3: Catriel Beeri, On the menbership problem for functional and multivalued dependencies in relational databases, ACM Transactions on Database Systems (TODS), v.5 n.3, p.241-259, Sept. 1980 [doi>10.1145/320613.320614]
• 4: BEERI, C., AND BERNSTEIN, P.A. An algorithmic approach to normalization of relational database schemas, CSRG-73, Univ. Toronto, 1975.
• 5: BEERI, C., BERNSTEIN, P.A., AND GOODMAN, N. A sophisticate's introduction to database normalization theory. In Proc. 4th Int. Conf. Very Large Databases, (West Berlin, Sept. 13-15), ACM, New York, 1978, pp. 113-124.
• 6: Catriel Beeri , Ronald Fagin , John H. Howard, A complete axiomatization for functional and multivalued dependencies in database relations, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509414]
• 7: Catriel Beeri , Ronald Fagin , David Maier , Mihalis Yannakakis, On the Desirability of Acyclic Database Schemes, Journal of the ACM (JACM), v.30 n.3, p.479-513, July 1983 [doi>10.1145/2402.322389]
• 8: BEERI, C., MENDELZON, A.O., SAGIV, Y., AND ULLMAN, J.D. Equivalence of relational database schemes. SIAM J. Comput. 10, 2 (June 1981), 352-370.
• 9: BZF.RI, C. AND VARDI, M.Y. On the properties of joint dependencies. In Proc. Workshop Formal Bases for Databases (Toulouse, Dec. 1979).
• 10: 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]
• 11: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 12: 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]
• 13: 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]
• 14: Ronald Fagin, Normal forms and relational database operators, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582120]
• 15: LIEN, Y.E. On the equivalence of database models. Database Research Report No. 3 (July 1980), Bell Laboratories, Holmdel, N.J.
• 16: Y. Edmund Lien, On the Semantics of the Entity-Relationship Data Model, Proceedings of the 1st International Conference on the Entity-Relationship Approach to Systems Analysis and Design, p.155-168, January 1980
• 17: 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]
• 18: David Maier , Jeffrey D. Ullman, Connections in acyclic hypergraphs: extended abstract, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588118]
• 19: David Maier , Yehoshua Sagiv , Mihalis Yannakakis, On the Complexity of Testing Implications of Functional and Join Dependencies, Journal of the ACM (JACM), v.28 n.4, p.680-695, Oct. 1981 [doi>10.1145/322276.322280]
• 20: MENDELZON, A.O., AND MAIER, D. Generalized mutual dependencies and the decomposition of database relations. In Proc. 5th Int. Conf. Very Large Databases, (Rio de Janeiro, Oct. 3-5), ACM, New York, 1979, pp. 75-82.
• 21: RISSANEN, J. Theory of joins for relational databases--A tutorial survey. In Proc. 7th Symp. Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 64, Springer-Verlag, pp. 537-551.
• 22: 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]
• 23: ScIoRE, E. Null values, updates, and normalization in relational databases. Doctoral dissertation, Princeton Univ., Princeton, N. J., 1980.
• 24: Edward Sciore, Real-world MVD's, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582337]
• 25: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 26: VARD1, M.~(. Inferring multivalued dependencies from functional and join dependencies. Dep. of Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel, 1980.

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.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Trees

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

General Terms:
Algorithms, Design, Languages, Management, Theory

Keywords:
acyclic, database scheme, hypergraph, join dependency, multivalued dependency, relational database