On the complexity of join dependencies

ABSTRACT

In [10] a method is proposed for decomposing join dependencies (jds) in a relational database using the notion of a hinge. This method was subsequently studied in [11] and [12]. We show how the technique of decomposition can be used to make integrity checking more efficient. It turns out that it is important to find a decomposition that minimizes the number of edges of its largest element. We show that the decompositions obtained with the method described in [10] are optimal in this respect. This minimality criterion leads to the definition of the degree of cyclicity, which allows us to classify jds and leads to the notion of n-cyclicity, of which acyclicity is a special case for n = 2. We then show that, for a fixed value of n (which may be greater than 2). integrity checking can be performed in polynomial time provided we restrict ourselves to n-cyclic jds. Finally, we generalize a well-known characterization for acyclic jds by proving that n-cyclicity is equivalent to “n-wise consistency implies global consistency.” As a consequence, consistency checking can be performed in polynomial time if we restrict ourselves to n-cyclic jds, for a tired value of n, not necessarily equal to 2.

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: Catriel Beeri , Ronald Fagin , David Maier , Alberto Mendelzon , Jeffrey Ullman , Mihalis Yannakakis, Properties of acyclic database schemes, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.355-362, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802489]
• 3: 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]
• 4: BERGI~, C. Graphes et Hypergraphes. Dunod, Paris, 1970.
• 5: 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]
• 6: CODD, E.F. Further normalizations of the relational data base model. In Data Base Systems, R. Rustin, Ed., Prentice Hall, Englewood Cliffs, N.J., 1972, 33-64.
• 7: 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]
• 8: Ronald Fagin, Acyclic Database Schemes (of Various Degrees): A Painless Introduction, Proceedings of the 8th Colloquium on Trees in Algebra and Programming, p.65-89, March 09-11, 1983
• 9: 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]
• 10: GYSSENS, M., AND PAREDAENS, J. A decomposition methodology for cyclic databases. In Advances in Database Theory, vol 2, H. Gallaire, J. Minker, and J. M. Nicolas, Eds., Plenum Press, New York, 1973.
• 11: Marc Gyssens , Jan Paredaens, On the decomposition of join dependencies, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588032]
• 12: Marc Gyssens, Embedded join dependencies as a tool for decomposing full join dependencies, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.205-214, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325441]
• 13: Marc Gyssens, Decompositions of join dependencies in the relational database model, 1985
• 14: 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]
• 15: Jan Paredaens , Dirk Van Gucht, An Application of the Theory of Graphs and Hypergraphs to the Decomposition of Relational Database Schemes, Proceedings of the 8th Colloquium on Trees in Algebra and Programming, p.350-366, March 09-11, 1983
• 16: RISSANEN, J. Theory of joins for relational databasesmA tutorial survey. In Proceedings of the 7th Symposium on the Mathematical Foundations of Computer Science: Lecture Notes in Computer Sc&nce 64, Springer Verlag, 1978, 537-551.
• 17: THALHEJM, B. A complete axiomatization for join dependencies in relations. Tech. Rep., Technische Univ. Dresden, Sektion Math., 07-08-84.
• 18: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 19: ZANIOLO, C. Analysis and design of relational schemata for database systems. Tech. Pep. UCLA-ENG-7669, Dept. of Computer Science, Univ. of California, Los Angeles, 1976.

INDEX TERMS

Classification:
  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: Normal forms; Schema and subschema