Validation of Modern JSON Schema: Formalization and Complexity

Explore a 19-minute conference talk from POPL 2024 that delves into the formalization and complexity of Modern JSON Schema validation. Learn about the new features introduced in recent versions of JSON Schema, including dynamic references and annotation-dependent validation, which have significantly altered the evaluation model. Discover how these changes have impacted the complexity of data validation, elevating it from polynomial to PSPACE complexity. Gain insights into the formal description of Modern JSON Schema, the PSPACE-completeness of its data validation problem, and the implications for schema and data complexities. Examine experimental results demonstrating the practical impact of dynamic references on validation performance, even with small schemas.

[POPL'24] Validation of Modern JSON Schema: Formalization and Complexity