{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:14:29Z","timestamp":1779174869433,"version":"3.51.4"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006374","name":"NSF","doi-asserted-by":"publisher","award":["IIS-2008107"],"award-info":[{"award-number":["IIS-2008107"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>We describe a system called Qr-Hint that, given a (correct) target query Q* and a (wrong) working query Q, both expressed in SQL, provides actionable hints for the user to fix the working query so that it becomes semantically equivalent to the target. It is particularly useful in an educational setting, where novices can receive help from Qr-Hint without requiring extensive personal tutoring. Since there are many different ways to write a correct query, we do not want to base our hints completely on how Q* is written; instead, starting with the user's own working query, Qr-Hint purposefully guides the user through a sequence of steps that provably lead to a correct query, which will be equivalent to Q* but may still \"look\" quite different from it. Ideally, we would like Qr-Hint's hints to lead to the \"smallest\" possible corrections to Q. However, optimality is not always achievable in this case due to some foundational hurdles such as the undecidability of SQL query equivalence and the complexity of logic minimization. Nonetheless, by carefully decomposing and formulating the problems and developing principled solutions, we are able to provide provably correct and locally optimal hints through Qr-Hint. We show the effectiveness of Qr-Hint through quality and performance experiments as well as a user study in an educational setting.<\/jats:p>","DOI":"10.1145\/3654995","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-27","source":"Crossref","is-referenced-by-count":3,"title":["Qr-Hint: Actionable Hints Towards Correcting Wrong SQL Queries"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-3048-3867","authenticated-orcid":false,"given":"Yihao","family":"Hu","sequence":"first","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3764-1958","authenticated-orcid":false,"given":"Amir","family":"Gilad","sequence":"additional","affiliation":[{"name":"Hebrew University, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3058-7418","authenticated-orcid":false,"given":"Kristin","family":"Stephens-Martinez","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-8300-7891","authenticated-orcid":false,"given":"Sudeepa","family":"Roy","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0604-6790","authenticated-orcid":false,"given":"Jun","family":"Yang","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Foundations of databases: the logical level","author":"Abiteboul Serge","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of databases: the logical level. Addison-Wesley Longman Publishing Co., Inc."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2899415.2899464"},{"key":"e_1_2_1_3_1","first-page":"31","volume-title":"Verifix: Verified Repair of Programming Assignments.","author":"Ahmed Umair Z.","year":"2022","unstructured":"Umair Z. Ahmed, Zhiyu Fan, Jooyong Yi, Omar I. Al-Bataineh, and Abhik Roychoudhury. 2022. Verifix: Verified Repair of Programming Assignments. , Vol. 31, 4, Article 74 (jul 2022), bibinfonumpages31 pages."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208017"},{"key":"e_1_2_1_5_1","unstructured":"Marcelo Arenas Pablo Barcel\u00f3 Leonid Libkin Wim Martens and Andreas Pieris. 2022. Database Theory. Open source at https:\/\/github.com\/pdm-book\/community."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190662"},{"key":"e_1_2_1_7_1","unstructured":"TPC Benchmark. [n. d.]. http:\/\/www.tpc.org\/tpch."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 38th International Conference on Machine Learning (Proceedings of Machine Learning Research","volume":"791","author":"Berabi Berkay","year":"2021","unstructured":"Berkay Berabi, Jingxuan He, Veselin Raychev, and Martin Vechev. 2021. TFix: Learning to Fix Coding Errors with a Text-to-Text Transformer. In Proceedings of the 38th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 139), Marina Meila and Tong Zhang (Eds.). PMLR, 780--791. https:\/\/proceedings.mlr.press\/v139\/berabi21a.html"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180155.3180219"},{"key":"e_1_2_1_10_1","unstructured":"Stefan Brass and Christian Goldberg. 2004. Detecting Logical Errors in SQL Queries.. In Grundlagen von Datenbanken. 28--32."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/QSIC.2005.50"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2005.06.028"},{"key":"e_1_2_1_13_1","unstructured":"Stefan Brass Christian Goldberg and Alexander Hinneburg. 2003. Detecting semantic errors in SQL queries. Technical Report. Technical Report University of Halle. https:\/\/dbs.informatik.uni-halle.de\/sqllint\/semerr_techrep.pdf"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the International Symposium on Circuits and Systems. 42--48","author":"Brayton Robert K","year":"1982","unstructured":"Robert K Brayton, Gary D Hachtel, Lane A Hemachandra, A Richard Newton, and Alberto Luigi M Sangiovanni-Vincentelli. 1982. A comparison of logic minimization strategies using ESPRESSO: An APL program package for partitioned logic minimization. In Proceedings of the International Symposium on Circuits and Systems. 42--48."},{"key":"e_1_2_1_15_1","unstructured":"Tom Brown Benjamin Mann Nick Ryder Melanie Subbiah Jared D Kaplan Prafulla Dhariwal Arvind Neelakantan Pranav Shyam Girish Sastry Amanda Askell et al. 2020. Language models are few-shot learners. Advances in neural information processing systems Vol. 33 (2020) 1877--1901."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.011"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Ninth Annual ACM Symposium on Theory of Computing (STOC '77)","author":"Ashok","unstructured":"Ashok K. Chandra and Philip M. Merlin. 1977. Optimal Implementation of Conjunctive Queries in Relational Data Bases. In Proceedings of the Ninth Annual ACM Symposium on Theory of Computing (STOC '77). Association for Computing Machinery, 77--90."},{"key":"e_1_2_1_18_1","volume-title":"8th ACM IKDD CODS and 26th COMAD. 56--64.","author":"Chandra Bikash","unstructured":"Bikash Chandra, Ananyo Banerjee, Udbhas Hazra, Mathew Joseph, and S Sudarshan. 2021. Edit Based Grading of SQL Queries. In 8th ACM IKDD CODS and 26th COMAD. 56--64."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0395-0"},{"key":"e_1_2_1_20_1","first-page":"1943","article-title":"Sequencer: Sequence-to-sequence learning for end-to-end program repair","volume":"47","author":"Chen Zimin","year":"2019","unstructured":"Zimin Chen, Steve Kommrusch, Michele Tufano, Louis-No\u00ebl Pouchet, Denys Poshyvanyk, and Martin Monperrus. 2019. Sequencer: Sequence-to-sequence learning for end-to-end program repair. IEEE Transactions on Software Engineering, Vol. 47, 9 (2019), 1943--1959.","journal-title":"IEEE Transactions on Software Engineering"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236200"},{"key":"e_1_2_1_22_1","volume-title":"Cosette: An Automated Prover for SQL.. In CIDR.","author":"Chu Shumo","year":"2017","unstructured":"Shumo Chu, Chenglong Wang, Konstantin Weitz, and Alvin Cheung. 2017a. Cosette: An Automated Prover for SQL.. In CIDR."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3140587.3062348"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792734.1792766"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2735358"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626768"},{"key":"e_1_2_1_27_1","unstructured":"Chris Drake. [n. d.]. Python EDA. https:\/\/pyeda.readthedocs.io\/"},{"key":"e_1_2_1_28_1","unstructured":"Curtis Fenner. 2019. https:\/\/cs.stackexchange.com\/questions\/110674\/is-query-equivalence-decidable."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517898"},{"key":"e_1_2_1_30_1","volume-title":"7th Workshop on Teaching, Learning and Assessment in Databases","author":"Goldberg Christian","year":"2009","unstructured":"Christian Goldberg. 2009. Do you know SQL? About semantic errors in database queries. In 7th Workshop on Teaching, Learning and Assessment in Databases, Birmingham, UK, HEA. Citeseer."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2445583.2445586"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192387"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.3301930"},{"key":"e_1_2_1_34_1","volume-title":"Advances in Neural Information Processing Systems","volume":"32","author":"Gupta Rahul","year":"2019","unstructured":"Rahul Gupta, Aditya Kanade, and Shirish Shevade. 2019b. Neural attribution for semantic bug-localization in student programs. Advances in Neural Information Processing Systems , Vol. 32 (2019)."},{"key":"e_1_2_1_35_1","volume-title":"Qr-Hint: Actionable Hints Towards Correcting Wrong SQL Queries. arXiv preprint arXiv:2404.04352","author":"Hu Yihao","year":"2024","unstructured":"Yihao Hu, Amir Gilad, Kristin Stephens-Martinez, Sudeepa Roy, and Jun Yang. 2024. Qr-Hint: Actionable Hints Towards Correcting Wrong SQL Queries. arXiv preprint arXiv:2404.04352 (2024)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180155.3180245"},{"key":"e_1_2_1_37_1","volume-title":"Readings in Artificial Intelligence and Databases","author":"Imieli'nski Tomasz","unstructured":"Tomasz Imieli'nski and Witold Lipski Jr. 1989. Incomplete information in relational databases. In Readings in Artificial Intelligence and Databases. Elsevier, 342--360."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/211414.211419"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142363"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/42267.42273"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524168"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389767"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3395363.3397369"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319866"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of Data Mining for Educational Assessment and Feedback (ASSESS 2014)","author":"Perelman Daniel","year":"2014","unstructured":"Daniel Perelman, Sumit Gulwani, and Dan Grossman. 2014. Test-driven synthesis for automated feedback for introductory computer science assignments. Proceedings of Data Mining for Educational Assessment and Feedback (ASSESS 2014) (2014)."},{"key":"e_1_2_1_46_1","volume-title":"International conference on machine Learning. PMLR, 1093--1102","author":"Piech Chris","year":"2015","unstructured":"Chris Piech, Jonathan Huang, Andy Nguyen, Mike Phulsuksombati, Mehran Sahami, and Leonidas Guibas. 2015. Learning program embeddings to propagate feedback on student code. In International conference on machine Learning. PMLR, 1093--1102."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE-SEET52601.2021.00030"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s40593-015-0070-z"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322221"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(93)90040-N"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462195"},{"key":"e_1_2_1_52_1","first-page":"569","article-title":"The impossibility of an algorithm for the decision problem for finite domains","volume":"70","author":"Trahtenbrot Boris","year":"1950","unstructured":"Boris Trahtenbrot. 1950. The impossibility of an algorithm for the decision problem for finite domains. In Doklady Academii Nauk SSSR, Vol. 70. 569--572.","journal-title":"Doklady Academii Nauk SSSR"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17511-4_24"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192384"},{"key":"e_1_2_1_55_1","volume-title":"WeTune: Automatic Discovery and Verification of Query Rewrite Rules (SIGMOD '22)","author":"Wang Zhaoguo","year":"2022","unstructured":"Zhaoguo Wang, Zhou Zhou, Yicun Yang, Haoran Ding, Gansen Hu, Ding Ding, Chuzhe Tang, Haibo Chen, and Jinyang Li. 2022. WeTune: Automatic Discovery and Verification of Query Rewrite Rules (SIGMOD '22). Association for Computing Machinery, 94--107."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180155.3180182"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342267"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654995","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654995","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:41:17Z","timestamp":1755787277000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654995"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654995"],"URL":"https:\/\/doi.org\/10.1145\/3654995","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}