Schema Validation

Every index in the previous lesson was built over fields that already existed, and none of them looked at what those fields carry: the copy.status index silently indexes a value that is not in the dictionary, and the publication years written as text that the first lesson measured also enter the index under their own type. A flexible schema does not bind whether a field is present, or its type, at write time; the first lesson counted this returning 5,991 or 3,491 documents instead of 3,990 in a range query, and left the question of how to place a rule to this lesson.

A rule can be placed. Schema validation is a rule set attached to a collection and evaluated at write time. This lesson produces two measures of that rule: the class of broken document it catches versus the class it misses, and the number of violations that appear when the rule is placed on an already-full collection, along with the cost of a backfill.

The Scope of a Rule

A validation rule carries three separate decisions. The first is scope: does the rule look only at top-level fields, or does it descend into nested documents and array elements. The second is closedness: does a field not listed in the rule count as a violation if it is present in the document. The third is mode: is a violating write rejected, or written and counted. All three decisions produce a measurable result.

// validator.mjs — a rule set attached to a collection. The rule is evaluated at write
// time and returns violations along with their class: missing field, wrong type,
// out-of-dictionary value, field not present in the rule. The rule can descend into
// nested documents and array elements.

export function typeName(d) {
  if (d === null) return "null";
  if (Array.isArray(d)) return "array";
  if (typeof d === "number") return Number.isInteger(d) ? "int" : "decimal";
  return typeof d === "string" ? "text" : "document";
}

export function bytes(d) {                       // lesson 01's encoding rule
  if (d === null || d === undefined) return 0;
  if (typeof d === "number") return Number.isInteger(d) ? 4 : 8;
  if (typeof d === "string") return 4 + Buffer.byteLength(d) + 1;
  const item = Array.isArray(d) ? d.map((v, i) => [String(i), v]) : Object.entries(d);
  return 5 + item.reduce((t, [a, v]) => t + 2 + Buffer.byteLength(a) + bytes(v), 0);
}

// rule: { fields: { name: { required, type, dictionary, element } }, closed }
// closed=true means every field not in the fields list is a violation.
export function validate(doc, rule, path = "") {
  const violation = [];
  for (const [name, spec] of Object.entries(rule.fields)) {
    const d = doc[name];
    if (d === undefined) {
      if (spec.required) violation.push({ class: "missing", field: path + name });
      continue;
    }
    if (typeName(d) !== spec.type) {
      violation.push({ class: "type", field: path + name });
      continue;
    }
    if (spec.dictionary && !spec.dictionary.includes(d)) violation.push({ class: "dictionary", field: path + name });
    if (spec.element) for (const o of d) violation.push(...validate(o, spec.element, `${path}${name}.`));
  }
  if (rule.closed)
    for (const name of Object.keys(doc))
      if (name !== "_k" && !(name in rule.fields)) violation.push({ class: "extra", field: path + name });
  return violation;
}

export class Collection {
  // mode: "reject" reverses a violating write, "warn" writes and counts, null if no rule.
  constructor(rule = null, mode = "reject") {
    Object.assign(this, { rule, mode, doc: new Map() });
    this.o = { written: 0, rejected: 0, warned: 0, bytesWritten: 0 };
  }
  write(b) {
    const violation = this.rule ? validate(b, this.rule) : [];
    if (violation.length) {
      if (this.mode === "reject") {
        this.o.rejected += 1;
        return false;
      }
      this.o.warned += 1;
    }
    this.doc.set(b._k, b);
    this.o.written += 1;
    this.o.bytesWritten += bytes(b);
    return true;
  }
  audit() {                                       // scanning a full collection against the rule
    const counts = new Map();
    let broken = 0;
    for (const b of this.doc.values()) {
      const violation = validate(b, this.rule);
      if (violation.length) broken += 1;
      for (const v of violation) counts.set(v.class + " " + v.field,
        (counts.get(v.class + " " + v.field) ?? 0) + 1);
    }
    return { broken, counts };
  }
}

Four Broken Classes, Two Rules

The measurement is done with the broken data the previous lessons left behind. NS7 (assumption): the catalog is 20,000 book documents, and the seed is 424242. NS8 (assumption): in one out of every eight records, the publication year is written as text. NS12 (assumption): in one out of every forty records, the publication year field is missing entirely. NS28 (assumption): in one out of every fifty records taken from an external source, one copy’s status is written with a value not in the dictionary, and in one out of every twenty the publication year is repeated under a second field name. Rationale: all four classes come from the same source — the absence of a definition binding the field’s name, type, and value set.

The rule is built in two forms. A is shallow: it looks only at top-level fields and is not closed. B descends to the element level and is closed. Both run on the same collection.

// rule-measurement.mjs — the same catalog is audited with two rules: a shallow rule that
// looks only at top-level fields, a full rule that descends into array elements and
// forbids any field not in the rule. Broken-document classes caught and missed, the rule
// placed on an already-full collection, and a backfill are all counted.
// validator.mjs is in the same directory.
import { Collection, validate, bytes } from "./validator.mjs";

let seed = 424242;                                        // visible seed
const random = () => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648;
const BRANCH = ["Central", "Bahcelievler", "Kadikoy", "Beyoglu", "Konak", "Nilufer"];
const STATUS = ["shelved", "checked_out", "in_repair"];
const TAGS = ["fiction", "history", "children", "poetry", "science", "reference"];

const CATALOG = [];
for (let i = 1; i <= 20000; i += 1) {
  const copy = [], tag = [];
  for (let j = 0, n = 1 + Math.floor(random() * 5); j < n; j += 1)
    copy.push({ barcode: `B${String(i * 10 + j).padStart(7, "0")}`,
      branch: BRANCH[Math.floor(random() * 6)], status: STATUS[Math.floor(random() * 3)] });
  for (let j = 0, n = 2 + Math.floor(random() * 3); j < n; j += 1)
    tag.push(TAGS[Math.floor(random() * 6)]);
  const b = { _k: `K-${String(i).padStart(5, "0")}`, author: `Author ${i % 4000}`,
    publication_year: 1950 + (i % 75), tag, copy };
  if (i % 8 === 0) b.publication_year = String(b.publication_year);  // NS8: year written as text
  if (i % 40 === 0) delete b.publication_year;                       // NS12: field absent
  if (i % 50 === 0) b.copy[0].status = "lost";                        // NS28: out-of-dictionary status
  if (i % 20 === 0) b.publicationYear = 1950 + (i % 75);              // NS28: field repeated under a second name
  CATALOG.push(b);
}

const FIELDS = {
  author: { required: true, type: "text" },
  publication_year: { required: true, type: "int" },
  tag: { required: true, type: "array" },
};
const RULE_A = { fields: FIELDS };                        // shallow: top-level fields
const RULE_B = {                                          // full: descends into elements, closed
  fields: { ...FIELDS, copy: { required: true, type: "array", element: {
    fields: { barcode: { required: true, type: "text" },
      branch: { required: true, type: "text", dictionary: BRANCH },
      status: { required: true, type: "text", dictionary: STATUS } }, closed: true } } },
  closed: true,
};

const CLASS = {
  "missing year": (b) => b.publication_year === undefined,
  "text year": (b) => typeof b.publication_year === "string",
  "out-of-dictionary status": (b) => b.copy.some((k) => !STATUS.includes(k.status)),
  "duplicate field": (b) => "publicationYear" in b,
};
console.log(`catalog ${CATALOG.length} documents, ${CATALOG.reduce((t, b) => t + bytes(b), 0)} bytes`);
for (const [name, f] of Object.entries(CLASS))
  console.log(`  ${name.padEnd(25)} ${CATALOG.filter(f).length} documents`);
console.log(`  ${"unique broken documents".padEnd(25)} ` +
  `${CATALOG.filter((b) => Object.values(CLASS).some((f) => f(b))).length}`);

// Which class each rule catches.
for (const [name, rule] of [["A shallow", RULE_A], ["B full", RULE_B]]) {
  const row = Object.entries(CLASS).map(([cname, f]) => {
    const items = CATALOG.filter(f);
    return `${cname} ${items.filter((b) => validate(b, rule).length > 0).length}/${items.length}`;
  });
  console.log(`${name.padEnd(11)} caught ` +
    `${CATALOG.filter((b) => validate(b, rule).length > 0).length} documents   ${row.join("  ")}`);
}

// The rule is placed on an already-full collection: violations on existing documents are counted first.
const collection = new Collection(RULE_B, "warn");
for (const b of CATALOG) collection.write(b);
const { broken, counts } = collection.audit();
console.log(`rule placed after the fact: ${broken} documents violating, ` +
  `${[...counts.values()].reduce((t, v) => t + v, 0)} violations:`);
for (const [name, n] of [...counts].sort((a, b) => b[1] - a[1])) console.log(`  ${name.padEnd(22)} ${n}`);

// The rule in "reject" mode, collection not yet fixed: what an ordinary update does.
function update(mode) {
  const c = new Collection(RULE_B, mode);
  for (let i = 0; i < 5000; i += 1) {
    const book = CATALOG[(i * 7) % CATALOG.length];
    const updated = { ...book, copy: book.copy.map((k) => ({ ...k })) };
    updated.copy[i % updated.copy.length].status = "shelved";
    c.write(updated);
  }
  return c.o;
}
const before = update("reject");
console.log(`5,000 status updates on the unfixed collection: ` +
  `${before.written} accepted, ${before.rejected} rejected`);

// Backfill: which violations close by machine, which need a decision.
let machine = 0, decision = 0, touched = 0, bytesWritten = 0;
for (const b of CATALOG) {
  if (validate(b, RULE_B).length === 0) continue;
  if (typeof b.publication_year === "string") { b.publication_year = Number(b.publication_year); machine += 1; }
  if ("publicationYear" in b) { delete b.publicationYear; machine += 1; }
  if (b.publication_year === undefined) decision += 1;
  decision += b.copy.filter((k) => !STATUS.includes(k.status)).length;
  touched += 1;
  bytesWritten += bytes(b);
}
console.log(`backfill touched ${touched} documents, wrote ${bytesWritten} bytes`);
console.log(`  violations closed by machine ${machine}, violations needing a decision ${decision}`);
console.log(`  documents still violating after the backfill ${collection.audit().broken}`);
const after = update("reject");
console.log(`same 5,000 updates on the fixed collection: ` +
  `${after.written} accepted, ${after.rejected} rejected`);

catalog 20000 documents, 7001623 bytes
  missing year              500 documents
  text year                 2000 documents
  out-of-dictionary status  400 documents
  duplicate field           1000 documents
  unique broken documents   3200
A shallow   caught 2500 documents   missing year 500/500  text year 2000/2000  out-of-dictionary status 100/400  duplicate field 500/1000
B full      caught 3200 documents   missing year 500/500  text year 2000/2000  out-of-dictionary status 400/400  duplicate field 1000/1000
rule placed after the fact: 3200 documents violating, 3900 violations:
  type publication_year  2000
  extra publicationYear  1000
  missing publication_year 500
  dictionary copy.status 400
5,000 status updates on the unfixed collection: 4215 accepted, 785 rejected
backfill touched 3200 documents, wrote 1103144 bytes
  violations closed by machine 3000, violations needing a decision 900
  documents still violating after the backfill 800
same 5,000 updates on the fixed collection: 4821 accepted, 179 rejected

Caught and Missed

The first five lines give the distribution of the breakage and carry a side finding: the year written as text is in 2,000 documents, not 2,500. One in forty of the one-in-eight records written as text are also records that carry no year field at all, and if the field is absent, it has no type. The two broken classes overlap; the classes total 3,900, the distinct document count is 3,200. This is why a violation count and a document count differ in a validation report.

The two rules produce different numbers on the same collection. Rule A, shallow, catches 2,500 documents; rule B, full, catches 3,200. The difference is in the rule’s scope, and it can be read line by line. On the year classes the two rules agree: 500/500 and 2,000/2,000. On the out-of-dictionary status class, A catches only 100 of the 400 — and these 100 documents are caught not because of the copy status but because of a year violation present in the same document. The class A truly misses is the full one: rule A never looks inside an array element at all. The duplicate-field class shows the same illusion: A catches 500 of the 1,000, every one of them thanks to a different violation.

From this comes how the rule should be read. The sentence “the rule caught 2,500 documents” is not a coverage measure; coverage only becomes visible when asked class by class. The shallow rule never touches the document model’s most-used structure — a nested document inside an array — and because it is not closed, it does not count a field written under the wrong name as a violation. A field written under the wrong name is a silent class: the query does not read it, the index does not index it, the rule does not see it.

The Rule Placed Late

When a rule is placed on an empty collection, its cost is only the check on the write path. When it is placed on a full collection, three separate numbers appear. The first is the violation count: 3,200 documents, 3,900 violations. The second is what happens to ordinary updates while the rule is in reject mode and the collection has not been fixed. When the second lesson’s third task, 5,000 copy status changes, runs on this collection, 785 are rejected. None of the rejected writes were introducing a new defect — they only wanted to set the status to shelved. The reason for rejection is that, in the embedded schema, an update rewrites the entire document, and the rewritten document still carries its own old violation. A rule placed without fixing the past stops today’s work.

The third number is the backfill itself. 3,200 documents are read and rewritten: 1,103,144 bytes, 15.8% of the collection. 3,000 of the backfill’s violations close by machine — a text year can be converted to a number, a duplicate field can be deleted. The remaining 900 violations need a decision: the year of the 500 documents that have no year at all cannot be derived, and what the 400 out-of-dictionary statuses mean can only be known by asking the library itself — is lost a typo, or a real status that belongs in the dictionary. After the backfill, 800 documents still violate, and the same 5,000 updates’ rejection count drops from 785 to 179.

The rule for the decision follows from these three numbers. A validation rule is not a schema definition, it is a check on the write path; its coverage is measured class by class, and the order for placing it on a full collection is this: first measure in warn mode, then backfill, then switch to reject mode. The reverse order stops every task that touches an unfixed document.

Summary

• Schema validation is a rule attached to a collection and evaluated at write time; its scope, closedness, and mode are each chosen separately.
• A shallow rule fully catches two of four broken classes; it catches 100 of the array element’s 400 dictionary violations and 500 of the 1,000 duplicate-field violations, and it catches these documents not because of their own class but because of a different violation in the same document.
• Violation count and document count differ: 3,900 violations spread across 3,200 documents, because the broken classes overlap.
• When a rule is placed on a full collection in reject mode, 785 of 5,000 ordinary status updates are rejected; the rejected writes were not introducing a new defect.
• A backfill touches 3,200 documents and writes 1,103,144 bytes; 3,000 violations close by machine, 900 need a decision, 800 documents remain violating, and the rejection count drops to 179.

Next Step

The backfill touched 3,200 documents one at a time, and this makes visible an assumption the topic has not stated until now: every write covered a single document. The document model’s atomicity guarantee sits exactly here — a write to one document happens either completely or not at all, but no such bond exists between two writes to two documents. If the backfill had been interrupted halfway, part of the collection would be fixed and part not, with no record saying which part was which. The same question shows up in the library’s daily work: issuing one loan changes a copy’s status, a member’s loan count, and a loan record together. The next lesson counts where single-document atomicity is enough for this task and where it is not, by running the same task in two schemas, and measures the cost of a multi-document transaction.