  In this paper we solve the ancestry-labeling scheme problem which aims at
assigning the shortest possible labels (bit strings) to nodes of rooted trees,
so that ancestry queries between any two nodes can be answered by inspecting
their assigned labels only. This problem was introduced more than twenty years
ago by Kannan et al. [STOC '88], and is among the most well-studied problems in
the field of informative labeling schemes. We construct an ancestry-labeling
scheme for $n$-node trees with label size $\log_2 n + O(\log \log n)$ bits,
thus matching the $\log_2 n + O(\log \log n)$ bits lower bound given by Alstrup
et al. [SODA '03]. Our scheme is based on a simplified ancestry scheme that
operates extremely well on a restricted set of trees. In particular, for the
set of n-node trees with depth at most d, the simplified ancestry scheme enjoys
label size of $\log_2 n + 2 \log_2 d + O(1)$ bits. Since the depth of most XML
trees is at most some small constant, such an ancestry scheme may be of
practical use. In addition, we also obtain an adjacency-labeling scheme that
labels n-node trees of depth d with labels of size $\log_2 n + 3 \log_2 d +
O(1)$ bits. All our schemes assign the labels in linear time, and guarantee
that any query can be answered in constant time. Finally, our ancestry scheme
finds applications to the construction of small universal partially ordered
sets (posets). Specifically, for any fixed integer k, it enables the
construction of a universal poset of size $\tilde O(n^k)$ for the family of
$n$-element posets with tree-dimension at most $k$. Up to lower order terms,
this bound is tight thanks to a lower bound of $n^{k-o(1)}$ due to Alon and
Scheinerman [Order '88].
