{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T12:26:41Z","timestamp":1753360001473,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T00:00:00Z","timestamp":1659052800000},"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":[[2022,7,29]]},"abstract":"<jats:p>Modern data analytics applications, such as knowledge graph reasoning and machine learning, typically involve recursion through aggregation. Such computations pose great challenges to both system builders and theoreticians: first, to derive simple yet powerful abstractions for these computations; second, to define and study the semantics for the abstractions; third, to devise optimization techniques for these computations.<\/jats:p>\n          <jats:p>In recent work we presented a generalization of Datalog called Datalog, which addresses these challenges. Datalog is a simple abstraction, which allows aggregates to be interleaved with recursion, and retains much of the simplicity and elegance of Datalog. We define its formal semantics based on an algebraic structure called Partially Ordered Pre-Semirings, and illustrate through several examples how Datalog can be used for a variety of applications. Finally, we describe a new optimization rule for Datalog, called the FGH-rule, then illustrate the FGH-rule on several examples, including a simple magic-set rewriting, generalized semi-na\u00efve evaluation, and a bill-of-material example, and briefly discuss the implementation of the FGH-rule and present some experimental validation of its effectiveness.<\/jats:p>","DOI":"10.1145\/3552490.3552492","type":"journal-article","created":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T18:51:29Z","timestamp":1659120689000},"page":"6-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Datalog in Wonderland"],"prefix":"10.1145","volume":"51","author":[{"given":"Mahmoud Abo","family":"Khamis","sequence":"first","affiliation":[{"name":"RelationalAI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hung Q.","family":"Ngo","sequence":"additional","affiliation":[{"name":"RelationalAI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[{"name":"TU Wien"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yisu","family":"Remy Wang","sequence":"additional","affiliation":[{"name":"University of Washington"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/551350"},{"key":"e_1_2_1_2_1","volume-title":"Evaluating Answer Set Programming with non-convex recursive aggregates. Fundam. Informaticae","author":"ALVIANO M.","year":"2016","unstructured":"ALVIANO , M. Evaluating Answer Set Programming with non-convex recursive aggregates. Fundam. Informaticae ( 2016 ). ALVIANO, M. Evaluating Answer Set Programming with non-convex recursive aggregates. Fundam. Informaticae (2016)."},{"key":"e_1_2_1_3_1","volume-title":"Datalog","author":"ALVIANO M.","year":"2010","unstructured":"ALVIANO , M. , FABER , W. , LEONE , N. , PERRI , S. , PFEIFER , G. , AND TERRACINA , G. The disjunctive Datalog system DLV . In Datalog ( 2010 ). ALVIANO, M., FABER, W., LEONE, N., PERRI, S., PFEIFER, G., AND TERRACINA, G. The disjunctive Datalog system DLV. In Datalog (2010)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742796"},{"key":"e_1_2_1_5_1","volume-title":"PODS","author":"BANCILHON F.","year":"1986","unstructured":"BANCILHON , F. , MAIER , D. , SAGIV , Y. , AND ULLMAN , J. D. Magic sets and other strange ways to implement logic programs . In PODS ( 1986 ). BANCILHON, F., MAIER, D., SAGIV, Y., AND ULLMAN, J. D. Magic sets and other strange ways to implement logic programs. In PODS (1986)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"BEERI C. AND RAMAKRISHNAN R. On the power of magic. J. Log. Program. (1991).  BEERI C. AND RAMAKRISHNAN R. On the power of magic. J. Log. Program. (1991).","DOI":"10.1016\/0743-1066(91)90038-Q"},{"key":"e_1_2_1_7_1","volume-title":"DBSP: automatic incremental view maintenance for rich query languages. CoRR abs\/2203.16684","author":"BUDIU M.","year":"2022","unstructured":"BUDIU , M. , MCSHERRY , F. , RYZHYK , L. , AND TANNEN , V. DBSP: automatic incremental view maintenance for rich query languages. CoRR abs\/2203.16684 ( 2022 ). BUDIU, M., MCSHERRY, F., RYZHYK, L., AND TANNEN, V. DBSP: automatic incremental view maintenance for rich query languages. CoRR abs\/2203.16684 (2022)."},{"key":"e_1_2_1_8_1","volume-title":"Graphs and networks","author":"CARR\u00c9 B.","year":"1979","unstructured":"CARR\u00c9 , B. Graphs and networks . The Clarendon Press, Oxford University Press , New York , 1979 . CARR\u00c9, B. Graphs and networks. The Clarendon Press, Oxford University Press, New York, 1979."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2391229.2391230"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"e_1_2_1_11_1","volume-title":"CSL","author":"DANNERT K. M.","year":"2021","unstructured":"DANNERT , K. M. , GR-DEL , E. , NAAF , M. , AND TANNEN , V. Semiring provenance for fixed-point logic . In CSL ( 2021 ). DANNERT, K. M., GR-DEL, E., NAAF, M., AND TANNEN, V. Semiring provenance for fixed-point logic. In CSL (2021)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"FABER W. PFEIFER G. AND LEONE N. Semantics and complexity of recursive aggregates in Answer Set Programming. Artif. Intell. (2011).  FABER W. PFEIFER G. AND LEONE N. Semantics and complexity of recursive aggregates in Answer Set Programming. Artif. Intell. (2011).","DOI":"10.1016\/j.artint.2010.04.002"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3311880.3311886"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/113413.113427"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/73721.73722"},{"key":"e_1_2_1_16_1","volume-title":"The well-founded semantics for general logic programs. J. ACM","author":"GELDER A. V.","year":"1991","unstructured":"GELDER , A. V. , ROSS , K. A. , AND SCHLIPF , J. S. The well-founded semantics for general logic programs. J. ACM ( 1991 ). GELDER, A. V., ROSS, K. A., AND SCHLIPF, J. S. The well-founded semantics for general logic programs. J. ACM (1991)."},{"key":"e_1_2_1_17_1","volume-title":"Logic Programming","author":"GELFOND M.","year":"1988","unstructured":"GELFOND , M. , AND LIFSCHITZ , V. The stable model semantics for logic programming . In Logic Programming ( 1988 ). GELFOND, M., AND LIFSCHITZ, V. The stable model semantics for logic programming. In Logic Programming (1988)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"GELFOND M. AND ZHANG Y. Vicious circle principle and logic programs with aggregates. Theory Pract. Log. Program. (2014).  GELFOND M. AND ZHANG Y. Vicious circle principle and logic programs with aggregates. Theory Pract. Log. Program. (2014).","DOI":"10.1017\/S1471068414000222"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375706"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1386688"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"HALEVY A. Y. Answering queries using views: A survey. VLDB J. (2001).  HALEVY A. Y. Answering queries using views: A survey. VLDB J. (2001).","DOI":"10.1007\/s007780100054"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1999.782634"},{"key":"e_1_2_1_24_1","volume-title":"CAV","author":"JORDAN H.","year":"2016","unstructured":"JORDAN , H. , SCHOLZ , B. , AND SUBOTIC , P. Souffl\u00e9: On synthesis of program analyzers . In CAV ( 2016 ). JORDAN, H., SCHOLZ, B., AND SUBOTIC, P. Souffl\u00e9: On synthesis of program analyzers. In CAV (2016)."},{"key":"e_1_2_1_25_1","volume-title":"Logic Programming","author":"KEMP D. B.","year":"1991","unstructured":"KEMP , D. B. , AND STUCKEY , P. J. Semantics of logic programs with aggregates . In Logic Programming ( 1991 ). KEMP, D. B., AND STUCKEY, P. J. Semantics of logic programs with aggregates. In Logic Programming (1991)."},{"key":"e_1_2_1_26_1","volume-title":"Convergence of Datalog over (pre-) semirings. CoRR abs\/2105.14435","author":"KHAMIS M. A.","year":"2021","unstructured":"KHAMIS , M. A. , NGO , H. Q. , PICHLER , R. , SUCIU , D. , AND WANG , Y. R. Convergence of Datalog over (pre-) semirings. CoRR abs\/2105.14435 ( 2021 ). KHAMIS, M. A., NGO, H. Q., PICHLER, R., SUCIU, D., AND WANG, Y. R. Convergence of Datalog over (pre-) semirings. CoRR abs\/2105.14435 (2021)."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524140"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_9"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"LEHMANN D. J. Algebraic structures for transitive closure. Theor. Comput. Sci. (1977).  LEHMANN D. J. Algebraic structures for transitive closure. Theor. Comput. Sci. (1977).","DOI":"10.1016\/0304-3975(77)90056-1"},{"key":"e_1_2_1_30_1","unstructured":"LESKOVEC J. AND KREVL A. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014.  LESKOVEC J. AND KREVL A. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014."},{"key":"e_1_2_1_31_1","series-title":"SIAM J. Numer. Anal. (1979)","volume-title":"Generalized nested dissection","author":"LIPTON R. J.","unstructured":"LIPTON , R. J. , ROSE , D. J. , AND TARJAN , R. E. Generalized nested dissection . SIAM J. Numer. Anal. (1979) . LIPTON, R. J., ROSE, D. J., AND TARJAN, R. E. Generalized nested dissection. SIAM J. Numer. Anal. (1979)."},{"key":"e_1_2_1_32_1","series-title":"SIAM J. Comput. (1980)","volume-title":"Applications of a planar separator theorem","author":"LIPTON R. J.","unstructured":"LIPTON , R. J. , AND TARJAN , R. E. Applications of a planar separator theorem . SIAM J. Comput. (1980) . LIPTON, R. J., AND TARJAN, R. E. Applications of a planar separator theorem. SIAM J. Comput. (1980)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-93100-1_11"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"MAZURAN M. SERRA E. AND ZANIOLO C. A declarative extension of horn clauses and its significance for Datalog and its applications. Theory Pract. Log. Program. (2013).  MAZURAN M. SERRA E. AND ZANIOLO C. A declarative extension of horn clauses and its significance for Datalog and its applications. Theory Pract. Log. Program. (2013).","DOI":"10.1017\/S1471068413000380"},{"key":"e_1_2_1_35_1","volume-title":"VLDB","author":"MUMICK I. S.","year":"1990","unstructured":"MUMICK , I. S. , PIRAHESH , H. , AND RAMAKRISHNAN , R. The magic of duplicates and aggregates . In VLDB ( 1990 ). MUMICK, I. S., PIRAHESH, H., AND RAMAKRISHNAN, R. The magic of duplicates and aggregates. In VLDB (1990)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/555142"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/b98874"},{"key":"e_1_2_1_38_1","volume-title":"Semantics and optimization of constraint queries in databases","author":"RAMAKRISHNAN R.","year":"1994","unstructured":"RAMAKRISHNAN , R. , AND SRIVASTAVA , D. Semantics and optimization of constraint queries in databases . IEEE Data Eng. Bull . ( 1994 ). RAMAKRISHNAN, R., AND SRIVASTAVA, D. Semantics and optimization of constraint queries in databases. IEEE Data Eng. Bull. (1994)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/137097.137852"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-9076-0_9"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915229"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113340"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168907"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509578.2509586"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458815"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517827"},{"key":"e_1_2_1_47_1","volume-title":"Optimizing recursive queries with program synthesis. CoRR abs\/2202.10390","author":"WANG Y. R.","year":"2022","unstructured":"WANG , Y. R. , KHAMIS , M. A. , NGO , H. Q. , PICHLER , R. , AND SUCIU , D. Optimizing recursive queries with program synthesis. CoRR abs\/2202.10390 ( 2022 ). WANG, Y. R., KHAMIS, M. A., NGO, H. Q., PICHLER, R., AND SUCIU, D. Optimizing recursive queries with program synthesis. CoRR abs\/2202.10390 (2022)."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434304"},{"key":"e_1_2_1_49_1","volume-title":"Monotonic properties of completed aggregates in recursive queries. CoRR abs\/1910.08888","author":"ZANIOLO C.","year":"2019","unstructured":"ZANIOLO , C. , DAS , A. , GU , J. , LI , Y. , LI , M. , AND WANG , J. Monotonic properties of completed aggregates in recursive queries. CoRR abs\/1910.08888 ( 2019 ). ZANIOLO, C., DAS, A., GU, J., LI, Y., LI, M., AND WANG, J. Monotonic properties of completed aggregates in recursive queries. CoRR abs\/1910.08888 (2019)."},{"key":"e_1_2_1_50_1","volume-title":"AMW","author":"ZANIOLO C.","year":"2016","unstructured":"ZANIOLO , C. , YANG , M. , DAS , A. , AND INTERLANDI , M. The magic of pushing extrema into recursion: Simple, powerful Datalog programs . In AMW ( 2016 ). ZANIOLO, C., YANG, M., DAS, A., AND INTERLANDI, M. The magic of pushing extrema into recursion: Simple, powerful Datalog programs. In AMW (2016)."},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"ZANIOLO C. YANG M. DAS A. SHKAPSKY A. CONDIE T. AND INTERLANDI M. Fixpoint semantics and optimization of recursive Datalog programs with aggregates. Theory Pract. Log. Program. (2017).  ZANIOLO C. YANG M. DAS A. SHKAPSKY A. CONDIE T. AND INTERLANDI M. Fixpoint semantics and optimization of recursive Datalog programs with aggregates. Theory Pract. Log. Program. (2017).","DOI":"10.1017\/S1471068417000436"},{"key":"e_1_2_1_52_1","unstructured":"ZIMMERMANN U. Linear and combinatorial optimization in ordered algebraic structures. Ann. Discrete Math. (1981).  ZIMMERMANN U. Linear and combinatorial optimization in ordered algebraic structures. Ann. Discrete Math. (1981)."}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3552490.3552492","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3552490.3552492","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:45:12Z","timestamp":1750268712000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3552490.3552492"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,29]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,7,29]]}},"alternative-id":["10.1145\/3552490.3552492"],"URL":"https:\/\/doi.org\/10.1145\/3552490.3552492","relation":{},"ISSN":["0163-5808"],"issn-type":[{"type":"print","value":"0163-5808"}],"subject":[],"published":{"date-parts":[[2022,7,29]]},"assertion":[{"value":"2022-07-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}