クエリ（複雑さ）

記述的複雑性において、クエリとは、あるシグネチャの構造から別の語彙の構造への マッピングです。ニール・イマーマンは著書『記述的複雑性』^[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}}}$

参考文献

1. ニール・イマーマン (1999).記述的複雑性. ニューヨーク: シュプリンガー・ニューヨーク. ISBN 9781461205395. OCLC  853271745。