On Functional Aggregate Queries with Additive Inequalities

Summary: Introduces FAQ-AI (functional aggregate queries with additive inequalities) and relaxed tree decompositions/widths, enabling faster Boolean evaluation by extending InsideOut with Chazelle's semigroup range-search. Defines counting submodular width (#subw) between submodular and fractional hypertree widths to bound runtimes and gives faster in-database algorithms for k-means, linear SVM, and non-polynomial-loss training than materializing joins. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1756
Venue: PODS
Year: 2019
Pagerank: 7.7299363e-05
Overall Rank: 3,006 | 79.09%
DOI: 10.1145/3294052.3319694

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05
3,715	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8220943e-05
4,787	The Relational Data Borg is Learning	2020	VLDB	5.9224501e-05
5,718	Conjunctive Queries with Comparisons	2022	SIGMOD	5.3552123e-05
5,855	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3006096e-05
5,962	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2536266e-05
5,994	A Query Language Perspective on Graph Learning	2023	PODS	5.2415551e-05
7,332	The Complexity of Boolean Conjunctive Queries with Intersection Joins	2022	PODS	4.7606012e-05
7,491	Saibot: A Differentially Private Data Search Platform	2023	VLDB	4.7180617e-05
7,920	JoinBoost: Grow Trees Over Normalized Data Using Only SQL	2023	VLDB	4.6163888e-05
8,472	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	4.5036378e-05
8,589	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	4.4897014e-05
9,744	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	4.2897489e-05
10,009	The Space-Time Complexity of Sum-Product Queries	2026	PODS	4.1945683e-05
10,177	InferF: Declarative Factorization of AI/ML Inferences over Joins	2026	SIGMOD	4.1945683e-05
10,347	Fast Matrix Multiplication meets the Submodular Width	2025	PODS	4.1945683e-05
10,483	Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized	2025	SIGMOD	4.1945683e-05
10,898	Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization	2024	PODS	4.1945683e-05
10,924	Improved Approximation Algorithms for Relational Clustering	2024	PODS	4.1945683e-05
10,970	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.1945683e-05
11,220	Lightweight Materialization for Fast Dashboards Over Joins	2023	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
140	The MADlib Analytics Library or MAD Skills, the SQL	2012	VLDB	0.00042270404
502	Worst-case Optimal Join Algorithms	2012	PODS	0.00021526612
583	FAQ: Questions Asked Frequently	2016	PODS	0.00019717214
1,027	Accelerating XPath Location Steps	2002	SIGMOD	0.0001458865
1,167	Learning Generalized Linear Models Over Normalized Data	2015	SIGMOD	0.00013547713
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
2,728	Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities	2009	SIGMOD	8.2185032e-05
3,571	Lightning Fast and Space Efficient Inequality Joins	2015	VLDB	6.9580858e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,665	Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms	2025	VLDB	4.471975e-05
1,522	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS	0.0001153051
8,851	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4363908e-05
407	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024004562
8,589	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	4.4897014e-05
10,001	A Unifying Algorithm for Hierarchical Queries	2026	PODS	4.1945683e-05
10,898	Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization	2024	PODS	4.1945683e-05
1,038	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014492414
11,557	Aggregate Queries on Sparse Databases	2020	PODS	4.1945683e-05
583	FAQ: Questions Asked Frequently	2016	PODS	0.00019717214