Functional Dependencies

• Can be used to identify schemas with such problems and to suggest refinements
• X → A is an assertion about a relation R
• Read as “X determines A holds in R.”
• Conventions
  • $\dots ,X,Y,Z$ represent sets of attributes
  • $A,B,C,\dots$ represent single attributes
  • Sets of attributes can be written without set formers: e.g., just $ABC$, rather than $\{A,B,C\}$
• Multiple attributes
  • No need for multiple attributes on the right
    • It can be split using armstrong’s axioms
    • Can still be used as a shorthand for multiple functional dependencies though
  • Multiple attributes on the left might be necessary
• Where do functional dependencies come from
  • Key constraints on entities and relationships
  • K → A holds for R (candidate keys) Superkeys vs. keys
  • many-one, one-one relationships
  • domain knowledge of the application
• Inferring
  • We are given a set of FD’s $F:X1\to A1,X2\to A2,\dots ,Xn\to An$ , we want to know whether an FD $Y\to B$ must hold in every relation instance that satisfies the given FD’s in $F$.
  • If so, we say $Y\to B$ is implied by $F$

Finding Closures

• A closure $F^{+}$ contains all of the functional dependencies that $F$ implies

Armstrong Axioms

• Sound and complete inference rules for FDs
• Core
  • Reflexivity: $X\subseteq Y⟹Y\to X$
  • Augmentation: $X\to Y⟹XZ\to YZ$ for any $Z$
  • Transitivity: $X\to Y\wedge Y\to Z⟹X\to Z$
• Follows
  • Union: $X\to Y\wedge X\to Z⟹X\to YZ$
  • Decomposition: $X\to YZ⟹X\to Y\wedge X\to Z$

Closure Test

• An easier way to test is to compute $Y^{+}$
  • Linear time algorithm
• Basis: $Y^{+}=Y$
• Inductions: Look for a FD $X\to A$ which has a left side $X$ that is a subset of the current $Y^{+}$ and right side $A$ is not in $Y^{+}$. If exists, add $A$ to $Y^{+}$

Inference Test

• Uses Armstrong Axioms
• To test if $Y\to B$, start by assuming two tuples agree in all attributes of $Y$
• Ute the given FDs to infer that these tuples must also agree in certain other attributes
  • If $B$ is one of these attributes, $Y\to B$ is true
  • Otherwise, find a counter example: two tuples, with forced equality of $Y$ values form a two-tuple relation that proves that $Y\to B$ does not aollow

Projecting

• Finding All Implied FD’s on a Projected Schema
• Useful for decomposition (because all of the decompositions are projections)
• Basic Idea
  1. Start with given FD’s and find all nontrivial FD’s that follow from the given FD’s.
  2. Restrict to those FD’s that involve only attributes of the projected schema.
• Simple, exponential algorithm
  1. For each set of attributes $X$, compute $X^{+}$
  2. Add $X\to A$ for all $A$ in $X^{+}-X$
  3. However, drop $XY\to A$ whenever we discover $X\to A$
     • because $X\to A$ follows from $XY\to A$ in any projection
  4. Finally only include FDs for the projected attributes
• Tricks
  • No need to compute the closure of the empty set or of the set of all attributes.
  • If we find $X^{+}=$ all attributes, so does the closure of any superset of X.