クエリ（複雑さ）

記述的複雑性において、クエリとは、あるシグネチャの構造から別の語彙の構造への マッピングです。Neil Immerman は、著書『記述的複雑性^』[1]の中で、 「クエリの概念を計算の基本的なパラダイムとして使用しています」(p. 17)。

署名とが与えられた場合、各言語上の構造の集合とを定義する。クエリは任意のマッピングである。 ${\displaystyle \sigma}$${\displaystyle \tau}$${\displaystyle {\mbox{STRUC}}[\sigma ]}$${\displaystyle {\mbox{STRUC}}[\tau ]}$

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

計算複雑性理論は、特定のクエリを表現するために必要な数学的論理の力という観点から表現することができます。

クエリは、構造内のオブジェクトの順序がクエリの結果に影響しない場合は順序に依存しません。データベースでは、これらのクエリは汎用クエリに対応します (Immerman 1999、p. 18)。クエリが順序に依存しない場合、それは任意の同型構造およびの場合に限ります。 ${\displaystyle I({\mathfrak {A}})\equiv I({\mathfrak {B}})}$${\displaystyle {\mathfrak {A}}}$${\displaystyle {\mathfrak {B}}}$