## Kolmogorov Expressive Power Of Boolean Query Languages

- DIMACS Center - Room 431
- Busch Campus
- Piscataway, New Jersey
- November 20, 1995 at 10:30 AM

### Abstract:

We address the question "How much of the information stored in a given
database can be retrieved by all Boolean queries in a given query
language?".
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.