Comparing and Transforming Between Data Models Via an Intermediate Hypergraph Data Model

  • Michael Boyd
  • Peter McBrien
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3730)


Data integration is frequently performed between heterogeneous data sources, requiring that not only a schema, but also the data modelling language in which that schema is represented must be transformed between one data source and another.

This paper describes an extension to the hypergraph data model (HDM), used in the AutoMed data integration approach, that allows constraint constructs found in static data modelling languages to be represented by a small set of primitive constraint operators in the HDM. In addition, a set of five equivalence preserving transformation rules are defined that operate over this extended HDM. These transformation rules are shown to allow a bidirectional mapping to be defined between equivalent relational, ER, UML and ORM schemas.

The approach we propose provides a precise framework in which to compare data modelling languages, and precisely identifies what semantics of a particular domain one data model may express that another data model may not express. The approach also forms the platform for further work in automating the process of transforming between different data modelling languages. The use of the both-as-view approach to data integration means that a bidirectional association is produced between schemas in the data modelling language. Hence a further advantage of the approach is that composition of data mappings may be performed such that mapping two schemas to one common schema will produce a bidirectional mapping between the original two data sources.


conceptual data modelling mappings transformations multiple representations 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Andersson, M.: Extracting an entity relationship schema from a relational database through reverse engineering. In: Loucopoulos, P. (ed.) ER 1994. LNCS, vol. 881, pp. 403–419. Springer, Heidelberg (1994)Google Scholar
  2. 2.
    Atzeni, P., Torlone, R.: Management of multiple models in an extensible database design tool. In: Apers, P.M.G., Bouzeghoub, M., Gardarin, G. (eds.) EDBT 1996. LNCS, vol. 1057, pp. 79–95. Springer, Heidelberg (1996)CrossRefGoogle Scholar
  3. 3.
    Baresi, L., Heckel, R.: Tutorial introduction to graph transofrmation: A software engineering perspective. In: Corradini, A., Ehrig, H., Kreowski, H.-J., Rozenberg, G. (eds.) ICGT 2002. LNCS, vol. 2505, pp. 402–429. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  4. 4.
    Batini, C., Lenzerini, M., Navathe, S.: A comparative analysis of methodologies for database schema integration. ACM Computing Surveys 18(4), 323–364 (1986)CrossRefGoogle Scholar
  5. 5.
    Bernstein, P.A.: Applying model management to classical meta data problems. In: Proc. CIDR 2003 (2003)Google Scholar
  6. 6.
    Bowers, S., Delcambre, L.: On modeling conformance for flexible transformation over data models. In: Knowledge Transformation for the Semantic Web, pp. 34–48. IOS Press, Amsterdam (2003)Google Scholar
  7. 7.
    Bowers, S., Delcambre, L.: The uni-level description: A uniform framework for representing information in multiple data models. In: Song, I.-Y., Liddle, S.W., Ling, T.-W., Scheuermann, P. (eds.) ER 2003. LNCS, vol. 2813, pp. 45–58. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  8. 8.
    Boyd, M., Kittivoravitkul, S., Lazanitis, C., McBrien, P.J., Rizopoulos, N.: AutoMed: A BAV data integration system for heterogeneous data sources. In: Persson, A., Stirna, J. (eds.) CAiSE 2004. LNCS, vol. 3084, pp. 82–97. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  9. 9.
    Boyd, M., McBrien, P.J.: Towards a semi-automated approach to intermodel transformations. In: Proc. EMMSAD 2004, CAiSE Workshop Proceedings, vol. 1, pp. 175–188 (2004)Google Scholar
  10. 10.
    Claypool, K.T., Rundensteiner, E.A.: Sangam: A framework for modeling heterogeneous database transformations. In: Proc. ICEIS 2003, pp. 219–224 (2003)Google Scholar
  11. 11.
    Date, C.J.: Object identifiers vs. relational keys. In: Relational Database: Selected Writings [14], ch. 12, pp. 457–476 (1994-1997)Google Scholar
  12. 12.
    Date, C.J.: An Introduction to Database Systems, 8th edn. Addison-Wesley, Reading (2004)Google Scholar
  13. 13.
    Date, C.J., Darwen, H., Lorentzos, N.A.: Temporal Data and the Relational Model. Morgan Kaufmann, San Francisco (2003)Google Scholar
  14. 14.
    Date, C.J., Darwen, H., McGoveran, D.: Relational Database: Selected Writings 1994–1997. Addison-Wesley, Reading (1998)Google Scholar
  15. 15.
    Davidson, S.B., Buneman, P., Kosky, A.S.: Semantics of database transformations. In: Thalheim, B. (ed.) Semantics in Databases 1995. LNCS, vol. 1358. Springer, Heidelberg (1998)CrossRefGoogle Scholar
  16. 16.
    Davidson, S.B., Kosky, A.S.: WOL: A language for database transformations and constraints. In: Proc. ICDE 1997, pp. 55–65 (1997)Google Scholar
  17. 17.
    Hainaut, J.-L.: Transformation-based database engineerig. In: Transformation of Knowledge, Information, and Data [48], ch.1, pp. 1–28Google Scholar
  18. 18.
    Hainaut, J.-L., Englebert, V., Henrard, J., Hick, J.-M., Roland, D.: Database evolution: the DB-MAIN approach. In: Loucopoulos, P. (ed.) ER 1994. LNCS, vol. 881, pp. 112–131. Springer, Heidelberg (1994)Google Scholar
  19. 19.
    Hall, P., Owlett, J., Todd, S.J.P.: Relations and entities. In: Nijssen, G.M. (ed.) Modelling in Data Base Management Systems. North-Holland, Amsterdam (1975)Google Scholar
  20. 20.
    Halpin, T.: Information Modeling and Relational Databases. Academic Press, London (2001)Google Scholar
  21. 21.
    Hartmann, S.: Reasoning about participation constraints and Chen’s constraints. In: Proc. 14th Australasian database conference, pp. 105–113. Australian Computer Society (2003)Google Scholar
  22. 22.
    Hick, J.-M., Hainaut, J.-L.: Strategy for database application evolution: The DB-MAIN approach. In: Song, I.-Y., Liddle, S.W., Ling, T.-W., Scheuermann, P. (eds.) ER 2003. LNCS, vol. 2813, pp. 291–306. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  23. 23.
    Jahnke, J.H., Zündorf, A.: Apply graph transformations to database re-engineering. In: Handbook of Graph Grammars and Computing by Graph Transformations, vol. 2, ch.6. World Scientific, Singapore (1999)Google Scholar
  24. 24.
    Jasper, E., Poulovassilis, A., Zamboulis, L.: Processing IQL queries and migrating data in the AutoMed toolkit. Technical Report No. 20, AutoMed (2003)Google Scholar
  25. 25.
    Lenzerini, M.: Data integration: A theoretical perspective. In: Proc. PODS 2002, pp. 233–246. ACM, New York (2002)CrossRefGoogle Scholar
  26. 26.
    Mark, L., Roussopoulos, N.: Integration of data, schema and meta-schema. In: Proc. ER 1983, vol. 1983, pp. 585–602 (1983)Google Scholar
  27. 27.
    McBrien, P.J., Poulovassilis, A.: A formalisation of semantic schema integration. Information Systems 23(5), 307–334 (1998)CrossRefGoogle Scholar
  28. 28.
    McBrien, P.J., Poulovassilis, A.: A uniform approach to inter-model transformations. In: Jarke, M., Oberweis, A. (eds.) CAiSE 1999. LNCS, vol. 1626, pp. 333–348. Springer, Heidelberg (1999)CrossRefGoogle Scholar
  29. 29.
    McBrien, P.J., Poulovassilis, A.: Schema evolution in heterogeneous database architectures, a schema transformation approach. In: Pidduck, A.B., Mylopoulos, J., Woo, C.C., Ozsu, M.T. (eds.) CAiSE 2002. LNCS, vol. 2348, pp. 484–499. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  30. 30.
    McBrien, P.J., Poulovassilis, A.: Data integration by bi-directional schema transformation rules. In: Proc. ICDE 2003, pp. 227–238. IEEE, Los Alamitos (2003)Google Scholar
  31. 31.
    McBrien, P.J., Poulovassilis, A.: Defining peer-to-peer data integration using both as view rules. In: Proc. DBISP2P, at VLDB 2003, pp. 91–107 (2003)Google Scholar
  32. 32.
    Miller, R.J., Ioannidis, Y.E., Ramakrishnan, R.: Schema equivalence in heterogeneous systems: Bridging theory and practice. Information Systems 19(1), 3–31 (1994)CrossRefGoogle Scholar
  33. 33.
    Munch, M.: Programmed graph rewriting system PROGRES. In: Münch, M., Nagl, M. (eds.) AGTIVE 1999. LNCS, vol. 1779, pp. 441–448. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  34. 34.
    Munch, M., Schurr, A., Winter, A.J.: Integrity constraints in the multi-paradigm language progres. In: Ehrig, H., Engels, G., Kreowski, H.-J., Rozenberg, G. (eds.) TAGT 1998. LNCS, vol. 1764, pp. 338–352. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  35. 35.
    Patig, S.: Measuring expressiveness in conceptual modeling. In: Persson, A., Stirna, J. (eds.) CAiSE 2004. LNCS, vol. 3084, pp. 127–141. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  36. 36.
    Petit, J.-M., Toumani, F., Boulicaut, J.-F., Kouloumdjian, J.: Towards the reverse engineering of denormalized relational databases. In: Proc. ICDE 1996, pp. 218–227 (1996)Google Scholar
  37. 37.
    Popa, L., Hernandez, M.A., Velegrakis, Y., et al.: Mapping XML and relational schemas with Clio. In: Proc. ICDE 2002, pp. 498–499 (2002)Google Scholar
  38. 38.
    Poulovassilis, A., Levene, M.: A nested-graph model for the representation and manipulation of complex objects. ACM Trans. on Information Systems 12(1), 35–68 (1994)CrossRefGoogle Scholar
  39. 39.
    Poulovassilis, A., McBrien, P.J.: A general formal framework for schema transformation. Data and Knowledge Engineering 28(1), 47–71 (1998)zbMATHCrossRefGoogle Scholar
  40. 40.
    Rizopoulos, N.: Automatic discovery of semantic relationships between schema elements. In: Proc. of 6th ICEIS (2004)Google Scholar
  41. 41.
    Rizopoulos, N., McBrien, P.J.: A general approach to the generation of conceptual model transformations. In: Pastor, Ó., Falcão e Cunha, J. (eds.) CAiSE 2005. LNCS, vol. 3520, pp. 326–341. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  42. 42.
    Schewe, K.: Design theory for advanced datamodels. In: Proc. 12th Australasian Conf. on Database Technologies, pp. 3–9 (2001)Google Scholar
  43. 43.
    Sheth, A., Larson, J.: Federated database systems. ACM Computing Surveys 22(3), 183–236 (1990)CrossRefGoogle Scholar
  44. 44.
    Song, G., Zhang, K., Kong, J.: Model management through graph transformations. In: Proc. Visual Languages and Human-Centric Computing, pp. 75–82. IEEE, Los Alamitos (2004)CrossRefGoogle Scholar
  45. 45.
    Song, I.Y., Evans, M., Park, E.K.: A comparative analysis of entity-relationship diagrams. Journal of Computer & Software Engineering 3(4), 427–459 (1995)Google Scholar
  46. 46.
    Thalheim, B.: Entity-Relationship Modeling: Foundations of Database Technology. Springer, Heidelberg (2000)zbMATHGoogle Scholar
  47. 47.
    Tong, N.: Database schema transformation optimisation techniques for the AutoMed system. In: James, A., Younas, M., Lings, B. (eds.) BNCOD 2003. LNCS, vol. 2712, pp. 157–171. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  48. 48.
    van Bommel, P.: Transformation of Knowledge, Information, and Data. Idea Group, USA (2005)Google Scholar
  49. 49.
    Wieringa, R.: A survey of structured and object-oriented software specification methods and techniques. ACM Computing Surveys 30(4), 459–527 (1998)CrossRefGoogle Scholar
  50. 50.
    Yan, L.L., Miller, R.J., Haas, L.M., Fagin, R.: Data-driven understanding and refinement of schema mappings. In: Proc. SIGMOD 2001, pp. 485–496 (2001)Google Scholar
  51. 51.
    Zaniolo, C., Melkanoff, M.: A formal approach to the definition and the design of conceptual schemata for database systems. ACM TODS 7(1), 24–59 (1982)zbMATHCrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Michael Boyd
    • 1
  • Peter McBrien
    • 2
  1. 1.PSA Parts LtdLondon
  2. 2.Dept. of ComputingImperial CollegeLondon

Personalised recommendations