On the equivalence of an Egd to a set of Fd's

ABSTRACT

The question “Is a given join dependency equivalent to some set of multivalued dependencies?” led to the development of acyclicity theory [1]. The central question of this paper is: “Is a given equality-generating dependency equivalent to a set of functional dependencies?” An algorithm is presented that answers that question in polynomial time without using the chase process and, in the case of a “yes” answer, can be used to find (a cover of) the set of functional dependencies involved. This question is also related to the similar question about join dependencies and multivalued dependencies by proving a result about the hypergraph representation of an egd. It is interesting to note that a minimal representation of an egd must be &bgr;-acyclic for the egd to be equivalent to a set of fd's, in contrast to the jd/mvd case, in which only &agr;-acyclicity is needed. The &bgr;-acyclicity of an egd not necessarily minimal is always sufficient for the egd to be equivalent to a set of fd's as shown. Finally, the algorithm is extended for a single egd to answer the question whether a set of egd's with the same right-hand-side column is equivalent to a set of fd's.

REFERENCES

• 1: 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]
• 2: BEERI, C., AND VARDI, M.Y. On the complexity of testing implications of data dependencies. Dept. of Computer Science, The Hebrew Univ., Jerusalem, Israel, Dec. 1980.
• 3: Ronald Fagin, Degrees of acyclicity for hypergraphs and relational database schemes, Journal of the ACM (JACM), v.30 n.3, p.514-550, July 1983 [doi>10.1145/2402.322390]
• 4: Ronald Fagin, Horn clauses and database dependencies, Journal of the ACM (JACM), v.29 n.4, p.952-985, Oct. 1982 [doi>10.1145/322344.322347]
• 5: Marc H. Graham, Path expressions in databases, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588101]
• 6: GRAHAM, M. H., AND VARDI, M. On the complexity and axiomatizability of consistent database states. IBM Tech. Rep. RJ 4207. IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., 1984.
• 7: Marc H. Graham , Ke Wang, Constant time maintenance or the triumph of the FD., Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.202-216, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.6017]
• 8: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 9: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 10: Ke Wang, Constant time maintenance for consistent database state, 1986

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Data description languages (DDL)

General Terms:
Algorithms, Languages, Theory