Top-k generation of integrated schemas based on directed and weighted correspondences

ABSTRACT

Schema integration is the problem of creating a unified target schema based on a set of existing source schemas and based on a set of correspondences that are the result of matching the source schemas. Previous methods for schema integration rely on the exploration, implicit or explicit, of the multiple design choices that are possible for the integrated schema. Such exploration relies heavily on user interaction; thus, it is time consuming and labor intensive. Furthermore, previous methods have ignored the additional information that typically results from the schema matching process, that is, the weights and in some cases the directions that are associated with the correspondences.

In this paper, we propose a more automatic approach to schema integration that is based on the use of directed and weighted correspondences between the concepts that appear in the source schemas. A key component of our approach is a novel top-k ranking algorithm for the automatic generation of the best candidate schemas. The algorithm gives more weight to schemas that combine the concepts with higher similarity or coverage. Thus, the algorithm makes certain decisions that otherwise would likely be taken by a human expert. We show that the algorithm runs in polynomial time and moreover has good performance in practice.

REFERENCES

• 1: 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]
• 2: P. Brown, P. J. Haas, J. Myllymaki, H. Pirahesh, B. Reinwald, and Y. Sismanis. Toward Automated Large-Scale Information Integration and Discovery. In Data Management in a Connected World, pages 161--180, 2005.
• 3: 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
• 4: Laura Chiticariu , Phokion G. Kolaitis , Lucian Popa, Interactive generation of integrated schemas, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376700]
• 5: Thomas M. Connolly , Carolyn E. Begg, Database Systems: A Practical Approach to Design, Implementation and Management (4th Edition), Pearson Addison Wesley, 2004
• 6: M.-P. Dubuisson and A. K. Jain. A Modified Hausdorff Distance for Object Matching. In Proc. Int. Conf. on Pattern Recognition, pages 566--568, 1994.
• 7: A. Gal. Managing Uncertainty in Schema Matching with Top-K Schema Mappings. J. Data Semantics, 6:90--114, 2006.
• 8: H. Hamacher and M. Queyranne. K-best solutions to combinatorial optimization problems. Annals of Operations Research, 4:123--143, 1985/6.
• 9: D. P. Huttenlocher , G. A. Klanderman , W. A. Rucklidge, Comparing Images Using the Hausdorff Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.9, p.850-863, September 1993 [doi>10.1109/34.232073]
• 10: 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
• 11: R. J. Miller, D. Fisla, M. Huang, D. Kymlicka, F. Ku, and V. Lee. The Amalgam schema and data integration test suite. www.cs.toronto.edu/ miller/amalgam, 2001.
• 12: 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
• 13: www.dbis.informatik.uni-goettingen.de/Mondial.
• 14: J. Munkres. Algorithms for the Assignment and Transportation Problems. Journal of the Society of Industrial and Applied Mathematics, 5(1):32--38, 1957.
• 15: J. R. Munkres. Topology. Prentice Hall, Inc., 2000.
• 16: K. G. Murty. An algorithm for ranking all the assignments in order of increasing cost. Operations Research, 16:682--687, 1968.
• 17: Natalya Fridman Noy , Mark A. Musen, PROMPT: Algorithm and Tool for Automated Ontology Merging and Alignment, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.450-455, July 30-August 03, 2000
• 18: Lucian Popa , Yannis Velegrakis , Mauricio A. Hernández , Renée J. Miller , Ronald Fagin, Translating web data, Proceedings of the 28th international conference on Very Large Data Bases, p.598-609, August 20-23, 2002, Hong Kong, China
• 19: Rachel A. Pottinger , Philip A. Bernstein, Merging models based on given correspondences, Proceedings of the 29th international conference on Very large data bases, p.862-873, September 09-12, 2003, Berlin, Germany
• 20: Rachel Pottinger , Philip A. Bernstein, Schema merging and mapping creation for relational sources, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353357]
• 21: A. Radwan, A. Younis, M. A. Hernández, H. Ho, L. Popa, S. Shivaji, and S. Khuri. BioFederator: A Data Federation System for Bioinformatics on the Web. In IIWeb Workshop, pages 92--97, 2007.
• 22: 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]
• 23: S. Spaccapietra , C. Parent, View Integration: A Step Forward in Solving Structural Conflicts, IEEE Transactions on Knowledge and Data Engineering, v.6 n.2, p.258-274, April 1994 [doi>10.1109/69.277770]
• 24: G. Stumme and A. Maedche. FCA-MERGE: Bottom-up merging of ontologies. In IJCAI, pages 225--234, 2001.
• 25: Octavian Udrea , Lise Getoor , Renée J. Miller, Leveraging data and structure in ontology integration, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247531]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.5 Heterogeneous Databases
          Subjects: Data translation**

General Terms:
Algorithms, Design

Keywords:
data integration, data merging, interactive schema generation, model management, schema integration, schema mapping, top-k generation