Query (complexity)

In descriptive complexity, a query is a mapping from structures of one signature to structures of another vocabulary. Neil Immerman, in his book Descriptive Complexity[1], "use[s] the concept of query as the fundamental paradigm of computation" (p. 17).

Given signatures $\sigma$ and $\tau$ , we define the set of structures on each language, ${\mbox{STRUC}}[\sigma ]$ and ${\mbox{STRUC}}[\tau ]$ . A query is then any mapping

$I:{\mbox{STRUC}}[\sigma ]\to {\mbox{STRUC}}[\tau ]$

Computational complexity theory 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 $I({\mathfrak {A}})\equiv I({\mathfrak {B}})$ for any isomorphic structures ${\mathfrak {A}}$ and ${\mathfrak {B}}$ .

gollark: Although it *may* be redundant since the OS is likely caching disk pages in RAM anyway.

gollark: Caching is nice, I suppose.

gollark: Actually, SQLite is just very fast anyway, it can do sensible queries in a few milliseconds.

gollark: <@!330678593904443393> While better-sqlite3 *can* let me do what your PHP framework does, prepared statements are apparently more efficient and this is neater.

gollark: This is rendered to HTML.

References

Neil, Immerman (1999). Descriptive Complexity. New York, NY: Springer New York. ISBN 9781461205395. OCLC 853271745.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Neil, Immerman (1999). Descriptive Complexity. New York, NY: Springer New York. ISBN 9781461205395. OCLC 853271745.