Encode a structure of size $n$ by $n$ one-bits and a zero-bit, followed by the characteristic tables of its relations in vocabulary order. Each table lists tuples in lexicographic order. The distinguished order is determined by $n$ and needs no table. Append each coordinate $a_i$ of the query tuple as $a_i$ one-bits and a zero-bit.

The fixed vocabulary and query arity determine all table boundaries. The encoding is injective and has length $n+1+\sum_{R\in\sigma}n^{\operatorname{arity}(R)}+\sum_{i<k}(a_i+1)$. In particular, the length is at least $n$ and polynomial in $n$ for a fixed vocabulary and arity, including empty vocabularies and small universes.