In
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
A signature (; from la, signare, "to sign") is a Handwriting, handwritten (and often Stylization, stylized) 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 ...
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
and
, we define the set of
structures on each language,
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 ...
/math> and
tau
Tau (uppercase Τ, lowercase τ, or \boldsymbol\tau; el, ταυ ) is the 19th letter of the Greek alphabet, representing the voiceless dental or alveolar plosive . In the system of Greek numerals, it has a value of 300.
The name in English ...
/math>. A query is then any mapping
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 ...
\to \mboxtau
Tau (uppercase Τ, lowercase τ, or \boldsymbol\tau; el, ταυ ) is the 19th letter of the Greek alphabet, representing the voiceless dental or alveolar plosive . In the system of Greek numerals, it has a value of 300.
The name in English ...
/math>
Computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
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