/    /  DBMS – Bitmap Indices

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.NoD.NoD.NameF.NameQual
52221CSEMMPh.D
52422ITNNM.Tech
52522ITVVM.Tech
52723ECEPPM.Tech
53023ECEQQM.Tech
53324MERRPh.D
53524MESSPh.D
53725EEETTM.Tech
53925EEEWWM.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’ ;

  1.  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.

 

DeptBitmap
CSE100 000 000
IT011 000 000
ECE000 110 000
ME000 001 100
EEE000 000 011
  1. Consider the ‘QUAL’ attribute.
DeptBitmap
CSE100 000 000
IT011 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

Bitmap Indices