  We address the problem of answering queries over a distributed information
system, storing objects indexed by terms organized in a taxonomy. The taxonomy
consists of subsumption relationships between negation-free DNF formulas on
terms and negation-free conjunctions of terms. In the first part of the paper,
we consider the centralized case, deriving a hypergraph-based algorithm that is
efficient in data complexity. In the second part of the paper, we consider the
distributed case, presenting alternative ways implementing the centralized
algorithm. These ways descend from two basic criteria: direct vs. query
re-writing evaluation, and centralized vs. distributed data or taxonomy
allocation. Combinations of these criteria allow to cover a wide spectrum of
architectures, ranging from client-server to peer-to-peer. We evaluate the
performance of the various architectures by simulation on a network with
O(10^4) nodes, and derive final results. An extensive review of the relevant
literature is finally included.
