Query (complexity)
Encyclopedia
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", "use[s] the concept of query as the fundamental paradigm of computation" (p. 17).
Given signatures
and 
, we define the set of structure
s 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.
for any isomorphic structures 
and 
.
Descriptive complexity
Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the...
, a query is a mapping from structures of one signature
Signature (logic)
In logic, especially mathematical logic, a signature lists and describes the non-logical symbols of a formal language. In universal algebra, a signature lists the operations that characterize an algebraic structure. In model theory, signatures are used for both purposes.Signatures play the same...
to structures of another vocabulary. Neil Immerman
Neil Immerman
Neil Immerman is an American theoretical computer scientist, a professor of computer science at the University of Massachusetts Amherst...
, in his book "Descriptive Complexity", "use[s] the concept of query as the fundamental paradigm of computation" (p. 17).
Given signatures
and , we define the set of structureStructure (mathematical logic)
In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations which are defined on it....
s on each language,
and . A query is then any mapping
Computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
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 for any isomorphic structures and .