Consulta (complejidad)

En complejidad descriptiva , una consulta es un mapeo de estructuras de una signatura a estructuras de otro vocabulario. Neil Immerman , en su libro Descriptive Complexity, ^{[ 1 ]} "utiliza el concepto de consulta como el paradigma fundamental de la computación" (p.  17).

Firmas dadas${\displaystyle \sigma }$y${\displaystyle \tau }$, definimos el conjunto de estructuras en cada lenguaje,${\displaystyle {\mbox{STRUC}}[\sigma ]}$y${\displaystyle {\mbox{STRUC}}[\tau ]}$Una consulta es entonces cualquier mapeo

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

La teoría de la complejidad computacional puede entonces formularse en términos del poder de la lógica matemática necesaria para expresar una consulta determinada.

Una consulta es independiente del orden si el orden de los objetos en la estructura no afecta los resultados de la consulta. En las bases de datos, estas consultas corresponden a consultas genéricas (Immerman 1999, p.  18). Una consulta es independiente del orden si y solo si${\displaystyle I({\mathfrak {A}})\equiv I({\mathfrak {B}})}$para cualquier estructura isomorfa${\displaystyle {\mathfrak {A}}}$y${\displaystyle {\mathfrak {B}}}$.