In
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 formal language, languages in them. For example, PH (complexity), PH, ...
, a query is a mapping from structures of one
signature
A signature (; from , "to sign") is a depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. Signatures are often, but not always, Handwriting, handwritt ...
to structures of another vocabulary.
Neil Immerman, in his book Descriptive Complexity,
"use
the concept of query as the fundamental paradigm of computation" (p. 17).
Given signatures
and
, 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,
sigma
Sigma ( ; uppercase Σ, lowercase σ, lowercase in word-final position ς; ) 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 an operator ...
/math> and
tau
Tau (; uppercase Τ, lowercase τ or \boldsymbol\tau; ) is the nineteenth letter of the Greek alphabet, representing the voiceless alveolar plosive, voiceless dental or alveolar plosive . In the system of Greek numerals, it has a value of 300 ...
/math>. A query is then any mapping
sigma
Sigma ( ; uppercase Σ, lowercase σ, lowercase in word-final position ς; ) 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 an operator ...
\to \mboxtau
Tau (; uppercase Τ, lowercase τ or \boldsymbol\tau; ) is the nineteenth letter of the Greek alphabet, representing the voiceless alveolar plosive, voiceless dental or alveolar plosive . In the system of Greek numerals, it has a value of 300 ...
/math>
Computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
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
.
References
Descriptive complexity
{{comp-sci-theory-stub