Database Paper Browser

Back to papers

Parallel Evaluation of Conjunctive Queries

Summary: Propose a simple synchronous parallel model measuring global synchronization rounds to analyze conjunctive-query evaluation on massive clusters. Characterize one-round computable queries as "tall-flat" (strict subset of hierarchical), give a one-round algorithm and matching impossibility for others, with extensions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1551
Venue
PODS
Year
2011
Pagerank
0.00013968198
Overall Rank
1,110 | 92.28%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank Citing Paper Year Venue Pagerank
772 Answering Conjunctive Queries under Updates 2017 PODS 0.00016876498
1,056 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.0001441128
1,308 Upper and Lower Bounds on the Cost of a Map-Reduce Computation 2013 VLDB 0.00012661651
1,334 SkewTune: Mitigating Skew in MapReduce Applications 2012 SIGMOD 0.0001250413
1,411 Communication Steps for Parallel Query Processing 2013 PODS 0.0001212565
1,939 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00010025655
2,336 Optimizing Graph Algorithms on Pregel-like Systems 2014 VLDB 9.0109891e-05
2,674 Minimal MapReduce Algorithms 2013 SIGMOD 8.3328645e-05
2,849 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 8.0195487e-05
3,781 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 6.7723513e-05
3,833 Output-optimal Parallel Algorithms for Similarity Joins 2017 PODS 6.7173578e-05
4,205 Association Rules with Graph Patterns 2015 VLDB 6.3597474e-05
4,708 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 5.980172e-05
5,639 Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins 2021 PODS 5.393897e-05
7,017 Query Evaluation by Circuits 2022 PODS 4.8603097e-05
7,122 Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries 2020 PODS 4.8252188e-05
7,413 On Scale Independence for Querying Big Data 2014 PODS 4.7358047e-05
7,822 Weaker Forms of Monotonicity for Declarative Networking: a More Fine-grained Answer to the CALM-conjecture 2014 PODS 4.6426494e-05
8,215 Parallel-Correctness and Transferability for Conjunctive Queries 2015 PODS 4.5577562e-05
9,578 Querying Shared Data with Security Heterogeneity 2020 SIGMOD 4.3248081e-05
10,911 Topology-aware Parallel Joins 2024 PODS 4.1945683e-05
11,436 Algorithms for a Topology-aware Massively Parallel Computation Model 2021 PODS 4.1945683e-05
11,437 Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins 2021 PODS 4.1945683e-05
11,831 Logical Aspects of Massively Parallel and Distributed Systems 2016 PODS 4.1945683e-05
11,882 Parallel Evaluation of Multi-Semi-Joins 2016 VLDB 4.1945683e-05
12,097 Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory) 2013 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

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
22 SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets 2008 VLDB 0.0008456613
70 Hive - A Warehousing Solution Over a Map-Reduce Framework 2009 VLDB 0.00059533166
109 Dremel: Interactive Analysis of Web-Scale Datasets 2010 VLDB 0.00048186983
780 Building a High-Level Dataflow System on top of Map-Reduce: The Pig Experience 2009 VLDB 0.00016775082
1,915 Handling Data Skew in Parallel Joins in Shared-Nothing Systems 2008 SIGMOD 0.00010104123
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,849 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 8.0195487e-05
4,288 Parallel Processing of Recursive Queries in Distributed Architectures 1989 VLDB 6.2891396e-05
2,079 A Framework for the Parallel Processing of Datalog Queries 1990 SIGMOD 9.5979932e-05
2,212 Skew in Parallel Query Processing 2014 PODS 9.2771827e-05
4,689 Algorithmic Aspects of Parallel Query Processing 2018 SIGMOD 5.9980099e-05
9,520 Implementation and Analysis of a Parallel Collection Query Language 1996 VLDB 4.3323764e-05
11,831 Logical Aspects of Massively Parallel and Distributed Systems 2016 PODS 4.1945683e-05
9,305 Parallelizing Query Optimization on Shared-Nothing Architectures 2016 VLDB 4.3577129e-05
1,939 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00010025655
8,215 Parallel-Correctness and Transferability for Conjunctive Queries 2015 PODS 4.5577562e-05