Database Management System | Gate Vidyalay

Category: Database Management System

Functional Dependency in DBMS

Database Management System

Functional Dependency-

In any relation, a functional dependency α → β holds if-

Two tuples having same value of attribute α also have same value for attribute β.

Mathematically,

If α and β are the two sets of attributes in a relational table R where-

α ⊆ R
β ⊆ R

Then, for a functional dependency to exist from α to β,

If t1[α] = t2[α], then t1[β] = t2[β]

α	β
t1[α]	t1[β]
t2[α]	t2[β]
…….	…….

f_d : α → β

Types Of Functional Dependencies-

There are two types of functional dependencies-

Trivial Functional Dependencies
Non-trivial Functional Dependencies

1. Trivial Functional Dependencies-

A functional dependency X → Y is said to be trivial if and only if Y ⊆ X.
Thus, if RHS of a functional dependency is a subset of LHS, then it is called as a trivial functional dependency.

Examples-

The examples of trivial functional dependencies are-

AB → A
AB → B
AB → AB

2. Non-Trivial Functional Dependencies-

A functional dependency X → Y is said to be non-trivial if and only if Y ⊄ X.
Thus, if there exists at least one attribute in the RHS of a functional dependency that is not a part of LHS, then it is called as a non-trivial functional dependency.

Examples-

The examples of non-trivial functional dependencies are-

AB → BC
AB → CD

Inference Rules-

Reflexivity-

If B is a subset of A, then A → B always holds.

Transitivity-

If A → B and B → C, then A → C always holds.

Augmentation-

If A → B, then AC → BC always holds.

Decomposition-

If A → BC, then A → B and A → C always holds.

Composition-

If A → B and C → D, then AC → BD always holds.

Additive-

If A → B and A → C, then A → BC always holds.

Rules for Functional Dependency-

Rule-01:

A functional dependency X → Y will always hold if all the values of X are unique (different) irrespective of the values of Y.

Example-

Consider the following table-

A	B	C	D	E
5	4	3	2	2
8	5	3	2	1
1	9	3	3	5
4	7	3	3	8

The following functional dependencies will always hold since all the values of attribute ‘A’ are unique-

A → B
A → BC
A → CD
A → BCD
A → DE
A → BCDE

In general, we can say following functional dependency will always hold-

A → Any combination of attributes A, B, C, D, E

Similar will be the case for attributes B and E.

Rule-02:

A functional dependency X → Y will always hold if all the values of Y are same irrespective of the values of X.

Example-

Consider the following table-

A	B	C	D	E
5	4	3	2	2
8	5	3	2	1
1	9	3	3	5
4	7	3	3	8

The following functional dependencies will always hold since all the values of attribute ‘C’ are same-

A → C
AB → C
ABDE → C
DE → C
AE → C

In general, we can say following functional dependency will always hold true-

Any combination of attributes A, B, C, D, E → C

Combining Rule-01 and Rule-02 we can say-

In general, a functional dependency α → β always holds-

If either all values of α are unique or if all values of β are same or both.

Rule-03:

For a functional dependency X → Y to hold, if two tuples in the table agree on the value of attribute X, then they must also agree on the value of attribute Y.

Rule-04:

For a functional dependency X → Y, violation will occur only when for two or more same values of X, the corresponding Y values are different.

Next Article- Equivalence of Functional Dependencies

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

Watch video lectures by visiting our YouTube channel LearnVidFun.

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.

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,