ReCG · PVLDB 2024 · Worked Example

Discovering a JSON schema from the leaves up

ReCG infers a set of JSON schemas from documents alone. It resolves instance trees bottom-up, clusters the partially derived objects at each level, generalizes the clusters into a spectrum of candidate schema sets, and lets the minimum description length principle pick the winner inside a beam search. Step through one small collection below.

{ }

Given three JSON documents and no schema, which set of JSON schemas should describe the collection — specific enough to reject junk, general enough to accept the documents we have not seen yet?

OUTPUTZ = {S₁, S₂}

1 / 10

ProblemJSON schema discovery: from documents alone, derive a schema set that is neither one-schema-per-document nor accept-anything.

IdeaExisting algorithms derive schemas top-down and must classify a node before its children are known. ReCG goes bottom-up: children first, so each decision is informed.

Stage 1The lowest level is resolved first: every primitive value becomes a primitive schema node. Arrays would be handled here too (generalized to a single ∗ edge, then clustered once).

Stage 2 · clusterAt level 2 the three info objects are CD-instances. They are clustered by a Jaccard-style distance over (key, child-schema) pairs: {c₁, c₃} together, c₂ apart.

Stage 2 · generalizeFrom the clusters ReCG does not pick one schema set — it enumerates a spectrum, from the initial clusters to repeatedly merged (more general) ones. Each is a sibling state of stage 2.

MDLStates compete on minimum description length: bits to write the schemas plus bits to write the data given the schemas. The balanced state wins.

Stage 3At the roots the same cluster → generalize → cost loop runs once more. Here the two-schema set beats the merged one: merging would admit key combinations nobody has seen.

SearchThe whole run is a beam search over states: each stage clusters, generalizes into siblings, scores them with MDL and keeps the best three.

OutputThe result is an ordinary JSON Schema set: two document types sharing one info definition with an optional key.

✦ Why it worksInformed decisions (bottom-up), a spectrum of candidates (cluster-and-generalize) and a principled judge (MDL) — each fixes one failure of top-down discovery.

Navigate with ← →, the buttons, the dots, or swipe on touch · 10 frames