  Let $\mathrm{SO}^{\mathit{plog}}$ denote the restriction of second-order
logic, where second-order quantification ranges over relations of size at most
poly-logarithmic in the size of the structure. In this article we investigate
the problem, which Turing machine complexity class is captured by Boolean
queries over ordered relational structures that can be expressed in this logic.
For this we define a hierarchy of fragments $\Sigma^{\mathit{plog}}_m$ (and
$\Pi^{\mathit{plog}}_m$) defined by formulae with alternating blocks of
existential and universal second-order quantifiers in quantifier-prenex normal
form. We first show that the existential fragment $\Sigma^{\mathit{plog}}_1$
captures NPolyLogTime, i.e. the class of Boolean queries that can be accepted
by a non-deterministic Turing machine with random access to the input in time
$O((\log n)^k)$ for some $k \ge 0$. Using alternating Turing machines with
random access input allows us to characterise also the fragments
$\Sigma^{\mathit{plog}}_m$ (and $\Pi^{\mathit{plog}}_m$) as those Boolean
queries with at most $m$ alternating blocks of second-order quantifiers that
are accepted by an alternating Turing machine. Consequently,
$\mathrm{SO}^{\mathit{plog}}$ captures the whole poly-logarithmic time
hierarchy. We demonstrate the relevance of this logic and complexity class by
several problems in database theory.
