Validating Streaming JSON Documents with Learned VPAs
In: Tools and Algorithms for the Construction and Analysis of Systems (TACAS) 2023, pp. 271-289; (2022) S. 271-289
Online
report
Zugriff:
We present a new streaming algorithm to validate JSON documents against a set of constraints given as a JSON schema. Among the possible values a JSON document can hold, objects are unordered collections of key-value pairs while arrays are ordered collections of values. We prove that there always exists a visibly pushdown automaton (VPA) that accepts the same set of JSON documents as a JSON schema. Leveraging this result, our approach relies on learning a VPA for the provided schema. As the learned VPA assumes a fixed order on the key-value pairs of the objects, we abstract its transitions in a special kind of graph, and propose an efficient streaming algorithm using the VPA and its graph to decide whether a JSON document is valid for the schema. We evaluate the implementation of our algorithm on a number of random JSON documents, and compare it to the classical validation algorithm.
Comment: 46 pages, 10 figures, published at TACAS 2023
Titel: |
Validating Streaming JSON Documents with Learned VPAs
|
---|---|
Autor/in / Beteiligte Person: | Bruyère, Véronique ; Perez, Guillermo A. ; Staquet, Gaëtan |
Link: | |
Quelle: | Tools and Algorithms for the Construction and Analysis of Systems (TACAS) 2023, pp. 271-289; (2022) S. 271-289 |
Veröffentlichung: | 2022 |
Medientyp: | report |
DOI: | 10.1007/978-3-031-30823-9_14 |
Schlagwort: |
|
Sonstiges: |
|