In order to answer it we develop a Kolmogorov complexity based measure of expressive power of Boolean query languages over finite structures. This turns the above informal question into a precisely defined mathematical one. This notion gives a meaningful definition of the expressive power of a Boolean query language in a single finite database.
The notion of Kolmogorov expressive power of a Boolean query language L in a finite database A is defined by considering two values: the Kolmogorov complexity of the isomorphism type of A, equal to the length of the shortest binary description of this type, and the number of bits of this description that can be reconstructed from truth values of all queries from L in A. The closer is the second value to the first, the more expressive is the query language.
The such defined notion has been shown to be strongly related to the possibility of optimization of queries. Namely, it appears that if the fixed variable fragments of fixpoint logic give only a little information about structures, i.e., a sub-logarithmic amount, then some very effective methods of optimization of fixpoint queries are possible.