We study relations on trees defined by first-order constraints over a
vocabulary that includes tree extension inequalities, in
addition to unary node tests and domain comparisons. We show that
from a formula one can generate a tree automaton that accepts the set
of tuples of trees defined by the formula, and conversely that every
automaton over tree-tuples is captured by such a formula. We look at
the fragment with only extension inequalities and leaf tests, and show
that it corresponds to a new class of automata on tree tuples, which
is strictly weaker then general tree-tuple automata. We use the
automata representations to show separation and expressibility results
for formulae in the logic. We then turn to relational calculi over the
logic defined here: that is, from constraints we extend to queries
that have second-order parameters for a finite set of tree tuples. We
give normal forms for queries, and use these to get bounds on the data
complexity of query evaluation, showing that while general query
evaluation is unbounded within the polynomial hierarchy, generic query
evaluation has very low complexity, giving strong bounds on the
expressive power of relational calculi with tree extension
constraints. We also give normal forms for safe queries in the
calculus.
