Bootstrapping pay-as-you-go data integration systems

ABSTRACT

Data integration systems offer a uniform interface to a set of data sources. Despite recent progress, setting up and maintaining a data integration application still requires significant upfront effort of creating a mediated schema and semantic mappings from the data sources to the mediated schema. Many application contexts involving multiple data sources (e.g., the web, personal information management, enterprise intranets) do not require full integration in order to provide useful services, motivating a pay-as-you-go approach to integration. With that approach, a system starts with very few (or inaccurate) semantic mappings and these mappings are improved over time as deemed necessary.

This paper describes the first completely self-configuring data integration system. The goal of our work is to investigate how advanced of a starting point we can provide a pay-as-you-go system. Our system is based on the new concept of a probabilistic mediated schema that is automatically created from the data sources. We automatically create probabilistic schema mappings between the sources and the mediated schema. We describe experiments in multiple domains, including 50-800 data sources, and show that our system is able to produce high-quality answers with no human intervention.

REFERENCES

• 1: Knitro optimization software. http://www.ziena.com/knitro.htm.
• 2: Secondstring. http://secondstring.sourceforge.net/.
• 3: C. Batini , M. Lenzerini , S. B. Navathe, A comparative analysis of methodologies for database schema integration, ACM Computing Surveys (CSUR), v.18 n.4, p.323-364, Dec. 1986 [doi>10.1145/27633.27634]
• 4: Adam L. Berger , Vincent J. Della Pietra , Stephen A. Della Pietra, A maximum entropy approach to natural language processing, Computational Linguistics, v.22 n.1, p.39-71, March 1996
• 5: Jacob Berlin , Amihai Motro, Database Schema Matching Using Machine Learning with Feature Selection, Proceedings of the 14th International Conference on Advanced Information Systems Engineering, p.452-466, May 27-31, 2002
• 6: Peter Buneman , Susan B. Davidson , Anthony Kosky, Theoretical Aspects of Schema Merging, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.152-167, March 23-27, 1992
• 7: Robin Dhamankar , Yoonkyong Lee , AnHai Doan , Alon Halevy , Pedro Domingos, iMAP: discovering complex semantic matches between database schemas, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007612]
• 8: Hong-Hai Do , Erhard Rahm, COMA: a system for flexible combination of schema matching approaches, Proceedings of the 28th international conference on Very Large Data Bases, p.610-621, August 20-23, 2002, Hong Kong, China
• 9: AnHai Doan , Jayant Madhavan , Pedro Domingos , Alon Halevy, Learning to map between ontologies on the semantic web, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511532]
• 10: Xin Dong , Alon Y. Halevy , Cong Yu, Data integration with uncertainty, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 11: M. Dudik, S. J. Phillips, and R. E. Schapire. Performance guarantees for regularized maximum entropy density estimation. In Proc. of the 17th Annual Conf. on Computational Learning Theory, 2004.
• 12: Michael Franklin , Alon Halevy , David Maier, From databases to dataspaces: a new abstraction for information management, ACM SIGMOD Record, v.34 n.4, p.27-33, December 2005 [doi>10.1145/1107499.1107502]
• 13: Avigdor Gal, Why is schema matching tough and what can we do about it?, ACM SIGMOD Record, v.35 n.4, p.2-5, December 2006 [doi>10.1145/1228268.1228269]
• 14: Bin He , Kevin Chen-Chuan Chang, Statistical schema matching across web query interfaces, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872784]
• 15: Richard Hull, Relative information capacity of simple relational database schemata, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588027]
• 16: Shawn R. Jeffery , Michael J. Franklin , Alon Y. Halevy, Pay-as-you-go user feedback for dataspace systems, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376701]
• 17: Leonid A. Kalinichenko, Methods and tools for equivalent data model mapping construction, Proceedings of the 2nd international conference on extending database technology: Advances in Database Technology, p.92-119, March 1990, Venice, Italy
• 18: Jaewoo Kang , Jeffrey F. Naughton, On schema matching with opaque column names and data values, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872783]
• 19: M. Magnani and D. Montesi. Uncertainty in data integration: current approaches and open problems. In VLDB workshop on Management of Uncertain Data, pages 18--32, 2007.
• 20: M. Magnani, N. Rizopoulos, P. Brien, and D. Montesi. Schema integration based on uncertain semantic mappings. Lecture Notes in Computer Science, pages 31--46, 2005.
• 21: Similarity Flooding: A Versatile Graph Matching Algorithm and Its Application to Schema Matching, Proceedings of the 18th International Conference on Data Engineering, p.117, February 26-March 01, 2002
• 22: Renée J. Miller , Yannis E. Ioannidis , Raghu Ramakrishnan, The Use of Information Capacity in Schema Integration and Translation, Proceedings of the 19th International Conference on Very Large Data Bases, p.120-133, August 24-27, 1993
• 23: Henrik Nottelmann , Umberto Straccia, Information retrieval and machine learning for probabilistic schema matching, Information Processing and Management: an International Journal, v.43 n.3, p.552-576, May, 2007 [doi>10.1016/j.ipm.2006.10.014]
• 24: Stephen Della Pietra , Vincent Della Pietra , John Lafferty, Inducing Features of Random Fields, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.4, p.380-393, April 1997 [doi>10.1109/34.588021]
• 25: R. Pottinger and P. Bernstein. Creating a mediated schema based on initial correspondences. In IEEE Data Eng. Bulletin, pages 26--31, Sept 2002.
• 26: 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]
• 27: S. E. Fienberg W. Cohen, P. Ravikumar. A comparison of string distance metrics for name-matching tasks. In Proc. of IJCAI, 2003.
• 28: Jiying Wang , Ji-Rong Wen , Fred Lochovsky , Wei-Ying Ma, Instance-based schema matching for web databases by domain-specific query probing, Proceedings of the Thirtieth international conference on Very large data bases, p.408-419, August 31-September 03, 2004, Toronto, Canada

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.0 GENERAL

General Terms:
Algorithms, Design, Experimentation

Keywords:
data integration, mediated schema, pay-as-you-go, schema mapping