Syntactic Characterization of Tree Database Schemas

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Syntactic Characterization of Tree Database Schemas

Full text

Pdf (1.02 MB)

Source

Journal of the ACM (JACM) archive
Volume 30 , Issue 4 (October 1983) table of contents

Pages: 767 - 786

Year of Publication: 1983

ISSN:0004-5411

Authors

Nathan Goodman	Computer Science Department, Boston University, Boston, MA and Harvard University, Cambridge, Massachusetts
Oded Shmueli	Computer Science Department, Technion-Israel Institute of Technology, Haifa 32000, Israel and Harvard University, Cambridge, Massachusetts

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 24, Citation Count: 11

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/2157.322405 What is a DOI?

REFERENCES

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	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]
	2	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]
	3	BEROe, C. Graphs and Hypergraphs. North Holland, New York, 1973.
	4	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]
	5	BERNSTEININ, P.A., AND GOODMAN, N The power of natural semijoms SIAM ~ Comput. 10, 4 (Nov. 198t),
	6	BUNEMAN, P.A characterization of ngtd circuit graphs Discrete Math 9 (1974), 205-212
	7	CHASE, K Join graphs and acydic data base schemas In Prec. 7th Int. Conf. on Very Large Databases (Cannes, France, Sept. 9-11, 1981), ACM, New York, pp. 95-100
	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	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
	11	GRAHAM, M.H.On the universal relation. Tech. Pep., Univ. of Toronto, Toronto, Ont., Can, Sept 1979.
	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	HARARY, F.Graph Theory. Addison-Wesley, Reading, Mass, 1972.
	14	HULL, R Acyclic join dependencies and database projections ~ Comput. Syst. S~i (to appear).
	15	MAXER, D., ~d~O ULLMAN, J D Connecttons in acychc hypergraphs. Tech..Pep STAN-CS-81-853, Stanford Univ, Stanford, Calif, May 1981.
	16	David Maier , Jeffrey D. Ullman, Maximal objects and the semantics of universal relation databases, ACM Transactions on Database Systems (TODS), v.8 n.1, p.1-14, March 1983 [doi>10.1145/319830.319831]
	17	ROSE, D.J., TAR/AN, R.E., AND LUCKER, G.S. Algorithmic aspects of vertex elimination on graphs. SlAM d. Comput. 5 (1976), 266-283.
	18	SCtOR~, E. Null values, updates, and normalizaUon m relational databases. Ph.D. Dlssertatton, Princeton Univ, Princeton, N J, 1980.
	19	Jeffrey D. Ullman, The U. R. strikes back, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588114]
	20	YANNAKAKIS, M. Algortthms for acyclic database schemes. In Prec. 7th. Int. Conf. on Very Large Databases (Cannes, France, Sept. 9-11, 1981), ACM, New York, pp. 82-94.
	21	Yu, C T., ANY OZSOYOGLU, M.X.Aa algorithm for tree-query membership of a distributed query. In Proc. Compsac79, IEEE, New York, Nov. 1979.
	22	Carlo Antonio Zaniolo, Analysis and design of relational schemata for database systems., 1976

CITED BY 11

	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
	Yehoshua Sagiv , Oded Shmueli, Solving queries by tree projections, ACM Transactions on Database Systems (TODS), v.18 n.3, p.487-511, Sept. 1993
	Y. C. Tay, Attribute agreement, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.110-119, March 1989, Philadelphia, Pennsylvania, United States
	Dan E. Willard, Quasilinear algorithms for processing relational calculus expressions (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.243-257, April 02-04, 1990, Nashville, Tennessee, United States
	Yehoshua Sagiv, Sagiv,Y-On finite FD-acyclicity, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.173-182, March 24-26, 1986, Cambridge, Massachusetts, United States
	J. Leuchner , L. Miller , G. Slutzki, A polynomial time algorithm for testing implications of a join dependency and embodied functional dependencies, ACM SIGMOD Record, v.17 n.3, p.218-224, June 1988
	Weining Zhang , C. T. Yu, A necessary condition for a doubly recursive rule to be equivalent to a linear recursive rule, ACM SIGMOD Record, v.16 n.3, p.345-356, Dec. 1987
	C. T. Yu , C. C. Chang, Distributed query processing, ACM Computing Surveys (CSUR), v.16 n.4, p.399-433, Dec. 1984
	Georg Gottlob , Nicola Leone , Francesco Scarcello, The complexity of acyclic conjunctive queries, Journal of the ACM (JACM), v.48 n.3, p.431-498, May 2001
	Nathan Goodman , Oded Shmueli , Y. C. Tay, GYO reductions, canonical connections, tree and cyclic schemas and tree projections, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia
	D. J. Troy , C. T. Yu , W. Zhang, Linearization of Nonlinear Recursive Rules, IEEE Transactions on Software Engineering, v.15 n.9, p.1109-1119, September 1989