Content deleted Content added
Hans Adler (talk | contribs) switching from vocabulary to signature, which has an article |
m Fix REFPUNCT + other minor fixes |
||
(6 intermediate revisions by 5 users not shown) | |||
Line 1:
In [[descriptive complexity]], a '''query''' is a mapping from structures of one [[signature (logic)|signature]] to structures of another vocabulary. [[Neil Immerman]], in his book
Given signatures <math>\sigma</math> and <math>\tau</math>, we define the set of [[structure (mathematical logic)|structure]]s on each language, <math>\mbox{STRUC}[\sigma]</math> and <math>\mbox{STRUC}[\tau]</math>. A query is then any mapping
Line 9:
==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 query|generic queries]] (Immerman 1999, p.
{{comp-sci-stub}}▼
==References==
<references />
[[Category:Descriptive complexity]]
▲{{comp-sci-theory-stub}}
|