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.00013342243
Overall Rank: 1,200 | 91.67%
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
541	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00020586706
1,611	One-Sided Recursions	1987	PODS	0.00011146101
1,687	Automata Theory for Database Theoreticians	1989	PODS	0.0001090256
1,905	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD	0.00010142772
1,997	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.837483e-05
2,212	A Decidable Class of Bounded Recursions	1987	PODS	9.2818302e-05
3,860	On Distributed Processibility of Datalog Queries by Decomposing Databases	1989	SIGMOD	6.6864693e-05
4,138	Safety of Datalog Queries over Infinite Databases	1989	PODS	6.4127061e-05
4,367	Distributed Processing Of Logic Programs	1988	SIGMOD	6.2423944e-05
7,069	Magic-sets Transformation in Nonrecursive Systems	1992	PODS	4.8380576e-05
7,594	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.6983854e-05
9,737	The Space-Efficient Core of Vadalog	2019	PODS	4.2895392e-05
10,356	Circuits and Formulas for Datalog over Semirings	2025	PODS	4.1905499e-05
11,444	Deciding Boundedness of Monadic Sirups	2021	PODS	4.1905499e-05
12,914	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.1905499e-05
12,931	Semigroup techniques in recursive query optimization	1990	PODS	4.1905499e-05
12,972	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD	4.1905499e-05
12,992	A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule	1987	SIGMOD	4.1905499e-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.00099936325
1,167	On Computing Restricted Projections of Representative Instances	1985	PODS	0.0001354084

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,489	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011687823
6,380	Finite Queries do not Have Effective Syntax	1995	PODS	5.0841675e-05
3,856	Relational Specifications of Infinite Query Answers	1989	SIGMOD	6.6938945e-05
12,914	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.1905499e-05
1,189	Independence of Logic Database Queries and Updates	1990	PODS	0.0001342924
2,715	Query Processing in Deductive Databases with Incomplete Information	1986	SIGMOD	8.2411079e-05
2,212	A Decidable Class of Bounded Recursions	1987	PODS	9.2818302e-05
1,552	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD	0.00011393892
7,066	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS	4.8389293e-05
12,972	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD	4.1905499e-05