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 σ and τ, we define the set of structures on each language, STRUC[σ] and STRUC[τ]. A query is then any mapping
![I : \mbox{STRUC}[\sigma] \to \mbox{STRUC}[\tau]](http://wpcontent.answers.com/math/5/8/8/588ee82173e5b3dfc8cd7c21c51c3164.png)
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 
for any isomorphic structures 
and 
.
References
- Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag. ISBN 0-387-98600-6.
| P ≟ NP | This theoretical computer science-related article is a stub. You can help Wikipedia by expanding it. |
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
