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).
, we define the set of structures on each language,
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.
A query is order-independent iff
This theoretical computer science–related article is a stub.