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: 9627
Venue: VLDB
Year: 2006
Pagerank: 0.00010156479
Overall Rank: 1,636 | 88.78%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Nick Koudas (University of Toronto)
2. Chen Li (University of California Irvine)
3. Anthony K. H. Tung (National University of Singapore)
4. Rares Vernica (University of California Irvine)

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
856	How to ConQueR Why-Not Questions	2010	SIGMOD	0.00013573466
2,677	Explore-by-Example: An Automatic Query Steering Framework for Interactive Data Exploration	2014	SIGMOD	8.2682753e-05
3,935	Output Perturbation with Query Relaxation	2008	VLDB	7.0083453e-05
4,076	A Probabilistic Optimization Framework for the Empty-Answer Problem	2013	VLDB	6.9221203e-05
5,412	Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction	2011	SIGMOD	6.2272563e-05
5,667	Efficient Approximate Search on String Collections (Tutorial)	2009	VLDB	6.1279762e-05
5,873	QRelX: Generating Meaningful Queries that Provide Cardinality Assurance	2010	SIGMOD	6.0596577e-05
6,293	Query Refinement for Diversity Constraint Satisfaction	2024	VLDB	5.9247942e-05
6,389	Query Refinement for Diverse Top-k Selection	2024	SIGMOD	5.8895166e-05
6,571	Query Relaxation Using Malleable Schemas	2007	SIGMOD	5.8374223e-05
6,643	Skyline Query Processing over Joins	2011	SIGMOD	5.8152344e-05
7,654	Positive Higher-Order Queries	2010	PODS	5.5746273e-05
8,028	On the Complexity of Package Recommendation Problems	2012	PODS	5.504636e-05
9,435	In-Browser Interactive SQL Analytics with Afterburner	2017	SIGMOD	5.269408e-05
10,576	Efficient Query Repair for Aggregate Constraints	2026	VLDB	5.093636e-05
10,979	Finding Convincing Views to Endorse a Claim	2025	VLDB	5.093636e-05
11,672	Exploring Ratings in Subjective Databases	2021	SIGMOD	5.093636e-05
12,563	Stretch 'n' Shrink: Resizing Queries to User Preferences	2008	SIGMOD	5.093636e-05

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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
243	Efficient Progressive Skyline Computation	2001	VLDB	0.00023495903
308	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021787597
466	Automated Ranking of Database Query Results	2003	CIDR	0.00018014467
623	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00015684963
635	Evaluating Top-k Selection Queries	1999	VLDB	0.00015527042
656	Foundations of Preferences in Database Systems	2002	VLDB	0.00015258172
827	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00013769938
973	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012874284
1,185	Maximal Vector Computation in Large Data Sets	2005	VLDB	0.00011772712
1,360	Efficient Computation of the Skyline Cube	2005	VLDB	0.00011040203
2,306	Catching the Best Views of Skyline: A Semantic Approach Based on Decisive Subspaces	2005	VLDB	8.7755724e-05
6,426	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.8809448e-05

Semantically Similar Papers

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