Category: Database Management System

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. 

 

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.

Equivalence of Schedules | Equivalent Schedules in DBMS

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.

View Serializability in DBMS | Practice Problems

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 W(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 W(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

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

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.