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.7230513e-05
Overall Rank: 3,009 | 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,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05
3,702	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8251643e-05
4,787	The Relational Data Borg is Learning	2020	VLDB	5.9168117e-05
5,728	Conjunctive Queries with Comparisons	2022	SIGMOD	5.350072e-05
5,845	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3057391e-05
5,963	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2485815e-05
5,998	A Query Language Perspective on Graph Learning	2023	PODS	5.2365238e-05
7,328	The Complexity of Boolean Conjunctive Queries with Intersection Joins	2022	PODS	4.7560344e-05
7,490	Saibot: A Differentially Private Data Search Platform	2023	VLDB	4.7135369e-05
7,920	JoinBoost: Grow Trees Over Normalized Data Using Only SQL	2023	VLDB	4.6120304e-05
8,470	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	4.4993203e-05
8,587	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	4.4853975e-05
9,743	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	4.2856385e-05
10,009	The Space-Time Complexity of Sum-Product Queries	2026	PODS	4.1905499e-05
10,177	InferF: Declarative Factorization of AI/ML Inferences over Joins	2026	SIGMOD	4.1905499e-05
10,359	Fast Matrix Multiplication meets the Submodular Width	2025	PODS	4.1905499e-05
10,493	Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized	2025	SIGMOD	4.1905499e-05
10,902	Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization	2024	PODS	4.1905499e-05
10,928	Improved Approximation Algorithms for Relational Clustering	2024	PODS	4.1905499e-05
10,973	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.1905499e-05
11,222	Lightweight Materialization for Fast Dashboards Over Joins	2023	SIGMOD	4.1905499e-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
139	The MADlib Analytics Library or MAD Skills, the SQL	2012	VLDB	0.00042320525
503	Worst-case Optimal Join Algorithms	2012	PODS	0.00021517145
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796
1,028	Accelerating XPath Location Steps	2002	SIGMOD	0.00014578947
1,172	Learning Generalized Linear Models Over Normalized Data	2015	SIGMOD	0.00013504249
1,322	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00012595941
1,452	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011922523
2,733	Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities	2009	SIGMOD	8.2106718e-05
3,575	Lightning Fast and Space Efficient Inequality Joins	2015	VLDB	6.9509846e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,663	Advancing Fact Attribution for Query Answering: Aggregate Queries and Novel Algorithms	2025	VLDB	4.4676883e-05
1,520	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS	0.00011524911
8,850	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4324268e-05
401	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024281448
8,587	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	4.4853975e-05
10,000	A Unifying Algorithm for Hierarchical Queries	2026	PODS	4.1905499e-05
10,902	Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization	2024	PODS	4.1905499e-05
1,039	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014488271
11,561	Aggregate Queries on Sparse Databases	2020	PODS	4.1905499e-05
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796