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: hc558d6959150ed87
Venue: PODS
Year: 1986
Pagerank: 0.00015323882
Overall Rank: 637 | 95.74%
DOI: 10.1145/6012.15421

Incoming Non-self Citations Over Time

Authors

1. Stavros S. Cosmadakis (IBM)
2. Paris C. Kanellakis (Brown University)

BibTeX Citation

@inproceedings{cosmadakis_pods86,
        address = {New York, NY, USA},
        series = {{PODS} '86},
        title = {{Parallel Evaluation of Recursive Rule Queries}},
        url = {https://dl.acm.org/doi/10.1145/6012.15421},
        doi = {10.1145/6012.15421},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cosmadakis, Stavros S. and Kanellakis, Paris C.},
        year = {1986}
}

Incoming Citations (Sorted by Pagerank)

Showing 23 of 23 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
299	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00021766741
319	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021142713
981	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012688969
1,688	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	9.8481921e-05
1,842	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.5141238e-05
1,934	The Expressiveness of a Family of Finite Set Languages	1991	PODS	9.3427942e-05
2,038	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.1328477e-05
2,483	Diagnosis of Asynchronous Discrete Event Systems: Datalog to the Rescue!	2005	PODS	8.3820186e-05
3,030	Graph-Theoretic Methods In Database Theory	1990	PODS	7.7156987e-05
3,147	A New Paradigm For Parallel And Distributed Rule-Processing	1990	SIGMOD	7.5793335e-05
3,326	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.4103766e-05
4,224	Distributed Processing Of Logic Programs	1988	SIGMOD	6.710075e-05
4,443	On Distributed Processibility of Datalog Queries by Decomposing Databases	1989	SIGMOD	6.5820613e-05
4,575	Why A Single Parallelization Strategy Is Not Enough In Knowledge Bases	1989	PODS	6.5132348e-05
4,728	Tools for Datalog Boundedness	1991	PODS	6.4324136e-05
5,516	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.0859896e-05
5,971	Parallelizing Datalog Programs by Generalized Pivoting	1991	PODS	5.9115526e-05
8,160	On the First-Order Expressibility of Recursive Queries	1989	PODS	5.3722218e-05
8,503	Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries	1987	VLDB	5.3129351e-05
11,707	The Vadalog Parallel System: Distributed Reasoning with Datalog+/-	2024	VLDB	4.9605343e-05
11,996	Deciding Boundedness of Monadic Sirups	2021	PODS	4.9605343e-05
12,505	Does Query Evaluation Tractability Help Query Containment?	2014	PODS	4.9605343e-05
12,890	Complexity and Composition of Synthesized Web Services	2008	PODS	4.9605343e-05

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
916	Horn Clauses and the Fixpoint Query Hierarchy	1982	PODS	0.00013066729
950	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00012888761
1,204	Data Independent Recursion in Deductive Databases	1986	PODS	0.00011517335
1,459	On Computing Restricted Projections of Representative Instances	1985	PODS	0.00010559266
4,774	On The Complexity And Axiomatizability Of Consistent Database States	1984	PODS	6.4094211e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,453	Semigroup techniques in recursive query optimization	1990	PODS
2	6,894	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB
3	9,878	Implementation and Analysis of a Parallel Collection Query Language	1996	VLDB
4	7,254	A Query Language for NC	1994	PODS
5	2,638	Convergence of Datalog over (Pre-) Semirings	2022	PODS
6	6,764	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
7	5,701	A Parallel Processing Strategy for Evaluating Recursive Queries	1986	VLDB
8	2,016	The Parallel Complexity of Simple Chain Queries (Extended Abstract)	1987	PODS
9	1,082	CONVERGENCE OF SIDEWAYS QUERY EVALUATION (Extended Abstract)	1986	PODS
10	2,112	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD