Worst-case complexity analysis of methods for logic query implementation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Worst-case complexity analysis of methods for logic query implementation

Full text

Pdf (687 KB)

Source

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

San Diego, California, United States

Pages: 294 - 301

Year of Publication: 1987

ISBN:0-89791-223-3

Authors

A. Marchetti-Spaccamella	Dipartimento di Informatica e Slstemistica, Università di Roma "La Saptenza", Rome, Italy
A. Pelaggi	Dipartimento di Informatica e Slstemistica, Università di Roma "La Saptenza", Rome, Italy
D. Sacca	Dipartimento di Sistemi, Università della Calabria and CRAI, Rende, Italy

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data
SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 13, Citation Count: 14

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

	BMSU1	Francois Bancilhon , David Maier , Yehoshua Sagiv , Jeffrey D Ullman, Magic sets and other strange ways to implement logic programs (extended abstract), Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.1-15, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15399]
	BR	Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
	HN	Lawrence J. Henschen , Shamim A. Naqvi, On compiling queries in recursive first-order databases, Journal of the ACM (JACM), v.31 n.1, p.47-85, Jan. 1984 [doi>10.1145/2422.2423]
	SZ1	Domenico Saccà , Carlo Zaniolo, On the implementation of a simple class of logic queries for databases, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.16-23, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.6013]
	SZ2	Domenico Saccá , Carlo Zaniolo, The generalized counting method for recursive logic queries, Proceedings on International conference on database theory, p.31-53, December 1986, Rome, Italy
	SZ3	Sacc~, D, Zamolo, C, "Implemcntauon of recurslve queries for a data language based on pure Horn clauses", unpubhshed manuscript, 1986
	SZ4	Sacca, D, Zamolo, C, "Magic counting methods", unpubhshed manuscript, 1986
	U1	Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
	U2	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]

CITED BY 14

	O. Wolfson, Sharing the load of logic-program evaluation, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.46-55, December 05-07, 1988, Austin, Texas, United States
	M. Nussbaum, An interpreter for large knowledge bases, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.87-97, February 21-23, 1989, Louisville, Kentucky
	Yangjun Chen , Theo Härder, An optimal graph traversal algorithm for evaluating linear binary-chain programs, Proceedings of the third international conference on Information and knowledge management, p.34-41, November 29-December 02, 1994, Gaithersburg, Maryland, United States
	Adam L. Buchsbaum , Paris C. Kanellakis , Jeffrey S. Vitter, A data structure for arc insertion and regular path finding, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.22-31, January 22-24, 1990, San Francisco, California, United States
	Ramsey W. Haddad , Jeffrey F. Naughton, Counting methods for cyclic relations, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.333-340, March 1988, Austin, Texas, United States
	Domenico Sacca , Carlo Zaniolo, Magic counting methods, ACM SIGMOD Record, v.16 n.3, p.49-59, Dec. 1987
	Mihalis Yannakakis, Graph-theoretic methods in database theory, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.230-242, April 02-04, 1990, Nashville, Tennessee, United States
	S. Seshadri , Jeffrey F. Naughton, On the expected size of recursive Datalog queries, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.268-279, May 29-31, 1991, Denver, Colorado, United States
	W. Nejdl , S. Ceri , G. Wiederhold, Evaluating Recursive Queries in Distributed Databases, IEEE Transactions on Knowledge and Data Engineering, v.5 n.1, p.104-121, February 1993
	Yangjun Chen, On the Graph Traversal and Linear Binary-Chain Programs, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.573-596, March 2003
	David A. Briggs, A correction of the termination conditions of the Henschen-Naqvi technique, Journal of the ACM (JACM), v.37 n.4, p.711-719, Oct. 1990
	Jiawei Han , Ling Liu, Efficient Evaluation of Multiple Linear Recursions, IEEE Transactions on Software Engineering, v.17 n.12, p.1241-1252, December 1991
	Petros Potikas , Panos Rondogiannis , Manolis Gergatsoulis, A Value-propagating Transformation Technique for Datalog Programs Based on Non-Deterministic Constructs, Fundamenta Informaticae, v.72 n.4, p.485-527, December 2006
	Wolfgang Nejdl, Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy, Proceedings of the 13th International Conference on Very Large Data Bases, p.43-50, September 01-04, 1987