Lossless Join Decomposition

decomposition of a relation R into relations R1, R2 such that if we perform a natural join of two smaller relations it will return the original relation

$$ R_1 ∪ R_2 = R, R1 ∩ R2 \neq \phi $$

$$ \forall r \in R, r_1 = \Pi_{R_1}(r), r_2 = \Pi_{R_2}(r) $$

$$ r_1 \bowtie r_2 = r $$

<aside> 💡 Decompostion is lossy if $r_1 \bowtie r_2 \supset r$

</aside>

Checking for lossless join decomposition

• Union of Attributes of $R_1$ and $R_2$ must be equal to attribute of $R$

  $$ R_1 \cup R_2 = R $$

• Intersection of Attributes of $R1$ and $R_2$ must not be NULL

  $$ R_1 \cap R_2 \neq \phi $$

• Common attribute must be a key for at least one relation ($R_1$ or $R_2$)

  $$ R_1 \cap R_2 \rightarrow R_1 \textrm{ or } R_1 \cap R_2 \rightarrow R_2 $$

Atomicity of a domain

• A domain is atomic if its elements are considered to be indivisible units.
• Examples of non-atomic domains:
  • Set of names, composite attributes
  • Identification numbers like CS101 can be broken up into parts
• Atomicity is actually a property of how the elements of the domain are used

Functional Dependency

Let R be a relation schema

$$ \alpha \subseteq R \textrm{ and } \beta \subseteq R $$

The functional dependency or FD

$$ α → β $$