On compiling queries in recursive first-order databases

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On compiling queries in recursive first-order databases

Full text

Pdf (1.85 MB)

Source

Journal of the ACM (JACM) archive
Volume 31 , Issue 1 (January 1984) table of contents

Pages: 47 - 85

Year of Publication: 1984

ISSN:0004-5411

Authors

Lawrence J. Henschen	Northwestern University, Evanston, Illinois
Shamim A. Naqvi	Bell Laboratories, Murray Hill, New Jersey

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms review 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/2422.2423 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	Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
	2	CHANG, C. On evaluation of quenes containing derived relations in a relational data. In Advances in Data Base Theory, Vol. 1, H. Gallaire and J. Minker, and J. M. Nicolas, Eds., Plenum Press, New York, 1981, pp. 235-260.
	3	FISHMAN, D., AND MINKER, J. H-representation: A clause representation for parallel search. Artif. Intell. 6 (1975), 103-127
	4	MCKAY, D. AND SHAPIRO, S. Using active connection graphs for reasoning with recursive rules. In Proc of 7th Int Joint Conf. on Artificial Intelligence, Vancouver, B.C., Aug. 24-28, 1981.
	5	MINKER, J. AND NICOLAS, J. M. On recursive axioms in relational databases. Tech. Rep. TR- 1119, University of Maryland, College Park, Md., 1981.
	6	NILSSON, J Computational schemes for recursive relational languages. In Workshop on Formal Basis for Data Bases, Toulouse, France, 1979.
	7	REITER, R. Deductive question answering on relational data bases. In Logic and Data Bases, H. Gallaire and J. Minker, Eds, Plenum Press, New York, 1978, pp. 149-177.
	8	REITER, R. On structuring a first-order database. In Proe of 2nd Nat. Conf. Canadian Society for Computational Studies of Intelligence, Toronto, July 19-21, 1978, pp. 90-99.
	9	REITER, R. On closed world databases. In Logic and Data Bases. H. Gallaire and J. Minker, Eds., Plenum Press, New York, 1978, pp. 55-76.
	10	Raymond Reiter, Equality and Domain Closure in First-Order Databases, Journal of the ACM (JACM), v.27 n.2, p.235-249, April 1980 [doi>10.1145/322186.322189]
	11	J. A. Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of the ACM (JACM), v.12 n.1, p.23-41, Jan. 1965 [doi>10.1145/321250.321253]
	12	SHAPIRO, S. AND MCKAY, D. Inference with recursive rules. In Proc AAAI Conf. on Artificial Intelligence, Stanford, Calif., 1980, pp. 151-153.
	13	SICKEL, S. A search technique for clause mterconnectivity graphs. IEEE Trans. Comput. C-25, 8 (Aug. 1976), pp. 823-834.
	14	Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983

CITED BY 86

	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
	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
	Eliezer L. Lozinskii, A problem-oriented inferential database system, ACM Transactions on Database Systems (TODS), v.11 n.3, p.323-356, Sept. 1986
	Michael Kifer , Eliezer L. Lozinskii, On compile-time query optimization in deductive databases by means of static filtering, ACM Transactions on Database Systems (TODS), v.15 n.3, p.385-426, Sept. 1990
	Gabriel M. Kuper , Moshe Y. Vardi, The logical data model, ACM Transactions on Database Systems (TODS), v.18 n.3, p.379-413, Sept. 1993
	J. Han, Constraint-Based Query Evaluation in Deductive Databases, IEEE Transactions on Knowledge and Data Engineering, v.6 n.1, p.96-107, February 1994
	S. S. Cosmadakis, On the first-order expressibility of recursive queries, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.311-323, March 1989, Philadelphia, Pennsylvania, 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
	C. Beeri , R. Ramakrishnan, On the power of magic, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.269-284, March 23-25, 1987, San Diego, California, United States
	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
	A. Marchetti-Spaccamella , A. Pelaggi , D. Sacca, Worst-case complexity analysis of methods for logic query implementation, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.294-301, March 23-25, 1987, San Diego, California, United States
	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
	Allen Van Gelder, A message passing framework for logical query evaluation, ACM SIGMOD Record, v.15 n.2, p.155-165, June 1986
	Arnon Rosenthal , Sandra Heiler , Umeshwar Dayal , Frank Manola, Traversal recursion: a practical approach to supporting recursive applications, ACM SIGMOD Record, v.15 n.2, p.166-176, June 1986
	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
	G. M. Kuper, Logic programming with sets, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.11-20, March 23-25, 1987, San Diego, California, United States
	Haim Gaifman , Harry Mairson , Yehoshua Sagiv , Moshe Y. Vardi, Undecidable optimization problems for database logic programs, Journal of the ACM (JACM), v.40 n.3, p.683-713, July 1993
	Y. Sagiv, Optimizing datalog programs, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.349-362, March 23-25, 1987, San Diego, California, United States
	Jeffrey F. Naughton, Minimizing function-free recursive inference rules, Journal of the ACM (JACM), v.36 n.1, p.69-91, Jan. 1989
	F. Afrati , S. S. Cosmadakis, Expressiveness of restricted recursive queries, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.113-126, May 14-17, 1989, Seattle, Washington, United States
	G. Grahne , S. Sippu , E. Soisalon-Soininen, Efficient evaluation for a subset of recursive queries, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.284-293, March 23-25, 1987, San Diego, California, United States
	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
	J. F. Naughton , R. Ramakrishnan , Y. Sagiv , J. D. Ullman, Efficient evaluation of right-, left-, and multi-linear rules, ACM SIGMOD Record, v.18 n.2, p.235-242, June 1989
	Georges Gardarin , Christophe de Maindreville, Evaluation of database recursive logic programs as recurrent function series, ACM SIGMOD Record, v.15 n.2, p.177-186, June 1986
	R. Ramnarayan , H. Lu, A data/knowledge base management testbed and experimental results on data/knowledge base query and update processing, ACM SIGMOD Record, v.17 n.3, p.387-395, June 1988
	Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, ACM SIGMOD Record, v.15 n.2, p.16-52, June 1986
	Yannis E. Ioannidis , Eugene Wong, Towards an algebraic theory of recursion, Journal of the ACM (JACM), v.38 n.2, p.329-381, April 1991
	C. Beeri , P. Kanellakis , F. Bancilhon , R. Ramakrishnan, Bounds on the propagation of selection into logic programs, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.214-226, March 23-25, 1987, San Diego, California, United States
	J. F. Naughton, One-sided recursions, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.340-348, March 23-25, 1987, San Diego, California, United States
	Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984
	Y. Sagiv , M. Y. Vardi, Safety of datalog queries over infinite databases, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.160-171, March 1989, Philadelphia, Pennsylvania, United States
	Guido Moerkotte , Peter C. Lockemann, Reactive consistency control in deductive databases, ACM Transactions on Database Systems (TODS), v.16 n.4, p.670-702, Dec. 1991
	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
	Isabel F. Cruz , Alberto O. Mendelzon , Peter T. Wood, A graphical query language supporting recursion, ACM SIGMOD Record, v.16 n.3, p.323-330, Dec. 1987
	Jeffrey F. Naughton, Compiling separable recursions, ACM SIGMOD Record, v.17 n.3, p.312-319, June 1988
	J. Shao , D. A. Bell , M. E. C. Hull, An experimental performance study of a pipelined recursive query processing strategy, Proceedings of the second international symposium on Databases in parallel and distributed systems, p.30-43, July 02-04, 1990, Dublin, Ireland
	Hussien Aly , Z. Meral Ozsoyoglu, Non-deterministic modelling of logical queries in deductive databases, ACM SIGMOD Record, v.16 n.3, p.60-72, Dec. 1987
	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
	A. Giordana , L. Saitta , F. Bergadano , F. Brancadori , D. De Marchi, ENIGMA: A System That Learns Diagnostic Knowledge, IEEE Transactions on Knowledge and Data Engineering, v.5 n.1, p.15-28, February 1993
	H. V. Jagadish , Rakesh Agrawal , Linda Ness, A study of transitive closure as a recursion mechanism, ACM SIGMOD Record, v.16 n.3, p.331-344, Dec. 1987
	Jiawei Han , Lawrence J. Henschen, Handling redundancy in the processing of recursive database queries, ACM SIGMOD Record, v.16 n.3, p.73-81, Dec. 1987
	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
	K. -C. Guh , C. Yu, Efficient Management of Materialized Generalized Transitive Closure in Centralized and Parallel Environments, IEEE Transactions on Knowledge and Data Engineering, v.4 n.4, p.371-381, August 1992
	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
	I. S. Mumick , S. J. Finkelstein , Hamid Pirahesh , Raghu Ramakrishnan, Magic is relevant, ACM SIGMOD Record, v.19 n.2, p.247-258, Jun. 1990
	Michael C. Chen , Evon Y. Lai, Issues on knowledge bases: a capital budgeting example, Proceedings of the 1985 ACM annual conference on The range of computing : mid-80's perspective: mid-80's perspective, p.507-510, October 1985, Denver, Colorado, United States
	Cheong Youn , Lawrence J. Henschen , Jiawei Han, Classification of recursive formulas in deductive databases, ACM SIGMOD Record, v.17 n.3, p.320-328, June 1988
	Matthias Jarke , Jim Clifford , Yannis Vassiliou, An optimizing prolog front-end to a relational query system, ACM SIGMOD Record, v.14 n.2, June 1984
	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
	Yim Yung Leung , Dik Lun Lee, Logic Approaches for Deductive Databases, IEEE Expert: Intelligent Systems and Their Applications, v.3 n.4, p.64-75, December 1988
	K. -C. Guh , C. Yu, Efficient Query Processing for a Subset of Linear Recursive Binary Rules, IEEE Transactions on Knowledge and Data Engineering, v.6 n.5, p.842-849, October 1994
	C. Youn , H. -J. Kim , L. J. Henschen , J. Han, Classification and Compilation of Linear Recursive Queries in Deductive Databases, IEEE Transactions on Knowledge and Data Engineering, v.4 n.1, p.52-67, February 1992
	Velko Iltchev, Bottom-up method for processing recursive sets of rules, Proceedings of the 4th international conference conference on Computer systems and technologies: e-Learning, p.178-183, June 19-20, 2003, Rousse, Bulgaria
	M. V. Mannino , L. D. Shapiro, Extensions to Query Languages for Graph Traversal Problems, IEEE Transactions on Knowledge and Data Engineering, v.2 n.3, p.353-363, September 1990
	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
	S. Ceri , G. Gottlob , L. Tanca, What You Always Wanted to Know About Datalog (And Never Dared to Ask), IEEE Transactions on Knowledge and Data Engineering, v.1 n.1, p.146-166, March 1989
	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
	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
	J. Han , W. Lu, Asynchronous Chain Recursions, IEEE Transactions on Knowledge and Data Engineering, v.1 n.2, p.185-195, June 1989
	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
	Jiawei Han , Ling Liu, Efficient Evaluation of Multiple Linear Recursions, IEEE Transactions on Software Engineering, v.17 n.12, p.1241-1252, December 1991
	Sang Ho Lee , Lawrence J. Henschen, Evaluation of Recursive Queries with Extended Rules in Deductive Databases, IEEE Transactions on Knowledge and Data Engineering, v.7 n.2, p.328-331, April 1995
	Rakesh Agrawal, Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries, IEEE Transactions on Software Engineering, v.14 n.7, p.879-885, July 1988
	Weining Zhang , Clement T. Yu , Daniel Troy, Necessary and sufficient conditions to linearize doubly recursive programs in logic databases, ACM Transactions on Database Systems (TODS), v.15 n.3, p.459-482, Sept. 1990
	W. Lu , D. L. Lee , J. Han, A Study on the Structure of Linear Recursion, IEEE Transactions on Knowledge and Data Engineering, v.6 n.5, p.723-737, October 1994
	Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988
	Yannis E. Ioannidis, A time bound on the materialization of some recursively defined views, Proceedings of the 11th international conference on Very Large Data Bases, p.219-226, August 21-23, 1985, Stockholm, Sweden
	Matthias Jarke , Volker Linnemann , Joachim W. Schmidt, Data constructors: on the integration of rules and relations, Proceedings of the 11th international conference on Very Large Data Bases, p.227-240, August 21-23, 1985, Stockholm, Sweden
	Carlo Zaniolo, The representation and deductive retrieval of complex objects, Proceedings of the 11th international conference on Very Large Data Bases, p.458-469, August 21-23, 1985, Stockholm, Sweden
	A. Giordana , F. Neri , L. Saitta , M. Botta, Integrating Multiple Learning Strategies in First Order Logics, Machine Learning, v.27 n.3, p.209-240, June 1997
	Qi Yang , Son Dao , Clement Yu , Naphtali Rishe, A Parallel Scheme Using the Divide-and-Conquer Method, Distributed and Parallel Databases, v.5 n.4, p.405-438, Oct. 1997
	G. Hulin, Parallel processing of recursive queries in distributed architectures, Proceedings of the 15th international conference on Very large data bases, p.87-96, July 1989, Amsterdam, The Netherlands
	Charles Kellogg , Anthony B. O'Hare , Larry Travis, Optimizing the Rule-Data Interface in a KMS, Proceedings of the 12th International Conference on Very Large Data Bases, p.42-51, August 25-28, 1986
	Eliezer L. Lozinskii, Computing Facts in Non-Horn Deductive Systems, Proceedings of the 14th International Conference on Very Large Data Bases, p.273-279, August 29-September 01, 1988
	Stefano Ceri , Georg Gottlob , Luigi Lavazza, Translation and Optimization of Logic Queries: The Algebraic Approach, Proceedings of the 12th International Conference on Very Large Data Bases, p.395-402, August 25-28, 1986
	Yannis E. Ioannidis, On the Computation of the Transitive Closure of Relational Operators, Proceedings of the 12th International Conference on Very Large Data Bases, p.403-411, August 25-28, 1986
	Louiqa Raschid , Stanley Y. W. Su, A Parallel Processing Strategy for Evaluating Recursive Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.412-419, August 25-28, 1986
	Kyu-Young Whang , Shamkant B. Navathe, An Extended Disjunctive Normal Form Approach for Optimizing Recursive Logic Queries in Loosely Coupled Environments, Proceedings of the 13th International Conference on Very Large Data Bases, p.275-287, September 01-04, 1987
	Georges Gardarin, Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs, Proceedings of the 13th International Conference on Very Large Data Bases, p.21-30, September 01-04, 1987
	Stefano Ceri , Letizia Tanca, Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries, Proceedings of the 13th International Conference on Very Large Data Bases, p.31-41, September 01-04, 1987
	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
	Mihalis Yannakakis, Perspectives on database theory, ACM SIGACT News, v.27 n.3, p.25-49, Sept. 1996
	Adnan H. Yahya, Duality for Goal-Driven Query Processing in Disjunctive Deductive Databases, Journal of Automated Reasoning, v.28 n.1, p.1-34, January 2002
	Shamim A. Naqvi , Lawrence J. Henschen, Synthesizing least fixed point queries into non-recursive iterative programs, Proceedings of the Eighth international joint conference on Artificial intelligence, p.25-28, August 08-12, 1983, Karlsruhe, West Germany
	Eliezer L. Lozinskii, Evaluating queries in deductive databases by generating, Proceedings of the 9th international joint conference on Artificial intelligence, p.173-177, August 18-23, 1985, Los Angeles, California

INDEX TERMS

Primary Classification:
D. Software
D.3 PROGRAMMING LANGUAGES
D.3.4 Processors
Subjects: Compilers

Additional Classification:
I. Computing Methodologies
I.2 ARTIFICIAL INTELLIGENCE
I.2.3 Deduction and Theorem Proving
Subjects: Logic programming

General Terms:
Algorithms, Languages, Theory, Verification

REVIEW

"Jack Minker : Reviewer"

As has been shown by Aho and Ullman [1], for example, the language of the relational algebra has limitations in that some operations, such as the transitive closure of a relation, cannot be expressed. In deductive databases, on extend more...

Collaborative Colleagues:

Lawrence J. Henschen: colleagues

Shamim A. Naqvi: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player