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: 765
Venue: PODS
Year: 1986
Pagerank: 0.00015712636
Overall Rank: 616 | 95.78%
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
300	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00022046803
313	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.0002168869
953	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012997935
1,653	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	0.000101081
1,788	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.7653696e-05
1,864	The Expressiveness of a Family of Finite Set Languages	1991	PODS	9.5928463e-05
1,970	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.3746238e-05
2,425	Diagnosis of Asynchronous Discrete Event Systems: Datalog to the Rescue!	2005	PODS	8.6005163e-05
2,957	Graph-Theoretic Methods In Database Theory	1990	PODS	7.9200375e-05
3,076	A New Paradigm For Parallel And Distributed Rule-Processing	1990	SIGMOD	7.7817058e-05
3,245	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.60327e-05
4,121	Distributed Processing Of Logic Programs	1988	SIGMOD	6.8889854e-05
4,343	On Distributed Processibility of Datalog Queries by Decomposing Databases	1989	SIGMOD	6.7529086e-05
4,464	Why A Single Parallelization Strategy Is Not Enough In Knowledge Bases	1989	PODS	6.6860087e-05
4,615	Tools for Datalog Boundedness	1991	PODS	6.6050069e-05
5,361	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.2484907e-05
5,850	Parallelizing Datalog Programs by Generalized Pivoting	1991	PODS	6.0664613e-05
7,972	On the First-Order Expressibility of Recursive Queries	1989	PODS	5.5160399e-05
8,314	Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries	1987	VLDB	5.4554917e-05
11,336	The Vadalog Parallel System: Distributed Reasoning with Datalog+/-	2024	VLDB	5.093636e-05
11,639	Deciding Boundedness of Monadic Sirups	2021	PODS	5.093636e-05
12,165	Does Query Evaluation Tractability Help Query Containment?	2014	PODS	5.093636e-05
12,551	Complexity and Composition of Synthesized Web Services	2008	PODS	5.093636e-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
888	Horn Clauses and the Fixpoint Query Hierarchy	1982	PODS	0.00013402577
916	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00013224702
1,173	Data Independent Recursion in Deductive Databases	1986	PODS	0.00011822695
1,417	On Computing Restricted Projections of Representative Instances	1985	PODS	0.00010839353
4,659	On The Complexity And Axiomatizability Of Consistent Database States	1984	PODS	6.5797982e-05

Semantically Similar Papers

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