Semigroup techniques in recursive query optimization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Semigroup techniques in recursive query optimization

Full text

Pdf (958 KB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems table of contents

Nashville, Tennessee, United States

Pages: 145 - 153

Year of Publication: 1990

ISBN:0-89791-352-3

Author

Thane Plambeck

Department of Computer Science, Stanford University, Stanford CA

Sponsors

SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 18, Citation Count: 0

Additional Information:

references 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/298514.298553 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.

	AhUl79	Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
	Blum65	E.K. Blum, 1965. A note on free subsemigroups with two generators, Bull. Am. Math. Soc. 71,678-679.
	Blu65b	E.K. Blum, 1965. Free subsemigroups of a free semigroup, Mich. Math. J. 12, 179- 182.
	ChHa85	A.K. Chandra, D. Harel, 1985. Hornclause queries and generalizations. J. Logic Programming 1, 1-15.
	ChMe77	Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
	Cosm88	Stavros Cosmadakis , Haim Gaifman , Paris Kanellakis , Moshe Vardi, Decidable optimization problems for database logic programs, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.477-490, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62259]
	GMN84	Herve Gallaire , Jack Minker , Jean-Marie Nicolas, Logic and Databases: A Deductive Approach, ACM Computing Surveys (CSUR), v.16 n.2, p.153-185, June 1984 [doi>10.1145/356924.356929]
	GMSV87	H. Gaifman, H. Mairson, Y. Sagiv, and M. Y. Vardi, 1987. Undecidable optimization problems for database logic programs. Proc. 2nd IEEE Syrup. on Logic in Computer Science, Ithaca, 1987, 106-115.
	Hu74	T.W. Hungerford, 1974. Algebra. Springer- Verlag, New York.
	Ioan89	Y. E. Ioannidis, Commutativity and its role in the processing of linear recursion, Proceedings of the 15th international conference on Very large data bases, p.155-163, July 1989, Amsterdam, The Netherlands
	IoWo88	Y.E. Ioannidis, and E. Wong, 1988. Towards an Algebraic Theory of Recursion. University of Wisconsin CS technical report No. 801, October, 1988.
	JAN87	H. V. Jagadish , Rakesh Agrawal , Linda Ness, A study of transitive closure as a recursion mechanism, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.331-344, May 27-29, 1987, San Francisco, California, United States
	Kane88	P.C. Kanellakis, 1988. Elements of Relational Database Theory. In Handbook of Computer Science, North-Holland, (to appear).
	KMR82	K.H. Kim, L. G. Makar-Limanov, and F. W. Roush, 1982. Graph monoids. Semigroup Forum 25,1-7.
	Lall79	Gerard Lallement, Semigroups and Combinatorial Applications, John Wiley & Sons, Inc., New York, NY, 1979
	Mark62	A1. A. Markov, 1962. Non-recurrent coding. Problem, Kybern. 8, 169-189 (Russian).
	Naug86	Jeff Naughton, Data independent recursion in deductive databases, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.267-279, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15420]
	Plam89	T. Plambeck, 1989. Containment depth and uniform boundedness of linear recursive single rule Datalog programs, Manuscript submitted for publication.
	RSUV89	R. Ramakrishnan , Y. Sagiv , J. D. Ullman , M. Y Vardi, Proof-tree transformation theorems and their applications, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.172-181, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73739]
	SaYa80	Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
	Sar89a	Y. P. Saraiya, Linearising nonlinear recursions in polynomial time, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.182-189, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73740]
	Sar89b	Y. Saraiya, 1989. NAIL! seminar, Stanford University, Summer 1989.
	Speh75	J.C. Spehner, 1975. Quelques constructions et algorithmes relatifs aux sous-. monoides d'un monoide libre, Semigroup Forum 9,334-353.
	Ullm85	Jeffrey D. Ullman, Implementation of logical query languages for databases, ACM Transactions on Database Systems (TODS), v.10 n.3, p.289-321, Sept. 1985 [doi>10.1145/3979.3980]
	Ull88a	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
	Ull88b	Jeffrey D. Ullman, Principles of Database and Knowledge-Base Systems: Volume II: The New Technologies, W. H. Freeman & Co., New York, NY, 1990
	Vard88	Moshe Y. Vardi, Decidability and undecidability results for boundedness of linear recursive queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.341-351, March 1988, Austin, Texas, United States [doi>10.1145/308386.308470]