title: Query (complexity)
text: # 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 $\sigma$ and $\tau$, we define the set of structures on each language, ${\mbox{STRUC}}[\sigma ]$ and ${\mbox{STRUC}}[\tau ]$. A query is then any mapping
  
     $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({\mathfrak {A}})\equiv I({\mathfrak {B}})$ for any isomorphic structures ${\mathfrak {A}}$ and ${\mathfrak {B}}$.
  
  