Since you say that the preprocessing step does not need to be super-fast, then I suggest storing it as a graph. Once you add the "base" comparisons as directed edges, you can compute the transitive closure of the graph. To check a comparison query, you just have to see whether the edge exists in the transitive closure, which is a very fast operation if the graph is pre-computed.
The only thing to watch out for is the equalities in the data. As long as we're using graphs, you can use an undirected graph to keep track of which items are equivalent, so you can map the members of each equivalence class to a unique representative. Also, if something comes in the data that says xx>yy and later yy>xx, should I infer that xx=yy, or is that an error? My sample code below treats it as an error (the resulting graph is not a DAG), but I suppose you could do either.
Here is a rough proof-of-concept that I hope doesn't have too many bugs.
use strict;
use Graph::Undirected;
use Graph::Directed;
my @data = qw[ xx<yy yy<zz zz>aa bb<yy yy=aa aa>cc ];
## take all equalities in the data, map each item to
## a canonical (equivalent) representative.
my $eq = Graph::Undirected->new;
$eq->add_edge( split /=/, $_ ) for grep /=/, @data;
my %canonical;
for ($eq->connected_components) {
my $representative = $_->[0];
for (@$_) {
$canonical{$_} = $representative;
}
}
sub canonical {
exists $canonical{$_[0]} ? $canonical{$_[0]} : $_[0];
}
## take all inequalities in the data, make a dag from them
## and take the transitive closure.
my $g = Graph::Directed->new;
for (grep !/=/, @data) {
my ($x, $y) = split /<|>/, $_;
($x,$y) = ($y,$x) if /</;
$g->add_edge( canonical($x), canonical($y) );
}
die "Not a DAG!" unless $g->is_dag;
$g = $g->transitive_closure;
sub compare {
my ($x,$y) = map canonical($_), @_;
return 0 if $x eq $y;
return 1 if $g->has_edge($x,$y);
return -1 if $g->has_edge($y,$x);
return 0;
}
my @items = qw[ aa bb cc xx yy zz ];
for my $x (@items) {
for my $y (@items) {
print "$x, $y: " . compare($x,$y). $/;
}
}