Beyond Equi-joins: Ranking, Enumeration and Factorization

Summary: Ranked theta-join enumeration with inequalities; top-k on acyclic full joins in O(n polylog n + k log k). On-the-fly factorized output representation; memory-efficient, fast; experiments show orders-of-magnitude speedups over state-of-the-art DB systems. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12434
Venue: VLDB
Year: 2021
Pagerank: 5.2536266e-05
Overall Rank: 5,962 | 58.53%
DOI: 10.14778/3476249.3476306

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,718	Conjunctive Queries with Comparisons	2022	SIGMOD	5.3552123e-05
7,166	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.8124491e-05
8,061	Efficient Computation of Quantiles over Joins	2023	PODS	4.5943269e-05
9,744	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	4.2897489e-05
9,940	Worst-Case-Optimal Similarity Joins on Graph Databases	2024	SIGMOD	4.2456408e-05
9,986	Database Research needs an Abstract Relational Query Language	2026	CIDR	4.1945683e-05
10,926	Complex Event Recognition meets Hierarchical Conjunctive Queries	2024	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 34 of 34 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
7	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015496097
152	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00040963225
430	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.00023463938
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
465	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00022455702
552	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00020310903
674	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00018327585
772	Answering Conjunctive Queries under Updates	2017	PODS	0.00016876498
834	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016135159
1,024	Path Problems in Temporal Graphs	2014	VLDB	0.00014609643
1,167	Learning Generalized Linear Models Over Normalized Data	2015	SIGMOD	0.00013547713
1,259	Aggregation and Ordering in Factorised Databases	2013	VLDB	0.00012995821
1,328	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00012565612
1,442	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011956109
1,557	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	0.00011392493
2,296	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.0776226e-05
2,728	Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities	2009	SIGMOD	8.2185032e-05
2,933	Answering Top-k Queries Using Views	2006	VLDB	7.8679669e-05
3,006	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	7.7299363e-05
3,082	FDB: A Query Engine for Factorised Relational Databases	2012	VLDB	7.6014248e-05
3,371	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	7.1696145e-05
3,387	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	7.1573735e-05
3,715	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8220943e-05
4,159	F: Regression Models over Factorized Views	2016	VLDB	6.3993326e-05
4,737	Joining Interval Data in Relational Databases	2004	SIGMOD	5.9604127e-05
5,373	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	5.5425231e-05
5,855	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3006096e-05
5,858	Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries	2021	PODS	5.2997454e-05
6,619	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	4.9910152e-05
7,692	Processing Top-k Join Queries	2010	VLDB	4.6761366e-05
7,762	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	4.6583829e-05
7,840	Progressive Join Algorithms Considering User Preference	2021	CIDR	4.6371736e-05
8,652	Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration	2020	PODS	4.4753042e-05
11,560	Factorized Graph Representations for Semi-Supervised Learning from Sparse Data	2020	SIGMOD	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,953	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8085795e-05
6,728	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS	4.9483326e-05
8,966	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4193184e-05
12,191	Efficient Rank Join with Aggregation Constraints	2011	VLDB	4.1945683e-05
552	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00020310903
3,387	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	7.1573735e-05
8,061	Efficient Computation of Quantiles over Joins	2023	PODS	4.5943269e-05
10,324	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB	4.1945683e-05
3,715	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8220943e-05
7,166	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.8124491e-05