Witness Generation for Classical JSON Schema
Open Access
- 17 June 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 51 (4) , 1-45
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 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 — if it exists — 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 "uniqueItems" 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.Keywords
Funding Information
- European Commission (HORIZON-INFRA-2021-DEV-02-01)
- “SoBigData RI PPP: SoBigData RI Preparatory Phase Project” (n.101079043)
- PRIN Project “BioConceptum” (2022AEEKXS)
- NRRP MUR
This publication has 15 references indexed in Scilit:
- Negation-closure for JSON SchemaTheoretical Computer Science, 2023
- JSON2017
- Foundations of JSON Schema2016
- Extended Regular Expressions: Succinctness and DecidabilityTheory of Computing Systems, 2012
- Succinctness of the Complement and Intersection of Regular ExpressionsACM Transactions on Computational Logic, 2012
- Complexity of Decision Problems for XML Schemas and Chain Regular ExpressionsSIAM Journal on Computing, 2010
- Expressiveness and complexity of XML SchemaACM Transactions on Database Systems, 2006
- Optimizing Schema Languages for XML: Numerical Constraints and InterleavingLecture Notes in Computer Science, 2006
- Deciding Equivalence of Finite Tree AutomataSIAM Journal on Computing, 1990
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986