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,{{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}} "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}$ .

References

Category:Descriptive complexity