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", "use[s] the concept of query as the fundamental paradigm of computation" (p. 17).

In computational complexity and communication complexity theories the decision tree model is the model of computation or communication in which an algorithm or communication process is considered to be basically a decision tree, i.e., a sequence of branching operations based on comparisons of some quantities, the comparisons being assigned the unit computational cost.