JSON Schema Inclusion through Refutational Normalization: Reconciling Efficiency and Completeness
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917402778796032 |
|---|---|
| author | Baazizi, Mohamed-Amine Ali, Nour El Houda Ben Colazzo, Dario Ghelli, Giorgio Klessinger, Stefan Sartiani, Carlo Scherzinger, Stefanie |
| author_facet | Baazizi, Mohamed-Amine Ali, Nour El Houda Ben Colazzo, Dario Ghelli, Giorgio Klessinger, Stefan Sartiani, Carlo Scherzinger, Stefanie |
| contents | JSON Schema is the de facto standard for describing the structure of JSON documents. Reasoning about JSON Schema inclusion -- whether every instance satisfying a schema S1 also satisfies a schema S2 -- is a key building block for a variety of tasks, including version and API compatibility checks, schema refactoring tools, and large-scale schema corpus analysis. Existing approaches fall into two families: rule-based algorithms that are efficient but incomplete and witness generation-based algorithms that are complete but oftentimes extremely slow. This paper introduces a new approach that reconciles the efficiency of rule-based procedures with the completeness of the witness-generation technique, by enriching the latter with a specialized form of normalization. This refutational normalization paves the way for use-cases that are too hard for current tools. Our experiments with real-world and synthetic schemas show that the refutational normalization greatly advances the state-of-the-art in JSON Schema inclusion checking. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_25306 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | JSON Schema Inclusion through Refutational Normalization: Reconciling Efficiency and Completeness Baazizi, Mohamed-Amine Ali, Nour El Houda Ben Colazzo, Dario Ghelli, Giorgio Klessinger, Stefan Sartiani, Carlo Scherzinger, Stefanie Databases JSON Schema is the de facto standard for describing the structure of JSON documents. Reasoning about JSON Schema inclusion -- whether every instance satisfying a schema S1 also satisfies a schema S2 -- is a key building block for a variety of tasks, including version and API compatibility checks, schema refactoring tools, and large-scale schema corpus analysis. Existing approaches fall into two families: rule-based algorithms that are efficient but incomplete and witness generation-based algorithms that are complete but oftentimes extremely slow. This paper introduces a new approach that reconciles the efficiency of rule-based procedures with the completeness of the witness-generation technique, by enriching the latter with a specialized form of normalization. This refutational normalization paves the way for use-cases that are too hard for current tools. Our experiments with real-world and synthetic schemas show that the refutational normalization greatly advances the state-of-the-art in JSON Schema inclusion checking. |
| title | JSON Schema Inclusion through Refutational Normalization: Reconciling Efficiency and Completeness |
| topic | Databases |
| url | https://arxiv.org/abs/2603.25306 |