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.00013871948
Overall Rank
1,114 | 92.26%
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
770 Answering Conjunctive Queries under Updates 2017 PODS 0.0001686092
1,054 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00014397587
1,312 Upper and Lower Bounds on the Cost of a Map-Reduce Computation 2013 VLDB 0.00012650678
1,339 SkewTune: Mitigating Skew in MapReduce Applications 2012 SIGMOD 0.00012492978
1,411 Communication Steps for Parallel Query Processing 2013 PODS 0.00012118832
1,938 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00010025547
2,332 Optimizing Graph Algorithms on Pregel-like Systems 2014 VLDB 9.0173968e-05
2,714 Minimal MapReduce Algorithms 2013 SIGMOD 8.2426646e-05
2,856 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 8.0120856e-05
3,785 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 6.7658346e-05
3,831 Output-optimal Parallel Algorithms for Similarity Joins 2017 PODS 6.7146681e-05
4,709 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 5.9744219e-05
5,120 Association Rules with Graph Patterns 2015 VLDB 5.6754325e-05
5,650 Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins 2021 PODS 5.3887172e-05
7,017 Query Evaluation by Circuits 2022 PODS 4.8556471e-05
7,117 Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries 2020 PODS 4.8205884e-05
7,410 On Scale Independence for Querying Big Data 2014 PODS 4.7320027e-05
7,826 Weaker Forms of Monotonicity for Declarative Networking: a More Fine-grained Answer to the CALM-conjecture 2014 PODS 4.6381971e-05
8,213 Parallel-Correctness and Transferability for Conjunctive Queries 2015 PODS 4.5533861e-05
9,577 Querying Shared Data with Security Heterogeneity 2020 SIGMOD 4.3206631e-05
10,915 Topology-aware Parallel Joins 2024 PODS 4.1905499e-05
11,439 Algorithms for a Topology-aware Massively Parallel Computation Model 2021 PODS 4.1905499e-05
11,440 Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins 2021 PODS 4.1905499e-05
11,839 Logical Aspects of Massively Parallel and Distributed Systems 2016 PODS 4.1905499e-05
11,890 Parallel Evaluation of Multi-Semi-Joins 2016 VLDB 4.1905499e-05
12,105 Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory) 2013 VLDB 4.1905499e-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.00084679526
70 Hive - A Warehousing Solution Over a Map-Reduce Framework 2009 VLDB 0.00059744625
109 Dremel: Interactive Analysis of Web-Scale Datasets 2010 VLDB 0.00048217028
776 Building a High-Level Dataflow System on top of Map-Reduce: The Pig Experience 2009 VLDB 0.00016765694
1,919 Handling Data Skew in Parallel Joins in Shared-Nothing Systems 2008 SIGMOD 0.00010097452
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,856 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 8.0120856e-05
4,320 Parallel Processing of Recursive Queries in Distributed Architectures 1989 VLDB 6.2822407e-05
2,087 A Framework for the Parallel Processing of Datalog Queries 1990 SIGMOD 9.5715836e-05
2,216 Skew in Parallel Query Processing 2014 PODS 9.2693784e-05
4,641 Algorithmic Aspects of Parallel Query Processing 2018 SIGMOD 6.0215749e-05
9,521 Implementation and Analysis of a Parallel Collection Query Language 1996 VLDB 4.3282242e-05
11,839 Logical Aspects of Massively Parallel and Distributed Systems 2016 PODS 4.1905499e-05
9,312 Parallelizing Query Optimization on Shared-Nothing Architectures 2016 VLDB 4.353536e-05
1,938 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00010025547
8,213 Parallel-Correctness and Transferability for Conjunctive Queries 2015 PODS 4.5533861e-05