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-03946256Date
2022Journal name
Proceedings of the VLDB EndowmentVolume
15Number
13Publisher
ACM - Association for Computing Machinery
Pages
4002-4014
Publication identifier
Metadata
Show full item recordAuthor(s)
Attouche, LyesLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Baazizi, Mohamed-Amine
LIP6
Colazzo, Dario

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

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
JSONRelated items
Showing items related by title and author.
-
Attouche, Lyes; Baazizi, Mohamed-Amine; Colazzo, Dario; Ding, Yunchen; Fruth, Michael; Ghelli, Giorgio; Sartiani, Carlo; Scherzinger, Stefanie (2021) Communication / Conférence
-
Baazizi, Mohamed-Amine; Colazzo, Dario; Ghelli, Giorgio; Sartiani, Carlo; Scherzinger, Stefanie (2020) Communication / Conférence
-
Fruth, Michael; Baazizi, Mohamed-Amine; Colazzo, Dario; Ghelli, Giorgio; Sartiani, Carlo; Scherzinger, Stefanie (2020) Communication / Conférence
-
Baazizi, Mohamed-Amine; Colazzo, Dario; Ghelli, Giorgio; Sartiani, Carlo; Scherzinger, Stefanie (2021) Communication / Conférence
-
Baazizi, Mohamed-Amine; Colazzo, Dario; Ghelli, Giorgio; Sartiani, Carlo (2019) Communication / Conférence