DBMS
GATE फर्रे
Module 1. Database design
Limitations of File System (Short Notes)
No Data Abstraction: Users must manage physical
data access manually (no data independence).
Not Scalable: Suitable only for small datasets;
inefficient for large databases.
No Concurrency Control: Cannot handle multiple
users or concurrent transactions safely.
Single-User Access: Lacks multi-user support; no in- 1. Trivial FD : Always valid, X → Y is trivial iff X ⊇ Y.
built locking or transaction management. Ex AB → A
Data Redundancy & Inconsistency: No central 2. Non Trivial FD: X → Y is non trivial FD if X ⋂ Y = Φ
control over data integrity or duplication. and X → Y must satisfy FD definition. Ex A → B
Relational Model Terminology Armstrong's Axioms / Inference Rules
Tuple : A tuple is a single row in a relation (table), Armstrong’s Axioms (or inference rules) provide a
representing a single record in that table. sound and complete set of rules for reasoning about
functional dependencies (FDs) in relational database
Attribute : An attribute refers to a column in a relation. design.
It defines the properties or characteristics of the
relation. Let X, Y, Z, W be sets of attributes. The following three
fundamental axioms form the basis of all functional
Domain : The domain of an attribute is the set of all dependency inference:
possible values that an attribute can take. It defines the
data type and constraints of the attribute. Rule Name Rule
Degree : The degree of a relation is the total number of Reflexivity If X⊇YX, then X→Y
attributes (columns) it contains. Augmentation If X→Y, then XZ→YZ
Cardinality : The cardinality of a relation is the total Transitivity If X→Y and Y→Z, then X→Z
number of tuples (rows) present in it. Decomposition If X→YZ, then X→Y and X→Z
Relational Instance : A relation instance is a specific set Union If X→Y, and X→Z, then X→YZ
of tuples that exist in a relation at a particular moment. Pseudotransitive If X→ Y, and WY → Z, then WX → Z
It is a finite set that changes over time.
Attribute closure [X]+ Let x be the attribute set of
Relation Schema: A relation schema describes the
relation R set of all possible attributes which are
structure of a relation, including its relation and the
logically or functionally determined by X is called
names and data types of its attributes.
attribute closure of X [X]+
Functional dependencies & Normalization
X —-> Y or X determines Y
Page No:- 01
DBMS
GATE फर्रे
Key Concept A functional dependency X→Y is said to be a member
of F+ (i.e., logically implied by F) iff
Primary key: Randomly chosen candidate key is the X→Y ∈ F+ ⟺ Y ⊆ X+
primary key which is Unique and Not Null. Where X+ is the attribute closure of X with respect to
the set F.
Alternate Key: All other keys are alternate keys from { closure of x determines y then x → y is a m em ber/
the set of candidate keys, except the primary key. logically implies / inferred by FD set F }
Super-key: If all attributes of relation R are Equality between 2FD set:
determined by attribute (attribute set) closure of X Let two FD set F & G give
[X]+,then X is super key.. The superset of the candidate
key is known as the super key in a relation.
Example: consider Emp-id as a candidate key in a
relation Employee.
Then, {Emp-id, Emp-name} is a super-key. Relation F⊃G G⊃F F=G Uncomaparabl
e
Candidate key: The minimal superkey is defined as F Covers G True False True False
the candidate key.
G Covers F False True True False
R(ABCDE) [AB → C, C → D, B → EA]
[AB]+ = [ABCDE], therefore AB is super key,
[A]+ = [A]
[B]+ = [ABCDE], therefore B is the candidate key. Minimal cover: To eliminate redundant FD.
Key / Prime attribute: Set of attributes which belongs Minimal / Canonical cover: Sets of FD may have
in any candidate key. redundant dependencies that can be inferred from
others.
Non Key / Non Prime attribute: Set of attributes
which does not belong in any candidate key. Procedure to find canonical cover:
Key/prime attribute = [B] 1. Split the FD such that RHS contain single attribute
Non key/ Non Prime attribute = [A, C, D, E] Ex. A → BC : A → B, A → C
Note: To find the candidate key, first find the super 2. Find the redundant attribute on LHS and delete
key, then check the minimum of that super key. them.
3. Find the redundant FD and delete them from the
Finding Multiple candidate Key: First find any one
FD set. { A → B, B → C, A → C } : { A → B, B → C }
candidate key in relation R, the attribute present in
that candidate key is key/prime attribute.
Note: Minimal cover may or may not be unique i.e. we
can have more than one.
If X → {Prime/Key Attribute}, then
Attribute Finding number of super key: Let R be the relational
multiple candidate keys are possible. schema with n attributes A1, A2, ….An
Total number of super keys = 2n-1 (with only CK A1)
Maximum number of candidate key = n C ⌊n/2⌋ , Where n
Membership set is number of attributes.
Let F be a given set of functional dependencies.
Page No:- 02