GeezerVison

In descriptive complexity, a query is a mapping from structures of one signature to structures of another vocabulary. Neil Immerman, in his book Descriptive Complexity,^[1] "use[s] the concept of query as the fundamental paradigm of computation" (p. 17).

Given signatures $\sigma$ and $\tau$, we define the set of structures on each language, $\text{STRUC}\left[\sigma \right]$ and $\text{STRUC}\left[\tau \right]$. A query is then any mapping

$I:\text{STRUC}\left[\sigma \right]\to \text{STRUC}\left[\tau \right]$

Computational complexity theory can then be phrased in terms of the power of the mathematical logic necessary to express a given query.

A query is order-independent if the ordering of objects in the structure does not affect the results of the query. In databases, these queries correspond to generic queries (Immerman 1999, p. 18). A query is order-independent iff $I\left(𝔄\right)\equiv I\left(𝔅\right)$ for any isomorphic structures $𝔄$ and $𝔅$.