{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T02:20:35Z","timestamp":1773886835170,"version":"3.50.1"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2024,1,2]],"date-time":"2024-01-02T00:00:00Z","timestamp":1704153600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["385808805"],"award-info":[{"award-number":["385808805"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["101079043"],"award-info":[{"award-number":["101079043"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100021856","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"crossref","award":["2022AEEKXS"],"award-info":[{"award-number":["2022AEEKXS"]}],"id":[{"id":"10.13039\/501100021856","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,1,2]]},"abstract":"<jats:p>\n            JSON Schema is the de-facto standard schema language for JSON data. The language went through many minor revisions, but the most recent versions of the language, starting from Draft 2019-09, added two novel features,\n            <jats:italic toggle=\"yes\">dynamic references<\/jats:italic>\n            and\n            <jats:italic toggle=\"yes\">annotation-dependent validation<\/jats:italic>\n            , that change the evaluation model.\n            <jats:italic toggle=\"yes\">Modern JSON Schema<\/jats:italic>\n            is the name used to indicate all versions from Draft 2019-09, which are characterized by these new features, while\n            <jats:italic toggle=\"yes\">Classical JSON Schema<\/jats:italic>\n            is used to indicate the previous versions.\n          <\/jats:p>\n          <jats:p>These new \u201cmodern\u201d features make the schema language quite difficult to understand and have generated many discussions about the correct interpretation of their official specifications; for this reason, we undertook the task of their formalization. During this process, we also analyzed the complexity of data validation in Modern JSON Schema, with the idea of confirming the polynomial complexity of Classical JSON Schema validation, and we were surprised to discover a completely different truth: data validation, which is expected to be an extremely efficient process, acquires, with Modern JSON Schema features, a PSPACE complexity.<\/jats:p>\n          <jats:p>In this paper, we give the first formal description of Modern JSON Schema, which we have discussed with the community of JSON Schema tool developers, and which we consider a central contribution of this work. We then prove that its data validation problem is PSPACE-complete. We prove that the origin of the problem lies in the Draft 2020-12 version of dynamic references, and not in annotation-dependent validation. We study the schema and data complexities, showing that the problem is PSPACE-complete with respect to the schema size even with a fixed instance but is in P when the schema is fixed and only the instance size is allowed to vary. Finally, we run experiments that show that there are families of schemas where the difference in asymptotic complexity between dynamic and static references is extremely visible, even with small schemas.<\/jats:p>","DOI":"10.1145\/3632891","type":"journal-article","created":{"date-parts":[[2024,1,5]],"date-time":"2024-01-05T20:48:51Z","timestamp":1704487731000},"page":"1451-1481","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Validation of Modern JSON Schema: Formalization and Complexity"],"prefix":"10.1145","volume":"8","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, Paris, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2728-5838","authenticated-orcid":false,"given":"Mohamed-Amine","family":"Baazizi","sequence":"additional","affiliation":[{"name":"Sorbonne University, Paris, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6031-0049","authenticated-orcid":false,"given":"Dario","family":"Colazzo","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Dauphine - PSL, Paris, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0596-6395","authenticated-orcid":false,"given":"Giorgio","family":"Ghelli","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6514-3569","authenticated-orcid":false,"given":"Carlo","family":"Sartiani","sequence":"additional","affiliation":[{"name":"University of Basilicata, Potenza, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1960-6171","authenticated-orcid":false,"given":"Stefanie","family":"Scherzinger","sequence":"additional","affiliation":[{"name":"University of Passau, Passau, Germany"}]}],"member":"320","published-online":{"date-parts":[[2024,1,5]]},"reference":[{"key":"e_1_3_1_2_1","unstructured":"Ajv JSON Schema validator. 2023. https:\/\/ajv.js.org Retrieved 10 January 2023."},{"key":"e_1_3_1_3_1","unstructured":"Hyperjump JSON Schema Validator. 2023. https:\/\/json-schema.hyperjump.io\/ Online tool. Retrieved 10 January 2023."},{"key":"e_1_3_1_4_1","unstructured":"JSON Schema validators. 2023. https:\/\/json-schema.org\/implementations.html#validators Retrieved 10 January 2023."},{"key":"e_1_3_1_5_1","unstructured":"Henry Andrews. 2023. Modern JSON Schema. Available online at https:\/\/modern-json-schema.com\/."},{"key":"e_1_3_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565852"},{"key":"e_1_3_1_7_1","author":"Attouche Lyes","year":"2023","unstructured":"Lyes Attouche, Mohamed-Amine Baazizi, Dario Colazzo, Giorgio Ghelli, Carlo Sartiani, and Stefanie Scherzinger. 2023a. ModernJSONSchemaValidator. https:\/\/gitlab.lip6.fr\/jsonschema\/modernjsonschemavalidator","journal-title":"ModernJSONSchemaValidator"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.10019663"},{"key":"e_1_3_1_9_1","article-title":"Validation of Modern JSON Schema: Formalization and Complexity","author":"Attouche Lyes","year":"2023","unstructured":"Lyes Attouche, Mohamed-Amine Baazizi, Dario Colazzo, Giorgio Ghelli, Carlo Sartiani, and Stefanie Scherzinger. 2023c. Validation of Modern JSON Schema: Formalization and Complexity. arXiv:2307.10034 [cs.DB]","journal-title":"arXiv:2307.10034 [cs.DB]"},{"key":"e_1_3_1_10_1","first-page":"437","article-title":"Schemas And Types For JSON Data","author":"Baazizi Mohamed Amine","year":"2019","unstructured":"Mohamed Amine Baazizi, Dario Colazzo, Giorgio Ghelli, and Carlo Sartiani. 2019a. Schemas And Types For JSON Data. In Proc. EDBT. 437\u2013439.","journal-title":"Proc. EDBT"},{"key":"e_1_3_1_11_1","first-page":"2060","article-title":"Schemas and Types for JSON Data: From Theory to Practice","author":"Baazizi Mohamed Amine","year":"2019","unstructured":"Mohamed Amine Baazizi, Dario Colazzo, Giorgio Ghelli, and Carlo Sartiani. 2019b. Schemas and Types for JSON Data: From Theory to Practice. In Proc. SIGMOD Conference. 2060\u20132063.","journal-title":"Proc. SIGMOD Conference"},{"key":"e_1_3_1_12_1","unstructured":"Julian Bergman. 2023a. Bowtie JSON Schema Meta Validator. https:\/\/github.com\/bowtie-json-schema\/bowtie Online tool. Version 0.67.0."},{"key":"e_1_3_1_13_1","unstructured":"Julian Bergman. 2023b. JSON-Schema-Test-Suite (draft2020-12). https:\/\/github.com\/json-schema-org\/JSON-Schema-Test-Suite\/tree\/main\/tests\/draft2020-12"},{"key":"e_1_3_1_14_1","doi-asserted-by":"crossref","unstructured":"T. Berners-Lee R. Fielding and L. Masinter. January 2005. Uniform Resource Identifier (URI): Generic Syntax. Technical Report. Internet Engineering Task Force. https:\/\/datatracker.ietf.org\/doc\/html\/rfc3986","DOI":"10.17487\/rfc3986"},{"key":"e_1_3_1_15_1","first-page":"123","article-title":"JSON: Data model, Query languages and Schema specification","author":"Bourhis Pierre","year":"2017","unstructured":"Pierre Bourhis, Juan L. Reutter, Fernando Su\u00e1rez, and Domagoj Vrgoc. 2017. JSON: Data model, Query languages and Schema specification. In Proc. PODS. 123\u2013135. https:\/\/doi.org\/10.1145\/3034786.3056120","journal-title":"Proc. PODS"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2019.101478"},{"key":"e_1_3_1_17_1","unstructured":"Francis Galiegue and Kris Zyp. 2013. JSON Schema: interactive and non interactive validation - draft-fge-json-schema-validation-00. Technical Report. Internet Engineering Task Force. https:\/\/tools.ietf.org\/html\/draft-fge-json-schema-validation-00"},{"key":"e_1_3_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800001143"},{"key":"e_1_3_1_19_1","unstructured":"Mark Jacobson. 2021. The meaning of \"additionalProperties\" has changed. Available online at https:\/\/github.com\/orgs\/json-schema-org\/discussions\/57."},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/080743457"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166076"},{"key":"e_1_3_1_22_1","unstructured":"Oliver Neal. 2022. Ambiguous behaviour of \u201cadditionalProperties\u201d when invalid. Available online at https:\/\/github.com\/json-schema-org\/json-schema-spec\/issues\/1172."},{"key":"e_1_3_1_23_1","unstructured":"JSON Schema Org. 2022. JSON Schema. Available at https:\/\/json-schema.org."},{"key":"e_1_3_1_24_1","first-page":"263","article-title":"Foundations of JSON Schema","author":"Pezoa Felipe","year":"2016","unstructured":"Felipe Pezoa, Juan L. Reutter, Fernando Su\u00e1rez, Mart\u00edn Ugarte, and Domagoj Vrgoc. 2016. Foundations of JSON Schema. In Proc. WWW. 263\u2013273.","journal-title":"Proc. WWW"},{"key":"e_1_3_1_25_1","volume-title":"Introduction to the Theory of Computation - Third Edition","author":"Sipser Michael","year":"2012","unstructured":"Michael Sipser. 2012. Introduction to the Theory of Computation - Third Edition. Cengage."},{"key":"e_1_3_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804029"},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_3_1_28_1","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. https:\/\/tools.ietf.org\/html\/draft-handrews-json-schema-validation-02 Retrieved 19 September 2022.","journal-title":"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_1_29_1","author":"Wright A.","year":"2022","unstructured":"A. Wright, H. Andrews, B. Hutton, and G. Dennis. 2022. JSON Schema: A Media Type for Describing JSON Documents - draft-bhutton-json-schema-01. Technical Report. Internet Engineering Task Force. https:\/\/json-schema.org\/draft\/2020-12\/json-schema-core.html Retrieved 15 October 2022.","journal-title":"JSON Schema: A Media Type for Describing JSON Documents - draft-bhutton-json-schema-01. Technical Report. Internet Engineering Task Force"},{"key":"e_1_3_1_30_1","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. https:\/\/tools.ietf.org\/html\/draft-wright-json-schema-validation-01 Retrieved 19 September 2022.","journal-title":"JSON Schema Validation: A Vocabulary for Structural Validation of JSON - draft-wright-json-schema-validation-01. Technical Report. Internet Engineering Task Force"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632891","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632891","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:05:10Z","timestamp":1751659510000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632891"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,2]]},"references-count":29,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2024,1,2]]}},"alternative-id":["10.1145\/3632891"],"URL":"https:\/\/doi.org\/10.1145\/3632891","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,2]]},"assertion":[{"value":"2024-01-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}