Problem solving

Enough cases to cover

Grain: one row per generated case · Class: Generation · Signals: enough cases, all combinations, every pair, test matrix, cover, generate then filter · Operators: COVER, × (generate)

The problem

"We test across three browsers, three operating systems and two plans. The full matrix is 18 combinations, and Safari only runs on macOS. Give me the smallest test suite that still exercises every pair of factor values — and prove it is complete."

How to recognise it

The question is about producing rows rather than filtering existing ones — enough cases, every combination, all pairs, a test matrix, generate and then narrow. The tell is a combinatorial space that explodes and a budget that cannot afford all of it. Two moves make the class:

• Generate the candidate space, then constrain it — a cross product (×) proposes every combination, and a σ removes the invalid ones. Generator proposes, selection disposes.
• Thin it to just enough — COVER t keeps a small subset in which every combination of t values still appears at least once. t = 2 is all-pairs, the usual sweet spot.

The data

Three factors — the full space is 3 × 3 × 2 = 18.

Browser := [
| browser |
|---------|
| Chrome  |
| Firefox |
| Safari  |
];

OS := [
| os      |
|---------|
| Windows |
| macOS   |
| Linux   |
];

Plan := [
| plan |
|------|
| Free |
| Pro  |
];

Recipe 1: generate, then constrain (× and σ)

The cross product is the generator: it proposes every combination. A σ then removes the ones that cannot happen — Safari runs only on macOS:

Full  := { Browser × OS × Plan };
Valid := { σ browser ≠ "Safari" ∨ os = "macOS" (Full) };
query { γ COUNT(*) → valid_combos (Valid) };

Full  := { Browser CROSS OS CROSS Plan };
Valid := { SELECT browser != "Safari" OR os = "macOS" (Full) };
query { GROUP COUNT(*) -> valid_combos (Valid) };

 valid_combos
 ────────────
           14
(1 row)

Recipe 2: thin to a covering suite (COVER)

COVER 2 keeps a subset in which every pair of factor values still appears together at least once. Crucially, it derives the pairs it must cover from the constrained input — so the invalid combinations are never demanded, and the constraint comes for free:

Suite := { COVER 2 (Valid) };
query { τ browser, os (Suite) };

Suite := { COVER 2 (Valid) };
query { SORT browser, os (Suite) };

 browser  os       plan
 ───────  ───────  ────
 Chrome   Linux    Free
 Chrome   Windows  Free
 Chrome   macOS    Pro
 Firefox  Linux    Pro
 Firefox  Windows  Pro
 Firefox  macOS    Free
 Safari   macOS    Free
 Safari   macOS    Pro
(8 rows)

Eight cases instead of the full fourteen, yet every browser–os, browser–plan and os–plan pair is present somewhere. The τ only sorts for reading; COVER emits in selection order.

Prove it is complete, in-language. Coverage is verifiable with a difference — every pair in the valid space minus every pair in the suite is empty when the design is complete, so no external oracle is needed:

query { (π browser, os (Valid)) − (π browser, os (Suite)) };

query { (PROJECT browser, os (Valid)) DIFF (PROJECT browser, os (Suite)) };

 browser  os
 ───────  ──
(0 rows)

query { σ browser = "Safari" (Suite) };

query { SELECT browser = "Safari" (Suite) };

 browser  os     plan
 ───────  ─────  ────
 Safari   macOS  Free
 Safari   macOS  Pro
(2 rows)

Variations

• COVER 1 keeps every value once (the cheapest); COVER t at t = the number of columns is every distinct row (equivalent to δ). t interpolates between them.
• Bias which candidates win — order the input first: COVER 2 (τ priority DESC (Valid)), since the greedy search breaks ties toward earlier rows.
• An unbounded generator (a numeric range, the naturals) must be bounded before a blocking operator like COVER, γ or δ consumes it — a σ or TOP below it. A cross product of finite tables, as here, is already bounded.

Pitfalls

• Strength is required and is not a filter. COVER (…) with no t is an error. COVER 2 does not reduce the semantics — it selects rows; it never invents a combination that was not in the input.
• Greedy, not minimal. COVER finds a near-minimal suite, not a provably minimal one — it may be a row or two above the theoretical optimum. That is the right trade-off for the cost of an exact solver.
• Constrain before you cover, not after. Filtering the suite after COVER can break coverage. Put the σ below COVER so the coverage universe is the valid space — then the constraint is respected by construction.
• A blocking generator over an unbounded input is rejected. Bound it first.

Check it

• Verify coverage in-language with the difference above — do not trust the row count alone. An empty difference for every factor pair is the proof.
• Add a constraint and confirm the excluded combinations appear in neither the valid space nor the suite (no Safari on Windows).
• Compare the suite size to the full matrix — a covering suite should be markedly smaller, or COVER is not earning its place.

Related

• Which rows, and which columns — the σ that constrains the generated space is ordinary selection.
• What changed, what differs — the coverage proof is a set difference.
• Reference pages (docs/reference): cover, cross, distinct, difference.