Data exchange between heterogeneous schemas is a di cult problem that becomes more acute if the source and target schemas are from di erent 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 e ective in data exchange in general. This work aims to show how the common data model approach can be useful speci cally in exchanging type information by use of a common type hierarchy.
Fagin et al. de ne data exchange as `the problem of taking data structured
under a source schema and creating an instance of a target schema that
re ects the source data as accurately as possible' [
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
difcult if the source and target schemas come from di erent data models. Type
information forms part of these constraints [
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 di erent models by de ning bi-directional mappings from the high
level data types to a common, extensible hierarchy of data types. Cardelli
[
The contributions this paper makes are as follows: { O er a way of improving the expressiveness and safety of inter model transformations in a data exchange environment by adding type information. { Provide a way of transforming data between schemas whose data types support di erent 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 di culties inherent in data type exchange. Section 3 describes the formal de nition 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 de nition 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 transformation of data types in a data exchange system. Finally some conclusions are drawn and some of our on-going work is described. 2
In an inter model data exchange system with a typed target schema it is
necessary 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 di erent models [
Our solution is to represent the data types in a data exchange system as a
directed acyclic graph (DAG) and to de ne 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 [
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 de ned, 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 gure. 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.
string nonPositive
Integer negative Integer
A particular problem in data exchange is found when transferring between di erent 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 uni ed. Two di culties arise from the fact that the modelling of the type systems might be quite di erent: int integer int4 smallint int2 { 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 de nition 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 demonstrate how mapping rules between schemas in di erent modelling languages may be made type safe. 3
To facilitate the precise representation of types in a data exchange environment, we introduce in De nition 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 speci c to a particular schema.
A type hierarchy T Hx is a tuple hT ypesx; Extx; =t x; x; 6 \x; M appingxi where: { A nite 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 2 T ypesx ! Extx(t) Extx(anyT ypex) The type anyT ypex represents the set of data values that a particular language (or collection of languages) may handle, and has the property that Extx(anyT ypex) C where C is the set of all data values that may be handled by the data exchange system. { An equality relation, =t x, such that for t; t0 2 T ypesx
t =t x t0 () Extx(t) = Extx(t0) { A partial ordering relation x, such that for t; t0 2 T ypesx t x t0 () Extx(t) Extx(t0) When all types t; t0 2 T ypesx that have t =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 2 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; fhs1a; sb1i; : : : ; hsan; sbnigi, where ta; tb 2 T ypesx, s1a; : : : ; san are subsets of Ext(ta) and are disjoint. Similarly sb1; : : : ; sbn are subsets of Ext(tb) and are disjoint.
We overload M appingx to be used as a function with the following de nition: M appingx(ta; tb; va) = First(sbn) j hta; tb; mapi 2 M appingx ^ hsan; sbni 2 map ^ va 2 sa n M appingx 1(ta; tb; va) = First(sbn) j
htb; ta; mapi 2 M appingx ^ hsbn; sani 2 map ^ va 2 san where First returns the rst element of a set according to a sort order that is xed for the system. We use M appingx(typea; typeb) to denote the speci c 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 = fanyT ypexml; shortxml; intxml; nonP ositiveIntegerxml; negativeIntegerxml; stringxml; : : : g Extxml = fbooleanxml ! f0; 1; true; f alseg;
shortxml ! f-32768, . . . ,32767g; : : : g =xml = fanyT ypexml =t stringxmlg t xml = fshortxml intxml; unsignedShortxml intxml; intxml longxml; longxml integerxml; integerxml stringxml : : : g 6 \xml = fnegativeIntegerxml 6 \ positiveIntegerxml; : : : g M appingxml = fg The Postgres type hierarchy in Example 2 is quite di erent. 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: T ypespg = fanyT ypepg; booleanpg; boolpg; integerpg; intpg; int4pg; smallintpg; int2pg; char(n)pg; varchar(n)pg; textpg : : : g Extpg = fbooleanpg ! f`0',`1',`y',`n',`yes',`no',`t',`f',true,falseg;
smallintpg ! f-32768; : : : ; 32767g; : : : g =pg = fbooleanpg =t boolpg; intpg =t integerpg; intpg =t int4pg; : : : g t pg = fsmallintpg integerpg; integerpg bigintpg; bigintpg anyT ype; varchar(1)pg varchar(2)pg; charpg varcharpg; varcharpg textpg; textpg anyT ypepg; : : : g 6 \pg = fintegerpg 6 \ varcharpg; booleanpg 6 \ varchar; : : : g M appingpg = fg
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) = fhbooleanpg; int2pg; fhf`0',`n',`no',`f',falseg; f0gi; hf`1',`y',`yes',`t',trueg; f1gigig 3.1
If the source and target schemas are de ned in di erent data modelling languages we need a way of linking the type hierarchy de ned for the source model, the source type hierarchy, to that de ned 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 de ne new associations each time we are faced with a new target model.
T ypesc = fanyT ypec; stringc; charc; integerc; shortc;
f loatc; realc; booleancg Extc = fbooleanc ! ftrue; f alseg; integerc ! f
shortc ! f 32768; : : : ; 32767g; : : : g t =c = fg c = fshortc integerc; integerc anyT ypec; realc f loatc anyT ypec; charc stringc; stringc anyT ypec; booleanc anyT ypecg 6 \c = fintegerc 6 \ booleanc; integerc 6 \ f loatc; : : : g M appingc = fg 231; : : : ; 231
1g; f loatc;
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. De nition 3 gives a procedure for building such an inter model type hierarchy T Hxc from a data model's type hierarchy T Hx, and existing inter model type hierarchy T Him, and a (possibly extended) CTH T Hc.
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 =xc := =t x [ =im t t M appingxc := M appingx [ M appingim [ CMxc for each tx 2 T ypesx txc := anyT ypec for each tc 2 T ypesc if Ext(tx) Ext(tc) ^ Ext(tc)
Ext(txc) then txc := tc endif end end if Ext(tx) Ext(txc) t0c := NewType(tx) T ypesc := T ypesc [ ft0cg
c := c [ft0c txcg txc = t0
c for each tc 2 T ypesc
if Ext(tc) 6 \Ext(t0c) then 6 \c := 6 \c [ ftc 6 \ t0cg endif end end =xc := =t xc [ ftx =t xc txcg t return hT ypesxc; Extxc; 6 \xc; =t xc; xc; M appingxci The function NewType(t) generates a new type t0 such that Ext(t0) = Ext(t).
Assume that XML Schema is our source data modelling language, Postgres is our target modelling language and we use the CTH in De nition 2. We will also assume the following reduced type hierarchies for XML and Postgres: T Hxml = hfanyT ypexml; booleanxml; integerxml; negativeIntegerxmlg; fintegerxml ! f 231; : : : ; 231 1g; negativeIntegerxml ! f 231; : : : ; 0g; booleanxml ! f0; 1; true; f alsegg; fg; fbooleanxml anyT ypexml; integerxml anyT ypexml; negativeIntegerxml integerxmlg; fg; fgi T Hpg = hfanyT ypepg; booleanpg; int4pg; smallintpgg; fint4pg ! f 231; : : : ; 231 1g; smallintpg ! f 32768; : : : ; 32767g; booleanpg ! f`0',`1',`y',`n',`yes',`no',`t',`f',true,falsegg; fg; fbooleanpg anyT ypepg; int4pg anyT ypepg; smallintpg int4pgg; fbooleanpg 6 \ int4pgg; fgi Using De nition 3 we rst 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; fhf0,falseg; ffalsegi; hf1,trueg; ftruegigi) As a side e ect, T Hc has the following changes:
T ypesc := T ypesc [ fnegativeIntegercg
c:= c [fnegativeIntegerc integercg and the following inter model equalities are found in =t im: =im = fintegerxml = integerc; negativeIntegerxml =t negativeIntegerc; : : : g t t No additional disjoint relations are added. We can now add in the Postgres type hierarchy to expand the inter model hierarchy to T Him0 :
T Him0 = Merge(T Hpg; T Him; T Hc; hbooleanpg; booleanc;
fhf`0',`n',`no',`f',falseg; ffalsegi; hf`1',`y',`yes',`t',trueg; ftruegigi) No new changes to T Hc occur, but the following additional inter model equalities are =foiumn0d=infi=nttim4p0g: =t integerc; smallintpg =t shortc; : : : g
t Note that the two mapping tables in T Him0 , M appingim0 (booleanxml; booleanc) and M appingim10 (booleanpg; booleanc) allow us to map from a boolean in XML to a boolean Postgres. 3.2
The inter model type hierarchy described above can help us decide whether or not to add constraints. For example shortxml and smallintpg are both equivalent to shortc. We can say with con dence that any value from a construct of type shortxml can be stored in a construct of type smallintpg. If we later expanded 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 necessary 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 integerxml, equivalent to integerc and a target of a Postgres column of type smallintpg, equivalent to shortc. We know from De nition 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 de nition that Ext(integerc) Ext(shortc).
It may be necessary to nd a common ancestor in the merged inter model hierarchy to be able to move between certain source and target data types. 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 integerc. 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 target includes data types t and t0 such that t 6 \ t0 then the cast is illegal from De nition 1. 4
AutoMed [
AutoMed handles multiple data models de ning the constructs of a higher
level modelling language such as the relational model or XML in a lower level
hypergraph data model (HDM) [
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 fhhnnii j nn 2 N amesg 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 fhhne; s1; : : : ; snii j
ne 2 N ames[f g^s1 2 Schemes^: : :^sn 2 Schemesg 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 fc(s1; : : : ; sn) j c 2 F uncs ^ s1 2 Schemes ^ : : : ^ sn 2 Schemesg i.e. Cons is a set of boolean-valued functions (i.e. constraints) whose variables 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 ExtS;I where I is a speci c instance of the schema S. Thus ExtS;I (hhnii) returns the values associated with node hhnii.
As detailed in [
Using the simple HDM constructs de ned above, the extensional constructs
of higher level modelling languages can be de ned, based on the HDM. In [
In AutoMed, data exchange is done in two phases: rst the transformation pathways are set up, and second the data values are transformed using those pathways. This is roughly analogous to compile and run time for a conventional program. Setting up the pathways is a static operation whose complexity is linear 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
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. CREATE TABLE money ( cashIn smallint, complete boolean )
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 le 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 speci ed how to map the XML boolean values into Postgres. These transformations are not type safe. 5
To add types to the AutoMed system, we extend the De nition 4 by adding a type hierarchy T H = hT ypes; Ext; =t ; ; 6 \; M appingi from De nition 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 2 T ypes added, making the scheme of a node be hhn; tii The extent of a node can now be de ned as a subset of the values represented by the node's type so for x 2 hhn; tii ! x 2 Ext(t), i.e. hhn; tii 2 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 [
It may be necessary to change the data type of a node during a transformation. We present two new primitive operations to allow this. These changes are done on the inter model type hierarchy. De nition 5. changeNodeType(hhn; toldii; hhn; tnewii) Condition: Ext(told) \ Ext(tnew) 6= , returns a new schema which di ers only in that node hhnii has a di erent type. If told 6 tnew this operation will generate the following constraint used during query processing: 8hxi 2 hhn; toldii:x 2 Ext(tnew).
De nition 6. convertNodeType(hhn; toldii; hhn; tnewii; M appingim(told; tnew)) denes a bidirectional type conversion from a node of type told to type tnew. Each value in the extent of hhn; toldii is mapped to a value in the extent of tnew using the mapping tables and function from De nition 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
We can now de ne an AutoMed transformation pathway between the XML and SQL schemas from Section 4.2 using the operators de ned 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; booleanpgii will be created using the addNode operator.
The extents of the high level model types are the set of allowable values as
de ned by the data source. For example the extent of shortxml as de ned by the
XML Schema standard in [
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; negativeIntegerxmlii; hhcashxml; negativeIntegercii) 2 convertNodeType(hhcompletexml; booleanxmlii;
hhcompletepg; booleancii; Mappingim0(booleanxml; booleanc)) 3 addNode(hhcashInpg; negativeIntegercii; hhcashxml; negativeIntegercii) 4 addNode(hhcompletepg; booleancii; hhcompletexml; booleancii) 5 deleteNode(hhcompletexml; booleancii; hhcompletepg; booleancii) 6 deleteNode(hhcashxml; negativeIntegercii; hhcashInpg; negativeIntegercii) 7 convertNodeType(hhcompletepg; booleancii;
hhcompletepg; booleanpgii; Mappingim0(booleanpg; booleanc)) 8 changeNodeType(hhcashInpg; negativeIntegercii; hhcashInpg; smallintpgii)
Two nodes hhcashxml; negativeIntegerxmlii and hhcompletexml; booleanxmlii representing the XML Schema elements along with their data types are created by the wrapping process. Before adding nodes to represent the Postgres columns we change the type of the XML node to its equivalent in the CTH 1 because we have negativeIntegerxml =t negativeIntegerc. 2 uses the mapping de ned 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; booleancii using the convertNodeType operation. We again use the mapping de ned in Example 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; negativeIntegercii using changeNodeType. smallintpg =t shortc but shortc 6 negativeIntegerc so we need to nd a common ancestor. The common ancestor is integerc. Since we have to move down the hierarchy to get from integerc to shortc the constraint: 8x 2 hhcashxml; negativeIntegerxmlii:x 2 Ext(smallintpg) is generated from De nition 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 rst problem we had in the example in Section 4.2.
After transformations 1 { 8 we have the nodes hhcashInpg; smallintpgii and hhcompletepg; booleanpgii, 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 compiletime, based on the types of the nodes involved. This could not have been done without using the type information. We have also identi ed a potential type casting problem that will need to be checked during run-time. Without the explicit identi cation 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
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 di erent models [
Some methods ignore the problem [
A number of systems provide support for data types. TSIMMIS [
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 de ned between disjoint types. A formal de nition 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 di erent 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 values as single characters `t' and `f' of type char(1) while another database may use a eld of type boolean. We also hope to increase the e ciency of the method by de ning direct transformation rules between certain well-known data models, bypassing the need to transform each data type into its HDM equivalent rst.