{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:18:09Z","timestamp":1778807889251,"version":"3.51.4"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,12,6]],"date-time":"2020-12-06T00:00:00Z","timestamp":1607212800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CAREER DMS-1351362 and CNS-1409303"],"award-info":[{"award-number":["CAREER DMS-1351362 and CNS-1409303"]}]},{"name":"European Union's Horizon 2020 research and innovation programme","award":["682588"],"award-info":[{"award-number":["682588"]}]},{"name":"Google Research Award, and NSF","award":["CCF-1830711, CCF-1824303, and CCF-1733873"],"award-info":[{"award-number":["CCF-1830711, CCF-1824303, and CCF-1733873"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"<jats:p>\n            Motivated by fundamental applications in databases and relational machine learning, we formulate and study the problem of answering\n            <jats:italic>functional aggregate queries<\/jats:italic>\n            (FAQ) in which some of the input factors are defined by a collection of additive inequalities between variables. We refer to these queries as FAQ-AI for short.\n          <\/jats:p>\n          <jats:p>\n            To answer FAQ-AI in the Boolean semiring, we define\n            <jats:italic>relaxed<\/jats:italic>\n            tree decompositions and\n            <jats:italic>relaxed<\/jats:italic>\n            submodular and fractional hypertree width parameters. We show that an extension of the InsideOut algorithm using Chazelle\u2019s geometric data structure for solving the semigroup range search problem can answer Boolean FAQ-AI in time given by these new width parameters. This new algorithm achieves lower complexity than known solutions for FAQ-AI. It also recovers some known results in database query answering.\n          <\/jats:p>\n          <jats:p>\n            Our second contribution is a relaxation of the set of polymatroids that gives rise to the\n            <jats:italic>counting<\/jats:italic>\n            version of the submodular width, denoted by #subw. This new width is sandwiched between the submodular and the fractional hypertree widths. Any FAQ and FAQ-AI over one semiring can be answered in time proportional to #subw and respectively to the relaxed version of #subw.\n          <\/jats:p>\n          <jats:p>\n            We present three applications of our FAQ-AI framework to relational machine learning:\n            <jats:italic>k<\/jats:italic>\n            -means clustering, training linear support vector machines, and training models using non-polynomial loss. These optimization problems can be solved over a database asymptotically faster than computing the join of the database relations.\n          <\/jats:p>","DOI":"10.1145\/3426865","type":"journal-article","created":{"date-parts":[[2020,12,6]],"date-time":"2020-12-06T22:18:33Z","timestamp":1607293113000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Functional Aggregate Queries with Additive Inequalities"],"prefix":"10.1145","volume":"45","author":[{"given":"Mahmoud Abo","family":"Khamis","sequence":"first","affiliation":[{"name":"RelationalAI Inc., Berkeley, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryan R.","family":"Curtin","sequence":"additional","affiliation":[{"name":"RelationalAI Inc., Berkeley, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hung Q.","family":"Ngo","sequence":"additional","affiliation":[{"name":"RelationalAI Inc., Berkeley, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuanlong","family":"Nguyen","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Olteanu","sequence":"additional","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maximilian","family":"Schleich","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,12,6]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319694"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196960"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375661"},{"key":"e_1_2_2_4_1","volume-title":"Proceedings of ICDT","author":"Khamis Mahmoud Abo","year":"2019","unstructured":"Mahmoud Abo Khamis , Hung Q. Ngo , Dan Olteanu , and Dan Suciu . 2019 . Boolean tensor decomposition for conjunctive queries with negation . In Proceedings of ICDT 2019. Article 21, 19 pages. Mahmoud Abo Khamis, Hung Q. Ngo, Dan Olteanu, and Dan Suciu. 2019. Boolean tensor decomposition for conjunctive queries with negation. In Proceedings of ICDT 2019. Article 21, 19 pages."},{"key":"e_1_2_2_5_1","volume-title":"FAQ: Questions asked frequently. arxiv:1504.04044","author":"Khamis Mahmoud Abo","year":"2015","unstructured":"Mahmoud Abo Khamis , Hung Q. Ngo , and Atri Rudra . 2015 . FAQ: Questions asked frequently. arxiv:1504.04044 Mahmoud Abo Khamis, Hung Q. Ngo, and Atri Rudra. 2015. FAQ: Questions asked frequently. arxiv:1504.04044"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093754.3093757"},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Mahmoud Abo Khamis Hung Q. Ngo and Dan Suciu. 2016. What do Shannon-type inequalities submodular width and disjunctive datalog have to do with one another? arxiv:1612.02503  Mahmoud Abo Khamis Hung Q. Ngo and Dan Suciu. 2016. What do Shannon-type inequalities submodular width and disjunctive datalog have to do with one another? arxiv:1612.02503","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.43"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2392389.2392412"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998196.1998198"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217026"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.79149"},{"key":"e_1_2_2_15_1","volume-title":"Computational Geometry","author":"de Berg Mark","unstructured":"Mark de Berg , Otfried Cheong , Marc van Kreveld , and Mark Overmars . 2008. Computational Geometry ( 3 rd ed.). Springer-Verlag , Berlin, Germany . Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. 2008. Computational Geometry (3rd ed.). Springer-Verlag, Berlin, Germany.","edition":"3"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855057"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287379"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564705"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2765617"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367510"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2009.09.011"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150429"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2831360.2831362"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/42267.42273"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9684-2"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723713"},{"key":"e_1_2_2_29_1","volume-title":"Proceedings of ICALP","author":"Lincoln Andrea","year":"2016","unstructured":"Andrea Lincoln , Virginia Vassilevska Williams , Joshua R. Wang , and R. Ryan Williams . 2016. Deterministic time-space trade-offs for k-SUM . In Proceedings of ICALP 2016 . Article 58, 14 pages. Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, and R. Ryan Williams. 2016. Deterministic time-space trade-offs for k-SUM. In Proceedings of ICALP 2016. Article 58, 14 pages."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2208106"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2380985"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196990"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559887"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873687"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882939"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448498"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1966806.1966812"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000055"},{"key":"e_1_2_2_41_1","volume-title":"Proceeding of ICDT","author":"Veldhuizen Todd L.","year":"2014","unstructured":"Todd L. Veldhuizen . 2014 . Triejoin: A simple, worst-case optimal join algorithm . In Proceeding of ICDT 2014. 96--106. Todd L. Veldhuizen. 2014. Triejoin: A simple, worst-case optimal join algorithm. In Proceeding of ICDT 2014. 96--106."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3426865","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3426865","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:46Z","timestamp":1750197706000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3426865"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,6]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3426865"],"URL":"https:\/\/doi.org\/10.1145\/3426865","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,6]]},"assertion":[{"value":"2020-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}