Functional dependencies on cyclic database schemes

ABSTRACT

We study how functional dependencies affect the cyclicity of a database scheme; in particular, when does a set of functional dependencies make a cyclic database scheme behave like an acyclic one.A database scheme is fd-acyclic if every pairwise-consistent database state that satisfies the fd's is join-consistent. We give a simple characterization of fd-acyclicity over a restricted class of database schemes. We then give a tableau-based characterization for the general case that leads to an algorithm for testing fd-acyclicity. This algorithm actually solves the more general problem of query equivalence under functional dependencies and typed inclusion dependencies.

REFERENCES

• 1: {ASU} Aho, A., Sagiv, Y., Ullman, J., "Equivalences Among Relational Expressions", SIAM J. Comp. 8,2 (1979), pp. 218--246.
• 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: {BFMY} Beeri, C., Fagin, R., Maier, D., Yannakakis, M., "On The Desirable Properties of Acyclic Database Schemas", IBM Report RJ3131, San Jose, Calif., 1981.
• 4: {BG} Bernstein, P.A., Goodman, N., "The Power of Natural Semi-Joins", Siam J. of Comp., 10,4, (1981).
• 5: Marco A. Casanova , Ronald Fagin , Christos H. Papadimitriou, Inclusion dependencies and their interaction with functional dependencies, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588141]
• 6: Edward P. F. Chan , Alberto O. Mendelzon, Independent and separable database schemes, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588091]
• 7: 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]
• 8: 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]
• 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: Marc Henry Graham, Satisfying database states, 1982
• 11: {GM} Graham, M., Mendelzon, A.O., "Strong Equivalence of Relational Expressions Under Dependencies", Infor. Proc. Letters, 14,2, (1982), pp. 57--62.
• 12: Nathan Goodman , Oded Shmueli, Tree queries: a simple class of relational queries, ACM Transactions on Database Systems (TODS), v.7 n.4, p.653-677, Dec. 1982 [doi>10.1145/319758.319775]
• 13: {GS2} Goodman, N., Shmueli, O., "Limitations of the Chase", Infor. Proc. Letters, 13,4 (1982), pp. 154--157.
• 14: Marc H. Graham , Mihalis Yannakakis, Independent database schemas, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588144]
• 15: Peter Honeyman, Testing satisfaction of functional dependencies, Journal of the ACM (JACM), v.29 n.3, p.668-677, July 1982 [doi>10.1145/322326.322330]
• 16: D. S. Johnson , A. Klug, Testing containment of conjunctive queries under functional and inclusion dependencies, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588138]
• 17: {K} Katsumo, H., "A Desirable Class of Sets Of FD's and MVD's", NTT Technical Report, Japan, (1982).
• 18: {L} Laver, K., Forthcoming Ph.D. dissertation, Univ. of Toronto.
• 19: 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]
• 20: Yehoshua Sagiv, Can we use the universal instance assumption without using nulls?, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582336]
• 21: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 22: Yannis Vassiliou, A formal treatment of imperfect information in database management, 1980