Method for schema mapping and data transformation

[0001] The present application relates to co-pending U.S. patent application Ser. No. 09/658,303, filed on Sep. 8, 2000, titled “System and Method for Schema Mapping,” and Ser. No. 09/500,648, filed on Feb. 9, 2000, titled “User-Defined Relationships For Diagramming User-Defined Database Relations,” both of which are assigned to the same assignee as the present application.

[0002] The present invention generally relates to the field of data processing, and particularly to a software system and associated method for use with possibly dissimilar databases to transfer data from at least one source database or schema to a target database or schema. The method of this invention relies on data examples to understand and refine declarative schema mappings. More specifically, this invention pertains to a visual method of mapping data from at least one source schema to a target schema in which the user incrementally creates, evolves, and composes the complex queries required for mapping large, complex, or unfamiliar data sources to a target schema while verifying that the mapping is correct.

[0003] Database systems are collections of files stored on computers or other linked systems such as the Internet. The files together contain all the information about a topic or related topics. Generally, a file system is used to “file away” information which a user will later retrieve for processing. Normally, a file resides in directly accessible storage and can be manipulated as a unit by file system operations. A file system allows a user the means for storing data in files, accessing the data in those files, managing direct access to storage space where the files are stored, and guaranteeing the integrity of those files. Businesses and other organizations use databases to manage information about clients, orders, client accounts, etc. Businesses often need to manage and merge the data from many different sources, among which are “legacy” sources that use obsolete software or data structures.

[0004] The World Wide Web (WWW) is essentially a large database. The WWW, or Internet, is comprised of an expansive network of interconnected computers upon which businesses, governments, groups, and individuals throughout the world maintain inter-linked computer files known as web pages. The volume of data available on the Internet is increasing daily, but the ability of users to understand and transform this data has not kept pace. Businesses need the ability to capture and manipulate data available on the Internet for such applications as data warehousing, global information systems, and electronic commerce.

[0005] E-commerce and other data-intensive applications rely on the ability to capture, use, and integrate data from multiple sources. To transform data from one structure or schema to another, mappings must be created between the data source (or set of heterogeneous data sources) and a target or integrated schema. While important advances have been made in the ability to create and manage these mappings, a number of important issues remain.

[0006] First, the number of possible, reasonable mappings between a data source and a target schema can be enormous. Users are unable to conceive of all the possible alternatives and may have difficulty specifying the correct mapping for a specific application. A system is needed that considers, manages, and ranks alternate mappings while allowing the final choice of mapping by a user who understands the semantics of the target schema.

[0007] Second, schema mappings are typically complex queries. Subtle changes to the mapping such as changing an inner join to an outer join may dramatically change the target data results. In other cases, the same mapping change may have no effect due to constraints held on the source schema. A system is needed that embodies the complex query and constraint reasoning needed to understand subtleties while effectively communicating these subtleties to the user.

[0008] Third, the user performing the mapping may not fully understand the source data or schema fully. This is especially true when dealing with legacy data sources. A system is needed that facilitates both schema and data exploration. In addition, the system must leverage the parts of the data and schema that the user does understand to gain maximum advantage in forming the schema mapping.

[0009] Fourth, given the complexity of the mappings and the subtle differences between alternative mappings, even an expert user may require assistance. To select a specific mapping, the user must understand the mapping plus how the specific mapping differs from other possible mappings. A system is needed that allows the user to map portions of the source data to the target without exposing the user to tangled SQL (Structured Query Language) or complex QBE (Query By Example) queries. The system should also illustrate the effects of alternate mappings, helping the user differentiate between subtle changes.

[0010] Fifth, data merging queries require the use of complex, non-associative operators. Reasoning about such operators can be extremely difficult for both users and query management tools. Because the operators may not be associative, even managing compositions of queries can be a difficult task. However, to be scalable to large schemas, mapping tools must permit users to incrementally create, evolve, and compose such complex queries. A system is needed that develops a mapping representation and set of mapping operators permitting the incremental creation and management of large, complex mappings.

[0011] The ultimate goal of schema mapping is not to build the correct query, but to extract the correct data from the source to populate the target schema. Current data transformation (ETL—Extract, Transform, and Load) tools and query formation tools focus on building queries or transformation programs, but provide limited support in verifying that the derived data set is correct. If a query or transformation is incomplete or incorrect, there is typically no support for refining and correcting it. The user is expected to have a thorough understanding of the data source and to debug complicated SQL queries or procedural transformation programs by hand.

[0012] Systems currently exist which allow a user to map data from one schema to another, as in System and Method for Schema Mapping, ARC9-2000-0125. This system allows the user to quickly transfer data from one schema to another, but requires the user to be familiar with both the source and target schema. In addition, the user interface with the system uses a visual depiction of the database structure but not of its data content. Another system, “User-Defined Relationships For Diagramming User-Defined Database Relations” RO999-167, provides a graphical interface for the user. This interface allows the user to visualize the structure of a schema, but does not provide for transfer of data from one schema to another and does not use data to guide the user.

[0013] Some ad hoc query tools focus on helping users access data using natural language or through a point-and-click graphic user interface (GUI). These requests are processed by a meta-data layer that translates them into SQL queries. In these systems, the user does not have to know SQL, understand the schema, or know how attributes are decomposed among relations. The translation process is hard-coded using (often procedural) transformation programs. These programs are provided by an expert data administrator with complete knowledge of the data. Most of these tools are tightly integrated with a report generating facility so they can readily display the query result. However, the tools do not allow the users to verify or rectify queries by working with the displayed data. Visual query builders focus on helping users compose SQL queries faster and with fewer errors, rather than focusing on understanding the data source using data and allowing users to refine their queries using data examples.

[0014] Thus, there is need for a system that provides a graphical interface for transferring data from one complex schema to another. This system should create, manage, and rank alternative mappings. In addition, the system should provide facilities for schema and data exploration to help the user understand the source structure and data. The system should also permit users to incrementally create, evolve, and compose complex queries that are scalable to large schemas. Most importantly, the system should support the understanding and verification of the correctness of complex data-transformation queries. The need for such a system has heretofore remained unsatisfied.

[0015] The system and method of the present invention for data-driven understanding and refinement of schema mappings satisfies this need. The invention describes a system and method that presents a new data-driven framework for understanding and choosing mappings based on examples. A novel aspect of the schema mapping system is the use of data examples extracted from the source databases to help users understand the extracted, transformed data. This is in contrast to QBE-style approaches that use examples as an abstraction of the query itself.

[0016] The schema mapping system of the invention uses a powerful mapping representation that facilitates the incremental creation and management of complex mappings over large data sources. In addition, use of a mapping example eases the tasks of understanding, selecting, and refining schema mappings. The schema mapping system identifies a set of operators on mapping examples and mappings, providing formal semantics for each. These operators provide an appropriate, easy-to-use abstraction for tackling the schema-mapping problem; some of the supported activities are establishing a correspondence, data linking, data trimming, data walking, and data chasing.

[0017] The schema mapping system develops a framework for showing carefully selected examples to the user, examples that change as needed in response to changes in the mapping. The schema mapping system chooses the examples to permit a user both to understand a mapping and to understand how it differs from alternative mappings. Using examples, the user can “walk around” inside the database, manipulate the data, understand how data is organized and see how to combine pieces of data meaningfully in the context of the target schema. The user can “walk” along paths known to the system of the invention (a data walk), or actively discover new ways of connecting data (a data chase). By following the “tracks” of the user, the schema mapping system gains sufficient semantic knowledge to compose complex mapping queries.

[0018] The system of the invention allows the user to visualize schema mappings from at least one source schema to a target schema. The method of the present invention can operate on one source database at a time or process all source databases at once to obtain examples from each. Additionally, the data-driven understanding and schema mapping system of the present invention provides the following actions and benefits; the schema mapping system of the present invention:

• • [0019] defines each mapping as a union of jointerms (or joint terms), each jointerm mapping different parts of the data;
  • [0020] selects examples (if possible) of actual user data content such that each jointerm produces only a few examples as opposed to selecting an entire table;
  • [0021] performs optimization to minimize the use of data common to multiple jointerms when selecting examples;
  • [0022] uses sample databases to increase efficiency in finding examples;
  • [0023] presents examples and possible alternative mappings to the user in a graphical user interface so the user can modify the mapping until satisfied;
  • [0024] shows examples of what data will be included in the target schema (positive examples) and what data will not be included in the target schema (negative examples);
  • [0025] shows the number of tuples each jointerm represents;
  • [0026] generates SQL corresponding to mappings;
  • [0027] allows data exploration in the form of a “data walk”;
  • [0028] allows identification in the form of a “data chase” of domain values occurring elsewhere in the databases; and
  • [0029] enables the user to evolve complex queries defining the mapping while continuously verifying that the current mapping is appropriate.
    These benefits are particularly useful when the relationships between the source schema and the target schema are complex, the source and target databases are large, and/or the schema and data is unfamiliar to the user.

[0030] The system of the invention derives the SQL needed to map from multiple source rows in multiple source tables to a combined row in the target table, so the user does not have to create any SQL code. The system of the invention shows carefully selected example rows that would be mapped or excluded by the mapping so the user can view the actual data to determine if the mapping is appropriate. In addition, the system of the invention displays examples of how the source data is mapped to the target database. These examples may be unfinished mappings or alternate mappings. Mappings can be positive (data that will be moved to the target) or negative (data that will not be moved to the target). One novel feature of the system of the invention is the emphasis on placing data in the target properly, as opposed to formulating queries and SQL.

[0031] There may be a tremendous number of potential mappings from the source to the target databases. In addition, the user may not fully understand the source data or schema. Another novel feature of the system of the invention is the ability to explore the source schema and data through data walks and data chases. The system of the invention allows users to incrementally create, evolve, and compose complex queries while allowing the user to verify that a desired data set is correct.

[0049] The following definitions and explanations provide background information pertaining to the technical field of the present invention, and are intended to facilitate the understanding of the present invention without limiting its scope:

[0050] GUI: Graphical User Interface, a program interface that takes advantage of the computer's graphics capabilities to make the program easier to use.

[0051] Join: In relational databases, a join operation matches records in two tables. The two tables must be joined by at least one common field, i.e. the join field is a member of both tables. Typically, a join operation is part of a SQL query

[0052] Inner Join: the default join, producing a resulting record if a matching condition evaluates to true.

[0053] Outer Join: creates the same record whether or not the matching condition is met.

[0054] Internet: A collection of interconnected public and private computer networks that are linked together with routers by a set of standard protocols to form a global, distributed network.

[0055] Metadata: Data about data; for example, tags that indicate the subject of a WWW document. Metadata describes how or when or by whom a particular set of data was collected, and how the data is formatted. Metadata is essential for understanding information stored in data warehouses.

[0056] Record/Tuple: In database management systems, a set of information. Records are composed of fields, each of which contains one item of information. A set of records constitutes a file. For example, a personnel file might contain records that have three fields: a name field, an address field, and a phone number field. A record corresponds to a row in a table.

[0057] QBE: Query By Example, a method of forming queries in database management systems in which the database program displays a blank record with a space for each field. The user then enters conditions for each field included in the query.

[0058] Schema: Format or structure. It defines the structure and type of contents of constituent structures of, for example, a relational database, XML documents, etc.

[0059] SQL: Structured Query Language, a standardized query language for requesting information from a database.

[0060] FIG. 1 portrays the overall environment in which a data-driven-understanding-and-refinement-of-schema-mapping system 10 according to the present invention may be used. The system 10 includes software or a computer program that is typically embedded within or installed on a host server 15. Alternatively, the system 10 can be saved on a suitable storage medium such as a diskette, a CD, a hard drive, or like devices. While the system 10 will be described in connection with the WWW, the system 10 can be used with a stand-alone database of documents or other text sources that may have been derived from the WWW and/or other sources.

[0061] The cloud-like communication network 20 is comprised of communication lines and switches connecting servers such as servers 25, 27, to gateways such as gateway 30. The servers 25, 27 and the gateway 30 provide the communication access to the WWW Internet. Users, such as remote Internet users are represented by a variety of computers such as computers 35, 37, 39, and can query the host server 15 for the desired information.

[0062] The host server 15 is connected to the network 20 via a communication link such as a telephone, cable, or satellite link. The servers 25, 27 can be connected via high speed Internet network lines 44, 46 to other computers and gateways. The servers 25, 27 provide access to stored information such as hypertext or web documents indicated generally at 50, 55, and 60. The hypertext documents 50, 55, 60 most likely include embedded hypertext link to other locally stored pages, and hypertext links 70, 72, 74, 76 to other webs sites or documents 55, 60 that are stored by various web servers such as the server 27.

[0063] FIG. 2 illustrates the high-level architecture showing the schema mapping system 10 used in the context of an Internet or Intranet environment. A data source such as a data base management system (dbms) 200 with associated database 205 stores data in a source schema while the data target 210 stores data in the target schema. The database 205 may reside in a Web server or other location remote from the user computer 15 and may be accessible via a wide area network such as, but not limited to, an Internet.

[0064] As shown in FIG. 2, the computer 15 is electrically or optically connected to one or more input devices 215 such as a mouse or keyboard which are manipulated by the user to interact with the schema mapping system 10. The results of the system 10 execution can be output via an output device 220 such as a printer or monitor that are connected to the user computer 15.

[0065] The logic framework used by the schema mapping system 10 includes mappings and examples. Mapping is defined as a query on the source schema 205 that produces a subset of a target 210 relation. Generally, portions of a target 210 relation are computed by separate queries. The results of these queries are then combined to form the final content of the target 210 relation. Thus, a mapping defines one out of possibly many ways of forming target 210 tuples. Examples demonstrate either how a set of source 205 tuples combine together to contribute toward the target 210 relation, or how source 205 tuples are combined together correctly but fail to make it into the target 210.

[0066] Mapping construction includes three activities. The first activity, determining correspondences, determines where and how source data values 205 should appear in the target schema 210 and how the system 10 combines or transforms source 205 values to make up target 210 values. The second activity, data linking, determines how source 205 tuples from different relations should be combined to form a target 210 tuple plus the conditions used to join source 205 relations. The third activity, data trimming, determines which of the joined source 205 tuples should be used in forming a target 210 tuple.

[0067] Design of the schema mapping system is based on the following formal notion of mapping that represents the decisions made in each of the three mapping activities. Let A be a set of attributes, where for each A∈A there is an associated domain dom(A) of values. A scheme S is a finite set of attributes. A tuple t on S is an assignment of values to the attributes of S. For an attribute A∈S, t [A]∈dom(A) denotes the value of t on A.

[0068] A tuple may be denoted using a set of attribute-value pairs:
t={A₁:v₁,A₂:v₂, . . . }.  (1)
A relation on scheme S is a named, finite set of tuples on S. When confusion will not arise, the system 10 uses the same symbol for both a relation and its name. A database is a set of relations over mutually disjoint schemes where the database schema is the corresponding set of relation names. The common assumption is that the relations in the source database 205 do not contain any tuples null on all attributes because it is unclear how such a tuple should be should be reflected in a schema mapping. A predicate P over a scheme S maps tuples on S to true or false. A predicate is strong if it evaluates to false on every tuple that is null for all attributes in S. A join predicate is a strong predicate over attributes in two relations. Note that join predicates in SQL are strong. A selection predicate is a predicate over attributes in one relation. The system 10 does not require selection predicates to be strong. Mappings may require multiple copies of a relation. System 10 assumes that if multiple copies of a relation are required, each copy and its attributes have been given unique names that in turn may be used unambiguously in predicates.

[0069] To construct a mapping, the system 10 uses value correspondences to know where data should appear in the target 210, i.e., in what attribute and manner the data should appear. A value correspondence is a function defining how a value or set of values from a source database 205 can be used to form a value in a target 210 relation such that v is a function over the values of a set of source 205 attributes A¹, . . . , A^k that computes a value for target 210 attribute B.
v:dom(A¹) x . . . xdom(A^k)→dom(B)∪{null}  (2)
Note that value correspondences are simply functions on attribute values. They do not indicate which values will be included in the mapping nor how different values will be associated.

[0070] Data linking uses query graphs to represent the linkage among source 205 tuples, that is, how the system 10 combines source 205 tuples correctly in the context of a target 210 relation. A query graph G=(N, E) over a database schema S is an undirected, connected graph where N is a subset of the relation names in S. Each edge
e=(n₁, n₂)∈E  (3)
is labeled by a conjunction of join predicates on attributes in the union of the schemes of n₁ and n₂. A query graph thus defines a way of associating tuples from different source 205 relations. The nodes of a query graph are source 205 relation names. The edges represent join predicates between pairs of source 205 relations.

[0071] Before defining the scope of a mapping, i.e., which source 205 tuples are to be included in the mapping, the system 10 must consider possible interpretations of a query graph. Clearly, one interpretation is as a join query. However, to support the data merging semantics of mappings, the system 10 may also need to interpret a query graph as an outer join query or as a combination of joins and outer joins. The system 10 refers to the set of all possible tuple associations that conform to a query graph as its data associations. The data associations for system 10 fall into three categories: full data associations, possible data associations, and data associations.

[0072] The set of full data associations of the query graph G is defined as
F(G)=σ_p(R₁× . . . ×R_n)  (4)
where G(N, E) is the query graph and P is the conjunction of all edge predicates in G Given a query graph G, the full data associations of G can be computed by an inner join query, based on G. Note that the join need not be lossless; there may be tuples from the source 205 relations that do not contribute to any full data association. A full data association is “full” because it involves tuples from all nodes of G. In defining mappings, the system 10 may also consider non-full associations. For each induced, connected subgraph J=(J_J, E_J) of the query graph G, if d is a full data association of J, then d padded with nulls on all attributes in N−N_J is a possible data association of G. The coverage of d is N_J, denoted as coverage(d)=N_J.

[0073] Generally, non-full data associations may be important to include in a mapping if there is no full data association that includes more information, as is represented by subsumption. A tuple t₁ subsumes a tuple t₂ if t₁ and t₂ have the same scheme and t₁[A]=t₂[A] for all attributes A where t₂[A]≠null. Moreover, t₁ strictly subsumes t₂ if t₁≠t₂; a strictly subsumed tuple is “redundant” since it repeats information that is already represented by another tuple. The minimum union operator removes such redundancies where the minimum union of two relations R₁ and R₂, denoted R₁⊕R₂, is the outer union of R₁ and R₂ with strictly subsumed tuples removed. The outer union is the union of R₁ (padded with nulls on attributes that are in R₂ but not in R₁) and R₂ (padded with nulls on all attributes that are in R₁ but not in R₂).

[0074] The set of all data associations of the query graph G is defined as D(G):
D(G)=S(G)−U(G)  (5)
where S(G) is all the possible data associations of G and U(G) is the set of tuples in S(G) that are strictly subsumed by another tuple in S(G). A data association is therefore a tuple in D(G), which can be computed by combining full data associations over all induced and connected subgraphs of G, using minimum union. That is, if J₁, . . . , J_ω are all the induced and connected subgraphs of G, then
D(G)=F(J₁)⊕ . . . ⊕F(J_ω).  (6)
D(G) is the full disjunction of query graph G. The full disjunction provides natural semantics for data merging queries.

[0075] Once a query graph G is established, the system 10 preserves all possible linkages among source 205 tuples by computing D(G). However, not all tuples of D(G) may be semantically meaningful in the context of the target 210 relation. The schema mapping system uses data trimming to specify which data associations match the semantics of the target 210 relation.

[0076] For any induced subgraphs J₁, J₂ of G,
D(G, J₁)∩D(G, J₂)=Ø if J₁≠J₂  (7)
where system 10 assumes that no source 205 tuples are null on all attributes, J=(N_J, E_J) is an induced connected subgraph of G, and D(G,J) is the set of data associations in D(G) whose coverage is N_J. D(G) can be partitioned into ω subsets, D(G,J₁), . . . , D(G,J_ω), if J₁, . . . , J_ω are all the induced connected subgraphs of G. Each D(G,J_i) is a category of D(G). Data associations in some of these categories may be too incomplete to include in the mapping. Generally, a user may determine that some categories D(G) (i.e., specific D(G,J_i)) must be excluded from the mapping because they have incomplete coverage.

[0077] Alternatively, a user may wish to exclude data associations that satisfy some selection predicate or other criteria. The user may determine that some data associations must be excluded from the mapping because they have invalid values, i.e., the associations fail to satisfy certain conditions on the values they contain. System 10 allows exclusion of both incomplete and invalid values by using filters.

[0078] As described above, the three activities involved in mapping construction are creating correspondences, data linking, and data trimming. System 10 supports the activity of creating value correspondences, the activity of data linking, and the activity of data trimming. System 10 uses these three activities to build a representation of a mapping.

[0079] A mapping from N to T is a four-tuple G, V, C_S, C_T where:

• • [0080] G is a connected query graph with node set N;
  • [0081] V={v₁, . . . , v_m} is a set of value correspondences where each
    v_i: dom(A₁ⁱ)x . . . xdom(A_ki)→dom(B_i)∪{null};
  • [0082] C_S={p₁^s, . . . , p_x^s} is a set of selection predicates over source 205 relations in N; and
  • [0083] C_T={p₁^t, . . . , p_y^t} is a set of selection predicates over the target 210 relation T based on the assumptions that N={R₁, . . . ,R_n} is a set of source 205 relation names and T(B₁, . . . ,B_m) is a target 210 relation name. The mapping query defined by M is the following:

[0084]

	select	*
	from	(	select	v1(A11, . . . , Ak11) as B1, . . . ,
				vm(A1m, . . . , Akmm) as Bm
			from D (G)
	where p1S and . . . and pks)
	where p1t and . . . and pkt.

[0085] A mapping defines the relationship between a target 210 relation and a set of source 205 relations using three components, the query graph G, the set V of value correspondences, and two sets of filters, C_S and C_T. The query graph G defines how data in the source 205 relations are linked, or “pieced” together to produce all data associations. The set V of value correspondences defines how system 10 can translate the data associations into tuples in the target 210 relation. The two sets of filters, C_S and C_T, define the conditions that source 205 and target 210 tuples, respectively, must satisfy. The schema mapping system 10 uses this mapping representation to depict arbitrary combinations of join and outer join queries, allowing system 10 to represent and manipulate a powerful class of mapping queries.

[0086] The mapping representations created by the schema mapping system 10 support the incremental development of mapping queries. The concept of mapping examples is critical to the ability of system 10 to use source 205 data to assist users in constructing mappings and in verifying that they are semantically correct.

[0087] For a mapping M=(G, V, C_S, C_T), Q_M is the mapping query defined by M. Query Q_M is a query over all data associations of G. For a specific data association d∈D(G), system 10 defines Q_M(d) as the result of the mapping query applied only to {d}. The mapping φ(M)=(G,V, Ø, Ø) (with mapping query Q_φM)) is the mapping defined by M without any source 205 or target 210 filters. An example e of a mapping M=(G, V, C_S, C_T) is a pair e=(d, t), where d∈D(G), and t=Q_φM)(d). Example e is a positive example if t=Q_M(d) (that is, if d satisfies all the conditions in C_S, and t satisfies all conditions in C_T). Otherwise, e is a negative example.

[0088] A positive example demonstrates how a set of source 205 tuples is combined together to contribute towards the target 210 relation. It provides insight into the target 210 tuples that a mapping will produce. A negative example demonstrates either a case where source 205 tuples are combined correctly (using the valid join conditions) but fail to make it into the target 210, or a case where source 205 tuples are combined by a different but plausible join condition. A negative example provides insight into what will be omitted from the target 210 by filter predicates, or by the choice of a particular join condition. An illustration is then any set of examples for a mapping. System 10 is interested only in illustrations that provide a satisfactory showcase of the behavior of a mapping.

[0089] An illustration includes a set of data associations. System 10 tags each data association with a field that encodes its coverage and that indicates whether the example it includes is positive or negative. A sufficient illustration is one that demonstrates all aspects of a mapping: the query graph, the filters, and the value correspondence. If I is a set of examples of a mapping M=(G, V, C_S, C_T), then I is a sufficient illustration of mapping M if it is a sufficient illustration of a query graph G, a data correspondence V, and the data trimming filters C_S and C_T.

[0090] A query graph defines the data associations of a mapping. As discussed previously, the set of all data associations defined by a query graph G can be partitioned according to the coverage of the data associations. Each connected subgraph J defines one component of the partition of D(G,J) called a category. It is possible that some of these categories are empty. To sufficiently illustrate a query graph, an illustration must include at least one example induced by a data association from each category of D(G) that is not empty. If I is a set of examples of a mapping M=(G, V, C_S, C_T), then I is a sufficient illustration of the query graph G=(N, E) if it satisfies the following property: for each induced, connected subgraph J=(N_J, E_J) of G, if there exists a data association in D(G) whose coverage is N_J, then I contains an example (d, t)∈I whose coverage is N_J.

[0091] Each way of forming a data association in D(G), i.e., each category of D(G), is one component of the mapping. Since there may be many such components, it is important that a user understands correctly the effect that each component has on the resulting mapping. In particular, it is important that for each category the chosen example illustrates the effect of using that and only that category. More precisely, if an example (d, t) illustrates a category induced by a connected subgraph J of the query graph, then there exists a guarantee that the tuple t will appear in the target as a result of running the mapping query applied only on {d}. Moreover, if the component induced by the connected subgraph J is ignored from the mapping, then t will not appear in the target data. System 10 guarantees this, by ensuring that there does not exist some other tuple t′ that can subsume t and that may be the result of a different category in the query graph. This is implemented in system 10 by an algorithm that generates queries to retrieve examples.

[0092] The definition of a sufficient illustration of a query graph is refined to develop a sufficient illustration of filters. I is a sufficient illustration of the data trimming predicates C_S and C_T if, for each induced, connected subgraph J=(N_J, E_J) of G, the following conditions hold:

• • [0093] if there exists a positive example (d,t) where coverage(d)=N_J, then I contains such a positive example; and
  • [0094] if there exists a negative example (d,t) where coverage(d)=N_J, then I contains such a negative example.

[0095] The effect of the filters on a mapping is illustrated from two perspectives. First, system 10 illustrates the data associations with incomplete coverage that are eliminated by the filters; these data associations do not carry enough semantics to be meaningful in the context of the target 210. Second, system 10 illustrates data associations that have enough coverage, but fail to satisfy the filters for other reasons. In this sense, the illustration provides some insight into the effect of filters in removing data associations with invalid values.

[0096] System 10 focuses on three salient properties of value correspondences to help users understand the correspondence. First, system 10 must provide enough information that the user can understand how a correspondence transforms data associations. To illustrate this, for each target 210 attribute B system 10 ensures there is an example that creates a tuple with a non-null value on B (if such an example exists). Second, system 10 must help the user understand how complete the mapping is, i.e., whether all the target 210 tuples created will have a non-null value for a particular attribute. Third, system 10 must facilitate the user's understanding of the properties of the source 205 columns that have an impact on the behavior of the value correspondence. For instance, the user should be able to understand how a value correspondence behaves when one or more of its source 205 columns are null.

[0097] I is a sufficient illustration of the value correspondences V if for each induced connected subgraph J=(N_J, E_J) of G and for each target 210 attribute B:

• • [0098] if there exists a positive example (d,t), where coverage(d)=N_J and where t[B]≠null, then I contains such an example; and
  • [0099] if there exists a positive example (d,t), where coverage(d)=N_J and where t[B]=null, then I contains such and example.
    As before, I is a set of examples of a mapping M=(G, V, C_S, C_T).

[0100] Sufficiency is a way of ensuring all aspects of a mapping are illustrated. The system 10 permits a user to select values they understand and use the examples induced by these values. Most likely, a user will be familiar with the manner in which specific data values relate to other data values; therefore, system 10 is designed to take maximum advantage of user knowledge in its illustrations.

[0101] Given a mapping, the system 10 is able to build a sufficient illustration that provides an entry point into the data source 205. System 10 makes use of evaluation and optimization techniques for the minimal union operator to efficiently compute D(G) and select a minimal sufficient illustration. From this starting point, a user may select subsets of the illustration or subsets of the original source 205 relations to focus the illustration on specific data of interest.

[0102] Several user interface methods help users understand the mapping and its illustration: The difference between positive and negative examples is displayed. For example, positive examples are displayed in black letters, negative examples are displayed in red letters. The relationship of example data in the target table and data in the source tables is displayed. For example, highlighting a row in the target table automatically highlights the corresponding rows in the (possibly multiple) source tables. For negative examples due to filter conditions, the reason for failing the filter condition is shown. For example, the data value that contradicts the filter condition is shown in a different color or font. For examples that combine data from multiple source through join conditions, the attribute values of the join conditions are displayed. This technique illustrates how and why these source tuples were combined to a target tuple. For instance, the attributes are shown in a different font.

[0103] The focus relation with scheme S_f is a distinguished relation F∈N, where the focus tuples, f, are a distinguished set of tuples from the relation associated with F. I is then focused on f if, for every data association
d∈D(G) where Π_SF(d)∈f  (8)
the resulting example (d, t) is in I, where I is a set of examples of a mapping M=(G, V, C_S, C_T) and G=(N, E). An illustration focuses on f if all data associations involving tuples of f are included in the illustration.

[0104] Illustrations help a user understand mappings, understand differences between mappings, and identify shortcomings or flaws in a mapping. System 10 enables a user to act on the knowledge gained through illustrations to extend or refine a mapping by providing to the user a suite of operators for manipulating mapping. These operators permit users to easily and effectively make use of the sophisticated query reasoning and query management knowledge encapsulated within system 10. By nature, the process of creating complex mappings is incremental. System 10 allows the user to easily invoke these operators and quickly discern their results.

[0105] After examining an illustration of a mapping, a user may invoke a mapping modification operator which creates a new mapping or set of new alternative mappings. Each new mapping is illustrated by a set of examples that are derived naturally from the current example presented by system 10. A few of the operators provided by system 10 are presented in the following description. The mapping modification operators are grouped by their effect on the mapping. First, correspondence operators permit a user to change the value correspondences. As the user adds new value correspondences to a mapping, system 10 determines a set of alternate mappings and helps the user decide among them using illustrations. Second, data trimming operators modify the source 205 and target 210 filters of a mapping. These operators change the set of source 205 and target 210 tuples included in the mapping rather than the query graph of a mapping. Data trimming operators are illustrated by system 10 using positive and negative examples so a user can see the effect of the different filters.

[0106] Additionally, system 10 provides a set of data linking operators, which directly change the query graph of the mapping. Data linking operators allow the user to extend a query graph. Using these operators, a user can incrementally build potentially complex mappings. However, the user does not need to undertake the daunting task of specifying the structure of the new query graph or changes to the current graph. Rather, the user may use data to invoke these operators by indicating what source 205 data is missing from the current illustration.

[0107] Two of the data linking operators are the data walk and the data chase. Additional data linking operators are provided by system 10; these two are described to illustrate the approach used by system 10 in data linking. When invoking a data walk, the user knows where the missing data resides in the source 205 or what source 205 relation(s) specifically contain this data. Using this information, system 10 infers possible ways of augmenting the query graph to include the new data and illustrates each new mapping alternative, for example, each alternative joinpath. A data chase is implemented when the user does not know where the missing data resides. The chase permits the user to explore the source 205 data incrementally to locate the desired data by exploiting data values included in the data associations in the current illustration. These values are “chased” through the source database 205 to discover new ways of linking the illustration data with other data values until the desired data is found. For both operators, system 10 provides the complex query management required to create and illustrate the new mapping.

[0108] For both the data walk and data chase operators, system 10 may discover many ways to extend the query graph. However, the majority of these can be quickly dismissed by the user as semantically invalid, leaving a few viable alternatives that the user can explore further using other mapping or example operators.

[0109] A data walk makes use of the knowledge of the source 205 schema of system 10, which is gathered from schema and constraint definitions and from mining the source 205 data, views, stored queries, and metadata. Using this knowledge, system 10 deduces a set of possible ways of joining relations (different joinpaths) each specified by a query graph. In general, system 10 has knowledge of a (possibly empty) set of potential query graphs for joining any two source 205 relations.

[0110] Given a query graph 300 G(N, E) shown in FIG. 3, a walk from node Q 305 of G 300 to a relation name R 310∉N is a path from Q 305 to R 310. There may be many such paths. Formally, walks (G(N, E), Q, R) are the set of all query graphs G′(N′, E′) conceivable by system 10's inference engine that satisfy the following conditions:

• • [0111] G′ is a path between Q 305 and R 310, and
  • [0112] If e∈E′ is an edge between two nodes in N, then e∈E and the label on this edge is the same in both G 300 and G′.
    If a potential graph violates the second condition above, system 10 introduces a new copy of a relation to create a valid extension.

[0113] The data walk operator extends a mapping with data walks. Let M=G(N, E), V, C_S, C_T be a mapping. Let Q∈N be the start relation which may be chosen by the user or by system 10. Let R∉N be the end relation. The result of the operator DataWalk(M, Q, R) is a set of new mappings, one for each extension G′∈walks(G, Q, R). Each new mapping is defined as M_e=G_e, V, C_S, C_T> where G_e=G∪G′. The union of a graph is defined as the union of the nodes and the union of the edges. Notice that G is an induced, connected subgraph of G_e.

[0114] The user can also extend the query graph of the mapping by using the data chase operator. The chase is designed for cases the user may not know which relations should be included in the extended query graph. When implementing a data chase, the user selects a source 205 attribute value in the current illustration and asks system 10 to show how this specific value can be used to extend the mapping. In response, system 10 identifies all occurrences of the value within the data source 205. For each occurrence, an extended mapping is formed and illustrated.

[0115] Let M=G, V, C_S, C_T be a mapping with illustration I. Let v be a value of attribute Q[A] where Q is one of the relations referenced by a node in G and v is in I. For each relation R that is not referenced by a node in M, where v∈R[B], the mapping M is extended to a new mapping chase(M).=<G′, V, C_S, C_T> The new query graph is G′=(N′, E′) where N′=N∪{R}, e=(Q, R) with label Q[A]=R[B] and E′=E∪{e}.

[0116] A data chase provides the user with a set of alternative scenarios for extending the current mapping with one outer equijoin using a selected value. It is up to the user to decide whether each extension is meaningful in the context of the current mapping. Note that chase is not targeted, i.e., the user is not asking for suggestions about how to best extend the mapping to cover a particular relation. Rather, system 10 helps the user in experimenting with new data connections. Usually, the data chase operator is used in combination with data walks to combine the user's understanding of the data with that of system 10.

[0117] As a mapping evolves, its illustration must also evolve. System 10 evolves illustrations in such a way that the user is not required to learn a new set of data in order to understand the evolution. The data in the old illustration, which is familiar to the user is retained as much as possible in the new illustration, providing a continuity requirement of illustration evolution.

[0118] Instead of selecting a completely new set of examples, a continuous evolution extends each example in the current illustration. If the new illustration is not sufficient, the user may request system 10 to add new examples to preserve sufficiency. Through continuous evolution of mapping, the role of these new examples in understanding the mapping is made clear and the user does not lose his place when existing examples disappear or mutate beyond recognition.

[0119] In addition to simple mappings, system 10 is designed to map large amounts of data between complex schemas. Mapping complexity generally falls into three categories. During the mapping process, the user must be able to manage and manipulate multiple mappings while the user explores the data, creates new correspondences and extends the query graph. System 10 provides a transformation framework to support the mapping process. The more complex the relationship between source 205 and target 210, the more mappings system 10 must handle. As a complex transformation is created, system 10 reuses portions of mappings to greatly ease the user's task as the number of mappings needed for a particular target 210 mapping becomes more numerous and complex. Finally, users often contend with large volumes of data that need to be transformed. If the user is unfamiliar with the data source 205, the amount of data itself may be an obstacle to developing a mapping strategy. System 10 helps users deal with both large source schemas 205 and large target schemas 210.

[0120] Since each mapping produces a subset of the tuples of a single target 210 mapping, many mappings may need to be created to map an entire target schema 210. Often, these mappings will have a great deal of overlap, differing only in a few correspondences or a small portion of the query graph. Re-creating the bulk of each mapping would be tedious for the user. Fortunately, system 10 stores the decisions made in creating one mapping and makes that decision process available to the user for creation of additional mappings. System 10 initiates such automatic creation of mappings when the user adds a new correspondence, forcing the system to generate an additional mapping to help complete a target 210. System 10 tries to reuse as much of an existing mapping as possible.

[0121] The performance of the data-driven understanding and refinement of schema mappings system 10 is further explained through the flowchart of FIG. 4, with further reference to an exemplary source database 205 shown in FIG. 5 and an exemplary target relation 210 shown in FIG. 6c. Assume that the user chooses in step 400 to map the source database 205 “School” shown in FIG. 5 to the target relation 210 “Kids” in FIG. 6c. The source database 205 School includes 6 related files, Children 500, Parents 505, PhoneDir 510, SBPS 515, and XmasBox 520. From schematic information, the user in step 405 indicates a correspondence between either attributes or schema constructs, using value correspondences. As shown in FIG. 6a, the user indicates that Children.ID of Children 500 corresponds to Kids.ID of Kids 210 by edge v1 600 and Children.name corresponds to Kids.name through edge v2 605. System 10 displays a sample of the data from the relevant source 205 table, Children 500, as shown in FIG. 6b along with the result of the current mapping, as shown in FIG. 6c. This allows the user to verify that Children.ID not only looks like Kids.ID at the schema level, but that the values of Children.ID belong in the Kids.ID attribute in the target database 210.

[0122] Tuples in a target 210 relation can often be computed in several ways. For instance, tuples in the target 210 relation Kids may be computed differently for children in public school and children who are home schooled. A mapping defines one out of possibly many ways of forming target 210 tuples; the mapping construction include determining correspondences, data linking, and data trimming. When determining correspondences, the user may wish to populate a FamilyIncome field with the sum of a child's parent's salaries from the source 205 Parents.Salary field of Parents 505 in FIG. 5. Using correspondences, System 10 determines how source 205 values should be combined to make up target 210 values. In the example shown in FIG. 6, several value correspondences map values in Children.ID of Children 500 to the target 210 attribute Kids.ID including a simple identity function, v_id: Children.ID→Kids.ID. Other correspondences might use several source 205 relations or even several copies of the same source 205 relation. To populate the target 210 attribute Kids.FamilyIncome, system 10 could use the value correspondence v_sal: Parents.Salary+Parents2.Salary→Kids.FamilyIncome.

[0123] In step 410 of FIG. 4, the user next indicates that the Parents.affiliation of Parents 505 should map to Kids.affiliation (edge v3 610 of FIG. 6a). The user in step 415 knows where the desired value is located in the source 205 schema and in step 420 understands how the desired value corresponds with the target schema. Since Kids.affiliation in FIG. 6c corresponds to a different relation than the rest of the Kids 210 data already mapped, it is not clear in step 425 which affiliation value should go with which kid tuple. System 10 is aware of two foreign keys in the source database 205 of FIG. 5, mid and fid of Children 500, both referencing Parents.ID of Parents 505. In step 430, system 10 shows the user these two ways of associating children with affiliations in the source database 205 as illustrated in FIG. 7. FIG. 7 shows two scenarios with the Children 500's tuple for Maya and the parent affiliation highlighted in the source database 205 School and the resulting mapping to the target database 210 Kids highlighted. Because the user is familiar with the data in the source database 205, she quickly realizes that mid and fid of Children 500 are mother ID and father ID, respectively. The user selects the scenario with the desired target 210 semantics in step 435 and system 10 adds this association to the target 210 schema in step 440. In this example, the user identifies Scenario 1, where children are associated with their father's affiliations.

[0124] Data linking is used to determine first which parent tuples belong with a child. FIG. 8 shows three different query graphs; each one represents one way of linking tuples for the source database 205 of FIG. 5, that is, one for each joinpath. For graph G 800, PhoneDir 510 and Parents 505 tuples are associated if they have common ID values. Similarly, Parents 505 and Children 500 tuples are associated if Parents.ID=Children.mid. The node set {Children, Parents2} induces graph G₁ 805, a connected subgraph of G 800. Tuple t 900 in FIG. 9 is a full data association of G₁ 805, as seen by referring to FIG. 5. The node set {Children, Parents2, PhoneDir} also induces a connected subgraph, G₂ 810, shown in FIG. 8. System 10 can pad t 900 with nulls to form a possible data association u 905 of G₂ 810. The new association u 905 is not a full data association of G₂ 810 since it does not involve a tuple of PhoneDir 510. Tuple v 910 is a full data association of G₂ 810, as seen by referring to FIG. 5.

[0125] In addition, if R₁ is the set of full data associations of G₁ 805 and R₂ is the set of full data associations of G₂ 810 then R₁=Children _mid=ID Parents and R₂=Children_mid=ID Parents _ID=ID PhoneDir. As a result, R₁⊕+R₂=R₂. It is easy to verify that all tuples in R₁, after being padded with attributes of PhoneDir 510, are strictly subsumed by tuples in R₂. This would not be true if some parents had no phone numbers in the data source 205 of FIG. 5.

[0126] The set of all induced, connected subgraphs of G 800 from FIG. 8 is the set of subgraphs induced by the following sets of nodes: {C}, {P}, {Ph}, {S}, {C, P}, {C, S}, {P, Ph}, {C, P, Ph}, {C, P, S}, and {C, P, Ph, S}. The set of all data associations of G, D(G), can be computed as follows (where p₁, p₂, and p₃ are all the predicates “C.mid=P.ID”, “C.ID=S.ID”, and P.ID=Ph.ID”, respectively):
D(G)=C⊕P⊕Ph⊕S⊕(C_p1P)⊕(C_p2S)⊕(P_p3Ph)⊕(C_p1P_p3Ph)⊕(C_p1P_p2S)⊕(C_p1P_p2S_p3Ph)  (9)
FIG. 10 shows the tuples in D(G). Each data association is tagged with its coverage. Due to space constraints, Children.docid and SBPS.location attributes are not shown since these are not used in the mapping. However, these attributes are part of the data association.

[0127] Data trimming determines which of the joined source 205 tuples should be used in forming a target 210 tuple. For example, the user may not want all children 500 to appear in the target database 210, only those under the age of seven. Similarly, a user may not wish to see information about a person's income in the target 210 unless that income is associated with a child. For instance, Row 7 1000 of FIG. 10 contains information that is not related to any children 500, and thus may not be useful for the target 210 relation Kids.

[0128] In creating a mapping for the Kids target 210 relation, the user may wish to exclude all target 210 tuples that have a null Kids.ID. The user may indicate this by specifying a not-null constraint in the target schema 210. In the mapping, system 10 represents this using a target 210 predicate over the target 210 relation Kids: Kids.ID<> null. Alternatively, the user may indicate that unless a data association involves Children 500, it is not of interest. This choice can be represented by the following source 205 predicate:
(C.ID=nullC.name=nullC.age=nullC.mid=nullC.fid=nullC.docid=null)  (10)
A simpler predicate may be used if one or more attributes of Children 500 are constrained to be non-null. Note that these two predicates on Kids 210 and Children 500 are not necessarily equivalent. Finally, a user may also specify constraints on source 205 or target 210 values. The following examples constrain the FamilyIncome attribute of the target 210 to be under $100,000 and the source 205 attribute Age of Children 500 to be under 7:

[0129] Kids.FamilyIncome<$100,000

[0130] Chidren.Age<7.

[0131] Value correspondences, query graphs, and selection predicates are combined to build a representation of a mapping. Each mapping represents one alternative joinpath. Based on the query graph G 800 of FIG. 8, V={v1, v2, v3, v4, v5} are value correspondences for Kids.ID, Kids.name, Kids.affiliation, Kids.contactPh, and Kids.BusSchedule, respectively, of the target database 210 shown in FIG. 6. Identity functions v1, v2, v3, and v5 are defined on attributes C.ID, Can., P.affiliation, and S.time, respectively. The function concat, v4, is defined on attributes Ph.type and Ph.number, with the following signature:

[0132]

	concat: String × String → String.
	The function concat produces a new string s
	by concatenating its first parameter, “:”,
	and its second parameter. For CS = {“C.age < 7”}
	and CT = {“Kids.ID ≠ null”}, {G, V, CS, CT} is
	a mapping. The query defined by this mapping is
	the following:
	select *
	from ( select C.ID as ID, Cname as name,
	P.affiliation as affiliation,
	concat(Ph.type, Ph.number) as contact Ph,
	S.time as BusSchedule
	from D(G)
	where C.age < 7
	where ID ≠ null

[0133] A sufficient illustration is one that demonstrates all aspects of a mapping. FIG. 11 shows a sufficient illustration of the query graph G 800 of FIG. 8. Notice that the query graph remains sufficient if one of the examples with coverage row 1100 CPPhS is removed. However, if the example with coverage row 1105 PPh is removed, this illustration is no longer sufficient in regard to the G 800 since it does not illustrate data associations with coverage row 1105 PPh. Also, notice that there are no parents in the database who have children and no phone. Therefore, there exists no data association with coverage CP. For similar reasons, there is no example with coverage C or CPS.

[0134] As discussed earlier, examples are chosen such that they faithfully illustrate the effect that each component of the mapping has. For example, the component CPPh is illustrated in FIG. 11 by three source tuples in tables Children, Parents and PhoneDir, representing information about “Kyle”. Although not shown in the figure, to complete the illustration for CPPh, the target tuple t is added, that would result by applying this component of the mapping to the set of three tuples mentioned before:
t={ID:001, name: Kyle, affiliation: Xerox, contactPh: 201-0001, BusSchedule: null, FamilyIncome: null}.

[0135] The example is chosen so that no other component of the mapping (such as CPPhS etc.) can produce a similar output target tuple (possibly with more information). For example, it is guaranteed that “Kyle” has no Bus Schedule entry in the database. Otherwise, a more informative tuple would have been produced by a different component of the mapping (CPPhS) and t would not make it to the target. In contrast, “Maya” is chosen as an illustration for the component CPPhS because it is an example of a child that has a Bus Schedule entry. System 10 has a query generation algorithm that is able to efficiently and correctly retrieve examples that illustrate one and exactly one component of the mapping. As an example, the SQL query used to produce examples to illustrate CPPh is the following:

[0136]

	(Select C.ID as ID, C.name as name, P.affiliation as
	affiliation,
	Ph.number as contactPh
	From Children C, Parents P, PhoneDir Ph
	Where C.mid = P.ID and P.ID = Ph.ID
	EXCEPT
	Select C.ID as ID, C.name as name, P.affiliation as
	affiliation,
	Ph.number as contactPh
	From Children C, Parents P, PhoneDir Ph, SBPS S
	Where C.mid = P.ID and P.ID = Ph.ID and C.ID = s.ID)
	JOIN
	(Select C.ID as ID, C.name as name, P.affiliation as affiliation,
	Ph.number as contactPh,
	null as BusSchedule, null as FamilyIncome,
	C.ID, C.name, C.age, C.mid,
	P.ID, P.affiliation
	Ph.ID, Ph.number
	From Children C, Parents P, PhoneDir Ph
	Where C.mid = P.ID and P.ID = Ph.ID)

[0137] The first part of the query checks that the only tuples that are retrieved are generated by the first SELECT FROM WHERE block (CPPh component of the mapping) and are not subsumed by any tuple generated by the second SELECT FROM WHERE block (CPPhS component of the mapping). The result is then joined with the third SELECT FROM WHERE block (in effect CPPh again). In addition to the values used for the target attributes, all the source columns are retrieved as well by this join. Each tuple in the result of the above query can be used as a correct, sufficient illustration for the CPPh component of the mapping.

[0138] To increase efficiency, system 10 issues these queries against an initially generated sample database. This sample database has the same schema as the original source database 200, but each table in the sample database contains only a fixed number of randomly chosen tuples of database 205. If the SQL query finds as many examples as needed in the sample database, these example tuples are used. If not, the query is issued against the original database 205 to find all possible example tuples. The tuples that are chosen to be shown to the user as examples are then inserted into the sample database, so that the next time a query is issued against the sample database, there will be a sufficient number of examples therein.

[0139] An illustration is focused on f if all data associations involving tuples of f are included in the illustration. The illustration shown in FIG. 11 is focused on Children 500, with Children 500 tuples with ID values 001, 002, 004, and 009 as the focus tuples 1100. All data associations from FIG. 10 that involve these children are included in the illustration. This illustration is not focused on the Parents 505 tuple identified by ID 205 since the data association shown in row 3 1005 of FIG. 10 involving parent 505 with ID 205 is not included in this illustration. This illustration does not provide a complete picture of the behavior of parent 505 with ID 205 under the mapping. However, this illustration allows the user to learn everything about the children mentioned.

[0140] Returning to the flow chart of FIG. 4, the user next decides to populate Kids.contactPh of Kids 210 with source 205 data (step 410). The user notices that phone numbers in the source 205 all appear in the PhoneDir 510 relation in step 415, but is unsure in step 420 how to associate phone numbers with Kids 210. The user requests system 10 to perform a data walk in step 445 to find associations between children and phone numbers. In response, system 10 produces several scenarios in step 430, two of which are shown in FIG. 12. Scenario 1 of FIG. 12a associates children with their father's phone numbers and scenario 2 of FIG. 12b with their mother's phone numbers. To illustrate the second alternative, system introduces a second copy of the Parents 505 relation to indicate that children are being associated with values in two parent tuples. The user is able to view and manipulate the illustrations, asking for different example tuples to gain sufficient understanding of the alternatives, allowing the user to select the most appropriate mapping. For this example, the user chooses the Scenario 2 in FIG. 12b and adds a correspondence from PhoneDir.number to Kids.contactPh as represented by the edge v4 615 of FIG. 6a.

[0141] Based on the example database of FIG. 5, the user wishes to add phone numbers to the Kids 210 database of FIG. 6 and the basic query graph G₁ 1300 of FIG. 13a. The possible query graphs meeting the conditions for a data walk are G₂′ 1305, G₃′ 1310, and G₄′ 1315, as shown in FIG. 13b. In response to the data walk request, system 10 produces for the user a set of alternative query graphs, depicted as query graphs G₂ 1320, G₃ 1325 and G₄ 1330 in FIG. 13a. The graph G₂ 1320 is obtained by merging G₁ 1300 and G₂′ 1305, G₃ 1325 is obtained by merging G₁ 1300 and G₃′ 1310, and G₄ 1330 is obtained by merging G₁ 1300 and G4′ 1315. Each graph represents a different way of associating children with phone numbers, i.e., different joins.

[0142] Each graph of FIG. 13a is the basis for a mapping and an illustration of that mapping. Suppose the user likes the mapping associated with query graph G₂ 1320, but notices that in cases where mid is null (child has no mother), there is no contact Ph in the target 210. The user might accept that mapping while adding the filter “mid not null”. However, the result is that motherless children disappear from the target 210. Realizing that when there is no mother, the father's phone should be used, the user also accepts the mapping associated with query graph G₃ 1325, adding the filter “mid is null”.

[0143] Returning to the flow chart of FIG. 4, the user now wishes to populate Kids.BusSchedule in the target database 210 (step 410). From the source database 205, it is not obvious where to find this data (step 415), unless the user knows that the cryptic name SBPS stands for “School Bus Pickup Schedule”. The user may not have enough knowledge of the source 205 to request a data walk to a specific relation (step 420). However, the user guesses that any tuple that records the school bus schedule of a child might carry the ID of the child. The user chooses an ID value, for example Maya's ID, 002, and asks system 10 to chase this value in step 450. System 10 locates all occurrences of this value in other relations, finding that 002 appears in one attribute of SBPS and in two attributes of XmasBox. Using the “Maya” example, system 10 displays the results as three scenarios in step 430, shown in FIG. 14 with the appearances of ID 002 highlighted. FIG. 15 illustrates possible query graphs followed by system 10 in this data chase. After reviewing the relevant data, the user selects in step 435 scenario 1 of FIG. 14 (corresponding to graph G₄ 1500 of FIG. 15) as the correct association of school bus schedules with children, adding a correspondence v5 620 from SBPS.time to Kids.BusSchedule as shown in FIG. 6a. System 10 then adds this association to the target schema in step 440.

[0144] During the mapping process, system 10 maintains and manipulates a mapping between the source database 205 and target database 210 and uses this mapping to generate examples. System 10 uses input from the user along with sophisticated query and constraint reasoning to derive this mapping. System 10 also uses target 210 constraints provided as part of the schema or input by the user as part of mapping creation. For example, a target 210 constraint may indicate that every Kid 210 tuple must have an ID value. From this constraint, system 10 knows not to include SBPS 515 or Parent 505 values in the target 210 if they are not associated with a Children 500 tuple. Using this constraint plus the user choices made in the example of FIGS. 4 through 15, system 10 derives the following mapping:

[0145] create view Kids as

• • [0146] select C.ID as ID, Can. as name, Paffiliation as affiliation, D.number as contactPH, S.time as BusSchedule
  • [0147] from Children C
  • [0148] left join Parents P on C.fid=P.ID
  • [0149] left join Parents P2 on C.mid−P2.ID
  • [0150] left join PhoneDir D on C.ID=D.ID
  • [0151] left join SBPS S on D.ID=S.ID
  • [0152] where C.ID is not null;
    Notice that system 10 uses left outer joins extensively to make sure that even children without affiliation, contactPh, or BusSchedule are extracted from the source database 205. By showing the result of the mapping as well as sample source 205 data, system 10 allows the user to fine-tune this mapping. For example, if the user is interested only in children who do have a bus schedule, the user can indicate that BusSchedule is a required field. System 10 would then change this left outer join to an inner join.

[0153] The schema mapping system provides users with a target table viewer 1600, a source table viewer 1605, displaying all source relation 1610 through 1630 participating in the mapping, as shown in FIG. 16. The target viewer 1600 shows the examples of contents of target schema 210 as positive examples, as they would be under the “current mapping”. The target viewer 1600 also shows negative examples as they would be under other mappings using different joinpaths. Finally, the target viewer 1600 shows negative examples as they would be if filter conditions would be missing.

[0154] The source table viewer 1605 shows examples of contents of source schema 200. It shows a set of examples for each source table. These examples correspond to the examples shown in the target table viewer 1600. An example shown in the target table viewer combines data values from at least one source table. Highlighting an example therein automatically highlights the corresponding examples in the source table viewer. Thus it is visualized where data values come from and how they are combined.

[0155] The source table viewer also serves as a palette from which users can choose the relations with which they want to work or explicitly select a data value to follow. Following a data value is one way to request a data walk. As the user works with these examples, modifying the query graph, the examples displayed change. The associated mapping also changes, and these changes are reflected both in the source table viewer 1605, and in the target viewer 1600. When a data walk or data chase results in several alternative mappings, new examples are created to represent those alternatives. One of the new examples is chosen by system 10 as the new positive example representing the “current mapping”, and the other examples are changed to be negative.

[0156] When multiple mappings are possible, system 10 orders them from most likely to least likely, using simple heuristics related to path length, least perturbation to the current active mapping, etc. The user can rotate through mappings or explicitly select a examples as positive in order to test the effects of different mappings.

[0157] System 10 ensures that the active mapping and the mapping examples 1610 through 1630 in the active workspace 1605 are all synchronized. Changes to any of them are automatically reflected in the others. In addition, the positive examples displayed in the target viewer 1600 are always the data produced by the current mapping. Consequently, users are able to explore the source data and its linkages through both the data and the schema at the same time, seamlessly. Further, and perhaps more importantly, system 10 helps the user understand the results of the mappings being formed and allows the user to verify that the transformations that result are what was intended.

[0158] The system 10 shows one or more example-tuples per mapping, as described previously. The displayed tuples are selected from a set of tuples obtained through a query to the source 205 database. In addition to these tuples, an extension to system 10 can be provided that shows the size of the tuple set as an integer number. This number appears in a separate column. There is one such number for each type of example for each mapping, i.e., there is one such number for the standard example tuples of each jointerm, and one such number for the set of filtered out tuples, and one such number for each set of tuples representing a different joinpath.

[0159] By seeing the amount of data that an example exemplifies, the user is able to gauge the effect and necessity of including/excluding certain mappings. For example, if an example-tuple represents a set of only 2 or 3 tuples, it is likely that these tuples are exceptions and should not be included in a mapping. However, if the example represents a significant portion of the available data, a user might want to include this data in the mapping (if it is not already included). Metaphorically speaking, knowing tuple set sizes gives users a better feeling for the data and the mapping.

[0160] The tuple set sizes for each jointerm and each example can be found by simply executing a query. From the result of this query, the system 10 chooses one or more example tuples. System 10 counts the number of tuples in this result and displays this number. System 10 describes the use of sample databases to increase performance of the system. Thus, the query result size will only reflect the portion of the sample database. System 10 multiplies this number with the inverse of the sampling ratio to find an approximation of the true number reflecting the portion of the original database. As an alternative, an efficient query can be constructed against the original database that only returns the number of tuples and not the entire result tuple set

[0161] It is to be understood that the specific embodiments of the invention that have been described are merely illustrative of certain application of the principle of the present invention. Numerous modifications may be made to the data-driven understanding and refinement of schema mappings invention described herein without departing from the spirit and scope of the present invention. Moreover, while the present invention is described for illustration purpose only in relation to mapping data from one database to another, it should be clear that the invention is applicable as well to any collection of data or databases accessible either through an internet or intranet connection.