{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:16:50Z","timestamp":1778807810104,"version":"3.51.4"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,5,12]],"date-time":"2017-05-12T00:00:00Z","timestamp":1494547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2017,5,12]]},"abstract":"<jats:p>We define and study the Functional Aggregate Query (FAQ) problem, which captures common computational tasks across a very wide range of domains including relational databases, logic, matrix and tensor computation, probabilistic graphical models, constraint satisfaction, and signal processing. Simply put, an FAQ is a declarative way of defining a new function from a database of input functions.<\/jats:p>\n          <jats:p>We present InsideOut, a dynamic programming algorithm, to evaluate an FAQ. The algorithm rewrites the input query into a set of easier-to-compute FAQ sub-queries. Each subquery is then evaluated using a worst-case optimal relational join algorithm. The topic of designing algorithms to optimally evaluate the classic multiway join problem has seen exciting developments in the past few years. Our framework tightly connects these new ideas in database theory with a vast number of application areas in a coherent manner, showing potentially that -- with the right abstraction, blurring the distinction between data and computation -- a good database engine can be a general purpose constraint solver, relational data store, graphical model inference engine, and matrix\/tensor computation processor all at once.<\/jats:p>\n          <jats:p>The InsideOut algorithm is very simple, as shall be described in this paper. Yet, in spite of solving an extremely general problem, its runtime either is as good as or improves upon the best known algorithm for the applications that FAQ specializes to. These corollaries include computational tasks in graphical model inference, matrix\/tensor operations, relational joins, and logic. Better yet, InsideOut can be used within any database engine, because it is basically a principled way of rewriting queries. Indeed, it is already part of the LogicBlox database engine, helping efficiently answer traditional database queries, graphical model inference queries, and train a large class of machine learning models inside the database itself.<\/jats:p>","DOI":"10.1145\/3093754.3093757","type":"journal-article","created":{"date-parts":[[2017,5,15]],"date-time":"2017-05-15T12:13:58Z","timestamp":1494850438000},"page":"6-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Juggling Functions Inside a Database"],"prefix":"10.1145","volume":"46","author":[{"given":"Mahmoud Abo","family":"Khamis","sequence":"first","affiliation":[{"name":"LogicBlox Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hung Q.","family":"Ngo","sequence":"additional","affiliation":[{"name":"LogicBlox Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Atri","family":"Rudra","sequence":"additional","affiliation":[{"name":"University at Buffalo, SUNY"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,5,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745776"},{"key":"e_1_2_1_2_1","volume-title":"FAQ: questions asked frequently. CoRR, abs\/1504.04044","author":"Khamis M. Abo","year":"2015","unstructured":"M. Abo Khamis , H. Q. Ngo , and A. Rudra . FAQ: questions asked frequently. CoRR, abs\/1504.04044 , 2015 . M. Abo Khamis, H. Q. Ngo, and A. Rudra. FAQ: questions asked frequently. CoRR, abs\/1504.04044, 2015."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902289"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.825794"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742796"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.43"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556579"},{"key":"e_1_2_1_10_1","first-page":"1","volume-title":"ICDT","author":"B\u00e1r\u00e1ny V.","year":"2016","unstructured":"V. B\u00e1r\u00e1ny , B. ten Cate , B. Kimelfeld , D. Olteanu , and Z. Vagena . Declarative probabilistic programming with datalog . In ICDT , pages 7: 1 -- 7 :19, 2016 . V. B\u00e1r\u00e1ny, B. ten Cate, B. Kimelfeld, D. Olteanu, and Z. Vagena. Declarative probabilistic programming with datalog. In ICDT, pages 7:1--7:19, 2016."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2012.31"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2750545"},{"key":"e_1_2_1_13_1","first-page":"49","volume-title":"SIGMOD '06","author":"Cohen S.","unstructured":"S. Cohen . User-defined aggregate functions: Bridging theory and practice . In SIGMOD '06 , pages 49 -- 60 . S. Cohen. User-defined aggregate functions: Bridging theory and practice. In SIGMOD '06, pages 49--60."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"e_1_2_1_15_1","volume-title":"Introduction to algorithms","author":"Cormen T. H.","year":"2001","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein . Introduction to algorithms . MIT Press , 2 nd edition, 2001 . T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to algorithms. MIT Press, 2nd edition, 2001.","edition":"2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/368273.368557"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(99)00059-4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448508"},{"key":"e_1_2_1_19_1","volume-title":"Nov.","author":"Fischl W.","year":"2016","unstructured":"W. Fischl , G. Gottlob , and R. Pichler . General and Fractional Hypertree Decompositions: Hard and Easy Cases. ArXiv e-prints , Nov. 2016 . W. Fischl, G. Gottlob, and R. Pichler. General and Fractional Hypertree Decompositions: Hard and Easy Cases. ArXiv e-prints, Nov. 2016."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/321296.321300"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109590"},{"key":"e_1_2_1_22_1","volume-title":"Flexible caching in trie joins","author":"Kalinsky O.","year":"2017","unstructured":"O. Kalinsky , Y. Etsion , and B. Kimelfeld . Flexible caching in trie joins , 2017 . To appear in EDBT. O. Kalinsky, Y. Etsion, and B. Kimelfeld. Flexible caching in trie joins, 2017. To appear in EDBT."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2005.04.004"},{"key":"e_1_2_1_24_1","volume-title":"Probabilistic graphical models. Adaptive Computation and Machine Learning","author":"Koller D.","year":"2009","unstructured":"D. Koller and N. Friedman . Probabilistic graphical models. Adaptive Computation and Machine Learning . MIT Press , 2009 . Principles and techniques. D. Koller and N. Friedman. Probabilistic graphical models. Adaptive Computation and Machine Learning. MIT Press, 2009. Principles and techniques."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723713"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721845"},{"key":"e_1_2_1_27_1","volume-title":"In-database learning with sparse tensors","author":"Ngo H. Q.","year":"2017","unstructured":"H. Q. Ngo , X. Nguyen , D. Olteanu , and M. Schleich . In-database learning with sparse tensors , 2017 . Manuscript . H. Q. Ngo, X. Nguyen, D. Olteanu, and M. Schleich. In-database learning with sparse tensors, 2017. Manuscript."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_2_1_29_1","first-page":"5","volume-title":"SIGMOD RECORD","author":"Ngo H. Q.","year":"2013","unstructured":"H. Q. Ngo , C. R\u00e9 , and A. Rudra . Skew strikes back: New developments in the theory of join algorithms . In SIGMOD RECORD , pages 5 -- 16 , 2013 . H. Q. Ngo, C. R\u00e9, and A. Rudra. Skew strikes back: New developments in the theory of join algorithms. In SIGMOD RECORD, pages 5--16, 2013."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764947.2764948"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007312"},{"issue":"1","key":"e_1_2_1_32_1","article-title":"Size bounds for factorised representations of query results","volume":"40","author":"Olteanu D.","year":"2015","unstructured":"D. Olteanu and J. Z\u00e1vodn? . Size bounds for factorised representations of query results . ACM Trans. Datab. Syst. , 40 ( 1 ), 2015 . D. Olteanu and J. Z\u00e1vodn?. Size bounds for factorised representations of query results. ACM Trans. Datab. Syst., 40(1), 2015.","journal-title":"ACM Trans. Datab. Syst."},{"key":"e_1_2_1_33_1","volume-title":"v. Beek, and T. Walsh. Handbook of Constraint Programming (Foundations of Artificial Intelligence)","author":"Rossi F.","year":"2006","unstructured":"F. Rossi , P. v. Beek, and T. Walsh. Handbook of Constraint Programming (Foundations of Artificial Intelligence) . Elsevier Science Inc ., 2006 . F. Rossi, P. v. Beek, and T. Walsh. Handbook of Constraint Programming (Foundations of Artificial Intelligence). Elsevier Science Inc., 2006."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882939"},{"key":"e_1_2_1_35_1","first-page":"96","volume-title":"ICDT","author":"Veldhuizen T. L.","year":"2014","unstructured":"T. L. Veldhuizen . Triejoin : A simple, worst-case optimal join algorithm . In ICDT , pages 96 -- 106 , 2014 . T. L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In ICDT, pages 96--106, 2014."},{"key":"e_1_2_1_36_1","first-page":"171","volume-title":"Canadian AI","author":"Zhang N.","year":"1994","unstructured":"N. Zhang and D. Poole . A simple approach to Bayesian network computations . In Canadian AI , pages 171 -- 178 , 1994 . N. Zhang and D. Poole. A simple approach to Bayesian network computations. In Canadian AI, pages 171--178, 1994."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622756.1622765"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3093754.3093757","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3093754.3093757","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:16Z","timestamp":1750217416000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3093754.3093757"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,12]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,5,12]]}},"alternative-id":["10.1145\/3093754.3093757"],"URL":"https:\/\/doi.org\/10.1145\/3093754.3093757","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2017,5,12]]},"assertion":[{"value":"2017-05-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}