DISWEB'06 307 Inter Model Data Exchange of Type Information via a Common Type Hierarchy Andrew Smith and Peter McBrien Dept. Computing, Imperial College London, London SW7 2AZ Abstract. Data exchange between heterogeneous schemas is a difficult problem that becomes more acute if the source and target schemas are from different data models. The data type of the objects to be exchanged can be useful information that should be exploited to help the data exchange process. So far little has been done to take advantage of this in inter model data exchange. Using a common data model has been shown to be effective in data exchange in general. This work aims to show how the common data model approach can be useful specifically in exchanging type information by use of a common type hierarchy. Keywords: data exchange, model management, data modelling 1 Introduction Fagin et al. define data exchange as ‘the problem of taking data structured under a source schema and creating an instance of a target schema that reflects the source data as accurately as possible’ [1]. Data exchange may occur within a single data model, for example when building a relational data ware- house from a number of relational databases. However, it is often necessary to perform inter model data exchange in which two or more different data models are involved, such as when XML is used as data exchange format between a number of databases, which may use relational, XML, or other models for their internal storage of data. One of the most challenging aspects of data exchange is how to transform constraints on the source schema to the target schema. This is particularly dif- ficult if the source and target schemas come from different data models. Type information forms part of these constraints [2]. The inter model transformation of integrity constraints, like primary and foreign keys, has been investigated [3, 4] and data types have received attention in the field of database programming languages [2], but little has been written about how simple types, i.e. integer, float, string etc., should be transformed between models in a data exchange environment. The solution we present is a graph based logical type hierarchy that can represent the data types of multiple data models and that links similar data types from different models by defining bi-directional mappings from the high level data types to a common, extensible hierarchy of data types. Cardelli [5] points out that the purpose of type systems is to prevent execution errors in 308 Data Integration and the Semantic Web the running of a program. We present a system that attempts to prevent data errors during data exchange. The contributions this paper makes are as follows: – Offer a way of improving the expressiveness and safety of inter model trans- formations in a data exchange environment by adding type information. – Provide a way of transforming data between schemas whose data types sup- port different values. – Show when transformations are illegal, when they need to be checked for data errors and when they do not, based on the data types of the source and target constructs. The rest of the paper is organised as follows. Section 2 provides motivation by describing some of the difficulties inherent in data type exchange. Section 3 describes the formal definition of our type system. Section 4 introduces the AutoMed automatic mediation system which we have used to test our approach. Section 5 describes how the new type system can be added to AutoMed along with the definition of a number of operators that can be applied to the data types of objects in AutoMed. Section 6 describes a data exchange scenario in AutoMed using the new type system. Section 7 describes some other approaches to trans- formation of data types in a data exchange system. Finally some conclusions are drawn and some of our on-going work is described. 2 Motivation In an inter model data exchange system with a typed target schema it is neces- sary to transform the data type of source schema objects to the target schema. Current solutions make use of simple one to one matching between data types in different models [6, 7]. This approach can lead to some problems: – The data type of the source object may allow a greater range of values than that of the target object. This could lead to run-time errors when the materialised target schema is populated with data from the source schema. – Types representing an identical concept may support a different range of values. For example, a boolean in one data modelling language may represent true as 1 while another may represent it as T. Again populating the target schema would cause errors. Some way of mapping the data values between the source and target is required. Our solution is to represent the data types in a data exchange system as a directed acyclic graph (DAG) and to define a number of operations on the graph that can be used to overcome the problems described above. Hierarchies exist in some well known type systems, for example, Figure 1 is a portion of the XML Schema [8] type hierarchy. However, for data exchange purposes, the familiar tree hierarchy of Figure 1 has several short comings due to the hierarchy not fully modelling the domain of data values in XML. In particular: DISWEB'06 309 – Figure 1 does not distinguish between types which are disjoint in their ex- tent, such as positiveInteger (representing all positive integer values) and negativeInteger (representing all negative integer values), and those which overlap, such as int (representing −231 ..231 − 1) and unsignedInt (represent- ing 0..232 − 1). In data exchange, a mapping between source and target objects where the types are disjoint should be ruled illegal, unless an explicit conversion has been defined, but a mapping between objects that overlap should be allowed, with runtime range checking. – Figure 1 fails to identify all isa associations in the hierarchy, shown as dashed lines in the figure. For example, all unsignedShort values (which are in the range 0..216 − 1) are a subset of int values and all values in XML can be represented as string. In data exchange, if the source object type is a subset of the target object type, then the values may be cast without runtime range checking, since the cast will never fail. anyType string decimal boolean integer nonPositive nonNegative Integer Integer negative long unsigned positive Integer Long Integer int unsigned Int short unsigned Short Fig. 1. A portion of the XML Schema type hierarchy [9] A particular problem in data exchange is found when transferring between different type systems. Figure 2 shows a portion of a type hierarchy built for Postgres, showing some of the built-in types, and following the built-in casting rules, giving some isa relationships. When translating between the types of XML and Postgres the type systems need to be unified. Two difficulties arise from the fact that the modelling of the type systems might be quite different: 310 Data Integration and the Semantic Web anyType int boolean integer bit(n) text int4 bool smallint varchar(n) int2 char(n) Fig. 2. A portion of the Postgres type hierarchy – The types might not be named consistently. For example the Postgres integer (a 4-byte integer in the range −231 ..231 − 1) semantically corresponds to the XML int type, and not the XML integer type. Also the types might not be stored consistently: in XML all data is held as strings, whilst in Postgres the integer will be held as a twos complement binary number. – There may be no equivalent type in the target model as compared with a source model type. For example, the bit(n) type of Postgres has no direct equivalent in XML. Hence in the following sections we introduce our own definition of a type hierarchy that is suited to data exchange applications. In particular, it builds hierarchies solely on the range of data values a type may take. We then demon- strate how mapping rules between schemas in different modelling languages may be made type safe. 3 Data Exchange Type Hierarchy To facilitate the precise representation of types in a data exchange environment, we introduce in Definition 1 a logical type hierarchy to be used to describe the types of a single or collection data modelling languages in a manner that allows us to address the problems discussed in the previous section. We will show that this type hierarchy can also be used to capture some semantics of types that are specific to a particular schema. Definition 1. Type Hierarchy t A type hierarchy T Hx is a tuple hT ypesx , Extx , =x , ≺x , 6 ∩x , M appingx i where: – A finite set of type names T ypesx . These will make up the nodes of the graph. – An Extx function that returns a subset of the set of all possible data values anyT ypex of the hierarchy that is consistent with a type: t ∈ T ypesx → Extx (t) ⊆ Extx (anyT ypex ) The type anyT ypex represents the set of data values that a particular lan- guage (or collection of languages) may handle, and has the property that DISWEB'06 311 Extx (anyT ypex ) ⊆ C where C is the set of all data values that may be handled by the data exchange system. t – An equality relation, =x , such that for t, t0 ∈ T ypesx t t =x t0 ⇐⇒ Extx (t) = Extx (t0 ) – A partial ordering relation ≺x , such that for t, t0 ∈ T ypesx t ≺x t0 ⇐⇒ Extx (t) ⊂ Extx (t0 ) t When all types t, t0 ∈ T ypesx that have t =x t0 are treated as a single node, the ≺x relation builds the types into a connected directed acyclic graph. t =x and ≺x together make up the edges of the graph. – A disjoint operator, 6 ∩x , such that for t, t0 ∈ T ypesx t 6 ∩x t0 ⇐⇒ Extx (t) ∩ Extx (t0 ) = φ. This implies there is no pathway from t to t0 in the graph and so we cannot cast between t and t0 . If t 6 ∩x t0 then any subtype of t will also be disjoint from t0 . – A set M appingx of mapping tables hta , tb , {hs1a , s1b i, . . . , hsna , snb i}i, where ta , tb ∈ T ypesx , s1a , . . . , sna are subsets of Ext(ta ) and are disjoint. Similarly s1b , . . . , snb are subsets of Ext(tb ) and are disjoint. We overload M appingx to be used as a function with the following definition: M appingx (ta , tb , va ) = First(snb ) | hta , tb , mapi ∈ M appingx ∧ hsna , snb i ∈ map ∧ va ∈ sna M appingx−1 (ta , tb , va ) = First(snb ) | htb , ta , mapi ∈ M appingx ∧ hsnb , sna i ∈ map ∧ va ∈ sna where First returns the first element of a set according to a sort order that is fixed for the system. We use M appingx (typea , typeb ) to denote the specific mapping table that maps typea to typeb . Examples 1 and 2 illustrate the values for the type hierarchy for the XML and Postgres type models. Example 1. The type hierarchy for the XML Schema data modelling language, T Hxml , can be derived from Figure 1 as follows: T ypesxml = {anyT ypexml , shortxml , intxml , nonP ositiveIntegerxml , negativeIntegerxml , stringxml , . . . } Extxml = {booleanxml → {0, 1, true, f alse}, shortxml → {-32768, . . . ,32767}, . . . } t t =xml = {anyT ypexml = stringxml } ≺xml = {shortxml ≺ intxml , unsignedShortxml ≺ intxml , intxml ≺ longxml , longxml ≺ integerxml , integerxml ≺ stringxml . . . } 6 ∩xml = {negativeIntegerxml 6 ∩ positiveIntegerxml , . . . } M appingxml = {} The Postgres type hierarchy in Example 2 is quite different. The integer and varchar branches of the hierarchy are quite distinct, since converting an integer to a varchar in Postgres requires a mapping function to be used. Example 2. From the Postgres RDBMS type system illustrated in Figure 2, we derive the type hierarchy T Hpg as: 312 Data Integration and the Semantic Web T ypespg = {anyT ypepg , booleanpg , boolpg , integerpg , intpg , int4pg , smallintpg , int2pg , char(n)pg , varchar(n)pg , textpg . . . } Extpg = {booleanpg → {‘0’,‘1’,‘y’,‘n’,‘yes’,‘no’,‘t’,‘f’,true,false}, smallintpg → {-32768, . . . , 32767}, . . . } t t t t =pg = {booleanpg = boolpg , intpg = integerpg , intpg = int4pg , . . . } ≺pg = {smallintpg ≺ integerpg , integerpg ≺ bigintpg , bigintpg ≺ anyT ype, varchar(1)pg ≺ varchar(2)pg , charpg ≺ varcharpg , varcharpg ≺ textpg , textpg ≺ anyT ypepg , . . . } 6 ∩pg = {integerpg 6 ∩ varcharpg , booleanpg 6 ∩ varchar, . . . } M appingpg = {} Example 3. Type Mapping for Postgres During a single model data exchange, it might be found that the boolean type in one Postgres database should map to 0 or 1 of type smallint in another Postgres database. This can be achieved by including the mapping table shown below: M appingpg (booleanpg , smallintpg ) = {hbooleanpg , int2pg , {h{‘0’,‘n’,‘no’,‘f’,false}, {0}i, h{‘1’,‘y’,‘yes’,‘t’,true}, {1}i}i} 3.1 The Common Type Hierarchy If the source and target schemas are defined in different data modelling languages we need a way of linking the type hierarchy defined for the source model, the source type hierarchy, to that defined for the target model, the target type hierarchy. To do this we introduce the extensible common type hierarchy (CTH). Using the common hierarchy as an intermediary means that we only need to create one set of associations between the high level data types of a given model and those of the CTH. We do not need to define new associations each time we are faced with a new target model. Definition 2. Common type hierarchy T ypesc = {anyT ypec , stringc , charc , integerc , shortc , f loatc , realc , booleanc } Extc = {booleanc → {true, f alse}, integerc → { − 231 , . . . , 231 − 1}, shortc → { − 32768, . . . , 32767}, . . . } t =c = {} ≺c = {shortc ≺ integerc , integerc ≺ anyT ypec , realc ≺ f loatc , f loatc ≺ anyT ypec , charc ≺ stringc , stringc ≺ anyT ypec , booleanc ≺ anyT ypec } 6 ∩c = {integerc 6 ∩ booleanc , integerc 6 ∩ f loatc , . . . } M appingc = {} During an inter model data exchange the source and target type hierarchies will be merged with the CTH to form an inter model type hierarchy. Definition 3 DISWEB'06 313 gives a procedure for building such an inter model type hierarchy T H xc from a data model’s type hierarchy T Hx , and existing inter model type hierarchy T Him , and a (possibly extended) CTH T Hc . Definition 3. Inter model type hierarchy Merge(T Hx ,T Him ,T Hc ,CMxc ) T ypesxc := T ypesx ∪ T ypesim Extxc := Extx ∪ Extim 6 ∩xc := 6 ∩x ∪ 6 ∩im ≺xc := ≺x ∪ ≺im t t t =xc := =x ∪ =im M appingxc := M appingx ∪ M appingim ∪ CMxc for each tx ∈ T ypesx txc := anyT ypec for each tc ∈ T ypesc if Ext(tx ) ⊆ Ext(tc ) ∧ Ext(tc ) ⊆ Ext(txc ) then txc := tc endif end if Ext(tx ) ⊂ Ext(txc ) t0c := NewType(tx ) T ypesc := T ypesc ∪ {t0c } ≺c := ≺c ∪{t0c  txc } txc = t0c for each tc ∈ T ypesc if Ext(tc ) 6 ∩Ext(t0c ) then 6 ∩c := 6 ∩c ∪ {tc 6 ∩ t0c } endif end end t t t =xc := =xc ∪ {tx =xc txc } end t return hT ypesxc , Extxc , 6 ∩xc , =xc , ≺xc , M appingxc i The function NewType(t) generates a new type t0 such that Ext(t0 ) = Ext(t). Example 4. Constructing an inter model type hierarchy Assume that XML Schema is our source data modelling language, Postgres is our target modelling language and we use the CTH in Definition 2. We will also assume the following reduced type hierarchies for XML and Postgres: T Hxml = h{anyT ypexml , booleanxml , integerxml , negativeIntegerxml }, {integerxml → { − 231 , . . . , 231 − 1}, negativeIntegerxml → { − 231 , . . . , 0}, booleanxml → {0, 1, true, f alse}}, {}, {booleanxml  anyT ypexml , integerxml  anyT ypexml , negativeIntegerxml  integerxml }, {}, {}i 314 Data Integration and the Semantic Web T Hpg = h{anyT ypepg , booleanpg , int4pg , smallintpg }, {int4pg → { − 231 , . . . , 231 − 1}, smallintpg → { − 32768, . . . , 32767}, booleanpg → {‘0’,‘1’,‘y’,‘n’,‘yes’,‘no’,‘t’,‘f’,true,false}}, {}, {booleanpg  anyT ypepg , int4pg  anyT ypepg , smallintpg  int4pg }, {booleanpg 6 ∩ int4pg }, {}i Using Definition 3 we first extend the CTH with the XML types to get a inter model type hierarchy T Him T Him = Merge(T Hxml , T Hc , T Hc , hbooleanxml , booleanc , {h{0,false}, {false}i, h{1,true}, {true}i}i) As a side effect, T Hc has the following changes: T ypesc := T ypesc ∪ {negativeIntegerc } c :=c ∪{negativeIntegerc ≺ integerc } t and the following inter model equalities are found in =im : t t t =im = {integerxml = integerc , negativeIntegerxml = negativeIntegerc , . . . } No additional disjoint relations are added. We can now add in the Postgres type hierarchy to expand the inter model hierarchy to T H im0 : T Him0 = Merge(T Hpg , T Him , T Hc , hbooleanpg , booleanc , {h{‘0’,‘n’,‘no’,‘f’,false}, {false}i, h{‘1’,‘y’,‘yes’,‘t’,true}, {true}i}i) No new changes to T Hc occur, but the following additional inter model equalities t are found in =im0 : t t t =im0 = {int4pg = integerc , smallintpg = shortc , . . . } Note that the two mapping tables in T Him0 , M appingim0 (booleanxml , booleanc ) −1 and M appingim 0 (booleanpg , booleanc ) allow us to map from a boolean in XML to a boolean Postgres. 3.2 Reducing constraint checking The inter model type hierarchy described above can help us decide whether or not to add constraints. For example shortxml and smallintpg are both equiva- lent to shortc . We can say with confidence that any value from a construct of type shortxml can be stored in a construct of type smallintpg . If we later ex- panded our system to include schemas from Microsoft SQL Server and discover that smallintms also maps to shortc we would know that values from all three modelling languages could be safely interchanged without checking. This method can also highlight when checking is needed. Any time it is neces- sary to move down the merged inter model hierarchy to transform from one high level type to another we know that checking is necessary. For example assume we have an XML source schema that contains an element of type integer xml , equivalent to integerc and a target of a Postgres column of type smallintpg , equivalent to shortc . We know from Definition 2 that shortc ≺ integerc . To get from integerxml to smallintpg we need to go via integerc and then down the hierarchy to shortc . The checking is necessary here because we know from the definition that Ext(integerc ) ⊃ Ext(shortc ). It may be necessary to find a common ancestor in the merged inter model hierarchy to be able to move between certain source and target data types. DISWEB'06 315 In Example 4 we added negativeIntegerc to the hierarchy. To transform from negativeIntegerc to shortc we need to go via a type in the merged hierarchy that is an ancestor of both types, in this case integer c . If no such ancestor, other than the root node anyT ypec , can be found the type transformation is invalid. As with the previous example, the step from integerc to shortc is down the hierarchy so a constraint is generated. Finally we can identify illegal castings. If our pathway from source to tar- get includes data types t and t0 such that t 6 ∩ t0 then the cast is illegal from Definition 1. 4 AutoMed AutoMed [10] is a data integration and exchange system developed as a joint project between Imperial College London and Birkbeck College. It has been used successfully for data integration of schemas from a number of different data models including both XML and relational schemas. AutoMed handles multiple data models defining the constructs of a higher level modelling language such as the relational model or XML in a lower level hypergraph data model (HDM) [11, 12]. Definition 4. HDM Schema Given a set of N ames that we may use for modelling the real world, an HDM schema, S, is a triple hN odes, Edges, Consi where: – N odes ⊆ {hhnn ii | nn ∈ N ames} i.e. N odes is a set of nodes in the graph, each denoted by its name enclosed in double chevron marks. – Schemes = N odes ∪ Edges – Edges ⊆ {hhne , s1 , . . . , sn ii | ne ∈ N ames∪{ }∧s1 ∈ Schemes∧. . .∧sn ∈ Schemes} i.e. Edges is a set of edges in the graph where each edge is denoted by its name, together with the list of nodes/edges that the edge connects, enclosed in double chevron marks. – Cons ⊆ {c(s1 , . . . , sn ) | c ∈ F uncs ∧ s1 ∈ Schemes ∧ . . . ∧ sn ∈ Schemes} i.e. Cons is a set of boolean-valued functions (i.e. constraints) whose vari- ables are members of Schemes and where the set of functions F uncs forms the HDM constraint language. The extent of a node or edge is returned by the function Ext S,I where I is a specific instance of the schema S. Thus ExtS,I (hhnii) returns the values associated with node hhnii. As detailed in [11, 12], the HDM may be used to model a wide range of higher level modelling languages, and we develop the techniques in [12] to handle types in translating between one higher level modelling language and another by using the HDM as a common data model (CDM). Using the simple HDM constructs defined above, the extensional constructs of higher level modelling languages can be defined, based on the HDM. In [13], 316 Data Integration and the Semantic Web higher level modelling language constructs were classified into (1) nodal con- structs, which can exist independently, and map to nodes in the HDM, (2) link- nodal constructs, which must be attached to other constructs, but have some additional data, which map to a node and an edge in the HDM, and (3) link- ing constructs, which associate data values in existing constructs, and map onto edges in the HDM. For example, in an ER model, entities are nodal constructs, attributes are link-nodal, and relationships linking constructs. Once the con- structs of the new modelling language have been defined in the HDM, we can define transformations that allow us to add, delete and rename these constructs. 4.1 Data Exchange in AutoMed In AutoMed, data exchange is done in two phases: first the transformation path- ways are set up, and second the data values are transformed using those path- ways. This is roughly analogous to compile and run time for a conventional program. Setting up the pathways is a static operation whose complexity is lin- ear in the number of constructs to be mapped. It can be done before data from the data source is imported into the system. The complexity of transforming the data values during run-time depends on the data involved and is less easy to quantify. 4.2 Example of Data Exchange without Type Information Figures 3 and 4 show two schemas modeling the same Universe of Discourse (UoD), namely account debits. We wish to transform the XML Schema in Figure 3 in such a way that we can exchange data between it and the SQL table in Figure 4. hxsd:element name=“ledger”i hxsd:complexTypei hxsd:sequencei hxsd:element name=“cash” type=“xsd:negativeInteger”/i hxsd:element name=“complete” type=“xsd:boolean”/i h/xsd:sequencei h/xsd:complexTypei h/xsd:elementi Fig. 3. XML Schema fragment 1 On the face of it the transformation is very simple. The values in the complete element in the XML schema will be added to those in the complete column in the relational table, and those in the cash element will be added to the cashIn column. However, this example highlights some problems we may face if we ignore type information when transferring data between XML and SQL. DISWEB'06 317 CREATE TABLE money ( cashIn smallint, complete boolean ) Fig. 4. Postgres definition of table money The XML Schema element cash with type negativeInteger can contain any negative integer whereas the largest negative number the Postgres column cashIn with type smallint is -32678. If the XML file had a value less than -32678 in it, attempting to put that into the Postgres table would cause an error. Similarly if we try to put the boolean value 0 from the complete element into the boolean column complete the operation will fail, since there are XML boolean values that cannot be stored in a Postgres boolean column and we have not specified how to map the XML boolean values into Postgres. These transformations are not type safe. 5 Adding the Type System to AutoMed To add types to the AutoMed system, we extend the Definition 4 by adding t a type hierarchy T H = hT ypes, Ext, =, ≺, 6 ∩, M appingi from Definition 1 to make a typed HDM schema be a tuple hN odes, Edges, Constraints, T Hi. The scheme of each node will have an extra component, t ∈ T ypes added, making the scheme of a node be hhn, tii The extent of a node can now be defined as a subset of the values represented by the node’s type so for x ∈ hhn, tii → x ∈ Ext(t), i.e. hhn, tii ∈ Ext(t). Note that edges connect other nodes and edges, and therefore their type can always be inferred from the base nodes they connect. The primitive node operations described in [11, 12] are modified and ex- panded on to incorporate the new type information as follows. 1. A new operation getNodeType(q) returns the type, t, of a query q. 2. The primitive transformations add and delete are adapted slightly: – addNode(hhn, tii, q) returns a new schema by adding a node n of type t to t the schema, where getNodeType(q) = t. The extent of the node is given by the value of the IQL (Intermediate Query Language) [14] query q. – deleteNode(hhn, tii, q) returns a new schema by deleting a node from the schema, where the value of the node may be recovered from q, and t getNodeType(q) = t It may be necessary to change the data type of a node during a transforma- tion. We present two new primitive operations to allow this. These changes are done on the inter model type hierarchy. 318 Data Integration and the Semantic Web Definition 5. changeNodeType(hhn, told ii, hhn, tnew ii) Condition: Ext(told ) ∩ Ext(tnew ) 6= φ, returns a new schema which differs only in that node hhnii has a different type. If told 6≺ tnew this operation will generate the following constraint used during query processing: ∀hxi ∈ hhn, told ii.x ∈ Ext(tnew ). Definition 6. convertNodeType(hhn, told ii, hhn, tnew ii, M appingim (told , tnew )) de- fines a bidirectional type conversion from a node of type t old to type tnew . Each value in the extent of hhn, told ii is mapped to a value in the extent of tnew using the mapping tables and function from Definition 1. This section has shown how our formalism can be applied to the AutoMed system by the addition of primitive operations to manipulate the types of the nodes in a schema. However, the method in Section 3 could equally well be applied to other data exchange systems. 6 AutoMed Transformation with Data Types We can now define an AutoMed transformation pathway between the XML and SQL schemas from Section 4.2 using the operators defined above. The pathway is shown in Example 5. The initial data type of each node matches the data type of the corresponding data source object. For example if we add a node representing the Postgres column complete from Figure 4 with type boolean, a node hhcomplete, boolean pg ii will be created using the addNode operator. The extents of the high level model types are the set of allowable values as defined by the data source. For example the extent of short xml as defined by the XML Schema standard in [9] will be the integers from -32768 to 32767. We merge T Hpg of Example 2 and T Hxml of Example 1 with the CTH as shown in Example 4 to form T Him0 . Example 5. Type safe transformation pathway 1 changeNodeType(hhcashxml , negativeIntegerxml ii, hhcashxml , negativeIntegerc ii) 2 convertNodeType(hhcompletexml , booleanxml ii, hhcompletepg , booleanc ii, Mappingim0 (booleanxml , booleanc )) 3 addNode(hhcashInpg , negativeIntegerc ii, hhcashxml , negativeIntegerc ii) 4 addNode(hhcompletepg , booleanc ii, hhcompletexml , booleanc ii) 5 deleteNode(hhcompletexml , booleanc ii, hhcompletepg , booleanc ii) 6 deleteNode(hhcashxml , negativeIntegerc ii, hhcashInpg , negativeIntegerc ii) 7 convertNodeType(hhcompletepg , booleanc ii, hhcompletepg , booleanpg ii, Mappingim0 (booleanpg , booleanc )) 8 changeNodeType(hhcashInpg , negativeIntegerc ii, hhcashInpg , smallintpg ii) Two nodes hhcashxml , negativeIntegerxml ii and hhcompletexml , booleanxml ii repre- senting the XML Schema elements along with their data types are created by the wrapping process. Before adding nodes to represent the Postgres columns DISWEB'06 319 we change the type of the XML node to its equivalent in the CTH 1 because t we have negativeIntegerxml = negativeIntegerc . 2 uses the mapping defined in Example 4. In transformations 7 and 8 we convert the data types of the nodes from the HDM to the Postgres model. In 7 we change the type of hhcompletepg , booleanc ii using the convertNodeType operation. We again use the mapping defined in Ex- ample 4, but this time the inverse of the function to map the values of the CTH boolean to the Postgres boolean. This overcomes the incompatibility of the XML Schema boolean and Postgres boolean data types and solves the second problem from the example in Section 4.2. Finally in 8 we change the type of node hhcashInpg , negativeIntegerc ii using t changeNodeType. smallintpg =shortc but shortc 6≺ negativeIntegerc so we need to find a common ancestor. The common ancestor is integer c . Since we have to move down the hierarchy to get from integerc to shortc the constraint: ∀x ∈ hhcashxml , negativeIntegerxml ii.x ∈ Ext(smallintpg ) is generated from Definition 5. The transformation is legal because there are no disjoint pairs of types in the pathway. We can check the constraint as we transfer data into the SQL table and so be guaranteed that we will not get any errors from the database. This solves the first problem we had in the example in Section 4.2. After transformations 1 – 8 we have the nodes hhcashInpg , smallintpg ii and hhcompletepg , booleanpg ii, that correspond to the columns in the Postgres table in Figure 4. Using the type hierarchy has allowed us to identify a mapping between the XML and Postgres boolean data types. This was done automatically at compile- time, based on the types of the nodes involved. This could not have been done without using the type information. We have also identified a potential type casting problem that will need to be checked during run-time. Without the explicit identification of the latter problem a system would either need to check every transformation for type safety during the data value exchange or adopt a no-checking policy that could lead to unexpected problems. 7 Related Work A number of papers have shown how to transform schemas from one model to another, most commonly XML to relational [15–17]. There are also systems that will exchange data between a number of different models [18, 12]. AutoMed falls into this category. Transforming integrity constraints from one model to another has also received some attention [3]. There does not, however, seem to have been much written about exchanging primitive type information between different models and in particular manipulating that information during the transformation process. Some methods ignore the problem [15, 7] and make no explicit mention of how data type from one model are transformed into the other model. Rahm and Bernstein [6] suggest using a special synonym table to match data types 320 Data Integration and the Semantic Web between different models to each other, an approach they adopt in Cupid [19]. This method is effective when mapping between two specific models but does not scale well to a system like AutoMed that supports multiple models. A number of systems provide support for data types. TSIMMIS [20] allows data types to be stored as part of their Object-Exchange Model [21] but there is no mechanism to manipulate the data types. WOL [22] is another language for database transformations that stores type information, however, the lan- guage is only able to describe transformations in relational and object-relational databases, not inter model transformations. The Clio system [1, 23] defines a number of value based source-to-target dependencies that specify how and what source data should appear in the target. This data-centric approach does not make use of type information in the source schema to help map to the target schema. In ignoring type information these systems risk losing expressiveness during the transformations [2] and allowing type-incompatible transformations to be written. We have shown that there are times when data types are significant and should not be ignored. 8 Conclusions and Future Work We have presented a method of improving the expressiveness of inter model data exchange between models that have constructs with associated data types. The method relies on converting the types from the source into a common type hierarchy capable of representing types from any data source, and from there into types from the target schema. Types can be cast from one type to another and mappings can be defined between disjoint types. A formal definition of the type system has been provided and it has been shown how this can be included in the existing AutoMed system. An example inter model transformation with and without using the type system was presented to show the advantages of using the type system. The type hierarchy described above has been implemented in AutoMed and has been used for data exchange from source schemas in a number of different models to an empty target schema in the relational and XML Schema models. In the future we will extend the use of the mapping function to single model data exchange where for instance one Postgres database represents boolean val- ues as single characters ‘t’ and ‘f’ of type char(1) while another database may use a field of type boolean. We also hope to increase the efficiency of the method by defining direct transformation rules between certain well-known data models, bypassing the need to transform each data type into its HDM equivalent first. References 1. Fagin, R., Kolaitis, P.G., Miller, R.J., Popa, L.: Data exchange: Semantics and query answering. In: ICDT. (2003) 207–224 2. Atkinson, M.P., Buneman, P.: Types and persistence in database programming languages. ACM Comput. Surv. 19(2) (1987) 105–190 DISWEB'06 321 3. Davidson, S.B., Fan, W., Hara, C., Qin, J.: Propagating XML Constraints to Relations. In: ICDE. (2003) 543–554 4. Calı̀, A., Calvanese, D., Giacomo, G.D., Lenzerini, M.: Data integration under integrity constraints. Inf. Syst. 29(2) (2004) 147–163 5. Cardelli, L.: Type systems. ACM Comput. Surv. 28(1) (1996) 263–264 6. Rahm, E., Bernstein, P.A.: A survey of approaches to automatic schema matching. VLDB J. 10(4) (2001) 334–350 7. C. Liu, M. Vincent, J.L., Guo, M.: A virtual XML database engine for relational databases. XSYM 2003 (2003) 8. Henry S. Thompson et al. Eds: XML Schema part 1: Structures. http://www.w3.org/TR/xmlschema-1 (2001) 9. Paul V. Biron et al. Eds: XML Schema part 2: Datatypes second edition. http://www.w3.org/TR/xmlschema-2 (2004) 10. M. Boyd, S. Kittivoravitkul, C. Lazanitis, P.J. McBrien and N. Rizopoulos: Au- toMed: A BAV Data Integration System for Heterogeneous Data Sources. In: CAiSE04. Volume 3084 of LNCS., Springer Verlag (2004) 82–97 11. McBrien, P., Poulovassilis, A.: A general formal framework for schema transfor- mation. In: Data and Knowledge Engineering. Volume 28. (1998) 47–71 12. Boyd, M., McBrien, P.: Comparing and transforming between data models via an intermediate hypergraph data model. J. Data Semantics IV (2005) 69–109 13. McBrien, P., Poulovassilis, A.: A semantic approach to integrating XML and structured data sources. In: Advanced Information Systems Engineering. Volume 2068 of LNCS., Springer Verlag (2001) 330–345 14. Poulovassilis, A.: A tutorial on the IQL query language. AutoMed Technical Report http://www.doc.ic.ac.uk/automed/ (2004) 15. Phil Bohannon et al.: From XML Schema to relations: A cost-based approach to XML storage. In: Proc. of Intl. Conf. on Data Engineering (ICDE). (2002) 16. Ferández, M., Tan, W.C., Suciu, D.: Silkroute: Trading between relations and XML. In: Proceedings of the Ninth International World Wide Web Conference. (2000) 17. Jayavel Shanmugasundaram et al.: A general techniques for querying XML docu- ments using a relational database system. SIGMOD Record 30(3) (2001) 20–26 18. Fagin, R., Kolaitis, P.G., Popa, L.: Data exchange: getting to the core. ACM Trans. Database Syst. 30(1) (2005) 174–210 19. Madhavan, J., Bernstein, P.A., Rahm, E.: Generic schema matching with cupid. In: VLDB. (2001) 49–58 20. Garcia-Molina, H., Papakonstantinou, Y., Quass, D., Rajaraman, A., Sagiv, Y., Ullman, J.D., Vassalos, V., Widom, J.: The tsimmis approach to mediation: Data models and languages. J. Intell. Inf. Syst. 8(2) (1997) 117–132 21. Papakonstantinou, Y., Garcia-Molina, H., Widom, J.: Object exchange across heterogeneous information sources. In Yu, P.S., Chen, A.L.P., eds.: 11th Conference on Data Engineering, Taipei, Taiwan, IEEE Computer Society (1995) 251–260 22. Susan Davidson and A. Kosky: WOL: A Language for Database Transformations and Constraints. In: Proceedings of the International Conference of Data Engi- neering. (1997) 55–65 23. Miller, R.J., Haas, L.M., Hernández, M.A.: Schema mapping as query discovery. In: VLDB. (2000) 77–88