functional dependencies keys and normalization notes

Chapter Roadmap: Functional Dependencies, Keys and Normalization

Databases › Functional Dependencies, Keys and Normalization Chapter Journey Three topics that form the backbone of relational database theory. 1 Functional Dependency Inference and Armstrong's Axioms The logical rules for deriving new dependencies from a given set. You are here. 5 PYQs 2 Candidate Keys, Closures and Superkeys Using attribute closures to find all candidate keys and count superkeys. 2 PYQs 3 Normal Forms, Lossless Decomposition and Dependency Preservation 1NF through BCNF, checking whether a decomposition loses data or dependencies. 6 PYQs

What Is a Functional Dependency?

What Is a Functional Dependency? A **Functional Dependency (FD)** is a constraint between two sets of attributes in a relation. Definition X \to Y holds on a relation R if, for every valid instance of R, any two tuples that agree on all attributes of X also agree on all attributes of Y . In plain English: If you know the value of X, you can uniquely determine the value of Y . Determinant (X) The attribute(s) you already know Dependent (Y) The attribute(s) you can deduce Key point: An FD is a statement about all possible valid instances of the relation, not just the rows you currently see in a table.

Trivial vs Non-Trivial Functional Dependencies

Trivial vs Non-Trivial FDs Trivial FD X \to Y where Y \subseteq X The right side is already inside the left side. Always true. No real information. Ex: A B \to A, A B C \to B C Non-Trivial FD X \to Y where Y \neq \subseteq X Right side has at least one new attribute. Carries genuine information. Ex: A \to B Completely Non-Trivial X \cap Y = \emptyset Left and right sides share no attributes. Often called "useful" in exams.

32 more cards in this chapter

Functional Dependencies, Keys and Normalization Notes for GATE CS

Functional Dependencies, Keys and Normalization notes for GATE CS: 35 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Chapter Roadmap: Functional Dependencies, Keys and Normalization

Databases › Functional Dependencies, Keys and Normalization

Chapter Journey

Three topics that form the backbone of relational database theory.

Functional Dependency Inference and Armstrong's Axioms

The logical rules for deriving new dependencies from a given set. You are here.

5 PYQs

Candidate Keys, Closures and Superkeys

Using attribute closures to find all candidate keys and count superkeys.

2 PYQs

Normal Forms, Lossless Decomposition and Dependency Preservation

1NF through BCNF, checking whether a decomposition loses data or dependencies.

6 PYQs

What Is a Functional Dependency?

A **Functional Dependency (FD)** is a constraint between two sets of attributes in a relation.

Definition

X \to Y

holds on a relation

R

if, for every valid instance of

R

, any two tuples that agree on all attributes of

X

also agree on all attributes of

Y

In plain English: If you know the value of

X

, you can uniquely determine the value of

Y

Determinant (

X

)

The attribute(s) you already know

Dependent (

Y

)

The attribute(s) you can deduce

Key point: An FD is a statement about all possible valid instances of the relation, not just the rows you currently see in a table.

Trivial vs Non-Trivial Functional Dependencies

Trivial vs Non-Trivial FDs

Trivial FD

X \to Y

where

Y \subseteq X

The right side is already inside the left side. Always true. No real information.

Ex: AB→A, ABC→BC

Non-Trivial FD

X \to Y

where

Y \neq \subseteq X

Right side has at least one new attribute. Carries genuine information.

Ex: A→B

Completely Non-Trivial

X \cap Y = \emptyset

Left and right sides share no attributes. Often called "useful" in exams.

Armstrong's Axioms: The Three Core Rules

Armstrong's Axioms

Three inference rules for deriving new FDs from a given set $F$ . They are sound (never derive false FDs) and complete (can derive all true FDs).

1. Reflexivity

Y \subseteq X

, then

X \to Y

2. Augmentation

X \to Y

, then

X Z \to Y Z

for any

Z

3. Transitivity

X \to Y

and

Y \to Z

, then

X \to Z

Why these matter: Together, soundness and completeness mean these three rules are all you need to reason about functional dependencies. Every other rule is a shortcut derived from these three.