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
9437
Venue
VLDB
Year
2006
Pagerank
0.0001037611
Overall Rank
1,830 | 87.29%
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,124 How to ConQueR Why-Not Questions 2010 SIGMOD 0.00013832959
3,076 Explore-by-Example: An Automatic Query Steering Framework for Interactive Data Exploration 2014 SIGMOD 7.6063803e-05
3,204 A Probabilistic Optimization Framework for the Empty-Answer Problem 2013 VLDB 7.3884503e-05
3,769 Output Perturbation with Query Relaxation 2008 VLDB 6.7744696e-05
5,071 Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction 2011 SIGMOD 5.7122974e-05
5,660 Query Refinement for Diverse Top-k Selection 2024 SIGMOD 5.3859487e-05
5,892 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 5.2829767e-05
6,096 QRelX: Generating Meaningful Queries that Provide Cardinality Assurance 2010 SIGMOD 5.2079002e-05
6,644 Query Refinement for Diversity Constraint Satisfaction 2024 VLDB 4.973836e-05
6,714 Query Relaxation Using Malleable Schemas 2007 SIGMOD 4.9466377e-05
6,923 Skyline Query Processing over Joins 2011 SIGMOD 4.8878659e-05
7,244 Positive Higher-Order Queries 2010 PODS 4.7856771e-05
7,768 On the Complexity of Package Recommendation Problems 2012 PODS 4.6523419e-05
9,294 In-Browser Interactive SQL Analytics with Afterburner 2017 SIGMOD 4.3580163e-05
10,289 Efficient Query Repair for Aggregate Constraints 2026 VLDB 4.1905499e-05
10,747 Finding Convincing Views to Endorse a Claim 2025 VLDB 4.1905499e-05
11,478 Exploring Ratings in Subjective Databases 2021 SIGMOD 4.1905499e-05
12,378 Stretch 'n' Shrink: Resizing Queries to User Preferences 2008 SIGMOD 4.1905499e-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.0032118946
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016113151
8 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0015436578
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083300888
262 Efficient Progressive Skyline Computation 2001 VLDB 0.00029962961
386 Shooting Stars in the Sky: An Online Algorithm for Skyline Queries 2002 VLDB 0.00024740283
427 Automated Ranking of Database Query Results 2003 CIDR 0.0002350378
706 Foundations of Preferences in Database Systems 2002 VLDB 0.00017777858
746 An Optimal and Progressive Algorithm for Skyline Queries 2003 SIGMOD 0.00017212135
802 Evaluating Top-k Selection Queries 1999 VLDB 0.00016440813
1,093 Minimal Probing: Supporting Expensive Predicates for Top-k Queries 2002 SIGMOD 0.00014123221
1,207 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.0001327437
1,471 Maximal Vector Computation in Large Data Sets 2005 VLDB 0.0001181903
1,576 Efficient Computation of the Skyline Cube 2005 VLDB 0.00011278557
2,699 Catching the Best Views of Skyline: A Semantic Approach Based on Decisive Subspaces 2005 VLDB 8.2758509e-05
6,496 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.0327729e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,051 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB 9.6871984e-05
7,829 Optimization of Multiple-Relation Multiple-Disjunct Queries 1988 PODS 4.6373918e-05
8,972 Output-sensitive Conjunctive Query Evaluation 2024 PODS 4.4150824e-05
1,621 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.00011105663
2,281 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 9.122455e-05
4,734 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD 5.9553181e-05
144 Optimization of Nonrecursive Queries 1986 VLDB 0.00041430126
3,204 A Probabilistic Optimization Framework for the Empty-Answer Problem 2013 VLDB 7.3884503e-05
6,714 Query Relaxation Using Malleable Schemas 2007 SIGMOD 4.9466377e-05
1,018 Automatic Physical Database Tuning: A Relaxation-based Approach 2005 SIGMOD 0.00014626746