Summary
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 and , we define the set of structures on each language, and . A query is then any mapping
![{\displaystyle {\mbox{STRUC}}[\sigma ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bbb1b6cb871373070d84dfce92ff90adbb971515)
![{\displaystyle {\mbox{STRUC}}[\tau ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b84dfe41dfb6a45d27366be7dce3a2ee81fdc42f)
![{\displaystyle I:{\mbox{STRUC}}[\sigma ]\to {\mbox{STRUC}}[\tau ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/816a8508c68f407dacb4842779a3c229b3a3fd69)
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 edit
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 edit
- ^ Neil, Immerman (1999). Descriptive Complexity. New York, NY: Springer New York. ISBN 9781461205395. OCLC 853271745.