Database Paper Browser

Back to papers

Relaxing Join and Selection Queries

Summary: Introduces a lattice-based framework to relax join and selection queries until an answer appears. Nodes encode relaxation options; algorithms compute minimal-relaxation answers and efficient lattice traversal, with comprehensive evaluation on real and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
9436
Venue
VLDB
Year
2006
Pagerank
0.000103862
Overall Rank
1,830 | 87.28%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank Citing Paper Year Venue Pagerank
1,125 How to ConQueR Why-Not Questions 2010 SIGMOD 0.00013845652
3,070 Explore-by-Example: An Automatic Query Steering Framework for Interactive Data Exploration 2014 SIGMOD 7.6137064e-05
3,197 A Probabilistic Optimization Framework for the Empty-Answer Problem 2013 VLDB 7.3955829e-05
3,760 Output Perturbation with Query Relaxation 2008 VLDB 6.7805033e-05
5,073 Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction 2011 SIGMOD 5.7177424e-05
5,649 Query Refinement for Diverse Top-k Selection 2024 SIGMOD 5.3911246e-05
5,887 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 5.2879769e-05
6,095 QRelX: Generating Meaningful Queries that Provide Cardinality Assurance 2010 SIGMOD 5.2128855e-05
6,643 Query Refinement for Diversity Constraint Satisfaction 2024 VLDB 4.9786132e-05
6,713 Query Relaxation Using Malleable Schemas 2007 SIGMOD 4.951387e-05
6,921 Skyline Query Processing over Joins 2011 SIGMOD 4.8925595e-05
7,248 Positive Higher-Order Queries 2010 PODS 4.7902631e-05
7,770 On the Complexity of Package Recommendation Problems 2012 PODS 4.6562597e-05
9,289 In-Browser Interactive SQL Analytics with Afterburner 2017 SIGMOD 4.362197e-05
10,277 Efficient Query Repair for Aggregate Constraints 2026 VLDB 4.1945683e-05
10,740 Finding Convincing Views to Endorse a Claim 2025 VLDB 4.1945683e-05
11,474 Exploring Ratings in Subjective Databases 2021 SIGMOD 4.1945683e-05
12,370 Stretch 'n' Shrink: Resizing Queries to User Preferences 2008 SIGMOD 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Rank Cited Paper Year Venue Pagerank
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0032169493
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016162015
7 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0015496097
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083378538
262 Efficient Progressive Skyline Computation 2001 VLDB 0.00029987552
386 Shooting Stars in the Sky: An Online Algorithm for Skyline Queries 2002 VLDB 0.00024768022
427 Automated Ranking of Database Query Results 2003 CIDR 0.0002352637
707 Foundations of Preferences in Database Systems 2002 VLDB 0.00017782998
749 An Optimal and Progressive Algorithm for Skyline Queries 2003 SIGMOD 0.00017228334
805 Evaluating Top-k Selection Queries 1999 VLDB 0.00016437265
1,096 Minimal Probing: Supporting Expensive Predicates for Top-k Queries 2002 SIGMOD 0.00014120512
1,262 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.00012986539
1,473 Maximal Vector Computation in Large Data Sets 2005 VLDB 0.00011828508
1,575 Efficient Computation of the Skyline Cube 2005 VLDB 0.00011286884
2,696 Catching the Best Views of Skyline: A Semantic Approach Based on Decisive Subspaces 2005 VLDB 8.2814799e-05
6,500 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.0381573e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,044 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB 9.6953608e-05
7,824 Optimization of Multiple-Relation Multiple-Disjunct Queries 1988 PODS 4.6418459e-05
8,966 Output-sensitive Conjunctive Query Evaluation 2024 PODS 4.4193184e-05
1,619 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.00011111678
2,275 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 9.1262202e-05
4,738 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD 5.9600502e-05
143 Optimization of Nonrecursive Queries 1986 VLDB 0.00041510555
3,197 A Probabilistic Optimization Framework for the Empty-Answer Problem 2013 VLDB 7.3955829e-05
6,713 Query Relaxation Using Malleable Schemas 2007 SIGMOD 4.951387e-05
1,017 Automatic Physical Database Tuning: A Relaxation-based Approach 2005 SIGMOD 0.00014634307