Find the candidate keys from the given relation for normalization

Find the candidate keys from the given relation for normalization

Question:

Consider a relation with schema R(A,B,C,D) with functional dependencies (FD’s):

BC → A, AD → B, CD → B, AC → D.

Find all the candidate keys of R.

Solution:

Let us find the closure for the left hand side (LHS) attributes of given set of functional dependencies.

Let us take the FD BC → A to check whether the LHS BC forms a candidate key or not.

We know	Result =	How?	Description
BC	BC	Given
BC	BCA	BC → A	If we know BC, then we can derive A uniquely as per the reflexivity rule, hence result = BCA
BCA	BCAD	AC → D	From the previous step we know attribute A, and by the FD AC → D the result becomes ABCD which is equal to R. Hence, BC is a candidate key

We derived all the other candidate keys in the same way as stated above and given in the table below;

LHS Closure	Due to the FDs	Result becomes	Description
(BC)+	BC → A AC → D	= ABC (Reflexive) = ABCD (Pseudo-transitive)	The result of (BC)+ is equivalent to R. Hence BC is a candidate key.
(AD)+	AD → B	= ABD (Reflexive)	(AD)+ ≠ R. Hence AD does not form candidate key.
(CD)+	CD → B BC → A	= BCD (Reflexive) = ABCD (Pseudo-transitive)	(CD)+ is equivalent to R. Hence CD forms a candidate key.
(AC)+	AC → D AD → B or CD → B	= ACD (Reflexive) = ABCD (Pseudo-transitive)	(AC)+ = R hence is a candidate key.

BC, AC, and CD are the candidate keys for the given relation.

********

Go to Normalization - Solved Exercises page

Go to - 1NF,    2NF,    3NF,    BCNF

Go to How to find closure? page

find the candidate keys

find all the candidate keys of a relation for normalization purpose

how to find the closure

armstrong's axioms

reflexive rule in database design

normalization solved exercises

normalization solved examples

How many disk blocks to be accessed to answer the SQL query

How many disk blocks to be accessed to answer the SQL query

Question:

Consider the following table:

EMPLOYEES (EmpID, Name, Salary)

The table is stored on a disk file consisting of 40 blocks. EmpID is the primary key and the primary key index is a B-Tree with 3 levels and 20 leaf nodes.

For each of the following queries, state how the query is to be executed (e.g., full table scan, full index scan, etc.) and calculate the associated cost (in number of blocks):

(i) SELECT empID FROM employees;

(ii) SELECT name FROM employees WHERE empID = 120;

(iii) SELECT * FROM employees WHERE salary > 15000;

Solution:

(i) SELECT empID FROM employees;

This query does not have a WHERE clause hence there is no filtering condition. Also, it projects only one attribute EmpID which is also the primary key. As per the given information, there is B-Tree index table on EmpID.

The query requests values stored in empID attribute alone. Therefore, no need to access the table on disk as all the data requested in the query is contained in the index. Hence, we need to do a full scan of the index and it will cost: number of leaf nodes = 20 blocks.

20 blocks to be scanned to produce the result for the given query.

(ii) SELECT name FROM employees WHERE empID = 120;

This query has a WHERE clause and the filtering condition (empID = 120) involves the key attribute. To locate the empID with the value 120, we need to scan the index table. As we use B-Tree index and the index values are unique, we need to scan the number of levels of the B-Tree and one leaf node where the request value is stored.

Hence, unique index scan does the following;

Number of levels to be scanned in the B-Tree + 1 leaf node = 3 + 1 = 4

4 blocks to be scanned to produce the result for the above query.

(iii) SELECT * FROM employees WHERE salary > 15000;

Given that there is no index on salary, a full table scan is performed. Cost = 40 blocks.

***********

Go to Solved Exercises in DBMS page

Go to Multiple Choice Questions in Disk Storage and Access page

 

find the number of disk blocks to be accessed to answer the SQL query

SQL query cost calculation

Index scan

Full index scan, full table scan

when do we need to perform full index scan

the occasions we need to go for full table scan

given a table, calculate the cost of execution of SQL query in terms of disk block access

SQL and Relational Algebra short exercises solved

SQL and Relational Algebra short exercises solved

SQL and Relational Algebra Exercises

1. Consider relation R₁(A, B, C) and R₂(B,D), where number of tuples in R₁, T(R₁) = 25 and number of tuples in R₂, T(_R2) = 40, and B is a key for R₁. How many tuples R₁ ⋈ R₂ will give?

Answer: 40 tuples

B is the foreign key in R₂. The permissible values for attribute B in R₂ are the values that are stored in attribute B of R₁. The value of B can be duplicated. Hence, the result is all the tuples from R₂.

2. Write the following query in relational algebra, for relations R(a, b) and S(c, d): select a, d from R, S where R.a > 10 and R.b = S.c.

Answer: π_a,d(σ_a>10(R ⋈_b=c S))

3. Write the following relation algebra expression in SQL, for relations Students(regno, name, age) and Stu_Tour_Regd(regno, name, tour_amt): π_{regno, name}(σ_{age > 20}(STUDENTS)) − π_{regno, name}(STU_TOUR_REGD)

Answer: (SELECT regno, name FROM Students WHERE age > 20) EXCEPT (SELECT regno, name FROM Stu_tour_regd)

This query finds the register number and names of students whose age is greater than 20 and not registered for tour.

4. For relation Student(regno, name, dept), suppose dept can be one of {ite, cse, ece, eee, mech, civil}. If number of tuples in relation Student is 1000, then what is the size estimate of the query σ_{dept = ‘physics’}(Student)?

Answer: Nil.

Physics is not one of the departments. Hence, no students belong to that department.

5. How exactly the relational algebra expression R ⋈_θ S can be expressed using only the basic relational algebra operators?

Answer: σ_θ(R X S)

The given expression is called as theta join. It is a combination of a join condition (θ) and the join operation (X).

***********

Go to DBMS - solved exercises page 

Go to DBMS - Multiple Choice Questions (MCQs) page

 

solved exercises in dbms

solved exercises in relational algebra

solved exercises in SQL

SQL and relational algebra short answers

SQL and relational algebra short exercises