CSE Roadmap

Common tier · about 3 hours · 5 parts

Part 2 of 5 · 1 min read

Lossless decomposition

Splitting a table so the original can be reconstructed exactly by joining the pieces back together.

Think of cutting a photograph into two pieces along a clean line. Taping them back together exactly reproduces the original. Cutting it badly, overlapping or losing a sliver, does not.

In plain words: a decomposition is lossless if joining the resulting tables back together, on their shared columns, reproduces exactly the original table, with no rows lost and no new, incorrect rows created. A decomposition is guaranteed lossless if the shared column is a key of at least one of the resulting tables.

A worked example. Splitting customers (customer_id, postal_code, city) into customers (customer_id, postal_code) and postal_codes (postal_code, city) is lossless, since postal_code is a key of postal_codes.

The key lines.

-- confirming losslessness: joining back should reproduce the original exactly
SELECT c.customer_id, c.postal_code, p.city
FROM customers c JOIN postal_codes p ON c.postal_code = p.postal_code;

Lossless decomposition

A lossless decomposition splits a table such that joining the resulting pieces back together reproduces the original exactly. It is guaranteed when the shared column is a key of at least one resulting table.

Example: splitting out postal_codes, keyed on postal_code, is lossless, since joining it back to customers on postal_code recreates the original table exactly.