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.
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 warehouse 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 difficult 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 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 transformations in a data exchange environment by adding type information. -Provide a way of transforming data between schemas whose data types support 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 transformation of data types in a data exchange system. Finally some conclusions are drawn and some of our on-going work is described.
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 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:
-Figure 1 does not distinguish between types which are disjoint in their extent, such as positiveInteger (representing all positive integer values) and negativeInteger (representing all negative integer values), and those which overlap, such as int (representing −2 31 ..2 31 − 1) and unsignedInt (representing 0..2 32 − 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.. 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: 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 demonstrate how mapping rules between schemas in different modelling languages may be made type safe.
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.
A type hierarchy T H x is a tuple T ypes x , Ext x , t = x , ≺ x , ∩ x , M apping x where:
-A finite set of type names T ypes x . These will make up the nodes of the graph. -An Ext x function that returns a subset of the set of all possible data values anyT ype x of the hierarchy that is consistent with a type:
The type anyT ype x represents the set of data values that a particular language (or collection of languages) may handle, and has the property that Ext x (anyT ype x ) ⊆ C where C is the set of all data values that may be handled by the data exchange system. -An equality relation,
When all types t, t ∈ T ypes x that have t t = x t 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.
This implies there is no pathway from t to t in the graph and so we cannot cast between t and t . If t ∩ x t then any subtype of t will also be disjoint from t . -A set M apping x of mapping tables t a , t b , { s 1 a , s 1 b , . . . , s n a , s n b } , where t a , t b ∈ T ypes x , s 1 a , . . . , s n a are subsets of Ext(t a ) and are disjoint. Similarly s 1 b , . . . , s n b are subsets of Ext(t b ) and are disjoint. We overload M apping x to be used as a function with the following definition:
where First returns the first element of a set according to a sort order that is fixed for the system. We use M apping x (type a , type b ) to denote the specific mapping table that maps type a to type b .
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 H xml , can be derived from Figure 1
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.
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 gives a procedure for building such an inter model type hierarchy T H xc from a data model's type hierarchy T H x , and existing inter model type hierarchy T H im , and a (possibly extended) CTH T H c .
The function NewType(t) generates a new type t such that Ext(t ) = Ext(t).
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
The inter model type hierarchy described above can help us decide whether or not to add constraints. For example short xml and smallint pg are both equivalent to short c . We can say with confidence that any value from a construct of type short xml can be stored in a construct of type smallint pg . If we later expanded our system to include schemas from Microsoft SQL Server and discover that smallint ms also maps to short c 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 integer xml , equivalent to integer c and a target of a Postgres column of type smallint pg , equivalent to short c . We know from Definition 2 that short c ≺ integer c . To get from integer xml to smallint pg we need to go via integer c and then down the hierarchy to short c . The checking is necessary here because we know from the definition that Ext(integer c ) ⊃ Ext(short c ).
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.
In Example 4 we added negativeInteger c to the hierarchy. To transform from negativeInteger to short c 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 ype c , can be found the type transformation is invalid. As with the previous example, the step from integer c to short c 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 t such that t ∩ t then the cast is illegal from Definition 1.
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].
Given a set of N ames that we may use for modelling the real world, an HDM schema, S, is a triple N odes, Edges, Cons where:
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 Ext S,I where I is a specific instance of the schema S. Thus Ext S,I ( n ) returns the values associated with node n .
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],
DISWEB'06 higher level modelling language constructs were classified into (1) nodal constructs, which can exist independently, and map to nodes in the HDM, (2) linknodal 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) linking 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 constructs 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.
In AutoMed, data exchange is done in two phases: first 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.
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. 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.
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.
To add types to the AutoMed system, we extend the Definition 4 by adding a type hierarchy T H = T ypes, Ext, t =, ≺, ∩, M apping from Definition 1 to make a typed HDM schema be a tuple N odes, Edges, Constraints, T H . The scheme of each node will have an extra component, t ∈ T ypes added, making the scheme of a node be n, t The extent of a node can now be defined as a subset of the values represented by the node's type so for x ∈ n, t → x ∈ Ext(t), i.e. n, t ∈ 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 expanded 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( n, t , q) returns a new schema by adding a node n of type t to the schema, where getNodeType(q) t = t. The extent of the node is given by the value of the IQL (Intermediate Query Language) [14] query q.
-deleteNode( n, t , q) returns a new schema by deleting a node from the schema, where the value of the node may be recovered from q, and getNodeType(q
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.
Definition 5. changeNodeType( n, t old , n, t new ) Condition: Ext(t old ) ∩ Ext(t new ) = φ, returns a new schema which differs only in that node n has a different type. If t old ≺ t new this operation will generate the following constraint used during query processing: ∀ x ∈ n, t old .x ∈ Ext(t new ). Definition 6. convertNodeType( n, t old , n, t new , M apping im (t old , t new )) defines a bidirectional type conversion from a node of type t old to type t new . Each value in the extent of n, t old is mapped to a value in the extent of t new 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.
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 complete, boolean pg 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 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 complete pg , boolean c using the convertNodeType operation. We again use the mapping defined 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 cashIn pg , negativeInteger c using changeNodeType. smallint pg t =short c but short c ≺ negativeInteger c 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 integer c to short c the constraint: ∀x ∈ cash xml , negativeInteger xml .x ∈ Ext(smallint pg ) 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 cashIn pg , smallint pg and complete pg , boolean pg , 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 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.
A number of papers have shown how to transform schemas from one model to another, most commonly XML to relational [15][16][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 DISWEB'06 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 language 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.
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 values 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.