Lossless Decomposition and Dependency Preservation

Concept

Splitting a relation is only correct if two properties hold. Every normalisation question that asks you to "verify the decomposition" is asking for these two tests.

What a lossy decomposition looks like

  ORIGINAL

  emp | dept | project
  ----+------+--------
  E1  | CS   | P1
  E2  | CS   | P2

  BAD SPLIT - on dept, which is not a key of either piece

  R1 ( emp, dept )        R2 ( dept, project )
     E1  CS                  CS  P1
     E2  CS                  CS  P2

  JOIN THEM BACK on dept

  emp | dept | project
  ----+------+--------
  E1  | CS   | P1        original
  E1  | CS   | P2        SPURIOUS - E1 never worked on P2
  E2  | CS   | P1        SPURIOUS
  E2  | CS   | P2        original

  Two rows became four. The two extra rows are FALSE.
  Information was not lost - it was CORRUPTED by addition,
  which is worse, because nothing marks the false rows.

The lossless join test for two relations

  A decomposition of R into R1 and R2 is LOSSLESS if and
  only if the common attributes form a SUPER KEY of at
  least one of them:

      ( R1 intersect R2 ) -> R1     OR
      ( R1 intersect R2 ) -> R2

  In words: the shared column must uniquely identify rows
  in at least one of the two pieces.

  APPLYING IT to the bad split

    R1 intersect R2 = { dept }
    dept+ = { dept }        determines neither R1 nor R2
    -> LOSSY. Confirmed by the spurious rows above.

  A GOOD SPLIT of the same relation

    R1 ( emp, dept )        R2 ( emp, project )
    common = { emp }
    emp -> dept, so emp is a key of R1
    -> LOSSLESS

  Joining on emp gives back exactly two rows.

Why BCNF decomposition is always lossless

  The BCNF algorithm splits R on  X -> Y  into

      R1 = X union Y
      R2 = X union ( R minus Y )

  common attributes = X
  and X -> Y means X is a key of R1.

  The condition is satisfied by construction, which is why
  the algorithm never needs a separate losslessness check.

Dependency preservation

  A decomposition preserves dependencies if the union of
  the dependencies enforceable on each piece is EQUIVALENT
  to the original set F.

  TEST
    1  for each relation Ri, find which dependencies of F
       have both sides entirely inside Ri
    2  collect them into G
    3  test whether G is equivalent to F, using the closure
       method from Phase 7

  WORKED TEST

  R ( A, B, C ),  F = { A -> B, B -> C }
  decomposed into R1 ( A, B ) and R2 ( B, C )

  LOSSLESS?
    common = { B }
    B+ = { B, C } which is R2
    -> B is a key of R2  -> LOSSLESS

  DEPENDENCY PRESERVING?
    R1 ( A, B ) can enforce  A -> B     both sides inside
    R2 ( B, C ) can enforce  B -> C     both sides inside
    G = { A -> B, B -> C } = F
    -> PRESERVED

  Both properties hold. This is a good decomposition.

  A DECOMPOSITION THAT LOSES A DEPENDENCY

  ADDRESS ( city, street, pincode )
  F = { { city, street } -> pincode, pincode -> city }

  BCNF decomposition:
    R1 ( pincode, city )      R2 ( pincode, street )

  LOSSLESS?
    common = { pincode }, and pincode -> city means
    pincode is a key of R1                 -> LOSSLESS

  DEPENDENCY PRESERVING?
    R1 can enforce  pincode -> city              yes
    R2 can enforce  nothing
    { city, street } -> pincode needs city, street AND
    pincode together - no single relation holds all three
    -> NOT PRESERVED

  To enforce that rule you must join R1 and R2 on every
  insert. That is the real, practical cost of BCNF here.

The matrix method for three or more relations

For a decomposition into more than two relations, the two relation shortcut does not apply. The standard technique is a tableau.

  1  draw a grid: one row per relation, one column per
     attribute of R
  2  cell = "a" if that attribute is in that relation,
             "b" otherwise
  3  for each dependency X -> Y:
       find rows agreeing (all "a") on every attribute of X
       for those rows, make the Y columns agree - if any
       is "a", set all of them to "a"
  4  repeat until no change
  5  LOSSLESS if some row becomes all "a"

  EXAMPLE
  R ( A, B, C, D ),  F = { A -> B, B C -> D }
  decomposed into R1 ( A, B ), R2 ( B, C ), R3 ( C, D )

  initial          A    B    C    D
  R1 ( A B )       a    a    b    b
  R2 ( B C )       b    a    a    b
  R3 ( C D )       b    b    a    a

  apply A -> B  : only R1 has "a" under A. No two rows
                  agree on A, so nothing changes.
  apply B C -> D: rows agreeing on B and C? R1 has a,b
                  and R2 has a,a - they do not both have
                  "a" for C. No change.

  No row is all "a"  -> LOSSY.

  Check: joining R1, R2 and R3 does produce spurious rows,
  because nothing links A to D reliably.

Summary of guarantees

This table is the reason 3NF is often the practical target: it is the strongest form that can always promise both properties at once.

Common mistakes

• Testing only losslessness. Both properties are required for a full answer.
• Using the two relation rule on three relations. Use the tableau method instead.
• Thinking lossy means rows disappear. Rows are added, and the added rows are false.
• Claiming a dependency is preserved when only part of it fits. Both sides must be inside one relation.
• Forgetting that dependency loss is acceptable if deliberate. Document it and enforce the rule elsewhere.

Exam and interview questions

1. Define lossless join decomposition and state the two relation test.
2. Show a lossy decomposition and the spurious tuples it produces.
3. Why is BCNF decomposition always lossless?
4. Define dependency preservation and give the test.
5. Which normal form guarantees both properties, and which does not?
6. Describe the tableau method for three or more relations.

Practice

1. R ( A, B, C ), F = { A -> B, B -> C }, split into ( A, C ) and ( B, C ). Test both properties.
2. Show the spurious tuples produced by that split with three sample rows.
3. Apply the tableau method to R ( A, B, C, D ) with F = { A -> B, B -> C, C -> D } decomposed into ( A, B ), ( B, C ), ( C, D ).
4. Give a decomposition that is dependency preserving but lossy, and explain why that is the worse failure.

Conclusion

Lossless means the join reproduces the original with no false rows; dependency preserving means every rule remains checkable on a single relation. Test both, remember that 3NF guarantees both while BCNF guarantees only the first, and document any dependency you deliberately give up.