Exercise 1.9

For a conjunctive query, is processing postings lists in order of size guaranteed to be optimal? Explain why it is, or give an example where it isn’t.

Answer:

Processing conjunctive query in order of size is not guarantee to be optimal because the distributive law proof that addition in any direction has always produce exactly same result and the representation of linear growth tell that any addition function of size is always exactly product total of length of its element. For example, (a + b) + c is equivalent with a + (b + c).