Query (complexity) explained

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

\sigma

and

\tau

, we define the set of structures on each language,

STRUC[\sigma]

and

STRUC[\tau]

. A query is then any mapping

I:STRUC[\sigma]\toSTRUC[\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(ak{A})\equivI(ak{B})

for any isomorphic structures

ak{A}

and

ak{B}

.

References

  1. Book: Neil, Immerman. Descriptive Complexity. Descriptive Complexity . 1999. Springer New York. 9781461205395. New York, NY. 853271745.