Information integration is the general problem that arises in applications that need to consolidate (in a virtual or materialized way) data coming from di erent sources [9, Ch.21]. In this paper, we consider a scenario for data integration, very common in practice, for which existing solutions are not e ective. We refer to those applications where there are many (dozens or hundreds or even more) sources, in the same domain, that have to contribute to one, single global (\target") system. A common case is that of \central" organizations that receive data from a large set of \local" companies or administrations; a speci c case is that of a national central bank that receives data from all the banks in the country. This scenario is often handled by imposing to all local sources an exchange format, so that data are transferred to the central institution in a standardized form. In some cases, this solution is just inapplicable, as companies might refuse the adoption of the standard unless forced by regulations. Moreover, exchange formats (especially for statistics and nance) are inherently exible, versatile and unstable, allowing a number of di erent source schemas. Finally, due to the complexity of exchange formats, their adoption is often partial or incorrect. In particular, a diverging interpretation of the exchange format can be even accepted in case the central institution realizes that the various sources have speci c features that, though not general, are nevertheless interesting and deserve to appear in the target.
An approach based on the theory of mappings [
We also have an observation that mitigates the di culties: in many cases the sources are indeed di erent from one another, but they do share similarities that can be exploited.
On the basis of the above requirements we propose a new approach, where
there is one source schema S0, used as a reference, and the other source schemas
can be seen as variations of S0. Then, we consider variations on the target
schema, induced by speci c features of the source schemas, including their data,
in order to support \schematic transformations" [
G
RepositoryOfBalances
Bank IoBName Amount 1005 Asset 8 1005 Liability 19 1006 Asset -42 1006 Liability 21
G0
RepositoryOfBalancesAlt
Bank Asset Liability 1005 8 19 1006 -42 21
For example, Figure 1 represents two desired global schemas, each of which is able to store summaries of balance sheets of banks. The relation RepositoriesOfBalances stores the Amount (that is, the di erence between credits and debits) aggregated by Bank and IoBName (item of balance name). RepositoriesOfBalancesAlt (\Alt" stands for \alternate") stores the same items for each bank with the di erence that Asset and Liabilities are attributes.
In the example, S1 is identical to S0 and reports the balance sheet as a single relation. In S2 the balance sheet is (horizontally) partitioned into two relations, with the same attributes as S0: tuples having Year preceding 2012 are stored in BalSheet2010-2011, the others in BalSheet2013. In S3, the balance is (vertically) decomposed into credits and debits, with a coarser level of granularity, as data are reported and grouped by Bank , disregarding the years.
In the rest of the paper we study the data integration scenario we have just sketched. In Section 2 we show how we handle a large number of heterogeneous but similar sources and in Section 3 we discuss how we cope with the issue of generating new features in target schemas on the basis of source schemas and data. Finally, in Section 4 we draw our conclusions and brie y discuss related work. S1
BalSheetTemplate
Year Bank IoBName IoBCred IoBDeb BalSheet
Year Bank IoBName IoBCred IoBDeb 2010 1005 Asset 35 27 2011 1005 Liability 29 10 2010 1006 Asset 41 30 2010 1006 Liability 31 30 2013 1006 Asset 0 53 2013 1006 Liability 33 13 BalSheet2010-2011 Year Bank IoBName IoBCred IoBDeb BalSheet2013 2010 1005 Asset 35 27 Year Bank IoBName IoBCred IoBDeb S2 2011 1005 Liability 29 10 2013 1006 Asset 0 53 2010 1006 Asset 41 30 2013 1006 Liability 33 13 2010 1006 Liability 31 30
S3
BalSheetCredit
Bank IoBName IoBCred 1005 Asset 35 1005 Liability 29 1006 Asset 41 1006 Liability 64
BalSheetDebit
Bank IoBName IoBDeb 1005 Asset 27 1005 Liability 10 1006 Asset 83 1006 Liability 43 Let us rst concentrate on cases in which the global schema is completely de ned beforehand (and so coinciding with the baseline global schema G0), while in Section 3, we give some insights about how we handle dynamic global schemas.
We recognize that each source schema Si can be considered as a variation
of S0. In this, we notice an analogy with the schema evolution problem [
Thus, we propose a new approach where each Si is described as an evolution
of S0, that is, as if it were the result of a \virtual" application of one or more
schema evolution operators to S0. In the remainder of the paper we will
concentrate only on transformations involving a single operation. We consider a small
set of operators, which is however su ciently expressive and general for most
common real scenarios: addition/deletion of attributes, partition of tuples into
separate relations, union of relations into a single relation, projection
decomposition of a relation into multiple ones, join of multiple relations into a single one,
attribute dereferencing (that is extracting an attribute into a foreign key-related
relation).
Transformations could be modeled in various ways, procedural or declarative. We
adopt the notion of schema mapping [
Hence, each transformation relating the reference schema S0 to any Si can be associated with a schema mapping Ei. In the example, S1 is identical to S0 (so we have the identity mapping), while S2 is obtained with a partition on the basis of Year values and S3 with decomposition by projection.
Then, in our example, the mappings between S0, S2 and S3 would be represented as follows: BalSheet(Year: y, Bank: b, IoBName: in, IoBCred: ic, IoBDeb: id), y 2012 ! BalSheet2013(Year: y, Bank: b, IoBName: in, IoBCred: ic, IoBDeb: id) E3: BalSheet(Year: y, Bank: b, IoBName: in, IoBCred: ic, IoBDeb: id) ! BalSheetCredit(Bank: b, IoBName: in, IoBCred: sum(ic, groupBy(b; in))),
BalSheetDebit(Bank: b, IoBName: in, IoBDeb: sum(id, groupBy(b; in)))
The idea we have just discussed, that the various source schemas are
variations of a reference one S0, allows us to concentrate on the mapping between S0
and the target schema G0. This is summarized in Figure 3, where M relates S0 to
G0 and Ei is the representation of the transformation between S0 and a speci c
source Si. Then, with our approach, the user should focus just on the reference
source schema S0 and describe its mapping M to the global schema. Indeed, we
are interested in mappings between the various Si's and G. Intuitively, this can
be obtained by composing the inverse of each Ei with M . Let us go back to our
example; with respect to G in Figure 1, we have:
1 Our tgd's are indeed a bit more complex than those usually found in data exchange
settings [
M : BalSheet(Year: y, Bank: b, IoBName: in, IoBCred: ic, IoBDeb: id)
! RepoOfBalances(Bank: b, IoBName: in, Amount: sum(ic id, groupBy(b; in)))
where for each Bank and IoBName, the Amount is calculated by subtracting
debits from credits. The aggregation then sums the contributions from di erent
Year s. In order to make M work also for S2, we should \undo" the
transformations from S0 to S2 (E2) and then apply the original mapping M , as
summarized in Figure 3. In other words, the goal would be to nd a new mapping
M2 = E2 1 M and similarly for every other possible source Si. In most cases, the
various results would need to be consolidated, usually by means of a merge
operator [
Technical issues
Let us now discuss the technical issues. Indeed, our goal is to nd a mapping Mi
between Si and G0, given the mappings Ei between S0 and Si and M between S0
and G0. For this kind of problems, solutions have been discussed in the literature,
based on composition and inversion operators [
One major problem is that rarely do schema mappings have such an exact
inverse, as they may involve information loss; in such cases, source instances
cannot be rebuilt from target ones. This is also the case for our transformations:
E3, for instance, is lossy, since it decomposes a relation into two other relations
where aggregations are applied. This causes loss of information and the original
relation cannot be reconstructed with a join. Vice versa, E2 is lossless, because
the partition (which, by de nition, forbids overlapping) can be reversed with
a union. However, let us consider, in this case, a relaxed notion of inverse, for
example quasi-inverses of schema mappings [
BalSheetDebit(Bank: b, IoBName: in, IoBDeb: id) ! 9y (BalSheet(Year: y, Bank: b, IoBName: in, IoBCred: ic, IoBDeb: id)) Notice that E3 1 is far from being an exact inverse because the aggregated contributions of di erent Year s have not been decomposed; moreover Year is existentially quanti ed and its original values have not been restored. Nevertheless, we deem that this inverse is su cient for our purpose since, in this case, E3 loses less information than M . In facts, with a simple substitution, the composition 2 The inverse M 1 of a schema mapping M is such that M 1 M = Id, where Id is the identity mapping, transforming each instance into itself. 3 Notice that the original de nition does not foresee aggregations, which however we support here. with M yields:
An interesting idea is the de nition of some kind of order relation s, based
on the amount of \transferred information" [
Our result is that whenever the order relation M S0 Ei holds for every Si, it is possible to integrate all the di ering sources, also in presence of aggregations, calculating Mi through a suitable notion of inverse, for example quasi-inverses. An intuitive proof for this consists in verifying that the order relation guarantees the presence of some mappings from Si to G (since Ei transfers more information than M ) and one of them, Mi , can be calculated by suitably inverting Ei and composing with M . 3
Let us now consider the more general case, where the global schema is not dened in advance, but it may depend on the speci c sources. Di erent scenarios are indeed possible and the global schema may depend on source data or metadata (names of relations and attributes) or both. Here we concentrate on the most interesting case, which is the one where attributes of the global schema derive from values in the sources. This is also the most relevant condition in real contexts, as it can be the consequence of a common practice in exchange formats between a local and a central organization, that of embedding \schematic" information into data.
An example appears in Figure 2, where the values of IoBName (\Asset" and \Liability") are schematic elements as they qualify the other two attributes IoBCred and IoBDeb: a credit or a debit, in facts, is meaningful only if referred to a speci c item of balance. An alternative representation would have four attributes, for expressing credits and debits for each of the two possible item names. In this latter representation, the introduction of a new item of balance, for instance \Equity", would require to alter the schema giving rise to a new variant and so on.
Here we sketch a novel technique to handle such situations. Basically, it consists in the de nition of template tgd's, an extended version of usual tgd's that allow metadata-data correspondences. They are intended to be used for expressing correspondences between S0 and the baseline global schema G0, in the mapping M . We allow quanti ed variables not only to denote values, but also attribute names. Indeed, the baseline global schema referred to in the rhs of template tgd's is somehow polymorphic, as it contains variables for the attributes that are not known in advance, but their presence and name depend on the source data.
A key feature of our approach is a rewriting algorithm, generating usual tgd's
out of the template ones, given the source data. For each tuple matching the lhs
of a template tgd, the algorithm generates one or more attributes in the schema
of the rhs, eventually specifying the global schema G, where all the attributes
have been made explicit. The tgd's generated in this way respond to the usual
de nition and can be then enforced with the common chase procedure [
An example of template tgd is the following mapping M 0 between S0 and G0: M 0: BalSheet(Year: y, Bank: b, IoBName: in, IoBCred: ic, IoBDeb: id) ! RepoOfBalancesAlt(Bank: b, in: sum(ic id, groupBy(b))) The rhs describes the baseline global schema G0, with an attribute variable, in, used for unknown attributes. For its value, the expression sum(ic id, groupBy(b)) speci es that in RepositoryOfBalancesAlt, Asset and Liability are all calculated as aggregations (an aggregation each), grouping by the only disaggregated attribute, which is Bank .
Initially G0 contains all the attributes that are fully speci ed in G0 (only Bank in this case). In the rewriting phase, for each tuple in the lhs, an attribute named after the value bound to in (\Asset" or \Liability") is added. 4 At the end, the rewritten tgd, which can be chased and enforced in the usual way, is: Mc0: BalSheet(Year: ya, Bank: b, IoBName: \Asset", IoBCred: ica, IoBDeb: ida),
BalSheet(Year: yl, Bank: b, IoBName: \Liability" , IoBCred: icl, IoBDeb: idl) ! RepoOfBalancesAlt(Bank: b, Asset: sum(ica ida, groupBy(b)),
Liability: sum(icl idl, groupBy(b))) 4
We provided a solution to the problem of data integration in contexts where there are a large number of di erent sources whose schema is not completely known beforehand and the global schema can depend on the source data. We consider a single data source as a reference and map it, with schema mappings, into the global schema. All the other sources are described as if they were obtained as a schema evolution of the reference.
While data integration has been studied in a variety of theoretical and
practical contexts [
Dynamic global schemas rely on the notion of \schematic transformation",
introduced in [