Computer Science – Databases
Scientific paper
2007-09-19
Computer Science
Databases
Scientific paper
In this study, we 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 our study, we first consider the centralized case, deriving the complexity of the decision problem and of query evaluation. We 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. We then move to the distributed case, and introduce a logical model of a network of taxonomy-based sources. On such network, a distributed version of the centralized algorithm is then presented, based on a message passing paradigm, and its correctness is proved. We finally discuss optimization issues, and relate our work to the literature.
Analyti Anastasia
Meghini Carlo
Tzitzikas Yannis
No associations
LandOfFree
Query Evaluation in P2P Systems of Taxonomy-based Sources: Algorithms, Complexity, and Optimizations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Query Evaluation in P2P Systems of Taxonomy-based Sources: Algorithms, Complexity, and Optimizations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Query Evaluation in P2P Systems of Taxonomy-based Sources: Algorithms, Complexity, and Optimizations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-336958