Thumbnail - No thumbnail

Witness Generation for JSON Schema

Attouche, Lyes; Baazizi, Mohamed-Amine; Colazzo, Dario; Ghelli, Giorgio; Sartiani, Carlo; Scherzinger, Stefanie (2022), Witness Generation for JSON Schema, Proceedings of the VLDB Endowment, 15, 13, p. 4002-4014. 10.14778/3565838.3565852

Type
Article accepté pour publication ou publié
External document link
https://hal.science/hal-03946256
Date
2022
Journal name
Proceedings of the VLDB Endowment
Volume
15
Number
13
Publisher
ACM - Association for Computing Machinery
Pages
4002-4014
Publication identifier
Metadata
Show full item record
Author(s)
Attouche, Lyes
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Baazizi, Mohamed-Amine
LIP6
Colazzo, Dario cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ghelli, Giorgio
Dipartimento di Informatica [Pisa]
Sartiani, Carlo
Dipartimento di Matematica Informatica ed Economia [DiMIE]
Scherzinger, Stefanie cc
Fakultät für Mathematik und Informatik [Passau]
Abstract (EN)
JSON Schema is a schema language for JSON documents, based on a complex combination of structural operators, Boolean operators (negation included), and recursive variables. The static analysis of JSON Schema documents comprises practically relevant problems, including schema satisfiability, inclusion, and equivalence. These 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. However, no witness generation algorithm has yet been formally described. We contribute a first, direct algorithm for JSON Schema witness generation, and study its effectiveness and efficiency in experiments over several schema collections, including thousands of real-world schemas.
Subjects / Keywords
JSON