Page 222 - DCAP603_DATAWARE_HOUSING_AND_DATAMINING

Data Warehousing and Data Mining

notes ati = 0.01
itime = 0.07

total number of tuples = 10,000
step 1) 1500 = 10,000 * found set * (0.1 + 0.01 + 0.07)
step 2) 1500 = 1800 * found set
step 3) found set = 1500/1800 = 83.33 %
From the result, we can conclude that the full scan technique outperforms the RID index technique
when there is more than or equal to 83.33 % found set in the relation. Therefore, DBMSs shall use
full scan technique instead of the RID index technique.

11.4.6 BitMap index technique

The BitMap Index technique saves more spaces than the RID index technique that stores bits
instead of record identification. The total time that is required to process a query is 1/8 of access
time of index level and access time of selective table level.

The response time of a query in BitMap is
CostModel(sc) = 1/8 * ((|sc| * att) + (|sc| * ati)) +(|sc| * itime(bm)))
Where,
sc = Selective conditions
|sc| = The total number of found sets in selective conditions

m = Total number of tuples in the relation
att = Access time per tuple
itime = Instruction time of an algorithm
ati = Access time per index

bm = BitMap index algorithm
The response time of a query seems faster than the RID index technique. However, the instruction
time of a BitMap index has more steps than the RID index algorithm.

Example:
Let |sc| = found set * total number of tuples = 10% * 10,000 = 1,000
Let att = 0.1
Let ati = 0.01

Let itime(bm) = 1.2
The response time of a query:
= 1/8 (|sc| * (att + ati + itime(bm)))

= 1/8 (1,000 * (0.1 + 0.01 + 1.2)) = 164 sec..
If the foundset is 20%, then the response time of a query will be:
= 1/8(2,000 * (0.1 + 0.01 + 1.2)) = 382 sec. and the response times are as summarized in Table
11.6.

216 LoveLy professionaL university