Preprint
Abstract
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 assertions, and features negation and recursion. The static analysis of JSON Schema documents comprises practically relevant problems, including schema satisfiability, inclusion, and equivalence. These three problems can be reduced to witness generation: given a schema, generate an element of the schema, if it exists, and report failure otherwise. 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 uniqueItems operator, and on the ability of the algorithm to run in a reasonable time on a large set of real-world examples, despite the exponential complexity of the underlying problem.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Negation-closure for JSON SchemaTheoretical Computer Science, 2023
- An Empirical Study on the “Usage of Not” in Real-World JSON Schema Documents2021
- Finding data compatibility bugs with JSON subschema checking2021
- What Are Real JSON Schemas Like?2019
- JSON2017
- Foundations of JSON Schema2016
- Jsongen2014
- Succinctness of the Complement and Intersection of Regular ExpressionsACM Transactions on Computational Logic, 2012
- Introduction to automata theory, languages, and computation, 2nd editionACM SIGACT News, 2001
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986