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.00010001728
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.00013970743
2,648 Explore-by-Example: An Automatic Query Steering Framework for Interactive Data Exploration 2014 SIGMOD 8.172373e-05
3,993 Output Perturbation with Query Relaxation 2008 VLDB 6.8652975e-05
4,165 A Probabilistic Optimization Framework for the Empty-Answer Problem 2013 VLDB 6.7643246e-05
4,327 Query Refinement for Diversity Constraint Satisfaction 2024 VLDB 6.6600895e-05
5,551 Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction 2011 SIGMOD 6.0852227e-05
5,797 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 5.9898117e-05
5,972 QRelX: Generating Meaningful Queries that Provide Cardinality Assurance 2010 SIGMOD 5.9283441e-05
6,522 Query Refinement for Diverse Top-k Selection 2024 SIGMOD 5.7546462e-05
6,695 Query Relaxation Using Malleable Schemas 2007 SIGMOD 5.7045295e-05
6,781 Skyline Query Processing over Joins 2011 SIGMOD 5.6820651e-05
7,812 Positive Higher-Order Queries 2010 PODS 5.4475778e-05
8,190 On the Complexity of Package Recommendation Problems 2012 PODS 5.3791856e-05
9,622 In-Browser Interactive SQL Analytics with Afterburner 2017 SIGMOD 5.1487399e-05
10,813 Efficient Query Repair for Aggregate Constraints 2026 VLDB 4.9769913e-05
11,369 Finding Convincing Views to Endorse a Claim 2025 VLDB 4.9769913e-05
11,985 Exploring Ratings in Subjective Databases 2021 SIGMOD 4.9769913e-05
12,859 Stretch 'n' Shrink: Resizing Queries to User Preferences 2008 SIGMOD 4.9769913e-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.0019923528
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011402175
5 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0010679903
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045319457
256 Efficient Progressive Skyline Computation 2001 VLDB 0.00022971009
313 Shooting Stars in the Sky: An Online Algorithm for Skyline Queries 2002 VLDB 0.00021301023
474 Automated Ranking of Database Query Results 2003 CIDR 0.00017665834
638 An Optimal and Progressive Algorithm for Skyline Queries 2003 SIGMOD 0.00015331662
643 Evaluating Top-k Selection Queries 1999 VLDB 0.0001521012
672 Foundations of Preferences in Database Systems 2002 VLDB 0.00014922272
840 Minimal Probing: Supporting Expensive Predicates for Top-k Queries 2002 SIGMOD 0.00013544367
962 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.00012818013
1,214 Maximal Vector Computation in Large Data Sets 2005 VLDB 0.00011507029
1,395 Efficient Computation of the Skyline Cube 2005 VLDB 0.00010791312
2,358 Catching the Best Views of Skyline: A Semantic Approach Based on Decisive Subspaces 2005 VLDB 8.5779705e-05
6,542 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.7496415e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,138 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB
2 8,020 Optimization of Multiple-Relation Multiple-Disjunct Queries 1988 PODS
3 6,469 Output-sensitive Conjunctive Query Evaluation 2024 PODS
4 1,185 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,800 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,695 Query Relaxation Using Malleable Schemas 2007 SIGMOD
10 751 Automatic Physical Database Tuning: A Relaxation-based Approach 2005 SIGMOD