Database Paper Browser

Back to papers

Parallel Evaluation of Recursive Rule Queries

Summary: Analyzes parallel complexity of recursive rule queries, re-proves Sagiv's decidability for FO-equivalence, and proves a 'gap' theorem. Characterizes two classes in NC via O(log) iterations of a FO operator and gives syntactically tight PTIME queries that are logspace-complete and resist such parallelization. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
766
Venue
PODS
Year
1986
Pagerank
0.0002068591
Overall Rank
537 | 96.27%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 23 of 23 citing papers.

Rank Citing Paper Year Venue Pagerank
200 OPTIMIZING DATALOG PROGRAMS (Extended Abstract) 1987 PODS 0.00035012858
256 GraphLog: a Visual Formalism for Real Life Recursion 1990 PODS 0.00030259041
909 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00015428222
1,712 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.00010804573
1,835 The Expressiveness of a Family of Finite Set Languages 1991 PODS 0.00010375854
1,865 Diagnosis of Asynchronous Discrete Event Systems: Datalog to the Rescue! 2005 PODS 0.00010275334
1,991 Decidability and Undecidability Results for Boundedness of Linear Recursive Queries 1988 PODS 9.84713e-05
2,036 Proof-Tree Transformation Theorems and Their Applications 1989 PODS 9.714898e-05
2,221 A New Paradigm For Parallel And Distributed Rule-Processing 1990 SIGMOD 9.2614541e-05
2,474 Graph-Theoretic Methods In Database Theory 1990 PODS 8.7135761e-05
3,413 On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs 1994 PODS 7.1240395e-05
3,855 On Distributed Processibility of Datalog Queries by Decomposing Databases 1989 SIGMOD 6.6953401e-05
4,222 Why A Single Parallelization Strategy Is Not Enough In Knowledge Bases 1989 PODS 6.3480169e-05
4,370 Distributed Processing Of Logic Programs 1988 SIGMOD 6.2486359e-05
4,631 Tools for Datalog Boundedness 1991 PODS 6.0347472e-05
5,471 Answering Queries Using Views with Arithmetic Comparisons 2002 PODS 5.4888202e-05
5,925 Parallelizing Datalog Programs by Generalized Pivoting 1991 PODS 5.2717743e-05
7,591 On the First-Order Expressibility of Recursive Queries 1989 PODS 4.702934e-05
7,817 Optimization Of Systems Of Algebraic Equations For Evaluating Datalog Queries 1987 VLDB 4.6435605e-05
11,130 The Vadalog Parallel System: Distributed Reasoning with Datalog+/- 2024 VLDB 4.1945683e-05
11,441 Deciding Boundedness of Monadic Sirups 2021 PODS 4.1945683e-05
11,967 Does Query Evaluation Tractability Help Query Containment? 2014 PODS 4.1945683e-05
12,358 Complexity and Composition of Synthesized Web Services 2008 PODS 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank Cited Paper Year Venue Pagerank
490 Horn Clauses and the Fixpoint Query Hierarchy 1982 PODS 0.00022016773
617 A Time Bound on the Materialization of Some Recursively Defined Views 1985 VLDB 0.00019090876
1,185 Data Independent Recursion in Deductive Databases 1986 PODS 0.00013445831
1,196 On Computing Restricted Projections of Representative Instances 1985 PODS 0.00013403617
3,917 On The Complexity And Axiomatizability Of Consistent Database States 1984 PODS 6.6328189e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
12,921 Semigroup techniques in recursive query optimization 1990 PODS 4.1945683e-05
5,628 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB 5.4030815e-05
9,520 Implementation and Analysis of a Parallel Collection Query Language 1996 VLDB 4.3323764e-05
5,974 A Query Language for NC 1994 PODS 5.246329e-05
2,907 Convergence of Datalog over (Pre-) Semirings 2022 PODS 7.933806e-05
6,236 Inherent Complexity of Recursive Queries (Extended Abstract) 1999 PODS 5.1436959e-05
5,743 A Parallel Processing Strategy for Evaluating Recursive Queries 1986 VLDB 5.3442345e-05
1,545 The Parallel Complexity of Simple Chain Queries (Extended Abstract) 1987 PODS 0.0001144821
452 CONVERGENCE OF SIDEWAYS QUERY EVALUATION (Extended Abstract) 1986 PODS 0.00022799064
1,529 Evaluation Of Database Recursive Logic Programs As Recurrent Function Series 1986 SIGMOD 0.00011496686