This paper proposes a framework for transforming and integrating heterogeneous XML data sources, making use of known correspondences from them to ontologies expressed in the form of RDFS schemas. The paper ¯rst illustrates how correspondences to a single ontology can be exploited. The approach is then extended to the case where correspondences may refer to multiple ontologies, themselves interconnected via schema transformation rules. The contribution of this research is an XML-speci¯c approach to the automatic transformation and integration of XML data, making use of RDFS ontologies as a `semantic bridge'.
This paper proposes a framework for the automatic transformation and integration of heterogeneous XML data sources by exploiting known correspondences between them to ontologies expressed as RDFS schemas. Our algorithms generate schema transformation rules implemented in the AutoMed heterogeneous data integration system (http://www.doc.ic.ac.uk/automed/). These rules can be used to transform an XML data source into a target format, or to integrate a set of heterogeneous XML data sources into a common format. The transformation/integration may be virtual or materialised.
There are several advantages of our approach, compared with say constructing pairwise mappings between the XML data sources, or between each data source and some known global XML format: known semantic correspondences between data sources and domain and other ontologies can be utilised for transforming or integrating the data sources; the correspondences from the data sources to the ontology do not need to perform a complete mapping of the data sources; and changes in a data source, or addition or removal of a data source, do not a®ect the other sets of correspondences.
Paper outline: Section 2 compares our approach with related work. Section 3 gives an overview of AutoMed to the level of detail necessary for the purposes of this paper. Section 4 presents the process of transforming and integrating XML data sources which are linked to the same ontology, while Section 5 extends this to the more general case of data sources being linked to di®erent ontologies. Section 6 gives our concluding remarks and plans for future work.
The work in [
In contrast to all of these approaches, we use RDFS schemas merely as a `semantic bridge' for transforming/integrating XML data, and the target/global schema is in all cases an XML schema.
Other approaches to transforming or integrating XML data which do not
make use of RDF/S or OWL include [16, 18{20, 23]. Our own earlier work in
[
AutoMed is a heterogeneous data transformation and integration system which o®ers the capability to handle virtual, materialised and hybrid data integration across multiple data models. It supports a low-level hypergraph-based data model (HDM) and provides facilities for specifying higher-level modelling languages in terms of this HDM. An HDM schema consists of a set of nodes, edges and constraints, and each modelling construct of a higher-level modelling language is speci¯ed as some combination of HDM nodes, edges and constraints. For any modelling language M speci¯ed in this way (via the API of AutoMed's Model De¯nitions Repository) AutoMed provides a set of primitive schema transformations that can be applied to schema constructs expressed in M. In particular, for every construct of M there is an add and a delete primitive transformation which add to/delete from a schema an instance of that construct. For those constructs of M which have textual names, there is also a rename primitive transformation.
Instances of modelling constructs within a particular schema are identi¯ed by means of their scheme enclosed within double chevrons hh: : :ii. AutoMed schemas can be incrementally transformed by applying to them a sequence of primitive transformations, each adding, deleting or renaming just one schema construct (thus, in general, AutoMed schemas may contain constructs of more than one modelling language). A sequence of primitive transformations from one schema S1 to another schema S2 is termed a pathway from S1 to S2 and denoted by S1 ! S2. All source, intermediate, and integrated schemas, and the pathways between them, are stored in AutoMed's Schemas & Transformations Repository.
Each add and delete transformation is accompanied by a query specifying the extent of the added or deleted construct in terms of the rest of the constructs in the schema. This query is expressed in a functional query language, IQL, and we will see some examples of IQL queries in Section 4. Also available are extend and contract primitive transformations which behave in the same way as add and delete except that they state that the extent of the new/removed construct cannot be precisely derived from the rest of the constructs. Each extend and contract transformation takes a pair of queries that specify a lower and an upper bound on the extent of the construct. These bounds may be Void or Any, which respectively indicate no known information about the lower or upper bound of the extent of the new construct.
The queries supplied with primitive transformations can be used to translate
queries or data along a transformation pathway S1 ! S2 by means of query
unfolding: for translating a query on S1 to a query on S2 the delete, contract
and rename steps are used, while for translating data from S1 to data on S2 the
add, extend and rename steps are used | we refer the reader to [
The queries supplied with primitive transformations also provide the
necessary information for these transformations to be automatically reversible, in that
each add/extend transformation is reversed by a delete/contract
transformation with the same arguments, while each rename is reversed by a rename with
the two arguments swapped. As discussed in [
The standard schema de¯nition languages for XML are DTD [
We have therefore de¯ned a simple modelling language called XML DataSource Schema (XMLDSS) which summarises the structure of an XML document. XMLDSS schemas consist of four kinds of constructs: Element: Elements, e, are identi¯ed by a scheme hheii and are represented by nodes in the HDM.
Attribute: Attributes, a, belonging to elements, e, are identi¯ed by a scheme hhe; aii. They are represented by a node in the HDM, representing the attribute; an edge between this node and the node representing the element e; and a cardinality constraint stating that an instance of e can have at most one instance of a associated with it, and that an instance of a can be associated with one or more instances of e.
NestList: NestLists are parent-child relationships between two elements ep and ec and are identi¯ed by a scheme hhep; ec; iii, where i is the position of ec within the list of children of ep. In the HDM, they are represented by an edge between the nodes representing ep and ec; and a cardinality constraint that states that each instance of ep is associated with zero or more instances of ec, and each instance of ec is associated with precisely one instance of ep.1 PCData: In any XMLDSS schema there is one construct with scheme hhPCDataii, representing all the instances of PCData within an XML document.
In an XML document there may be elements with the same name occurring at di®erent positions in the tree. In XMLDSS schemas we therefore use an identi¯er of the form elementN ame$count for each element in the schema, where count is a counter incremented every time the same elementN ame is encountered in a depth-¯rst traversal of the schema. If the su±x $count is omitted from an element name, then the su±x $1 is assumed. For the XML documents themselves, our XML wrapper generates a unique identi¯er of the form elementN ame$count&instanceCount for each element where instanceCount is a counter identifying each instance of elementN ame$count in the document.
The XMLDSS schema, S, of an XML document, D, is derived by our XML
wrapper by means of a depth-¯rst traversal of D and is equivalent to the tree
resulting as an intermediate step in the creation of a minimal dataguide [
To illustrate XMLDSS schemas, consider the following XML document: 1 Here, the fact that IQL is inherently list-based means that the ordering of children instances of ec under parent instances of ep is preserved within the extent of the NestList hhep; ec; iii. <university> <school name="School of Law"> <academic> <name>Dr. G. Grigoriadis</name> <office>123</office></academic> <academic> <name>Prof. A. Karakassis</name> <office>111</office></academic> </school> <school name="School of Medicine"> <academic> <name>Dr. A. Papas</name> <office>321</office></academic> </school> </university> The XMLDSS schema extracted from this document is S1 in Figure 1. Note that a new root element r is generated for each XMLDSS schema, populated by a unique instance r&1 This is useful in adopting a more uniform approach to schema restructuring and schema integration by not having to consider whether schemas have the same or di®erent roots.
As mentioned earlier, after a modelling language has been speci¯ed in terms of the HDM, AutoMed automatically makes available a set of primitive transformations for transforming schemas de¯ned in that modelling language. Thus, for XMLDSS schemas there are transformations addElement (hheii,query), addAttribute (hhe; aii, query), addNestList ((hhep; ec; iii, query), and similar transformations for the extend, delete, contract and rename of Element, Attribute and NestList constructs. 4
In this section we consider ¯rst a scenario in which two XMLDSS schemas S1
and S2 are each semantically linked to an RDFS schema by means of a set of
correspondences. These correspondences may be de¯ned by a domain expert or
extracted by a process of schema matching from the XMLDSS schemas and/or
underlying XML data, e.g. using the techniques described in [
In Section 4.1 we show how these correspondences can be used to generate a transformation pathway from S1 to an intermediate schema IS1, and a pathway from S2 to an intermediate schema IS2. The schemas IS1 and IS2 are `conformed' in the sense that they use the same terms for the same RDFS concepts.
Due to the bidirectionality of BAV, from these two pathways S1 ! IS1 and S2 ! IS2 can be automatically derived the reverse pathways IS1 ! S1 and IS2 ! S2.
In Section 4.2 we show how a transformation pathway from IS1 ! IS2 can then be automatically generated. An overall transformation pathway from S1 to S2 can ¯nally be obtained by composing the three pathways S1 ! IS1, IS1 ! IS2 and IS2 ! S2.
This pathway can subsequently be used to automatically translate queries expressed on S2 to operate on S1, using AutoMed's XML Wrapper over source S1 to return the query results. Or the pathway can be used to automatically transform data that is structured according to S1 to be structured according to S2, and an XML document structured according to S2 can be output.
In Section 4.3 we discuss the automatic integration of a number of XML data sources described by XMLDSS schemas S1; : : : ; Sn, each semantically linked to a single RDFS schema by a set of correspondences. This process extends the approach of Sections 4.1 and 4.2 to integrate a set of schemas into a single global XMLDSS schema.
S2 name name
r 1 staffMember 1 office 1 college 2
PCData
belongs R1
belongs College name
IS2 S1
r
In our approach, a correspondence de¯nes an Element or Attribute of an
XMLDSS schema by means of an IQL path query over an RDFS schema2. In
particular, an Element e may map either to a Class c, or to a path ending
with a class-valued property of the form hhp; c1; c2ii, or to a path ending with
a literal-valued property of the form hhp; c; Literalii; additionally, the
correspondence may state that the instances of a class are constrained by membership in
some subclass. An Attribute may map either to a literal-valued property or to
a path ending with a literal-valued property. Our correspondences are similar to
path-path correspondences in [
For example, Tables 1 and 2 show the correspondences between the XMLDSS schemas S1 and S2 and the RDFS schema R1 (Figure 1). In Table 1 the 1st correspondence maps element hhuniversityii to class hhUniversityii. The 2nd correspondence states that the extent of element hhschoolii corresponds to the instances of class School derived from the join of properties hhbelongs, College, Universityii 2 An RDFS schema can be represented in the HDM using ¯ve kinds of constructs:
Class, Property, subClassOf, subPropertyOf, Literal. See [
The conformance of a pair of XMLDSS schemas S1 and S2 to equivalent XMLDSS schemas IS1 and IS2 that represent the same concepts in the same way is achieved by renaming the constructs of S1 and S2 using the sets of correspondences from these schemas to a common ontology.
For every correspondence i in the set of correspondences between an XMLDSS
schema S and an ontology R, a rename AutoMed transformation is generated,
as follows:
1. If i concerns an Element e:
3 The IQL query de¯ning this correspondence may be read as \return all values s such
that the pair of values fc; ug is in the extent of construct hhbelongs; College; Universityii
and the pair of values fs; cg is in the extent of construct hhbelongs; School; Collegeii".
IQL is a comprehensions-based language and we refer the reader to [
Note that not all the constructs of S1 and S2 need be mapped by correspondences to the ontology. Such constructs are not a®ected and are treated as-is by the subsequent schema restructuring phase.
Figure 1 shows the schemas IS1 and IS2 produced by the application of the renamings to S1 and S2 arising from the sets of correspondences in Tables 1 and 2. 4.2
In order to next transform schema IS1 to have the same structure as schema
IS2, we have developed a schema restructuring algorithm that, given a source
XMLDSS schema S and a target XMLDSS schema T , automatically transforms
S to the structure of T , given that S and T have been previously conformed.
This algorithm is able to use information that identi¯es an element/attribute
in S to be equivalent to, a superclass of, or a subclass of an element/attribute
in T . This information may be produced by, for example, a schema matching
tool or, in our context here, via correspondences to an RDFS ontology. We note
that this algorithm is an extension of our earlier schema restructuring algorithm
described in [
The AutoMed transformations generated by the schema restructuring algorithm for transforming schema IS1 to schema IS2 are illustrated in Table 3. In the growing phase, the ¯rst three transformations concern the element hhSta®ii of IS2. This element is inserted in IS1 using Element hhAcademicSta®ii, which corresponds to a class that is a subclass of the class hhSta®ii corresponds to in After growing phase
1 University
1 University.belongs.College.
belongs.School
1 University.belongs.College.belongs.
School.belongs. AcademicStaff University.belo1ngs. Un2iversity.belongs.
College.belongs. College.belongs.
School.belongs. School.belongs.
AcademicStaff. AcademicStaff.
name office r
1
University.belongs.
College.belongs.School.
belongs.Staff. name University.belongs.
College.belongs.
School.name
University.belongs.
College.name
University.belongs.
College.belongs.
School.belongs. Staff
1 University.belongs.College.belongs.
School.belongs.Staff. office
1 University.belongs. College 2 1 1
PCData the RDFS ontology; the ren IQL function is used here to rename the instances of Element hhAcademicSta®ii appropriately. After that, a NestList is inserted, linking hhSta®ii to its parent, which is the root r, using the path from r to AcademicStaff. hhSta®ii in T is not linked to the PCData construct, and therefore its attribute is handled next. The addAttribute transformation performs an element-to-attribute transformation by inserting Attribute hhSta®; nameii using the extents of hhAcademicSta®; nameii and hhname; PCDataii. The following three transformations insert Element hhSta®:o±ceii along with its incoming and outgoing NestList constructs in a similar manner. Then the last two transformations insert Element hhCollegeii along with its Attribute and its incoming NestList. Since there is no information relevant to the extents of these constructs in S, extend transformations are used, with Void as the lower-bound query. Note however that the upper-bound query generates a synthetic extent for both the hhCollegeii Element and its incoming NestList (for the latter, the IQL function generateNestLists is used4); this is to make sure that if any following transformations attach other constructs to hhCollegeii, their extent is not lost (assuming that these constructs are not themselves inserted with extend transformations and the constants Void and Any as the lower-bound and upperbound queries). At the end of the growing phase, the transformations applied to schema IS1 result in the intermediate schema shown in Figure 2. 4 Generally, function generateNestLists either accepts Element schemes hhaii and hhbii, with equal size of extents, and generates the extent of NestList construct hha; bii; or, it accepts Element schemes hhaii and hhbii, where the extent of hhaii is a single instance, and generates the extent of NestList construct hha; bii.
The shrinking phase operates similarly. The transformations removing hhAcademicSta®,AcademicSta®.nameii, hhAcademicSta®, PCDataii and hhAcademicSta®.nameii specify the inverse of the element-to-attribute transformation of the growing phase. To support attribute-to-element transformations, the IQL function skolemiseEdge is used; it takes as input a NestList hhep; ecii, and an Element hheii, which have the same extent size, and for each pair of instances e of hheii and fep; ecg of hhep; ecii generates a tuple fep; e; ecg.
The result of applying the transformations of Table 3 to schema IS1 is IS2
illustrated in Figure 1. There now exists a transformation pathway S1 ! IS1 !
IS2 ! S2, which can be used to query S2 by obtaining data from the data
source corresponding to schema S1. For example, if this is the XML document
of Section 3.1, the IQL query
returns the following result:
[f`Dr: G: Grigoriadis';`123'g; f`P rof: A: Karakassis';`111'g; f`Dr: A: P apas';`321'g]
We could also use the pathway S1 ! IS1 ! IS2 ! S2 to materialise S2 using
the data from the data source corresponding to S1 | see [
The separation of the growing phase from the shrinking phase ensures the completeness of the restructuring algorithm: the growing phase considers in turn each node in the target schema T and generates if necessary a query de¯ning this node in terms of the source schema S; conversely, the shrinking phase considers in turn each node of S and generates if necessary a query de¯ning this node in terms of T; inserting new target schema constructs before removing any redundant source schema constructs ensures that the constructs needed to de¯ne the extent of any construct are always present in the current schema. Consider now the integration of a set of XMLDSS schemas S1; : : : ; Sn all conforming to some ontology R into a global XMLDSS schema. The renaming algorithm of Section 4.1 can ¯rst be used to produce intermediate XMLDSS schemas IS1; : : : ; ISn. The initial global schema, GS1, is IS1. IS2 is then integrated with GS1 producing GS2. The integration of ISi with GSi¡1 to produce GSi proceeds until i = n. This integration consists of ¯rst an expansion of GSi¡1 with the constructs from ISi that it is missing (again via a growing and a shrinking phase) and then a restructuring, using the algorithm of Section 4.2, of ISi with the resulting schema GSi. In our framework, XML data sources are accessed using an XMLDSS wrapper. This has SAX and DOM versions for XML ¯les, supporting a subset of XPath. There is also a wrapper over the eXist XML repository which translates IQL queries representing (possibly nested) select-project-join-union queries into (possibly nested) XQuery FLWR expressions.
The XML wrapper can be used in three di®erent settings: (i) When a source XMLDSS schema S1 has been transformed into a target XMLDSS schema S2, the resulting pathway S1 ! S2 can be used to translate an IQL query expressed on S2 to an IQL query on S1, and the XML wrapper of the XML data source corresponding to S1 can be used to retrieve the necessary data for answering the query. (ii) In the integration of multiple data sources with schemas S1; : : : ; Sn under a virtual global schema GS, AutoMed's Global Query Processor can process an IQL query expressed on GS in cooperation with the XML wrappers for the data sources corresponding to the Si. (iii) In a materialised data transformation or data integration setting, where the XML wrapper(s) of the data source(s) retrieve the data and the XML wrapper of the target schema materialises the data into the target schema format. 5
We now discuss how our approach can also handle XMLDSS schemas that are linked to di®erent ontologies. These may be connected either directly via an AutoMed transformation pathway, or via another ontology (e.g. an `upper' ontology) to which both ontologies are connected by an AutoMed pathway.
Consider in particular two XMLDSS schemas S1 and S2 that are semantically linked by two sets of correspondences C1 and C2 to two ontologies R1 and R2. Suppose that there is an articulation between R1 and R2, in the form of an AutoMed pathway between them. This may be a direct pathway R1 ! R2. Alternatively, there may be two pathways R1 ! RGeneric and R2 ! RGeneric linking R1 and R2 to a more general ontology RGeneric, from which we can derive a pathway R1 ! RGeneric ! R2 (due to the reversibility of pathways). In both cases, the pathway R1 ! R2 can be used to transform the correspondences C1 expressed w.r.t. R1 to a set of correspondences C10 expressed on R2. This is using the query translation algorithm mentioned in Section 3 which performs query unfolding using the delete, contract and rename steps in R1 ! R2.
The result is two XMLDSS schemas S1 and S2 that are semantically linked by two sets of correspondences C10 and C2 to the same ontology R2. Our approach described for a single ontology in Section 4 can now be applied. There is a proviso here that the new correspondences C10 must conform syntactically to the correspondences accepted as input by the schema conformance process of Section 4.1 i.e. their syntax is as described in the ¯rst paragraph of Section 4.1. Determining necessary conditions for this to hold, and extending our approach to handle a more expressive set of correspondences, are areas of future work. 6
This paper has discussed the automatic transformation and integration of XML data sources, making use of known correspondences between them and one or more ontologies expressed as RDFS schemas. The novelty of our approach lies in the use of XML-speci¯c graph restructuring techniques in combination with correspondences from XML schemas to the same or di®erent ontologies. The approach promotes the reuse of correspondences to ontologies and mappings between ontologies. It is applicable on any XML data source, be it an XML document or an XML database. The data source does not need to have an accompanying DTD or XML Schema, although if this is available it is straightforward to translate such a schema in our XMLDSS schema type.
The schema conformance algorithm handles 1-1 mappings between XMLDSS and RDFS constructs, enriched with containment relationships through the use of subclass/superclass and subproperty/superproperty RDFS constraints. This semantic reconciliation of the data source schemas is followed by their structural reconciliation by the schema restructuring algorithm, which handles 1-1 mappings between XMLDSS schemas, utilising the constraints de¯ned in the correspondences. Extending our approach to be capable of utilising 1:n, n:1 and more complex mappings, is a matter of ongoing work. To this end, and at the same time aiming to maintain the current separation of semantic and structural schema reconciliation, we are currently extending the schema conformance algorithm.