Data integration: a theoretical perspective

ABSTRACT

Data integration is the problem of combining data residing at different sources, and providing the user with a unified view of these data. The problem of designing data integration systems is important in current real world applications, and is characterized by a number of issues that are interesting from a theoretical point of view. This document presents on overview of the material to be presented in a tutorial on data integration. The tutorial is focused on some of the theoretical issues that are relevant for data integration. Special attention will be devoted to the following aspects: modeling a data integration application, processing queries in data integration, dealing with inconsistent data sources, and reasoning on queries.

REFERENCES

• 1: Serge Abiteboul , Oliver M. Duschka, Complexity of answering queries using materialized views, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.254-263, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275516]
• 2: S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. L. Wiener. The Lorel query language for semistructured data. Int. J. on Digital Libraries, 1(1):68-88, 1997.
• 3: S. Adali , K. S. Candan , Y. Papakonstantinou , V. S. Subrahmanian, Query caching and optimization in distributed mediator systems, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.137-146, June 04-06, 1996, Montreal, Quebec, Canada
• 4: Foto N. Afrati , Manolis Gergatsoulis , Theodoros G. Kavalieros, Answering Queries Using Materialized Views with Disjunctions, Proceeding of the 7th International Conference on Database Theory, p.435-452, January 10-12, 1999
• 5: A. V. Aho, Y. Sagiv, and J. D. Ullman. Equivalence among relational expressions. SIAM J. on Computing, 8:218-246, 1979.
• 6: 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]
• 7: M. Arenas, L. E. Bertossi, and J. Chomicki. Specifying and querying database repairs using logic programs with exceptions. In Proc. of the 4th Int. Conf. on Flexible Query Answering Systems (FQAS'00), pages 27-41. Springer, 2000.
• 8: Franz Baader , Diego Calvanese , Deborah L. McGuinness , Daniele Nardi , Peter F. Patel-Schneider, The description logic handbook: theory, implementation, and applications, Cambridge University Press, New York, NY, 2003
• 9: Catriel Beeri , Alon Y. Levy , Marie-Christine Rousset, Rewriting queries using views in description logics, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.99-108, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263673]
• 10: Domenico Beneventano , Sonia Bergamaschi , Silvana Castano , Alberto Corni , R. Guidetti , G. Malvezzi , Michele Melchiori , Maurizio Vincini, Information Integration: The MOMIS Project Demonstration, Proceedings of the 26th International Conference on Very Large Data Bases, p.611-614, September 10-14, 2000
• 11: Alexander Borgida, Description Logics in Data Management, IEEE Transactions on Knowledge and Data Engineering, v.7 n.5, p.671-682, October 1995 [doi>10.1109/69.469829]
• 12: M. Bouzeghoub and M. Lenzerini. Introduction to the special issue on data extraction, cleaning, and reconciliation. Information Systems, 26(8):535-536, 2001.
• 13: François Bry, Query Answering in Information Systems with Integrity Constraints, Proceedings of the IFIP TC11 Working Group 11.5, First Working Conference on Integrity and Internal Control in Information Systems: Increasing the confidence in Information Systems, p.113-130, December 04-05, 1997
• 14: Peter Buneman, Semistructured data, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.117-121, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263675]
• 15: Peter Buneman , Susan Davidson , Gerd Hillebrand , Dan Suciu, A query language and optimization techniques for unstructured data, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.505-516, June 04-06, 1996, Montreal, Quebec, Canada
• 16: Andrea Calì , Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, Accessing Data Integration Systems through Conceptual Schemas, Proceedings of the 20th International Conference on Conceptual Modeling: Conceptual Modeling, p.270-284, November 27-30, 2001
• 17: Andrea Calì , Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, Data Integration under Integrity Constraints, Proceedings of the 14th International Conference on Advanced Information Systems Engineering, p.262-279, May 27-31, 2002
• 18: A. Calì, D. Calvanese, G. De Giacomo, and M. Lenzerini. On the expressive power of data integration systems. Submitted for pubblication, 2002.
• 19: A. Calì, G. De Giacomo, and M. Lenzerini. Models of information integration: Turning local-as-view into global-as-view. In Foundations of Models for Information Integration. On line proceedings, http://www.fmldo.org/FMII-2001, 2001.
• 20: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, On the decidability of query containment under constraints, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.149-158, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275504]
• 21: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, Answering Queries Using Views over Description Logics Knowledge Bases, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.386-391, July 30-August 03, 2000
• 22: D. Calvanese, G. De Giacomo, M. Lenzerini, D. Nardi, and R. Rosati. Description logic framework for information integration. In Proc. of the 6th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR'98), pages 2-13, 1998.
• 23: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, Rewriting of regular expressions and regular path queries, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.194-204, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303996]
• 24: Answering Regular Path Queries Using Views, Proceedings of the 16th International Conference on Data Engineering, p.389, February 28-March 03, 2000
• 25: D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. Containment of conjunctive regular path queries with inverse. In Proc. of the 7th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR 2000), pages 176-185, 2000.
• 26: Diego Calvanese , Moshe Y. Vardi , Giuseppe de Giacomo , Maurizio Lenzerini, View-based query processing for regular path queries with inverse, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.58-66, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335207]
• 27: Diego Calvanese , Giuseppe de Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, View-Based Query Processing and Constraint Satisfaction, Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, p.361, June 26-29, 2000
• 28: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, View-Based Query Answering and Query Containment over Semistructured Data, Revised Papers from the 8th International Workshop on Database Programming Languages, p.40-61, September 08-10, 2001
• 29: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, Lossless regular views, 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.543646]
• 30: M. J. Carey , L. M. Haas , P. M. Schwarz , M. Arya , W. F. Cody , R. Fagin , M. Flickner , A. W. Luniewski , W. Niblack , D. Petkovic , J. Thomas , J. H. Williams , E. L. Wimmers, Towards heterogeneous multimedia information systems: the Garlic approach, Proceedings of the 5th International Workshop on Research Issues in Data Engineering-Distributed Object Management (RIDE-DOM'95), p.124, March 06-07, 1995
• 31: 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.
• 32: Edward P. F. Chan, Containment and minimization of positive conjunctive queries in OODB's, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.202-211, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137869]
• 33: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 34: Surajit Chaudhuri , Ravi Krishnamurthy , Spyros Potamianos , Kyuseok Shim, Optimizing Queries with Materialized Views, Proceedings of the Eleventh International Conference on Data Engineering, p.190-200, March 06-10, 1995
• 35: Surajit Chaudhuri , Moshe Y. Vardi, On the equivalence of recursive and nonrecursive datalog programs, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.55-66, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137109]
• 36: Rada Chirkova , Alon Y. Halevy , Dan Suciu, A Formal Perspective on the View Selection Problem, Proceedings of the 27th International Conference on Very Large Data Bases, p.59-68, September 11-14, 2001
• 37: Sara Cohen , Werner Nutt , Alexander Serebrenik, Rewriting aggregate queries using views, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.155-166, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303992]
• 38: William W. Cohen, Integration of heterogeneous databases without common domains using queries based on textual similarity, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.201-212, June 01-04, 1998, Seattle, Washington, United States
• 39: A. C. K. David S. Johnson. Testing containment of conjunctive queries under functional and inclusion dependencies. J. of Computer and System Sciences, 28(1):167-189, 1984.
• 40: Giuseppe De Giacomo, Intensional query answering by partial evaluation, Journal of Intelligent Information Systems, v.7 n.3, p.205-233, Nov. 1996 [doi>10.1007/BF00125368]
• 41: Alin Deutsch , Val Tannen, Optimization Properties for Classes of Conjunctive Regular Path Queries, Revised Papers from the 8th International Workshop on Database Programming Languages, p.21-39, September 08-10, 2001
• 42: Oliver Michael Duschka , Michael R. Genesereth, Query planning and optimization in information integration, 1998
• 43: Oliver M. Duschka , Michael R. Genesereth, Answering recursive queries using views, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.109-116, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263674]
• 44: O. M. Duschka and A. Y. Levy. Recursive plans for information gathering. In Proc. of the 15th Int. Joint Conf. on Artificial Intelligence (IJCAI'97), pages 778-784, 1997.
• 45: Mary Fernández , Daniela Florescu , Jaewoo Kang , Alon Levy , Dan Suciu, Catching the boat with Strudel: experiences with a Web-site management system, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.414-425, June 01-04, 1998, Seattle, Washington, United States
• 46: Mary F. Fernandez , Dan Suciu, Optimizing Regular Path Expressions Using Graph Schemas, Proceedings of the Fourteenth International Conference on Data Engineering, p.14-23, February 23-27, 1998
• 47: Daniela Florescu , Alon Levy , Dan Suciu, Query containment for conjunctive queries with regular expressions, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.139-148, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275503]
• 48: Daniela Florescu , Alon Levy , Ioana Manolescu , Dan Suciu, Query optimization in the presence of limited access patterns, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.311-322, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 49: 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
• 50: H. Galhardas, D. Florescu, D. Shasha, and E. Simon. An extensible framework for data cleaning. Technical Report 3742, INRIA, Rocquencourt, 1999.
• 51: Hector Garcia-Molina , Yannis Papakonstantinou , Dallan Quass , Anand Rajaraman , Yehoshua Sagiv , Jeffrey Ullman , Vasilis Vassalos , Jennifer Widom, The TSIMMIS Approach to Mediation: Data Models and Languages, Journal of Intelligent Information Systems, v.8 n.2, p.117-132, March/April 1997 [doi>10.1023/A:1008683107812]
• 52: Cheng Hian Goh , Stéphane Bressan , Stuart Madnick , Michael Siegel, Context interchange: new features and formalisms for the intelligent integration of information, ACM Transactions on Information Systems (TOIS), v.17 n.3, p.270-293, July 1999 [doi>10.1145/314516.314520]
• 53: Gösta Grahne , Alberto O. Mendelzon, Tableau Techniques for Querying Information Sources through Global Schemas, Proceeding of the 7th International Conference on Database Theory, p.332-347, January 10-12, 1999
• 54: 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
• 55: S. Gribble, A. Halevy, Z. Ives, M. Rodrig, and D. Suciu. What can databases do for peer-to-peer? In Proc. of the Int. Workshop on the Web and Databases (WebDB'01), 2001.
• 56: Stéphane Grumbach , Maurizio Rafanelli , Leonardo Tininini, Querying aggregate data, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.174-184, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303994]
• 57: Stéphane Grumbach , Leonardo Tininini, On the content of materialized aggregate views, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.47-57, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335174]
• 58: Michael Gruninger , Jintae Lee, Introduction, Communications of the ACM, v.45 n.2, February 2002 [doi>10.1145/503124.503146]
• 59: Jarek Gryz, Query Folding with Inclusion Dependencies, Proceedings of the Fourteenth International Conference on Data Engineering, p.126-133, February 23-27, 1998
• 60: Alon Y. Halevy, Answering queries using views: A survey, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.270-294, December 2001 [doi>10.1007/s007780100054]
• 61: Richard Hull, Managing semantic heterogeneity in databases: a theoretical prospective, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.51-61, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263668]
• 62: T. Kirk, A. Y. Levy, Y. Sagiv, and D. Srivastava. The Information Manifold. In Proceedings of the AAAI 1995 Spring Symp. on Information Gathering from Heterogeneous, Distributed Enviroments, pages 85-91, 1995.
• 63: Anthony Klug, On conjunctive queries containing inequalities, Journal of the ACM (JACM), v.35 n.1, p.146-160, Jan. 1988 [doi>10.1145/42267.42273]
• 64: D. Lembo, M. Lenzerini, and R. Rosati. Source inconsistency and incompleteness in data integration. In Proc. of the 9th Int. Workshop on Knowledge Representation meets Databases (KRDB 2002), 2002.
• 65: Alon Y. Levy, Obtaining Complete Answers from Incomplete Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.402-412, September 03-06, 1996
• 66: Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220198]
• 67: Alon Y. Levy , Anand Rajaraman , Joann J. Ordille, Querying Heterogeneous Information Sources Using Source Descriptions, Proceedings of the 22th International Conference on Very Large Data Bases, p.251-262, September 03-06, 1996
• 68: Alon Y. Levy , Anand Rajaraman , Jeffrey D. Ullman, Answering queries using limited external query processors (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.227-237, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237716]
• 69: A. Y. Levy and M.-C. Rousset. CARIN: A representation language combining Horn rules and description logics. In Proc. of the 12th Eur. Conf. on Artificial Intelligence (ECAI'96), pages 323-327, 1996.
• 70: Alon Y. Levy , Marie-Christine Rousset, Combining Horn rules and description logics in CARIN, Artificial Intelligence, v.104 n.1-2, p.165-209, Sept. 1998 [doi>10.1016/S0004-3702(98)00048-4]
• 71: Alon Y. Levy , Dan Suciu, Deciding containment for queries with complex objects (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.20-31, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263665]
• 72: Chen Li , Mayank Bawa , Jeffrey D. Ullman, Minimizing View Sets without Losing Query-Answering Power, Proceedings of the 8th International Conference on Database Theory, p.99-113, January 04-06, 2001
• 73: Query Planning with Limited Source Capabilities, Proceedings of the 16th International Conference on Data Engineering, p.401, February 28-March 03, 2000
• 74: Chen Li , Edward Y. Chang, On Answering Queries in the Presence of Limited Access Patterns, Proceedings of the 8th International Conference on Database Theory, p.219-233, January 04-06, 2001
• 75: Chen Li , Ramana Yerneni , Vasilis Vassalos , Hector Garcia-Molina , Yannis Papakonstantinou , Jeffrey Ullman , Murty Valiveti, Capability based mediation in TSIMMIS, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.564-566, June 01-04, 1998, Seattle, Washington, United States
• 76: J. Lin and A. O. Mendelzon. Merging databases under constraints. Int. J. of Cooperative Information Systems, 7(1):55-76, 1998.
• 77: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 78: Ioana Manolescu , Daniela Florescu , Donald Kossmann, Answering XML Queries on Heterogeneous Data Sources, Proceedings of the 27th International Conference on Very Large Data Bases, p.241-250, September 11-14, 2001
• 79: Todd Millstein , Alon Levy , Marc Friedman, Query containment for data integration systems, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.67-75, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335208]
• 80: Tova Milo , Dan Suciu, Index Structures for Path Expressions, Proceeding of the 7th International Conference on Database Theory, p.277-295, January 10-12, 1999
• 81: Felix Naumann , Ulf Leser , Johann Christoph Freytag, Quality-driven Integration of Heterogenous Information Systems, Proceedings of the 25th International Conference on Very Large Data Bases, p.447-458, September 07-10, 1999
• 82: Yannis Papakonstantinou , Vasilis Vassalos, Query rewriting for semistructured data, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.455-466, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 83: Erhard Rahm , Philip A. Bernstein, A survey of approaches to automatic schema matching, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.334-350, December 2001 [doi>10.1007/s007780100057]
• 84: Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman, Answering queries using templates with binding patterns (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.105-112, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220199]
• 85: R. Reiter. On closed world data bases. In H. Gallaire and J. Minker, editors, Logic and Databases, pages 119-140. Plenum Publ. Co., New York, 1978.
• 86: Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
• 87: Divesh Srivastava , Shaul Dar , H. V. Jagadish , Alon Y. Levy, Answering Queries with Aggregation Using Views, Proceedings of the 22th International Conference on Very Large Data Bases, p.318-329, September 03-06, 1996
• 88: Odysseas G. Tsatalos , Marvin H. Solomon , Yannis E. Ioannidis, The GMAP: a versatile tool for physical data independence, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.2, p.101-118, April 1996 [doi>10.1007/s007780050018]
• 89: Jeffrey D. Ullman, Information Integration Using Logical Views, Proceedings of the 6th International Conference on Database Theory, p.19-40, January 08-10, 1997
• 90: Ronald van der Meyden, The complexity of querying indefinite information: defined relations, recursion and linear order, Rutgers University, New Brunswick, NJ, 1992
• 91: Ron van der Meyden, Logical approaches to incomplete information: a survey, Logics for databases and information systems, Kluwer Academic Publishers, Norwell, MA, 1998
• 92: G. Zhou, R. Hull, R. King, and J.-C. Franchitti. Using object matching and materialization to integrate heterogeneous databases. In Proc. of the 3rd Int. Conf. on Cooperative Information Systems (CoopIS'95), pages 4-18, 1995.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Mathematics and statistics

Additional Classification:
  K. Computing Milieux
  K.8 PERSONAL COMPUTING
      K.8.1 Application Packages
          Subjects: Database processing

General Terms:
Design, Performance, Theory