DBScholar

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
h8ea47dbba1b42697
Venue
VLDB
Year
2006
Pagerank
0.00010006399
Overall Rank
1,643 | 88.96%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{koudas_vldb06,
        title = {{Relaxing Join and Selection Queries}},
        author = {Koudas, Nick and Li, Chen and Tung, Anthony K. H. and Vernica, Rares},
        journal = {PVLDB},
        series = {{VLDB} '06},
        pages = {199--210},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank Citing Paper Year Venue Pagerank
791 How to ConQueR Why-Not Questions 2010 SIGMOD 0.00013976192
2,648 Explore-by-Example: An Automatic Query Steering Framework for Interactive Data Exploration 2014 SIGMOD 8.1761271e-05
3,993 Output Perturbation with Query Relaxation 2008 VLDB 6.8685183e-05
4,165 A Probabilistic Optimization Framework for the Empty-Answer Problem 2013 VLDB 6.7675283e-05
4,327 Query Refinement for Diversity Constraint Satisfaction 2024 VLDB 6.6632438e-05
5,549 Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction 2011 SIGMOD 6.088104e-05
5,795 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 5.9926463e-05
5,972 QRelX: Generating Meaningful Queries that Provide Cardinality Assurance 2010 SIGMOD 5.9311519e-05
6,520 Query Refinement for Diverse Top-k Selection 2024 SIGMOD 5.7573717e-05
6,691 Query Relaxation Using Malleable Schemas 2007 SIGMOD 5.70723e-05
6,776 Skyline Query Processing over Joins 2011 SIGMOD 5.6847562e-05
7,805 Positive Higher-Order Queries 2010 PODS 5.4501544e-05
8,183 On the Complexity of Package Recommendation Problems 2012 PODS 5.3817332e-05
9,615 In-Browser Interactive SQL Analytics with Afterburner 2017 SIGMOD 5.1511784e-05
10,803 Efficient Query Repair for Aggregate Constraints 2026 VLDB 4.9793485e-05
11,362 Finding Convincing Views to Endorse a Claim 2025 VLDB 4.9793485e-05
11,979 Exploring Ratings in Subjective Databases 2021 SIGMOD 4.9793485e-05
12,853 Stretch 'n' Shrink: Resizing Queries to User Preferences 2008 SIGMOD 4.9793485e-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.001992968
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011405675
5 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0010679641
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045337853
256 Efficient Progressive Skyline Computation 2001 VLDB 0.00022981799
313 Shooting Stars in the Sky: An Online Algorithm for Skyline Queries 2002 VLDB 0.00021311041
474 Automated Ranking of Database Query Results 2003 CIDR 0.00017672562
638 An Optimal and Progressive Algorithm for Skyline Queries 2003 SIGMOD 0.00015338893
643 Evaluating Top-k Selection Queries 1999 VLDB 0.00015217076
671 Foundations of Preferences in Database Systems 2002 VLDB 0.00014929237
838 Minimal Probing: Supporting Expensive Predicates for Top-k Queries 2002 SIGMOD 0.00013550235
961 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.0001282305
1,213 Maximal Vector Computation in Large Data Sets 2005 VLDB 0.00011512468
1,394 Efficient Computation of the Skyline Cube 2005 VLDB 0.00010796403
2,357 Catching the Best Views of Skyline: A Semantic Approach Based on Decisive Subspaces 2005 VLDB 8.5820096e-05
6,540 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.7523628e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,136 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB
2 8,015 Optimization of Multiple-Relation Multiple-Disjunct Queries 1988 PODS
3 6,467 Output-sensitive Conjunctive Query Evaluation 2024 PODS
4 1,186 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD
5 1,596 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB
6 3,797 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD
7 143 Optimization of Nonrecursive Queries 1986 VLDB
8 4,165 A Probabilistic Optimization Framework for the Empty-Answer Problem 2013 VLDB
9 6,691 Query Relaxation Using Malleable Schemas 2007 SIGMOD
10 751 Automatic Physical Database Tuning: A Relaxation-based Approach 2005 SIGMOD