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,<ref>{{Cite book|title=Descriptive Complexity|title-link= Descriptive Complexity |last=Neil|first=Immerman|date=1999|publisher=Springer New York|isbn=9781461205395|location=New York, NY|oclc=853271745}}</ref> "use[s] the concept of query as the fundamental paradigm of computation" (p. 17).
Given signatures <math>\sigma</math> and <math>\tau</math>, we define the set of structures on each language, <math>\mbox{STRUC}[\sigma]</math> and <math>\mbox{STRUC}[\tau]</math>. A query is then any mapping <blockquote> <math>I : \mbox{STRUC}[\sigma] \to \mbox{STRUC}[\tau]</math> </blockquote> 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).<!-- This isn't a great reference for this information, since it's in the "background" section. A reference that goes into more detail would be great. --> A query is order-independent iff <math> I(\mathfrak{A}) \equiv I(\mathfrak{B})</math> for any isomorphic structures <math>\mathfrak{A}</math> and <math>\mathfrak{B}</math>.
==References== <references />
Category:Descriptive complexity
{{comp-sci-theory-stub}}