Query (complexity): Difference between revisions

Revision as of 20:27, 21 December 2017

Revision as of 20:28, 21 December 2017

Line 10:

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. 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==

*{{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}}