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.00020586706
Overall Rank
541 | 96.25%
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
209 OPTIMIZING DATALOG PROGRAMS (Extended Abstract) 1987 PODS 0.00034147258
256 GraphLog: a Visual Formalism for Real Life Recursion 1990 PODS 0.00030241337
907 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00015417107
1,636 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.00011058643
1,833 The Expressiveness of a Family of Finite Set Languages 1991 PODS 0.00010365844
1,872 Diagnosis of Asynchronous Discrete Event Systems: Datalog to the Rescue! 2005 PODS 0.00010255586
1,997 Decidability and Undecidability Results for Boundedness of Linear Recursive Queries 1988 PODS 9.837483e-05
2,038 Proof-Tree Transformation Theorems and Their Applications 1989 PODS 9.7062591e-05
2,227 A New Paradigm For Parallel And Distributed Rule-Processing 1990 SIGMOD 9.2521507e-05
2,473 Graph-Theoretic Methods In Database Theory 1990 PODS 8.7048914e-05
3,414 On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs 1994 PODS 7.1172834e-05
3,860 On Distributed Processibility of Datalog Queries by Decomposing Databases 1989 SIGMOD 6.6864693e-05
4,225 Why A Single Parallelization Strategy Is Not Enough In Knowledge Bases 1989 PODS 6.3396067e-05
4,367 Distributed Processing Of Logic Programs 1988 SIGMOD 6.2423944e-05
4,631 Tools for Datalog Boundedness 1991 PODS 6.0289457e-05
5,496 Answering Queries Using Views with Arithmetic Comparisons 2002 PODS 5.4741922e-05
5,927 Parallelizing Datalog Programs by Generalized Pivoting 1991 PODS 5.2666195e-05
7,594 On the First-Order Expressibility of Recursive Queries 1989 PODS 4.6983854e-05
7,823 Optimization Of Systems Of Algebraic Equations For Evaluating Datalog Queries 1987 VLDB 4.6390991e-05
11,133 The Vadalog Parallel System: Distributed Reasoning with Datalog+/- 2024 VLDB 4.1905499e-05
11,444 Deciding Boundedness of Monadic Sirups 2021 PODS 4.1905499e-05
11,975 Does Query Evaluation Tractability Help Query Containment? 2014 PODS 4.1905499e-05
12,366 Complexity and Composition of Synthesized Web Services 2008 PODS 4.1905499e-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.00021979489
612 A Time Bound on the Materialization of Some Recursively Defined Views 1985 VLDB 0.0001915957
1,167 On Computing Restricted Projections of Representative Instances 1985 PODS 0.0001354084
1,200 Data Independent Recursion in Deductive Databases 1986 PODS 0.00013342243
3,931 On The Complexity And Axiomatizability Of Consistent Database States 1984 PODS 6.6192327e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
12,931 Semigroup techniques in recursive query optimization 1990 PODS 4.1905499e-05
5,637 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB 5.3978567e-05
5,980 A Query Language for NC 1994 PODS 5.241279e-05
9,521 Implementation and Analysis of a Parallel Collection Query Language 1996 VLDB 4.3282242e-05
2,912 Convergence of Datalog over (Pre-) Semirings 2022 PODS 7.9261665e-05
6,234 Inherent Complexity of Recursive Queries (Extended Abstract) 1999 PODS 5.1387584e-05
5,754 A Parallel Processing Strategy for Evaluating Recursive Queries 1986 VLDB 5.3391931e-05
1,532 The Parallel Complexity of Simple Chain Queries (Extended Abstract) 1987 PODS 0.00011466849
459 CONVERGENCE OF SIDEWAYS QUERY EVALUATION (Extended Abstract) 1986 PODS 0.00022684266
1,552 Evaluation Of Database Recursive Logic Programs As Recurrent Function Series 1986 SIGMOD 0.00011393892