Jump to content

Query (complexity)

From Wikipedia, the free encyclopedia
(Redirected from First-order query)

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

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]
  1. ^ Neil, Immerman (1999). Descriptive Complexity. New York, NY: Springer New York. ISBN 9781461205395. OCLC 853271745.