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

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

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

${displaystyle I: {mbox {STRUC}} [сигма] o {mbox {STRUC}} [au]}$

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

Запросы, не зависящие от порядка

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

Рекомендации