When you split one table into two, which property of the functional dependencies guarantees that the split is lossless - that rejoining the fragments cannot invent rows - and what does 'dependency preserving' add on top of that?

## The problem decomposition solves and creates Splitting a wide relation into narrower ones removes redundancy, but a careless split destroys information. Two criteria judge a split: can the original data be reconstructed, and can the original rules still be enforced. ## Lossless join A decomposition of R into R1 and R2 is **lossless** (better: non-additive) if for every legal instance r of R, ``` projection(r, R1) JOIN projection(r, R2) = r ``` The join can never lose rows - every original row reappears - so the failure mode is always *extra* rows, called spurious tuples. Hence "non-additive join" is the more accurate term. **The test.** The split is lossless if and only if `(R1 ∩ R2) -> R1` or `(R1 ∩ R2) -> R2` is implied by F. Compute the closure of the shared attribute set and see whether it covers either fragment. **Why it works.** If the shared attributes form a key of R2, each row of R1 matches exactly one row of R2 in the join, so no row multiplies. If the overlap is a key of neither side, one shared value can match several rows on both sides, and the cross product manufactures combinations that never existed. **Concrete failure.** Take `R(employee, project, department)` where an employee works on many projects and belongs to one department. Split into `R1(employee, project)` and `R2(project, department)`. The overlap is `{project}`, and `project` is a key of neither fragment - a project has many employees and, across employees, several departments. Rejoining pairs every employee on a project with every department on that project, fabricating rows that assert employees belong to departments they never did. Splitting instead into `R1(employee, project)` and `R2(employee, department)` gives overlap `{employee}`, which is a key of R2 because `employee -> department`, so that split is lossless. **Binary versus n-ary.** The two-way test above is only for binary splits. For decomposition into three or more fragments the general test is the chase algorithm; in practice, splits produced by repeatedly applying the binary rule are lossless by construction, and the synthesis approach guarantees losslessness by ensuring some fragment contains a candidate key of the original relation. ## Dependency preservation Even a lossless split can make a rule unenforceable. Define the **projection** of F onto Ri as all dependencies in F+ whose attributes lie entirely within Ri. The decomposition is **dependency preserving** when the union of these projections implies the whole of F. If a dependency `X -> Y` ends up with X in one fragment and Y in another, no constraint on a single table can enforce it. Enforcement then requires either a join executed on every write - which is racy unless serialised or backed by extra locking - or a trigger, or acceptance that the rule can be broken. In a concurrent system two transactions can each insert a row that is individually legal while jointly violating the cross-table dependency, and neither sees the other. ## The two properties are independent You can have losslessness without preservation, and (for badly chosen splits) preservation without losslessness. The classic example is `R(city, street, zip)` with `{city, street} -> zip` and `zip -> city`. Splitting into `(street, zip)` and `(zip, city)` is lossless, since the overlap `{zip}` determines `city` and hence the second fragment. But `{city, street} -> zip` now spans both fragments and cannot be enforced by any single-table constraint: nothing stops two rows that together assign the same city and street to two different zips. ## Which one can you give up? **Losslessness is mandatory.** A lossy decomposition means the original information is not recoverable, so the design is simply wrong. There is no operational mitigation. **Dependency preservation is negotiable but costly.** Losing it converts a declarative constraint into procedural enforcement, which is exactly the class of rule that decays: it is enforced in one write path and forgotten in a backfill script or an admin tool. When a decomposition forces the choice, options are to accept the cross-fragment check with an explicit trigger or serialising constraint, to keep a stricter but slightly redundant design that preserves the dependency, or to relax the business rule if it turns out nobody actually needs it. Algorithmically, decomposition procedures that eliminate all dependency-based redundancy always achieve losslessness but may fail to preserve dependencies, while synthesis-style procedures built from a minimal cover achieve both at the cost of tolerating some residual redundancy. Recognising that this is a genuine trade-off rather than an oversight is the senior-level point. ## Practical checklist for reviewing a proposed split 1. What attributes do the fragments share? 2. Do those shared attributes form a key of at least one fragment? If not, reject the split. 3. List the original dependencies. Does each one live entirely inside one fragment? 4. For any that do not, decide explicitly how the rule will be enforced and write that decision down.