Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

A good early paper on the topic of bitmap indexes is "Bit Transposed Files" by Wong et al, published in 1985.

In all the query-decoding examples, it is left to the reader to understand how each decoded query is derived. One of the examples is too complex for me to figure out.

In section 5.3.3.b, the paper shows how the BTF query processor would decode the query to find all dogs receiving more than 30 dosage units.

In BTF, the query would look like this:

dosage[>30]

We are told that

Attribute dosage is encoded as a Composite unary with 3 fields of 6 bits. Assume dosage 30 is encoded as 000111,000011,011111."

Thus the paper claims

the query can be translated to

dosage ((b14 & b7 & b4) | (b14 & b8) | b15)

and says no more about it.

How does that work?

By my understanding, the decoded query dosage (b14 & b7 & b4) should alone select the correct values, if we interpret "more than" as "more than or equal to".

My attempt at understanding the solution follows.

Understanding the encoded value

I quote literal values in decimal unless specified otherwise.

We are told that the encoding represents the value 30.

We should remember a unary field that encodes value n+1 sets all the bits that encode n plus the next rightmost bit. A 0 is encoded by setting no bits.

To help me understand the derivation, I created a table that maps each bit of the attribute encoded value (u for unary) to its field value (d for decimal) and to its attribute ordinal position (n for n-th).

The table looks like this:

n 17 16 15 14 13 12    11 10  9  8  7  6     5  4  3  2  1  0

d  6  5  4  3  2  1     6  5  4  3  2  1     6  5  4  3  2  1

u  0  0  0  1  1  1     0  0  0  0  1  1     0  1  1  1  1  1

We can see from the table that the the values of the fields from left to right are (3, 2, and 5) respectively.

We know that 3 * 2 * 5 = 30, so we might assume that the product of the field values gives the attribute value.

If this is true, then:

  • the order of the fields should be insignificant.
  • 6 * 6 * 6 = 216 is the biggest encodable value.
  • each value might have multiple encodings.

Section 4 (Bit Transposition) states that attribute dosage has 200 distinct values, so all attribute values are encodable.

Understanding the decoded query

The decoded query ORs together three expressions.

The first expression (b14 & b7 & b4) selects attributes whose:

  • first field encodes 3, 4, 5, or 6.
  • second field encodes 2, 3, 4, 5, or 6
  • third field encodes 5 or 6.

The expression selects dosage values greater than 30, but selects dosages of 30 as well. If the aim is to find values strictly greater than 30, then the expression would select values that don't match the BTF query.

The second expression (14 & b8) and the third expression (b15) don't select bits for some fields, so these fields could have any value.

If this is true, then the whole expression would select dogs who received a dose of 0 and many other values less than 30.

By my understanding, the decoded query would select many values that don't match the BTF query.

share|improve this question
    
I was unsure about how much understanding of the paper to assume. Of course, if I had full understanding, I wouldn't ask the question! If you have read the paper and my question is unclear, I will try to make it clearer. –  Iain Elder May 7 '13 at 19:56
1  
By "composite", they state that they mean a radix system. So (b14 & b7 & b4) means abc where a>=3 and b>=2 and c>=5, while (b14 & b8) means abc where a>=3 and b>=3 and (b15) means abc where a>=4. So you have 325 and 33c and 4bc, all greater (or equal) to 325. –  ypercube May 8 '13 at 9:38
2  
In other words, 30 = 3 * 2 * 5 is just a coincidence. The number 30 is encoded as 325 where 3, 2 and 5 are just digits in a base-6 system. –  ypercube May 8 '13 at 10:02
    
@ypercube That explains why the three expressions are ORed together. But 325 base 6 is 125 in base 10, no? 5 * (6 ^ 0) + 2 * (6 ^ 1) + 3 * (6 ^ 2) = 5 + 12 + 108 = 125 So I don't see a direct relationship to a dosage value of 30. –  Iain Elder May 9 '13 at 12:14
1  
So, that explains it. It could start with 0, then 1/20, 1/10, 3/20, 1/5, ..., 1, 5/4, 3/2, 7/4, 2, ..., 29, 29.5, 30, ... It is not mandatory to have a linear relation between dosage and the enconding. Only that it is ascending. –  ypercube May 9 '13 at 12:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.