On the complexity of computing peer agreements for consistent query answering in peer-to-peer data integration systems

ABSTRACT

Peer-to-Peer (P2P) data integration systems have recently attracted significant attention for their ability to manage and share data dispersed over different peer sources. While integrating data for answering user queries, it often happens that inconsistencies arise, because some integrity constraints specified on peers' global schemas may be violated. In these cases, we may give semantics to the inconsistent system by suitably "repairing" the retrieved data, as typically done in the context of traditional data integration systems. However, some specific features of P2P systems, such as peer autonomy and peer preferences (e.g., different source trusting), should be properly addressed to make the whole approach effective. In this paper, we face these issues that were only marginally considered in the literature. We first present a formal framework for reasoning about autonomous peers that exploit individual preference criteria in repairing the data. The idea is that queries should be answered over the best possible database repairs with respect to the preferences of all peers, i.e., the states on which they are able to find an agreement. Then, we investigate the computational complexity of dealing with peer agreements and of answering queries in P2P data integration systems. It turns out that considering peer preferences makes these problems only mildly harder than in traditional data integration systems.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Marcelo Arenas , Leopoldo Bertossi , Jan Chomicki, Consistent query answers in inconsistent databases, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.68-79, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303983]
• 3: P. Bernstein, F. Giunchiglia, A. Kementsietsidis, J. Mylopoulos, L. Serafini, and I. Zaihrayeu. Data management for peer-to-peer computing: A vision. In Workshop on the Web and Databases, WebDB, 2002.
• 4: Leopoldo E. Bertossi , Jan Chomicki , Alvaro Cortés , Claudio Gutiérrez, Consistent Answers from Integrated Data Sources, Proceedings of the 5th International Conference on Flexible Query Answering Systems, p.71-85, October 27-29, 2002
• 5: Leopoldo E. Bertossi and Loreto Bravo. Query answering in peer-to-peer data exchange systems. In Proc. of EDBT Workshops 2004, pages 476--485, 2004.
• 6: Loreto Bravo and Leopoldo Bertossi. Logic programming for consistently querying data integration systems. In Proc. of IJCAI'03, pages 10--15, 2003.
• 7: Andrea Calì , Domenico Lembo , Riccardo Rosati, On the decidability and complexity of query answering over inconsistent and incomplete databases, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.260-271, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773179]
• 8: Andrea Calì, Domenico Lembo, and Riccardo Rosati. Query rewriting and answering under constraints in data integration systems. In Proc. of IJCAI'03, pages 16--21, 2003.
• 9: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Riccardo Rosati, Logical foundations of peer-to-peer data integration, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055593]
• 10: Thomas Eiter, Michael Fink, Gianluigi Greco, and Domenico Lembo. Efficient evaluation of logic programs for querying data integration systems. In Proc. of ICLP'03, pages 348--364, 2003.
• 11: Enrico Franconi, Gabriel Kuper, Andrei Lopatenko, and Luciano Serafini. A robust logical and computational characterisation of peer-to-peer database systems. In Proc. of DBISP2P'03, pages 64--76, 2003.
• 12: Enrico Franconi, Gabriel Kuper, Andrei Lopatenko, and Ilya Zaihrayeu. A distributed algorithm for robust data sharing and updates in p2p database networks. In Proc. of P2P&DB'04, pages 446--455, 2004.
• 13: Enrico Franconi, Gabriel Kuper, Andrei Lopatenko, and Ilya Zaihrayeu. Queries and updates in the codb peer to peer database system. In Proc. of VLDB'04, pages 1277--1280, 2004.
• 14: Gianluigi Greco , Sergio Greco , Ester Zumpano, A Logic Programming Approach to the Integration, Repairing and Querying of Inconsistent Databases, Proceedings of the 17th International Conference on Logic Programming, p.348-364, November 26-December 01, 2001
• 15: Gianluigi Greco and Domenico Lembo. Data integration with prefernces among sources. In Proc. of ER'04, pages 231--244, 2004.
• 16: Alon Y. Halevy , Zachary G. Ives , Peter Mork , Igor Tatarinov, Piazza: data management infrastructure for semantic web applications, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775231]
• 17: Maurizio Lenzerini. Quality-aware peer-to-peer data integration. In Proc. of IQIS'04, 2004.
• 18: Nicola Leone , Gianluigi Greco , Giovambattista Ianni , Vincenzino Lio , Giorgio Terracina , Thomas Eiter , Wolfgang Faber , Michael Fink , Georg Gottlob , Riccardo Rosati , Domenico Lembo , Maurizio Lenzerini , Marco Ruzzi , Edyta Kalka , Bartosz Nowicki , Witold Staniszkis, The INFOMIX system for advanced integration of incomplete and inconsistent data, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066286]
• 19: Nicola Leone, Gerald Pfeifer, Wolfgang Faber, Thomas Eiter, Georg Gottlob, Simona Perri, and Francesco Scarcello. The DLV System for Knowledge Representation and Reasoning. ACM Transaction on Cumputational Logic. To appear.
• 20: Luciano Serafini, Fausto Giunchiglia, John Mylopoulos, and Philip A. Bernstein. Local relational model: A logical formalization of database coordination. In Fourth International and Interdisciplinary Conference on Modeling and Using Context, CONTEXT 2003, pages 286--299, 2003.
• 21: Igor Tatarinov , Alon Halevy, Efficient query reformulation in peer data management systems, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007629]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Management, Theory

Keywords:
data integration systems, peer-to-peer systems