Logical foundations of peer-to-peer data integration

ABSTRACT

In peer-to-peer data integration, each peer exports data in terms of its own schema, and data interoperation is achieved by means of mappings among the peer schemas. Peers are autonomous systems and mappings are dynamically created and changed. One of the challenges in these systems is answering queries posed to one peer taking into account the mappings. Obviously, query answering strongly depends on the semantics of the overall system. In this paper, we compare the commonly adopted approach of interpreting peer-to-peer systems using a first-order semantics, with an alternative approach based on epistemic logic. We consider several central properties of peer-to-peer systems: modularity, generality, and decidability. We argue that the approach based on epistemic logic is superior with respect to all the above properties. In particular, we show that, in systems in which peers have decidable schemas and conjunctive mappings, but are arbitrarily interconnected, the first-order approach may lead to undecidability of query answering, while the epistemic approach always preserves decidability. This is a fundamental property, since the actual interconnections among peers are not under the control of any actor in the system.

REFERENCES

• 1: Karl Aberer , Magdalena Punceva , Manfred Hauswirth , Roman Schmidt, Improving Data Access in P2P Systems, IEEE Internet Computing, v.6 n.1, p.58-67, January 2002 [doi>10.1109/4236.978370]
• 2: P. A. Bernstein, F. Giunchiglia, A. Kementsietsidis, J. Mylopoulos, L. Serafini, and I. Zaihrayeu Data management for peer-to-peer computing: A vision. In Proc. of the 5th Int. Workshop on the Web and Databases (WebDB 2002), 2002.
• 3: A. Calì, D. Calvanese, G. De Giacomo, and M. Lenzerini. Accessing data integration systems through conceptual schemas. In Proc. of the 10th Ital. Conf. on Database Systems (SEBD 2002), pages 161--168, 2002.
• 4: Andrea Calì , Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, On the Expressive Power of Data Integration Systems, Proceedings of the 21st International Conference on Conceptual Modeling, p.338-350, October 07-11, 2002
• 5: Andrea Calì , Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, Data integration under integrity constraints, Information Systems, v.29 n.2, p.147-163, April 2004 [doi>10.1016/S0306-4379(03)00050-4]
• 6: 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]
• 7: A. Calì, D. Lembo, and R. Rosati. Query rewriting and answering under constraints in data integration systems. In Proc. of the 18th Int. Joint Conf. on Artificial Intelligence (IJCAI 2003), pages 16--21, 2003.
• 8: M. A. Casanova, R. Fagin, and C. H. Papadimitriou. Inclusion dependencies and their interaction with functional dependencies. J. of Computer and System Sciences, 28(1):29--59, 1984.
• 9: T. Catarci and M. Lenzerini. Representing and using interschema knowledge in cooperative information systems. J. of Intelligent and Cooperative Information Systems, 2(4):375--398, 1993.
• 10: A. K. Chandra and M. Y. Vardi. The implication problem for functional and inclusion dependencies is undecidable. SIAM J. on Computing, 14(3):671--677, 1985.
• 11: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data Exchange: Semantics and Query Answering, Proceedings of the 9th International Conference on Database Theory, p.207-224, January 08-10, 2003
• 12: Ronald Fagin , Phokion G. Kolaitis , Wang-Chiew Tan , Lucian Popa, Composing schema mappings: second-order dependencies to the rescue, 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.1055572]
• 13: Melvin Fitting, Basic modal logic, Handbook of logic in artificial intelligence and logic programming (vol. 1), Oxford University Press, Inc., New York, NY, 1993
• 14: Marc Friedman , Alon Levy , Todd Millstein, Navigational plans for data integration, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.67-73, July 18-22, 1999, Orlando, Florida, United States
• 15: S. Gribble, A. Halevy, Z. Ives, M. Rodrig, and D. Suciu. What can databases do for peer-to-peer? In Proc. of the 4th Int. Workshop on the Web and Databases (WebDB 2001), 2001.
• 16: A. Halevy, Z. Ives, D. Suciu, and I. Tatarinov. Schema mediation in peer data management systems. In Proc. of the 19th IEEE Int. Conf. on Data Engineering (ICDE 2003), pages 505--516, 2003.
• 17: Jeff Heflin , James Hendler, A Portrait of the Semantic Web in Action, IEEE Intelligent Systems, v.16 n.2, p.54-59, March 2001 [doi>10.1109/5254.920600]
• 18: Richard Hull , Michael Benedikt , Vassilis Christophides , Jianwen Su, E-services: a look behind the curtain, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-14, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773154]
• 19: Christoph Koch, Query Rewriting with Symmetric Constraints, Proceedings of the Second International Symposium on Foundations of Information and Knowledge Systems, p.130-147, February 20-23, 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: Hector J. Levesque , Gerhard Lakemeyer, The logic of knowledge bases, MIT Press, Cambridge, MA, 2001
• 22: J. Madhavan and A. Y. Halevy. Composing mappings among data sources. In Proc. of the 29th Int. Conf. on Very Large Data Bases (VLDB 2003), pages 572--583, 2003.
• 23: John C. Mitchell, The implication problem for functional and inclusion dependencies, Information and Control, v.56 n.3, p.154-173, March 1983 [doi>10.1016/S0019-9958(83)80002-3]
• 24: M. P. Papazoglou, B. J. Kramer, and J. Yang. Leveraging Web-services and peer-to-peer networks. In Proc. of the 15th Int. Conf. on Advanced Information Systems Engineering (CAiSE 2003), pages 485--501, 2003.
• 25: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988