{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:17:18Z","timestamp":1778807838624,"version":"3.51.4"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T00:00:00Z","timestamp":1697414400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF #2146518, #2124431, and #2107261"],"award-info":[{"award-number":["CCF #2146518, #2124431, and #2107261"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2023,10,16]]},"abstract":"<jats:p>Synthesizing relational queries from data is challenging in the presence of recursion and invented predicates. We propose a fully automated approach to synthesize such queries. Our approach comprises of two steps: it first synthesizes a non-recursive query consistent with the given data, and then identifies recursion schemes in it and thereby generalizes to arbitrary data. This generalization is achieved by an iterative predicate unification procedure which exploits the notion of data provenance to accelerate convergence. In each iteration of the procedure, a constraint solver proposes a candidate query, and a query evaluator checks if the proposed program is consistent with the given data. The data provenance for a failed query allows us to construct additional constraints for the constraint solver and refine the search. We have implemented our approach in a tool named Mobius. On a suite of 21 challenging recursive query synthesis tasks, Mobius outperforms three state-of-the-art baselines Gensynth, ILASP, and Popper, both in terms of runtime and accuracy. We also demonstrate that the synthesized queries generalize well to unseen data.<\/jats:p>","DOI":"10.1145\/3622847","type":"journal-article","created":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T15:41:29Z","timestamp":1697470889000},"page":"1394-1417","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Mobius: Synthesizing Relational Queries with Recursive and Invented Predicates"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3195-585X","authenticated-orcid":false,"given":"Aalok","family":"Thakkar","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-5900-0036","authenticated-orcid":false,"given":"Nathaniel","family":"Sands","sequence":"additional","affiliation":[{"name":"University of Southern California, Los Angeles, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-9675-1602","authenticated-orcid":false,"given":"George","family":"Petrou","sequence":"additional","affiliation":[{"name":"University of Southern California, Los Angeles, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1733-7083","authenticated-orcid":false,"given":"Rajeev","family":"Alur","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1348-8618","authenticated-orcid":false,"given":"Mayur","family":"Naik","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2879-0932","authenticated-orcid":false,"given":"Mukund","family":"Raghothaman","sequence":"additional","affiliation":[{"name":"University of Southern California, Los Angeles, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,10,16]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Foundations of Databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul , Richard Hull , and Victor Vianu . 1995. Foundations of Databases . Addison-Wesley . Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39799-8_67"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP).","author":"Albarghouthi Aws","year":"2017","unstructured":"Aws Albarghouthi , Paraschos Koutris , Mayur Naik , and Calvin Smith . 2017 . Constraint-based synthesis of Datalog programs . In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP). Aws Albarghouthi, Paraschos Koutris, Mayur Naik, and Calvin Smith. 2017. Constraint-based synthesis of Datalog programs. In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP)."},{"key":"e_1_2_1_4_1","volume-title":"Program Analysis and Specialization for the C Programming Language. Ph. D. Dissertation. DIKU","author":"Andersen Lars Ole","unstructured":"Lars Ole Andersen . 1994. Program Analysis and Specialization for the C Programming Language. Ph. D. Dissertation. DIKU , University of Copenhagen. Lars Ole Andersen. 1994. Program Analysis and Specialization for the C Programming Language. Ph. D. Dissertation. DIKU, University of Copenhagen."},{"key":"e_1_2_1_5_1","volume-title":"Provenance in Databases: Why, How, and Where. Foundations and Trends in Databases, 1, 4","author":"Cheney James","year":"2009","unstructured":"James Cheney , Laura Chiticariu , and Wang-Chiew Tan . 2009. Provenance in Databases: Why, How, and Where. Foundations and Trends in Databases, 1, 4 ( 2009 ). James Cheney, Laura Chiticariu, and Wang-Chiew Tan. 2009. Provenance in Databases: Why, How, and Where. Foundations and Trends in Databases, 1, 4 (2009)."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).","author":"Cropper Andrew","unstructured":"Andrew Cropper , Sebastijan Dumancic , and Stephen H. Muggleton . 2020. Turning 30: New Ideas in Inductive Logic Programming . In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). Andrew Cropper, Sebastijan Dumancic, and Stephen H. Muggleton. 2020. Turning 30: New Ideas in Inductive Logic Programming. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-020-05934-z"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3411949"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3241691.3241692"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-81685-8_39"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3296979.3192382"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192382"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926423"},{"key":"e_1_2_1_14_1","unstructured":"Daniel Conrad Halbert. 1984. Programming by Example. Ph. D. Dissertation. AAI8512843 \t\t\t\t  Daniel Conrad Halbert. 1984. Programming by Example. Ph. D. Dissertation. AAI8512843"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454087"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386025"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485544"},{"key":"e_1_2_1_18_1","volume-title":"The ILASP system for Inductive Learning of Answer Set Programs. CoRR, abs\/2005.00904","author":"Law Mark","year":"2020","unstructured":"Mark Law , Alessandra Russo , and Krysia Broda . 2020. The ILASP system for Inductive Learning of Answer Set Programs. CoRR, abs\/2005.00904 ( 2020 ). Mark Law, Alessandra Russo, and Krysia Broda. 2020. The ILASP system for Inductive Learning of Answer Set Programs. CoRR, abs\/2005.00904 (2020)."},{"key":"e_1_2_1_19_1","volume-title":"Interactive Program Synthesis. ArXiv, abs\/1703.03539","author":"Le Vu","year":"2017","unstructured":"Vu Le , Daniel Perelman , Oleksandr Polozov , Mohammad Raza , Abhishek Udupa , and Sumit Gulwani . 2017. Interactive Program Synthesis. ArXiv, abs\/1703.03539 ( 2017 ). Vu Le, Daniel Perelman, Oleksandr Polozov, Mohammad Raza, Abhishek Udupa, and Sumit Gulwani. 2017. Interactive Program Synthesis. ArXiv, abs\/1703.03539 (2017)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/icse.2015.63"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Conference on Artificial Intelligence (AAAI).","author":"Mendelson Jonathan","year":"2021","unstructured":"Jonathan Mendelson , Aaditya Naik , Mukund Raghothaman , and Mayur Naik . 2021 . GenSynth: Synthesizing Datalog Programs without Language Bias . In Proceedings of the Conference on Artificial Intelligence (AAAI). Jonathan Mendelson, Aaditya Naik, Mukund Raghothaman, and Mayur Naik. 2021. GenSynth: Synthesizing Datalog Programs without Language Bias. In Proceedings of the Conference on Artificial Intelligence (AAAI)."},{"key":"e_1_2_1_22_1","first-page":"562","volume-title":"Proceedings of the 2002 ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA","author":"Milanova Ana","year":"2002","unstructured":"Ana Milanova , Atanas Rountev , and Barbara Ryder . 2002 . Parameterized Object Sensitivity for Points-to and Side-effect Analyses for Java . In Proceedings of the 2002 ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2002). ACM, 1\u201311. isbn:1-58113- 562 - 569 Ana Milanova, Atanas Rountev, and Barbara Ryder. 2002. Parameterized Object Sensitivity for Points-to and Side-effect Analyses for Java. In Proceedings of the 2002 ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2002). ACM, 1\u201311. isbn:1-58113-562-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-014-5471-y"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276520"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371130"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837671"},{"key":"e_1_2_1_27_1","unstructured":"Tim Rockt\u00e4schel and Sebastian Riedel. 2017. End-to-end Differentiable Proving. In Advances in Neural Information Processing Systems (NeurIPS). \t\t\t\t  Tim Rockt\u00e4schel and Sebastian Riedel. 2017. End-to-end Differentiable Proving. In Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_2_1_28_1","volume-title":"Advances in Neural Information Processing Systems","author":"Rockt\u00e4schel Tim","year":"2017","unstructured":"Tim Rockt\u00e4schel and Sebastian Riedel . 2017. End-to-end Differentiable Proving . In Advances in Neural Information Processing Systems , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). 30, Curran Associates, Inc. . https:\/\/proceedings.neurips.cc\/paper\/ 2017 \/file\/b2ab001909a8a6f04b51920306046ce5-Paper.pdf Tim Rockt\u00e4schel and Sebastian Riedel. 2017. End-to-end Differentiable Proving. In Advances in Neural Information Processing Systems, I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). 30, Curran Associates, Inc.. https:\/\/proceedings.neurips.cc\/paper\/2017\/file\/b2ab001909a8a6f04b51920306046ce5-Paper.pdf"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236024.3236034"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/847"},{"key":"e_1_2_1_31_1","unstructured":"Michael Sipser. 2012. Introduction to the Theory of Computation. Cengage Learning. \t\t\t\t  Michael Sipser. 2012. Introduction to the Theory of Computation. Cengage Learning."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926390"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3410307"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the ACM Conference on Management of Data (SIGMOD).","author":"Wang Chenglong","year":"2017","unstructured":"Chenglong Wang , Alvin Cheung , and Rastislav Bodik . 2017 . Interactive Query Synthesis from Input-Output Examples . In Proceedings of the ACM Conference on Management of Data (SIGMOD). Chenglong Wang, Alvin Cheung, and Rastislav Bodik. 2017. Interactive Query Synthesis from Input-Output Examples. In Proceedings of the ACM Conference on Management of Data (SIGMOD)."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3058738"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the Conference on Programming Language Design and Implementation (PLDI).","author":"Wang Chenglong","year":"2017","unstructured":"Chenglong Wang , Alvin Cheung , and Rastislav Bodik . 2017 . Synthesizing highly expressive SQL queries from input-output examples . In Proceedings of the Conference on Programming Language Design and Implementation (PLDI). Chenglong Wang, Alvin Cheung, and Rastislav Bodik. 2017. Synthesizing highly expressive SQL queries from input-output examples. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI)."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996859"},{"key":"e_1_2_1_38_1","unstructured":"Fan Yang Zhilin Yang and William Cohen. 2017. Differentiable learning of logical rules for knowledge base reasoning. In Advances in Neural Information Processing Systems (NeurIPS). \t\t\t\t  Fan Yang Zhilin Yang and William Cohen. 2017. Differentiable learning of logical rules for knowledge base reasoning. In Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ase.2013.6693082"},{"key":"e_1_2_1_40_1","article-title":"Debugging Large-scale Datalog: A Scalable Provenance Evaluation Strategy","volume":"42","author":"Zhao David","year":"2020","unstructured":"David Zhao , Pavle Subotic , and Bernhard Scholz . 2020 . Debugging Large-scale Datalog: A Scalable Provenance Evaluation Strategy . ACM Trans. Program. Lang. Syst. , 42 , 2 (2020). David Zhao, Pavle Subotic, and Bernhard Scholz. 2020. Debugging Large-scale Datalog: A Scalable Provenance Evaluation Strategy. ACM Trans. Program. Lang. Syst., 42, 2 (2020).","journal-title":"ACM Trans. Program. Lang. Syst."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3622847","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3622847","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:57:27Z","timestamp":1750298247000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3622847"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,16]]},"references-count":40,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2023,10,16]]}},"alternative-id":["10.1145\/3622847"],"URL":"https:\/\/doi.org\/10.1145\/3622847","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,16]]},"assertion":[{"value":"2023-10-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}