Запрос (сложность)

В описательной сложности запрос представляет собой отображение структур одной сигнатуры в структуры другого словаря. Нил Иммерман в своей книге «Описательная сложность» «использовать концепцию запроса как фундаментальную парадигму вычислений» (стр. 17).

Данные подписи $\sigma$ и $\tau$, мы определяем набор структур на каждом языке, ${\mbox{STRUC}}[\sigma ]$ и ${\mbox{STRUC}}[\tau ]$. Тогда запрос — это любое отображение

$I:{\mbox{STRUC}}[\sigma ]\to {\mbox{STRUC}}[\tau ]$

Тогда теорию сложности вычислений можно сформулировать с точки зрения мощности математической логики, необходимой для выражения данного запроса.

Независимые от заказа запросы

Запрос не зависит от порядка , если порядок объектов в структуре не влияет на результаты запроса. В базах данных эти запросы соответствуют общим запросам (Immerman 1999, стр. 18). Запрос не зависит от порядка, если и только если $I({\mathfrak {A}})\equiv I({\mathfrak {B}})$ для любых изоморфных структур ${\mathfrak {A}}$ и ${\mathfrak {B}}$.