In
descriptive complexity
Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the formal language, languages in them. For example, PH (complexity), PH, ...
, a query is a mapping from structures of one
signature
A signature (; from , "to sign") is a depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. Signatures are often, but not always, Handwriting, handwritt ...
to structures of another vocabulary.
Neil Immerman, in his book Descriptive Complexity,
"use
the concept of query as the fundamental paradigm of computation" (p. 17).
Given signatures
and
, we define the set of
structure
A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such as ...
s on each language,