
















Abstract:Deciding JSON Schema inclusion - whether every instance of a schema $S$ is also an instance of a schema $S^{\prime}$ - is a building block for version and API compatibility checks, schema refactoring, and large-scale corpus analysis. The problem is EXPTIME-complete, and the two existing families of algorithms fail in practice in complementary ways: rule-based algorithms are fast but incomplete by design, while witness-generation algorithms are complete but so slow that, under any reasonable timeout, they are incomplete in practice as well. We show that this specific problem admits a way out. We redesign the normalization core of the complete algorithm, so that, on the easy cases, it mimics the behavior of the fast rule-based algorithm, without losing completeness. We prove that it is exactly as efficient as the rule-based approach on every inclusion that approach can prove, while remaining complete on all others. We validate this on a vast collection of real-world schemas and hand-crafted schemas. We show that our algorithm advances the state of the art, making tractable a range of use cases that were out of reach for existing tools.
From: Mohamed-Amine Baazizi [view email]
[v1]
Thu, 26 Mar 2026 10:53:47 UTC (129 KB)
[v2]
Mon, 13 Apr 2026 10:50:23 UTC (152 KB)
[v3]
Fri, 7 Aug 2026 09:08:29 UTC (168 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。