Zapytanie (złożoność)

W złożoności opisowej zapytanie jest odwzorowaniem struktur jednego podpisu na struktury innego słownictwa. Neil Immerman w swojej książce Descriptive Complexity „wykorzystuje pojęcie zapytania jako podstawowego paradygmatu obliczeń” (s. 17).

Biorąc pod uwagę sygnatury $\ displaystyle$ τ $\ tau}$ , definiujemy zestaw struktur w każdym języku, ${\ Displaystyle {\ mbox {STRUC}} [\ sigma]}$ i ${\ Displaystyle {\ mbox {STRUC}} [\ tau ]}$ . Zapytanie jest zatem dowolnym mapowaniem

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

Teorię złożoności obliczeniowej można następnie sformułować w kategoriach mocy logiki matematycznej niezbędnej do wyrażenia danego zapytania.

Zapytania niezależne od kolejności

Zapytanie jest niezależne od kolejności, jeśli kolejność obiektów w strukturze nie wpływa na wyniki zapytania. W bazach danych zapytania te odpowiadają zapytaniom rodzajowym (Immerman 1999, s. 18). Zapytanie $_$ dowolnych $_ {\ mathfrak {A}}}$ i ${\ Displaystyle {\ mathfrak {B}}}$ .