Mapping data in peer-to-peer systems: semantics and algorithmic issues

ABSTRACT

We consider the problem of mapping data in peer-to-peer data-sharing systems. Such systems often rely on the use of mapping tables listing pairs of corresponding values to search for data residing in different peers. In this paper, we address semantic and algorithmic issues related to the use of mapping tables. We begin by arguing why mapping tables are appropriate for data mapping in a peer-to-peer environment. We discuss alternative semantics for these tables and we present a language that allows the user to specify mapping tables under different semantics. Then, we show that by treating mapping tables as constraints (called mapping constraints) on the exchange of information between peers it is possible to reason about them. We motivate why reasoning capabilities are needed to manage mapping tables and show the importance of inferring new mapping tables from existing ones. We study the complexity of this problem and we propose an efficient algorithm for its solution. Finally, we present an implementation along with experimental results that show that mapping tables may be managed efficiently in practice.

REFERENCES

• 1: GDB. http://www.gdb.org/.
• 2: Gnutella. http://www.gnutelliums.com/.
• 3: Hugo. http://www.gene.ucl.ac.uk/hugo/.
• 4: Hyperion. http://www.cs.toronto.edu/db/hyperion/.
• 5: Locus. http://www.ncbi.nlm.nih.gov/LocusLink/.
• 6: MIM. http://www.ncbi.nlm.nih.gov/omim/.
• 7: Napster. http://www.napster.com/.
• 8: SWISS-PROT. http://www.ebi.ac.uk/swissprot/.
• 9: Unigene. http://www.ncbi.nlm.nih.gov/UniGene/.
• 10: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 11: P. Bernstein, F. Giunchiglia, A. Kementsietsidis, J. Mylopoulos, L. Serafini, and I. Zaihrayeu. Data Management for Peer-to-Peer Computing: A Vision. In WebDB, 2002.
• 12: Michael L. Brodie , Michael Stonebraker, Migrating legacy systems: gateways, interfaces & the incremental approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1995
• 13: Chen-Chuan K. Chang , Héctor García-Molina, Mind your vocabulary: query mapping across heterogeneous information sources, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.335-346, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 14: Brian F. Cooper , Hector Garcia-Molina, Peer-to-peer data trading to preserve information, ACM Transactions on Information Systems (TOIS), v.20 n.2, p.133-170, April 2002 [doi>10.1145/506309.506310]
• 15: S. Davidson, G. C. Overton, and P. Buneman. Challenges in Integrating Biological Data Sources. Journal of Computational Biology, 2(4):557--572, 1995.
• 16: L. G. DeMichiel, Resolving Database Incompatibility: An Approach to Performing Relational Operations over Mismatched Domains, IEEE Transactions on Knowledge and Data Engineering, v.1 n.4, p.485-493, December 1989 [doi>10.1109/69.43423]
• 17: S. Gribble, A. Halevy, Z. Ives, M. Rodrig, and D. Suciu. What Can Databases Do for Peer-to-Peer? In WebDB, 2001.
• 18: A. Halevy, Z. Ives, D. Suciu, and I. Tatarinov. Schema Mediation in Peer Data Management Systems. To appear in ICDE 2003.
• 19: Matthew Harren , Joseph M. Hellerstein , Ryan Huebsch , Boon Thau Loo , Scott Shenker , Ion Stoica, Complex Queries in DHT-based Peer-to-Peer Networks, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.242-259, March 07-08, 2002
• 20: Maurizio Lenzerini, Data integration: a theoretical perspective, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543644]
• 21: Bertram Ludäscher , Amarnath Gupta , Maryann E. Martone, Model-Based Mediation with Domain Maps, Proceedings of the 17th International Conference on Data Engineering, p.81-90, April 02-06, 2001
• 22: Jayant Madhavan , Philip A. Bernstein , Pedro Domingos , Alon Y. Halevy, Representing and reasoning about mappings between domain models, Eighteenth national conference on Artificial intelligence, p.80-86, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 23: L. Popa, Y. Velegrakis, R. J. Miller, M. A. Hernandez, and R. Fagin. Translating Web Data. In VLDB, pages 598--609, Aug. 2002.
• 24: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 25: S. Sarawagi, editor. IEEE Data Engineering Bulletin: Special Issue on Data Cleaning, volume 23, Dec. 2000.
• 26: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 27: Beverly Yang , Hector Garcia-Molina, Comparing Hybrid Peer-to-Peer Systems, Proceedings of the 27th International Conference on Very Large Data Bases, p.561-570, September 11-14, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Design, Experimentation, Performance, Theory