Boolean + Ranking: Querying a Database by K-Constrained Optimization

Summary: Proposes OPT* for k-constrained optimization: Boolean constraint + numeric objective in RDBMS. It merges discrete index-space search with continuous optimization, framing queries as A* search over multi-index states with tight heuristics, achieving up to 3 orders of magnitude speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3827
Venue: SIGMOD
Year: 2006
Pagerank: 5.6353412e-05
Overall Rank: 7,352 | 49.56%
DOI: 10.1145/1142473.1142515

Incoming Non-self Citations Over Time

Authors

1. Zhen Zhang (University of Illinois Urbana-Champaign)
2. Seung-won Hwang (Pohang University of Science and Technology)
3. Kevin Chen-Chuan Chang (University of Illinois Urbana-Champaign)
4. Min Wang (IBM)
5. Christian A. Lang (IBM)
6. Yuan-chi Chang (IBM)

BibTeX Citation

@inproceedings{zhang_sigmod06,
        title = {{Boolean + Ranking: Querying a Database by K-Constrained Optimization}},
        author = {Zhang, Zhen and Hwang, Seung-won and Chang, Kevin Chen-Chuan and Wang, Min and Lang, Christian A. and Chang, Yuan-chi},
        series = {{SIGMOD} '06},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1142473.1142515},
        url = {https://dl.acm.org/doi/10.1145/1142473.1142515},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,500	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD	7.3597562e-05
7,202	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	5.6755422e-05
8,029	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB	5.5045998e-05
9,115	A General Framework for Modeling and Processing Optimization Queries	2007	VLDB	5.3215443e-05
12,368	Exact Indexing for Support Vector Machines	2011	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
108	Optimizing Multi-Feature Queries for Image Databases	2000	VLDB	0.00033228866
170	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00027376361
499	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00017431827
675	Optimizing Queries over Multimedia Repositories	1996	SIGMOD	0.00015080025
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,525	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010493702
1,759	Rank-aware Query Optimization	2004	SIGMOD	9.8160244e-05
14,095	SPIRE: A Progressive Content-Based Spatial Image Retrieval Engine	2000	SIGMOD	-

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	290	An Overview of Query Optimization in Relational Systems	1998	PODS
2	3,596	On the Complexity of Query Result Diversification	2013	VLDB
3	1,759	Rank-aware Query Optimization	2004	SIGMOD
4	7,703	Constrained Optimalities in Query Personalization	2005	SIGMOD
5	6,389	Query Refinement for Diverse Top-k Selection	2024	SIGMOD
6	2,745	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB
7	12,308	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD
8	635	Evaluating Top-k Selection Queries	1999	VLDB
9	9,115	A General Framework for Modeling and Processing Optimization Queries	2007	VLDB
10	973	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD