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.00015373336
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
298	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00021830158
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021210493
979	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012723733
1,682	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	9.8804595e-05
1,830	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.5453747e-05
1,921	The Expressiveness of a Family of Finite Set Languages	1991	PODS	9.3737469e-05
2,026	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.1626332e-05
2,474	Diagnosis of Asynchronous Discrete Event Systems: Datalog to the Rescue!	2005	PODS	8.4083096e-05
3,021	Graph-Theoretic Methods In Database Theory	1990	PODS	7.741152e-05
3,137	A New Paradigm For Parallel And Distributed Rule-Processing	1990	SIGMOD	7.6044211e-05
3,316	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.4342107e-05
4,206	Distributed Processing Of Logic Programs	1988	SIGMOD	6.7322742e-05
4,422	On Distributed Processibility of Datalog Queries by Decomposing Databases	1989	SIGMOD	6.6037547e-05
4,557	Why A Single Parallelization Strategy Is Not Enough In Knowledge Bases	1989	PODS	6.5347712e-05
4,714	Tools for Datalog Boundedness	1991	PODS	6.4537538e-05
5,496	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.1058078e-05
5,964	Parallelizing Datalog Programs by Generalized Pivoting	1991	PODS	5.9303286e-05
8,142	On the First-Order Expressibility of Recursive Queries	1989	PODS	5.390003e-05
8,488	Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries	1987	VLDB	5.3305613e-05
11,660	The Vadalog Parallel System: Distributed Reasoning with Datalog+/-	2024	VLDB	4.9769913e-05
11,952	Deciding Boundedness of Monadic Sirups	2021	PODS	4.9769913e-05
12,462	Does Query Evaluation Tractability Help Query Containment?	2014	PODS	4.9769913e-05
12,847	Complexity and Composition of Synthesized Web Services	2008	PODS	4.9769913e-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
914	Horn Clauses and the Fixpoint Query Hierarchy	1982	PODS	0.00013109036
946	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00012930818
1,201	Data Independent Recursion in Deductive Databases	1986	PODS	0.00011555372
1,455	On Computing Restricted Projections of Representative Instances	1985	PODS	0.00010594127
4,756	On The Complexity And Axiomatizability Of Consistent Database States	1984	PODS	6.4305861e-05

Semantically Similar Papers

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