Validation of Modern JSON Schema: Formalization and Complexity

Lyes Attouche (1, 2) , Mohamed-Amine Baazizi (3) , Dario Colazzo (2) , Giorgio Ghelli (4) , Carlo Sartiani (5) , Stefanie Scherzinger (6)

1 Université Paris Dauphine-PSL
2 LAMSADE - Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision
3 BD - Bases de Données
4 DI - Dipartimento di Informatica [Pisa]
5 DiMIE - Dipartimento di Matematica Informatica ed Economia
6 Universität Passau [Passau]

JSON Schema is the standard language used to describe the structure of JSON documents. The standard is constantly evolving, and Draft 2019-09 added two new features, dynamic references and annotation-dependent validation. This addition changes the evaluation model, so that the versions after Draft 2019-09 are now called Modern JSON Schema, while Classical JSON Schema indicates those that precede it. These new features solve important practical problems, but they are not easy to understand, and the modification of the evaluation model renders the theory that has been developed for Classical JSON Schema not applicable to the new versions. In this paper we face these problems. We give the first formal description of Modern JSON Schema, we then use this formal apparatus in order to study the complexity of validation for Modern JSON Schema, and we present a surprising result: with the addition of dynamic references, the problem of JSON Schema validation moves from PTIME-complete to PSPACE-hard. We also show that the problem is PSPACE-complete, by providing a polynomial space algorithm. We show that the problem is in PTIME in the special case when there is a fixed bound on the number of distinct dynamic references in each schema, by defining a deterministic polynomial time algorithm. We study the influence of schema size and of instance size, showing that the problem is PSPACE-complete with respect to the schema size, but is in PTIME when the schema is fixed and only the instance size is allowed to vary. Finally, we run experiments that show that there are schemas where the asymptotic complexity difference between dynamic and static references is extremely visible with small schemas already. CCS Concepts: • Theory of computation → Type theory.

Mots clés: JSON Schema; complexity of validation

Domaines: Informatique [cs]

Lyes Attouche, Mohamed-Amine Baazizi, Dario Colazzo, Giorgio Ghelli, Carlo Sartiani, et al.. Validation of Modern JSON Schema: Formalization and Complexity. 2023. ⟨hal-04042629v1⟩