Normal Forms and Functional Dependency1

Question 1

What is redundancy?

Answer 1

having multiple copies of the same data in the database

Question 2

What is the effect of redundancy?

Answer 2

Anomaly: inconsistencies that can arise due to data changes in a database with
insertion, deletion, and update

Question 3

What are types of anomaly?

Answer 3

1. Insertion Anomaly
2. Deletion Anomaly
3. Update Anomaly

Question 4

What is Insertion Anomaly?

Answer 4

If there are lot of data redundancy.. then When the insertion of a data record is not possible without adding some additional
unrelated data to the record is called insertion anomaly

Question 5

What is Deletion Anomaly?

Answer 5

When deletion of a data record results in losing some unrelated information that
was stored as part of the record that was deleted from a table

Question 6

What is Update Anomaly?

Answer 6

When a data is changed, which could involve many records having to be changed,
leading to the possibility of some changes being made incorrectly.

Question 7

What is the cause of redundancy?

Answer 7

Dependency ⇒ Redundancy ⇒ Anomaly

Question 8

How to remove or atleast minimize redundancy?

Answer 8

Decompose (partition) the relation into smaller relations

Question 9

What is a good decomposition?

Answer 9

Good Decomposition ⇒ Minimization of Dependency

Question 10

Is every decomposition good?

Answer 10

No. It needs to preserve information, honour the dependencies, be efficient etc.
◦ Various schemes of normalization ensure good decomposition
◦ Normalization ⇒ Good Decomposition

Question 11

What is lossy decomposition?

Answer 11

If we cannot reconstruct the original
relation from the decomposed part relations, it is called a lossy decomposition. Loss doesn’t necessarily mean missing data.. even if there is additional data.. the decomposition is said to be lossy.

Question 12

What is lossless decomposition?

Answer 12

Lossless Join Decomposition is a decomposition of a relation R into relations R1, R2
such that if we perform natural join of two smaller relations it will return the original
relation
1. R1 ∪ R2 = R, R1 ∩ R2 6= φ
2. ∀r ∈ R,r1 = uR1(r),r2 = uR2(r)
3. r1 ./ r2 = r (join)

In other words by lossless decomposition it becomes feasible to reconstruct the relation
R from decomposed tables R1 and R2 by using Joins

Question 13

What is First Normal Form (1NF)?

Answer 13

A domain is atomic if its elements are considered to be indivisible units

A relational schema R is in First Normal Form (INF) if
◦ the domains of all attributes of R are atomic
◦ the value of each attribute contains only a single value from that domain

NO Composite, multivalued attributes

If an attribute is multivalued.. then split into 2 relations (one to many relationship)

Question 14

What does atomicity mean?

Answer 14

Atomicity is actually a property of how the elements of the domain are used
◦ Strings would normally be considered indivisible
◦ Suppose that students are given roll numbers which are strings of the form CS0012 or EE1127
◦ If the first two characters are extracted to find the department, the domain
of roll numbers is NOT atomic

Question 15

What is a functional dependency?

Answer 15

The functional dependency or FD
α → β
holds on R if and only if for any legal relations r(R), whenever any two tuples t1 and t2
of r agree on the attributes α, they also agree on the attributes β. That is,
t1[α] = t2[α] ⇒ t1[β] = t2[β]

In Short, if A →B means if A then B

Question 16

When is a Functional Dependency called Trivial?

Answer 16

• A functional dependency is trivial if it is satisfied by all instances of a relation
  ◦ Example:
  . ID, name → ID
  . name → name
• In general, α → β is trivial if β ⊆ α.

Question 17

What is a Super Key?

Answer 17

K is a superkey for relation schema R if and only if K → R
That is , K is super key if it uniquely identifies a row in the relation.

Question 18

What is a candidate key?

Answer 18

K is a candidate key for R if and only if
◦ K → R and
◦ for no α ⊂ K, α → R

That is, Candidate key is minimal super key.
Candidate key is subset of a Super Key

Question 19

How to find the candidate keys in a relation R?

Answer 19

start with all the attributes of the relation as super key.. remove attributes one by one which can be derived from other.. (i.e, maintaining closure). then , check with each and every proper subset to see if any of them has closure of R. If not then we have a candidate key. else we take the new attirbute which has closure to R and check its proper subsets. After arriving at a candidate key. we check the FDs to see if we could derive an attribute in candidate key from another FD. If so, we replace that attribute alone and check again. We do this for all attributes until no more replacements could be made.. then we would have all the candidate keys of the relation

Question 20

What are Armstrong’s Axioms, which help us dervie new functional dependencies from existing functional dependencies?

Answer 20

Armstrong’s Axioms:
◦ Reflexivity: if β ⊆ α, then α → β
◦ Augmentation: if α → β, then γα → γβ
◦ Transitivity: if α → β and β → γ, then α → γ
* These axioms can be repeatedly applied to generate new FDs and added to F

Question 21

What does Reflexivity axiom of Armstrong’s axiom derive?

Answer 21

◦ Reflexivity: if β ⊆ α, then α → β
Eg: (Student,Dept) -> Student
(Student, Dept) -> Dept

Question 22

How to compute closure of a set of Functional Dependencies - F+

Answer 22

To compute the closure of a set of functional dependencies F:
F+ ← F
repeat
for each functional dependency f in F+
apply reflexivity and augmentation rules on f
add the resulting functional dependencies to F+
for each pair of functional dependencies f1 and f2 in F+
if f1 and f2 can be combined using transitivity
then add the resulting functional dependency to F+
until F+ does not change any further

Question 23

What are some of additional derived rules from Armstrong’s Axioms

Answer 23

◦ Union: if α → β holds and α → γ holds, then α → βγ holds
◦ Decomposition: if α → βγ holds, then α → β holds and α → γ holds
◦ Pseudotransitivity: if α → β holds and γβ → δ holds, then αγ → δ holds

Question 24

How to test for a superkey?

Answer 24

To test if α is a superkey, we compute α
+, and check if α+ contains all attributes
of R

Question 25

How to find candidate key of a relation?

Answer 25

The attribute which is not in RHS of any functional dependency will be a part of candidate key (or super key) . So start from there.. find closure of those attributes, if closure covers R then it forms a candidate key. else add one more attribute and check if any of them covers R.

if the attributes of candidate key are not present in the RHS of any FD’s there wont be anymore candidate keys. we could stop looking

Question 26

How to test functional dependencies

Answer 26

To check if a functional dependency α → β holds (or, in other words, is in F+), just
check if β ⊆ α+
◦ That is, we compute α+ by using attribute closure, and then check if it contains β.
◦ Is a simple and cheap test, and very useful

Given a set of functional dependencies F, we could test for whether a new FD holds on F by just find out the closure of the LHS of new FD. If RHS could be derived then the new FD hold on F else otherwise.

Question 27

What is 2NF: Second Normal Form?

Answer 27

We need to find candidate keys first.

The relations R is in 1NF and there are no partial dependency (i.e., no proper subset of a candidate key is determining a non-prime attribute).

If there are no non-prime attributes then the relation R is in 2NF always.

Question 28

What is BCNF?

Answer 28

Intuitively: A relation is in BCNF if it is in 3NF and for all non trivial FDs , LHS is a Super Key

A relation schema R is in BCNF with respect to a set F of FDs if for all FDs in F+ of the form α → β, where α ⊆ R and β ⊆ R at least one of the following holds:
◦ α → β is trivial (that is, β ⊆ α)
◦ α is a Superkey for R

Question 29

What does BCNF ensure?

Answer 29

BCNF ensures that the FD is either trivial or the α in α → β is a Super key

That is, if there is a functional dependency.. then it can only be a super key of the relation.

Question 30

How to solve BCNF violation caused by a non-trivial dependency?

Answer 30

If in schema R and a non-trivial dependency α → β causes a violation of BCNF, we decompose R into:
◦ α ∪ β
◦ (R − (β − α))

That is, combine attributes of alpha and beta to a new relation.. remove beta from original relation leaving out alpha.

Question 31

How to check if a decomposition is lossless using Functional Dependency Set?

Answer 31

Union of Attributes of R1 and R2 must be equal to attribute of R
R1 ∪ R2 = R
◦ Intersection of Attributes of R1 and R2 must not be NULL
R1 ∩ R2 6= Φ
◦ Common attribute must be a key for at least one relation (R1 or R2)
R1 ∩ R2 → R1 or R1 ∩ R2 → R2

Question 32

What is Dependency Preservation?

Answer 32

If it is sufficient to test only those dependencies on each individual relation of a decomposition in order to ensure that all functional dependencies hold, then that
decomposition is dependency preserving.

If the dependencies involve two different relations then we could not check the FD without doing a join.

Question 33

What is Third Normal Form (3NF)?

Answer 33

Weaker than BCNF:
Intuitively: R is in 2NF and there are no transitive dependency(i.e., Non prime attribute determining a non prime attribute) - That is, LHS should be a Super Key (OR) RHS should be a Prime Attribute.

A relation schema R is in third normal form (3NF) if for all:
α → β ∈ F+
at least one of the following holds:
◦ α → β is trivial (that is, β ⊆ α)
◦ α is a superkey for R
◦ Each attribute A in β − α is contained in a candidate key for R
(Note: Each attribute may be in a different candidate key)

Question 34

Does BCNF ensure from anomalies?

Answer 34

No. A relation could be in BCNF but still have anomalies.. which is why higher order normal forms such as 4NF and above exist.

Question 35

What is attribute set closure helpful for?

Answer 35

1. Testing for superkey
2. Testing functional dependencies
3. Computing closure of F
   ◦ For each γ ⊆ R, we find the closure γ+, and for each S ⊆ γ+, we output a functional dependency γ → S.

Question 36

What are Extraneous Attributes?

Answer 36

Intuitively, An attribute of a functional dependency is said to be extraneous if we can remove it without changing the closure of the set of functional dependencies. Normally, occurs in the LHS of a Functional dependency where there is more than one attribute.

Attribute A is extraneous in α if A ∈ α and F logically implies (F − {α → β}) ∪ {(α − A) → β}.
◦ Attribute A is extraneous in β if A ∈ β and the set of FDs
(F − {α → β}) ∪ {α → (β − A)} logically implies F.
* Note: Implication in the opposite direction is trivial in each of the cases above, since a “stronger” functional dependency always implies a weaker one

Question 37

How to test for Extraneous Attributes?

Answer 37

Consider a set F of functional dependencies and the functional dependency α → β in F.
* To test if attribute A ∈ α is extraneous in α
a) Compute ({α} − A)
+ using the dependencies in F
b) Check that ({α} − A)
+ contains β; if it does, A is extraneous in α
* To test if attribute A ∈ β is extraneous in β
a) Compute α
+ using only the dependencies in
F
0 = (F − {α → β}) ∪ {α → (β − A)},
b) Check that α
+ contains A; if it does, A is extraneous in β

Question 38

When are two set of Functional dependencies considered equivalent?

Answer 38

Let F & G are two functional dependency sets.
◦ These two sets F & G are equivalent if F+ = G+. That is:
(F+ = G+) ⇔ (F+ ⇒ G and G + ⇒ F)
◦ Equivalence means that every functional dependency in F can be inferred from G,
and every functional dependency in G can be inferred from F

Question 39

What is a Canonical Cover ?

Answer 39

A Canonical Cover for F is a set of dependencies Fc such that ALL the following
properties are satisfied:
◦ F+ = Fc+
. Or,
. F logically implies all dependencies in Fc
. Fc logically implies all dependencies in F
◦ No functional dependency in Fc contains an extraneous attribute
◦ Each left side of functional dependency in Fc is unique. That is, there are no two
dependencies α1 → β1 and α2 → β2 in such that α1 → α2

• Intuitively, a Canonical cover of F is a minimal set of FDs
  ◦ Equivalent to F
  ◦ Having no redundant FDs
  ◦ No redundant parts of FDs
• Minimal / Irreducible Set of Functional Dependencies

Question 40

Where is canonical cover used?

Answer 40

Whenever there is an update, SQL system checks for compliance of all functional dependencies. If there is a violation, it throws an error. There may be many functional dependencies and so this task could be very expensive. So, it is effective to reduce to set of functional dependencies to the minimum so that it become cost effective. Hence, canonical cover is calculated and used. Note: closure of F and Canonical Cover are the same.

Question 41

What are the steps involved in calculating canonical cover?

Answer 41

1. convert all F s such that there is a single attribute on the RHS
2. Find out if there are any extraneous attributes
3. Find out if there are any redundant FDs (using Armstrong’s Axioms) - Check for the closure of LHS of all F’s . Remove a candidate redundant FD and recheck the closure of LHS of remaining F’s . we should get the same cover. If not , the candidate FD was not redundant

Question 42

What is lossless join decomposition?

Answer 42

To Identify whether a decomposition is lossy or lossless, it must satisfy the following conditions:
* R1 ∪ R2 = R
* R1 ∩ R2 != φ and
* R1 ∩ R2 → R1 or R1 ∩ R2 → R2

Question 43

If there are more that 2 decomposed relations how to check for whether it is a lossless or lossy decomposition?

Answer 43

Let R1, R2, R3 be 3 decomposed relations. First we check for R1 and R2. If passed, we taken union of R1 and R2 and check that with R3.

Note: we need to check the union of all relations.
we need to check for intersection and closure between a pair of relations one by one.

Question 44

What is Dependency Preservation?

Answer 44

Let Fi be the set of dependencies F
+ that include only attributes in Ri
◦ A decomposition is dependency preserving, if
(F1 ∪ F2 ∪ · · · ∪ Fn)+ = F+
◦ If it is not, then checking updates for violation of functional dependencies may
require computing joins, which is expensive.

Question 45

How to test if dependency is preserved?

Answer 45

Intuitively, for each and every attribute in each and every decomposed relation. find closure and extract the new dependencies valid in that relation, that is, remove attributes/FDs not pertaining to that decomposed relation.. Take a union of all of them and then using the newly formed dependencies, test the new FD for closure. use Armstrong’s axioms wherever needed.

To check if a dependency α → β is preserved in a decomposition of R into D = {R1, R2, . . . , Rn} we apply the following test (with attribute closure done with respect to F)
* The restriction of F+ to Ri is the set of all functional dependencies in F+ that include only attributes of Ri
.
◦ compute F+;
for each schema Ri in D do
begin
Fi = the restriction of F+ to Ri;
end
F’ = φ
for each restriction Fi do
begin
F’ = F’ ∪ Fi
end
compute F’+;
if (F’+ = F+) then return (true)
else return (false);

• The procedure for checking dependency preservation takes exponential time to compute F+ and (F1 ∪ F2 ∪ · · · ∪ Fn)+

Question 46

Does lossless decomposition and dependency preserving imply each other?

Answer 46

No. One can exist with or without the other.