Exam Questions - Normalization, File Organization, Indexing and Hashing

Exam Questions - Normalization, File Organization, Indexing and Hashing

1. List some advantages of DBMS over File Processing System.
2. Define the different levels of data abstraction
3. What do you mean by degree of relationship set?
4. What does DDL interpreter do?
5. What is Multi-valued dependency?
6. Define Loss-less join decomposition.
7. What do you mean by Full Functional Dependency?
8. Define Domain Key Normal Form (DKNF)
9. Define Query Optimization
10. What do you mean by Data transfer rate? How does it helpful in query processing?
11. Define average latency time, mean time to failure, and average seek time.
12. What are the responsibilities of Buffer manager?
13. Discuss the Toss-immediate buffer management strategy with an example.
14. Why the Most Recently Used (MRU) block replacement is considered the optimal one in database?
15. Define heap file organization, sequential file organization, and hash file organization.
16. How do we handle insertion of new records in Sequential file organization?
17. List down various information stored in the Data dictionary.
18. Does the allocation of records to blocks affect database-system performance? Why?
19. Define Dangling pointer.
20. List and define the types of indices.
21. Are primary index and clustering index meaning the same thing?
22. List and define the types of ordered indices.
23. List some advantages of dense index.
24. List some advantages of sparse index.
25. Why the sequential scan in primary index is efficient?
26. List some disadvantages of sequential file organization.
27. Why do we need a hash function which can both distribute uniformly and randomly?
28. Define skew.
29. What are the various issues one should consider while choosing File organization and Indexing techniques?
30. For executing a query which specifies a range of values in the WHERE clause, among Ordered indexing and Hash indexing, which is preferable? Why?
31. What would be the result of the SQL statement CREATE UNIQUE INDEX idxA ON TabA(A), if the column A is not a candidate key?
32. Differentiate Primary and Secondary index.
33. How could we reduce the occurrence of bucket overflows in hash file organization?
34. How does a database index work?
35. What is hash table?
36. What are the problems with static hashing?
37. What does an index record contain?
38. For a query like ‘SELECT * FROM Emp WHERE EmpNo = ‘E1’’, hashing is the best choice. Why?
39. How does Denormalization help in improving performance of the system?
40. How does Dynamic hashing manage file expansion?

Database Normal Forms - Quiz 1

Normalization and Normal Forms in Database Design - Quiz 1

1. For a relation R, we are given that the domains of all attributes of R are indivisible. With this information, we can say the relation R is in

1 NF
2 NF
3 NF
BCNF

2. In a table with the schema STU(STUNO, STUNAME, ADDRESS, COURSENO, COURSENAME) and with the functional dependencies, STUNO --> STUNAME ADDRESS, COURSENO --> COURSENAME, STUNO COURSENO --> STUNAME ADDRESS COURSENAME, which of the following anomalies would present?

Insetion Anomaly
Deletion Anomaly
Update Anomaly
All of the above

3. A relation which has only atomic attributes and every non-key attribute fully functionally dependent on candidate keys is said to be in

1 NF
2 NF
3 NF
BCNF

4. Consider the schema given in question 2. Is the relation STU in 2 NF?

YES
NO

5. What does Atomic attribute mean?

It is one type of attribute used in DBMS
An attribute whose values can be divided into meaningful subparts
An attribute whose values cannot be divided into meaningful subparts
None of the above

6. If you have removed repeated groups of values from a relation and also removed the partial key dependencies, then we would say that the given relation is in

1 NF
2 NF
3 NF
BCNF

7. Assume a table with the schema STU(STUNO, STUNAME, ADDRESS, PINCODE) and with the functional dependencies, STUNO --> STUNAME ADDRESS PINCODE, PINCODE --> ADDRESS. Is this relation is in 2 NF?

YES
NO

8. A relation is said to be in 3 NF if which of the following is/are true?

No partial key dependencies
All attributes are atomic
No presence of transitive dependencies
All of the above

9. Assume a table with the schema STU(STUNO, STUNAME, ADDRESS, PINCODE) and with the functional dependencies, STUNO --> STUNAME ADDRESS PINCODE, PINCODE --> ADDRESS. Is this relation is in 3 NF?

YES
NO

10. Assume a table with the schema STU(STUNO, STUNAME, ADDRESS, COURSENO, COURSENAME) and with the functional dependencies, STUNO --> STUNAME ADDRESS, COURSENO --> COURSENAME, STUNO COURSENO --> STUNAME ADDRESS COURSENAME with no transitive dependency. The relation STU is in _______ NF?

1 NF
2 NF
3 NF
BCNF

Score =

Correct answers:

* You can also try other DBMS quizzes here

3NF and BCNF Compared

Third normal form and boyce-codd normal form a comparison

Difference between 3NF and BCNF

Assume the following things;

A and B are set of attributes.

A is non-key attribute and B is the primary key.

FD – { A → B. }

The above Functional Dependency is about the dependency of primary key on a non-key attribute. This functional dependency is permitted in Third Normal Form (3NF). 3NF tries to identify and eliminate Non-key → Non-key dependency.

This Functional Dependency is not permitted in Boyce-Codd Normal Form (BCNF), because BCNF expects the determiner should be a candidate key. In our example, A is not a candidate key. This is why BCNF is termed as strict 3NF.

3NF is always achievable. BCNF is not. BCNF may result in Loss-less Join Decomposition and lead to loss of Dependency Preserving Decompositions.

Properties	3NF	BCNF
Achievability	Always achievable	Not always achievable
Quality of the tables	Less	More
Non-key Determinants	Can have non-key attributes as determinants	Cannot have.
Proposed by	Edgar F. Codd	Raymond F.Boyce and Edgar F.Codd jointly proposed
Decomposition	Loss-less join decomposition can be achieved	Sometimes Loss-less join decomposition cannot be achieved

Table 1 – 3NF – BCNF Comparisons

*********

Related Links

• Go to Normal Form - Home page

• Go to Normalization - Home page

• Go to Normalization Solved Exercises - Home page

• Go to Comparison of All Normal Forms page

Compare third normal form 3nf and boyce codd normal form bcnf

Boyce-Codd Normal Form (BCNF)

Boyce-Codd Normal Form / BCNF Explained / What is BCNF? / Boyce-Codd Normal Form with Example / A relation which is in 3NF but not in BCNF Example.

 Boyce-Codd Normal Form (BCNF)

BCNF was jointly proposed by Raymond F. Boyce and Edgar F. Codd in the year 1974 to address certain types of anomaly which were present even after the schema is normalized to 3NF.

For a relation schema which is in 3NF, the presence of modification anomalies which could not be treated well by 3NF is due to one of the following reasons;

Reason 1: A relation schema might contain more than one candidate keys.

Reason 2: In case of more than one candidate keys presents, all of them might be composite.

Reason 3: If the above two reasons exist, then there is a possibility of overlap between the candidate keys.

A relation schema R is in BCNF if and only if,

• For all the Functional Dependencies (FDs) hold in the relation R, if the FD is non-trivial then the determinant (LHS of FD) of that FD should be a Super key.

 Through this definition, BCNF insists that all the determinants of any Functional Dependency must be a Candidate Key. Due to this reason, BCNF sometimes referred as strict 3NF.

Note: A relation schema R which is in BCNF also in 3NF automatically. But, a relation schema R which is in 3NF need not be in BCNF.

Explanation:

If we have set of FDs in R such that X → Y, then X must be a super key. In other words, if X is not a key, then the relation R is not in BCNF. 

A relation which is not in BCNF.

RegNo	SName	Gen	PR	Phone
R1	Sundar	M	BTech	9898786756
R2	Ram	M	MS	9897786776
R3	Karthik	M	MCA	8798987867
R4	John	M	BSc	7898886756
R1	Sundar	M	BTech	9898781158
R3	Karthik	M	MCA	8798987867

Table 1 – STUDENT

Let us find out the set F of FDs holding on Table 1 STUDENT.

F = { RegNo → SName, RegNo → Gen, RegNo → PR }

But, Phone cannot be uniquely identified by RegNo. Hence, the key for this relation is a composite key (RegNo, Phone). We can write the set F of FDs as follows;

F = { (RegNo → SName Gen PR), (RegNo Phone → SName Gen PR) }

Among these two FDs, the first one which is having RegNo as the LHS is violating the rule of BCNF. The reason is, the determinant RegNo of the FD is not a key for this relation. Hence, the above table is not in BCNF.

How do we convert a table STUDENT into BCNF table?

We have to decompose the table into two or more tables as discussed in 2NF, and 3NF. For this, we can consider the set F of FDs already listed above.

Hence, the resultant schemas would be;

• STUDENT(RegNo, SName, Gen, PR)

• STU_PHONE(RegNo, Phone)

Now, the relation STUDENT with the FD {RegNo → SName Gen PR} satisfies,

1NF (because no repeating group of values/no multivalued attributes),

2NF (because no partial key FD as the key is simple attribute),

3NF (because there is no transitive FD since there is no FDs with non-key attribute on the LHS), BCNF (because there is only one key for the relation).

For the relation, STU_PHONE the key is trivial. That is, composite key (RegNo, Phone). Hence, it is holding all the Normal Forms in it.

Note: The relation schema with the following properties need not be checked for every normal form conditions;

1. If only two attributes are present

2. If more than one attribute present and the key is simple attribute.

A relation schema which is in 3NF but not in BCNF

Let us take the following table, DEALER for our discussion. This table stores the information about various dealers for various products. And it stores the dealer details along with the products we purchase from them and the product count. According to the sample table given below, it is very evident that same products may be purchased from different dealers.

Dealer_ID	DName	Product_ID	Quantity
D101	Sun Flower	P101	100
D101	Sun Flower	P103	150
D102	Market One	P102	200
D105	A One	P101	100
D104	Indian Curry	P110	250
D104	Indian Curry	P102	50

Table 2 – DEALER

For this table, let us identify the set of Functional Dependencies;

1. Attribute Dealer_ID cannot be a determinant for this table. Because, it does not uniquely identify any other attribute other than dealer name (DName). Hence,

Dealer_ID → DName

2. Attribute DName determine the value of Dealer_ID. That is, dealers have unique names. Hence,

DName → Dealer_ID

3. Attribute Product_ID cannot uniquely identify anything. Because, same products purchased from different dealers in different quantify.

If we go on analyzing this, we would get the following set of FDs;

Dealer_ID → DName

DName → Dealer_ID

Dealer_ID Product_ID → DName Quantity

DName Product_ID → Dealer_ID Quantity

From the above set of FDs, we can derive Two Candidate Keys. Those are;

(Dealer_ID, Product_ID) and (DName, Product_ID)

From the derived FDs, it is clear that the relation DEALER is in 3NF, because, no Transitive Functional Dependency is held.

According to the properties of BCNF, the relation DEALER must have FDs with the LHS as candidate keys. But, for DEALER among the set of FDs, we have the FDs Dealer_ID → DName and DName → Dealer_ID where neither Dealer_ID nor DName are the candidate keys. Thus, these two FDs violate the rules of BCNF. Hence, DEALER is not in BCNF.

How do we convert DEALER into BCNF table?

We need to decompose DEALER using the FDs which are violating the BCNF rules. Thus, we get following schemas as a result of decomposition.

1. DEALER1(Dealer_ID, DName)
2. DEALER_PROD(Dealer_ID, Product_ID, Quantity)

Relation DEALER1 satisfies all the Normal Forms.

Relation DEALER_PROD has the following set of FDs;

Dealer_ID Product_ID →  Quantity

As there are no other FDs, the relation DEALER_PROD is in BCNF.

*********

Related Links

• Go to Normal Form - Home page

• Go to Normalization - Home page

• Go to Normalization Solved Exercises - Home page

• Go to Comparison of All Normal Forms page

Explain Boyce-Codd Normal Form (BCNF) with example in Normaliation DBMS