mopdf.com

Clio: Schema Mapping Creation and Data Exchange201The chapter is organized as follows. Section 2 introduces a motivating exampleand describes the problem of schema mapping generation and the problem ofdata exchange. Section 3 presents the data model we will use for representingboth relational and nested relational schemas along with our schema mappingformalism. Section 4 presents our algorithm for generating schema mappings.Section 5 presents our algorithm for data exchange (mapping code generation).We present a discussion and analysis of our algorithms in Section 6, describe therelated work in Section 7 and then conclude.2A Motivating ExampleTo motivate our approach, we first walk through an example explaining theintuition behind our mapping creation algorithm, and highlighting some of itsfeatures. We then extend our example to illustrate how schema mappings canbe used to generate queries for data exchange, and describe the key innovationsin that algorithm.2.1Schema Mapping CreationSchema. Consider a data source with information about companies and grants.The structure of its data is described by the Schema S, illustrated in Figure 1. It isa relational schema containing three tables, companies, grants, and contacts,presented in a nested relational representation that we use to model both relational and XML schemas. It contains a set of grants (grants), each consisting ofa grant identifier (gid), a recipient (recipient), its amount (amount), its supervisor (supervisor) and its manager (manager). The recipient is actually thename of the company that received the grant. For each company, the databasestores its name (name), address (address) and the year it was founded (year).Similarly, the supervisor and manager are references to some contact information, which consists of an identifier (cid), an email (email) and a phone number(phone). The curved lines f1 , f2 and f3 in the figure represent referential constraints specified as part of the schema. For example, f1 may be a foreign key, orsimply an inclusion dependency, stating that values in grants.recipient mustalso appear in companies.name.Consider a second schema T , as illustrated on the right-hand side of Figure 1. It records the funding (fundings) that an organization (organizations)receives, nested within the organization record. The amount of each funding(budget) is kept in the finances record along with a contact phone number(phone). The target may be an XML schema containing a referential constraintin the form of a keyref definition (f4 ).Correspondences. To begin to understand the relationship between theschemas, we may invoke a schema matcher to generate a set of element correspondences (or matchings). Alternatively, we could ask a user (for example, adata designer or administrator familiar with the schemas) to draw lines between

202R. Fagin et al.Schema S:Schema T:organizations: Set of Rcdcompanies: Set of Rcdnameaddressyearv1fundings: Set of Rcdgrants: Set of v2fidfinIdfinances: Set of Rcdv3f3finIdbudgetphonef4contacts: Set of Rcdcidemailphonev4Fig. 1. A source and a target schema in a mapping scenarioelements that should contain related data. In our example, the dashed arrowsbetween the elements of the two schemas in Figure 1 represent a set of matchings or correspondences. The line v1 indicates (informally) that what is calleda company name in the first schema, is referred to as an organization code inthe second. In contrast, both schemas have an element year, but the data administrator (or matching tool) has specified no arrow between them. That maybe because there is reason to believe that these elements do not represent thesame concept. For instance, element year in the first schema may represent thetime the company was founded, while in the second it may represent the timethe company had its initial public offer (IPO).Our approach is agnostic to how correspondences are created, whether manually or (semi-)automatically, but is cognizant that matchings are often incomplete, and sometimes incorrect. Hence, we have developed techniques for incrementally modifying mappings as correspondences change [49]. To keep ourexample simple, we assume that correspondences v1 , v2 , v3 , v4 are correct.Mappings. One way a correspondence can be interpreted is that the targetschema element should be populated with values from the source schema element.This can be formally expressed using an inter-schema inclusion dependency ormore generally through a source-to-target tuple generating dependency, (tgd) [7].A tgd representing correspondence v1 of Figure 1 is shown below (the nested setfundings which is represented by the variable F inside organizations will beexplained below). n, d, y, companies(n, d, y) y , F organizations(n, y , F )(1)This simple mapping states that for each companies tuple, there must bean organizations tuple whose code is the same as the companies.name; this isrepresented by the shared variable n, which carries source data to the target. As aconvention, when writing tgds, we underline all the variables that appear in boththe left-hand side and the right-hand side of the implication. This target tuple

Clio: Schema Mapping Creation and Data Exchange203must have a value for the year attribute, but the mapping does not specify whatthis value should be (this is represented by the existential variable y ). Similarly,we could write simple tgds to express the other three correspondences.If our application only requires information about organizations (and notabout fundings or finances), then we can stop the mapping generation here.This simple element-to-element mapping can be used for data exchange or fordata integration [52]. However, if the user is interested in mapping more data,we can continue the mapping generation using the other correspondences fromFigure 1 to map additional concepts.Associations. Correspondences alone do not specify how individual data valuesshould be connected in the target. For example, in the target, funding information is nested inside organizations. This nesting indicates that there is a semantic association between organization and funding records. This may representorganizations and the funding that the organization has received, or possibly organizations and the funding that they have given to others. The semantics is notspecified precisely in the schema, but it is clear that some real-world associationis being represented. Given this, we will look for associations between organization information and funding information in the source to see if one of these canbe used to associate data in the target. For our example, organizations.codecorresponds to companies.name, while fundings.fid corresponds to grants.gid.Hence, our algorithm will search for associations between these source elementswithin the source schema. In our example, the referential constraint f1 indicatesthat each grant is associated with a company, thus this constraint can be usedto associate each company with a set of grants. In general, there may be manyways to associate elements within a schema. Our algorithm will use logical inference to find all associations represented by referential constraints and a schema’srelational and nesting structure.For our example, we have only one way of associating company names andgrant gids in the source, so we will use this association to associate fundings withorganizations in the target. A mapping reflecting this association is representedby the following formula. n, d, y, g, a, s, m companies(n, d, y), grants(g, n, a, s, m) y , F, f organizations(n, y , F), F(g, f )(2)The variable F in formula (2) does not represent an atomic value, but rather aset identifier, and is also used as a term in the formula. This variable representsthe set of fundings that an organizations tuple has.Notice that Mapping (2) specifies what must be true of the target data, giventhat a certain pattern holds in the source data. In this example, it says that ifa grant joins with a company in the source, then there must be an organizationin the target with the name of the company as its code, and with a fundingsrecord nested inside of the organization record that has the grant’s gid as itsfundings.fid. No other constraints are placed on what is in this set. So the

204R. Fagin et al.mapping is specifying that the association between grants and companies shouldbe preserved in the target.Now let us consider the correspondence v3 . Considered in isolation, this correspondence could be represented by the following mapping. g, r, a, s, m grants(g, r, a, s, m) f, p finances(f, a, p)(3)However, this mapping does not recognize that grant amounts are associated with specific grant gids (in the source) and that fundings.fid andfinances.budget are associated in the target (through the referential constraintf4 ). If these two associations represent the same semantic association, then abetter mapping can be constructed by using the source and target associations. n, d, y, g, a, s, m companies(n, d, y), grants(g, n, a, s, m) y , F, f, p organizations(n, y , F), F(g, f ), finances(f, a, p),(4)Notice that a company and grant tuple that join in the source will create threetuples in the target: an organizations tuple, a fundings tuple (which is nestedinside the organizations tuple), and a finances tuple. The mapping specifiesthat the fundings and finances tuples must share the same value (f ) in theirfinId attributes. It does not, however, specify what this value must be (that is,the variable f is existentially quantified and is not bound to source data).Now to complete our example, let us consider the final correspondence v4 . Inthe target, a phone is associated with a budget because they are representedin the same relation finances. In the source, there are two ways to associatea grants.amount (the source for finances.budget) and a contacts.phone (thesource for finances.phone). These are represented by the two referential constraints f2 (which associates a grant with its supervisor’s phone) and f3 (whichassociates a grant with its manager’s phone).It is not clear which, if either, of these associations should be used to createfinances tuples. Clio will create two mappings, one using f2 (Mapping (5))which uses a join on supervisor, and one using f3 (Mapping (6)) which uses ajoin on manager. To help a user decide which mapping to use, Clio provides adata viewer which allows users to see (and compare) sample target data createdby each mapping [51]. n, d, y, g, a, s, m, e, p companies(n, d, y), grants(g, n, a, s, m), contacts(s, e, p) y , F, f organizations(n, y , F), F(g, f ), finances(f, a, p)(5) n, d, y, g, a, s, m, e, p companies(n, d, y), grants(g, n, a, s, m), contacts(m, e, p) y , F, f organizations(n, y , F), F(g, f ), finances(f, a, p)(6)We have illustrated a few of the issues involved with generating schema mappings. We now highlight some of the features of the Clio mapping algorithm.

Clio: Schema Mapping Creation and Data Exchange205Mapping Formalism. As our example illustrated, we use source-to-target tgds,a generalization of the relational tgds of Fagin et al. [19] to the nested relationalmodel, to represent schema mappings. Our mappings are a form of what hasbeen called sound GLAV (global-and-local-as-view) mappings [33]. In general,a GLAV mapping asserts a relationship between a query over the source and aquery over the target. We use sound mappings, where the relationship betweenqueries is a containment relationship (the result of the source query is containedin the target query) as is common in data integration. Such mappings do notrestrict what data can be in the target; hence, we have the freedom to mapmultiple sources into a single target.Mapping Generation. Clio exploits the schema and its constraints to generate a set of alternative mappings. Our approach uses the chase technique [36]to generate all possible associations between source elements (and all possibleassociations between target elements). The mappings are formed using theseassociations or other associations given by a user.Multiple Mappings. As we create mappings, each query may omit informationthat the user may have wanted included. Consider Mapping (2). This mappingtakes grants that have an associated company and creates target data from thisinformation. Notice, however, that companies that have no grants would notbe included in the mapping. We may want to include all companies, not justcompanies with grants, in the target. To allow for this, Clio generates a setof mappings that would map all source data (in this example, both companieswith and without grants). A user can then choose among these mappings. If sheonly wishes to map a subset of the source data, she can do so by selecting anappropriate subset of the mappings Clio generates.2.2Query Generation for Data ExchangeFor data exchange, Clio can generate code that, given a source instance, willproduce an instance of the target schema that satisfies the mapping and thatrepresents the source data as accurately as possible. In general, given a sourceinstance there may be many target instances that satisfy the mapping (or manysolutions in data exchange parlance [19]). Hence, to perform data exchange, wemust choose a single “best” target instance, i.e., a single solution to materialize.Let us assume, for example, that the instance of the source schema of Figure 1is the one illustrated in Figure 2, and that a user has indicated that Mapping (5)is correct and would like to create a target instance. For each companies tuplethat joins with grants and contacts, the mapping indicates that there shouldbe an organizations tuple containing as organization code the company name.Furthermore, there must also be a nested fundings element containing the gidof the grant from the source. Finally, a finances element must also exist withthe same value for its finId as the value of finId in this fundings record.Moreover, the finances element must contain the grant amount in the budgetelement and the supervisor phone number as phone. An instance that satisfies

206R. Fagin et al.Companiesname addressMSRedmond, SAAT&T Dallas, TXIBM Armonk, NYGrantsgid recipientg1 MSg2 MSg4 [email protected] [email protected] [email protected]@attDorman 73706625236072703600102Fig. 2. An instance for the source schema in Figure 1the mapping, i.e., a solution, can be seen in Figure 3. In this solution, fundingstuple g1 can correctly be joined with the first finances tuple to associate it withits correct budget (1M). However, in Figure 3 all fundings tuples are associatedwith all finances tuples, which was not true in the source. In data exchange,we would like the target instance to represent only the data associations in thesource. Clearly the instance of Figure 3 does not fullfill that desire. Furthermore,the last tuple in the Finances table does not correspond to any source data, yetits inclusion in the instance does not violate Mapping (5). So while this instanceis a solution, it is not minimal.Fagin et al. [19] proposed the use of universal solutions for data exchange. A universal solution is an instance of the target schema that contains no more and noless than what the mapping specification requires. A universal solution for Mapping (5) is given in Figure 4. Note that the values of the finId attribute havebeen created to associate each fundings with all and only the finances tuplesthat contain the correct budget amount. The instance is also minimal in that itdoes not contain any tuples that were not required to be in the target. To computea universal solution, Fagin et al. [19] present an algorithm based on the chase [36].However, in Clio, we use queries to perform the data exchange. Here we presentalgorithms that, given a schema mapping, generate a set of executable queries toperform the desired data exchange. The queries can be in SQL, XQuery or XSLTdepending on the desired runtime environment. In the case of a pure relationalsetting (relational source and target schemas), these queries generate a universalsolution. In our algorithm, we make use of Skolem functions (one-to-one functions) that generate values based on a set of source values. We will discuss laterhow to determine the correct arguments for these Skolem functions and when oneSkolem function should be reused in different schema elements. For example, inSection 5, we show why the Skolem function for finId needs to depend on foursource attributes (name, gid, amount, and phone).In the case of a nested target schema, Clio applies additional groupingand nesting to produce a target instance that is in PNF (Partitioned Normal

Clio: Schema Mapping Creation and Data Exchange207Organizationscode yearMSFundingsfid finIdg1 10g2 10code yearAT&TFundingsfid finIdg4 10FinancesfinId 09479Fig. 3. A non-universal solution target instance for Mapping (5)Form) [1]. This is done to minimize the redundancy in the target instance.Consider the universal solution given in Figure 4 which contains a differentorganizations tuple with a singleton fundings set for each companies andgrants pair in the source, even if multiple pairs share the same company name.Clio avoids this redundancy, by producing a single organizations tuple for eachsource name and grouping all the fundings that belong to the same organization together under one single organization element (Figure 5). As shown in thefigure, we use Skolem functions to represent set identifiers for each fundingsset. Our algorithms determine the correct arguments for these Skolem functionsto achieve PNF grouping. In more recent work which will not be covered in thischapter [24], we have considered how to declaratively represent PNF groupingsemantics in the mapping specification along with other types of grouping. Inthis chapter, we will assume PNF is the desired semantics, and we present oursolutions for generating PNF target instances.There are two main innovations in our data exchange algorithm. The first isa new technique for generating Skolem terms to represent existential values andfor achieving grouping in the target instance. Second, our algorithm can identifyand merge data that are generated by different mappings, but represent thesame target entities. Assume, for instance, that the user wanted to populate thetarget with all the companies, independently of whether they have funding or not.Mapping (5) can generate only companies with grants (i.e., funding), due to thejoin it performs on the source data. Mapping (1) on the other hand, generates allthe companies, but without their potential funding. The desired target instancecan be achieved by using both mappings (5) and (1). The resulting instancewould be the same as Figure 5 but with an additional organizations elementfor IBM having an empty fundings subelement. The MS and AT&T tupleswould not be impacted, even though they are produced by both mappings.

208R. Fagin et al.Organizationscode yearMSFundingsfid finIdg1 Sk2 (MS,g1,1M,7062838)code yearMSFundingsfid finIdg2 Sk2 (MS,g2,2M,7066252)code yearAT&TFundingsfid finIdg4 Sk2 (AT&T,g4,3M,3607270)FinancesfinIdSk2 (MS,g1,1M,7062838)Sk2 (MS,g2,2M,7066252)Sk2 33607270Fig. 4. A universal solution target instance for Mapping (5)3Mapping Language and Schema ConstraintsSchemas and Types. We use a nested relational model to model both relationaland XML Schemas. In general, a schema is a sequence of labels (called roots),each with an associated type τ , defined by the grammar:τ :: String Integer Set of τ Rcd[ l1 : τ1 ,. . ., ln : τn ] Choice[ l1 : τ1 ,. . ., ln : τn ]Types Integer and String are called atomic types, Set of is a set type, and Rcdand Choice are complex types. With respect to XML Schema, we use Set of tomodel repeatable elements (or repeatable groups of elements), while Rcd andChoice are used to represent the “all” and “choice” model-groups. For each settype Set of τ , τ must be an atomic (String or Integer) type or a Rcd type. We donot consider order, that is, Set of represents unordered sets. “Sequence” modelgroups of XML Schema are also represented as (unordered) Rcd types.Instances. An instance of a schema associates each schema root l of type τ witha value v of type τ . For the atomic types, the allowed values are the expected ones(i.e., strings, integers). A value of type Rcd[l1 : τ1 , . . . , ln : τn ] is an unorderedtuple of pairs [l1 : v1 , . . . , ln : vn ] where vi is a value of type τi with 1 i n.A value of type Choice[l1 : τ1 , . . . , ln : τn ] on the other hand, is a pair li : vi where vi is a value of type τi with 1 i n. With respect to XML, the labelsl1 , . . . , ln model element names or attribute names, while the values v1 , . . . , vnrepresent the associated contents or value. In our model, we do not distinguishbetween XML elements and attributes.

Clio: Schema Mapping Creat

gorithms for both schema mapping creation via query discovery, and for query generation for data exchange. These algorithms can be used in pure relational, pure XML, nested relational, or mixed relational and nested contexts. 1 Introduction We present a retros