18CSC303J - Database Management System UNIT 4 & 5 - 12 MARKS
12M:
2) 2NF and 3NF with examples
Second Normal Form (2NF):
For a table to be in the Second Normal Form,
It should be in the first normal form
It should not have partial dependency
1 column primary key
(Basically no 2 rows have the same primary keys)
Example:
Here the course code is unique and can be taken as primary key
Storing student enrollment in various courses. Here, both the columns are not unique, but the tuple (student name, course code) is unique since a student cannot enroll in the same course more than once). But this is not the second normal form.
To convert to 2NF, we need to break it into 2 tables. In the first table, the second column is unique and we can attach each of these with the course codes in the second table
These 2 tables together provide us with the exact same information as our original table.
Third Normal Form (3NF):
A table is said to be in the Third Normal Form when,
It is in the second normal form
It doesn’t have transitive dependency
Column A is said to be functionally dependent on column B if changing the value of A may require a change in the value of B.
Example:
The department column is dependent on the professor name column. This is because if in a particular row, we change the name of the professor we will also have to change the department value. (PROF. C TO PROF. A)
When we changed the professor's name, we also had to change the department. But it may be forgotten to be updated and may cause inconsistencies in the database. 3NF avoids this by breaking this into separate tables:
In the above table, we use the id instead of the professor name, which can be used to reference the professor instead of the other details of the professor.
6) Types of dependencies with examples and attribute closure of functional dependency
Dependency:
Dependencies in DBMS is a relation between two or more attributes
It has the following types:
Functional dependency
Fully functional dependency
Transitive dependency
Multivalued dependency
Partial dependency
Functional dependency:
If the information stored in a table can uniquely determine another information in the same table, then it is called functional dependency
If P functionally determines Q, then P -> Q
Example:
EmpID -> EmpName
Fully functional dependency:
An attribute is fully functional dependent on another attribute, if it is functionally dependent on that attribute and not on any of its proper subset
Example:
{EmpID, ProjectID} -> (Days)
Transitive dependency:
When an indirect relationship causes functional dependency, it is called transitive dependency
If P -> Q and Q -> R is true, then P -> R is a transitive dependency
Multivalued dependency:
When existence of one or more attributes in a table implies one or more other attributes in the same table, then the multivalued dependencies occur
Represented by double arrow ->->
P->->Q Q->->R
Partial dependency:
Partial dependency occurs when a nonprime attribute is functionally dependent on part of a candidate key
Student name and project name should be functionally dependent on part of a candidate key, to be partially dependent
Student name can be determined by student id, making it partial dependent
project name can be determined by project id, making it partial dependent
Closure:
The closure of functional dependency means the complete set of all possible attributes that can be functionally derived from given functional dependency using the inference rules known as armstrong’s rules
Attribute closure of an attribute set can be defined as set of attributes which can be functionally determined from it
3) Transaction concept, states of transaction with diagram. How the integrity of the database is preserved during transaction
Transaction
A transaction is a unit of program execution that accesses and possibly update various data items
Eg: transaction to transfer 50$ from account A to account B
Read (A)
A:= A-50
Write (A)
Read (B)
B:= B+50
Write (B)
Two main issues:
Failures of various kinds
Concurrent execution of multiple transactions
States of Transaction:
Active: the initial state; the transaction stays in this state while it is executing
Partially committed: after the final statement has been executed
Failed: after the discovery that normal transaction can no longer proceed
Aborted: after the transaction has been rolled back and the database restored to its state prior to the start of the transaction
Committed: after successful completion
To preserve the integrity of data, the database system must ensure,
Atomicity: either all operations of the transaction are properly reflected in the database or none are
Consistency: execution of a transaction in isolation preserves the consistency of the database
Isolation: although multiple transactions may execute concurrently, each transaction must be unaware of the other concurrently executing transactions
Durability: after a transaction completes successfully, the changes made to the database persist even if there are system failures
4) Explain deadlock and deadlock prevention mechanism and deadlock recovery
Deadlock:
Consider the partial schedule,
Neither T4 nor T3 can make progress; T4 waits for T3 to release its lock on B and T3 waits for T4 to release its lock on A
Such a situation is called a deadlock
To handle a deadlock, one of T3 or T4 must be rolled back and its locks released
Deadlock Prevention:
System is deadlocked if there is a set of transactions such that every transaction in the set is waiting for another transaction in the set
Deadlock prevention protocols ensure that the system will never enter into a deadlock state. Some prevention strategies
Require that each transaction locks all its data items before it begins execution
Impose partial ordering of all data items and require that a transaction can lock data items only in the order specified by the partial order
Wait-die scheme (non-preemptive): older transaction may wait for younger transaction to release data items and younger transactions are rolled back
Wound-wait scheme (preemptive): older transactions wounds younger ones to roll back and younger ones wait for older ones
Timeout based scheme: a transaction waits for a lock only only for a specified amount of time; if exceeded, transaction is rolled back and restarted
Deadlock Recovery:
When deadlock is detected,
Some transactions may have to be rolled back to break deadlock
Select the transaction that will incur minimum cost as victim
Rollback - determine how far to roll back transaction
Starvation happens if same transaction is always chosen as the victim
Include the number of rollbacks in the cost factor to avoid starvation
7) Two phase locking protocol and how read and write operations are performed in transactions by using two phase locking protocol
A locking protocol is a set of rules followed by all transactions while requesting and releasing locks.
Locking protocols restrict the set of possible schedules
Two Phase Locking Protocol:
This protocol ensures conflict serializable schedules
Phase 1: Growing phase
Transaction may obtain locks
Transaction may not release locks
Phase 2: Shrinking phase
Transaction may release locks
Transaction may not obtain locks
This protocol ensures serializability
It can be proved that the transactions can be serialized in the order of their lock points
There can be conflict serialized schedules that cannot be obtained if two phase locking is used
However in the absence of extra information, two phase locking is needed for conflict serializability
Read operation:
If Ti has a lock on D
Then
Read (D)
Else begin
If necessary wait until no other transaction has a lock-X on D
Grant Ti a lock-S on D;
Read (D)
End
Write operation:
If Ti has a lock-X on D
Then
write (D)
Else begin
If necessary wait until no other transaction has any lock on D
If Ti has a lock-S on D
Then upgrade lock-S on D to lock-X
else
Grant Ti a lock-X on D;
write (D)
End
Comments
Post a Comment