{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T02:15:50Z","timestamp":1775873750927,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>\n                    Logic bugs can cause DBMSs to silently produce incorrect results for a given query, posing significant threats to software reliability and remaining challenging to detect. Join is a fundamental operation in DBMSs, enabling the combination of data from multiple tables; however, due to its complexity, it is also susceptible to logic bugs. Existing works detect logic bugs in join optimizations by altering query hints and system variables to alter the optimizer's choice of execution plans. However, these approaches struggle to detect logic bugs when query hints or system variables fail to influence the optimizer's behavior, or when the logic bugs reside in join implementation code that is unrelated to optimization. In this paper, we present\n                    <jats:bold>S<\/jats:bold>\n                    et\n                    <jats:bold>R<\/jats:bold>\n                    elation\n                    <jats:bold>S<\/jats:bold>\n                    ynthesis (SRS), a black-box testing approach that detects logic bugs of join implementation in DBMSs by leveraging set relations among different join operations. SRS applies transformations to the original join queries, including modifications to join types, join orders, and join conditions, while ensuring that the outputs of both the original and transformed queries preserve the expected set relations. Violations of these set relations indicate potential logic bugs. We realized SRS and evaluated it on five widely-used and extensively-tested DBMSs: MySQL, MariaDB, TiDB, PostgreSQL, and DuckDB. SRS uncovered 33 previously unknown and unique bugs, all of which have been confirmed, with 12 already fixed. Among these, 33 are logic bugs, demonstrating SRS's effectiveness and practicality in detecting logic bugs in the implementation of join operations within DBMSs.\n                  <\/jats:p>","DOI":"10.1145\/3769828","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-24","source":"Crossref","is-referenced-by-count":1,"title":["SRS: Detecting Logic Bugs of Join Implementation in DBMSs via Set Relation Synthesis"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-9331-1655","authenticated-orcid":false,"given":"Jinhui","family":"Lai","sequence":"first","affiliation":[{"name":"Nanchang University, Nanchang, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2848-6108","authenticated-orcid":false,"given":"Chi","family":"Zhang","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-8486-2019","authenticated-orcid":false,"given":"Bingyan","family":"Li","sequence":"additional","affiliation":[{"name":"Nanchang University, Nanchang, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-2685-7746","authenticated-orcid":false,"given":"Chenglin","family":"Liang","sequence":"additional","affiliation":[{"name":"Nanchang University, Nanchang, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1046-0337","authenticated-orcid":false,"given":"Jie","family":"Liang","sequence":"additional","affiliation":[{"name":"Beihang University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1908-5043","authenticated-orcid":false,"given":"Zhiyong","family":"Wu","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9759-878X","authenticated-orcid":false,"given":"Jingzhou","family":"Fu","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0955-503X","authenticated-orcid":false,"given":"Yu","family":"Jiang","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9293-8028","authenticated-orcid":false,"given":"Zichen","family":"Xu","sequence":"additional","affiliation":[{"name":"Nanchang University, Nanchang, China"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Bo Tang Andreas Seltenreich and Sjoerd Mullender. 2018. SQLsmith: a random SQL query generator. https:\/\/github.com\/anse1\/sqlsmith.git"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3597503.3639076"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654991"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247520"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083719"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3143561","article-title":"Metamorphic testing: A review of challenges and opportunities","volume":"51","author":"Chen Tsong Yueh","year":"2018","unstructured":"Tsong Yueh Chen, Fei-Ching Kuo, Huai Liu, Pak-Lok Poon, Dave Towey, TH Tse, and Zhi Quan Zhou. 2018. Metamorphic testing: A review of challenges and opportunities. ACM Computing Surveys (CSUR) 51, 1 (2018), 1-27.","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"e_1_2_1_8_1","unstructured":"DuckDB. 2025. https:\/\/duckdb.org\/"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191886"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2304510.2304525"},{"key":"e_1_2_1_11_1","first-page":"345","volume-title":"2023 USENIX Annual Technical Conference (USENIX ATC 23)","author":"Hao Zongyin","year":"2023","unstructured":"Zongyin Hao, Quanfeng Huang, Chengpeng Wang, Jianfeng Wang, Yushan Zhang, Rongxin Wu, and Charles Zhang. 2023. Pinolo: Detecting logical bugs in database management systems with approximate query synthesis. In 2023 USENIX Annual Technical Conference (USENIX ATC 23). 345-358."},{"key":"e_1_2_1_12_1","first-page":"4949","volume-title":"DynSQL: Stateful Fuzzing for Database Management Systems with Complex and Valid SQL Query Generation. In 32nd USENIX Security Symposium (USENIX Security 23)","author":"Jiang Zu-Ming","year":"2023","unstructured":"Zu-Ming Jiang, Jia-Ju Bai, and Zhendong Su. 2023. DynSQL: Stateful Fuzzing for Database Management Systems with Complex and Valid SQL Query Generation. In 32nd USENIX Security Symposium (USENIX Security 23). USENIX Association, Anaheim, CA, 4949-4965. https:\/\/www.usenix.org\/conference\/usenixsecurity23\/presentation\/jiang-zuming"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3691938.3691982"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3357377.3357382"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2008.34"},{"key":"e_1_2_1_16_1","first-page":"4309","volume-title":"Detecting Logical Bugs of DBMS with Coverage-based Guidance. In 31st USENIX Security Symposium (USENIX Security 22)","author":"Liang Yu","year":"2022","unstructured":"Yu Liang, Song Liu, and Hong Hu. 2022. Detecting Logical Bugs of DBMS with Coverage-based Guidance. In 31st USENIX Security Symposium (USENIX Security 22). USENIX Association, Boston, MA, 4309-4326. https:\/\/www.usenix.org\/conference\/usenixsecurity22\/presentation\/liang"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3510003.3510093"},{"key":"e_1_2_1_18_1","unstructured":"MariaDB. 2025. https:\/\/mariadb.org\/"},{"key":"e_1_2_1_19_1","first-page":"100","article-title":"Differential testing for software","volume":"10","author":"McKeeman William M","year":"1998","unstructured":"William M McKeeman. 1998. Differential testing for software. Digital Technical Journal 10, 1 (1998), 100-107.","journal-title":"Digital Technical Journal"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/128762.128764"},{"key":"e_1_2_1_21_1","unstructured":"MySQL. 2025. https:\/\/www.mysql.com\/"},{"key":"e_1_2_1_22_1","unstructured":"PostgreSQL. 2025. https:\/\/www.postgresql.org\/"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3368089.3409710"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428279"},{"key":"e_1_2_1_25_1","first-page":"667","volume-title":"14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)","author":"Rigger Manuel","year":"2020","unstructured":"Manuel Rigger and Zhendong Su. 2020. Testing Database Engines via Pivoted Query Synthesis. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). USENIX Association, 667-682. https:\/\/www.usenix.org\/conference\/osdi20\/presentation\/rigger"},{"key":"e_1_2_1_26_1","first-page":"618","volume-title":"VLDB","volume":"98","author":"Slutz Donald R","year":"1998","unstructured":"Donald R Slutz. 1998. Massive stochastic testing of SQL. In VLDB, Vol. 98. Citeseer, 618-622."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE48619.2023.00175"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588909"},{"key":"e_1_2_1_29_1","unstructured":"TiDB. 2025. https:\/\/www.pingcap.com\/"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993532"},{"key":"e_1_2_1_31_1","volume-title":"AFL: American Fuzzy Lop. https:\/\/github.com\/google\/AFL","author":"Zalewski Michal","year":"2015","unstructured":"Michal Zalewski. 2015. AFL: American Fuzzy Lop. https:\/\/github.com\/google\/AFL"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3709674"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3417260"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769828","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T04:35:22Z","timestamp":1775536522000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769828"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769828"],"URL":"https:\/\/doi.org\/10.1145\/3769828","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}