Irreducible set of FD


Irreducible set of Functional Dependency

In an irreducible set of functional dependency, we try to reduce all the transactions to reduce waste of the set of attributes.
Steps to decompose the set of attributes and make it irreducible are as follows:

Step-1: In the given functional dependency, decompose all possible right-hand side attributes and keep left-hand side attributes as it is.

Step-2: Now, find closure of all the transactions(decomposed functional dependencies) by including and excluding the same transaction.

Step-3: Compare the results obtained in closure set of the attribute after including and excluding the same transaction, if the closure of that transaction is the same for both included and excluded transactions then ignore the transaction else that transaction needs to be considered.

For eg.
Consider the relation R(w,x,y,z) with following functional dependencies and reduce them to irreducible set of attributes.
    x -> w
    wz - > xy
    y - > wxz

Firstly, decompose all the transactions:
    x  -> w    wz -> x    wz -> y    y  -> w    y  -> x    y  -> z

Now, find closure of all the decomposed transactions:
1) x -> w
  • Including the transaction
    {x}+={x,w}
  • Excluding the transaction
    {x}+={x}
As, closure are different in both cases so we cannot ignore this transaction.
2) wz -> x
  • Including the transaction
    {wz}+={x,y,w,z}
  • Excluding the transaction
    {wz}+={w,x,y,z}
Closure is same in both cases so, we can ignore this transaction.
3) wz -> y
  • Including the transaction
    {wz}+={x,y,w,z}
  • Excluding the transaction
    {wz}+={w,z}
Closure is different in both cases so, we cannot ignore this transaction.

4) y -> w
  • Including the transaction
    {y}+={x,y,w,z}
  • Excluding the transaction
    {y}+={w,x,y,z}
Closure are same in both cases so we ignore this transaction.
5) y -> x
  • Including the transaction
    {y}+={x,y,w,z}
  • Excluding the transaction
    {y}+={y,z}
Closure are different in both cases so we cannot ignore this transaction.
6) y -> z
  • Including the transaction
    {y}+={x,y,w,z}
  • Excluding the transaction
    {y}+={w,x,y}
Closure are different in both cases so we cannot ignore this transaction.
Now, we willl write all the transactions which cannot be ignored:
    x -> w
    wz -> y
    y -> x
    y -> z
This functional dependencies are now irreducible.

Comments

Post a Comment

Popular posts from this blog

Transaction State Diagram

Image
Transaction State Diagram Let us understand all the states in terms of stages in detail: Stage-1: Once a transaction becomes active it starts its execution and goes to active state . It chooses read or write operations in this stage and stays here till the transaction is executed. Stage-2: Once the read and write operation completes successfully, the transaction then goes to partially committed state, where all the read and write operations are performed on the local memory instead of actual database. The reason for having this state is that, the transaction may fail during execution, and may lead actual database instead of local memory, in an inconsistent state in case of failure. So having this state can help us rollback the changes made to the database in case of execution failure. Stage-3: Then, it is responsibility of recovery protocol, to ensure that a system failure will not disable permanent changes to the database. It any failure occurs either ...
Read more

Functional Dependency

What do you mean by functional dependency? It is defined as relation among two attributes, between primary key and another non-prime attribute within any table. For any relation R, attribute B is functionally dependent on attribute A, here we can say that value of A determines value of B uniquely. Here, A will act as determinant, B will act as a dependent. The relation can be indicated using -> symbol, in following manner: A -> B Let us take one example: Let us consider, we have student table consisting of Roll_no, Name, Age, Bdate, Address. So here, Roll_no can determine Name, Age, Bdate, Address. Roll_no -> Name, Age, Bdate, Address. Rules of Functional Dependencies 1. Reflexive rule:-  If A is a set of attributes and B is subset of A, then A holds the value of B. If A  ⊇   B then A → B         A = {a, b, c, d, e}      ...
Read more

Closure of Attributes

Closure of Attribute Set The set of all those attributes which can be functionally determined from an attribute set is called the closure of that attribute set. The closure of attribute set {A} is denoted as  {A} +  Steps for the closure of attribute set Step-1:  Add the attributes contained in the attribute set for which closure is being calculated to the result set. Step-2:  Thus, keep adding the attributes recursively to the result set which can be functionally determined from the attributes already contained in the result set. E.g.: In R(A,B,C,D) with the functional dependencies. FD1: A -> B FD2: B -> C FD3: C -> D Let us find closure for attribute A,B,C and D. {A} +  =    {A}                 {A,B}                 {A,B,C,D} {B} +  = ...
Read more