MGM’s College of engineering and Technology, Kamothe, Navi Mumbai

Department of Information Technology

Course Code: ITC304 Course Name: Database Management System
Assignment V
Class: SE AY: 2019-2020
Date of Issue:10/10/19 Date of Submission: 16/10/19 Date of Return: 19/10/19
Q. Question Module Bloom’s Program CO
No Taxanomy Indicato
level r (PI)
Q1. Fill in the blanks.
(a) If every non key attribute is functionally dependent on the primary 5 1 1.7.1 CO5
key, then the relation will be in__________________
(b) If the index is created on the basis of the primary key of the table, 6 1 1.7.1 CO6
then it is known as ______________
(c) Indexing based on a sorted order of values are 6 1 1.7.1 CO6
called________________
(d) While insertion in a sparse index, we assume that index stores an 6 1 1.7.1 CO6
entry for each_____________.
(e) Indices having two or more levels are called______ 6 1 1.7.1 CO6

Q2. Choose Correct Options.

(a) In 2NF 5 1 1.7.1 CO5

i) No functional dependencies exist.
ii) No multivalued dependencies exist.
iii) No partial functional dependencies exist
iv) No partial multivalued dependencies exist.
(b) Primary indexes, secondary indexes and cluster indexes are all 6 1 1.7.1 CO6
types of
i)ordered indexes ii)unordered indexes
iii)linear indexes iv)relative search indexes
(c) Hashing technique which allocates fixed number of buckets is 6 1 1.7.1 CO6
classified as
i)dynamic hashing ii)static hashing
iii)external hashing iv) internal hashing
(d) Functional Dependencies are the types of constraints that are based 5 1 1.7.1 CO5
on______
i) Key ii)Key revisited
iii) Superset key iii)None of the mentioned
(e) What is a bucket overflow? 6 1 1.7.1 CO6
i) When a bucket does not have enough space
ii) There are insufficient buckets
iii) When Bucket skew occurs
iv) All of the mentioned
Q3. State whether the following statements are true or false (Give Reasons)

(a) A hash index organizes the search keys, with their associated 6 1 1.7.1 CO6
pointers into a hash file structure.

(b) If a relation is in 3NF, then it is also in BCNF. 5 1 1.7.1 CO5

(c) Normalization is the process of removing anomalies from database 5 1 1.7.1 CO5
design.
Q4. Name or define or design the following.
 (a) Functional dependency 5 1 1.7.1 CO5

(b) Normalization 5 1 1.7.1 CO5

(c) Static hashing 6 1 1.7.1 CO6

Q5. Answer the following questions in brief. (20 to 30 words)

(a) List all FDs satisfied by the following table T. 5 3 1.7.1 CO5

A B C D

A1 B1 C1 D1

A1 B1 C2 D2

A1 B2 C2 D1

A1 B2 C4 D4

(b) What are the different guidelines for designing relational schema? 5 4 1.7.1 CO5

(c) Explain 1NF, 2NF, 3NF and BCNF with example. 5 2 1.7.1 CO5

Q6. Answer the following questions in brief. (50 to 70 words)

(a) What are the different operations on files? 6 2 1.7.1 CO6

bbbb What are the different hashing techniques? 6 2 1.7.1 CO6

(c ) What are the different types of indexes? 6 2 1.7.1 CO6

Q7. Think and Answer. (200 words)

(a) When is it preferable to use a dense index rather than a sparse 6 4 2.5.1 CO5
index? Explain your answer.
(b) Since indices speed query processing, why might they not be kept 6 4 2.5.1 CO5
on several search keys? List as many reasons as possible.
Q8. My Ideas. (200 words)

(a) How insertion anomaly occurs if the table is not normalized? 5 4 2.5.1 CO5

(b) How updation anomaly occurs if the table is not normalized? 5 4 1.7.1 CO5

*As per Blooms Taxonomy

 MGM’s College of engineering and Technology, Kamothe, Navi Mumbai
Department of Information Technology
Course Code: ITC304 Course Name: Database Management System
Assignment V Solution
Class: SE AY: 2019-2020

Q. Question
No
Q1. Fill in the blanks.
(a) If every non key attribute is functionally dependent on the primary key, then the relation will be in
Second Normal Form
(b) If the index is created on the basis of the primary key of the table, then it is known as
Primary indexing.
(c) Indexing based on a sorted order of values are called Ordered indices.

(d) While insertion in a sparse index, we assume that index stores an entry for each search key value.

(e) Indices having two or more levels are called multilevel indices.

Q2. Choose Correct Options.

(a) In 2NF
i) No functional dependencies exist.
ii) No multivalued dependencies exist.
iii) No partial functional dependencies exist
iv) No partial multivalued dependencies exist.
(b) Primary indexes, secondary indexes and cluster indexes are all types of
i)ordered indexes ii)unordered indexes
iii)linear indexes iv)relative search indexes
(c) Hashing technique which allocates fixed number of buckets is classified as
i)dynamic hashing ii)static hashing
iii)external hashing iv) internal hashing
(d) Functional Dependencies are the types of constraints that are based on______
i) Key ii)Key revisited
iii) Superset key iii)None of the mentioned

(e) What is a bucket overflow?

i) When a bucket does not have enough space
ii) There are insufficient buckets
iii) When Bucket skew occurs
iv) All of the mentioned
Q3. State whether the following statements are true or false (Give Reasons)
(a) A hash index organizes the search keys, with their associated pointers into a hash file structure. true

(b) If a relation is in 3NF, then it is also in BCNF. false

(c) Normalization is the process of removing anomalies from database design. true
Q4. Name or define or design the following.
(a) Functional dependency
A functional dependency (FD) is a relationship between two attributes, typically between the PK
and other non-key attributes within a table. For any relation R, attribute Y is functionally dependent
on attribute X (usually the PK), if for every valid instance of X, that value of X uniquely determines
the value of Y.
(b) Normalization
Normalization is a database design technique which organizes tables in a manner that reduces
redundancy and dependency of data. It divides larger tables to smaller tables and links them using
relationships.
(c) Static hashing
In static hashing, when a search-key value is provided, the hash function always computes the same
address. For example, if mod-4 hash function is used, then it shall generate only 5 values.
Q5. Answer the following questions in brief. (20 to 30 words)
(a) List all FDs satisfied by the following table T.

A B C D

A1 B1 C1 D1

A1 B1 C2 D2

A1 B2 C2 D1

A1 B2 C4 D4

B C, D A, B A, C A

(b) What are the different guidelines for designing relational schema?

Guideline 1
Do not combine attributes from multiple entity types and relationship types into a single relation.
Guideline 2
Design the base relation schemas so that no insertion, deletion, or modification anomalies are present
in the relations.
Guideline 3
As far as possible, avoid placing attributes in a base relation whose values may frequently be NULL.
If NULLs are unavoidable, make sure that they apply in exceptional cases only and do not apply to a
majority of tuples in the relation.
Guideline 4
Design relation schemas so that they can be joined with equality conditions on attributes that are
appropriately related (primary key, foreign key) pairs in a way that guarantees that no spurious tuples
are generated. Avoid relations that contain matching attributes that are not (foreign key, primary key)
combinations because joining on such attributes may produce spurious tuples.
(c) Explain 1NF, 2NF, 3NF and BCNF with example. Normalize upto 3NF. A and B are the primary
keys.

1. First Normal Form

First Normal Form is defined in the definition of relations (tables) itself. This rule defines that all the
attributes in a relation must have atomic domains. The values in an atomic domain are indivisible
units.

We re-arrange the relation (table) as below, to convert it to First Normal Form.

Each attribute must contain only a single value from its pre-defined domain.

2.Second Normal Form

Before we learn about the second normal form, we need to understand the following −
 Prime attribute − An attribute, which is a part of the candidate-key, is known as a prime
attribute.
 Non-prime attribute − An attribute, which is not a part of the prime-key, is said to be a
non-prime attribute.
If we follow second normal form, then every non-prime attribute should be fully functionally
dependent on prime key attribute. That is, if X → A holds, then there should not be any proper subset
Y of X, for which Y → A also holds true.

We see here in Student_Project relation that the prime key attributes are Stu_ID and Proj_ID.
According to the rule, non-key attributes, i.e. Stu_Name and Proj_Name must be dependent upon
both and not on any of the prime key attribute individually. But we find that Stu_Name can be
identified by Stu_ID and Proj_Name can be identified by Proj_ID independently. This is
called partial dependency, which is not allowed in Second Normal Form.

We broke the relation in two as depicted in the above picture. So there exists no partial dependency.
3.Third Normal Form
For a relation to be in Third Normal Form, it must be in Second Normal form and the following must
satisfy −

 No non-prime attribute is transitively dependent on prime key attribute.

 For any non-trivial functional dependency, X → A, then either −
o X is a superkey or,
o A is prime attribute.

We find that in the above Student_detail relation, Stu_ID is the key and only prime key attribute. We
find that City can be identified by Stu_ID as well as Zip itself. Neither Zip is a superkey nor is City a
prime attribute. Additionally, Stu_ID → Zip → City, so there exists transitive dependency.
To bring this relation into third normal form, we break the relation into two relations as follows −
 4.Boyce-Codd Normal Form
Boyce-Codd Normal Form (BCNF) is an extension of Third Normal Form on strict terms. BCNF
states that −

 For any non-trivial functional dependency, X → A, X must be a super-key.

In the above image, Stu_ID is the super-key in the relation Student_Detail and Zip is the super-key in
the relation ZipCodes. So,
Stu_ID → Stu_Name, Zip
Stu_ID → Stu_Name, Zip
and
Zip → City
Q6. Answer the following questions in brief. (50 to 70 words)
(a) What are the different operations on files?

File Operations
Operations on database files can be broadly classified into two categories −

 Update Operations
 Retrieval Operations

Update operations change the data values by insertion, deletion, or update. Retrieval operations, on
the other hand, do not alter the data but retrieve them after optional conditional filtering.
In both types of operations, selection plays a significant role. Other than creation and deletion of a file,
there could be several operations, which can be done on files.

 Open − A file can be opened in one of the two modes, read mode or write mode. In read
mode, the operating system does not allow anyone to alter data. In other words, data is read
only. Files opened in read mode can be shared among several entities. Write mode allows data
modification. Files opened in write mode can be read but cannot be shared.
 Locate − Every file has a file pointer, which tells the current position where the data is to be
read or written. This pointer can be adjusted accordingly. Using find (seek) operation, it can
be moved forward or backward.
 Read − By default, when files are opened in read mode, the file pointer points to the
beginning of the file. There are options where the user can tell the operating system where to
locate the file pointer at the time of opening a file. The very next data to the file pointer is
read.
 Write − User can select to open a file in write mode, which enables them to edit its contents.
It can be deletion, insertion, or modification. The file pointer can be located at the time of
opening or can be dynamically changed if the operating system allows to do so.
 Close − This is the most important operation from the operating system’s point of view.
When a request to close a file is generated, the operating system
o removes all the locks (if in shared mode),
o saves the data (if altered) to the secondary storage media, and
o releases all the buffers and file handlers associated with the file.

bbbb What are the different hashing techniques?

A.Static Hashing
In the static hashing, the resultant data bucket address will always remain the same. Therefore, if you
generate an address for say Student_ID = 10 using hashing function mod(3), the resultant bucket
address will always be 1. So, you will not see any change in the bucket address. Therefore, in this
 static hashing method, the number of data buckets in memory always remains constant.

A.Static hashing is further divided into

1. Open hashing
2. Close hashing.

1.Open Hashing
In Open hashing method, Instead of overwriting older one the next available data block is used to enter
the new record, This method is also known as linear probing.

For example, A2 is a new record which you wants to insert. The hash function generates address as
222. But it is already occupied by some other value. That's why the system looks for the next data
bucket 501 and assigns A2 to it.

2.Close Hashing
In the close hashing method, when buckets are full, a new bucket is allocated for the same hash and
result are linked after the previous one.

B.Dynamic Hashing
Dynamic hashing offers a mechanism in which data buckets are added and removed dynamically and
on demand. In this hashing, the hash function helps you to create a large number of values.
(c ) What are the different types of indexes?
Indexing can be of the following types −
 Primary Index − Primary index is defined on an ordered data file. The data file is ordered on
a key field. The key field is generally the primary key of the relation.
 Secondary Index − Secondary index may be generated from a field which is a candidate key
and has a unique value in every record, or a non-key with duplicate values.
 Clustering Index − Clustering index is defined on an ordered data file. The data file is
ordered on a non-key field.
Ordered Indexing is of two types −
 Dense Index
 Sparse Index
Dense Index
In dense index, there is an index record for every search key value in the database. This makes
searching faster but requires more space to store index records itself. Index records contain search
key value and a pointer to the actual record on the disk.

Sparse Index
In sparse index, index records are not created for every search key. An index record here contains a
search key and an actual pointer to the data on the disk. To search a record, we first proceed by index
record and reach at the actual location of the data. If the data we are looking for is not where we
directly reach by following the index, then the system starts sequential search until the desired data is
found.

Multilevel Index
Index records comprise search-key values and data pointers. Multilevel index is stored on the disk
along with the actual database files. As the size of the database grows, so does the size of the indices.
There is an immense need to keep the index records in the main memory so as to speed up the search
operations. If single-level index is used, then a large size index cannot be kept in memory which
leads to multiple disk accesses.
 Multi-level Index helps in breaking down the index into several smaller indices in order to make the
outermost level so small that it can be saved in a single disk block, which can easily be
accommodated anywhere in the main memory.

Q7. Think and Answer. (200 words)

(a) When is it preferable to use a dense index rather than a sparse index? Explain your answer.
It is preferable to use a dense index instead of a sparse index when the file is not sorted on the
indexed field (such as when the index is a secondary index) or when the index file is small
compared to the size of memory
(b) Since indices speed query processing, why might they not be kept on several search keys? List as
many reasons as possible.
Reasons for not keeping several search indices include:
a. Every index requires additional CPU time and disk I/O overhead during
inserts and deletions.
b. Indices on non-primary keys might have to be changed on updates, although an index on the
primary key might not (this is because updates
typically do not modify the primary key attributes).
c. Each extra index requires additional storage space.
d. For queries which involve conditions on several search keys, efficiency
might not be bad even if only some of the keys have indices on them.
Therefore database performance is improved less by adding indices when
many indices already exist
Q8. My Ideas. (200 words)
(a) How insertion anomaly occurs if the table is not normalized?
Insertion anomalies: To insert a new patient particular that makes an appointment with the designated
Doctor, we need to enter the correct detail for the staff. For example, to insert the details of new
patient in patientNo, patientName and an appointment, we must enter the correct details of the doctor
(staffNo, dentistName) so that the patient details are consistent with values for the designated Doctor
for example. To enter new patient data that doesn’t have Doctor to be assigned we can’t insert NULL
values for the primary key.
(b) How updation anomaly occurs if the table is not normalized?

Modification anomalies: With redundant data, when we want to change the value of one columns of a
particular Dentist, for example the dentistName, we must update all the Dentist records that assigned
to the particular patient otherwise the database will become inconsistent. We also need to modify the
appointment schedules because different Dentist has different schedules.

*As per Blooms Taxonomy