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, "use[s] the concept of query as the fundamental paradigm of computation" (p. 17).

Given signatures

σ

{\displaystyle \sigma }

and

τ

{\displaystyle \tau }

, we define the set of structures on each language,

STRUC

[

σ

]

{\displaystyle {\mbox{STRUC}}[\sigma ]}

and

STRUC

[

τ

]

{\displaystyle {\mbox{STRUC}}[\tau ]}

. A query is then any mapping

I

:

STRUC

[

σ

]

→

STRUC

[

τ

]

{\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.

Order-independent queries

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

I

(

A

)

≡

I

(

B

)

{\displaystyle I({\mathfrak {A}})\equiv I({\mathfrak {B}})}

for any isomorphic structures

A

{\displaystyle {\mathfrak {A}}}

and

B

{\displaystyle {\mathfrak {B}}}

.