Category: Subjects

Normal Forms in Database | Important Points

Database Management System

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.

Universal Logic Gates | NAND Gate | NOR Gate

Digital Design

Logic Gates-

 

Before you go through this article, make sure that you have gone through the previous article on Logic Gates.

 

We have discussed-

  • Logic gates are the basic building blocks of any digital circuit.
  • There are 3 basic logic gates- AND, NOT, OR.
  • Logic gates are classified as-

 

 

In this article, we will discuss about Universal Logic Gates.

 

Universal Logic Gates-

 

Universal logic gates are the logic gates that are capable of implementing any Boolean function

without requiring any other type of gate.

 

They are called as “Universal Gates” because-

  • They can realize all the binary operations.
  • All the basic logic gates can be derived from them.

 

They have the following properties-

  • Universal gates are not associative in nature.
  • Universal gates are commutative in nature.

 

There are following two universal logic gates-

 

 

  1. NAND Gate
  2. NOR Gate

 

1. NAND Gate-

 

  • A NAND Gate is constructed by connecting a NOT Gate at the output terminal of the AND Gate.
  • The output of NAND gate is high (‘1’) if at least one of its inputs is low (‘0’).
  • The output of NAND gate is low (‘0’) if all of its inputs are high (‘1’).

 

Logic Symbol-

 

The logic symbol for NAND Gate is as shown below-

 

 

Truth Table-

 

The truth table for NAND Gate is as shown below-

 

A B Y = (A.B)’
0 0 1
0 1 1
1 0 1
1 1 0

Truth Table

 

Timing Diagram-

 

The timing diagram for NAND Gate is as shown below-

 

 

2. NOR Gate-

 

  • A NOR Gate is constructed by connecting a NOT Gate at the output terminal of the OR Gate.
  • The output of OR gate is high (‘1’) if all of its inputs are low (‘0’).
  • The output of OR gate is low (‘0’) if any of its inputs is high (‘1’).

 

Logic Symbol-

 

The logic symbol for NOR Gate is as shown below-

 

 

Truth Table-

 

The truth table for NOR Gate is as shown below-

 

A B Y = A + B
0 0 1
0 1 0
1 0 0
1 1 0

Truth Table

 

Timing Diagram-

 

The timing diagram for NOR Gate is as shown below-

 

 

To gain better understanding about Universal Logic Gates,

Watch this Video Lecture

 

Next Article- Alternative Logic Gates

 

Get more notes and other study material of Digital Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Logic Gates | Definitions | Types | Symbols | Truth Tables

Digital Design

Logic Gates-

 

Logic Gates may be defined as-

 

Logic gates are the digital circuits capable of performing a particular logic function

by operating on a number of binary inputs.

OR

Logic gates are the basic building blocks of any digital circuit.

 

Types Of Logic Gates-

 

Logic gates can be broadly classified as-

 

 

In this article, we will discuss about Basic Logic Gates.

 

Basic Logic Gates-

 

Basic Logic Gates are the fundamental logic gates using which universal logic gates and other logic gates are constructed.

 

They have the following properties-

  • Basic logic gates are associative in nature.
  • Basic logic gates are commutative in nature.

 

There are following three basic logic gates-

  1. AND Gate
  2. OR Gate
  3. NOT Gate

 

1. AND Gate-

 

  • The output of AND gate is high (‘1’) if all of its inputs are high (‘1’).
  • The output of AND gate is low (‘0’) if any one of its inputs is low (‘0’).

 

Logic Symbol-

 

The logic symbol for AND Gate is as shown below-

 

 

Truth Table-

 

The truth table for AND Gate is as shown below-

 

A B Y = A.B
0 0 0
0 1 0
1 0 0
1 1 1

Truth Table

 

Timing Diagram-

 

The timing diagram for AND Gate is as shown below-

 

 

2. OR Gate-

 

  • The output of OR gate is high (‘1’) if any one of its inputs is high (‘1’).
  • The output of OR gate is low (‘0’) if all of its inputs are low (‘0’).

 

Logic Symbol-

 

The logic symbol for OR Gate is as shown below-

 

 

Truth Table-

 

The truth table for OR Gate is as shown below-

 

A B Y = A + B
0 0 0
0 1 1
1 0 1
1 1 1

Truth Table

 

Timing Diagram-

 

The timing diagram for OR Gate is as shown below-

 

 

Also Read- Alternative Logic Gates

 

3. NOT Gate-

 

  • The output of NOT gate is high (‘1’) if its input is low (‘0’).
  • The output of NOT gate is low (‘0’) if its input is high (‘1’).

 

From here-

  • It is clear that NOT gate simply inverts the given input.
  • Since NOT gate simply inverts the given input, therefore it is also known as Inverter Gate.

 

Logic Symbol-

 

The logic symbol for NOT Gate is as shown below-

 

 

Truth Table-

 

The truth table for NOT Gate is as shown below-

 

A Y = A’
0 1
1 0

Truth Table

 

Timing Diagram-

 

The timing diagram for NOT Gate is as shown below-

 

 

To gain better understanding about Logic Gates,

Watch this Video Lecture

 

Next Article- Universal Logic Gates

 

Get more notes and other study material of Digital Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Delay in Ripple Carry Adder | Ripple Carry Adder

Digital Design

Ripple Carry Adder-

 

Before you go through this article, make sure that you have gone through the previous article on Ripple Carry Adder.

 

We have discussed-

  • Ripple Carry Adder is a combinational logic circuit.
  • It is used for the purpose of adding two n-bit binary numbers.
  • It is also called as n-bit parallel adder.

 

 

In this article, we will discuss about Delay in Ripple Carry Adder.

 

Delay in Ripple Carry Adder-

 

Consider a N-bit Ripple Carry Adder as shown-

 

 

The following kinds of problems may be asked based on delay calculation in Ripple Carry Adder.

 

Type-01 Problem:

 

  • You will be given the carry propagation delay and sum propagation delay of each full adder.
  • You will be asked to calculate the worst case delay of the ripple carry adder.

 

Solution-

 

Know These Terms?

 

It is important to know the following terms-

  • Carry propagation delay of a full adder is the time taken by it to produce the output carry bit.
  • Sum propagation delay of a full adder is the time taken by it to produce the output sum bit.
  • Worst case delay of a ripple carry adder is the time after which the output sum bit and carry bit becomes available from the last full adder.

 

In Ripple Carry Adder,

  • A full adder becomes active only when its carry in is made available by its adjacent less significant full adder.
  • When carry in becomes available to the full adder, it starts its operation.
  • It produces the corresponding output sum bit and carry bit.

 

If you are asked to calculate the time after which the output sum bit or carry bit becomes available from any particular full adder, then it is calculated as-

 

Time After Which Carry Bit Cx Becomes Available-

 

Required time

= Total number of full adders till full adder producing Cx X Carry propagation delay of full adder

 

Time After Which Sum Bit Sx Becomes Available-

 

Required time

= Time taken for its carry in to become available + Sum propagation delay of full adder

= { Total number of full adders before full adder producing Sx X Carry propagation delay of full adder } + Sum propagation delay of full adder

 

We will calculate worst case delay for the last full adder.

 

Also Read- Full Adder

 

Type-02 Problem:

 

  • You will be given the propagation delay of some basic logic gates.
  • You will be told how the full adder has been implemented.
  • Then, you will be asked to calculate the worst case delay of Ripple Carry Adder.

 

Suppose each full adder in the given ripple carry adder has been implemented as-

 

 

Solution-

 

  • The computation has to be done in the same manner as in Type-01 problem.
  • It’s just that in Type-02 problem, one step is increased.
  • We have to first calculate the carry propagation delay and sum propagation delay in terms of logic gates.
  • Then, our problem will reduce to Type-01 problem.

 

Let-

  • Propagation delay of AND gate = Tpd (AND)
  • Propagation delay of OR gate = Tpd (OR)
  • Propagation delay of XOR gate = Tpd (XOR)

 

Calculating Carry Propagation Delay-

 

  • We calculate the carry propagation delay of full adder using its carry generator logic circuit.
  • It has 2 levels in the given implementation.
  • At first level, three AND gates operate.
  • All the three AND gates operate in parallel.
  • So, we consider the propagation delay due to only one AND gate.
  • At second level, OR gate operates.

 

Now,

Carry propagation delay of full adder

= Time taken by it to generate the output carry bit

= Propagation delay of AND gate + Propagation delay of OR gate

= Tpd (AND) + Tpd (OR)

 

Calculating Sum Propagation Delay-

 

  • We calculate the sum propagation delay of full adder using its sum generator logic circuit.
  • It has only 1 level at which XOR gate operates in the given implementation.

 

Now,

Sum propagation delay of full adder

=  Time taken by it to generate the output sum bit

= Propagation delay of XOR gate

= Tpd (XOR)

 

Now,

  • We have got the carry propagation delay and sum propagation delay of full adders.
  • Our problem reduces to Type-01 problem.
  • We use the same formulas as we have learnt in Type-01 problem to make the required calculations.

 

NOTE-

 

Consider in the question,

  • It was said that while implementing the sum generator logic circuit of full adders, only 2-input XOR gates are used.
  • Then, in that case we would require two such XOR gates which would work at 2 levels.
  • So, in that case, sum propagation delay would be twice the propagation delay of XOR gate.

 

PRACTICE PROBLEMS BASED ON RIPPLE CARRY ADDER DELAY CALCULATION-

 

Problem-01:

 

A 16-bit ripple carry adder is realized using 16 identical full adders. The carry propagation delay of each full adder is 12 ns and the sum propagation delay of each full adder is 15 ns. The worst case delay of this 16 bit adder will be ______?

A) 195 ns

B) 220 ns

C) 250 ns

D) 300 ns

 

Solution-

 

We consider the last full adder for worst case delay.

 

Time after which output carry bit becomes available from the last full adder

= Total number of full adders X Carry propagation delay of full adder

= 16 x 12 ns

= 192 ns

 

Time after which output sum bit becomes available from the last full adder

= Time taken for its carry in to become available + Sum propagation delay of full adder

= { Total number of full adders before last full adder X Carry propagation delay of full adder } + Sum propagation delay of full adder

= { 15 x 12 ns } + 15 ns

= 195 ns

 

Thus, Option (A) is correct.

 

For more explanation, Watch this Video Solution.

 

Problem-02:

 

Following figure shows the implementation of full adders in a 16-bit ripple carry adder realized using 16 identical full adders. The propagation delay of the XOR, AND and OR gates are 20 ns, 15 ns and 10 ns respectively. The worst case delay of this 16 bit adder will be ______?

A) 395 ns

B) 220 ns

C) 400 ns

D) 300 ns

 

 

Solution-

 

We consider the last full adder for worst case delay.

 

Time after which output carry bit becomes available from the last full adder

= Total number of full adders X Carry propagation delay of full adder

= Total number of full adders X { Propagation delay of AND gate + Propagation delay of OR gate }

= 16 x { 15 ns + 10 ns }

= 16 x 25 ns

= 400 ns

 

Time after which output sum bit becomes available from the last full adder

= Time taken for its carry in to become available + Sum propagation delay of full adder

= { Total number of full adders before last full adder X Carry propagation delay of full adder } + Propagation delay of XOR gate

= { 15 x (15 ns + 10 ns) } + 20 ns

= 395 ns

 

Thus, Option (C) is correct.

 

To gain better understanding about Delay in Ripple Carry Adder,

Watch this Video Lecture

 

Next Article- Carry Look Ahead Adder

 

Get more notes and other study material of Digital Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Equivalence of Schedules | Equivalent Schedules in DBMS

Database Management System

Equivalence of Schedules-

 

In DBMS, schedules may have the following three different kinds of equivalence relations among them-

 

 

  1. Result Equivalence
  2. Conflict Equivalence
  3. View Equivalence

 

1. Result Equivalent Schedules-

 

  • If any two schedules generate the same result after their execution, then they are called as result equivalent schedules.
  • This equivalence relation is considered of least significance.
  • This is because some schedules might produce same results for some set of values and different results for some other set of values.

 

2. Conflict Equivalent Schedules-

 

If any two schedules satisfy the following two conditions, then they are called as conflict equivalent schedules-

  1. The set of transactions present in both the schedules is same.
  2. The order of pairs of conflicting operations of both the schedules is same.

 

3. View Equivalent Schedules-

 

We have already discussed about View Equivalent Schedules.

 

PRACTICE PROBLEMS BASED ON EQUIVALENCE OF SCHEDULES-

 

Problem-01:

 

Are the following three schedules result equivalent?

 

 

Solution-

 

To check whether the given schedules are result equivalent or not,

  • We will consider some arbitrary values of X and Y.
  • Then, we will compare the results produced by each schedule.
  • Those schedules which produce the same results will be result equivalent.

 

Let X = 2 and Y = 5.

On substituting these values, the results produced by each schedule are-

 

Results by Schedule S1- X = 21 and Y = 10

Results by Schedule S2- X = 21 and Y = 10

Results by Schedule S3- X = 11 and Y = 10

 

  • Clearly, the results produced by schedules S1 and S2 are same.
  • Thus, we conclude that S1 and S2 are result equivalent schedules.

 

Problem-02:

 

Are the following two schedules conflict equivalent?

 

 

Solution-

 

To check whether the given schedules are conflict equivalent or not,

  • We will write their order of pairs of conflicting operations.
  • Then, we will compare the order of both the schedules.
  • If both the schedules are found to have the same order, then they will be conflict equivalent.

 

For schedule S1-

 

The required order is-

  • R1(A) , W2(A)
  • W1(A) , R2(A)
  • W1(A) , W2(A)

 

For schedule S2-

 

The required order is-

  • R1(A) , W2(A)
  • W1(A) , R2(A)
  • W1(A) , W2(A)

 

  • Clearly, both the given schedules have the same order.
  • Thus, we conclude that S1 and S2 are conflict equivalent schedules.

 

Next Article- Introduction to Relational Algebra

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.