On the Desirability of Acyclic Database Schemes

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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	ARMSTRONG, W.W.Dependency structures of database relauonships. In Prec. IFIP 74, North Holland, Amsterdam, 1974, pp 580--583
	3	Charles W. Bachman, Data structure diagrams, ACM SIGMIS Database, v.1 n.2, p.4-10, Summer 1969 [doi>10.1145/1017466.1017467]
	4	BATIm, C., D'ATm, A., AND MOSCAmNI, M. Formal tools for top.down and bottom-up generation of acy~lic relational schemata. Prec. 7th Int. Conf. on Graph-Theoretic Concepts in Computer Science, Linz, Austria, 1981.
	5	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]
	6	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]
	7	BEERI, C., MENDELZON, A.O., SAOIv, Y, AND ULLMAN, J.D. Equivalence of relational database schemes. SIAM J. Comput. 10, 2 (June 1981), 352-370.
	8	BEERI, C., AND RlSSANEN, J. Faithful representation of relational database schemes Res. Pep. RJ2722, IBM Research Laboratory, San Jose, Calif., 1980.
	9	BEERI, C., AND VARDI, M Y. On the properties of join dependencies, in Advances in Database Theory, H Gallaire, J. Minker, and J-M. Nicolas, Eds, Plenum, N.Y., 1981, pp. 25-72.
	10	C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
	11	Philip A. Bernstein , Dah-Ming W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM (JACM), v.28 n.1, p.25-40, Jan. 1981 [doi>10.1145/322234.322238]
	12	BtRNSrEIN, P.A., AND GOODMAN, N The power of natural semijoins SIAM ~ Comput 10, 4 (Nov. 1981), 751-771.
	13	BlsKtre, J. Inferences of multivalued dependencies in fixed and undetermined universe. Theor Comput. Sci. 10 (1980), 93-105.
	14	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]
	15	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]
	16	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]
	17	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]
	18	GOLUMBIC, M.C. Algonthrmc Graph Theory and Perfect Graphs. Academic Press, New York, 1980
	19	GOODMAN, N., AND Srt~mu, O Charactertzauons of tree database schemas Tech. Rep., Harvard Univ., Cambndge, Mass., 1981
	20	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]
	21	GRAHAm, M H. On the universal relaion Tech. Pep., Umv. of Toronto, Toronto, Oat, Can, Sept. 1979.
	22	HAGmAgA, K., ITO, M., TANIGUCHI, K, AND KxsAm, T. Decision problems for mulUvalued dependencies in relaUonal databases SIAM J Comput. 8, 2 (May 1979), 247-264.
	23	Peter Honeyman, Functional dependencies and the universal instance property in the relational model of database systems, 1980
	24	HONEYMAN, P, LADNER, R.E, ANt> YANNAKAKIS, i Testing the universal instance assumption. Inf. Prec. Lett. 10, 1 (1980), 14-19
	25	KORTFI, H.F., AND ULLMAN, J.D. SYSTEM/U" A database system based on the universal relation assumption. Proc XP1 Workshop, Stony Brook, N.Y., June 1980.
	26	Y. Edmund Lien, On the Equivalence of Database Models, Journal of the ACM (JACM), v.29 n.2, p.333-362, April 1982 [doi>10.1145/322307.322311]
	27	LmN, Y.E. Multwalued dependencies wath null values m relational data bases. In Proc 5th Int. Conf. on Very Large Data Bases (Rue de Janeiro, Brazil, Oct. 3-5, 1979), ACM, New York, pp. 61-66
	28	Y. Edmund Lien, Hierarchical schemata for relational databases, ACM Transactions on Database Systems (TODS), v.6 n.1, p.48-69, March 1981 [doi>10.1145/319540.319546]
	29	MAmg, D. Discarding the universal instance assumption Preliminary results Proc XPI Workshop, Stony Brook, N.Y., June 1980
	30	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]
	31	MENO~LZON, A O., AND M^IER, D. Generalized mutual dependencies and the decomposition of database relations, in Prec. 5th int. Conf. on Very Large Data Bases (Rue de Janeiro, Brazil, Oct 3-5, 1979), ACM, New York, pp. 75-82
	32	RISSANEN, J Theory of relations for databases~A tutorial survey, in Prec. 7th Symp on Mathematical Foundations of Computer Science, Lecture Notes m Computer Science 64, J. Winkowskl, Ed, Spnnger-Verlag, pp. 537-551
	33	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]
	34	Jorma Rissanen, On equivalences of database schemes, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588116]
	35	Edward Sciore, The universal instance and database design, 1980
	36	SCIOtLE, E.Some observations on real-world data dependencies Proc. XP1 Workshop, Stony Brook, N.Y, June 1980.
	37	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]
	38	TARSAN, R.E., AND YANNAKAKIS, M. Strnple lmear-tmae algonthms to test ehordality of graphs, test acychcity of hypergraphs, and selecuvely reduce acychc hypergraphs. Teeh. Pep., Bell Laboratories, Murray Hdl, N.J., Mar. 1982.
	39	VARDI, M.Y lnfemng multlvalued dependencies from funcUonal and join dependencies. Tech. Rep., Weizmann lnstttute, Rehovot, Israel, 1980
	40	VARDI, M.Y. On decompositton of relational databases. In Proc. 23rd IEEE Syrup. on Foundations of Computer Science (Chicago, I11., Oct. 1982), IEEE, New York, 1982, pp 176-185.
	41	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]
	42	WALKER, A Time and space m a lathce of umversal relations with blank entries. Proc. XP1 Workshop, Stony Brook, N Y, June 1980
	43	YANNAKAKIS, M.Algorithms for acychc database schemes. In Proc. 7th Int. Conf. on Very Large Data Bases (Cannes, France, Sept. 9-11, 1981), ACM, New York, 1981, pp. 82--94.
	44	Yu, C.T, AND OZSOYO~LO, M.Z An algorithm for tree-query membership of a distributed query Proc 1979 1EEE COMPSAC, IEEE, N.Y., 1979, pp 306-312
	45	Carlo Antonio Zaniolo, Analysis and design of relational schemata for database systems., 1976