Functional Dependencies

Definition of Functional Dependency

A functional dependency is a constraint between two sets of attributes from the database.

A functional dependency, denoted by X → Y, between two sets of attributes X and Y that are
subsets of R specifies a constraint on the possible tuples that can form a relation state r of R.
The constraint is that, for any two tuples t1 and t2 in r that have t1[X] = t2[X], they must also
have t1[Y] = t2[Y].

XY means there is a functional dependency from X to Y, or that Y is functionally

dependent on X.

X functionally determines Y in a relation schema R if, and only if, whenever two tuples of r(R)
agree on their X-value, they must necessarily agree on their Y-value.

Eg:- {State, Driver_license_number} → Ssn should normally hold for any adult in the United
States

NOTE

If X is a candidate key of R, then X → R.

■ If X → Y in R, this does not say whether or not Y → X in R.

These functional dependencies specify that (a) the value of an employee’s Social Security
number (Ssn) uniquely determines the employee name (Ename), (b) the value of a project’s
number (Pnumber) uniquely determines the project name (Pname) and location (Plocation),
and (c) a combination of Ssn and Pnumber values uniquely determines the number of hours
the employee currently works on the project per week (Hours).

Eg:2

Here, the following FDs may hold: B → C; C → B; {A, B} → C; {A, B} → D; and {C, D} → B.
However, : A → B do not hold because we already have violations of them in the given
extension (tuples 1 and 2 violate this constraint);

B → A (tuples 2 and 3 violate this constraint);

D → C (tuples 3 and 4 violate it).

Normalization of Relations
The normalization process, as first proposed by Codd (1972), takes a relation schema
through a series of tests to certify whether it satisfies a certain normal form. Normalization
of data can be considered a process of analyzing the given relation schemas based on their
FDs and primary keys to achieve the desirable properties of (1) minimizing redundancy and
(2) minimizing the insertion, deletion, and update anomalies

The process, which proceeds in a top-down fashion by evaluating each relation against the
criteria for normal forms and decomposing relations as necessary, can thus be considered as
relational design by analysis.

Initially, Codd proposed three normal forms, which he called first, second, and third normal
form. A stronger definition of 3NF—called Boyce-Codd normal form (BCNF)—was proposed
later by Boyce and Codd.

All these normal forms are based on a single analytical tool: the functional dependencies
among the attributes of a relation. Later, a fourth normal form (4NF) and a fifth normal form
(5NF) were proposed, based on the concepts of multivalued dependencies and join
dependencies, respectively.
First Normal Form(1NF)
1NF states that the domain of an attribute must include only atomic (simple, indivisible)
values and that the value of any attribute in a tuple must be a single value from the
domain of that attribute.

Hence, 1NF disallows having a set of values, a tuple of values, or a combination of both as an
attribute value for a single tuple. In other words, 1NF disallows relations within relations or
relations as attribute values within tuples. The only attribute values permitted by 1NF are
single atomic (or indivisible) values.

Consider the DEPARTMENT relation schema shown in Figure 14.1, whose primary key is
Dnumber, and suppose that we extend it by including the Dlocations attribute as shown in
Figure 14.9(a). We assume that each department can have a number of locations. The
DEPARTMENT schema and a sample relation state are shown in Figure14.9.

As we can see, this is not in 1NF because Dlocations is not an atomic attribute, as illustrated
by the first tuple in Figure 14.9(b). The domain of Dlocations contains sets of values and
hence is nonatomic , the DEPARTMENT relation in Figure 14.9 is not in 1NF;

There are three main techniques to achieve first normal form for such a relation:

1. Remove the attribute Dlocations that violates 1NF and place it in a separate relation
DEPT_LOCATIONS along with the primary key Dnumber of DEPARTMENT. The primary
 key of this newly formed relation is the combination {Dnumber, Dlocation}, as shown
in Figure . A distinct tuple in DEPT_LOCATIONS exists for each location of a
department. This decomposes the non-1NF relation into two 1NF relations.

2. Expand the key so that there will be a separate tuple in the original DEPARTMENT
relation for each location of a DEPARTMENT, as shown in Figure . In this case, the
primary key becomes the combination {Dnumber,Dlocation}. This solution has the
disadvantage of introducing redundancy inthe relation and hence is rarely adopted.

3. If a maximum number of values is known for the attribute—for example, if it is

known that at most three locations can exist for a department—replace the
Dlocations attribute by three atomic attributes: Dlocation1, Dlocation2, and
Dlocation3. This solution has the disadvantage of introducing NULL values if most
departments have fewer than three locations. It further introduces spurious
semantics about the ordering among the location values; that ordering is not
originally intended. Querying on this attribute becomes more difficult; for example,
consider how you would write the query: List the departments that have ‘Bellaire’ as
one of their locations in this design. For all these reasons, it is best to avoid this
alternative.

Of the three solutions above, the first is generally considered best because it does
not suffer from redundancy and it is completely general.

 First normal form also disallows multivalued attributes that are themselves
composite. These are called nested relations because each tuple can have a
relation within it .

To normalize this into 1NF, we remove the nested relation attributes into a new
relation and propagate the primary key into it; the primary key of the new relation
will combine the partial key with the primary key of the original relation.
Eg:- Normalise the following relation to 1NF

CANDIDATE (Ssn, Name, {JOB_HIST (Company, Highest_position, {SAL_HIST (Year,

Max_sal)})})
The relation describes data about candidates applying for jobs with their job history as a
nested relation within which the salary history is stored as a deeper nested relation.
The first normalization using internal partial keys Company and Year, respectively, results in
the following 1NF relations:

CANDIDATE_1 (Ssn, Name)

CANDIDATE_JOB_HIST (Ssn, Company, Highest_position)
CANDIDATE_SAL_HIST (Ssn, Company, Year, Max-sal)

Second Normal Form

 Second normal form (2NF) is based on the concept of full functional dependency.

A functional dependency X → Y is a full functional dependency if removal of any attribute A

from X means that the dependency does not hold anymore; that is, for any attribute
A ε X, (X − {A}) does not functionally determine Y.

A functional dependency X → Y is a partial dependency if some attribute A ε X can be

removed
from X and the dependency still holds; that is, for some A ε X, (X − {A}) → Y.

Definition: A relation schema R is in 2NF if every nonprime attribute A in R is fully

functionally dependent on the primary key of R.

(non prime attribute means attribute that is not part of a candidate key)

Eg:- Consider EMP_PROJ relation with the following functional dependencies

FD1:Ssn, PnumberHours
FD2:SsnEname
FD3:PnumberPname, Plocation
The test for 2NF involves testing for functional dependencies whose left-hand side
attributes are part of the primary key. If the primary key contains a single attribute,
the test need not be applied at all. The EMP_PROJ relation in Figure 14.3(b) is in 1NF but is
not in 2NF. The nonprime attribute Ename violates 2NF because of FD2, as do the nonprime
attributes Pname and Plocation because of FD3.

Each of the functional dependencies FD2 and FD3 violates 2NF because Ename can be
functionally determined by only Ssn, and both Pname and Plocation can be functionally
determined by only Pnumber. Attributes Ssn and Pnumber are a part of the primary key
{Ssn, Pnumber} of EMP_PROJ, thus violating the 2NF test.

If a relation schema is not in 2NF, it can be second normalized or 2NF normalized into a
number of 2NF relations in which nonprime attributes are associated only with the part of
the primary key on which they are fully functionally dependent.

Therefore, the functional dependencies FD1, FD2, and FD3 in Figure 14.3(b) lead to the
decomposition of EMP_PROJ into the three relation schemas EP1, EP2, and EP3 shown in
Figure below each of which is in 2NF.

Third Normal Form

Third normal form (3NF) is based on the concept of transitive dependency. A functional
dependency X → Y in a relation schema R is a transitive dependency if there
exists a set of attributes Z in R that is neither a candidate key nor a subset of any key of
R, and both X → Z and Z → Y hold.
SsnEname Bdate Address Dnumber
DnumberDname Dmgr_ssn

The dependency Ssn → Dmgr_ssn is transitive through Dnumber in EMP_DEPT in Figure (a),
because both the dependencies Ssn → Dnumber and Dnumber → Dmgr_ssn hold and
Dnumber is neither a key itself nor a subset of the key of EMP_DEPT.

We can normalize EMP_DEPT by decomposing it into the two 3NF relation schemas ED1 and
ED2 shown in Figure(b). Intuitively, we see that ED1 and ED2 represent independent
facts about employees and departments, both of which are entities in their own right. A
NATURAL JOIN operation on ED1 and ED2 will recover the original relation EMP_DEPT
without generating spurious tuples.

Consider the relation and functional dependency as shown in Fig(a)

Property_id# Country_name Lot# Area Price Tax_rate

Country_name , Lot#  Property_id# Area Price Tax_rate
Country_nameTax_rate
AreaPrice