Optimistic Data Generation for JSON Schema

JSON Schema is an expressive schema language for describing JSON documents which combines structural assertions with Boolean operators, including negation, and is able to express recursion. In typical situations, JSON Schema is used to validate JSON documents to ensure safety of operations processing these JSONdata. In many other situations, it is important to generate JSONdocuments starting from a JSON Schema schema as it allows for testing applications and for assessing interesting properties like scalability of processing engines. While existing work [6, 8] addressed the witness generation problem, by discarding the uniqueItems operator, our goal lifts this restriction and addresses the problem of generating multiple instances from a given schema. Since the witness generation problem, which is equivalent to checking the satisfiability in JSON Schema, is known to be EXPTIME-complete even when uniqueItems is absent [10], our solution adopts an optimistic approach which trades completeness for soundness and efficiency. From a practical point of view, our approach is very satisfactory since, on most real-life scenarios, it is very efficient and highly precise, as testified by our experiments.