select * from R where a=1
select * from R where d=2
select * from R where b=3 and c=4
select * from R where a=5 and b=6 and c=7

A relation with n attributes has 2ⁿ different query types.

Different query types have different costs   (different no. of *'s)

Cost(Q) = 2^s   where s = ∑_{i ∉ Q} d_i     (alternatively Cost(Q) = ∏_{i ∉ Q} 2^d_i)

Query distribution gives probability p_Q of asking each query type Q.