Properties of acyclic database schemes

ABSTRACT

There is a class of database descriptions, involving one “acyclic” join dependency and a collection of functional dependencies, and nothing else, that appears powerful enough to describe most any real-world body of data in relational database terms. Further, this class has many desirable properties. Some properties make operations like updates and the selection of joins to implement a query over a universal relation especially easy. Other properties of interest were studied by other researchers who described the same class in radically different terms, and found desirable properties in their own contexts. It is the purpose of this paper to define the class formally, to give its important properties and the equivalences with the other classes mentioned, and to explain the importance of each property. This paper is intended to summarize the results that will appear in more detail in [FMU] and [BFMY].

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: Beeri, C., P. A. Bernstein, and N. Goodman, "A sophisticate's introduction to database normalization theory," Proc. International Conference on Very Large Data Bases, pp. 113-124, 1978.
• 3: 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]
• 4: Beeri, C., R. Fagin, D. Maier, and M. Yannakakis, "On the desirable properties of acyclic database schemas," manuscript in preparation.
• 5: Catriel Beeri , Alberto O. Mendelzon , Yehoshua Sagiv , Jeffrey D. Ullman, Equivalence of relational database schemes, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.319-329, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804424]
• 6: Beeri, C. and M. Y. Vardi, "On the properties of join dependencies," Proc. Workshop on Formal Bases for Databases, Toulouse, Dec., 1979.
• 7: 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]
• 8: Bernstein, P. A. and N. Goodman, "What does Boyce-Codd normal form do?," Proc. International Conference on Very Large Data Bases, 1980.
• 9: Bernstein, P. A and N. Goodman, "The theory of semijoins," TR CCA-79-27, Computer Corp. of America, Cambridge, Mass., 1979.
• 10: 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]
• 11: 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]
• 12: 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]
• 13: Fagin, R., A. O. Mendelzon, and J. D. Ullman, "A simplified universal relation assumption and its properties," RJ2900, IBM, San Jose, Calif., 1980.
• 14: Graham, M. H., "On the universal relation," technical report, Univ. of Toronto, Sept., 1979.
• 15: Honeyman, P., "Properties of the universal relation assumption," Ph. D. thesis, Princeton Univ., Princeton, N. J., 1980.
• 16: Honeyman, P., R. E. Ladner, and M. Yannakakis, "Testing the universal instance assumption," Inf. Proc. Letters, 10:1 (1980), pp. 14-19.
• 17: Kent, W., "Consequences of assuming a universal relation," IBM technical report, Dec., 1979, to appear in TODS.
• 18: Korth, H. F. and J. D. Ullman, "SYSTEM/U: a database system based on the universal relation assumption," Proc. XP1 Conference, Stonybrook, N. Y., June, 1980.
• 19: Lien, Y. E., "On the equivalence of database models," private communication, June, 1980.
• 20: 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
• 21: Lien, Y.E., "Multivalued dependencies with null values in relational data bases," Proc. International Conference on Very Large Data Bases, pp. 61-66, 1979.
• 22: Maier, D., "Discarding the universal instance assumption: preliminary results," Proc. XP1 Conference, Stonybrook, N. Y., June, 1980.
• 23: 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]
• 24: Rissanen, J., "Theory of joins for relational databases—a tutorial survey," Proc. Seventh Symp. on Mathematical Foundations of Computer Science, Lecture Notes in CS, 64, Springer-Verlag, pp. 537-551.
• 25: 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]
• 26: Sciore, E., "Null values, updates, and normalization in relational databases," doctoral dissertation, Princeton Univ., Princeton, N. J., 1980.
• 27: Sciore, E., "Some observations on real-world data dependencies," Proc. XP1 Conference, Stonybrook, N. Y., June, 1980.
• 28: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 29: Vardi, M. Y., "Inferring multivalued dependencies from functional and join dependencies," Dept. of Applied Math., Weizmann Inst. of Science, Rehovot, Israel, 1980.
• 30: Yannis Vassiliou, Null values in data base management a denotational semantics approach, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582123]
• 31: Walker, A., "Time and space in a lattice of universal relations with blank entries," Proc. XP1 Conference, Stonybrook, N. Y., June, 1980.
• 32: 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:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Hypergraphs

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Normal forms

General Terms:
Design, Management, Theory