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,[1] "use[s] the concept of query as the fundamental paradigm of computation" (p. 17). Given signatures [math]\displaystyle{ \sigma }[/math] and [math]\displaystyle{ \tau }[/math], we define the set of structures on each language, [math]\displaystyle{ \mbox{STRUC}[\sigma] }[/math] and [math]\displaystyle{ \mbox{STRUC}[\tau] }[/math]. A query is then any mapping
[math]\displaystyle{ I : \mbox{STRUC}[\sigma] \to \mbox{STRUC}[\tau] }[/math]
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 [math]\displaystyle{ I(\mathfrak{A}) \equiv I(\mathfrak{B}) }[/math] for any isomorphic structures [math]\displaystyle{ \mathfrak{A} }[/math] and [math]\displaystyle{ \mathfrak{B} }[/math].
References
- ↑ Neil, Immerman (1999). Descriptive Complexity. New York, NY: Springer New York. ISBN 9781461205395. OCLC 853271745.
 |  |
