GYO reductions, canonical connections, tree and cyclic schemas and tree projections

ABSTRACT

Database schemas may be partitioned into two sub-classes tree schemas and cyclic schemas. The analysis of tree vs cyclic schemas introduced the concepts of GYO reductions, canonical connections and tree projections. This paper investigates the intricate relationships among these concepts in the context of universal relation databases.

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: {ASU} A V Aho, Y Sagiv, and J D Ullman, "Equivalence of Relational Expressions," SIAM J Comput 8(2), (1979)
• 3: 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]
• 4: 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]
• 5: 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]
• 6: {BG} Bernstein, P A, and N Goodman, "The Power of Natural Semijoins," SIAM J of Comput 10(4), November 1981
• 7: {Fag} Fagin, R, "Types of Acyclicity for Hypergraphs and Relational Database Systems," Research Report RJ3330, IBM Research Laboratory, San Jose, CA, November 1981
• 8: 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]
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: {Gra} Graham, M H, On the Universal Relation, Technical Report, Univ of Toronto, Sept 1979
• 11: 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]
• 12: Nathan Goodman , Oded Shmueli, Syntactic Characterization of Tree Database Schemas, Journal of the ACM (JACM), v.30 n.4, p.767-786, Oct. 1983 [doi>10.1145/2157.322405]
• 13: N. Goodman , O. Shmueli, The tree property is fundamental for query processing, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588119]
• 14: N. Goodman , O. Shmueli, Transforming cyclic schemas into trees, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588120]
• 15: {Hul} Hull, R, "Acyclic Join Dependencies and Database Projections," J Computer and Systems Sciences, to appear
• 16: David Maier , Jeffrey D. Ullman, Connections in acyclic hypergraphs: extended abstract, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588118]
• 17: {Ris} Rissanen, J, "Theory of Joins for Relational Databases A Tutorial Survey," Proc 7th Symp Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, 64, Springer-Verlag, pp 537-551
• 18: {Yan} Yannakakis, M, "Algorithms for Acyclic Database Schemes," In Proc VLDB, pages 82-94, Cannes, France, September 1981
• 19: {YO} Yu, C T, and M Z Ozsoyoglu, "An Algorithm for Tree-Query Membership of a Distributed Query," In Proc Compsac79, IEEE Comp Society, November 1979