550_4.7_Testing_for_a_Lossless_Join_default

Decomposition and Lossless Join

  • A decomposition into two relations is lossless if it maintains the connections between attributes within tuples.

  • A formal definition states that a decomposition r to r k is lossless if projecting r over the decomposed relations (r I) and then joining them reconstructs the original instance r.

  • Proving a decomposition is not lossless involves finding an instance where joining the projections introduces additional tuples (not reconstructing original instance).

Proving Lossless Join

  • Proving a decomposition is lossless requires examining all instances that satisfy the functional dependency set.

  • Example from earlier lesson showed non-lossless decomposition of pizza shop schema into pizza topping kind and topping kind.

Simpler Method for Lossless Join

  • There is a simpler test for binary decompositions based on functional dependencies:

    • Identify the intersection of two relations R1 and R2.

    • Look at attributes unique to each relation: R1 - R2 and R2 - R1.

  • If either of the following holds:

    • R1 ∩ R2 functionally determines R1 - R2

    • R1 ∩ R2 functionally determines R2 - R1

    • Then the decomposition is lossless.

Pizza Shop Example — Functional Dependencies Test

  • For the pizza shop schema, let's apply the test to the initial decomposition:

    • R1 = Pizza Topping Kind

    • R2 = Topping Topping Kind

    • Intersection (R1 ∩ R2): Topping Kind

    • Distinct attributes: R1 - R2: Pizza; R2 - R1: Topping

    • Conclusion: Topping Kind does not functionally determine Pizza (closure of Topping Kind yields only Topping).

    • Therefore, this decomposition is not lossless.

Another Example of Decomposition

  • Consider a second decomposition:

    • R1 = Pizza, Topping

    • R2 = Topping, Topping Kind

    • Intersection remains Topping.

    • Differences: R1 - R2 = Pizza; R2 - R1 = Topping

    • Conclusion: Topping does not functionally determine Pizza (closure of Topping includes Topping and Topping Kind, but not Pizza).

Conclusion of the Lesson

  • A simple test for lossless join decomposition exists for binary decompositions based on functional dependencies.

  • For n-ary decompositions, a more complex method known as the tableau technique exists (not covered in detail here).