dbms | Gate Vidyalay

Tag: dbms

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.

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-

Result Equivalence
Conflict Equivalence
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-

The set of transactions present in both the schedules is same.
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-

R₁(A) , W₂(A)
W₁(A) , R₂(A)
W₁(A) , W₂(A)

For schedule S2-

The required order is-

R₁(A) , W₂(A)
W₁(A) , R₂(A)
W₁(A) , W₂(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

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-

W₁(B) , W₂(B) (T₁ → T₂)
W₁(B) , W₃(B) (T₁ → T₃)
W₁(B) , W₄(B) (T₁ → T₄)
W₂(B) , W₃(B) (T₂ → T₃)
W₂(B) , W₄(B) (T₂ → T₄)
W₃(B) , W₄(B) (T₃ → T₄)

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-

R₁(A) , W₃(A) (T₁ → T₃)
R₂(A) , W₃(A) (T₂ → T₃)
R₂(A) , W₁(A) (T₂ → T₁)
W₃(A) , W₁(A) (T₃ → T₁)

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-

R₁(A) , W₂(A) (T₁ → T₂)
R₂(A) , W₁(A) (T₂ → T₁)
W₁(A) , W₂(A) (T₁ → T₂)
R₁(B) , W₂(B) (T₁ → T₂)
R₂(B) , W₁(B) (T₂ → T₁)

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 : R₁(A) , W₂(A) , R₃(A) , W₁(A) , W₃(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-

R₁(A) , W₂(A) (T₁ → T₂)
R₁(A) , W₃(A) (T₁ → T₃)
W₂(A) , R₃(A) (T₂ → T₃)
W₂(A) , W₁(A) (T₂ → T₁)
W₂(A) , W₃(A) (T₂ → T₃)
R₃(A) , W₁(A) (T₃ → T₁)
W₁(A) , W₃(A) (T₁ → T₃)

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

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-

Cascading Schedule
Cascadeless Schedule
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.

← Older Posts

Newer Posts →