Lossless Join Decomposition & Dependency Preservation

Lossless Join Decomposition

💡 In plain English: if you split a table in two, you should be able to join the pieces back together and get exactly the original table back — not extra, made-up rows, and not missing ones.

For \(R\) decomposed into \(R_1, R_2\), this must hold for every legal instance:

\[r = \pi_{R_1}(r) \bowtie \pi_{R_2}(r)\]

Sufficient condition: the decomposition is lossless if at least one of these is true:

\[R_1 \cap R_2 \rightarrow R_1 \quad \text{or} \quad R_1 \cap R_2 \rightarrow R_2\]

In other words: the attribute(s) shared between the two pieces must be enough, on their own, to act as a key for at least one of the two pieces.

⚠️ This condition is sufficient whenever all our constraints are FDs. If other kinds of constraints are in play, it isn’t guaranteed to be necessary.

Full checklist for a lossless decomposition:

• \(R_1 \cup R_2 = R\) — nothing gets left out
• \(R_1 \cap R_2 \neq \phi\) — the two pieces actually share something in common
• \(R_1 \cap R_2 \rightarrow R_1\) or \(R_1 \cap R_2 \rightarrow R_2\) — that shared part is a key on at least one side

Worked Example: Supplier-Parts

Supplier_Parts(S#, Sname, City, P#, Qty), with S# → Sname, City and (S#, P#) → Qty.

Here’s a sample instance:

S#	Sname	City	P#	Qty
S1	Smith	London	P1	300
S1	Smith	London	P2	200
S2	Jones	Paris	P1	400
S2	Jones	Paris	P2	300

A bad split: Supplier(S#, Sname, City, Qty) and Parts(P#, Qty)

The shared attribute here is Qty — and Qty isn’t a key of either piece. Projecting our sample data onto these two tables and joining them back on Qty gives:

S#	Sname	City	P#	Qty
S1	Smith	London	P1	300	✅ original
S1	Smith	London	P2	300	❌ spurious
S2	Jones	Paris	P1	300	❌ spurious
S2	Jones	Paris	P2	300	✅ original
S1	Smith	London	P2	200	✅ original
S2	Jones	Paris	P1	400	✅ original

Both suppliers happened to have a Qty = 300 row, so the join matches every Qty = 300 row in Supplier with every Qty = 300 row in Parts — creating two fabricated combinations that never existed in the original data. This decomposition is lossy, and it also fails to preserve (S#, P#) → Qty.

A good split: Supplier(S#, Sname, City) and Parts(S#, P#, Qty)

The shared attribute is S#, which is a key of Supplier. Joining these two projections back together on S# reconstructs exactly the original four rows — no more, no less. Lossless, and every dependency is preserved too.

📌 The lesson: it’s not whether you split a table, it’s where you split it. The same table can be decomposed well or badly.

TipTry it yourself: Test Lossless Join & Dependency Preservation

Click Run below to verify that decomposing R(S, Sname, City, P, Qty) into R1(S, Sname, City) and R2(S, P, Qty) is lossless and dependency preserving:

R(S, Sname, City, P, Qty)

S -> Sname, City
SP -> Qty

Decompose: R1(S, Sname, City), R2(S, P, Qty)

(You can click Edit to try the bad split R1(S, Sname, City, Qty), R2(P, Qty) and see the lossy diagnosis!)

Worked Example: Decomposing into Three Relations

A relation \(R(A, B, C, D)\) with functional dependencies: \[FD = \{ A \rightarrow B,\ B \rightarrow C,\ C \rightarrow D\}\]

is decomposed into three relations as follows: \[R_1(A, B),\ R_2(B, C),\ R_3(C, D)\]

We test for a lossless decomposition progressively in this exact order:

• Step 1: Attribute Union Check: \[R_1 \cup R_2 \cup R_3 = \{A, B, C, D\} = R\] All original attributes are accounted for (nothing is lost).

• Step 2: First Natural Join (\(R_1 \bowtie R_2\)):

  • Shared attributes: \(R_1 \cap R_2 = \{ B \}\)
  • Compute closure of shared attributes under \(FD\): \[B^+ = BCD\]
  • Since \(BCD \supseteq \{ B, C \} = R_2\), \(B\) is a superkey of \(R_2\).
  • Therefore, \(R_1 \bowtie R_2\) is lossless, producing intermediate relation: \[R_{12}(A, B, C)\]

• Step 3: Second Natural Join (\(R_{12} \bowtie R_3\)):

  • Shared attributes: \(R_{12} \cap R_3 = \{ C \}\)
  • Compute closure of shared attributes under \(FD\): \[C^+ = CD\]
  • Since \(CD \supseteq \{ C, D \} = R_3\), \(C\) is a superkey of \(R_3\).
  • Therefore, \(R_{12} \bowtie R_3\) is lossless, producing: \[R_{123}(A, B, C, D) = R\]

\(\therefore\) The 3-way decomposition is Lossless.

TipTry it yourself: Verify 3-Way Lossless Join

Click Run below to trace each progressive natural join step live:

R(A, B, C, D)

A -> B
B -> C
C -> D

Decompose: R1(A, B), R2(B, C), R3(C, D)

💡 Join Order Matters: We are not restricted to joining strictly \(R_1\) and \(R_2\) first. If \(R_1 \bowtie R_2\) fails the superkey condition, the algorithm searches for any pair of relations that can be joined losslessly. If a failed join occurs, no intermediate relation is created because merging them would generate spurious tuples.

TipTry it yourself: Non-Sequential Pairwise Join Example

In this example, \(R_1 \bowtie R_2\) cannot be joined first because their shared attribute \(A\) is not a superkey (\(A^+ = \{A\}\)). However, \(R_2\) and \(R_3\) share \(\{A, D\}\), where \((AD)^+ = \{A, D, E, F\} \supseteq R_2\). Thus \(R_2 \bowtie R_3\) joins losslessly into \(R_{23}\), which then joins losslessly with \(R_1\):

R(A, B, C, D, E, F)

AB -> C
E -> F
AC -> B
BC -> A
B -> D
AD -> E

Decompose: R1(A, B, C), R2(A, D, F), R3(A, C, D, E)

---

Dependency Preservation

• When a relation is decomposed, it is important to ensure that functional dependencies that held in original relation are still maintained.
• It helps to prevent anomalies and ensures data integrity.
• If \(F_i\) represents the dependencies preserved locally in each subrelation \(R_i\), we define \(F' = \bigcup F_i\). The decomposition preserves dependencies iff all dependencies in \(F\) can be derived from \(F'\): \[(F_1 \cup F_2 \cup \cdots \cup F_k)^+ = F^+\]

Note

📌 Lossless Decomposition and Dependency Preservation are independent of each other. - A decomposition can be lossless but lose dependencies. - A decomposition can preserve dependencies but be lossy. - Good normalization algorithms (like 3NF synthesis) guarantee both properties at the same time.

---

Worked Example: Dependency Preservation Step-by-Step

A relation \(R(A, B, C, D)\) with functional dependencies: \[FD = \{ A \rightarrow B,\ B \rightarrow C,\ C \rightarrow D,\ D \rightarrow A\}\]

is decomposed into three relations as follows: \[R_1(A, B),\ R_2(B, C),\ R_3(C, D)\]

Step 1: Find Local Functional Dependencies (\(F_i\) for each \(R_i\))

• \(F_1 = \{ A \rightarrow B,\ B \rightarrow A \}\) based on \(R_1(A, B)\)
• \(F_2 = \{ B \rightarrow C,\ C \rightarrow B \}\) based on \(R_2(B, C)\)
• \(F_3 = \{ C \rightarrow D,\ D \rightarrow C \}\) based on \(R_3(C, D)\)

Step 2: Combine Local Dependencies (\(F' = F_1 \cup F_2 \cup F_3\))

\[F' = \{ A \rightarrow B,\ B \rightarrow A,\ B \rightarrow C,\ C \rightarrow B,\ C \rightarrow D,\ D \rightarrow C \}\]

Step 3: Check Each Original Dependency Against \(F'\)

• \(A \rightarrow B\) is directly in \(F_1\) (preserved)
• \(B \rightarrow C\) is directly in \(F_2\) (preserved)
• \(C \rightarrow D\) is directly in \(F_3\) (preserved)

Now, \(D \rightarrow A\) is missing from \(F'\).

Let’s take \(D^+\) closure on \(F'\): 1. Start with \(D^+ = \{ D \}\) 2. Using \(D \rightarrow C \in F_3 \implies \{ D, C \}\) 3. Using \(C \rightarrow B \in F_2 \implies \{ D, C, B \}\) 4. Using \(B \rightarrow A \in F_1 \implies \{ D, C, B, A \} = DCBA\)

Since \(A \in D^+\), the dependency \(D \rightarrow A\) is preserved after decomposing it!

\(\therefore\) All functional dependencies are preserved, so this decomposition is Dependency Preserving.

TipTry it yourself: Verify the Dependency Preservation Algorithm

Click Run to compute the dependency preservation audit and progressive lossless join steps live:

R(A, B, C, D)

A -> B
B -> C
C -> D
D -> A

Decompose: R1(A, B), R2(B, C), R3(C, D)