How to check whether a functional dependency hold in a relation R

How to check whether a functional dependency hold in a relation R, Check the functional dependencies of a relation, Functional dependencies satisfied or not?, Find all the functional dependencies or a table

Exercise

Consider a relation R (A, B, C, D) with the following instance;

A	B	C	D
1	1	2	3
1	2	2	3
1	3	2	3
2	4	5	6
5	6	7	8

Which of the following functional dependencies are satisfied by this relation? How?

(a) A → B

(b) A → CD

(c) AB → CD

(d) C → D

(e) B → A

(f) BD → AC

(g) AD → BC

(h) D → B

(i) D → C

(j) C → A

Solution:

Functional dependency – For a given Left Hand Side (LHS) value of an attribute (or set of attributes) of a functional dependency, there should be at most one Right Hand Side (RHS) value of an attribute (or set of attributes). Then we would say that the functional dependency holds on that relation.

In other words, if you execute the following query, we should always get only one student_name for a given reg_no.

SELECT Student_Name FROM Student WHERE Reg_No = 123;

Example:

REG_NO → STUDENT_NAME. This functional dependency means that there is at most one student name is related to one register number. This is correct.

STUDENT_NAME → REG_NO. This functional dependency means that there is at most one register number is related to a student name. This may not be true. Because, there may be more than one student with the same name.

(a) A → B – does not hold in relation R.

WHY? In the table R, we have 3 B values (1, 2 and 3) for a given A value (1).

(b) A → CD – holds in relation R.

WHY? In R, we have single C and D combination of values for every A value. You can observe the following from R.

A	(C, D)
1	(2, 3)
2	(5, 6)
5	(7, 8)

Also observe that whenever 1 comes as A value, (2, 3) is repeated. That means, this should be true for all records of R. whenever 1 is inserted as A value for any new record, there must be only one combination of C and D, (2, 3).

(c) AB → CD – holds in relation R.  

WHY? In R there is one to one relationship between AB and CD, i.e., for a given A and B combination of values, there is unique C and D combination of values.

(d) C → D – holds in relation R.  

WHY? In R there is one to one relationship between C and D values.

C	D
2	3
5	6
7	8

(e) B → A – holds in relation R.  

WHY? In R there is one to one relationship between B and A values from B. that is, for a given B value, there is only one associated A value.

(f) BD → AC – holds in relation R.  

(g) AD → BC – does not hold in relation R.  

WHY? In R, for a given A and D values (1, 3), there are more than one (3 values - (1, 2), (2, 2), (3, 2)) B and C values.

(h) D → B – does not hold in relation R.  

WHY? In R, we have 3 different B values (1, 2, and 3) for a given D value (3).

(i) D → C – holds in relation R.  

(j) → D – holds in relation R.  

Go back to other Normalization Process Exercises

CS9024 Advanced Database Technology April May 2014

Anna University Questions - CS9024 Advanced Database Technology April May 2014, Computer Science and Engineering, Fifth Semester, Regulation 2008

Exam	B.E/B.Tech. (Full Time) DEGREE END SEMESTER EXAMINATIONS
Academic Year	April May 2014
Subject Code	CS9024
Subject Name	Advanced Database Technology
Branch	Computer Science and Engineering
Semester	Fifth Semester
Regulation	2008

B.E / B.Tech. (Full Time) DEGREE END SEMESTER EXAMINATIONS, APRIL / MAY 2014

Computer Science and Engineering

Fifth Semester

CS9024 ADVANCED DATABASE TECHNOLOGY

(Regulations 2008)

Time : 3 Hours                      Answer A L L Questions                Max. Marks 100

PART-A (10 x 2 = 20 Marks)

1. Brief on generalization in ER model.

2. Mention any two methods of database tuning.

3. How vertical fragmentation achieves data availability feature of distributed databases?

4. List the different types of failures in distributed database system.

5. What is the significance of multi version locking in OODB?

6. Illustrate the differences between the type constructors - Set and List.

7. What is data cube? Mention any two operations that can be performed on a data cube.

8. Mention any two features of web databases.

9. What are the major components of knowledge bases?

10. List any three data structures that support multimedia databases? Give the representation of any one.

Part-B (5* 16 = 80 Marks)

11. i) Consider the following relation containing the attributes:

Bookid, subject_category_of_book, authorname and nationality_of_author.

Primary Key : Bookid

1) What is the highest normal form satisfied by this relation?

2) Suppose the attributes books_title and author_address are added , and the PK is changed to {authorname, books_title}, what will be the highest normal form satisfied by this relation? (8)

ii) Illustrate the stages of query processing. (8)

12. a i) Explain the Client / Server architecture of distributed databases. (8)

a ii) Describe the concurrency control in distributed databases. (8)

Or

12. b i) Consider a company relation that is fragmented horizontally by plant-no and given as Employee(name, address, salary, plant-no). Assume that each fragment has two replicas; one stored at the Chennai site and another stored locally at the plant site of

Trichy. Describe a good processing strategy for the following queries entered at the Madurai site: (8)

(A.) Find all employees at the Chennai site.

(B.) Find the lowest paid employee at Cochin and Mumbai sites.

(C.) Find the highest paid employee in the company.

ii) Explain 2 phase commit protocol of distributed databases. (8)

13. a i) a ii) Express the RDB schema of Fig. 13.a. in POSTGRES. (8)

Fig. : 13. a.

a ii) Give a comparison between OODM and ER model. (8)

Or

13. b i) Explain the mechanism to make the objects persistence in OODB. (8)

b ii) Compare the features of GEMSTONE and JASMINE object databases with examples. (8)

14. a i) Give the benefits and limitations of data warehouse. (8)

a ii) Explain with examples, any four operations that can be performed on a data cube.

(8)

Or

14. b i) Explain the architecture of mobile database with a neat diagram. (8)

b ii) Compare and contrast the CGI and API (8)

15. a i) Illustrate how active databases help audit-trail applications. (8)

a ii) Explain how video sources are represented in a multimedia database. (8)

Or

15. b i) Explain deductive databases with suitable examples. (8)

b ii) What are range queries, neighbour queries and joins with respect to spatial database? Give example for each. (8)

************************

Go back to Anna University Question Papers - Regulation 2008 and Later

Go back to Anna University Question Papers - Regulation 2004

Go back to Previous Years University Question papers 

 

Database normalization - solved exercise to find keys

Set of solved exercises in Normalization / Normalization Solved Examples / How to find candidate keys, and primary keys in database? / Sets of examples to find the keys of a tables / Process of Key finding in a database – Examples

Question:

Relation R has eight attributes ABCDEFGH. Fields of R contain only atomic values. F = {CH → G, A → BC, B → CFH, E → A, F → EG} is a set of functional dependencies (FDs) so that F⁺ is exactly the set of FDs that hold for R. Find the candidate keys of relation R. (GATE 2013 question)

Solution:

Which attribute (or set of attributes) is the key? – We know that, if the closure of an attribute (or set of attributes) includes all the attributes of the relation, then that attribute (or set of attributes) is one of the candidate keys of the relation (table).

To simplify, we would find the closure for left hand side attributes of all the functional dependencies (we can skip redundant attributes).

Closure of A (A⁺):

Result = A

Result = ABC from A → BC

Result = ABCFH from B → CFH

Result = ABCEFGH from F → EG

Final result = ABCEFGH which is not ABCDEFGH i.e., result ≠ R. hence, A is not a candidate key.

Closure of E (E⁺):

Result = E

Result = EA from E → A

If we know A, from the above derivation, final result would be ABCEFGH. And this is not equal to R, hence E is not a candidate key.

At this stage, we need to observe one thing from the set of functional dependencies given. The thing is, attribute D is not part of any functional dependencies. Hence, we need to include D with other attributes. That means, whatever key we find, D should be a part of it.

Hence, we would try with D as a component attribute; if we follow the steps applied above; we would get the following;

Closure of AD (AD⁺) = R. Hence, AD is one of the candidate keys.

Closure of BD (BD⁺) = R. So BD is one of the candidate keys.

Closure of ED (ED⁺) = R. So, ED is one of the candidate keys.

Closure of FD (FD⁺) = R. Hence, FD is one of the candidate keys.

AD, BD, ED, and FD are the candidate keys of R.

What about other set of attributes?

The other attributes other than AD, BD, ED, and FD cannot be the keys (refer definition for candidate keys). Why?

We know that the closure of ABD, ADE, ADF, BED, etc. would form the keys. According to the definition (candidate key is a minimal key for which the proper subset must not contain a key), for example, the subset of ABD contains the keys AD, and BD which are keys. This holds for all the other combinations. Hence, they cannot form the candidate keys. (they are all super keys).

Another try: Let us try to find the closure of CH.

Closure of CH (CH⁺):

Result = CH

Result = CHG from CH → G.

We cannot move further because C, H and G are not (individually or collectively) uniquely determine any other attributes. Hence, CH⁺ = CHG.

As a result, we would conclude that AD, BD, ED, and FD are the qualified candidate keys for R.

Go back to Normalization – solved exercises page.

Related Posts:

Various uses of attribute closure

How to find Closure?