Video summary

Week 5 Live Session

Main summary

Key takeaways

Educational

Main ideas, concepts, and lessons (Week 5 focus)

1) Designing an “optimal” relational schema (continuation from Week 4)

Week 4 covered designing ER diagrams/schemas for relationship cardinalities (one-to-one, one-to-many, many-to-many) and total vs partial participation. Week 5 continues by teaching how to:

  • Recognize redundancy in a schema
  • Understand anomalies that result from redundancy
  • Use formal tools (functional dependencies → normalization-related concepts later in Week 6) to validate whether a design is optimal

Scope note: Only RDBMS (relational databases) are discussed. (No SQL / NoSQL is not covered.)

2) Redundancy and data “anomalies” (insertion, deletion, update)

Redundancy means multiple copies of the same data (duplicate storage) across rows and/or tables.

Redundancy can cause anomalies, i.e., inconsistencies during:

  • Insertions
  • Deletions
  • Updates

Types of anomalies

  • Insertion anomaly

    • Example idea: If a table stores student information together with project information and project fields must be non-null, then you cannot insert a student who has no project.

  • Deletion anomaly

    • Example idea: If deleting a student also forces deleting rows containing project evaluation/marks, you lose project-related information unintentionally.

  • Update anomaly

    • Example idea: If you update a value (e.g., marks) but the same data appears in multiple places, you may update only some copies (or redundantly update all), causing inconsistencies.

Teaching point: Schema decompositions/normalizations should avoid redundancy and these anomalies.

3) Dependency and decomposition groundwork

Functional Dependency (FD) is introduced as the core tool for reasoning about schema quality.

Week 5 covers:

  • Functional dependency
  • Armstrong axioms (rules)
  • Closure
  • Candidate keys / superkeys / prime attributes
  • Extraneous attributes
  • Canonical cover
  • Equivalence of FD sets
  • Lossless join decomposition
  • Dependency preservation (separate from lossless join)

Normalization details are stated as coming in Week 6.

Methodologies / detailed instruction-like procedures

A) How to check whether an FD is true or false (key rule)

Given an FD: α → β

  • Interpret α and β as sets of attributes/columns (not necessarily single columns).
  • To verify α → β using table instances:
  1. Consider the values of α (left side) across all rows.
  2. Uniqueness condition:
    • If α values are unique, then β values are determined → FD holds.
  3. Duplicate α values condition:
    • If α has duplicate-value rows, then for every repeated α value:
      • the β values must be the same across those duplicate rows,
      • otherwise α → β is false.
  4. If multiple attributes exist on either side, treat the left-side attribute set as one combined “key-like” unit for comparison.

B) Trivial functional dependencies

An FD α → β is trivial if:

  • β is a subset of α (β ⊆ α)

Also discussed: an attribute determining itself is always trivially true.

C) Armstrong Axioms (properties/rules to remember)

These rules infer additional FDs from a given set:

  • Reflexivity: if β ⊆ α, then α → β
  • Augmentation: if α → β, then αγ → βγ
  • Transitivity: if α → β and β → γ, then α → γ
  • Union / Decomposition:
    • Union: combine conclusions
    • Decomposition: split a multi-attribute RHS into individual parts
  • Pseudo-transitivity:
    • Combines augmentation + transitivity behavior

D) Closure computation (how to compute X⁺)

Goal: compute X⁺ = all attributes functionally determined by X using a given FD set.

Procedure (conceptual iterative method):

  1. Start with X⁺ = X
  2. Repeatedly apply any FD α → β such that α ⊆ X⁺
  3. Add β to X⁺ when applicable
  4. Continue until no new attributes can be added
  5. The final X⁺ is the closure

Important notes:

  • You can compute closure step-by-step or in a combined manner if dependencies are known.
  • Trivial FDs can imply that attributes already on the same side belong to the closure.

E) How to determine candidate keys / superkeys from closures

Given a relation R and its FD set:

  • Superkey

    • Any attribute set X such that X⁺ includes all attributes of R (i.e., X⁺ = R)
    • May be non-minimal.

  • Candidate key

    • A superkey that is minimal
    • i.e., no proper subset of it is also a superkey

  • Primary key

    • One chosen candidate key (from possibly multiple)
    • typically by convention/practical choice

  • Prime attributes

    • Attributes that appear in at least one candidate key

F) Maximum number of superkeys (formula mentioned)

A general formula discussed:

  • Maximum number of superkeys = 2^(n − 1)
  • where n is the number of attributes in relation R

The session also mentioned scenario-based computation involving overlap between candidate keys and subtracting intersection attributes (using inclusion–exclusion style reasoning) to avoid double counting.

G) Extraneous attributes (simplifying FDs) — detailed checks

Definition (concept): An attribute in an FD is extraneous if removing it does not change the closure (i.e., does not change inferable results).

Extraneous attributes can appear on:

  • Left side (α), or
  • Right side (β)

Check extraneous attribute on the LEFT side

To test whether attribute A in α is extraneous:

  1. Remove A from the left side in the FD.
  2. Compute the closure of the remaining left-side attributes using the modified FD set.
  3. If you still derive the same necessary behavior (same determinable RHS behavior as before), then A is extraneous.
  4. Otherwise, A is not extraneous.

Check extraneous attribute on the RIGHT side

To test whether C (or D) in β is extraneous:

  1. Remove that attribute from RHS in the FD.
  2. Compute closure using the modified FD set.
  3. If the closure still derives the removed attribute, then it is extraneous.
  4. Otherwise, it is not extraneous.

Constraint mentioned: Not all RHS attributes can be extraneous simultaneously; at least one RHS attribute must remain minimally necessary.

H) Canonical cover (canonical basis) method

Goal: obtain a minimal equivalent FD set.

Procedure:

  1. Decomposition (singletons on RHS):
    • Convert every FD so RHS contains single attributes (via decomposition).
  2. Remove redundant FDs:
    • If an FD can be inferred from others (via closure/Armstrong rules), drop it.
  3. Remove extraneous attributes:
    • In remaining FDs, remove extraneous attributes on left/right using closure tests.
  4. Result:
    • A reduced FD set equivalent to the original but more minimal.

I) Equivalence of functional dependency sets

Given FD sets F1 and F2:

  • F1 covers F2 if:
    • For every FD in F2, its RHS is derivable from its LHS using the closure computed from F1.
  • F1 and F2 are equivalent if:
    • F1 covers F2 and F2 covers F1

Key verification approach (conceptual):

  • For each LHS from F2, compute its closure under F1 and check whether it satisfies the corresponding FDs in F2.

J) Lossless join decomposition (checking if no information is lost)

Given a decomposition of relation R into R1 and R2, lossless join means:

Natural join reconstruction yields the original relation: R1 ⨝ R2 = R

For two-way decomposition, conditions referenced:

  1. Intersection must not be empty (common attribute exists):
    • Informally: R1 ∩ R2 ≠ null
  2. Attribute coverage:
    • attributes(R1) ∪ attributes(R2) = attributes(R)
  3. FD-related condition:
    • closure of the intersection should determine at least one needed side appropriately.

For three-way decomposition, the instructor emphasized checking order:

  • Check losslessness between the first two relations first
  • Only then include the next relation
  • If the first check fails, later checks are unnecessary

K) Dependency preservation (separate from lossless join)

Goal: Ensure that when decomposing R into R1, R2, …, the original functional dependencies F can still be enforced/recovered.

Definition idea used:

  • A decomposition is dependency-preserving if:
    • Every dependency in F is implied by dependencies from F1, F2, … (the FD sets of the decomposed relations).

Instructor check (example-based method):

  1. Compute the combined closure from decomposed schemas:
    • F+ = (F1 ∪ F2 ∪ F3)+
  2. For each original dependency in F (e.g., A → B, B → C, …):
    • check whether it is contained in or derivable from F+
  3. If all dependencies are derivable, dependency preservation holds.
  4. If any dependency cannot be derived, it fails.

Key note: Lossless join decomposition does not automatically imply dependency preservation. They are independent properties.

Speakers / sources featured

  • Instructor / speaker (main): Praveen
    • Mentioned as “Yes, sir / Hello” and introduces himself: “I’m Praveen.”
  • Students/participants (spoken/mentioned):
    • Neha (apology/mistake and lowered hand)
    • Manjeet (requesting slides for other weeks)
    • Other unnamed participants (e.g., “sir” responses)

Original video