Solving queries by tree projections

ABSTRACT

Suppose a database schema D is extended to D¯ by adding new relation schemas, and states for D are extended to states for D¯ by applying joins and projections to existing relations. It is shown that certain desirable properties that D¯ has with respect to D. These properties amount to the ability to compute efficiently the join of all relations in a state for D from an extension of this state over D¯. The equivalence is proved for unrestricted (i.e., both finite and infinite) databases. If D¯ is obtained from D by adding a set of new relation schemas that form a tree schema, then the equivalence also holds for finite databases. In this case there is also a polynomial time algorithm for testing the existence of a tree projection of D¯ with respect to D.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: AHO, A. V, SAGIV, Y., AND ULLMAN, J. D, Equivalences among relatmnal expressions. SIAM J. Comput. 8, 2 (May 1979), 218 246
• 3: 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]
• 4: 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]
• 5: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 6: 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]
• 7: BERNSTEIN, P. A., AND GOODMAN, N. The power of natural semijoins. SIAM J Comput. 10, 4 (Nov. 1981), 751-771.
• 8: 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]
• 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: 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]
• 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: GOODMAN, N., AND SHMUELI, O. The tree projection theorem and relational query processing. J. Comput. Syst. Sc~. 28, I (Feb. 1984), 60-79,
• 14: Nathan Goodman , Oded Shmueli , Y. C. Tay, GYO reductions, canonical connections, tree and cyclic schemas, and tree projections, Journal of Computer and System Sciences, v.29 n.3, p.338-358, Dec. 1984 [doi>10.1016/0022-0000(84)90004-7]
• 15: C-RAHAM~ M H. On the universal relation Tech. Rep. University of Toronto, Sept. 1979.
• 16: HULL, R. Acyelic join dependencies and data base projections. J Comput. Syst. Sci. 27, 2 (Oct. 1983), 331 349.
• 17: JOHNSON, D. S., AND KLUG, A. Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Scl. 28, 1 (1984), 167-189.
• 18: Yahiko Kambayashi , Masatoshi Yoshikawa, Query processing utilizing dependencies and horizontal decomposition, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California
• 19: Yahiko Kambayashi , Masatoshi Yoshikawa , Shuzo Yajima, Query processing for distributed databases using generalized semi-joins, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582381]
• 20: Hirofumi Katsuno, An extension of conflict-free multivalued dependency sets, ACM Transactions on Database Systems (TODS), v.9 n.2, p.309-326, June 1984 [doi>10.1145/329.354]
• 21: KLAUSNER, A. Semijoin reductions in cyclic databases. Unpublished manuscript, Dec. 1981.
• 22: Kent Laver , Alberto O. Mendelzon , Marc H. Graham, Functional dependencies on cyclic database schemes, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California
• 23: 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]
• 24: Z. Meral Ozsoyoglu , Elarbi Choukhmane, On the cyclic to acyclic scheme transformation and solving cyclic queries, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588031]
• 25: D. Sacca , F. Maufredi , A. Mecchia, Properties of database schemata with functional 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.588015]
• 26: Yehoshua Sagiv , Oded Shmueli, The equivalence of solving queries and producing tree projections (extended abstract), Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.160-172, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15413]
• 27: SAGW, Y., AND SHMUELI, O. A characterization of finite FD-acyclity. J. Comput. Syst. Sc~. 38, 2 (Apr. 1989), 380-404.
• 28: Robert E. Tarjan , Mihalis Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM Journal on Computing, v.13 n.3, p.566-579, August 1984 [doi>10.1137/0213035]
• 29: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 30: YANNAKAKIS, M. Algorithms for acyclic database schemes. In Proceedings of the 7th Internatwnal Conference on Very Large Data Bases (Cannes, Sept. 1981). VLDB Endowment, 82-94.
• 31: Yu, C. T., AND OZSOYOGLU, M.Z. An algorithm for tree-query membership of a distributed query. In Proceedings of the COMPSAC 79, (Chicago, Ill., Nov. 1979). IEEE, New York, 1979.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Theory

Keywords:
acyclicity, chase, database schema, hypergraph, inclusion dependency, join, monotone join expression, projection, qual graph, relational database, semijoin, semijoin reduction, tableau, tree projection, tree schema