Query Evaluation in P2P Systems of Taxonomy-Based Sources: Algorithms, Complexity, and Optimizations

In this paper the authors address the problem of answering queries over a peer-to-peer system of taxonomy-based sources. A taxonomy states subsumption relationships between negation-free DNF formulas on terms and negation-free conjunctions of terms. To the end of laying the foundations of the study, they first consider the centralized case, deriving the complexity of the decision problem and of query evaluation. They conclude by presenting an algorithm that is efficient in data complexity and is based on hypergraphs. More expressive forms of taxonomies are also investigated which however lead to intractability. They then move to the distributed case, and introduce a logical model of a network of taxonomy-based sources.