Normal Forms and Functional Dependency 2

Question 1

What is Normalization or Schema Refinement?

Answer 1

Normalization or Schema Refinement is a technique of organizing the data in the
database
* A systematic approach of decomposing tables to eliminate data redundancy and
undesirable characteristics

Normalization is used for mainly two purposes:
◦ Eliminating redundant (useless) data
◦ Ensuring data dependencies make sense, that is, data is logically stored

Question 2

What is a Normal Form?

Answer 2

A normal form specifies a set of conditions that the relational schema must satisfy in terms of its constraints – they offer varied levels of guarantee for the design

Question 3

What are some of the Normal Forms?

Answer 3

• Normalization rules are divided into various normal forms. Most common normal forms
  are:
  ◦ First Normal Form (1NF)
  ◦ Second Normal Form (2NF)
  ◦ Third Normal Form (3NF)
  Informally, a relational database relation is often described as ”normalized” if it meets
  the third normal form. Most 3NF relations are free of insertion, update, and deletion
  anomalies

Additional Normal Forms
◦ Elementary Key Normal Form (EKNF)
◦ Boyce-codd Normal Form (BCNF)
◦ Multivalued Dependencies And Fourth Normal Form (4NF)
◦ Essential Tuple Normal Form (ETNF)
◦ Join Dependencies and Fifth Normal Form (5NF)
◦ Sixth Normal Form (6NF)
◦ Domain/Key Normal Form (DKNF)

Question 4

What is 1NF: First Normal Form?

Answer 4

A relation is in First Normal Form if and only if all underlying domains contain atomic
values only (doesn’t have multivalued attributes (MVA))

Question 5

What is a Partial Dependency?

Answer 5

Partial Dependency:
Let R be a relational Schema and X, Y , A be the attribute sets over R where X : Any Candidate Key, Y : Proper Subset of Candidate Key, and A : Non Prime Attribute
If Y → A exists in R, then R is not in 2NF.
(Y → A) is a Partial dependency only if
* Y : Proper subset of Candidate Key
* A: Non Prime Attribute
A prime attribute of a relation is an attribute that is a part of a candidate key of the relation

Question 6

What are Prime Attributes?

Answer 6

A prime attribute of a relation is an attribute that is a part of a candidate key of the relation

Question 7

What is 2NF:Second Normal Form?

Answer 7

• Relation R is in Second Normal Form (2NF) only iff:
  ◦ R is in 1NF and
  ◦ R contains no Partial Dependency

Question 8

What does 2NF ensure?

Answer 8

2NF ensures that no subset of a candidate key determines a non prime attribute. That is, there is no partial dependency in the relation.

Question 9

What is a Transitive dependency?

Answer 9

A transitive dependency is a functional dependency which holds by virtue of transitivity. A transitive dependency can occur only in a relation that has three or more attributes.
* Let A, B, and C designate three distinct attributes (or distinct collections of attributes) in the relation. Suppose all three of the following conditions hold:
◦ A → B
◦ It is not the case that B → A
◦ B → C
* Then the functional dependency A → C (which follows from 1 and 3 by the axiom of
transitivity) is a transitive dependency

Question 10

What is 3NF: Third Normal Form?

Answer 10

Let R be the relational schema.
* [E. F. Codd,1971] R is in 3NF only if:
◦ R should be in 2NF
◦ R should not contain transitive dependencies (OR, Every non-prime attribute of R is
non-transitively dependent on every key of R)

[Simple Statement] A relational schema R is in 3NF if for every FD X → A associated with R either
◦ A ⊆ X (that is, the FD is trivial) or
◦ X is a superkey of R or
◦ A is part of some candidate key (not just superkey!)

Question 11

What does 3NF ensure?

Answer 11

3NF ensures that LHS is a superkey or RHS is a prime attribute. That is , no non prime attribute determines a non prime attribute.

Question 12

Does 3NF ensure no redundancy?

Answer 12

No. There is some redundancy even in 3NF

Question 13

How is 3NF important? What are its characteristics?

Answer 13

The next higher normal form is BCNF which is sometimes not dependency preserving. Hence, There is always a lossless-join, dependency-preserving decomposition into 3NF (tradeoff: some redundancy). Dependency preserving ensures that joins are not required for checking FDs.
1. Testing for 3NF has been shown to be NP-hard
2. Decomposition into 3NF can be done in polynomial time

Question 14

How to decompose relations into 3NF?

Answer 14

Algorithm:
a) Eliminate redundant FDs, resulting in a canonical cover Fc of F
b) Create a relation Ri = XY for each FD X → Y in Fc
c) If the key K of R does not occur in any relation Ri, create one more relation Ri = K

Question 15

What is BCNF?

Answer 15

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 16

How to check if a relation is in BCNF?

Answer 16

To check if a non-trivial dependency α → β causes a violation of BCNF
a) Compute α+ (the attribute closure of α), and
b) Verify that it includes all attributes of R, that is, it is a superkey of R.
* Simplified test: To check if a relation schema R is in BCNF, it suffices to check only the dependencies in the given set F for violation of BCNF, rather than checking all dependencies in F+.
◦ If none of the dependencies in F causes a violation of BCNF, then none of the dependencies in F+ will cause a violation of BCNF either.
* However, simplified test using only F is incorrect when testing a relation in a decomposition of R

Question 17

Does BCNF eliminate redundancy?

Answer 17

Yes. BCNF ensures 0% redundancy

Question 18

What are MVD: Multivalued Dependency?

Answer 18

Let R be a relation schema and let α ⊆ R and β ⊆ R. The multivalued dependency
α β
holds on R if in any legal relation r(R), for all pairs for tuples t1 and t2 in r such that
t1[α] = t2 [α], there exist tuples t3 and t4 in r such that:
t1[α] = t2 [α] = t3 [α] = t4 [α]
t3[β] = t1 [β]
t3[R – β] = t2[R – β]
t4 [β] = t2[β]
t4[R – β] = t1[R – β]

Question 19

What is 4NF: Fourth Normal Form?

Answer 19

• A relation schema R is in 4NF with respect to a set D of functional and multivalued dependencies if for all multivalued dependencies in D+ of the form α β, where α ⊆R and β ⊆ R, at least one of the following hold:
  ◦ α β is trivial (that is, β ⊆ α or α ∪ β = R)
  ◦ α is a superkey for schema R
• If a relation is in 4NF it is in BCNF

Question 20

What is 4NF Decomposition Algorithm?

Answer 20

a) For all dependencies A B in D+, check if A is a superkey
* By using attribute closure
b) If not, then
* Choose a dependency in F+ that breaks the 4NF rules, say A B
* Create R1 = A B
* Create R2 = (R – (B – A))
* Note that: R1 ∩ R2 = A and A AB (= R1), so this is lossless decomposition
c) Repeat for R1, and R2
* By defining D1+ to be all dependencies in F that contain only attributes in R1
* Similarly D2+

Question 21

What is the overall Database Design Process?

Answer 21

• We have assumed schema R is given
  ◦ R could have been generated when converting E-R diagram to a set of tables
  ◦ R could have been a single relation containing all attributes that are of interest
  (universal relation)
  ◦ Normalization breaks R into smaller relations
  ◦ R could have been the result of some ad hoc design of relations, which we then
  test/convert to normal form

Question 22

What are temporal Databases?

Answer 22

Temporal databases provide a uniform and systematic way of dealing with historical data

Question 23

What are Temporal Data?

Answer 23

Temporal data have an association time interval during which the data are valid.
* A snapshot is the value of the data at a particular point in time

Question 24

Valid Time Vs Transaction Time in temporal databases?

Answer 24

Valid Time: Time period during which a fact is true in real world, provided to the system.
◦ Transaction Time: Time period during which a fact is stored in the database, based on transaction serialization order and is the timestamp generated automatically by
the system.

Question 25

What are Uni-Temporal Relations and Bi-Temporal Relations?

Answer 25

Temporal Relation is one where each tuple has associated time; either valid time or transaction time or both associated with it.
◦ Uni-Temporal Relations: Has one axis of time, either Valid Time or Transaction Time.
◦ Bi-Temporal Relations: Has both axis of time – Valid time and Transaction time.
It includes Valid Start Time, Valid End Time, Transaction Start Time, Transaction End Time.

Question 26

What are the advantages and disadvantages of Bi-Temporal relations?

Answer 26

Advantages
◦ The main advantages of this bi-temporal relations is that it provides historical and roll back information.
. Historical Information – Valid Time.
. Rollback Information – Transaction Time.
◦ For example, you can get the result for a query on John’s history, like: Where did John live in the year 2001?. The result for this query can be got with the valid time
entry. The transaction time entry is important to get the rollback information.
* Disadvantages
◦ More storage
◦ Complex query processing
◦ Complex maintenance including backup and recovery