Correspondence and translation for heterogeneous data.
Data integration often requires a clean abstraction of the different formats in which data are stored, and means for specifying the correspondences/relationships between data in different worlds and for translating data from one world to another. For that, we introduce in this paper a middleware data model that serves as a basis for the integration task, and a declarative rules language for specifying the integration. We show that using the language, correspondences between data elements can be computed in polynomial time in many cases, and may require exponential time only when insensitivity to order or duplicates are considered. Furthermore, we show that in most practical cases the correspondence rules can be automatically turned into translation rules to map data from one representation to another. Thus, a complete integration task (derivation of correspondences, transformation of data from one world to the other, incremental integration of a new bulk of data, etc.) can be specified using a single set of declarative rules.
Introduction
A primary motivation for new database technology is to provide support for the broad spectrum
of multimedia data available notably through the network. These data are stored under different
formats: SQL or ODMG (in databases), SGML or LaTex (documents), DX formats (scientific data),
Step (CAD/CAM data), etc. Their integration is a very active field of research and development
(see for instance, for a very small sample, [10, 6, 7, 9, 8, 12, 19, 20]). In this paper, we provide a
formal foundation to facilitate the integration of such heterogeneous data and the maintenance of
heterogeneous replicated data.
A sound solution for a data integration task requires a clean abstraction of the different formats
in which data are stored, and means for specifying the correspondences/relationships between data
in different worlds and for translating data from one world to another. For that we introduce a
middleware data model that serves as a basis for the integration task, and declarative rules for
specifying the integration.
The choice of the middleware data model is clearly essential. One common trend in data integration
over heterogeneous models has always been to use an integrating model that encompasses the
source models. We take an opposite approach here, i.e., our model is minimalist. The data structure
we use consists of ordered labeled trees. We claim that this simple model is general enough to capture
the essence of formats we are interested in. Even though a mapping from a richer data model to
this model may loose some of the original semantics, the data itself is preserved and the integration
with other data models is facilitated. Our model is similar to the one used in [7] and to the OEM
model for unstructured data (see, e.g., [21, 20]). This is not surprising since the data formats that
motivated these works are part of the formats that our framework intends to support. A difference
with the OEM model is that we view the children of each vertex as ordered. This is crucial to
describe lists, an essential component of DX formats. Also, [13] introduces BNF generated trees to
unify hierarchical data models. However, due to the fixed number of sons of a rule, collections are
represented by left or right deep trees not suitable for the casual users.
A main contribution of the paper is in the declarative specification of correspondences between
data in different worlds. For this we use datalog-style rules, enriched with, as a novel feature, merge
and cons term constructors. The semantics of the rules takes into consideration the fact that some
internal nodes represent collections with specific properties (e.g., sets are insensitive to order and
duplicates). We show that correspondences between data elements can be computed in polynomial
time in many cases, and may require exponential time only when insensitivity to order or duplicates
are considered.
Deriving correspondences within existing data is only one issue in a heterogeneous context. One
would also want to translate data from one representation to another. Interestingly, we show that
y This author's permanent position is INRIA-Rocquencourt, France. His work was supported by the Air
Force Wright Laboratory Aeronautical Systems Center under ARPA Contract F33615-93-1-1339, and by
the Air Force Rome Laboratories under ARPA Contract F30602-95-C-0119.
This work was partially supported by EC Projects GoodStep and Opal and by the Israeli Ministry of
Science
in most practical cases, translation rules can be automatically be derived from the correspondence
rules. Thus, a complete integration task (derivation of correspondences, transformation of data from
one world to the other, incremental integration of a new bulk of data, etc.) can be specified using a
single declarative set of rules. This is an important result. It saves in writing different specifications
for each sub-component of the integration task, and also helps in avoiding inconsistent specifications.
It should be noted that the language we use to define correspondence rules is very simple. Similar
correspondences could be easily derived using more powerful languages previously proposed (e.g.,
LDL [5] or IQL [4]). But in these languages it would be much more difficult (sometimes impossible)
to derive translation rules from given correspondence rules. Nevertheless, our language is expressive
enough to describe many desired correspondences/translations, and in particular can express all the
powerful document-OODB mappings supported by the structuring schemas mechanism of [2, 3].
As will be seen, correspondence rules have a very simple and intuitive graphical representation.
Indeed, the present work serves as the basis for a system, currently being implemented, where a
specification of integration of heterogeneous data proceeds in two phases. In a first phase, data is
abstracted to yield a tree-like representation that is hiding details unnecessary to the restructuring
(e.g., tags or parsing information). In a second phase, available data is displayed in a graphical
window and starting from that representation, the user can specify correspondences or derive data.
The paper is organized as follows. Section 2 introduces a core data model and Section 3 a core
language for specifying correspondences. In Section 4, we extend the framework to better deal with
collections. Section 5 deals with the translation problem. The last section is a conclusion. More
examples and figures are given in two appendixes.
2 The Data Model
Our goal is to provide a data model that allows declarative specifications of the correspondence
between data stored in different worlds (DX, ODMG, SGML, etc. We first introduce the model,
then the concept of correspondence. To illustrate things we use below an example. A simple instance
of an SGML document is given in Figure 1. A tree representation of the document in our middleware
model, together with correspondences between this tree and a forest representation of a reference in
a bibliographical OODB is given in Figure 2.
2.1 Data Forest
We assume the existence of some infinite sets: (i) name of names; (ii) vertex of vertexes; (iii) dom
of data values. A data forest is a forest of ordered labeled trees. An ordered labeled tree is a tree with
a labeling of vertexes and for each vertex, an ordering of its children. The internal vertexes of the
trees have labels from name whereas the leaves have labels from name [ dom [ vertex. The only
constraint is that if a vertex occurs as a leaf label, it should also occur as a vertex in the forest.
Observe that this is a rather conventional tree structure. This is a data model in the spirit of complex
value model [17, 1, 11] and many others, it is particularly influenced by models for unstructured
data [21, 20] and the tree model of [7]. A particularity is the ordering of vertexes that is important
to model data formats essentially described by files obeying a certain grammar (e.g., SGML).
data forest F is a triple (E; G;L), where (E; G) is a finite ordered forest (the
ordering is implicit); E is the set of vertexes; G the set of edges; L (the labeling function) maps some
leaves in E to E [ dom; and all other vertexes to name.
For each vertex v in E, the maximal subtree of root v is called the object v. The set of vertexes
E of a forest F is denoted vertex(F ) and the set of data values appearing in F is denoted dom(F ).
Remark. Observe that by definition, we allow a leaf to be mapped to a name. For all purposes, we
may think of such leaves as internal vertexes without children. This will turn useful to represent for
instance the empty set or the empty list. In the following, we refer by the word leaf only to vertexes
v such that L(v) is a vertex or is in dom.
We illustrate this notion as well as syntactic representations we use in an example. Consider the
graphical representation of the forest describing the OODB, shown in the lower part of Figure 2. A
tabular representation of part of the same forest is given in Figure 3. Finally, below is the equivalent
textual representation:
reference f &21 key f &211 "ACM96" f g g;
authors f &231 &3 f
abstract f &241":::" f g g g
To get a morecompact representation, we omit brackets when a vertex has a single or no children, and
omit vertex identifiers when they are irrelevant for the discussion. For example the above reference
tree may be represented by
reference f key "ACM96";
&22 title "Correspondence:::";
authorsf &3; &4; &5
abstract ":::" g
Let us now see how various common data sources can be mapped into our middleware model.
We consider here three different types of mappings. The first concerns relational databases, but
also all simple table formats. The second is used for object-oriented databases, but a similar one
will fit most graph formats. Finally, the last will fit any format having a BNF (or similar) grammar
description. Note that the three mappings are invertible and can easily be implemented.
Relations can be represented by a tree whose root label is the relation name and which has as
many children as rows in the relation. At depth 2, nodes represent rows and are labeled by the
label "tuple". At depth 3, 4 and 5, nodes are labeled respectively by attribute names, types and
values.
An object oriented database is usually a cyclic graph. However, using object identifier one may
easily represents a cyclic graph as a tree [4].
We pick one possible representation but many other ones can be proposed. A class extent is
represented by a tree whose root node is labeled with the class name. This node has as many
children as there are objects in the extent, each of which is labeled by the object type. We
assume that objects appear in the class extent of their most specific class. We now describe the
representation of subtrees according to types.
- A node labeled by an atomic type has a unique child whose label is the appropriate atomic
value.
- A node labeled "tuple" has one child for each attribute. The children are labeled with the
attribute names and each has one child labeled by the appropriate type and having the
relevant structure.
- A node labeled "set" (or "list", "bag", .) has as many children as elements in the collection,
one for each collection member. (For lists the order of elements is preserved). Each child is
labeled by the appropriate type, and has the relevant structure.
- A node labeled by an object type has a unique child labeled by the identifier of the node
that representing the object in the tree of the class extent to which it belongs.
A document can be described by a simplified representation of its parsing tree. The labels of the
internal nodes (resp. leaves) represent the grammar non-terminal symbols (resp. tokens).
SGML and HTML, among other formats, allow references to internal and external data. Parsers
do not interpret these references. They usually consider them as strings. In our context, these
references should be interpreted when possible. As for object databases, the reference can be
replaced by the identifier of the node containing the referred data.
Note that the only identification of data in the middleware model is given by the nodes identifiers.
This means that it is the responsability of the data sources to keep relationships between the exported
data and the node identifiers. This relationship is not always needed (e.g., for a translation process),
and may be of a fine or large grain according to the application needs and the data source capacities.
The identification of data in the data sources can take various forms. It can be the key of a row
or some internal address in relational databases. For object databases, it can be the internal oid (for
objects), a query leading to the object/value, or similar ideas as in the relational case. For files it
can be an offset in the file, node in the parse tree, etc.
2.2 Correspondence
We are concerned with establishing/maintaining correspondences between objects. Some objects
may come from one data source with particular forest F 1 , and others from another forest, say F 2 .
To simplify, we consider here that we have a single forest (that can be viewed as the union of the
two forests) and look for correspondences within the forest. (If we feel it is essential to distinguish
between the sources, we may assume that the nodes of each tree from a particular data source have
the name of that source, e.g., F 1 as part of the label.) We describe correspondences between
objects using predicates.
Example 1. Consider the following forest with the SGML and OODB trees of Figure 2.
article f:::; &12 title "Correspondence:::"; &13 author "S:Abiteboul";
&14 author "S:Cluet"; &15 author "T:M ilo"; &16 abstract ":::"; ::: g
reference f key "ACM96"; &22 title "Correspondence:::"; authorsf &3; &4; &5
abstract ":::" g
We may want to have the following correspondences:
Note that there is an essential difference between the two predicates above: is relates objects that
represent the same real world entity, whereas concat is a standard concatenation predicate/function
that is defined externally. The is-relationship is represented on Figure 2.
Definition2. Let R be a relational schema. An R-correspondence is a pair (F; I) where F is a data
forest and I a relational instance over R with values in vertex(F ) [ dom(F ).
For instance, consider Example 1. Let R consists of binary relation is and a ternary one concat.
For the forest F and correspondences I as in the example, (F; I) is an R-correspondence. Note that
we do not restrict our attention to 1-1 correspondences. The correspondence predicates may have
arbitrary arity, and also, because of data duplication, some n-m correspondences may be introduced.
3 The Core Language
In this section, we develop the core language. This is in the style of rule-based languages for objects,
e.g., IQL [4], LDL [5], F-logic [15] and more precisely, of MedMaker [19]. The language we present in
this section is tailored to correspondence derivation, and thus in some sense more limited. However,
we will consider in a next section a powerful new feature.
We assume the existence of two infinite sorts: a sort data-var of data variables, and vertex-var
of vertex variables. Data variables start with capitals (to distinguish them from names); and vertex
variables start with the character & followed by a capital letter.
Rules are built from correspondence literals and tree terms. Correspondence literals have the form
are data/vertex variables/constants.
Tree terms are of the form &X L, &X L t 1 , and &X L where &X is a vertex vari-
able/constant, L is a label and t are tree terms. The &X and Ls can also be omitted. A
rule is obtained by distinguishing some correspondence literals and tree terms to be in the body,
and some to be in the head. Semantics of rules is given in the sequel. As an example, consider the
following rule that we name r so . Note again the distinction between concat which is a predicate on
data values and can be thought of as given by extension or computed externally, and the derived is
correspondence predicate.
reference f &X 14 ;
authorsf &Y
&X 19 abstract X 11 g
A rule consists of a body and a head. When a rule has only literals in its head, it is said to be a
correspondence rule. We assume that all variables in the head of a correspondence rule also occur in
the body. We now define the semantics of correspondence rules.
Given an instance (F; I) and some correspondence rule r, a valuation - over (F; I) is
a mapping over variables in r such that
1. - maps data variables to dom(F ) and object variables to vertex(F ).
2. For each term H in the body of r
(a) H is a correspondence literal and -(H) is true in I ; or
(b) H is a tree term and -(H) is an object 5 of F .
We say that a correspondence C(&U;&V ) is derived from (F; I) using r if C(&U;&V
some term H in the head of r, and some valuation - over (F; I).
Let P be a set of rules. Let I derived from (F; I) using some r in Pg. Then,
is denoted TP (F; I). If P is recursive, we may be able to apply TP to TP (F; I) to derive new
correspondences. The limit T !
exists, of the application of TP is denoted, P(F; I).
Theorem4. For each (possibly recursive) finite set P of correspondence-rules and each data forest
well-defined (in particular, the sequence of applications of TP converges in a finite
number of stages). Furthermore, P(F; I) can be computed in ptime.
We represent data forests using a relational database. A relation succ gives a portion of
the successor function over the integers. The number of facts that can be derived is polynomial.
Each step can be computed with a first-order formula, so it is in ptime. 2
The above rule r so is an example of a non-recursive correspondence rule. (We assume that the extension
of concat is given in I.) To see an example of a recursive rule, we consider the correspondence
between "left-deep" and "right-deep" trees. For instance, we would like to derive a correspondence
between the right and left deep trees shown in Figure 4. This is achieved using the program r2l
which consists of the following rules:
5 Recall that an object of a forest F is a maximal subtree of F rooted in some vertex of F .
&U rightfX; &Y g
Suppose that we start with I = ;, and the forest F shown on Figure 4. Then we derive the correspondences
The computation is:
r2l
r2l
r2l
r2l
r2l
r2l
This kind of deep trees is frequent in data exchange formats and it is important to be able to handle
them. However, what we have seen above is not quite powerful enough. It will have to be extended
with particular operations on trees and to handle data collections. This is described next.
4 Dealing with Collections
When data sources are mapped into the middleware model, some forest vertexes may represent data
collections. Observe that, in the above rules, the tree describes vertexes with a bounded number of
children, (where the number depends on the term structure). Data collections may have an arbitrary
number of members, and thus we need to extend our language to deal with vertexes having arbitrary
number of children. Also observe that ordered trees are perfect to represent ordered data collections
such as lists or arrays. However, if we want to model database constructs such as sets or bags, we
have to consider properties such as insensitivity to order or duplicates. The rules that we developed
so far do not support this. In this section, we address these two issues by extending our framework
to incorporate (i) operators on trees and (ii) special collection properties.
4.1 Tree Constructors
We consider two binary operations on trees. The first, cons(T takes two objects as input. The
first one is interpreted as an element and the second as the collection of its children vertexes. The
operation adds the element to the collection. The second operator, merge, allows to merge two data
collections into one. (The cons operator can be defined using a merge with a singleton collection.)
For example
More formally, let T; T trees where the roots of T 0 and T 00 have the same label l and
n and S 00
respectively. Then
tree with root labeled by l and children T; S 0
n , in that order.
is a tree with root labeled by l and children S 0
m , in that order.
The cons and merge operators provide alternative representations for collections that are essential
to describe restructuring. The data trees in the forests we consider are all reduced in the sense that
they will not include cons or merge vertexes. But, when using the rules, we are allowed to consider
alternative representations of the forest trees. The vertexes/objects of the trees with cons and merge
are regarded as implicit. So, for instance if we have the data tree &1 mylistf&2; &3g, we can view it
as &1 cons(&2; &v) where the object &v is implicit and has the structure mylistf&3g. Indeed, we
will denote this object &v by mylist(&1; &3) to specify that it is an object with label mylist, that
it is a subcollection of &1, and that it has a single child &3. This motivates the following definition:
Given a forest F , a vertex &v in F with children label
l, the expression l(&v; called an implicit object of F for each subsequence 6
. The set of all implicit objects of F is denoted impl(F ).
6 A subsequence &v obtained by removing 0 or more elements from the head
and the tail of &v1 ; :::; &vn .
Observe that vertex(F ) can be viewed as a subset of impl(F ) if we identify the object
of the definition, with &v. Observe also that the cardinality of impl(F ) is polynomial
in the size of F .
We can now use cons and merge in rules. The following example uses cons to define a correspondence
between a list structured as a right-deep tree and a list structured as a tree of depth one
(Observe that in the example mylist is not a keyword but only a name with no particular semantics;
cons is a keyword with semantics, the cons operation on trees):
Of course, to use such rules, we have to extend the notion of valuation to allow terms containing
cons. The new valuation may now assign implicit objects to object variables.
The fixpoint T !
computed as before using the new definition of valuation. Observe that
may now contain correspondences involving vertexes in impl(F ) and not only F . Since
we are interested only in correspondences between vertexes in F , we ultimately ignore all other
correspondences. So, P(F; I) is the restriction of T !
to objects in F . For instance, consider
rule tl and
Then:
tl
tl
tl
tl
tl
tl
In the sequel, we call the problem of computing P(F; I), the matching problem.
Theorem6. The matching problem is in ptime even in the presence of cons and merge.
The number of facts that can be derived is polynomial and each step can be computed
with a first-order formula, so is polynomial. 2
4.2 Special Properties
Data models of interest include collections with specific properties: e.g., sets that are insensitive to
order or duplicates, bags that are insensitive to order. In our context this translates to properties
of vertexes with particular labels. We consider here two cases, namely insensitivity to order (called
bag property), and insensitivity to both order and duplicates (called set property). For instance, we
may decide that a particular label, say mybag (resp. myset) denotes a bag (resp. a set). Then, the
system should not distinguish between:
The fact that these should be the same implicit objects is fundamental. (Otherwise the same set
would potentially have an infinite number of representations and computing correspondences would
become undecidable.) In the context of set/bag properties, the definition of implicit objects becomes
a little bit more intricate.
Given a forest F , a vertex &v in F with children label
l, implicit objects of vertexes with bag/set properties are obtained as follows:
l has set property: l(&v; &v i 1
for each subset f&v i 1
g of f&v g.
l has bag property: l(&v; &v i 1
for each subbag ff&v i 1
gg of ff&v 1 ; :::; &v n gg.
The notion of valuation is extended in a straightforward manner to use the above implicit objects
and take into consideration tree equivalence due to insensitivity to order and duplicates, (details
omitted for lack of space). It is important to observe at this point that the number of implicit
objects is now exponential in the size of F .
The next example shows how cons, and the set property can be used to define a correspondence
between a list and a set containing one copy for each distinct list member:
label myset : set
mylist fg
&V myset fg
Observe the symmetry of the rules between set and list. The only distinction is in the specification
of label myset. Using essentially the same proof as in Theorem 6 and a reduction to 3-sat, one can
prove:
Theorem8. In the presence of cons, merge, and collections that are insensitive to order/duplicates,
the matching problem can be solved in exptime. Even with insensitivity to order and cons only, the
matching problem becomes np-hard.
Remark. The complexity is data complexity. This may seem a negative result (that should have
been expected because of the matching of commutative collections). But in practice, merging is
rarely achieved based on collections. It is most often key-based and, in some rare cases, based on
the matching of "small collections", e.g., sets of authors.
To conclude the discussion of correspondence rules, and demonstratethe usage of cons and merge,
let us consider the following example where a correspondence between articles and OO references
is defined. Observe that while the correspondence rule r so presented at the beginning of the paper
handles articles with exactly three authors, articles/references here deal with arbitrary number of
authors. They are required to have the same title and abstract and the same author list (i.e., the
authors appear in the same order). The definition uses an auxiliary predicate same list.
The first rule defines correspondence between authors. The second and third rules define an
auxiliary correspondence between sequences from both world. It is used in rule R 4 that defines
correspondence between articles and references. It also defines correspondence between titles and
abstracts from both worlds.
same list(&X 2 ; &X 5 )
same list(&X 4 ; &X 11 )
We illustrated the language using rather simple examples. Nevertheless, it is quite powerful and
can describe many desired correspondences, and in particular all the document-OODB mappings
supported by the structuring schemas mechanism of [2, 3] (Omitted).
5 Data Translation
Correspondence rules are used to derive relationships between vertexes. We next consider the problem
of translating data. We first state the general translation problem (that is undecidable). We then
introduce a decidable subcase that captures the practical applications we are interested in. This is
based on translation rules obtained by moving tree terms from the body of correspondence rules to
the head.
We start with a data forest and a set of correspondence rules. For a particular forest object &v
and a correspondence predicate C , we want to know if the forest can be extended in such a way that
&v is in correspondence to some vertex &v 0 . In some sense, &v 0 could be seen as the "translation"
of &v. This is what we call the data translation problem.
input: an R-correspondence (F; I), a set P of correspondence rules, a vertex &v of F , and a binary
predicate C.
output: an extension F 0 of F such that C(&v;&v 0 ) holds in P(F 0 ; I) for some &v 0 ; or no if no such
extension exists.
For example consider a forest F with the right deep tree &1 f1; f2; f3; fgggg. Assume we want to
translate it into a left deep tree format. Recall that the r2l correspondence rules define correspondences
between right deep trees and left deep trees. So, we can give the translation problem the
R-correspondence (F; I), the root vertex &1, and the correspondence predicate R2L. The output
will be a forest F 0 with some vertex &v 0 s.t. R2L(&1;&v 0 ) holds. The tree rooted at &v 0 is exactly
the left deep tree we are looking for.
Remark. In the general case: (i) we would like to translate an entire collection of objects; and (ii) the
correspondence may be a predicate of arbitrary arity. To simplify the presentation, we consider the
more restricted problem defined above. The same techniques work for the general case with minor
modifications.
It turns out that data translation is in general very difficult. (The proof is by reduction of the
acceptance problem of Turing machines.)
Proposition 5.1 The translation problem is undecidable, even in absence of cons, merge, and labels
with set/bag properties.
Although the problem is undecidable in general, we show next that translation is still possible in
many practical cases and can often be performed efficiently. To do this, we impose two restrictions:
1. The first restriction we impose is that we separate data into two categories, input vertexes
and output vertexes. Vertex variables and labels are similarly separated 7 . We assume that the
presence of an output object depends solely on the presence of some input object(s) and possibly
some correspondence conditions. It allows us to focus on essentially one kind of recursion: that
found in the source data structure.
2. The second restriction is more technical and based on a property called body restriction that
is defined in the sequel. It prevents pathological behavior and mostly prevent correspondences
that relate "inside" of tree terms.
These restrictions typically apply when considering data translation or integration, and in particular
we will see that all the examples above have the appropriate properties.
The basic idea is to use correspondence rules and transform them into translation rules by moving
data tree terms containing output variables from the body of rules to their head. For example,
consider the r2l correspondence rules. To translate a right deep tree into a left deep tree, we move
the terms of the left deep trees to the head of rules, and obtain the following translation rules.
(Variables with prime are used to stress the separation between the two worlds.)
Of course we need to extend the semantics of rules. The tree terms in the head, and in particular
those containing variables that do not appear in the body, are used to create new objects. (This
essentially will do the data translation). We use Skolem functions in the style of [9, 14, 16, 18]
to denote new object ids. There are some difficulties in doing so. Consider a valuation - of the
second rule above. One may be tempted to use the Skolem term r 0 (-(&U); -(X); -(&Y ); -(&Y 0
to denote the new object. But since &Y 0 is itself a created object, this may lead to a potentially
non-terminating loop of object creation. To avoid this we choose to create objects only as a function
of input objects and not of new output created objects. (Thus in the above case the created object
is denoted r 0 &U 0 (-(&U); -(X); -(&Y )).)
Now, the price for this is that (i) we may be excluding some object creation that could be of
interest; and (ii) this may result in inconsistencies (e.g., the same object with two distinct values).
We accept (i), although we will give a class of programs such that (i) never occurs. For (ii), we rely
on non determinism to choose one value to be assigned to one object. Note that we need some form
of nondeterminism for instance to construct a list representation from a set.
For lack of space we do not give here the refined semantics for rules, (it is given in the full paper,)
but only state that:
Proposition9. For each finite set P of translation-rules and each R-correspondence (F; I), each
of the possible sequences of application of TP converges in a finite number of stages. Furthermore,
for rules with no set/bag labels each sequence converges in ptime, and otherwise in exptime.
So far, a program computation can be viewed as purely syntactic. We are guaranteed to terminate,
but we don't know the semantic properties of the constructed new objects and derived correspondences

It turns out this evaluation of translation rules allows to solve the translation problem for a
large class of correspondence rules. (Clearly not all since the problem is unsolvable in general.) In
7 Note that vertexes can easily be distinguished using their label.
particular it covers all rules we presented in the previous section, and the translations specified by
the structuring schemas mechanisms of [3] (proof omitted). We next present conditions under which
the technique can be used.
correspondence rule r is said to be body restricted if in its body (1) all the variables
in correspondence literals are leaves of tree terms, and each such variable has at most one occurrence
in a correspondence literal, and (2) non-leaf variables have at most one occurrence (as non leafs) in
tree terms, and (3) the only variables that input and output tree terms share are leaf variables.
We are considering correspondences specified with input/output data forests.
Proposition 5.2 Consider an input/output context. Let P be a set of body restricted correspondence
rules where correspondence literals always relate input to output objects. Let (F; I) be an
R-correspondence where F is an input data forest, &v a vertex in F , and C a binary correspondence
predicate. Let P 0 be the translation rules obtained from P by moving all output tree terms to the head
of rules. Then,
- If the translation problem has a solution on input (F; I) P, &v, C that leaves the input forest
unchanged, then each possible computations of P 0 object
some computation of P 0 derives C(&v;&v 0 ) for some object &v 0 , then the forest F 0 computed
by this computation is a correct solution to the translation problem.
By Proposition 5.2, to solve the translation problem (with unmodified input) for body restricted
rules, we only need to compute nondeterministically one of the possible outputs of P , and test if
6 Conclusion
We presented a specification of the integration of heterogeneous data based on correspondence rules.
We showed how a unique specification can served many purposes (including two-way translation) assuming
some reasonable restrictions. We claim that the framework and restrictions are acceptable in
practice, and in particular one can show that all the document-OODB correspondences/translations
of [2, 3] are covered. We are currently working on further substantiating this by more experimentation

When applying the work presented here a number of issues arise such as the specification of
default values when some information is missing in the translation. A more complex one is the
introduction of some simple constraints in the model, e.g., keys.
Another important implementation issue is to choose between keeping one of the representations
virtual vs. materializing both. In particular, it is conceivable to apply in this larger setting the
optimization techniques developed in a OODB/SGML context for queries [2] and updates [3].

Acknowledgment

We thank Catriel Beeri for his comments on a first draft of the paper.



--R

On the power of languages for the manipulation of complex objects.
Querying and updating the file.
A database interface for files update.
Object identity as a query language primitive.
Sets and negation in a logic database language (LDL1).
A data transformation system for biological data sources.
Programming constructs for unstructured data
Towards heterogeneous multimedia information systems: The Garlic approach.
Using witness generators to support bi-directional update between objact- based databases
From structured documents to novel query facilities.
The story of O2
Amalgame: a tool for creating interoperating persistent
A grammar based approach towards unifying hierarchical data models.
ILOG: Declarative creation and manipulation of object-identifiers
F-logic: A higher-order language for reasoning about objects
Logical foundations of object-oriented and frame-based languages
The logical data model.
A logic for objects.
Medmaker: A mediation system based on declarative specifications.
Object exchange across heterogeneous information sources.
Querying semistructured heterogeneous information.
--TR
Sets and negation in a logic data base language (LDL1)
F-logic: a higher-order language for reasoning about objects, inheritance, and scheme
Object identity as a query language primitive
A grammar-based approach towards unifying hierarchical data models
ILOG: declarative creation and manipulation of object identifiers
The SGML handbook
The logical data model
From structured documents to novel query facilities
Logical foundations of object-oriented and frame-based languages
Using witness generators to support bi-directional update between object-based databases (extended abstract)
A database interface for file update
Foundations of Databases
The Story of O2
Object Exchange Across Heterogeneous Information Sources
Correspondence and Translation for Heterogeneous Data
Querying and Updating the File
A Data Transformation System for Biological Data Sources
Amalgame
time algorithm for isomorphism of planar graphs (Preliminary Report)

--CTR
Natalya F. Noy , Mark A. Musen, Promptdiff: a fixed-point algorithm for comparing ontology versions, Eighteenth national conference on Artificial intelligence, p.744-750, July 28-August 01, 2002, Edmonton, Alberta, Canada
Yannis Kalfoglou , Marco Schorlemmer, Ontology mapping: the state of the art, The Knowledge Engineering Review, v.18 n.1, p.1-31, January
Olga Brazhnik , John F. Jones, Anatomy of data integration, Journal of Biomedical Informatics, v.40 n.3, p.252-269, June, 2007
data integration;middleware model;translation;data correspondence