14.24

An existence bitmap has a bit for each record position, with the bit set to $1$ if the record exists, and $0$ if there is no record at that position (for example, if the record were deleted). Show how to compute the existence bitmap from other bitmaps. Make sure that your technique works even in the presence of null values by using a bitmap for the value null.

---

Let $r(A,B,C)$ be a relation. Suppose there is a bitmap index on the attribute $A$. Suppose the attribute $A$ can have 2 distinct values and can also be null. Thus the bitmap index on the attribute $A$ is going to have 3 bitmaps, namely: $S_1,S_2,S_{null}$.

Thus, the existence bitmap can be computed as follows:-

$$S_1\vee S_2\vee S_{null}$$

where $\vee$ denotes the bitwise or operator.