Category: Subjects

Serializability in DBMS | Conflict Serializability

Database Management System

Schedules in DBMS-

 

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

 

We have discussed-

  • A schedule is the order in which the operations of multiple transactions appear for execution.
  • Serial schedules are always consistent.
  • Non-serial schedules are not always consistent.

 

In DBMS, schedules may be classified as-

 

 

In this article, we will discuss about Serializability in DBMS.

 

Serializability in DBMS-

 

  • Some non-serial schedules may lead to inconsistency of the database.
  • Serializability is a concept that helps to identify which non-serial schedules are correct and will maintain the consistency of the database.

 

Serializable Schedules-

 

If a given non-serial schedule of ‘n’ transactions is equivalent to some serial schedule of ‘n’ transactions, then it is called as a serializable schedule.

 

Characteristics-

 

Serializable schedules behave exactly same as serial schedules.

Thus, serializable schedules are always-

 

Serial Schedules Vs Serializable Schedules-

 

Serial Schedules Serializable Schedules
No concurrency is allowed.

Thus, all the transactions necessarily execute serially one after the other.

 Concurrency is allowed.

Thus, multiple transactions can execute concurrently.
Serial schedules lead to less resource utilization and CPU throughput. Serializable schedules improve both resource utilization and CPU throughput.
Serial Schedules are less efficient as compared to serializable schedules.

(due to above reason)

 Serializable Schedules are always better than serial schedules.

(due to above reason)

 

Types of Serializability-

 

Serializability is mainly of two types-

 

 

  1. Conflict Serializability
  2. View Serializability

 

In this article, we will discuss about Conflict Serializability.

Learn about View Serializability.

 

Conflict Serializability-

 

If a given non-serial schedule can be converted into a serial schedule by swapping its non-conflicting operations, then it is called as a conflict serializable schedule.

 

Conflicting Operations-

 

Two operations are called as conflicting operations if all the following conditions hold true for them-

  • Both the operations belong to different transactions
  • Both the operations are on the same data item
  • At least one of the two operations is a write operation

 

Example-

 

Consider the following schedule-

 

 

In this schedule,

  • W1 (A) and R2 (A) are called as conflicting operations.
  • This is because all the above conditions hold true for them.

 

Checking Whether a Schedule is Conflict Serializable Or Not-

 

Follow the following steps to check whether a given non-serial schedule is conflict serializable or not-

 

Step-01:

 

Find and list all the conflicting operations.

 

Step-02:

 

Start creating a precedence graph by drawing one node for each transaction.

 

Step-03:

 

  • Draw an edge for each conflict pair such that if Xi (V) and Yj (V) forms a conflict pair then draw an edge from Ti to Tj.
  • This ensures that Ti gets executed before Tj.

 

Step-04:

 

  • Check if there is any cycle formed in the graph.
  • If there is no cycle found, then the schedule is conflict serializable otherwise not.

 

NOTE-

 

 

Next Article- Practice Problems On Conflict Serializability

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.

Job Sequencing With Deadlines | Algorithm | Example

Design & Analysis of Algorithms

Job Sequencing With Deadlines-

 

The sequencing of jobs on a single processor with deadline constraints is called as Job Sequencing with Deadlines.

 

Here-

  • You are given a set of jobs.
  • Each job has a defined deadline and some profit associated with it.
  • The profit of a job is given only when that job is completed within its deadline.
  • Only one processor is available for processing all the jobs.
  • Processor takes one unit of time to complete a job.

 

The problem states-

“How can the total profit be maximized if only one job can be completed at a time?”

 

Approach to Solution-

 

  • A feasible solution would be a subset of jobs where each job of the subset gets completed within its deadline.
  • Value of the feasible solution would be the sum of profit of all the jobs contained in the subset.
  • An optimal solution of the problem would be a feasible solution which gives the maximum profit.

 

Greedy Algorithm-

 

Greedy Algorithm is adopted to determine how the next job is selected for an optimal solution.

The greedy algorithm described below always gives an optimal solution to the job sequencing problem-

 

Step-01:

 

  • Sort all the given jobs in decreasing order of their profit.

 

Step-02:

 

  • Check the value of maximum deadline.
  • Draw a Gantt chart where maximum time on Gantt chart is the value of maximum deadline.

 

Step-03:

 

  • Pick up the jobs one by one.
  • Put the job on Gantt chart as far as possible from 0 ensuring that the job gets completed before its deadline.

 

PRACTICE PROBLEM BASED ON JOB SEQUENCING WITH DEADLINES-

 

Problem-

 

Given the jobs, their deadlines and associated profits as shown-

 

Jobs J1 J2 J3 J4 J5 J6
Deadlines 5 3 3 2 4 2
Profits 200 180 190 300 120 100

 

Answer the following questions-

  1. Write the optimal schedule that gives maximum profit.
  2. Are all the jobs completed in the optimal schedule?
  3. What is the maximum earned profit?

 

Solution-

 

Step-01:

 

Sort all the given jobs in decreasing order of their profit-

 

Jobs J4 J1 J3 J2 J5 J6
Deadlines 2 5 3 3 4 2
Profits 300 200 190 180 120 100

 

Step-02:

 

Value of maximum deadline = 5.

So, draw a Gantt chart with maximum time on Gantt chart = 5 units as shown-

 

 

Now,

  • We take each job one by one in the order they appear in Step-01.
  • We place the job on Gantt chart as far as possible from 0.

 

Step-03:

 

  • We take job J4.
  • Since its deadline is 2, so we place it in the first empty cell before deadline 2 as-

 

 

Step-04:

 

  • We take job J1.
  • Since its deadline is 5, so we place it in the first empty cell before deadline 5 as-

 

 

Step-05:

 

  • We take job J3.
  • Since its deadline is 3, so we place it in the first empty cell before deadline 3 as-

 

 

Step-06:

 

  • We take job J2.
  • Since its deadline is 3, so we place it in the first empty cell before deadline 3.
  • Since the second and third cells are already filled, so we place job J2 in the first cell as-

 

 

Step-07:

 

  • Now, we take job J5.
  • Since its deadline is 4, so we place it in the first empty cell before deadline 4 as-

 

 

Now,

  • The only job left is job J6 whose deadline is 2.
  • All the slots before deadline 2 are already occupied.
  • Thus, job J6 can not be completed.

 

Now, the given questions may be answered as-

 

Part-01:

 

The optimal schedule is-

J2  , J4 , J3 , J5 , J1

This is the required order in which the jobs must be completed in order to obtain the maximum profit.

 

Part-02:

 

  • All the jobs are not completed in optimal schedule.
  • This is because job J6 could not be completed within its deadline.

 

Part-03:

 

Maximum earned profit

= Sum of profit of all the jobs in optimal schedule

= Profit of job J2 + Profit of job J4 + Profit of job J3 + Profit of job J5 + Profit of job J1

= 180 + 300 + 190 + 120 + 200

= 990 units

 

To gain better understanding about Job Sequencing With Deadlines,

Watch this Video Lecture

 

Next Article- Huffman Coding

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

JK Flip Flop | Diagram | Truth Table | Excitation Table

Digital Design

Flip Flops-

 

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

 

We have discussed-

  • A Flip Flop is a memory element that is capable of storing one bit of information.
  • It is also called as Bistable Multivibrator since it has two stable states either 0 or 1.

 

There are following 4 basic types of flip flops-

 

 

  1. SR Flip Flop
  2. JK Flip Flop
  3. D Flip Flop
  4. T Flip Flop

 

In this article, we will discuss about JK Flip Flop.

 

JK Flip Flop-

 

JK flip flop is a refined & improved version of SR Flip Flop

that has been introduced to solve the problem of indeterminate state

that occurs in SR flip flop when both the inputs are 1.

 

In JK flip flop,

  • Input J behaves like input S of SR flip flop which was meant to set the flip flop.
  • Input K behaves like input R of SR flip flop which was meant to reset the flip flop.

 

Construction of JK Flip Flop-

 

There are following two methods for constructing a JK flip flop-

 

 

  1. By using SR flip flop constructed from NOR latch
  2. By using SR flip flop constructed from NAND latch

 

1. Construction of JK Flip Flop By Using SR Flip Flop Constructed From NOR Latch-

 

This method of constructing JK Flip Flop uses-

  • SR Flip Flop constructed from NOR latch
  • Two other connections

 

Logic Circuit-

 

The logic circuit for JK Flip Flop constructed using SR Flip Flop constructed from NOR latch is as shown below-

 

 

2. Construction of JK Flip Flop By Using SR Flip Flop Constructed From NAND Latch-

 

This method of constructing JK Flip Flop uses-

  • SR Flip Flop constructed from NAND latch
  • Two other connections

 

Logic Circuit-

 

The logic circuit for JK Flip Flop constructed using SR Flip Flop constructed from NAND latch is as shown below-

 

 

Logic Symbol-

 

The logic symbol for JK Flip Flop is as shown below-

 

 

Truth Table-

 

The truth table for JK Flip Flop is as shown below-

 

INPUTS OUTPUTS
J K Qn

(Present State)

 Qn+1

(Next State)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0

Truth Table

 

The above truth table may be reduced as-

 

INPUTS OUTPUTS REMARKS
J K Qn

(Present State)

 Qn+1

(Next State)

 States and Conditions
0 0 X Qn Hold State condition J = K = 0
0 1 X 0 Reset state condition J = 0 , K = 1
1 0 X 1 Set state condition J = 1 , K = 0
1 1 X Q’n Toggle state condition J = K = 1

Truth Table

 

Characteristic Equation-

 

Draw a k map using the above truth table-

 

 

From here-

Qn+1 = Q’n (JK + JK’) + Qn (J’K’ + JK’)

 

Qn+1 = Q’nJ + QnK’

 

Excitation Table-

 

The excitation table of any flip flop is drawn using its truth table.

 

What is excitation table?

For a given combination of present state Qn and next state Qn+1, excitation table tell the inputs required.

 

Qn Qn+1 S R
0 0 0 X
0 1 1 X
1 0 X 1
1 1 X 0

Excitation Table

 

SR Flip Flop Vs JK Flip Flop-

 

Both JK flip flop and SR flip flop are functionally same.

The only difference between them is-

  • In JK flip flop, indeterminate state does not occur.
  • In JK flip flop, instead of indeterminate state, the present state toggles.
  • In other words, the present state gets inverted when both the inputs are 1.

 

To gain better understanding about JK Flip Flop,

Watch this Video Lecture

 

Next Article- Half Adder

 

Get more notes and other study material of Digital Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

SR Flip Flop | Diagram | Truth Table | Excitation Table

Digital Design

Flip Flops-

 

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

 

We have discussed-

  • A Flip Flop is a memory element that is capable of storing one bit of information.
  • It is also called as Bistable Multivibrator since it has two stable states either 0 or 1.

 

There are following 4 basic types of flip flops-

 

 

  1. SR Flip Flop
  2. JK Flip Flop
  3. D Flip Flop
  4. T Flip Flop

 

In this article, we will discuss about SR Flip Flop.

 

SR Flip Flop-

 

  • SR flip flop is the simplest type of flip flops.
  • It stands for Set Reset flip flop.
  • It is a clocked flip flop.

 

Construction of SR Flip Flop-

 

There are following two methods for constructing a SR flip flop-

 

 

  1. By using NOR latch
  2. By using NAND latch

 

1. Construction of SR Flip Flop By Using NOR Latch-

 

This method of constructing SR Flip Flop uses-

  • NOR latch
  • Two AND gates

 

Logic Circuit-

 

The logic circuit for SR Flip Flop constructed using NOR latch is as shown below-

 

 

2. Construction of SR Flip Flop By Using NAND Latch-

 

This method of constructing SR Flip Flop uses-

  • NAND latch
  • Two NAND gates

 

Logic Circuit-

 

The logic circuit for SR Flip Flop constructed using NAND latch is as shown below-

 

 

Logic Symbol-

 

The logic symbol for SR Flip Flop is as shown below-

 

 

Truth Table-

 

The truth table for SR Flip Flop is as shown below-

 

INPUTS OUTPUTS
S R Qn

(Present State)

 Qn+1

(Next State)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 Indeterminate
1 1 1 Indeterminate

Truth Table

 

The above truth table may be reduced as-

 

INPUTS OUTPUTS REMARKS
S R Qn

(Present State)

 Qn+1

(Next State)

 States and Conditions
0 0 X Qn Hold State condition S = R = 0
0 1 X 0 Reset state condition S = 0 , R = 1
1 0 X 1 Set state condition S = 1 , R = 0
1 1 X Indeterminate Indeterminate state condition S = R = 1

Truth Table

 

Characteristic Equation-

 

Draw a k map using the above truth table-

 

 

From here-

Qn+1 = ( SR + SR’ ) ( Qn +  Q’n ) + Qn ( S’R’ + SR’ )

 

Qn+1 = S + QnR’

 

Excitation Table-

 

The excitation table of any flip flop is drawn using its truth table.

 

What is excitation table?

For a given combination of present state Qn and next state Qn+1, excitation table tell the inputs required.

 

Qn Qn+1 S R
0 0 0 X
0 1 1 0
1 0 0 1
1 1 X 0

Excitation Table

 

To gain better understanding about SR Flip Flop,

Watch this Video Lecture

 

Next Article- JK Flip Flop

 

Get more notes and other study material of Digital Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Flip Flops in Digital Logic | Flip Flops Types

Digital Design

Flip Flop-

 

A Flip Flop is a memory element that is capable of storing one bit of information.

 

A flip flop has two outputs as shown-

 

 

A flip flop can maintain a binary state for an unlimited period of time as long as-

  • Power is supplied to the circuit.
  • Or until it is directed by an input signal to switch states.

 

A flip flop is also called as Bistable Multivibrator because it has two stable states either 0 or 1.

 

Flip Flops Types-

 

Flip flops are of different types depending on how their inputs and clock pulses cause transition between two states.

There are 4 basic types of flip flops-

 

 

  1. SR Flip Flop
  2. JK Flip Flop
  3. D Flip Flop
  4. T Flip Flop

 

We will discuss about these flip flops one by one.

 

To gain better understanding about Flip Flops in Digital Logic,

Watch this Video Lecture

 

Next Article- SR Flip Flop

 

Get more notes and other study material of Digital Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.