Kenton Labs / Computation

Relational algebra

Check query identities over explicit finite set semantics, and retain counterexamples to invalid rewrites.

The vocabulary.

These definitions state the objects and properties used by the dataset. The complete instance specification remains the authority for each result.

Set semantics: Each value occurs at most once; duplicates and NULLs are absent.
Relational identity: Two query expressions with the same output on every admitted relation.
Counterexample: A concrete set assignment making the outputs differ.

How the dataset works.

Three deterministic instances define this family. Each includes its input model, a checked result, evidence, and an acceptance procedure. Download the complete dataset JSON ↘ or the area’s readable source ↘.

Acceptance procedure

Enumerate every subset of the universe.
Evaluate both expressions on every triple of sets.
Compare the complete finite-domain outputs.
Replay a concrete sample, including a differing output for a false identity.

Cost and scope

A universe of n values has 2ⁿ subsets; three relation inputs create 2³ⁿ assignments.

A common failure

SQL bag semantics, NULL values, and outer joins can invalidate a rewrite valid for mathematical sets.

Worked records.

Three instances expose concrete claims and the artifacts that establish or refute them. Expand a record for the problem, checker reasoning, formal payload, and verification metadata.

KL-FCS-061
Relational algebraIntersection distributes over unionComplete relation assignments · 512 triples

The problem

Decide the proposed set identity over every triple of finite-universe relations.

The checked result

Equivalent on the stated domain: yes.

The finite universe makes every relation assignment enumerable. The sample output illustrates the identity or supplies a direct refutation.

Why the checker accepts it

Enumerate every subset of the universe.
Evaluate both expressions on every triple of sets.
Compare the complete finite-domain outputs.
Replay a concrete sample, including a differing output for a false identity.

Formal specification

{
  "universe_size": 3,
  "law": "intersection-distribution",
  "semantics": "Mathematical sets; unique values; no NULL or tuple multiplicity."
}

Claim and evidence

{
  "claim": {
    "equivalent_on_domain": true
  },
  "witness": {
    "sample": {
      "A": [
        0,
        1
      ],
      "B": [
        1,
        2
      ],
      "C": [
        0
      ],
      "left": [
        0,
        1
      ],
      "right": [
        0,
        1
      ]
    }
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 512 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

A universe of n values has 2ⁿ subsets; three relation inputs create 2³ⁿ assignments.

Finite enumeration is bounded to this universe; these artifacts do not certify an SQL optimizer or measured execution speed.

A boundary to investigate

SQL bag semantics, NULL values, and outer joins can invalidate a rewrite valid for mathematical sets. Add equijoin trees, bag multiplicities, NULL handling, and an explicit query-cost model.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-062 ↘Related KL-FCS-063 ↘

KL-FCS-062
Relational algebraSubtract after a unionComplete relation assignments · 4096 triples

The problem

Decide the proposed set identity over every triple of finite-universe relations.

The checked result

Equivalent on the stated domain: yes.

The finite universe makes every relation assignment enumerable. The sample output illustrates the identity or supplies a direct refutation.

Why the checker accepts it

Enumerate every subset of the universe.
Evaluate both expressions on every triple of sets.
Compare the complete finite-domain outputs.
Replay a concrete sample, including a differing output for a false identity.

Formal specification

{
  "universe_size": 4,
  "law": "difference-distribution",
  "semantics": "Mathematical sets; unique values; no NULL or tuple multiplicity."
}

Claim and evidence

{
  "claim": {
    "equivalent_on_domain": true
  },
  "witness": {
    "sample": {
      "A": [
        0,
        1
      ],
      "B": [
        1,
        2
      ],
      "C": [
        1
      ],
      "left": [
        0,
        2
      ],
      "right": [
        0,
        2
      ]
    }
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 4096 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

A universe of n values has 2ⁿ subsets; three relation inputs create 2³ⁿ assignments.

Finite enumeration is bounded to this universe; these artifacts do not certify an SQL optimizer or measured execution speed.

A boundary to investigate

SQL bag semantics, NULL values, and outer joins can invalidate a rewrite valid for mathematical sets. Add equijoin trees, bag multiplicities, NULL handling, and an explicit query-cost model.

Verification and provenance metadata

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-061 ↘Related KL-FCS-063 ↘

KL-FCS-063
Relational algebraSet difference is not commutativeComplete relation assignments · 64 triples

The problem

Decide the proposed set identity over every triple of finite-universe relations.

The checked result

Equivalent on the stated domain: no.

The finite universe makes every relation assignment enumerable. The sample output illustrates the identity or supplies a direct refutation.

Why the checker accepts it

Enumerate every subset of the universe.
Evaluate both expressions on every triple of sets.
Compare the complete finite-domain outputs.
Replay a concrete sample, including a differing output for a false identity.

Formal specification

{
  "universe_size": 2,
  "law": "difference-commutativity",
  "semantics": "Mathematical sets; unique values; no NULL or tuple multiplicity."
}

Claim and evidence

{
  "claim": {
    "equivalent_on_domain": false
  },
  "witness": {
    "sample": {
      "A": [
        0
      ],
      "B": [],
      "C": [],
      "left": [
        0
      ],
      "right": []
    }
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 64 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

A universe of n values has 2ⁿ subsets; three relation inputs create 2³ⁿ assignments.

Finite enumeration is bounded to this universe; these artifacts do not certify an SQL optimizer or measured execution speed.

A boundary to investigate

SQL bag semantics, NULL values, and outer joins can invalidate a rewrite valid for mathematical sets. Add equijoin trees, bag multiplicities, NULL handling, and an explicit query-cost model.

Verification and provenance metadata

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-061 ↘Related KL-FCS-062 ↘

Go further.

Add equijoin trees, bag multiplicities, NULL handling, and an explicit query-cost model.

Questions to investigate

SQL bag semantics, NULL values, and outer joins can invalidate a rewrite valid for mathematical sets.
Which assumption in the specification can be changed to make the current evidence insufficient?
Add equijoin trees, bag multiplicities, NULL handling, and an explicit query-cost model.

Conceptual references

These sources explain the surrounding theory. The linked material was not imported as a dataset, and these records do not claim checking by the source’s software.

Primary conceptual reference ↗

Related areas

Algorithms Graph algorithms Game theory