Query (complexity)

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

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

$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.