Tag: normal forms

Chomsky Normal Form | Normal Forms in Automata

Normal Forms-

 

Normalization is performed in order to standardize the grammar.

 

  • By reducing the grammar, the grammar gets minimized but does not gets standardized.
  • This is because the RHS of productions have no specific format.
  • In order to standardize the grammar, normalization is performed using normal forms.

 

Types of Normal Forms-

 

The most frequently used normal forms are-

 

 

  1. Chomsky Normal Form (CNF)
  2. Greibach Normal Form (GNF)

 

In this article, we will discuss about Chomsky Normal Form.

 

Chomsky Normal Form-

 

A context free grammar is said to be in chomsky normal form (CNF) if all its productions are of the form-

BC or a

where A, B, C are non-terminals and a is a terminal.

 

From here, we infer-

  • To be in CNF, all the productions must derive either two non-terminals or a single terminal.
  • CNF restricts the number of symbols on the right side of a production to be two.
  • The two symbols must be non-terminals or a single terminal.

 

Example-

 

S → AB

A → a

B → b

 

This context free grammar is in chomsky normal form.

 

Steps-

 

The following steps are followed to standardize the grammar using CNF-

 

Rule-01:

 

Reduce the grammar completely by-

  • Eliminating ∈ productions
  • Eliminating unit productions
  • Eliminating useless productions

 

Also Watch- How To Reduce Grammar?

 

Rule-02:

 

Replace each production of the form A → B1B2B3….Bn where n > 2 with A → B1C where C → B2B3….Bn.

Repeat this step for all the productions having more than two variables on RHS.

 

Rule-03:

 

Replace each production of the form A → aB with A → XB and X → a.

Repeat this step for all the productions having the form A → aB.

 

PRACTICE PROBLEMS BASED ON CHOMSKY NORMAL FORM-

 

Problem-01:

 

Convert the given grammar to CNF-

S → aAD

A → aB / bAB

B → b

D → d

 

Solution-

 

Step-01:

 

The given grammar is already completely reduced.

 

Step-02:

 

The productions already in chomsky normal form are-

B → b        ………..(1)

D → d        ………..(2)

These productions will remain as they are.

 

The productions not in chomsky normal form are-

S → aAD                ………..(3)

A → aB / bAB         ………..(4)

We will convert these productions in chomsky normal form.

 

Step-03:

 

Replace the terminal symbols a and b by new variables Ca and Cb.

 

This is done by introducing the following two new productions in the grammar-

Ca → a       ………..(5)

Cb → b       ………..(6)

 

Now, the productions (3) and (4) modifies to-

S → CaAD                  ………..(7)

A → CaB / CbAB         ………..(8)

 

Step-04:

 

Replace AD and AB by new variables CAD and CAB respectively.

 

This is done by introducing the following two new productions in the grammar-

CAD → AD       ………..(9)

CAB → AB       ………..(10)

 

Now, the productions (7) and (8) modifies to-

S → CaCAD                  ………..(11)

A → CaB / CbCAB         ………..(12)

 

Step-05:

 

From (1), (2), (5), (6), (9), (10), (11) and (12), the resultant grammar is-

 

S → CaCAD

A → CaB / CbCAB

B → b

D → d

Ca → a

Cb → b

CAD → AD

CAB → AB

 

This grammar is in chomsky normal form.

 

Problem-02:

 

Convert the given grammar to CNF-

S → 1A / 0B

A → 1AA / 0S / 0

B → 0BB / 1S / 1

 

Solution-

 

Step-01:

 

The given grammar is already completely reduced.

 

Step-02:

 

The productions already in chomsky normal form are-

A → 0        ………..(1)

B → 1        ………..(2)

These productions will remain as they are.

 

The productions not in chomsky normal form are-

S → 1A / 0B           ………..(3)

A → 1AA / 0S         ………..(4)

B → 0BB / 1S         ………..(5)

We will convert these productions in chomsky normal form.

 

Step-03:

 

Replace the terminal symbols 0 and 1 by new variables C and D.

 

This is done by introducing the following two new productions in the grammar-

C → 0       ………..(6)

D → 1       ………..(7)

 

Now, the productions (3), (4) and (5) modifies to-

S → DA / CB           ………..(8)

A → DAA / CS         ………..(9)

B → CBB / DS         ………..(10)

 

Step-04:

 

Out of (8), (9) and (10), the productions already in Chomsky Normal Form are-

S → DA / CB           ………..(11)

A → CS                   ………..(12)

B → DS                   ………..(13)

These productions will remain as they are.

 

The productions not in chomsky normal form are-

A → DAA         ………..(14)

B → CBB         ………..(15)

We will convert these productions in Chomsky Normal Form.

 

Step-05:

 

Replace AA and BB by new variables E and F respectively.

 

This is done by introducing the following two new productions in the grammar-

E → AA       ………..(16)

F → BB       ………..(17)

 

Now, the productions (14) and (15) modifies to-

A → DE         ………..(18)

B → CF         ………..(19)

 

Step-06:

 

From (1), (2), (6), (7), (11), (12), (13), (16), (17), (18) and (19), the resultant grammar is-

 

S → DA / CB

A → CS / DE / 0

B → DS / CF / 1

C → 0

D → 1

E → AA

F → BB

 

This grammar is in chomsky normal form.

 

To gain better understanding about Chomsky Normal Form,

Watch this Video Lecture

 

Next Article- Algorithm To Decide Whether CFL Is Empty

 

Get more notes and other study material of Theory of Automata and Computation.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Normal Forms in Database | Important Points

Normal Forms in DBMS-

 

Before you go through this article, make sure that you have gone through the previous article on Normalization in DBMS.

 

We have discussed-

  • Database normalization is a process of making the database consistent.
  • Normalization is done through normal forms.
  • The standard normal forms generally used are-

 

 

In this article, we will discuss some important points about normal forms.

 

Point-01:

 

Remember the following diagram which implies-

  • A relation in BCNF will surely be in all other normal forms.
  • A relation in 3NF will surely be in 2NF and 1NF.
  • A relation in 2NF will surely be in 1NF.

 

 

Point-02:

 

The above diagram also implies-

  • BCNF is stricter than 3NF.
  • 3NF is stricter than 2NF.
  • 2NF is stricter than 1NF.

 

Point-03:

 

While determining the normal form of any given relation,

  • Start checking from BCNF.
  • This is because if it is found to be in BCNF, then it will surely be in all other normal forms.
  • If the relation is not in BCNF, then start moving towards the outer circles and check for other normal forms in the order they appear.

 

Point-04:

 

  • In a relational database, a relation is always in First Normal Form (1NF) at least.

 

Point-05:

 

  • Singleton keys are those that consist of only a single attribute.
  • If all the candidate keys of a relation are singleton candidate keys, then it will always be in 2NF at least.
  • This is because there will be no chances of existing any partial dependency.
  • The candidate keys will either fully appear or fully disappear from the dependencies.
  • Thus, an incomplete candidate key will never determine a non-prime attribute.

 

Also read- Types of Keys in DBMS

 

Point-06:

 

  • If all the attributes of a relation are prime attributes, then it will always be in 2NF at least.
  • This is because there will be no chances of existing any partial dependency.
  • Since there are no non-prime attributes, there will be no Functional Dependency which determines a non-prime attribute.

 

Point-07:

 

  • If all the attributes of a relation are prime attributes, then it will always be in 3NF at least.
  • This is because there will be no chances of existing any transitive dependency for non-prime attributes.

 

Point-08:

 

  • Third Normal Form (3NF) is considered adequate for normal relational database design.

 

Point-09:

 

  • Every binary relation (a relation with only two attributes) is always in BCNF.

 

Point-10:

 

  • BCNF is free from redundancies arising out of functional dependencies (zero redundancy).

 

Point-11:

 

  • A relation with only trivial functional dependencies is always in BCNF.
  • In other words, a relation with no non-trivial functional dependencies is always in BCNF.

 

Point-12:

 

  • BCNF decomposition is always lossless but not always dependency preserving.

 

Point-13:

 

  • Sometimes, going for BCNF may not preserve functional dependencies.
  • So, go for BCNF only if the lost functional dependencies are not required else normalize till 3NF only.

 

Point-14:

 

  • There exist many more normal forms even after BCNF like 4NF and more.
  • But in the real world database systems, it is generally not required to go beyond BCNF.

 

Point-15:

 

  • Lossy decomposition is not allowed in 2NF, 3NF and BCNF.
  • So, if the decomposition of a relation has been done in such a way that it is lossy, then the decomposition will never be in 2NF, 3NF and BCNF.

 

Point-16:

 

  • Unlike BCNF, Lossless and dependency preserving decomposition into 3NF and 2NF is always possible.

 

Point-17:

 

  • A prime attribute can be transitively dependent on a key in a 3NF relation.
  • A prime attribute can not be transitively dependent on a key in a BCNF relation.

 

Point-18:

 

  • If a relation consists of only singleton candidate keys and it is in 3NF, then it must also be in BCNF. 

 

Point-19:

 

  • If a relation consists of only one candidate key and it is in 3NF, then the relation must also be in BCNF. 

 

Also Read- How To Find Candidate Keys?

 

Next Article- Transactions in DBMS

 

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Normalization in DBMS | Normal Forms

Normalization in DBMS-

 

In DBMS, database normalization is a process of making the database consistent by-

  • Reducing the redundancies
  • Ensuring the integrity of data through lossless decomposition

Normalization is done through normal forms.

 

Normal Forms-

 

The standard normal forms used are-

 

 

  1. First Normal Form (1NF)
  2. Second Normal Form (2NF)
  3. Third Normal Form (3NF)
  4. Boyce-Codd Normal Form (BCNF)

 

There exists several other normal forms even after BCNF but generally we normalize till BCNF only.

 

First Normal Form-

 

A given relation is called in First Normal Form (1NF) if each cell of the table contains only an atomic value.

OR

A given relation is called in First Normal Form (1NF) if the attribute of every tuple is either single valued or a null value.

 

Example-

 

The following relation is not in 1NF-

 

Student_idNameSubjects
100AkshayComputer Networks, Designing
101AmanDatabase Management System
102AnjaliAutomata, Compiler Design

Relation is not in 1NF

 

However,

  • This relation can be brought into 1NF.
  • This can be done by rewriting the relation such that each cell of the table contains only one value.

 

Student_idNameSubjects
100AkshayComputer Networks
100AkshayDesigning
101AmanDatabase Management System
102AnjaliAutomata
102AnjaliCompiler Design

Relation is in 1NF

 

This relation is in First Normal Form (1NF).

 

NOTE-

 

  • By default, every relation is in 1NF.
  • This is because formal definition of a relation states that value of all the attributes must be atomic.

 

Second Normal Form-

 

A given relation is called in Second Normal Form (2NF) if and only if-

  1. Relation already exists in 1NF.
  2. No partial dependency exists in the relation.

 

Also Read- Functional Dependency in DBMS

 

Partial Dependency

 

A partial dependency is a dependency where few attributes of the candidate key determines non-prime attribute(s).

OR

A partial dependency is a dependency where a portion of the candidate key or incomplete candidate key determines non-prime attribute(s).

 

In other words,

A → B is called a partial dependency if and only if-

  1. A is a subset of some candidate key
  2. B is a non-prime attribute.

If any one condition fails, then it will not be a partial dependency.

 

NOTE-

 

  • To avoid partial dependency, incomplete candidate key must not determine any non-prime attribute.
  • However, incomplete candidate key can determine prime attributes.

 

Also Read- How To Find Candidate Keys?

 

Example-

 

Consider a relation- R ( V , W , X , Y , Z ) with functional dependencies-

VW → XY

Y → V

WX → YZ

 

The possible candidate keys for this relation are-

VW , WX , WY

 

From here,

  • Prime attributes = { V , W , X , Y }
  • Non-prime attributes = { Z }

 

Now, if we observe the given dependencies-

  • There is no partial dependency.
  • This is because there exists no dependency where incomplete candidate key determines any non-prime attribute.

 

Thus, we conclude that the given relation is in 2NF.

 

Third Normal Form-

 

A given relation is called in Third Normal Form (3NF) if and only if-

  1. Relation already exists in 2NF.
  2. No transitive dependency exists for non-prime attributes.

 

Transitive Dependency

 

A → B is called a transitive dependency if and only if-

  1. A is not a super key.
  2. B is a non-prime attribute.

If any one condition fails, then it is not a transitive dependency.

 

NOTE-

 

  • Transitive dependency must not exist for non-prime attributes.
  • However, transitive dependency can exist for prime attributes.

 

OR

 

A relation is called in Third Normal Form (3NF) if and only if-

Any one condition holds for each non-trivial functional dependency A → B

  1. A is a super key
  2. B is a prime attribute

 

Example-

 

Consider a relation- R ( A , B , C , D , E ) with functional dependencies-

A → BC

CD → E

B → D

E → A

 

The possible candidate keys for this relation are-

A , E , CD , BC

 

From here,

  • Prime attributes = { A , B , C , D , E }
  • There are no non-prime attributes

 

Now,

  • It is clear that there are no non-prime attributes in the relation.
  • In other words, all the attributes of relation are prime attributes.
  • Thus, all the attributes on RHS of each functional dependency are prime attributes.

 

Thus, we conclude that the given relation is in 3NF.

 

Boyce-Codd Normal Form-

 

A given relation is called in BCNF if and only if-

  1. Relation already exists in 3NF.
  2. For each non-trivial functional dependency A → B, A is a super key of the relation.

 

Example-

 

Consider a relation- R ( A , B , C ) with the functional dependencies-

A → B

B → C

C → A

 

The possible candidate keys for this relation are-

A , B , C

 

Now, we can observe that RHS of each given functional dependency is a candidate key.

Thus, we conclude that the given relation is in BCNF.

 

Next Article- Important Points About Normal Forms

 

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.