Dotaz (složitost) - Query (complexity)

v popisná složitost, a dotaz je mapování ze struktur jedné podpis do struktur jiného slovníku. Neil Immerman, ve své knize Popisná složitost^[1]„„ použijte [s] koncept dotazu jako základní paradigma výpočtu “(s. 17).

Dané podpisy ${displaystyle sigma}$ a ${displaystyle au}$, definujeme množinu struktur v každém jazyce, ${displaystyle {mbox {STRUC}} [sigma]}$ a ${displaystyle {mbox {STRUC}} [au]}$. Dotazem je pak jakékoli mapování

${displaystyle I: {mbox {STRUC}} [sigma] o {mbox {STRUC}} [au]}$

Teorie výpočetní složitosti potom lze formulovat z hlediska síly matematické logiky potřebné k vyjádření daného dotazu.

Objednávky nezávislé dotazy

Dotaz je nezávislý na objednávce pokud uspořádání objektů ve struktuře neovlivní výsledky dotazu. V databázích tyto dotazy odpovídají obecné dotazy (Immerman 1999, s. 18). Dotaz je nezávislý na objednávce iff ${displaystyle I ({mathfrak {A}}) ekviv I ({mathfrak {B}})}$ pro jakékoli izomorfní struktury ${displaystyle {mathfrak {A}}}$ a ${displaystyle {mathfrak {B}}}$.

Reference