An n-ary query over trees takes an input tree t and returns a set of n-tuples of the nodes of t. In this paper, a compact data structure is introduced for representing the answer sets of n-ary queries defined by tree automata. Despite that the number of the elements of the answer set can be as large as vertical bar t vertical bar(n), our representation allows storing the set using only O(vertical bar t vertical bar) space. Several basic operations on the sets are shown to be efficiently executable on the representation. (C) 2010 Elsevier B.V. All rights reserved.