Query (complexity)

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, ${\displaystyle {\mbox{STRUC}}[\sigma ]}$ and ${\displaystyle {\mbox{STRUC}}[\tau ]}$. A query is then any mapping

...
Wikipedia