Query (complexity)

In descriptive complexity, a query is a mapping from structures of one signature to structures of another vocabulary. Neil Immerman, in his book Descriptive Complexity,^[1] "use[s] the concept of query as the fundamental paradigm of computation" (p. 17).

Given signatures ${\displaystyle \sigma }${\displaystyle \sigma } and ${\displaystyle \tau }${\displaystyle \tau }, we define the set of structures on each language, ${\displaystyle {\mbox{STRUC}}[\sigma ]}${\displaystyle {\mbox{STRUC}}[\sigma ]} and ${\displaystyle {\mbox{STRUC}}[\tau ]}${\displaystyle {\mbox{STRUC}}[\tau ]}. A query is then any mapping

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

Computational complexity theory can then be phrased in terms of the power of the mathematical logic necessary to express a given query.

A query is order-independent if the ordering of objects in the structure does not affect the results of the query. In databases, these queries correspond to generic queries (Immerman 1999, p. 18). A query is order-independent iff ${\displaystyle I({\mathfrak {A}})\equiv I({\mathfrak {B}})}${\displaystyle I({\mathfrak {A}})\equiv I({\mathfrak {B}})} for any isomorphic structures ${\displaystyle {\mathfrak {A}}}${\displaystyle {\mathfrak {A}}} and ${\displaystyle {\mathfrak {B}}}${\displaystyle {\mathfrak {B}}}.

• Descriptive complexity
• Theoretical computer science stubs

• All stub articles