The Parallel Complexity of Simple Chain Queries (Extended Abstract)

Summary: Classifies the parallel complexity of simple chain DATALOG queries (variants of transitive closure), proving some variants are in NC while others are P-complete. Provides a taxonomy to guide which recursive DATALOG programs admit efficient massively-parallel evaluation and compiler/implementation strategies. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 794
Venue: PODS
Year: 1987
Pagerank: 9.4146943e-05
Overall Rank: 1,957 | 86.58%
DOI: 10.1145/28659.28682

Incoming Non-self Citations Over Time

Authors

1. Foto Afrati (National Technical University of Athens)
2. Christos H. Papadimitriou (National Technical University of Athens; Stanford University)

BibTeX Citation

@inproceedings{afrati_pods87,
        address = {New York, NY, USA},
        series = {{PODS} '87},
        title = {{The Parallel Complexity of Simple Chain Queries (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/28659.28682},
        doi = {10.1145/28659.28682},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Afrati, Foto and Papadimitriou, Christos H.},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,653	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	0.000101081
1,856	Automata Theory for Database Theoreticians	1989	PODS	9.6053834e-05
2,247	A Framework for the Parallel Processing of Datalog Queries	1990	SIGMOD	8.8713691e-05
2,957	Graph-Theoretic Methods In Database Theory	1990	PODS	7.9200375e-05
4,121	Distributed Processing Of Logic Programs	1988	SIGMOD	6.8889854e-05
4,464	Why A Single Parallelization Strategy Is Not Enough In Knowledge Bases	1989	PODS	6.6860087e-05
5,850	Parallelizing Datalog Programs by Generalized Pivoting	1991	PODS	6.0664613e-05
6,690	Can Datalog be approximated?	1994	PODS	5.8012926e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,207	Communication Steps for Parallel Query Processing	2013	PODS
2	8,775	A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering	1990	VLDB
3	616	Parallel Evaluation of Recursive Rule Queries	1986	PODS
4	4,773	Parallel Processing of Recursive Queries in Distributed Architectures	1989	VLDB
5	2,247	A Framework for the Parallel Processing of Datalog Queries	1990	SIGMOD
6	8,569	The Power of Methods With Parallel Semantics	1991	VLDB
7	9,662	Implementation and Analysis of a Parallel Collection Query Language	1996	VLDB
8	414	On the Complexity of Database Queries (Extended Abstract)	1997	PODS
9	4,343	On Distributed Processibility of Datalog Queries by Decomposing Databases	1989	SIGMOD
10	954	Parallel Evaluation of Conjunctive Queries	2011	PODS