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: 9.9699016e-05
Overall Rank: 1,649 | 88.95%
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
790	How to ConQueR Why-Not Questions	2010	SIGMOD	0.00013929166
2,656	Explore-by-Example: An Automatic Query Steering Framework for Interactive Data Exploration	2014	SIGMOD	8.1460698e-05
4,008	Output Perturbation with Query Relaxation	2008	VLDB	6.8439132e-05
4,184	A Probabilistic Optimization Framework for the Empty-Answer Problem	2013	VLDB	6.7419575e-05
4,347	Query Refinement for Diversity Constraint Satisfaction	2024	VLDB	6.6380671e-05
5,566	Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction	2011	SIGMOD	6.0651335e-05
5,811	Efficient Approximate Search on String Collections (Tutorial)	2009	VLDB	5.9701598e-05
5,955	QRelX: Generating Meaningful Queries that Provide Cardinality Assurance	2010	SIGMOD	5.9169341e-05
6,534	Query Refinement for Diverse Top-k Selection	2024	SIGMOD	5.7356177e-05
6,692	Query Relaxation Using Malleable Schemas	2007	SIGMOD	5.6910171e-05
6,796	Skyline Query Processing over Joins	2011	SIGMOD	5.6632766e-05
7,829	Positive Higher-Order Queries	2010	PODS	5.4296075e-05
8,207	On the Complexity of Package Recommendation Problems	2012	PODS	5.3613986e-05
9,652	In-Browser Interactive SQL Analytics with Afterburner	2017	SIGMOD	5.1317151e-05
10,874	Efficient Query Repair for Aggregate Constraints	2026	VLDB	4.9605343e-05
11,422	Finding Convincing Views to Endorse a Claim	2025	VLDB	4.9605343e-05
12,029	Exploring Ratings in Subjective Databases	2021	SIGMOD	4.9605343e-05
12,902	Stretch 'n' Shrink: Resizing Queries to User Preferences	2008	SIGMOD	4.9605343e-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.0019892478
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011386412
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010688884
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045231517
258	Efficient Progressive Skyline Computation	2001	VLDB	0.00022896896
317	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021232519
478	Automated Ranking of Database Query Results	2003	CIDR	0.00017612826
640	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00015286314
647	Evaluating Top-k Selection Queries	1999	VLDB	0.00015165562
673	Foundations of Preferences in Database Systems	2002	VLDB	0.00014877371
840	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00013521251
941	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012938573
1,216	Maximal Vector Computation in Large Data Sets	2005	VLDB	0.00011469322
1,401	Efficient Computation of the Skyline Cube	2005	VLDB	0.0001075604
2,367	Catching the Best Views of Skyline: A Semantic Approach Based on Decisive Subspaces	2005	VLDB	8.549962e-05
6,552	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.7306642e-05

Semantically Similar Papers

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