# Query (complexity)

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Query_(complexity)
> Markdown URL: https://mediated.wiki/source/Query_(complexity).md
> Source: https://en.wikipedia.org/wiki/Query_(complexity)
> Source revision: 1000317254
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [descriptive complexity](/source/descriptive_complexity), a '''query''' is a mapping from structures of one [signature](/source/signature_(logic)) to structures of another vocabulary.  [Neil Immerman](/source/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.&nbsp;17).

Given signatures <math>\sigma</math> and <math>\tau</math>, we define the set of [structure](/source/structure_(mathematical_logic))s 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](/source/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](/source/generic_query) (Immerman 1999, p.&nbsp;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}}

---
Adapted from the Wikipedia article [Query (complexity)](https://en.wikipedia.org/wiki/Query_(complexity)) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Query_(complexity)?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.