Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Functional dependencies

Clear, exam-focused notes on functional dependencies: definitions, Armstrong's axioms and derived rules, attribute closure, minimal cover, algorithms and worked examples for finding closures, keys and minimal covers.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Functional dependencies (FDs) capture all important constraints about how one set of attributes determines another inside a relation. An engineer uses FDs when designing schemas (to find keys and to normalise), when checking if a decomposition preserves dependencies or is lossless, and when reasoning about query optimization and integrity constraints.

Key ideas

  • Trivial FD: An FD X → Y is trivial if Y ⊆ X.
  • Nontrivial FD: X → Y is nontrivial if Y ⊄ X.
  • Equivalence / implication: Given a set F of FDs, we write F ⊨ X → Y (or simply F ⊢ X → Y) when X → Y follows from F — i.e., every relation instance satisfying all FDs in F also satisfies X → Y. By soundness and completeness of Armstrong’s axioms, F ⊢ X → Y if and only if F ⊨ X → Y.
  • Closure of attribute set: For attribute set X and FD set F, X+ (read: X-plus) is the set of all attributes functionally determined by X using F. Computing X+ is the principal decidable test for implication.
  • Key and candidate key: A set of attributes K is a superkey if K+ contains all attributes of R. K is a candidate key if it is a minimal superkey (no proper subset is a superkey).
  • Minimal cover (canonical cover): A set G of FDs is a minimal cover of F if (1) every FD in G has a single attribute on the right-hand side, (2) no attribute can be removed from the left side of any FD in G without changing the closure, and (3) no FD can be removed from G without changing the closure. Minimal covers are not unique but are equivalent (imply the same FDs). An attribute A in the left side X of X → Y is extraneous if F ⊨ (X − {A}) → Y; an attribute B in the right side Y is extraneous if F ⊨ X → (Y − {B}).

Exact laws (Armstrong's axioms). State assumptions: F is a fixed set of FDs over schema R.

  • Reflexivity: If Y ⊆ X then X → Y holds. (Proof: trivial by definition)
  • Augmentation: If X → Y then XZ → YZ for any Z (where concatenation denotes set union). Proof: if tuples agree on X they agree on Y; if they also agree on Z, combined they agree on YZ.
  • Transitivity: If X → Y and Y → Z then X → Z.

Derived rules and short proofs (universities often ask to derive these):

  • Union rule: From X → Y and X → Z infer X → YZ. Proof: Semantic argument: if two tuples agree on X, then by X → Y they agree on Y and by X → Z they agree on Z; hence they agree on YZ, so X → YZ. (Equivalently derivable from Armstrong’s axioms.)
  • Decomposition rule: From X → YZ infer X → Y and X → Z. Proof: By reflexivity, YZ → Y and YZ → Z; by transitivity with X → YZ, we get X → Y and X → Z.
  • Pseudo-transitivity: From X → Y and YZ → W infer XZ → W. Proof: augment the first to XZ → YZ, then use transitivity with YZ → W.

Computing closures and implication: standard algorithm (formal):

  1. Start with S := X (X+ initially X).
  2. Repeatedly find any FD A → B in F with A ⊆ S and set S := S ∪ B.
  3. Stop when no more attributes can be added. Result S = X+.

Minimal cover algorithm (formal steps):

  1. Ensure right sides are single-attribute: replace X → YZ by X → Y and X → Z for each FD.
  2. For each FD X → A, for each attribute B in X test if (X − {B})+ (under the current FD set) still contains A; if yes, remove B from the left side.
  3. Remove redundant FDs: for each FD f in set, test if it is implied by the other FDs; if yes remove it.
  4. The result is a minimal cover (possibly not unique).

How to find candidate keys using FDs:

  1. Find attributes that never appear on any RHS of F (call this set R0). These must be in every key (otherwise their value would be determined by others and they could not appear arbitrarily).
  2. Start with K := R0. Compute K+. If K+ = R, then, since every candidate key must include R0, R0 is the only possible candidate key; verify minimality by checking whether any attribute in R0 can be removed while K+ still equals R. If not, add attributes from R − K one by one (choose minimal additions) until the closure covers R. Then check minimality by removing attributes if possible.

What to draw (for exam diagrams):

  • When asked to show closure computation, draw a vertical list of steps: initial S = X, then each line show the FD used and new S after adding RHS. Label each line with the FD. This resembles a small table with columns: step number | current S | FD used | new S.

Formulas

X → Y — X determines Y; X and Y are sets of attributes; unit: none; applies to attributes in a relation schema. F ⊨ X → Y — FD X → Y is implied by FD set F; unit: none; use when testing implication. X+ — closure of X under F (set of all attributes determined by X using F); unit: none; used to compute keys and implication. |R| — number of attributes in schema R (cardinality); unit: count; used when describing full closure (X+ = R means superkey).

Worked examples

Example 1 — compute closure and find candidate keys Question: Let R(A,B,C,D) and F = {A → BC, C → D, D → A}. Find A+ and all candidate keys. Model answer (step-by-step):

  1. Compute A+: start S = {A}.
  2. Use A → BC: S := {A, B, C}.
  3. Use C → D (C ∈ S): S := {A, B, C, D}.
  4. Now S contains all attributes, so A+ = {A,B,C,D}. Thus A is a superkey. Check minimality: proper subset = {} cannot determine A; singletons B+ = {B} (no FD), C+ = {A,B,C,D}. Compute C+: start {C}, C → D gives {C,D}, D → A gives {C,D,A}, then A → BC gives {A,B,C,D}. So C is also a candidate key. D+: {D}, D → A gives {D,A}, A → BC gives all. So D is also a candidate key. B is not. Candidate keys: {A}, {C}, {D}. (Explain minimality: each is singleton so minimal.) Final answer: A+, C+, D+ = {A,B,C,D}; candidate keys = {A}, {C}, {D}.

Example 2 — minimal cover Question: For R(A,B,C) and F = {A → BC, B → C, A → B}, compute a minimal cover. Model answer:

  1. Ensure single-attribute RHS: A → BC becomes A → B and A → C. Now F' = {A→B, A→C, B→C, A→B (duplicate)}.
  2. Remove duplicates: F' = {A→B, A→C, B→C}.
  3. Remove extraneous LHS attributes: All LHS are single attributes so none to remove.
  4. Remove redundant FDs: Check A→C: compute A+ using {A→B, B→C} gives A→B adds B, then B→C adds C, so A→C is implied by the other two; remove A→C.
  5. Check B→C: compute B+ using {A→B} only gives B, so B→C not implied; keep. Check A→B: compute A+ using {B→C} only gives A, so A→B not implied; keep. Result minimal cover: {A → B, B → C}.

Example 3 — test implication using closure Question: Given F = {A→B, B→C} does F imply A → C? Use closure. Model answer: Compute A+: {A} → using A→B gives {A,B} → using B→C gives {A,B,C}. So A+ contains C, therefore F ⊨ A → C. Answer: Yes, implied by transitivity.

Common mistakes

  • Not checking minimality of a candidate key (giving a superkey as key without proving minimality).
  • Confusing implication (logical consequence) with membership in the given set F. Always use closure test.
  • When computing closures, stopping too early — must repeat until no change.

For your exam

Typical question types: definitions (define FD, closure, candidate key), short notes (Armstrong axioms, minimal cover algorithm), derivations (derive union/decomposition from axioms), procedural problems (compute X+, find candidate keys, compute minimal cover), and small proofs (show FD is implied or not). What full-marks answers include:

  • Precise definitions using correct notation and examples.
  • For algorithmic problems: clear, numbered steps showing intermediate S (closures), FDs used each step, and final result. If asked, show the table/box of closure steps.
  • For minimal cover: show each transformation step (RHS split, extraneous attribute checks with explicit closure computations, redundant FD checks).
  • For derivations: write each application of an axiom (name it) and show the intermediate FDs.

Quick check

  1. State Armstrong's three axioms by name.
  2. Given R(A,B,C) and F = {A→B, B→C}, what is A+? Is A a key?
  3. What are the three stages of the minimal cover algorithm? Answers: 1) Reflexivity, Augmentation, Transitivity. 2) A+ = {A,B,C}; yes A is a superkey (and here a candidate key if no proper subset is a key). 3) Split RHS to single attributes; remove extraneous LHS attributes; remove redundant FDs.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?