TOPICS (Click to Navigate)
Friday, 19 February 2016
Database Indexing - Solved Exercise set 1
Question / Exercise:
Consider a relation Faculty with the relational schema Faculty (FID, FName, Dept, Salary). Here FID stores the values 1, 2, 3, … , n as faculty identification numbers.
The following query is the most frequent one;
SELECT * FROM Faculty WHERE FID > v1 AND FID < v2;
Assume that Faculty does not have any indexes. We need to create necessary indexes. Which of the following indexes is best suited for executing the above query efficiently?
(a) A sparse primary index on FID (b) A dense primary index on FID
Sparse primary index – an index with few FIDs listed sparsely in the index table. You can reach the record in the data file by choosing the record’s pointer whose value is the greatest below the searching value. Sparse index is smaller than dense index.
Dense primary index – an index with each FIDs listed densely in the index table for each record in the data file. It has one to one relationship between index table and data file. Dense index is larger than sparse index.
Primary index - The data file is sequentially ordered by an ordering key field, and the indexing field is built on the ordering key field.
Sparse primary index is best suited for handling the above query. When executing the query we search for v1 in the index table, and find an index entry with the smallest value that is greater than v1. Then we use the pointer value in that record to find the location (address) of the record in the data file. We then do a simple sequential scan in the data file from that point (address) till we reach a record with FID value greater than v2. Refer the example given below.
In simple terms, sparse index would be helpful when compared with dense index in the case of range queries.
Dense index occupies all five entries in the index table and makes index table bigger. Dense index is good for point queries.
Go back to the Indexing and Tuning –Solved exercises page
SQL Exercises for Beginners / Simple SQL Exercises with Answers / Solved SQL exercises / SQL solved exercises with simple conditions / So...
Advanced concepts in DBMS Advanced Database Topics (Click on the links to navigate) Advanced Concepts in D...
Set of solved exercises in Normalization / Normalization Solved Examples / How to find candidate keys, and primary keys in database? /...
Query Processing in DBMS / Steps involved in Query Processing in DBMS / How is a query gets processed in a Database Management System? / Q...