Query (complexity): Difference between revisions

Revision as of 05:05, 23 May 2020

Latest revision as of 16:39, 14 January 2021

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 Descriptive Complexity,<ref>{{Cite book|title=Descriptive Complexity|title-link= Descriptive Complexity |last=Neil|first=Immerman|date=1999|publisher=Springer New York|isbn=9781461205395|___location=New York, NY|oclc=853271745}}</ref>, "use[s] the concept of query as the fundamental paradigm of computation" (p. &nbsp;17).

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. &nbsp;18).<!-- This isn't a great reference for this information, since it's in the "background" section. A reference that goes into more detail would be great. --> A query is order-independent iff <math> I(\mathfrak{A}) \equiv I(\mathfrak{B})</math> for any isomorphic structures <math>\mathfrak{A}</math> and <math>\mathfrak{B}</math>.

==References==

<references />

{{comp-sci-theory-stub}}

[[Category:Descriptive complexity]]

{{comp-sci-theory-stub}}