Category: Subjects

View Serializability in DBMS | Practice Problems

Database Management System

View Serializability-

 

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

 

We have discussed-

  • The concept of serializability helps to identify the correct non-serial schedules that will maintain the consistency of the database.
  • There are two types of serializability-

 

 

In this article, we will discuss practice problems based on view serializability.

 

Also read- Conflict Serializability

 

PRACTICE PROBLEMS BASED ON VIEW SERIALIZABILITY-

 

Problem-01:

 

Check whether the given schedule S is view serializable or not-

 

 

Solution-

 

  • We know, if a schedule is conflict serializable, then it is surely view serializable.
  • So, let us check whether the given schedule is conflict serializable or not.

 

Checking Whether S is Conflict Serializable Or Not-

 

Step-01:

 

List all the conflicting operations and determine the dependency between the transactions-

  • W1(B) , W2(B)              (T1 → T2)
  • W1(B) , W3(B)              (T1 → T3)
  • W1(B) , W4(B)              (T1 → T4)
  • W2(B) , W3(B)              (T2 → T3)
  • W2(B) , W4(B)              (T2 → T4)
  • W3(B) , W4(B)              (T3 → T4)

 

Step-02:

 

Draw the precedence graph-

 

 

  • Clearly, there exists no cycle in the precedence graph.
  • Therefore, the given schedule S is conflict serializable.
  • Thus, we conclude that the given schedule is also view serializable.

 

Problem-02:

 

Check whether the given schedule S is view serializable or not-

 

 

Solution-

 

  • We know, if a schedule is conflict serializable, then it is surely view serializable.
  • So, let us check whether the given schedule is conflict serializable or not.

 

Checking Whether S is Conflict Serializable Or Not-

 

Step-01:

 

List all the conflicting operations and determine the dependency between the transactions-

  • R1(A) , W3(A)              (T1 → T3)
  • R2(A) , W3(A)              (T2 → T3)
  • R2(A) , W1(A)              (T2 → T1)
  • W3(A) , W1(A)             (T3 → T1)

 

Step-02:

 

Draw the precedence graph-

 

 

  • Clearly, there exists a cycle in the precedence graph.
  • Therefore, the given schedule S is not conflict serializable.

 

Now,

  • Since, the given schedule S is not conflict serializable, so, it may or may not be view serializable.
  • To check whether S is view serializable or not, let us use another method.
  • Let us check for blind writes.

 

Checking for Blind Writes-

 

  • There exists a blind write W3 (A) in the given schedule S.
  • Therefore, the given schedule S may or may not be view serializable.

 

Now,

  • To check whether S is view serializable or not, let us use another method.
  • Let us derive the dependencies and then draw a dependency graph.

 

Drawing a Dependency Graph-

 

  • T1 firstly reads A and T3 firstly updates A.
  • So, T1 must execute before T3.
  • Thus, we get the dependency T1 → T3.
  • Final updation on A is made by the transaction T1.
  • So, T1 must execute after all other transactions.
  • Thus, we get the dependency (T2, T3) → T1.
  • There exists no write-read sequence.

 

Now, let us draw a dependency graph using these dependencies-

 

 

  • Clearly, there exists a cycle in the dependency graph.
  • Thus, we conclude that the given schedule S is not view serializable.

 

Problem-03:

 

Check whether the given schedule S is view serializable or not-

 

 

Solution-

 

  • We know, if a schedule is conflict serializable, then it is surely view serializable.
  • So, let us check whether the given schedule is conflict serializable or not.

 

Checking Whether S is Conflict Serializable Or Not-

 

Step-01:

 

List all the conflicting operations and determine the dependency between the transactions-

  • R1(A) , W2(A)              (T1 → T2)
  • R2(A) , W1(A)              (T2 → T1)
  • W1(A) , W2(A)             (T1 → T2)
  • R1(B) , W2(B)              (T1 → T2)
  • R2(B) , W1(B)              (T2 → T1)

 

Step-02:

 

Draw the precedence graph-

 

 

  • Clearly, there exists a cycle in the precedence graph.
  • Therefore, the given schedule S is not conflict serializable.

 

Now,

  • Since, the given schedule S is not conflict serializable, so, it may or may not be view serializable.
  • To check whether S is view serializable or not, let us use another method.
  • Let us check for blind writes.

 

Checking for Blind Writes-

 

  • There exists no blind write in the given schedule S.
  • Therefore, it is surely not view serializable.

 

Alternatively,

  • You could directly declare that the given schedule S is not view serializable.
  • This is because there exists no blind write in the schedule.
  • You need not check for conflict serializability.

 

Problem-04:

 

Check whether the given schedule S is view serializable or not. If yes, then give the serial schedule.

S : R1(A) , W2(A) , R3(A) , W1(A) , W3(A)

 

Solution-

 

For simplicity and better understanding, we can represent the given schedule pictorially as-

 

 

  • We know, if a schedule is conflict serializable, then it is surely view serializable.
  • So, let us check whether the given schedule is conflict serializable or not.

 

Checking Whether S is Conflict Serializable Or Not-

 

Step-01:

 

List all the conflicting operations and determine the dependency between the transactions-

  • R1(A) , W2(A)              (T1 → T2)
  • R1(A) , W3(A)              (T1 → T3)
  • W2(A) , R3(A)              (T2 → T3)
  • W2(A) , W1(A)             (T2 → T1)
  • W2(A) , W3(A)             (T2 → T3)
  • R3(A) , W1(A)              (T3 → T1)
  • W1(A) , W3(A)             (T1 → T3)

 

Step-02:

 

Draw the precedence graph-

 

 

  • Clearly, there exists a cycle in the precedence graph.
  • Therefore, the given schedule S is not conflict serializable.

 

Now,

  • Since, the given schedule S is not conflict serializable, so, it may or may not be view serializable.
  • To check whether S is view serializable or not, let us use another method.
  • Let us check for blind writes.

 

Checking for Blind Writes-

 

  • There exists a blind write W2 (A) in the given schedule S.
  • Therefore, the given schedule S may or may not be view serializable.

 

Now,

  • To check whether S is view serializable or not, let us use another method.
  • Let us derive the dependencies and then draw a dependency graph.

 

Drawing a Dependency Graph-

 

  • T1 firstly reads A and T2 firstly updates A.
  • So, T1 must execute before T2.
  • Thus, we get the dependency T1 → T2.
  • Final updation on A is made by the transaction T3.
  • So, T3 must execute after all other transactions.
  • Thus, we get the dependency (T1, T2) → T3.
  • From write-read sequence, we get  the dependency T2 → T3

 

Now, let us draw a dependency graph using these dependencies-

 

 

  • Clearly, there exists no cycle in the dependency graph.
  • Therefore, the given schedule S is view serializable.
  • The serialization order T1 → T2 → T3.

 

Next Article- Recoverable and Irrecoverable Schedules

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.

Cascading Rollback | Cascadeless Schedule

Database Management System

Recoverability-

 

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

 

We have discussed-

  • Non-serial schedules which are not serializable are called as non-serializable schedules.
  • Non-serializable schedules may be recoverable or irrecoverable.

 

Recoverable Schedules-

 

If in a schedule,

  • A transaction performs a dirty read operation from an uncommitted transaction
  • And its commit operation is delayed till the uncommitted transaction either commits or roll backs

then such a schedule is called as a Recoverable Schedule.

 

Types of Recoverable Schedules-

 

A recoverable schedule may be any one of these kinds-

 

 

  1. Cascading Schedule
  2. Cascadeless Schedule
  3. Strict Schedule

 

Cascading Schedule-

 

  • If in a schedule, failure of one transaction causes several other dependent transactions to rollback or abort, then such a schedule is called as a Cascading Schedule or Cascading Rollback or Cascading Abort.
  • It simply leads to the wastage of CPU time.

 

Example-

 

 

Here,

  • Transaction T2 depends on transaction T1.
  • Transaction T3 depends on transaction T2.
  • Transaction T4 depends on transaction T3.

 

In this schedule,

  • The failure of transaction T1 causes the transaction T2 to rollback.
  • The rollback of transaction T2 causes the transaction T3 to rollback.
  • The rollback of transaction T3 causes the transaction T4 to rollback.

Such a rollback is called as a Cascading Rollback.

 

NOTE-

 

If the transactions T2, T3 and T4 would have committed before the failure of transaction T1, then the schedule would have been irrecoverable.

 

Cascadeless Schedule-

 

If in a schedule, a transaction is not allowed to read a data item until the last transaction that has written it is committed or aborted, then such a schedule is called as a Cascadeless Schedule.

In other words,

  • Cascadeless schedule allows only committed read operations.
  • Therefore, it avoids cascading roll back and thus saves CPU time.

 

Example-

 

 

NOTE-

 

  • Cascadeless schedule allows only committed read operations.
  • However, it allows uncommitted write operations.

 

Example-

 

 

Strict Schedule-

 

If in a schedule, a transaction is neither allowed to read nor write a data item until the last transaction that has written it is committed or aborted, then such a schedule is called as a Strict Schedule.

In other words,

  • Strict schedule allows only committed read and write operations.
  • Clearly, strict schedule implements more restrictions than cascadeless schedule.

 

Example-

 

 

Remember-

 

  • Strict schedules are more strict than cascadeless schedules.
  • All strict schedules are cascadeless schedules.
  • All cascadeless schedules are not strict schedules.

 

 

Next Article- Equivalence of Schedules

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.

ACID Properties | ACID Properties in DBMS

Database Management System

Transaction in DBMS-

 

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

 

We have discussed-

  • A transaction is a set of logically related operations.
  • A transaction goes through different states throughout its life cycle.
  • The life cycle of a transaction is-

 

 

In this article, we will discuss ACID properties of a transaction.

 

ACID Properties-

 

  • It is important to ensure that the database remains consistent before and after the transaction.
  • To ensure the consistency of database, certain properties are followed by all the transactions occurring in the system.
  • These properties are called as ACID Properties of a transaction.

 

 

1. Atomicity-

 

  • This property ensures that either the transaction occurs completely or it does not occur at all.
  • In other words, it ensures that no transaction occurs partially.
  • That is why, it is also referred to as “All or nothing rule“.
  • It is the responsibility of Transaction Control Manager to ensure atomicity of the transactions.

 

2. Consistency-

 

  • This property ensures that integrity constraints are maintained.
  • In other words, it ensures that the database remains consistent before and after the transaction.
  • It is the responsibility of DBMS and application programmer to ensure consistency of the database.

 

3. Isolation-

 

  • This property ensures that multiple transactions can occur simultaneously without causing any inconsistency.
  • During execution, each transaction feels as if it is getting executed alone in the system.
  • A transaction does not realize that there are other transactions as well getting executed parallely.
  • Changes made by a transaction becomes visible to other transactions only after they are written in the memory.
  • The resultant state of the system after executing all the transactions is same as the state that would be achieved if the transactions were executed serially one after the other.
  • It is the responsibility of concurrency control manager to ensure isolation for all the transactions.

 

4. Durability-

 

  • This property ensures that all the changes made by a transaction after its successful execution are written successfully to the disk.
  • It also ensures that these changes exist permanently and are never lost even if there occurs a failure of any kind.
  • It is the responsibility of recovery manager to ensure durability in the database.

 

Next Article- Concurrency Problems in DBMS

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.

Ripple Carry Adder | 4 bit Ripple Carry Adder

Digital Design

Ripple Carry Adder-

 

  • Ripple Carry Adder is a combinational logic circuit.
  • It is used for the purpose of adding two n-bit binary numbers.
  • It requires n full adders in its circuit for adding two n-bit binary numbers.
  • It is also known as n-bit parallel adder.

 

4-bit Ripple Carry Adder-

 

4-bit ripple carry adder is used for the purpose of adding two 4-bit binary numbers.

 

In Mathematics, any two 4-bit binary numbers A3A2A1A0 and B3B2B1B0 are added as shown below-

 

 

Using ripple carry adder, this addition is carried out as shown by the following logic diagram-

 

 

As shown-

  • Ripple Carry Adder works in different stages.
  • Each full adder takes the carry-in as input and produces carry-out and sum bit as output.
  • The carry-out produced by a full adder serves as carry-in for its adjacent most significant full adder.
  • When carry-in becomes available to the full adder, it activates the full adder.
  • After full adder becomes activated, it comes into operation.

 

Also Read- Full Adder Working

 

Working Of 4-bit Ripple Carry Adder-

 

Let-

  • The two 4-bit numbers are 0101 (A3A2A1A0) and 1010 (B3B2B1B0).
  • These numbers are to be added using a 4-bit ripple carry adder.

 

4-bit Ripple Carry Adder carries out the addition as explained in the following stages-

 

Stage-01:

 

  • When Cin is fed as input to the full Adder A, it activates the full adder A.
  • Then at full adder A, A0 = 1, B0 = 0, Cin = 0.

 

Full adder A computes the sum bit and carry bit as-

 

Calculation of S0–

 

S0 = A0 ⊕  B0 ⊕ Cin

S0 = 1 ⊕ 0 ⊕ 0

S0 = 1

 

Calculation of C0–

 

C0 = A0B0 ⊕  B0Cin ⊕ CinA0

C0 = 1.0 ⊕ 0.0 ⊕ 0.1

C0 = 0 ⊕ 0 ⊕ 0

C0 = 0

 

Stage-02:

 

  • When C0 is fed as input to the full adder B, it activates the full adder B.
  • Then at full adder B, A1 = 0, B1 = 1, C0 = 0.

 

Full adder B computes the sum bit and carry bit as-

 

Calculation of S1–

 

S1 = A1 ⊕  B1 ⊕ C0

S1 = 0 ⊕ 1 ⊕ 0

S1 = 1

 

Calculation of C1–

 

C1 = A1B1 ⊕  B1C0 ⊕ C0A1

C1 = 0.1 ⊕ 1.0 ⊕ 0.0

C1 = 0 ⊕ 0 ⊕ 0

C1 = 0

 

Stage-03:

 

  • When C1 is fed as input to the full adder C, it activates the full adder C.
  • Then at full adder C, A2 = 1, B2 = 0, C1 = 0.

 

Full adder C computes the sum bit and carry bit as-

 

Calculation of S2–

 

S2 = A2 ⊕  B2 ⊕ C1

S2 = 1 ⊕ 0 ⊕ 0

S2 = 1

 

Calculation of C2–

 

C2 = A2B2 ⊕  B2C1 ⊕ C1A2

C2 = 1.0 ⊕ 0.0 ⊕ 0.1

C2 = 0 ⊕ 0 ⊕ 0

C2 = 0

 

Stage-04:

 

  • When C2 is fed as input to the full adder D, it activates the full adder D.
  • Then at full adder D, A3 = 0, B3 = 1, C2 = 0.

 

Full adder D computes the sum bit and carry bit as-

 

Calculation of S3–

 

S3 = A3 ⊕  B3 ⊕ C2

S3 = 0 ⊕ 1 ⊕ 0

S3 = 1

 

Calculation of C3–

 

C3 = A3B3 ⊕  B3C2 ⊕ C2A3

C3 = 0.1 ⊕ 1.0 ⊕ 0.0

C3 = 0 ⊕ 0 ⊕ 0

C3 = 0

 

Thus finally,

  • Output Sum = S3S2S1S0 = 1111
  • Output Carry = C3 = 0

 

Why Ripple Carry Adder is Called So?

 

In Ripple Carry Adder,

  • The carry out produced by each full adder serves as carry-in for its adjacent most significant full adder.
  • Each carry bit ripples or waves into the next stage.
  • That’s why, it is called as “Ripple Carry Adder”.

 

Disadvantages of Ripple Carry Adder-

 

  • Ripple Carry Adder does not allow to use all the full adders simultaneously.
  • Each full adder has to necessarily wait until the carry bit becomes available from its adjacent full adder.
  • This increases the propagation time.
  • Due to this reason, ripple carry adder becomes extremely slow.
  • This is considered to be the biggest disadvantage of using ripple carry adder.

 

To overcome this disadvantage, Carry Look Ahead Adder comes into play.

 

To gain better understanding about Ripple Carry Adder,

Watch this Video Lecture

 

Next Article- Delay in Ripple Carry Adder

 

Get more notes and other study material of Digital Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Full Subtractor | Definition | Circuit Diagram | Truth Table

Digital Design

Half Subtractor-

 

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

 

We have discussed-

  • Half Subtractor is used for the purpose of subtracting two single bit numbers.
  • Half subtractors have no scope of taking into account “Borrow-in” from the previous circuit.
  • To overcome this drawback, full subtractor comes into play.

 

 

In this article, we will discuss about Full Subtractor.

 

Full Subtractor-

 

  • Full Subtractor is a combinational logic circuit.
  • It is used for the purpose of subtracting two single bit numbers.
  • It also takes into consideration borrow of the lower significant stage.
  • Thus, full subtractor has the ability to perform the subtraction of three bits.
  • Full subtractor contains 3 inputs and 2 outputs (Difference and Borrow) as shown-

 

 

Designing a Full Subtractor-

 

Full subtractor is designed in the following steps-

 

Step-01:

 

Identify the input and output variables-

  • Input variables = A, B, Bin (either 0 or 1)
  • Output variables = D, Bout where D = Difference and Bout = Borrow

 

Step-02:

 

Draw the truth table-

 

Inputs
 Outputs
A B Bin Bout (Borrow) D (Difference)
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 1 0
1 0 0 0 1
1 0 1 0 0
1 1 0 0 0
1 1 1 1 1

Truth Table

 

Step-03:

 

Draw K-maps using the above truth table and determine the simplified Boolean expressions-

 

 

Also Read- Full Adder

 

Step-04:

 

Draw the logic diagram.

The implementation of full adder using 1 XOR gate, 3 AND gates, 1 NOT gate and 1 OR gate is as shown below-

 

 

To gain better understanding about Full Subtractor,

Watch this Video Lecture

 

Next Article- Ripple Carry Adder

 

Get more notes and other study material of Digital Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.