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.00015380574
Overall Rank: 633 | 95.75%
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
297	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00021840374
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021220438
979	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012729663
1,682	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	9.8850863e-05
1,830	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.5498891e-05
1,919	The Expressiveness of a Family of Finite Set Languages	1991	PODS	9.3781849e-05
2,024	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.166955e-05
2,473	Diagnosis of Asynchronous Discrete Event Systems: Datalog to the Rescue!	2005	PODS	8.4120524e-05
3,020	Graph-Theoretic Methods In Database Theory	1990	PODS	7.7448163e-05
3,136	A New Paradigm For Parallel And Distributed Rule-Processing	1990	SIGMOD	7.6080212e-05
3,315	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.4376793e-05
4,205	Distributed Processing Of Logic Programs	1988	SIGMOD	6.735459e-05
4,420	On Distributed Processibility of Datalog Queries by Decomposing Databases	1989	SIGMOD	6.6068305e-05
4,556	Why A Single Parallelization Strategy Is Not Enough In Knowledge Bases	1989	PODS	6.5378593e-05
4,712	Tools for Datalog Boundedness	1991	PODS	6.4568103e-05
5,492	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.1086968e-05
5,962	Parallelizing Datalog Programs by Generalized Pivoting	1991	PODS	5.9331349e-05
8,136	On the First-Order Expressibility of Recursive Queries	1989	PODS	5.3925529e-05
8,481	Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries	1987	VLDB	5.3330859e-05
11,654	The Vadalog Parallel System: Distributed Reasoning with Datalog+/-	2024	VLDB	4.9793485e-05
11,946	Deciding Boundedness of Monadic Sirups	2021	PODS	4.9793485e-05
12,456	Does Query Evaluation Tractability Help Query Containment?	2014	PODS	4.9793485e-05
12,841	Complexity and Composition of Synthesized Web Services	2008	PODS	4.9793485e-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
913	Horn Clauses and the Fixpoint Query Hierarchy	1982	PODS	0.00013115161
946	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00012936921
1,201	Data Independent Recursion in Deductive Databases	1986	PODS	0.00011560838
1,455	On Computing Restricted Projections of Representative Instances	1985	PODS	0.00010599099
4,753	On The Complexity And Axiomatizability Of Consistent Database States	1984	PODS	6.4336287e-05

Semantically Similar Papers

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