Beeri, C., R. Fagin, D. Maier, A. Mendeizon, J.D. Ullman, and M. Yannakakis, "Properties of Aeyclie Database Schemas," Proe. Thirteenth Annual A CM Syrup. on Theory of Computing, 355-362. Association for Computing. Machinery, New York, N.Y., May 1981.

Digital Library

Google Scholar

[6]

Beeri, C., R. F a gin, D. Maier and M. Yannakakis, "On the Desirability of Acyclic Database Schemes," J. A CM 30 (3): 479-513, July 1983.

Digital Library

Google Scholar

[7]

Bernstein, P.A., and N. Goodman, "The Power of Natural Semijoins," SIAM J. of Comput. 10 (4): 751-771, November 1981.

Digital Library

Google Scholar

[8]

Fagin, R., "Degrees of Acyclieity for Hypergraphs and Relational Database Schemes," J. ACM30 (3): 514-550, July 1983.

Digital Library

Google Scholar

[9]

F a gin, R., A. O. Mendelzon, and J. D. Ullman, "A Simplified Universal Relation Assumption and Its Properties," A UM Trans. Database System8 7 (3): 343-360, Sept. 1982.

Digital Library

Google Scholar

[10]

Graham, M.H., "On the Universal Relation," Technical Report, University of Toronto, September 1979.

Google Scholar

[11]

Goodman, N., and O. Shmueli, :'Tree Queries: A Simple Class of Queries," A GM Trans. on Database System8 4 (7): 653-{}77, December 1982.

Digital Library

Google Scholar

[12]

Goodman, N., and O. Shmueli, "Syntactic Characterization of Tree Database Schemas," J. A CM 30 (4): 767-786, October 1983.

Digital Library

Google Scholar

[13]

Goodman, N., and O. Shmueli, "The Tree Projection Theorem and Relational Query Processing," Journal of Coml~. and Syst. Science 28 (1): 60-79, February 1984.

Crossref

Google Scholar

[14]

Goodman, N., and O. Shmueli, "Transforming Cyclic Schemas into Trees," Proc. A UM SIGACT-$IGMOD Conference on Principles of Database Systems, 49-54, Los Angeles, CA, March 1982.

Digital Library

Google Scholar

[15]

Goodman, N., O. Shmueli and ~.C. Toy, "GYO Reductions, Canonical Connections, Tree and Cyclic Schemas and Tree Projections," Journal of Comp. and S$tst. Science 29 (3): 338-358, December 1984.

Digital Library

Google Scholar

[16]

Honeyman, P., R. E. Ladner, and M. Yannskakis, "Testing the Universal instance Assumption," In)'. Proc. Lett. 10 (I): 14-19, Feb. 1980.

Crossref

Google Scholar

[17]

Hull, R., "Aeyclic Join Dependencies and Data Base Projections," Journal of Comp. and Syst. Science 27 (2): 331-349, October 1983.

Crossref

Google Scholar

[18]

Johnson, D. S., and A. Klug, "Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies," J. Computer and S3/atern Science 28" 167-189, 1984.

Google Scholar

[19]

Katsumo, H., "An Extension of Conflict-Free Multivalued Dependency Sets," A CM Trans. Database System8 9 (2): 309-326, March 1984.

Digital Library

Google Scholar

[20]

Kambayashi, Y., and M. Yoshikawa, "Query Processing Utilizing Dependencies and Horizontal Decomposition," Proc. A CM SIGMOD Conference, 55-67, San Jose, CA, :May 1983.

Digital Library

Google Scholar

[21]

Kambayashi, Y., Yoshikawa M. and S. Yajima, "Query Processing for Distributed Databases using Generalized Semi-Joins," Proc. A CM SIGMOD Conference, 151-160, Orlando, FL, May 1983.

Digital Library

Google Scholar

[22]

Klausner, A., "Semijoin Reductions in Cyclic Databases," unpublished manuscript, December 1981.

Google Scholar

[23]

Laver, K., Mendelzon, A.O. and M.H. Graham, "Functional Dependencies on Cyclic Database Schemes," Pro~. A CM SIGMOD Conference, 79-91, San J~e, CA, May 1983.

Digital Library

Google Scholar

[24]

Maier, D., A. O. Mendelzon, and Y. Sagiv, "Testing Implications of Data Dependencies," A CM Trans. on Database Systema 4 (4): 455- 469, Dec. 1979.

Digital Library

Google Scholar

[25]

Ozsoyoglu, M., and E. Choukhmmane, "On the Cyclic to Acyclic Scheme Transformation sad Solving Cyclic Queries," Proc. A CM SIGA C, T- SIGMOD" Conference on Principles of Database Systems, 133-142, Waterloo, Ontario, Canada, April 1984.

Digital Library

Google Scholar

[26]

Sacca, D., Msafredi, F. and A. Mecchia, "Properties of Database Schemata with Functional Dependencies," Proc. A CM SIGACT-SIGMOD Conference on Principle6 of Database Syotemo, 19-28, March 1984.

Digital Library

Google Scholar

[27]

Tarjan, R.E., and M. Y annakakis, "Simple Linear-time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs," SIAM J. of Comput. 13 (3): 566-579, August 1984.

Digital Library

Google Scholar

[28]

Ullman, J. D., Principle8 of Database Systems, Computer Science Press, Potomac, Md., 2nd Edition, 1983.

Digital Library

Google Scholar

[29]

Yannakakis, M., "Algorithms for Acyclic Database Schemes," Proc. 7th Int. Conf. on Very Large Data Bases, 82-94, Cannes, France, September 1981.

Google Scholar

[30]

Yu, C.T., and M.Z. Ozsoyoglu, "An Algorithm for Tree-Query Membership of a Distributed Query," Proc. COMPSAC 79, IEEE Comp. Society, November 1979.

Google Scholar

Cited By

View all

Sagiv YShmueli O(1993)Solving queries by tree projectionsACM Transactions on Database Systems10.1145/155271.15527718:3(487-511)Online publication date: 1-Sep-1993
https://dl.acm.org/doi/10.1145/155271.155277
Morishita SVardi MKanellakis P(1992)Avoiding Cartesian products in programs for multiple joins (extended abstract)Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems10.1145/137097.137911(368-379)Online publication date: 1-Jul-1992
https://dl.acm.org/doi/10.1145/137097.137911
Ullman J(1992)New frontiers in database system researchFuture Tendencies in Computer Science, Control and Applied Mathematics10.1007/3-540-56320-2_54(87-101)Online publication date: 1992
https://doi.org/10.1007/3-540-56320-2_54

Index Terms

Recommendations

Combined-semantics equivalence of conjunctive queries

Query containment and equivalence are fundamental problems in the context of query processing and optimization. In this paper, we consider combined-semantics equivalence of conjunctive (CQ) queries. The combined-semantics formalism 10,11 generalizes the ...
Equivalence and minimization of conjunctive queries under combined semantics
ICDT '12: Proceedings of the 15th International Conference on Database Theory

The problems of query containment, equivalence, and minimization are fundamental problems in the context of query processing and optimization. In their classic work [2] published in 1977, Chandra and Merlin solved the three problems for the language of ...
Solving queries by tree projections

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODS '86: Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems

June 1985

293 pages

ISBN:0897911792

DOI:10.1145/6012

Chairman:
Avi Silberschatz

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1985

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODS86

Sponsor:

PODS86: ACM SIGACT-SIGMOD Symposium on Principles of Database Systems

March 24 - 26, 1986

Massachusetts, Cambridge, USA

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
335
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)8

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Sagiv YShmueli O(1993)Solving queries by tree projectionsACM Transactions on Database Systems10.1145/155271.15527718:3(487-511)Online publication date: 1-Sep-1993
https://dl.acm.org/doi/10.1145/155271.155277
Morishita SVardi MKanellakis P(1992)Avoiding Cartesian products in programs for multiple joins (extended abstract)Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems10.1145/137097.137911(368-379)Online publication date: 1-Jul-1992
https://dl.acm.org/doi/10.1145/137097.137911
Ullman J(1992)New frontiers in database system researchFuture Tendencies in Computer Science, Control and Applied Mathematics10.1007/3-540-56320-2_54(87-101)Online publication date: 1992
https://doi.org/10.1007/3-540-56320-2_54

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Combined-semantics equivalence of conjunctive queries

Equivalence and minimization of conjunctive queries under combined semantics

Solving queries by tree projections