Data Independent Recursion in Deductive Databases

Summary: Decision procedure to test whether a recursive predicate in a deductive database admits an equivalent fixed finite set of conjunctions of base predicates, under either arbitrary or specified nonrecursive initialization. If no finite equivalent exists, the analysis still yields transformations that accelerate compiled evaluation of recursive queries, extending prior bounded-tableau and compilation results. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 765
Venue: PODS
Year: 1986
Pagerank: 0.00013445831
Overall Rank: 1,185 | 91.76%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Jeff Naughton

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
537	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.0002068591
673	One-Sided Recursions	1987	PODS	0.00018348841
1,648	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD	0.00011028408
1,688	Automata Theory for Database Theoreticians	1989	PODS	0.00010913301
1,991	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.84713e-05
2,206	A Decidable Class of Bounded Recursions	1987	PODS	9.2910236e-05
3,855	On Distributed Processibility of Datalog Queries by Decomposing Databases	1989	SIGMOD	6.6953401e-05
4,136	Safety of Datalog Queries over Infinite Databases	1989	PODS	6.4188795e-05
4,370	Distributed Processing Of Logic Programs	1988	SIGMOD	6.2486359e-05
7,075	Magic-sets Transformation in Nonrecursive Systems	1992	PODS	4.842703e-05
7,591	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.702934e-05
9,738	The Space-Efficient Core of Vadalog	2019	PODS	4.2936538e-05
10,344	Circuits and Formulas for Datalog over Semirings	2025	PODS	4.1945683e-05
11,441	Deciding Boundedness of Monadic Sirups	2021	PODS	4.1945683e-05
12,904	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.1945683e-05
12,921	Semigroup techniques in recursive query optimization	1990	PODS	4.1945683e-05
12,962	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD	4.1945683e-05
12,981	A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule	1987	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.0010066783
1,196	On Computing Restricted Projections of Representative Instances	1985	PODS	0.00013403617

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,490	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011699154
3,853	Relational Specifications of Infinite Query Answers	1989	SIGMOD	6.7004022e-05
6,382	Finite Queries do not Have Effective Syntax	1995	PODS	5.0890445e-05
12,904	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.1945683e-05
1,189	Independence of Logic Database Queries and Updates	1990	PODS	0.00013441514
2,712	Query Processing in Deductive Databases with Incomplete Information	1986	SIGMOD	8.2488274e-05
2,206	A Decidable Class of Bounded Recursions	1987	PODS	9.2910236e-05
1,529	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD	0.00011496686
7,070	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS	4.843579e-05
12,962	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD	4.1945683e-05