# Relational algebra

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

## Definitions

- **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.

## Acceptance procedure

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

## Complexity

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

## Common failure

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

## Extensions

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

## Instances

- KL-FCS-061: Intersection distributes over union — Equivalent on the stated domain: yes
- KL-FCS-062: Subtract after a union — Equivalent on the stated domain: yes
- KL-FCS-063: Set difference is not commutative — Equivalent on the stated domain: no

## References

- https://www.postgresql.org/docs/current/explicit-joins.html