Query (complexity): Difference between revisions

Revision as of 02:18, 26 August 2009

Latest revision as of 16:39, 14 January 2021

(5 intermediate revisions by 4 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 "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 />

[[Category:Descriptive complexity]]

==References==

*{{cite book | last = Immerman | first = Neil | authorlink = Neil Immerman | title = Descriptive Complexity | year = 1999 | publisher = Springer-Verlag | ___location = New York | isbn = 0-387-98600-6}}

{{comp-sci-theory-stub}}

[[Category:Descriptive complexity]]