{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:59:56Z","timestamp":1775638796944,"version":"3.50.1"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:p>Relational DBMS implementations are expected to adhere to SQL standards. However, there are currently no tools available that can automatically verify this conformance. The main reasons are twofold. First, the SQL standard specification, documented in natural language, tends to be ambiguous and is not directly executable. Second, it is difficult to generate test queries that thoroughly cover all aspects, e.g., keywords and parameters, defined in the SQL specification. In this work, we introduce the first method for semantic conformance testing of RDBMSs. Our contributions are threefold. Firstly, we formally define the denotational semantics of SQL and implement them in Prolog, creating an executable reference RDBMS for differential testing against existing RDBMSs. Secondly, we propose three coverage criteria based on these formal semantics, along with a coverage-guided query generation algorithm that effectively generates queries achieving high semantic coverage. Lastly, we apply our approach to six widely-used and thoroughly tested RDBMSs, e.g., MySQL, PostgreSQL and OceanBase, uncovering 19 bugs and 13 inconsistencies, all of which are confirmed by RDBMS developers.<\/jats:p>","DOI":"10.14778\/3712221.3712247","type":"journal-article","created":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T18:03:04Z","timestamp":1744048984000},"page":"850-862","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Semantic Conformance Testing of Relational DBMS"],"prefix":"10.14778","volume":"18","author":[{"given":"Shuang","family":"Liu","sequence":"first","affiliation":[{"name":"Renmin University of China"}]},{"given":"Chenglin","family":"Tian","sequence":"additional","affiliation":[{"name":"Beijing University of Posts and Telecommunications"}]},{"given":"Jun","family":"Sun","sequence":"additional","affiliation":[{"name":"Singapore Management University"}]},{"given":"Ruifeng","family":"Wang","sequence":"additional","affiliation":[{"name":"College of Intelligence and Computing, Tianjin University"}]},{"given":"Wei","family":"Lu","sequence":"additional","affiliation":[{"name":"Renmin University of China"}]},{"given":"Yongxin","family":"Zhao","sequence":"additional","affiliation":[{"name":"Shanghai Key Laboratory of Trustworthy Computing, East China, Normal University"}]},{"given":"Yinxing","family":"Xue","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China"}]},{"given":"Junjie","family":"Wang","sequence":"additional","affiliation":[{"name":"College of Intelligence and Computing, Tianjin University"}]},{"given":"Xiaoyong","family":"Du","sequence":"additional","affiliation":[{"name":"Renmin University of China"}]}],"member":"320","published-online":{"date-parts":[[2025,4,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"https:\/\/www.amazon.com\/. accessed on","year":"2023","unstructured":"Amazon. 1995. https:\/\/www.amazon.com\/. accessed on November 10, 2023."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293880.3294107"},{"key":"e_1_2_1_3_1","volume-title":"https:\/\/www.booking.com\/. accessed on","year":"2023","unstructured":"Booking. 1996. https:\/\/www.booking.com\/. accessed on November 10, 2023."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180155.3180202"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1985.232223"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3395032.3395322"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3475726.3475730"},{"key":"e_1_2_1_8_1","volume-title":"An Ordered Bag Semantics for SQL. Master's thesis","author":"Chinaei Hamid R","unstructured":"Hamid R Chinaei. 2007. An Ordered Bag Semantics for SQL. Master's thesis. University of Waterloo."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3058728"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3140587.3062348"},{"key":"e_1_2_1_11_1","volume-title":"Programming in PROLOG","author":"Clocksin William F","unstructured":"William F Clocksin and Christopher S Mellish. 2003. Programming in PROLOG. Springer Science & Business Media."},{"key":"e_1_2_1_12_1","volume-title":"https:\/\/duckdb.org. accessed on","author":"DB.","year":"2023","unstructured":"DuckDB. 2019. https:\/\/duckdb.org. accessed on November 10, 2023."},{"key":"e_1_2_1_13_1","volume-title":"https:\/\/www.ebay.com\/. accessed on","year":"2023","unstructured":"eBay. 1995. https:\/\/www.ebay.com\/. accessed on November 10, 2023."},{"key":"e_1_2_1_14_1","volume-title":"https:\/\/www.facebook.com\/. accessed on","year":"2023","unstructured":"Facebook. 2004. https:\/\/www.facebook.com\/. accessed on November 10, 2023."},{"key":"e_1_2_1_15_1","unstructured":"International Organization for Standardization. 2016. ISO\/IEC 9075-2:2016: Information technology - Database languages - SQL\/Foundation. (2016)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3551349.3560431"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3395032.3395327"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151113.3151116"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40000.2020.00066"},{"key":"e_1_2_1_20_1","volume-title":"https:\/\/github.com\/JSQLParser\/JSqlParser. accessed on","year":"2023","unstructured":"JSQLParser. 2011. https:\/\/github.com\/JSQLParser\/JSqlParser. accessed on November 10, 2023."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3357377.3357382"},{"key":"e_1_2_1_22_1","volume-title":"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). 4309--4326."},{"key":"e_1_2_1_23_1","unstructured":"Shuang Liu Chenglin Tian Jun Sun Ruifeng Wang Wei Lu Yongxin Zhao Yinxing Xue Junjie Wang and Xiaoyong Du. 2024. Conformance Testing of Relational DBMS Against SQL Specifications (Technical Report). https:\/\/github.com\/DBMSTesting\/Technical-report."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages. 237--248","author":"Malecha Gregory","year":"2010","unstructured":"Gregory Malecha, Greg Morrisett, Avraham Shinnar, and Ryan Wisnesky. 2010. Toward a verified relational database management system. In Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages. 237--248."},{"key":"e_1_2_1_25_1","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Eli Upfal. 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis (2nd ed.). Cambridge University Press, USA.","edition":"2"},{"key":"e_1_2_1_26_1","volume-title":"https:\/\/www.mysql.com. last accessed on","author":"SQL.","year":"2023","unstructured":"MySQL. 1995. https:\/\/www.mysql.com. last accessed on November 10, 2023."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/111197.111212"},{"key":"e_1_2_1_28_1","volume-title":"https:\/\/en.oceanbase.com\/. accessed on","year":"2023","unstructured":"OceanBase. 2016. https:\/\/en.oceanbase.com\/. accessed on November 10, 2023."},{"key":"e_1_2_1_29_1","volume-title":"https:\/\/www.postgresql.org. accessed on","author":"SQL.","year":"2023","unstructured":"PostgreSQL. 1996. https:\/\/www.postgresql.org. accessed on November 10, 2023."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-022-09632-4"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3368089.3409710"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428279"},{"key":"e_1_2_1_33_1","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). 667--682."},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1016\/j.jlap.2010.03.012","article-title":"An overview of the K semantic framework","volume":"79","author":"Ros Grigore","year":"2010","unstructured":"Grigore Ros, u and Traian Florin \u015eerb\u0103nut\u0103. 2010. An overview of the K semantic framework. The Journal of Logic and Algebraic Programming 79, 6 (2010), 397--434.","journal-title":"The Journal of Logic and Algebraic Programming"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3510003.3510112"},{"key":"e_1_2_1_36_1","volume-title":"SQLsmith: a random SQL query generator. https:\/\/github.com\/anse1\/sqlsmith. accessed on","author":"Seltenreich Andreas","year":"2022","unstructured":"Andreas Seltenreich, Bo Tang, and Sjoerd Mullender. 2019. SQLsmith: a random SQL query generator. https:\/\/github.com\/anse1\/sqlsmith. accessed on November 11, 2022."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/645924.671199"},{"key":"e_1_2_1_38_1","volume-title":"https:\/\/github.com\/sqlancer\/sqlancer. accessed on","year":"2023","unstructured":"SQLancer. 2019. https:\/\/github.com\/sqlancer\/sqlancer. accessed on November 10, 2023."},{"key":"e_1_2_1_39_1","volume-title":"https:\/\/www.sqlite.org\/index.html. accessed on","year":"2023","unstructured":"SQLite. 2000. https:\/\/www.sqlite.org\/index.html. accessed on November 10, 2023."},{"key":"e_1_2_1_40_1","volume-title":"An error occurred when the CAST function converted the numerical value in the form of scientific notation. https:\/\/sqlite.org\/forum\/forumpost\/3f085531bf. accessed on","author":"Tian Chenglin","year":"2022","unstructured":"Chenglin Tian. 2022. An error occurred when the CAST function converted the numerical value in the form of scientific notation. https:\/\/sqlite.org\/forum\/forumpost\/3f085531bf. accessed on November 11, 2022."},{"key":"e_1_2_1_41_1","volume-title":"https:\/\/www.pingcap.com\/tidb\/. accessed on","author":"DB.","year":"2023","unstructured":"TiDB. 2016. https:\/\/www.pingcap.com\/tidb\/. accessed on November 10, 2023."},{"key":"e_1_2_1_42_1","volume-title":"Translating SQL into the relational algebra. Course notes, Hasselt University and Universit\u00e9 Libre de Bruxelles","author":"den Bussche Jan Van","year":"2009","unstructured":"Jan Van den Bussche and Stijn Vansummeren. 2009. Translating SQL into the relational algebra. Course notes, Hasselt University and Universit\u00e9 Libre de Bruxelles (2009)."},{"key":"e_1_2_1_43_1","volume-title":"Qex: Symbolic SQL query explorer. In Logic for Programming, Artificial Intelligence, and Reasoning: 16th International Conference, LPAR-16, Dakar, Senegal, April 25--May 1","author":"Veanes Margus","year":"2010","unstructured":"Margus Veanes, Nikolai Tillmann, and Jonathan De Halleux. 2010. Qex: Symbolic SQL query explorer. In Logic for Programming, Artificial Intelligence, and Reasoning: 16th International Conference, LPAR-16, Dakar, Senegal, April 25--May 1, 2010, Revised Selected Papers 16. Springer, 425--446."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE-SEIP52600.2021.00042"},{"key":"e_1_2_1_45_1","volume-title":"A Symbolic Approach to Proving Query Equivalence Under Bag Semantics. arXiv preprint arXiv:2004.00481","author":"Zhou Qi","year":"2020","unstructured":"Qi Zhou, Joy Arulraj, Shamkant Navathe, William Harris, and Jinpeng Wu. 2020. A Symbolic Approach to Proving Query Equivalence Under Bag Semantics. arXiv preprint arXiv:2004.00481 (2020)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3512345"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3712221.3712247","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T18:20:44Z","timestamp":1744050044000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3712221.3712247"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11]]},"references-count":46,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["10.14778\/3712221.3712247"],"URL":"https:\/\/doi.org\/10.14778\/3712221.3712247","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,11]]},"assertion":[{"value":"2025-04-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}