Bitmap Indices
Bitmap Indices are a specialized type of index designed for easy querying on multiple keys, although each bitmap index is built on a single key.
For bitmap indices to be used, the records must be numbered from ‘0’.
Given a number ‘n’, it must be easy to retrieve the record numbered ‘n’.
If there are ‘k’ number of conditions in the ‘where’ clause of SQL query, then ‘k’ number of bitmap indices have to be created.
This concept is useful, when
- Records are fixed in size
- Records are allocated on consecutive blocks of a file.
- The record number can be translated easily into a block number and a number that identifies the record within the block.
Consider the ‘FACULTY’ relation :
F.No | D.No | D.Name | F.Name | Qual |
522 | 21 | CSE | MM | Ph.D |
524 | 22 | IT | NN | M.Tech |
525 | 22 | IT | VV | M.Tech |
527 | 23 | ECE | PP | M.Tech |
530 | 23 | ECE | M.Tech | |
533 | 24 | ME | RR | Ph.D |
535 | 24 | ME | SS | Ph.D |
537 | 25 | EEE | TT | M.Tech |
539 | 25 | EEE | WW | M.Tech |
Example-1:
Apply ‘bitmap method’ to answer the following SQL query.
“Find the FNames, who are working in ECE department and having MTech qualification.”
In general, the SQL query is :
Select FName
From FACULTY
Where D-Name = ‘ECE’ and Qual = ‘MTech’ ;
- Consider the D-Name attribute : Here, first take the D-Name attribute, then for every department, put ‘1’ for that department and ‘0’ for others, in the place of column values.
Dept | Bitmap |
CSE | 100 000 000 |
IT | 011 000 000 |
ECE | 000 110 000 |
ME | 000 001 100 |
EEE | 000 000 011 |
- Consider the ‘QUAL’ attribute.
Dept | Bitmap |
CSE | 100 000 000 |
IT | 011 000 000 |
Here, we need
For ‘ECE’ department : 000 110 000
For ‘MTech’ qualification : 011 110 011
The intersection operator between above two bitmaps is :
000 110 000
Here, ‘1’ is in the fourth and fifth tuples.
So, consider the FNames from Fourth and Fifth tuples, which gives the output.
Output : PP QQ
This way, for SQL queries having multiple conditions, one can get the output using ‘Bitmap index method’.
Reference Link