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, "use[s] the concept of query as the fundamental paradigm of computation" (p. 17).

Given signatures σ {\displaystyle \sigma } and τ {\displaystyle \tau } , we define the set of structures on each language, STRUC [ σ ] {\displaystyle {\mbox{STRUC}}[\sigma ]} and STRUC [ τ ] {\displaystyle {\mbox{STRUC}}[\tau ]} . A query is then any mapping

I : STRUC [ σ ] → STRUC [ τ ] {\displaystyle I:{\mbox{STRUC}}[\sigma ]\to {\mbox{STRUC}}[\tau ]}

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