descriptive complexity ''Descriptive Complexity'' is a book in mathematical logic and computational complexity theory by Neil Immerman. It concerns descriptive complexity theory, an area in which the expressibility of mathematical properties using different types of log ...

, a query is a mapping from structures of one signature to structures of another vocabulary.

Neil Immerman Neil Immerman (born 24 November 1953, Manhasset, New York) is an American theoretical computer scientist, a professor of computer science at the University of Massachusetts Amherst.

, in his book Descriptive Complexity, "use the concept of query as the fundamental paradigm of computation" (p. 17). Given signatures

\sigma

and

\tau

, we define the set of

structure A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such as ...

s on each language,

\mbox

sigma Sigma (; uppercase Σ, lowercase σ, lowercase in word-final position ς; grc-gre, σίγμα) is the eighteenth letter of the Greek alphabet. In the system of Greek numerals, it has a value of 200. In general mathematics, uppercase Σ is used as ...

/math> and

\mbox tau /math>.  A query is then any mapping

$I : \mbox$
sigma Sigma (; uppercase Σ, lowercase σ, lowercase in word-final position ς; grc-gre, σίγμα) is the eighteenth letter of the Greek alphabet. In the system of Greek numerals, it has a value of 200. In general mathematics, uppercase Σ is used as ...
\to \mbox 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

I(\mathfrak) \equiv I(\mathfrak)

for any isomorphic structures

\mathfrak

and

\mathfrak

References

Descriptive complexity {{comp-sci-theory-stub