# Functional Dependency and Attribute Closure in DBMS

Learn: In this article, we are going to discuss about the **functional dependency and attributes closure In Database management system** and check whether a functional dependency is valid or nor?

Submitted by Prerana Jain, on May 20, 2018

## Functional Dependency

A relational Database management System (RDBMS) represents the database o a collection of relations/tables. **A functional dependency is a constraint between two sets of attributes in a relation. It is the property of semantics or meaning of attribute. Functional dependency is also a property of relational schema "R" and not a particular legal relation "r" of "R"**.

Now let us consider, a relational "a" schema "R" and let "x" and "y" be the two set of attributes, now there is a functional dependency from "x" to "y"

If, **t1[x] = t2[x]** then, **t1[y] = t2[y]**

**Here**, "x" is the determinant and "y" is the dependent or "x" determines "y".

- Some functional dependency is directly visible in relational model but some either set of dependencies also hold good which are not directly visible.
- The entire set of functional dependency is called as complete set.
- Therefore, we must know how to calculate closure set of functional dependencies before Normalization.
- A functional dependency from "A" to "B" is said to be trivial if "B" is a subset of "A".

**Example:** In the corresponding relation,

Tuple A Ct1 a1 c1 t2 a1 c1 t3 a2 c2 t3 a2 c2 t4 a3 c3 t5 a3 c2A → C holds ast1[A] = t2[A] then t1[C] = t2[C] t3[A] = t3[A] then t3[C] = t4[C] but, C → A does not holds as. t3[C] = t4[C] = t3[C] but t3[A] = t4[A] does not equal t5[A].

### How to find whether a functional Dependency is valid or invalid?

There are some steps to **find whether a functional dependency is valid or invalid**:

**Step 1)** Check if all the values of "A" are distinct than it is valid otherwise invalid.

**Step 2)** Check if all the values of the "B" are same than the functional dependency is also valid.

**Step 3)** Otherwise we have to find at least one value of "A" on which are having different values of "B" than the functional dependency is invalid.

## Attribute Closure

The set "A*" is said to be the closure set of "A" if the set of attributes are functionally dependent on the attributes of "A"

### Some inference rules to calculate the closure set

**Reflexive rule:**A rule is said to be reflexive if B is a subset of a then A → B. This is called trivial functional dependency rule.**Augmentation rule:**A rule is said to be augmented if A → B then Ar → Br holds good.**Transitive rule:**A rule is said to be transitive if A → B, B → r then A → r.

These three rules are functionally complete and known as RAT rule or RAT axioms and also called Armstrong rule which means only theses rules are sufficient enough to find closure set.

**4) Union rule**

A rule is said to be union if A → B, B → r then A → Br also holds good.

**Decomposition rule:**A rule is said to be decomposed if A → Br, A → B then A → r.**Pseudo transitivity rule:**If A → B and BW → r then WA → r.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions