{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T11:56:41Z","timestamp":1781697401289,"version":"3.54.5"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T00:00:00Z","timestamp":1781654400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["HORIZON-INFRA-2021-DEV-02-01"],"award-info":[{"award-number":["HORIZON-INFRA-2021-DEV-02-01"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"name":"\u201cSoBigData RI PPP: SoBigData RI Preparatory Phase Project\u201d","award":["n.101079043"],"award-info":[{"award-number":["n.101079043"]}]},{"name":"PRIN Project \u201cBioConceptum\u201d","award":["2022AEEKXS"],"award-info":[{"award-number":["2022AEEKXS"]}]},{"name":"NRRP MUR"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2026,12,31]]},"abstract":"<jats:p>\n                    JSON Schema is an important, evolving standard schema language for families of JSON documents. It is based on a complex combination of structural and Boolean operators, including negation, as well as mutually recursive variables. The static analysis of JSON Schema documents comprises practically relevant problems, including schema satisfiability, inclusion, and equivalence. These three can be reduced to witness generation: given a schema, generate an element of the schema \u2014 if it exists \u2014 otherwise report unsatisfiability. Schema satisfiability, inclusion, and equivalence have been shown to be decidable, by reduction to reachability in alternating tree automata. However, no witness generation algorithm has yet been formally described. We contribute a first, direct algorithm for JSON Schema witness generation. We study its effectiveness and efficiency, in experiments over several schema collections, including thousands of real-world schemas. Our focus is on the completeness of the language (where we only exclude the\n                    <jats:monospace>\"uniqueItems\"<\/jats:monospace>\n                    operator), on the ability of the algorithm to run in reasonable time on a large set of real-world examples, despite the exponential complexity of the problem, and on proving its correctness and completeness.\n                  <\/jats:p>","DOI":"10.1145\/3799416","type":"journal-article","created":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T05:41:35Z","timestamp":1772257295000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Witness Generation for Classical JSON Schema"],"prefix":"10.1145","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-8454-6364","authenticated-orcid":false,"given":"Lyes","family":"Attouche","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris Dauphine - PSL","place":["Paris, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2728-5838","authenticated-orcid":false,"given":"Mohamed-Amine","family":"Baazizi","sequence":"additional","affiliation":[{"name":"Sorbonne Universite, LIP6","place":["Paris, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6031-0049","authenticated-orcid":false,"given":"Dario","family":"Colazzo","sequence":"additional","affiliation":[{"name":"LAMSADE, Universit\u00e9 Paris Dauphine - PSL","place":["Paris, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0596-6395","authenticated-orcid":false,"given":"Giorgio","family":"Ghelli","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Universit\u00e0 di Pisa","place":["Pisa, Italy"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6514-3569","authenticated-orcid":false,"given":"Carlo","family":"Sartiani","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi della Basilicata","place":["Potenza, Italy"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1960-6171","authenticated-orcid":false,"given":"Stefanii","family":"Scherzinger","sequence":"additional","affiliation":[{"name":"Universitat Passau","place":["Passau, Germany"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,17]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"2022. JSON schema validator. Retrieved 19 September 2022 from https:\/\/github.com\/networknt\/json-schema-validator"},{"key":"e_1_3_3_3_2","unstructured":"2024. hypothesis-jsonschema. Available on GitHub. Retrieved 4 December 2024 from https:\/\/github.com\/python-jsonschema\/hypothesis-jsonschema"},{"key":"e_1_3_3_4_2","unstructured":"2024. JSON Schema Store. Retrieved 23 March 2026 from https:\/\/www.schemastore.org"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/551350"},{"key":"e_1_3_3_6_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1007\/978-3-642-02882-3_19","volume-title":"Proceedings","volume":"5609","author":"Ackerman Margareta","year":"2009","unstructured":"Margareta Ackerman and Erkki M\u00e4kinen. 2009. Three new algorithms for regular language enumeration. In Proceedingsof the International Computing and Combinatorics Conference.Hung Q. Ngo (Ed.), Lecture Notes in Computer Science, Vol. 5609, Springer, 178\u2013191."},{"key":"e_1_3_3_7_2","unstructured":"Snowplow Analytics. 2022. Iglu Central. Retrieved 19 September 2022 from commit hash 726168e. https:\/\/github.com\/snowplow\/iglu-central"},{"key":"e_1_3_3_8_2","unstructured":"Henry Andrews. 2023. Modern JSON Schema. Retrieved 4 December 2024 from https:\/\/modern-json-schema.com\/"},{"key":"e_1_3_3_9_2","volume-title":"Database Theory, Querying Data","author":"Arenas Marcelo","year":"2022","unstructured":"Marcelo Arenas, Pablo Barcel\u00f3, Leonid Libkin, Wim Martens, and Andreas Pieris. 2022. Database Theory, Querying Data. Preliminary Version."},{"key":"e_1_3_3_10_2","first-page":"19","volume-title":"Proceedings of the ER 2021","author":"Attouche Lyes","year":"2021","unstructured":"Lyes Attouche, Mohamed Amine Baazizi, Dario Colazzo, Yunchen Ding, Michael Fruth, Giorgio Ghelli, Carlo Sartiani, and Stefanie Scherzinger. 2021. A test suite for JSON schema containment. In Proceedings of the ER 2021. 19\u201324."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.5441\/002\/edbt.2021.86"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565852"},{"key":"e_1_3_3_13_2","doi-asserted-by":"crossref","unstructured":"Lyes Attouche Mohamed Amine Baazizi Dario Colazzo Giorgio Ghelli Carlo Sartiani and Stefanie Scherzinger. 2024. Validation of modern JSON schema: Formalization and complexity. In Proceedings of the ACM on Programming Languages 8 POPL (2024) 1451\u20131481.","DOI":"10.1145\/3632891"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","unstructured":"Mohamed Amine Baazizi Dario Colazzo Giorgio Ghelli Carlo Sartiani and Stefanie Scherzinger. 2023. Negation-closure for JSON schema. Theoretical Computer Science 955 (April 2023) 113823. DOI:10.1016\/j.tcs.2023.113823","DOI":"10.1016\/j.tcs.2023.113823"},{"key":"e_1_3_3_15_2","volume-title":"Formal Specification, Expressiveness, and Complexity Analysis for JSON Schema","author":"Barr\u00eda Fernando Su\u00e1rez","year":"2016","unstructured":"Fernando Su\u00e1rez Barr\u00eda. 2016. Formal Specification, Expressiveness, and Complexity Analysis for JSON Schema. Master\u2019s thesis. Pontificia Universidad Cat\u00f3lica de Chile, Santiago, Chile. Retrieved from https:\/\/repositorio.uc.cl\/handle\/11534\/16908"},{"key":"e_1_3_3_16_2","unstructured":"Guillaume Baudart Martin Hirzel Kiran Kate Parikshit Ram and Avraham Shinnar. 2020. Lale: Consistent automated machine learning. arXiv:2007.01977. Retrieved from https:\/\/arxiv.org\/abs\/2007.01977"},{"key":"e_1_3_3_17_2","unstructured":"Jim Blackler. 2022. JSON Generator. Retrieved September 19 2022 from https:\/\/github.com\/jimblackler\/jsongenerator"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056120"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676819"},{"key":"e_1_3_3_20_2","volume-title":"Tree Automata Techniques and Applications","author":"Comon Hubert","year":"2008","unstructured":"Hubert Comon, Max Dauchet, R\u00e9mi Gilleron, Florent Jacquemard, Denis Lugiez, Christof L\u00f6ding, Sophie Tison, and Marc Tommasi. 2008. Tree Automata Techniques and Applications (2008), 262 pages. Available online at https:\/\/hal.inria.fr\/hal-03367725\/file\/tata.pdf."},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9389-0"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_19"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2071368.2071372"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3460319.3464796"},{"key":"e_1_3_3_25_2","unstructured":"Andrew Habib Avraham Shinnar Martin Hirzel and Michael Pradel. 2021. jsonsubschema (Replication Package). Retrieved 4 December 2024 from https:\/\/zenodo.org\/records\/4729863"},{"key":"e_1_3_3_26_2","unstructured":"Martin Hansen. 2023. json-schema-merge-allof. Retrieved 4 December 2024 from https:\/\/github.com\/mokkabonna\/json-schema-merge-allof commit hash 133f848."},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/1454320"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3450577"},{"key":"e_1_3_3_29_2","unstructured":"Kubernetes. 2022. Kubernetes JSON Schemas. Retrieved 4 December 2024 from https:\/\/github.com\/instrumenta\/kubernetes-json-schema commit hash b3cf311."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/080743457"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166076"},{"key":"e_1_3_3_32_2","unstructured":"Anders M\u00f8ller. 2021. dk.brics.automaton \u2013 Finite-State Automata and Regular Expressions for Java. Available at Retrieved 19 September 2022 from https:\/\/www.brics.dk\/automaton\/"},{"key":"e_1_3_3_33_2","unstructured":"JSON Schema Org. 2022. JSON Schema Test Suite. Retrieved 19 September 2022 from https:\/\/github.com\/json-schema-org\/JSON-Schema-Test-Suite"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2883029"},{"key":"e_1_3_3_35_2","unstructured":"The Washington Post. 2022. ans-schema. Retrieved 19 September 2022 from https:\/\/github.com\/washingtonpost\/ans-schema commit hash abdd6c211."},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1137\/0219027"},{"key":"e_1_3_3_37_2","volume-title":"The Complexity of Decision Problems in Automata Theory and Logic","author":"Stockmeyer Larry J.","year":"1974","unstructured":"Larry J. Stockmeyer. 1974. The Complexity of Decision Problems in Automata Theory and Logic. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_3_3_38_2","unstructured":"Arash Vahidi. 2020. JDD. Retrieved 19 September 2022 from https:\/\/bitbucket.org\/vahidi\/jdd\/src\/master\/"},{"key":"e_1_3_3_39_2","volume-title":"JSON Schema Validation: A Vocabulary for Structural Validation of JSON - draft-handrews-json-schema-validation-02","author":"Wright A.","year":"2019","unstructured":"A. Wright, H. Andrews, and B. Hutton. 2019. JSON Schema Validation: A Vocabulary for Structural Validation of JSON - draft-handrews-json-schema-validation-02. Technical Report. Internet Engineering Task Force."},{"key":"e_1_3_3_40_2","volume-title":"JSON Schema Validation: A Vocabulary for Structural Validation of JSON - draft-bhutton-json-schema-validation-00","author":"Wright A.","year":"2020","unstructured":"A. Wright, H. Andrews, and B. Hutton. 2020. JSON Schema Validation: A Vocabulary for Structural Validation of JSON - draft-bhutton-json-schema-validation-00. Technical Report. Internet Engineering Task Force."},{"key":"e_1_3_3_41_2","volume-title":"JSON Schema Validation: A Vocabulary for Structural Validation of JSON - draft-wright-json-schema-validation-01","author":"Wright A.","year":"2017","unstructured":"A. Wright, G. Luff, and H. Andrews. 2017. JSON Schema Validation: A Vocabulary for Structural Validation of JSON - draft-wright-json-schema-validation-01. Technical Report. Internet Engineering Task Force."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3799416","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T11:29:17Z","timestamp":1781695757000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3799416"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,17]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,12,31]]}},"alternative-id":["10.1145\/3799416"],"URL":"https:\/\/doi.org\/10.1145\/3799416","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,17]]},"assertion":[{"value":"2024-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-06-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}