UNIT – 3

TOPIC

Unit-3/Lecture-01

FUNCTIONAL DEPENDENCY

Definition: A set of attributes X functionally determines a set of attributes Y if the value of X determines a unique value for Y.

This is similar to functions in mathematics. In mathematics, a function f is said to be valid function when for every value of x ,f(x) return single value of y. For example, function y = x² returns single value of y for every value of x (at x=0 y=0,at x=1 y=1,at x=2 y=4). Now

consider the function, y=√x this function returns 2 values of by for every value of x(for x=4 it returns y = -2 and y = +2). So it is not a valid function. For a valid function we can say x functionally determine y.

Q24.Consider Relation R(A,B,C) and sample data in R

A	B	C
a1	b1	c1
a1	b2	c1
a2	b3	c2
a2	b4	c2

Which of the following dependencies holds in R?

1. AàB 2. BàA 3. BàC 4. AàC

Ans.

1. AàB – this functional dependency does not hold since for a1 there are two values in

field B.

2. BàA - functional dependency holds

3. BàC - functional dependency holds

4. AàC - functional dependency holds

Note:by using sample data we can only decide which functional dependency is not holding. If a functional dependency is holding in sample data then it may or may not hold in whole relation.

Q25. From the following instance of a relation schema R(A,B,C), we can conclude that:

A	B	C
1	1	1
1	1	0
2	3	2
2	3	2

(a) A functionally determines B and B functionally determines C

(b) A functionally determines B and B does not functionally determines C

(c) B does not functionally determines C

(d) A does not functionally determines B and B does not functionally determines C

Ans. d

Explanation: from a instance of schema we can only prove that particular functional dependency is not holding but we can’t determine that functional dependency is holding. So, options (a) and (b) are wrong. Option (c) is wrong because for data ‘1’ in B there are two values in C.

Unit-3/Lecture-02

Inference rules for Functional dependencies:

1. Reflexivity: XàX always holds. It means a attribute or group of attribute always functionally determines itself.

2. Transitivity: if XàY and YàZ then XàZ

3. Pseudo-transitivity: if XàY and YZàW then XZàW

4. Additivity: if XàY and XàZ then XàYZ

5. Projectivity: if XàYZ then XàY and XàZ

6. Augmentation: if XàY then XZàY

Where X,Y and Z are single attributes or group of attributes of a relation.

Note: if ABàC then you can’t divide ABà C into AàC and BàC.

Closure of anattribute (*): closure of attributes contains all attributes those are directly or indirectly driven by this attribute (using above rules). Example: for a relation R(A,B,C,D), functional dependencies are: AàB , BàC , BCàD.

Closure of A: By 1^st rule a attribute derives itself so its closure contain A(i.e {A}^*={A}). Now from AàB, B can be directly derive from B. if AàB and BàC then AàC(2^nd rule), C can be derived from A . Similarly if AàB and AàC then AàBC(4^th rule) and if AàBC and BCàD then AàD, so D can be derived from A.

A^* = {A,B,C,D}

Similarly, B^*={B,C,D} , C^*={C} , D^*={D}

If closure of an attribute of attributes contains all attributes of relation then attribute is candidate key of relation. In above example A is candidate key of R.

Note: How to find closure of group of attributes: suppose we want to find closure of BC in above example then closure of BC contains attribute directly or indirectly driven by B, C and BC. {BC}^*={B,C,D}

Q26. consider following functional dependencies for relation R(A,B,C,D,E,F,G,H,I,J,K)

ABàC , AàDE, BàF , FàGH , D àIJ

Find closure of AB

Ans.

{AB}* ={A,B,C,D,E,F,G,H,I,J}

Note: in above example AB is not candidate key of R since K is not in closure of AB. K is also not in any functional dependency. Attributes those are not in any functional dependency must be part of candidate key, so candidate key of R is ABK.

Q27. In a schema with attributes A, B, C, D and E following set of functional dependencies

are given.

AàB , AàC , CDàE, BàD, EàA

Which of the following functional dependencies is NOT implied by the above set?

(A) CD à AC

(B) BD à CD

(C) BC à CD

(D)ACàBC IT2005

Ans. B

Explanation: Find closure of attributes in left of all options

(A) {CD}⁺ = { CDEAB} - AC is in closure so AC can be derived from CD

(B) {BD}⁺ = {BD} - CD is not in closure so CD cannot be derived from BD

(C) {BC}⁺ = { BCDEA} - CD is in closure so CD can be derived from BC

(D) {AC}⁺ = { ACBDEA} - CD is in closure so CD can be derived from AC

Unit-3/Lecture-03

Minimal Cover: Minimal cover of functional dependencies is set of functional dependencies which does not contain any redundant functional dependency. For example, if a relation R (A, B, C) has functional dependencies {AàB, BàC, AàC}. In this set AàC is redundant because it can be derived from AàB and BàC, so we need not to write this functional dependency in set. {AàB, BàC} is minimal cover of dependencies.

Steps to find Minimal Cover:

Consider the following functional dependencies of relation R(A,B,C,D,E,F)

AàC , ACàD , EàADH

Step1: covert all functional dependencies to simple form. (If XàYZ then break it into XàY and XàZ).Now functional dependencies for R is:

AàC , ACàD, EàA, EàD, EàH

Step2: to check whether a functional dependency is redundant or not , first hide that functional from set and then find closure attributes those are at left of that functional dependency without using reflexivity rule , if closure contains same attributes for whom we are finding closure then functional dependency is redundant, remove this functional dependency from the set.

First we check for AàC , dependencies remains after hiding it:

ACàD , EàA , EàD , EàH

References:

1. Korth, Silbertz,Sudarshan, “Fundamental of Database System”, McGraw Hill

2. Elmasri, Navathe, “Fundamentals Of Database Systems”, Pearson Educations

Q.1	DEFINE FUNCTIONAL DEPENDENCY.	2011	3
Q.2	WHAT IS MULTIVALUED DEPENDENCIES?	DEC 2015	2
Q.3	WRITE A BRIEF NOTES ON TRIVAL AND NON TRIVAL DEPENDENCIES.	DEC 2015	3

Unit-3/Lecture-04

Problems In Unorganized Relation

Consider the relation student (Rollno, Name, CourseNo , CourseName) with (rollno,courseno) as primary key. following problems are in this relation:

Data Redundancy: if one course is assigned to many student then that course name and course number will be in many records in tables. This causes following anomalies in table:

1. Insertion anomaly: we can’t insert a new course until at least one student register for it.

2. Deletion Anomaly: if we want to delete a course from table then student information may loss.

3. Updation anomaly: if we want to change course name of that course then we have to change course in all the records of students those are assigned to that course

Normalization: To remove data redundancy and anomalies we Normalize table by decomposing into multiple tables. Following normal forms are defined for Normalization:

1^st Normal Form: a relation is said to be in 1st normal form if it’s data is represented in tabular form or atomic and there should not be duplicated row(whole row should not be duplicated, at least value in one same field of two rows must be different ).

Example:

Consider following data in employee table.

Empid	Ename	Job	Salary
1	Vivek	Programmer	30000
		Analyzer	20000
		Project manager	12000

Above table appears to be in tabular form but it’s not in tabular form. A table in is in tabular form if it for every row each column have single value.

Above table will be in 1NF if it is represented as

Empid	Ename	Job	Salary
1	Vivek	Programmer	30000
1	Vivek	Analyzer	20000
1	Vivek	Project manager	12000

Unit-3/Lecture-05

2^nd Normal Form(2NF) : To understand 2NF first look at these terms:

Consider relation Student(Rollno, Name, CourceNo,CourceName, Deptid, DeptName)

· Prime attribute: Attributes those are parts of candidate key/primary key but not a candidate key. For example, if {rollno , courseno , deptid} is candidate key of student relation then rollno , courseno , {rollno, courseno}, {rollno,deptid} and {courseno,deptid} are the prime attributes. In other words, prime attributes are proper subset of candidate keys.

· Determinant: in functional dependency X à Y , X is determinant(attributes at the tail(left side) of arrow)

· Partial dependency: a functional dependency is said to be partial when determinant is prime attribute and right side of arrow have non-prime attribute. Consider following functional dependencies for student relation defined above and {rollno , courseno , deptid} as candidate key .

Rollnoàname partial (primeànon-Prime)

Rollno ,courseno ,deptidà name not partial(non-primeànon-Prime)

Rollnoàcourseno not partial(primeàPrime)

Name,coursenoàrollno not partial(non-primeàPrime)

A relation is said to be in 2NF if and only if it is in 1NF and every non-key attribute is fully dependent on the primary key. or in other words, A relation is said to be in 2NF if and only if it is in 1NF and there exist no partial dependency.

Relation in 2NF has redundancy and suffers from anomalies.

Note: if all candidate keys have single attribute, then there will be no prime attribute and relation will be in 2NF.

References:

1. Korth, Silbertz,Sudarshan, “Fundamental of Database System”, McGraw Hill

2. Elmasri, Navathe, “Fundamentals Of Database Systems”, Pearson Educations

Q.1	WHAT IS NORMALIZATION? JUSTIFY THE NEED FOR NORMALIZATION WITH EXAMPLE.	DEC 2015	7
Q.2

Unit-3/Lecture-06

3^rd Normal Form (3NF): A relation R is in third normal form (3NF) if and only if it is in 2NF and every non-key (non-prime) attribute is non-transitively dependent on the primary key.

A functional dependency XàY not violates 3NF conditions if either X is candidate key or Y is prime attribute , where X and Y attributes or group of attributes. If any of the functional dependencies violates 3NF conditions then relation is not in 3NF.

An attribute C is transitively dependent on attribute A if there exists an attribute B such that: AàB and BàC. Note that 3NF is concerned with transitive dependencies which do not involve candidate keys.

If A 3NF relation has more than one candidate key then it can have transitive dependencies of the form: primary_keyàother_candidate_keyàany_non-key_column.

A relation R having just one candidate key is in third normal form (3NF) if and only if the non-key attributes of R (if any) are:

1) mutually independent(attributes, those are not present in any functional dependency, are mutually independent) , and

2) fully dependent on the primary key of R.

A non-key attribute is any column which is not part of the primary key. Two or more attributes are mutually independent if none of the attributes is functionally dependent on any of the others.

A relation R having just one candidate key is in third normal form (3NF) if and only if no non-key (non-prime) column (or group of columns) determines another non-key (non-prime) column (or group of columns).

Example: consider a relation ShipDetails (Ship, Capacity, Date, Cargo ,Value) with following functional dependencies:

Ship, DateàCargo, Capacity

Cargo à Value

Capacityà Value

To find whether given relation is in 3NF or not, first find all candidate keys of relation using closure of attributes, then find whether relation is in 2NF or not, then check for 3NF.

Step1: candidate key of above relation is {ship, date}.

Step 2: There is no partial dependency so relation is in 2NF.

Step 3:

Ship, DateàCargo, Capacity not violates 3NF conditions(candidate keyànon-prime attribute)

Cargo à Value violates 3NF(non-primeànon-prime)

Capacityà Value violates 3NF(non-primeànon-prime)

Relation ShipDetails is not in 3NF.

A relation in 3NF does not have any anomalies but it still have redundancy.

Boyce-Codd’s Normal form (BCNF): A relation is in BCNF if it contains functional dependencies of form XàY, where X is superkey. This is Strongest than 3NF.

Powers of Normal Form can be compared as

1NF < 2NF < 3NF < BCNF

Q28. consider the following functional dependencies in a database.

Date_of_Birthà Age Ageà Eligibility

Name àRoll_Number Roll_Numberà Name

Course_NumberàCourse_Name Course_Numberà Instructor

(Roll_Number, Course_number)àGrade

The relation (Roll_Number, Name,Date_of_Birth,Age) is

(A) in second normal form but not in third normal form

(B) in third normal form but not in BCNF

(C) in BCNF

(D) in none of the above

Ans. D

Explanation: functional dependencies applicable for relation (Roll_Number, Name, Date_of_Birth, Age) are:

Date_of_Birthà Age

Name àRoll_Number

Roll_Numberà Name

To check that a relation is in which normal form we should apply test from lower level. First apply test for 2NF

Candidate keys of relations are: {Name , Date_of_birth} and {Roll_number , Date_of_birth}

Now check for partial dependencies

Date_of_Birthà Age - partial

Name àRoll_Number - partial

Roll_Numberà Name - partial

There exist partial dependency in relation, relation is not in 2NF , so relation will not be in neither 3NF nor BCNF.

Q29. The relation scheme Student Performance (name, courseNo, rolINo, grade) has the following functional dependencies:

name, courseNoà grade

rolINo, courseNoà grade

name àrolINo

rolINoà name

The highest normal form of this relation scheme is

(a) 2 NF (b) 3 NF (c) BCNF (d) 4 NF

Ans.b

Explanation: candidate keys of relation are: {name, courseNo} and {rollno, courseNo}

First apply test for 2NF.

name, courseNoà grade - not partial(non-primeànon-prime)

rolINo, courseNoà grade - not partial(non-primeànon-prime)

name àrolINo - not partial(primeàprime)

rolINoà name - not partial(non-primeànon-prime)

in this relation no partial dependency exist so relation is in 2NF.

Now check for 3NF: for every XàY either X is candidate key or Y is prime attribute.

name, courseNoà grade - not violating 3NF( candidate key at left side)

rolINo, courseNoà grade - not violating 3NF( candidate key at left side)

name àrolINo - not violating 3NF( prime attribute at right side)

rolINoà name - not violating 3NF( prime attribute at right side)

No dependency is violating 3NF condition ,so relation is in 3NF

Now check for BCNF: for every XàY X should be super key.

name, courseNoà grade - not violating BCNF( super key at left side)

rolINo, courseNoà grade - not violating BCNF( super key at left side)

name àrolINo - violating BCNF

rolINoà name - violating BCNF

Relation is not in BCNF.

Highest normal form of relation is 3NF.

References:

1. Korth, Silbertz,Sudarshan, “Fundamental of Database System”, McGraw Hill

2. Elmasri, Navathe, “Fundamentals Of Database Systems”, Pearson Educations

S.NO	RGPV QUESTIONS	Year	Marks
Q.1	WHAT DO YOU MEAN BY NORMALIZATION, EXPLAIN BCNF & 3 NF.	2011	10
Q.2	PROVE THAT A RELATION WHICH IS IN 4NF MUST BE IN BCNF.	DEC 2015	7

Unit-3/Lecture-06

Desirable Properties of Decomposition:

Lossy and lossless-join decomposition: if divided tables are not able to produce original table after join then decomposition of table is lossy. This does not data is lost after joining tables but extra spurious tuples may produced.

Consider the following relation

enrol (sno, cno, date-enrolled, room-No., instructor)

Sno	cno	date-enrolled	room-No.	instructor
830057 830057 820159 825678 826789	CP302 CP303 CP302 CP304 CP305	1FEB1984 1FEB1984 10JAN1984 1FEB1984 15JAN1984	MP006 MP006 MP006 CE122 EA123	Gupta Jones Gupta Wilson Smith

Suppose we decompose the above relation into two relations enrol1 and enrol2 as follows

enrol1 (sno, cno, date-enrolled)

enrol2 (date-enrolled, room-No., instructor)

There are problems with this decomposition but we wish to focus on one aspect at the moment.

date-enrolled	room-No.	instructor
1FEB1984 1FEB1984 10JAN1984 1FEB1984 15JAN1984	MP006 MP006 MP006 CE122 EA123	Gupta Jones Gupta Wilson Smith

Let the decomposed relations enrol1 and enrol2 be:

Sno	Cno	date-enrolled
830057 830057 820159 825678 826789	CP302 CP303 CP302 CP304 CP305	1FEB1984 1FEB1984 10JAN1984 1FEB1984 15JAN1984

All the information that was in the relation enrol appears to be still available in enrol1 and enrol2 but this is not so. Suppose, we wanted to retrieve the student numbers of all students taking a course from Wilson, we would need to join enrol1 and enrol2. The join would have 11 tuples as follows:

Sno	Cno	date-enrolled	room-No.	instructor
830057 830057 830057 830057 830057 830057	CP302 CP302 CP303 CP303 CP302 CP303	1FEB1984 1FEB1984 1FEB1984 1FEB1984 1FEB1984 1FEB1984	MP006 MP006 MP006 MP006 CE122 CE122	Gupta Jones Gupta Jones Wilson Wilson

The join contains a number of spurious tuples that were not in the original relation Enrol. Because of these additional tuples, we have lost the information about which students take courses from WILSON. (Yes, we have more tuples but less information because we are unable to say with certainty who is taking courses from WILSON). Such decompositions are called lossy decompositions.

A decomposition must be lossless.

How to check whether a decomposition is lossy or lossless-join decomposition.

For this we have to check whether decomposed tables are able to produce original table or not. Suppose we have relation R(A,B,C,D,E) with functional dependencies :

AàB , AàC , DàC , DàE

Let we decomposes R in two table R1(A,B,D) and R2(C,D,E)

Step 1: Create at table with row equals to number of decomposed relations, and columns equals to all attributes in R.

	A	B	C	D	E
R1
R2

Step2: Now put X into cell(m,n) where m is decomposed relation and n is field which is present in relation m

	A	B	C	D	E
R1	X	X		X
R2			X	X	X

Step 3: Now search for all column in table which X in two rows(which is D here).

Step 4: find those functional dependencies which have column, found in step 3, at left side.

(DàC and DàE in above example).

Put X into cell(m,n) where m is row selected in step 3 and n is attributes in the right of these functional dependencies(C and E for rows selected in D).

	A	B	C	D	E
R1	X	X	X	X	X
R2			X	X	X

Step 5: repeat step 3-5 until no further filling is possible.

If any of the row contain X in all columns then decomposition is lossless-join else it is lossy.

Suppose we decompose R in R1(A,B,C) and R2(A,D,E) then final table for it will be

	A	B	C	D	E
R1	X	X	X
R2	X	X	X	X	X

Means this decomposition is also loss-less join

If we divide R in R1(A,B,C) and R2(C,D,E) then final table for it will be

	A	B	C	D	E
R1	X	X	X
R2			X	X	X

No further filling of table is possible because there is no functional dependency in relation having C as determinant.

Dependency Preserving: when we decompose a table into multiple table then every dependency in original table must be preserved (every dependency must be satisfied by at least one decomposed table). in previous example if we divide R in R1(A,B,C) and R2(A,D,E) then the dependency DàC is not satisfied by R! and R2, because of them not containing D and C together. This decomposition is not dependency preserving.

References:

1. Korth, Silbertz,Sudarshan, “Fundamental of Database System”, McGraw Hill

2. Elmasri, Navathe, “Fundamentals Of Database Systems”, Pearson Educations

S.NO	RGPV QUESTIONS	Year	Marks
Q.1	EXPLAIN DEPENDENCY PRESERVATION.	2011	3
Q.2	WHAT DO YOU MEAN BY THE TERMS LOSS LESS DECOMPOSITION?	DEC 2015	2

Unit-3/Lecture-07

How to decompose a relation into BCNF

A relation is not in BCNF when functional dependencies of relation not satisfying the conditions of BCNF. Consider a relation R(A,B,C,D) with following dependencies:

AàB

BàC

CàD

From these set of dependencies we can find primary key of R which is because closure of A, A*={ABCD}

In this set of functional dependencies BàC and CàD is violating conditions of BCNF.

Take dependencies , those are violating BCNF conditions, one by one and create separate table containing attributes in functional dependency(attributes in the left of functional dependency forms) and remove attribute at the right of these functional dependency from original table.

First we take CàD .create separate table for this relation,R1(C,D) and remove D from R, now remaining attributes in R are {A,B,D}.

First we take BàC . Create separate table for this relation,R2(B,C) and remove C from R, now remaining attributes in R are {A,B}.

So finally three tables are created : R(A,B) , R1(C,D), R2(B,C) . these tables are now in BCNF. This decomposition is lossless and dependency preserving.

Suppose if we would have taken BàC first instead of CàD then R and R1 after first decomposition would be

R(A,B,D) R1(B,C)

Now CàD is not holding by R and R1, so this dependency is lost, no further decomposition is possible. This decomposition is lossless but not dependency preserving.

BCNF decomposition is lossless but may or may not dependency preserving.

Note: if a relation R is having no functional dependency then highest normal form supported by such relation is BCNF.

Q30. Relation R with an associated set of functional dependencies, F, is decomposed into BCNF. The redundancy (arising out of functional dependencies) in the resulting set of relations is

(a) Zero

(b) More than zero but less than that of an equivalent 3NF decomposition

(c) Proportional to the size of F⁺

(d) Indeterminate CS2002

Ans. a

Explanation: if a relation is in BCNF then there is no redundancy left in relation , but if a relation is in 3NF then there will be redundancy with no anomalies.

Q31. Relation R is decomposed using a set of functional dependencies, F, and relation S is decomposed using another set of functional dependencies, G. One decomposition is definitely BCNF, the other is definitely 3NF, but it is not known which is which. To make a guaranteed identification, which one of the following tests should be used on the decompositions?

(Assume that the closures of F and G are available).

(a) Dependency-preservation

(b) Lossless-join

(c) BCNF definition

(d) 3NF definition CS2002

Ans. C

Explanation: if we apply BCNF test to both F and G then only one of them will pass the test(which is in BCNF) other will fail(which is in 3NF).

Q32. Which one of the following statements about normal forms is FALSE?

(a) BCNF is stricter than 3NF

(b) Lossless, dependency-preserving decomposition into 3NF is always possible

(c) Lossless, dependency-preserving decomposition into BCNF is always possible

(d) Any relation with two attributes is in BCNF CS2005

Ans. c

References:

1. Korth, Silbertz,Sudarshan, “Fundamental of Database System”, McGraw Hill

2. Elmasri, Navathe, “Fundamentals Of Database Systems”, Pearson Educations

Setting of page

1. Page no. at top in the center.

2. Theme font -Calibri

3. Main text font size-12

4. All headings in bold (12)

5. Top centre headings font size-14

6. Page A-4 size

7. Header and footer -0

8. margin -left (1.25), right (1)

9. Line spacing-1.00