# Other Functional Dependencies

**
**

Contents

# Other Functional Dependencies

There are same rather types of functional dependencies, which play a vital rule during the process .of normalization of data.

** **

# Candidate Functional Dependency

A candidate functional dependency is a functional dependency that includes all attributes of the table. It should also be noted that a well-fanned dependency diagram must have at least one candidate functional dependency, and that there can be more than .one candidate functional dependency for a given dependency diagram.

** **

# Primary Functional Dependency

A primary functional dependency is a candidate functional dependency that is selected to determine the primary key. The determinant of the primary functional dependency is the primary key of the relational database table. Each dependency diagram must have one and only on primary functional dependency. If a relational database table has .only .one candidate functional dependency, then it automatically becomes the primary functional dependency

Once the primary key has been determined, there will be three possible types of functional dependencies:

* *

# Description

A à B A key attribute functionally determines a non-key attribute.

A à B A non-key attribute functionally determines a non-key attribute.

A à B A non-key attribute functionally determines a key attribute.

A **partial functional dependency** is a functional dependency where the determinant consists of key attributes, but not the entire primary key, and the determined consist~ of non-key attributes.

A **transitive functional dependency** is a functional dependency where the determinant consists of non-key attributes and the determined also consists of non-key attributes.

A **Boyce-Codd functional dependency** is a functional dependency where the determinant consists of non-key attributes and the determined consists of key attributes.

A **Multi-Value Dependency (MVD)** occurs when two or more independent multi valued facts about the same attribute occur within the same table. It means that if in a relation R having A, Band C as attributes, B and Care multi-value facts about A, which is represented as A ààB and A ààC ,then multi value dependency exist only if B and C are independent on each other.

A **Join Dependency** exists if a relation R is equal to the join of the projections X Z. where X, Y, Z projections of R.

**Closure of set of dependencies**

Let a relation *R *have some functional dependencies *F *specified. The *closure of F *(usually written as *F*+) is the set of all functional dependencies that may be logically derived from *F. *Often *F *is the set of most obvious and important functional dependencies and. *F*+, the closure, is the set of all the functional dependencies including *F *and those that can be deduced from *F. *The closure is important and may, for example, be needed in finding one or more candidate keys of the relation.

For example, the *student *relation has the following functional dependencies

* *

*sno *à *Sname*

*cno *à *came*

*sno *à *address*

*cno *à *instructor*

*Instructor **à* *office*

* *

Let these dependencies be denoted by *F. *The closure of *F, *denoted by *F *+, includes *F *and all functional- dependencies that are implied by *F.*

* *

To determine *F*+, we need rules for deriving all functional dependencies that are implied:* *by *F. *A set of rules that may be used to infer additional dependencies was proposed by* *Armstrong in 1974. These rules (or axioms) are a complete set of rules in· that all possible* *functional dependencies may be derived from them. The rules are:

* *

*1. Reflexivity Rule – *If *X *is a set of attributes and Y is a subset of *X, *then *X **à**Y *holds.

The reflexivity rule is the simplest (almost trivial) rule. It states that each subset of *X *is functionally dependent on *X. *In other words trivial dependence is defined as follows:

**Trivial functional dependency**: A trivial functional dependency is a functional dependency of an attribute on a superset of itself.

**For example:** {Employee ID, Employee Address} à {Employee Address} is trivial, here {Employee Address} is a subset of {Employee ID, Employee Address}.

* *

*2. Augmentation Rule – *If *X **à Y *holds and *W *is a set of attributes, and then *WX **à **WY *holds.

The argumentation (‘u rule is also quite simple. It states that if *Y *is determined by *X *then a set of attributes *W *and *Y*together will be determined by *W *and *X *together.* *Note that we use the notation *WX *to mean the collection of all attributes in *W *and *X *and write *WX *rather than the more conventional *(W, X) *for convenience.

**For example**: Rno – Name; Class and Marks is a set of attributes and act as

*W. *Then· {Rno, Class, Marks} -> {Name, Class, Marks}

*3. Transitivity Rule – *If *X -> *Y and Y -> *Z *hold, then *X -> Z *holds.

The transitivity rule is perhaps the most important one. It states that if *X *functionally determines Y and Y functionally determine *Z *then *X *functionally determines *Z.*

**For example:** Rno -> City and City -> Status, then Rno -> Status should be holding true.

These rules are called *Armstrong’s Axioms.*

Further axioms may be derived from the above although the above three axioms are *sound and complete *in that they do not generate any incorrect functional dependencies (soundness) and they do generate all possible functional dependencies that can be inferred from *F *(completeness). The most important additional axioms are:

* *

*1. Union Rule – *If *X -> Y *and *X -> Z *hold, then *X -> YZ *holds.

*2. Decomposition Rule – *If *X **à YZ *holds, then so do *X **à Y *and *X **à *Z.

* *

*3. Pseudotransitivity Rule – *If *X **à Y *and *WY **à *Z hold then so does *WX **àZ.*

Based on the above axioms and the .functional dependencies specified for relation *student, *we may write a large number of functional dependencies. Some of these are:

* *

*( sno, cno) **à sno *(Rule 1)

*(sno, cno) **à** cno *(Rule 1)

*(sno, cno) **à** (Sname, cname) *(Rule 2)

*cno **à office *(Rule 3)

*sno **à (Sname, address) *(Union Rule)

Etc.

Often a very large list of dependencies can be derived from a given set *F *since Rule 1 itself will lead to a large number of dependencies. Since we have seven attributes *(sno,* *Sname, address, cno, cname, instructor, office), *there are 128 (that is, 2^7) subsets of these attributes. These 128 subsets could form 128 values of *X *in functional dependencies of the type *X ~ Y. *Of course, each value of *X *will then be associated with a number of values for *Y (Y *being a subset of x) Leading to several thousand dependencies. These large numbers of dependencies are not particularly helpful in achieving our aim of normalizing relations.

Although we could follow the present procedure and compute the closure of *F *to find all the functional dependencies, the computation requires exponential time and the list of dependencies is often very large and therefore not very useful. There are two possible approaches that can be taken to avoid dealing with the large number of dependencies in the closure. ‘One’ is to deal with one attribute or a set of attributes at a time and find its closure (i.e. all functional dependencies relating to them). The aim of this exercise is to find what attributes depend on a given set of attributes and therefore ought to be together. The other approach is to find the *minimal· covers.*