Patent Description:
Recently, in a broader trend known as "self-service data preparation," non technical users such as business analysts (e.g., in Excel or Tableau) increasingly need to manipulate data and perform tasks like data transformation. However, unlike expert users, these non-technical users lack the expertise to write programs. Democratizing data transformation for the non-technical users (e.g., without asking them to write code) has become increasingly important.

In response to this demand, "transform-by-example" (TBE) paradigm was developed for data transformation. In a TBE system, users provide a few paired input/output examples to demonstrate a desired transformation task. The TBE system would then search for programs consistent with all given examples, from a predefined space of candidate programs. This has led to a fruitful line of research on TBE, advancing the state-of-the-art and producing real impacts on commercial systems.

<FIG> illustrates an example spreadsheet <NUM> that provides a TBE feature called "Add-Column-From-Examples. " The example spreadsheet has an "Input" column <NUM> on the left with a list of date-time strings. In this case, a user invokes the TBE feature, and enters two output examples (<NUM>-<NUM>-<NUM> and <NUM>-<NUM>-<NUM>) in the "Custom" column <NUM> on the right, and demonstrates a desired transformation for the corresponding input values. The TBE system then synthesizes a transformation program consistent with the two given input/output examples, which is shown within the transformation definition field <NUM>. The TBE system invokes multiple functions, including Text. Combine, Date. ToText, etc. Furthermore, a preview of the output for remaining values may be shown as represented within the Custom column <NUM> underneath the two output examples (see region <NUM>), which can help non-technical users to verify the correctness of the transformation.

While the TBE paradigm clearly helps non-technical users in spreadsheet environments, the need for users to manually identify columns for transformation programs, and then enter input/output examples, still burdens users in many applications.

<CIT> discloses a system that provides an intuitive way for merging or joining data from different datasets. The system may provide graphical interfaces to enable a user to combine or join datasets identified as having a relationship. In at least one embodiment, the system can determine options for joining datasets, such as by a left join, right join, or outer join. A graphical interface may display a visual representation to illustrate options for joining datasets based on identifying a relationship between the data sets. The representation may further illustrate one or more types of joins and information about the data, such as rows where data may be joined based on the type of join function for the relationship by columns. The visual representation may indicate where the datasets can be joined, such that they are not overlapping.

This Summary is provided to introduce a selection of concepts in a simplified form that is further described below in the Detailed Description.

According to an aspect of the present invention there is provided a computing system according to claim <NUM>. Optional features are defined by the dependent claims.

The principles described herein disclose a new transform-by-pattern (TBP) system (hereinafter may also be referred to as "the system") that can proactively suggest relevant TBP programs based on input/output datasets without requiring users typing in examples. The embodiments described herein are related to systems and methods for generating a plurality of TBP programs and/or automatic transformation of data by patterns using the generated plurality of TBP programs. The process of generating TBP programs can be performed offline at the service provider's site. Once the TBP programs are generated, they can then be made available online to users for automatic transformation of user data.

Each TBP program includes a combination (e.g., a triple) of a source pattern, a target pattern, and a transformation program that is configured to transform data that fits into the target pattern into data that fits into the source pattern. When a source dataset and a target dataset are received, the system identifies a subset of the source dataset (e.g., a column of the source dataset) and a subset of the target dataset (e.g., a column of the target dataset) as related data. Based on the identified related data, the system identifies one or more applicable TBP programs amongst the plurality of TBP programs. A TBP program is applicable to the related data, when at least one data unit of the subset of the source dataset (e.g., a row of the column of the source table) fits into the source pattern of the TBP program, and at least one data unit of the subset of the target dataset (e.g., a row of the column of the target table) fits into the target pattern of the TBP program. The system then suggests or applies the one or more applicable TBP programs to the user.

In some embodiments, the applying the one or more TBP programs includes selecting one of the one or more applicable TBP programs, and using a transformation program of the selected TBP program to automatically transform the subset of the target data to transformed data. The transformed data may include (are but not limited to) (<NUM>) a transformed subset of the target dataset that fits into the source pattern of the selected TBP program, (<NUM>) a transformed target dataset including the transformed subset of the target dataset, and/or (<NUM>) an integrated dataset including the source dataset and the transformed target dataset.

There are many ways that the system can learn or generate the plurality of TBP programs. In some embodiments, the system is configured to learn TBP programs from TBE query logs that contains users input and output datasets. Based on the users input and output datasets, one or more TBP programs may be learned or identified. For each of the identified one or more TBP programs, at least a pair of user input dataset and user output dataset fit into a respective source pattern and target pattern of the TBP program, and a corresponding transformation program of the TBP program is configured to transform the user input dataset into the user output dataset.

In some embodiments, the system is configured to learn or generate TBP programs from related datasets. Such related datasets may be obtained from various sources, such as query logs of a search engine and/or intra-wiki links. For example, a same search query may generate many pages of results, including many related tables. As another example, wiki pages (e.g., Wikipedia pages) include many intra-wiki links, each of which points to another related wiki page. These related pages linked by intra-wiki links may contain related tables. The related tables from search results and/or intra-wiki links can be obtained by crawling search results and/or wiki pages.

Once the related datasets are obtained, the system first pairs two subsets (i.e., a first subset of dataset and a second subset of dataset) of the related datasets. The first subset of dataset and the second subset of dataset may be from a same dataset or different dataset of the related datasets. The system then links one or more data units of the first subset with one or more units of the second subset. Each of the one or more data units of the subset is linked with one of the one or more data units of the second subset. The system then identifies one or more TBP programs that are applicable to the linked data units of the first subset and second subset. Each of the one or more TBP programs is applicable to transform the linked data unit of the first subset to the corresponding linked data units of the second subset.

In some embodiments, an existing TBE system may also be leveraged to identify the applicable transformation programs from the related datasets obtained from resources that are different from user queries. For example, the identifying the one or more transformation programs may include inputting the linked data units of the first subset and the second subset into a TBE system as one or more paired input/output examples to cause the TBE system to generate the one or more transformation programs.

Furthermore, the system may also identify one or more first patterns. For each of the one or more first patterns, at least one data unit of the first subset fits into the corresponding first pattern. Similarly, the computing system also identifies one or more second patterns; and for each of the one or more second patterns, at least one data unit of the second subset fits into the corresponding second pattern. For each of the one or more transformation programs, the one or more first patterns, and/or the one or more second patterns, a candidate TBP program can be formed. Each candidate TBP program includes a corresponding first pattern, a corresponding second pattern, and a corresponding transformation program. A large number of candidate TBP programs may be generated through this process.

From these candidate TBP programs, the system may then identify the suitable TBP programs. In some embodiments, for each candidate TBP program, the system applies corresponding TBP program to multiple pairs of source data units and target data units to generate a coverage score and/or an accuracy score. The coverage score indicates an applicability rate of the candidate TBP program. The accuracy score indicates an accuracy rate of the candidate TBP program. When the coverage score and/or the accuracy score is greater than a predetermined threshold, the candidate TBP program is then identified as a suitable TBP program.

In some embodiments, the system may further identify high-quality TBP programs amongst the candidate or suitable TBP programs. In some embodiments, the system uses the existing TBP programs to generate a directed graph. Each first pattern or second pattern of the TBP programs corresponds to a vertex of the directed graph, and each transformation program of the TBP programs corresponds to a directed edge.

Based on the directed graph, the computing system can then determine whether one or more special relationships exist amongst the TBP programs based on the graph and identify one or more high-quality TBP programs based on the determined one or more special relationships. The one or more special relationships include (but are not limited to) (<NUM>) a lossless inverse relationship between two TBP programs, and/or (<NUM>) a triangular equivalence relationship amongst three TBP programs. When a lossless inverse relationship between two TBP programs exists, the computing system identifies each of the two TBP programs as a high-quality TBP program. Similarly, when a triangular equivalence relationship amongst three TBP programs exists, the computing system identifies each of the three TBP programs as a high-quality TBP program.

In some cases (e.g., when a high accuracy (e.g., near <NUM>%) is required), the system may select a predetermined number of top high-quality TBP programs and send the selected top high-quality TBP programs to a human curator to verify. For each of the predetermined number of high-quality TBP programs, the system may then receive and record a label from the human curator, indicating whether the corresponding high-quality TBP program is correct or incorrect.

Accordingly, the principles described herein are capable of systematically harvesting TBP programs (including high-quality TBP programs) using available data resources. The harvested TBP programs can then be used to perform many data management tasks (e.g., auto-unify, auto-repair, etc.) automatically without any or with very little human input.

The principles described herein disclose a new transform-by-pattern (TBP) system that can proactively suggest relevant TBP programs based on input/output data patterns (without users typing in examples). The embodiments described herein are related to systems and methods for generating a plurality of TBP programs and/or automatic transformation of data by patterns using the generated plurality of TBP programs. The process of generating TBP programs can be performed offline at the service provider's site. Once the TBP programs are generated, they can be made available online to users for automatic transformation of user data.

Each TBP program includes a combination (e.g., a triple) of a source pattern, a target pattern, and a transformation program that is configured to transform data that fits into the target pattern into data that fits into the source pattern. When a source dataset (e.g., a source table) and a target dataset (e.g., a target table) are received, the system identifies a subset of the source dataset (e.g., a column of the source table) and a subset of the target dataset (e.g., a column of the target table) as related data. Based on the identified related data, the system identifies one or more applicable TBP programs amongst the plurality of TBP programs. A TBP program is applicable to the related data, when at least one data unit of the subset of the source dataset fits into the source pattern of the TBP program, and at least one data unit of the subset of the target dataset fits into the target pattern of the TBP program. The system then suggests or applies the one or more applicable TBP programs to the target dataset.

<FIG> illustrates an example TBP system <NUM>, including a TBP program generator <NUM>, a TBP selector <NUM>, and a data transformer <NUM>. The TBP program generator <NUM> obtains various sources <NUM>, including (but not limited to) user query logs of TBE systems, search query logs of search engines, intra-wiki links, and uses these resources <NUM> to generate multiple TBP programs <NUM>. Each TBP program includes a combination (e.g., a triple) of a source pattern Ps, a target pattern Pt, and a transformation program T, denoted as (Ps, Pt, T). The generated TBP programs <NUM> are then used by the TBP selector <NUM> to automatically select one or more applicable TBP programs based on the input source dataset <NUM> and target dataset <NUM>.

In some embodiments, the TBP selector <NUM> automatically select one best applicable TBP program and send the selected TBP program to the data transformer <NUM>, which, in turn, automatically transform target data <NUM> into transformed data <NUM>. In some embodiments, the TBP selector <NUM> may recommend the selected one or more applicable TBP programs to a user <NUM> via a user interface <NUM>, the user <NUM> can then manually select one of the recommended TBP programs to cause the data transformer <NUM> to transform the target dataset <NUM> to the transformed data <NUM>. The transformed data <NUM> may include (but are not limited to) (<NUM>) a transformed subset of the target dataset that fits into the source pattern of the selected TBP program, (<NUM>) a transformed target dataset including the transformed subset of the target dataset, and/or (<NUM>) an integrated dataset including the source dataset and the transformed target dataset.

The TBP programs <NUM> may be stored in a data structure (e.g., a table) at a service provider's site or in a cloud. <FIG> illustrates an example table <NUM> that stores a list of TBP programs. For example, the first row TBP-<NUM> corresponds to a TBP program with source pattern Ps: <letter>{<NUM>}. <digit>{<NUM>}, <digit>{<NUM>}" and target pattern Pt: "<digit>{<NUM>}-<digit>{<NUM>}-<digit>{<NUM>}", and a corresponding transformation program T is deserialized in the last column of this row.

<FIG> illustrate an example source table 300A and an example target table 300B, which may correspond to the source dataset <NUM> and target dataset <NUM> of <FIG>. Each of the source table 300A and target table 300B contains telemetry information, such as time-stamp, cellular-device-numbers, geo-coordinates. As is often the case in the real world, the source table 300A and the target table 300B are formatted differently, because the data may come from different versions of programs or devices. Such two datasets, each of which is in a different format, often need to be integrated into a same format and/or into a single table. Thus, transformation is required to unify or standardize the data in different formats. Currently, when such a transformation is required, data engineers often need to write ad-hoc transformation scripts for each identified incompatibility issue. Alternatively, the user needs to manually enter a few input/output examples into a TBE system to cause a TBE system to transform a target column in the target table based on the entered examples.

The TBP selector <NUM> described herein solves the above-mentioned problem by automatically selecting one or more applicable TBP programs from a repository of TBP programs, like that illustrated in <FIG>. The data transformer <NUM> can then automatically transform the columns in the target table 300B into the formats of the corresponding columns in the source table 300A, using a selected TBP program. For example, R. timestamp and S. timestamp in <FIG> need to be merged or unified. Based on the patterns of values in these two columns, it can be suggested that TBP-<NUM> in table <NUM> is to be used, because TBP-<NUM>'s Ps = "<letter>{<NUM>}. <digit>{<NUM>}, <digit>{<NUM>}" and Pt="<digit>{<NUM>}-<digit>{<NUM>}-<digit>{<NUM>}" match R. timestamp and S. timestamp in <FIG>, respectively. As such, the TBP selector <NUM> is capable of proactively suggesting an applicable TBP program for transformation.

Similarly, Ps and Pt of TBP-<NUM> and TBP-<NUM> in table <NUM> of <FIG> match (S-phone, R-phone) and (S-coordinates, R-coordinates) in <FIG>, respectively. The TBP selector may suggest that two additional transformation programs can also be performed. Notably, TBE requires paired examples and is clearly burdensome for such scenarios. Unlike a TBE system, the TBP system described herein can automatically identify an applicable TBP program without any user input of examples.

Additionally, the TBP selector <NUM> and data transformer <NUM> can also help to identify and fix inconsistent data values in tables. <FIG> illustrate many real issues in tables that can be identified and fixed by the TBP selector <NUM>, using the TBP programs shown in table <NUM> of <FIG>. For instance, in <FIG>, the TBP selector <NUM> can detect that values in the Date column have two distinct patterns: "<digit>{<NUM>}-<digit>{<NUM>}-<digit>{<NUM>}" (e.g., "<NUM>-<NUM>-<NUM>") and "<letter>+ <digit>{<NUM>}, <digit>{<NUM>}" (e.g., "January <NUM>, <NUM>"). These two patterns would match Ps and Pt of a TPB program in table <NUM>, indicating potential data inconsistency. The system can bring this to the user's attention, and propose fixes by applying the corresponding T (e.g., transforming "<NUM>-<NUM>-<NUM>" to "June <NUM>, <NUM>").

Further, the TBP system is not only applicable to transforming formats of dates, but also applicable to diverse types of transformation programs, including data in different languages (e.g., Spanish, Chinese, etc.) and different domains (e.g., chemical, financial, etc.). For example, <FIG> also illustrate examples of data inconsistencies that require transformation programs in languages other than English. Each of these inconsistencies in <FIG> can also be addressed by the TBP selector <NUM> and data transformer <NUM> in a similar manner. For example, the issue in <FIG> is fixable by TBP-<NUM> in table <NUM>, and the issue in <FIG> is fixable by TBP-<NUM> in table <NUM>, so on and so forth.

The experiments and evaluations performed by inventors suggest that the TBP system described herein not only can detect and fix thousands of real issues like those shown in web page tables across many languages (as illustrated in <FIG>), but also can auto-detect and repair data inconsistencies and format issues for non-technical users working on spreadsheet data (e.g., Microsoft Excel).

As briefly discussed above, the TBP program generator <NUM> can learn or generate many high-quality TBP programs via various methods and resources. Additional details of how the TBP programs can be learned or generated will now be discussed. In some embodiments, the query logs of a TBE system may be leveraged. Some TBE systems (such as Transform-Data-by-Example (TDE) system of Microsoft) can be used to obtain telemetry data for over half a million unique TBE tasks submitted by users. When users input/output data sets can be fully logged, the system is capable of identifying common combinations (e.g., input-data-pattern, output-data-pattern, and transformation program), which are likely good TBP programs.

However, in many situations (e.g., due to privacy laws or internal product policies), users' input/output data sets may not be fully logged. In such a case, alternative or additional approaches may be implemented to learn or generate TBP programs. In some embodiments, TBP programs may be learned from a large collection of related tables. For example, table columns with related content may be automatically "linked" together, and content redundancy can be used to "learn" common transformation programs.

<FIG> illustrates an example architecture of the TBP program generator <NUM>, which may correspond to the TBP program generator <NUM> of <FIG>. The TBP program generator <NUM> includes a pairing and linking module <NUM> (hereinafter also referred to as "pairing module"), a program learner <NUM>, and an optimizer <NUM>. The pairing and linking module <NUM> has access to a plurality of related datasets <NUM>. The plurality of related datasets <NUM> may be obtained from query logs <NUM> of search engine(s), intra-wiki links <NUM>, and/or other resources <NUM> (e.g., user content).

The pairing module <NUM> then pairs subsets of the related datasets and links the data units between the related subsets. For example, when the related datasets may be related tables, the pairing module <NUM> is configured to pair the related tables, related columns, and link the rows between the related columns. These related rows in the linked columns <NUM> are then fed into the program learner <NUM>. The program learner <NUM> may then leverage a TBE system <NUM> to generate patterns that represent the columns and generate transformation programs that are applicable to the linked columns. The generated patterns and transformation programs are then enumerated as combinations (e.g., triples) <NUM>, each of which includes a source pattern, a target pattern, and a transformation program. These enumerated combinations <NUM> are the candidate TPB programs. The candidate TBP programs <NUM> are then fed into the optimizer <NUM> to identify suitable TBP programs and/or high-quality TBP programs.

In some cases, high accuracy (e.g., near <NUM>% accuracy) is required. In such a case, the optimizer <NUM> may also include a program selector <NUM> that selects a predetermined number of high-quality TBP programs and sent the selected TBP programs to human curator(s) <NUM>. The human curator(s) <NUM> may verify each of the predetermined number of high-quality TBP programs and labels each of them as correct or incorrect. The optimizer <NUM> may then update its depository of TBP programs based on the labels generated by the human curator(s) <NUM>.

As briefly described above, search engine query logs <NUM> and/or intra-wiki links <NUM> may be used to obtain related tables. Additional details of how the pairing module <NUM> may use search engine query logs <NUM> and/or intra-wiki links <NUM> to identify related tables, pair related columns and/or link related rows will be further discussed below with respect to <FIG>.

Search engine query logs may be leveraged to obtain related tables, because search result pages returned in a search engine for the same keyword query often contain related tables. To leverage search results, query logs <NUM> of one or more commercial search engines may be accessed. Amongst all the queries, the table-intent queries may be identified. A table-intent query is a data-seeking query, such as "list of U. presidents", "list of national parks", "list of chemical elements", etc. The identifying of the table-intent queries may be performed by a production classifier. There may be a large number of table-intent queries (e.g., several millions) that can be identified. The obtained table-intent queries are denoted by Q.

In some embodiments, for each query q ∈ Q, the pairing module <NUM> may retrieve some or all web tables in the top several (e.g., top <NUM>) pages returned by the search engine, denoted by Tq. Tq contains tables related to query q. For example, <FIG> illustrates a set of example tables that are retrieved for the query "list of U. presidents. " Such tables Ta can then be paired to produce table-pairs PQ = {(T,T')|T ∈ Tq, T' ∈ Tq, T ≠ T', q ∈ Q}.

Further, for a given pair (T, T') ∈ PQ, the pairing module <NUM> also generates row-level "links" between T and T'. For example, the first row of the top-left table of <FIG> corresponds to the first row of the top-right table, etc. In an ideal setting, such row-level links can be obtained by equi-join on key-columns.

However, when values are coded or formatted differently between tables, equi-join may fail. As illustrated in <FIG>, the names of presidents are formatted differently in different tables, which would cause equi-join to fail. To solve the problem of the format variations in the key-columns (e.g., columns of the names of presidents in the tables of <FIG>), an existing auto-join system may be leveraged to automatically identify join relationships.

In some cases, given (T, T') ∈ PQ, two left-most non-numeric columns from T and T' are likely include key columns. Thus, the two left-most non-numeric columns from T and T' are taken to invoke the "auto-join" to find possible joins (or linked rows). For example, the two tables at the top of <FIG>, a j oin-program may be inferred to link values of "Washington, George" and "George Washington" together by (<NUM>) splitting names from the first table by comma (producing an array ["Washington", "George"]); (<NUM>) flipping and concatenating the two components with an empty space (producing "George Washington"). Results from this join-program on the "Name" column in the left table produces {"George Washington", "John Adams",. }, which can then be equi-joined with the right table, producing <NUM>:<NUM> joins for most rows.

In some cases, the left-most non-numeric column of a table may not be a key column. In such a case, each column of the first table and each column of the second table is paired. The relationship between each pair of columns is then identified. For example, for the top two tables in <FIG>, (C, C') column pairs such as (Name, Date-of-birth), (#, Date-of-birth), (Born, Date-of-birth), etc. may be produced. Similarly, this process may repeat to allow joining/linking of rows between other table pairs in <FIG>.

The tables in <FIG> are merely example set of related tables that can be found from search engine query logs. Many additional related tables may be identified from the search engine query logs. This process may repeat on those additional related tables to produce a large number (e.g., many million) of column pairs. For each table pair (T, T') ∈ PQ that is now linked at a row-level, pairs of columns can then be enumerated in (T, T'), written as CQ = {(C, C')|(T, T') ∈ PQ, C ∈ T, C' ∈ T'}.

Alternatively, or in addition, the pairing module <NUM> may also leverage intra-Wiki cross-language links to pair columns. Wiki pages have extensive intra-Wiki links pointing to other related Wiki pages. Wiki is a piece of server software that allows users to freely create and edit Web page content using any Web browser. Wiki supports hyperlinks and has a simple text syntax for creating new pages and intra-Wiki links between internal pages on the fly. A special form of the intra-Wiki links is the cross-language links.

<FIG> illustrates example cross-language links on a wiki page 700A related to "list of U. presidents. " The wiki page 700A includes multiple cross-language links, each of which points to a similar page written in a different language. As illustrated in <FIG>, the cross-language links point to similar pages written in <NUM> other languages.

Each of such wiki page p, containing cross-language links, has a list of links on the left side-bar pointing to wiki pages with the same content as p but written in other languages. Many wiki pages from a crawl can be parsed to identify many cross-language links to produce Llink = {(p, p')} that records all pairs of page p, p' linked by cross-language links, from which the system can again produce pairs of related tables. Pwiki = {(T, T')|T ∈ p, T' ∈ p', (p, p') ∈ Llink}. Each produced pair (T, T') will likely have the same content in different languages.

<FIG> illustrates several example pages, each of which is linked by one of the cross-language links of <FIG>. As shown in <FIG>, each table has the same content in different languages, including English, Chinese, Spanish, and German.

Furthermore, given table pairs (T, T') ∈ Pwiki, cross-language links can then be leveraged for a second time to identify row-level links between (T, T'). Specifically, for each table in a given language (e.g., English, Chinese, etc.), the presidents' names are all links pointing to Wiki entity pages of these presidents in that same language. For example, the first row of the top two tables in <FIG> links to the Wiki entity page of "George Washington" in English and Chinese, respectively, denote as <MAT> and <MAT>. These two pages <MAT> and <MAT> are again linked by cross-language links, or <MAT>, which allows the paring module <NUM> to determine that the two first rows should be linked together. Similarly, links for other rows can also be produced, as shown in dotted lines in <FIG>.

The pairing module <NUM> may focus on language-pairs between English and the other languages (e.g., en-es, en-de, etc.). The pairing module <NUM> may repeat this process and produce a large number (e.g., several million) of table pairs across languages. Similarly, from Pwiki, paired columns can again be enumerated as Cwiki = {(C, C')|(T, T') ∈ Pwiki, C ∈ T, C' ∈ T'}, (values in (C, C') are paired based on two-level links). Example of Cwiki include pairs of different "time-in-office" columns shown in <FIG>. As described above, another large set (e.g., millions) of column pairs Cwiki may be obtained from intra-Wiki links.

In addition to columns in related tables, in some cases, column pairs within a same table may also have programmatic relationships. Each of <FIG> illustrates an example tables 800A and 800B, each of which includes related columns. Such column pairs extracted from a same table can be represented as CT = {(C, C')|T ∈ T, C ∈ T, C' ∈ T, C ≠ C'}, where T is the corpus of many web tables. Since such column-pairs are from the same table, these column-pairs are already linked at a row-level. Such a method can also generate a large number of column pairs (e.g., over <NUM> billion).

These column pairs (C, C'), generated from the above-described process (which may be denoted by C = CQ ∪ Cwiki ∪ CT ), may then be populated into a table. <FIG> illustrates an example table <NUM> that records multiple input columns (C) of a target table and output columns (C') of a source table. As illustrated in table <NUM>, values in C and C' may be ordered based on row-level links from the previous step. Also, not all (C, C') column-pairs exhaustively enumerated have programmatic relationships. For example, CCT-<NUM> includes a column pair (name, date of birth). The column "name" and the column "date of birth" does not have any programmatic relationship. Such column pairs may simply be ignored.

Given the paired-columns from the resulting column pairs generated from the above-described process, the program learner <NUM> can then invoke a TBE system <NUM> to find out whether there are any programmatic relationships.

The TBE system <NUM> may be capable of indexing and leveraging a collection of functions crawled from code deposits (e.g., github) to synthesize complex programs. <FIG> illustrates an example process <NUM> of how a TBE system <NUM> (e.g., TDE of Microsoft) may synthesize a program that can transform each value in the column "Born" <NUM> (shown on the left) to match a corresponding value in the column "Date of birth" <NUM> (shown on the right).

In this example, the TBE system <NUM> identifies a function in its index called DateTime. Parse(String) as a promising candidate and invokes the function with each input value in "Born" as a parameter (e.g., DateTime. Parse("<NUM>/<NUM>/<NUM>"). For each input value, invoking DateTime. Parse(String) produces a DateTime object, which has attributes, Year, Month, and Day that are populated with relevant values. These values can be seen in the table <NUM> of <FIG>. From the table <NUM>, the system can then leverage program-synthesis techniques to "piece-together" relevant parts to exactly match the target output for every single input value. The pieced-together parts are shown in table <NUM> of <FIG>. Let ret be the object returned from invoking DateTime. Parse(String), A synthesized program T perform the following steps:.

Example source code <NUM> corresponding to the above synthesized program (also referred to as Listing <NUM>) is shown in <FIG>.

Similarly, for each column pair (C, C'), a program T may be synthesized or learned. The learned T is populated in the corresponding entry in the table <NUM> of <FIG>. For example, listing <NUM> is populated for each of CCT-<NUM> and CCT-<NUM>. The collection of (C, C', T) combinations <NUM> is referred to as TCCT = {(C, C', T)}, which is then fed into the optimizer <NUM>.

The optimizer <NUM> is tasked to identify suitable TBP programs and/or high-quality TBP programs amongst the candidate TBP programs. <FIG> illustrates an example process <NUM> for generating TBP programs from the column pair combinations TCCT = {(C, C', T)}. To identify candidate TBP programs amongst the collection of TCCT = {(C, C', T)} combinations, pattern-profiling may be performed. Various pattern languages (such as regex pattern language) may be implemented to enumerate these patterns.

As illustrated in <FIG>, given a single combination (C, C', T) <NUM>, there are many possible patterns P(C) <NUM> and P(C') <NUM> for C and C', respectively. In some embodiments, for a given column C, all or multiple possible patterns P1a <NUM>, P1b <NUM> may be enumerated. The ellipsis <NUM> represents that there may be any number of possible patterns P being enumerated. Similarly, for a given column C', all or multiple possible patterns P'2a <NUM>, P'2b <NUM> may be enumerated. The ellipsis <NUM> represents that there may be any number of patterns P' being enumerated.

For each P in P(C) and each P' in P(C'), a TBP program (P, P', T) may be enumerated as a candidate TBP program. For example, given patterns P1a <NUM> and P'2a <NUM>, a candidate TBP program (P1a, P'2a, T) <NUM> may be enumerated. Similarly, given patterns P1a <NUM>, P'2b <NUM>, a TBP program (P1a, P'2b, T) <NUM> may be enumerated. This process may repeat until all the candidate TBP programs <NUM> are enumerated.

However, not all patterns in P(C) <NUM> and/or P(C') are equally suitable for TBP. One of the key challenges of the optimizer <NUM> is to pick the right P ∈ P(C) and P' ∈ P(C'), so that the resulting (P, P', T) becomes a suitable TBP program.

For example, considering row CCT-<NUM> in the table <NUM> in <FIG> again, the input column C1 = {"<NUM>/<NUM>/<NUM>", "<NUM>/<NUM>/<NUM>",. }, the possible patterns that can be generated in P(C1) include (but are not limited to): P1a= "<digit>{<NUM>}/<digit>{<NUM>}/<NUM><digit>{<NUM>}"; or an even more general P1b="<digit>{<NUM>}/<digit>{<NUM>}/<digit>{<NUM>}"; or an even more general P1c = "<num><symbol><num><symbol><num>", among many other options. Here "<digit>" Stands for [<NUM>-<NUM>], "<num>" stands for both integer and floating-numbers, "<symbol>" Stands for any punctuation, and "<letter>" Stands for [a-z, A-Z].

Notably, the ideal way to generalize CCT-<NUM> into a TBP program is to use the second option P1b="<digit>{<NUM>}/<digit>{<NUM>}/<digit>{<NUM>}" to describe column C1, because it would match other similar columns for which the same transformation in Listing <NUM><NUM> is also applicable (e.g., column C4 of CCT-<NUM> in the table <NUM>). In comparison, using a less general pattern like P1a would lead to reduced applicability, and using a more general pattern like P1c would trigger the system to apply the program to certain non-applicable columns (e.g., phone numbers like <NUM>-<NUM>-<NUM>), thus produce false-positives. As such, only P<NUM>b ∈ P(C<NUM>) generalizes values in C1 into the right level for TBP, because it strikes the right balance between generality and accuracy in the context of this TBP program.

Similarly, many patterns P(C'i) can be generated in CCT-<NUM>, such as P2b="<letter>+<digit>{<NUM>},<digit>{<NUM>}", which generalizes at the right level and is more suitable choice for this TBP program.

While it is hard to know what candidate TBP programs are suitable by only looking at one (C, C', T) combination, it would become possible when a large collection of combinations or triples TCCT <NUM> is available. For example, for CCT-<NUM>, assuming P<NUM>b ∈ P(C<NUM>) and P2b ∈ P(C'<NUM>) are picked, and a candidate TPB program TBP1b=(P1b, P2b, Listing-<NUM>) is produced. If the candidate TPB1b is applied across combinations in TCCT, additional evidence can be found to prove that TPB1b is good, because in CCT-<NUM>, C<NUM> and C'<NUM> are also consistent with P1b and P2b. Furthermore, the program T in CCT-<NUM> is also Listing-<NUM>, suggesting that TPB1b is also applicable to CCT-<NUM>. As such, the system can determine that TPB1b is a suitable program with many such combinations in TCCT.

Assuming a large number of combinations (C, C', T) ∈ TCCT <NUM> are found, and for each of the large number of combinations <NUM>, P1b matches C, and P2bmatches C'. Intuitively, these are the column-pairs for which TBP1b could trigger. If it is found that majority of the total combinations have the same program Listing-<NUM>, the finding would indicate that TBP1b has a good coverage. For example, if a total number of combinations may be <NUM>, and <NUM> of these <NUM> combinations have the same program Listing-<NUM>, the accuracy would be <NUM>/<NUM>, which indicates that TBP1b has high coverage and high accuracy.

A second candidate TBP1a= (P1a, P2b, Listing-<NUM>) uses a less general pattern P1a= "<digit>{<NUM>}/<digit>{<NUM>}/<NUM><digit>{<NUM>}". If it is found that TBP1a is only applicable to <NUM> combinations amongst the <NUM> combinations, the finding suggests that TBP1a has low coverage. A third candidate TBP1c= (P1c, P2b, Listing-<NUM>) uses a more general pattern P1c = "<num><symbol><num><symbol><num>". The two patterns P1c and P2b are applied to a large number of column pairs (C, C') in TCCT. If it is found that TBP1c is only applicable to <NUM> pairs amongst <NUM> pairs, the finding suggests that TBP1c has the same coverage <NUM>, but low accuracy (<NUM>/<NUM>).

The above examples show that a global analysis of TCCT can help identify suitable patterns for TBP. The coverage of a TBP program (P, P', T) on a given TCCT may be denoted as Cov(P, P', T), which may be defined as Equation (<NUM>) below: <MAT>.

Cov(P, P', T) represents the number of combinations in TCCT, where P matches C (P ∈ P(C)), P' matches C' (P' ∈ P(C')), and T is applicable.

The accuracy of a TBP program (P, P', T) given TCCT may be denoted as Acc(P, P', T), which may be defined as Equation (<NUM>) below:
<MAT>.

Acc(P, P', T) measures the fraction of column pairs matching P and P', for which T is actually applicable.

Referring to <FIG> again, for each candidate TBP program1240, a score <NUM>, including (but not limited to) a coverage score <NUM> Cov(P, P', T) and/or an accuracy score <NUM> Acc(P, P', T), can be determined. Based on the determined score(s) <NUM>, a suitable TBP program <NUM> may then be identified. For example, in some embodiments, a TBP program that has the coverage score and/or accuracy score greater than a predetermined threshold may be identified as a suitable TBP program. In some other embodiments, a TBP program that has the highest coverage score and/or accuracy score may be identified as the suitable TBP program. Alternatively, or in addition, a combination of the coverage score <NUM> and accuracy score <NUM> may be considered to determine the suitable TBP programs. It is proven that these estimated coverage and accuracy scores are consistent with high-quality TBPs harvested from search-engine-like settings or fully available logged user data sets.

However, in some cases, the coverage scores may indicate a reasonable indicator of program popularity, but accuracy scores may indicate an inaccurate TBP. For example, when columns are auto-paired in <FIG>, the "Died" column and the "Date of birth" column would also be paired, producing a combination CCT-<NUM> shown in the table <NUM> in <FIG>. Since there is no relationship between the two columns in CCT-<NUM>, no program can be learned. However, because the columns in CCT-<NUM> have identical patterns as those in CCT-<NUM>, the patterns of the candidate TBP program may be applicable to the source column and target column, and a reasonable coverage score may be generated, even though no transformation program should be applicable.

To further solve the above-mentioned problem, a directed graph may be used to identify special relationships amongst many candidate TBP programs. The candidate TBP programs in TCCT may be modeled using a directed graph G = (V, E), where each pattern P corresponds to a vertex Vp ∈ V, and each candidate program (P, P', T) ∈ TPPT corresponds to a directed edge EPP'T ∈ E that connects vertex VP to VP'. Notably, the graph G is a directed graph because TBP programs are directional (e.g., T converts data in pattern P to pattern P', but not in the other direction).

<FIG> illustrates an example directed TBP graph <NUM> including a plurality of vertices and edges. Each vertex here corresponds to a source pattern or a target pattern, and each edge corresponds to a candidate TBP program. There can be multiple edges between vertices (making it a directed multi-graph), because multiple candidate programs may be generated between two patterns (though some of which are incorrect). In <FIG>, such incorrect programs have been omitted to avoid clutter.

The TBP graph is then used to identify special types of implicit relationships (and/or corroborations) between TBP programs to infer their quality. One type of special relationship is referred to as lossless inverse programs (also called inverse programs). The definition of inverse programs is defined as follows. Two TBP programs (P, P', T) and (P', P, T') are lossless inverse programs, if applying T on column C matching P (or P ∈ P(C)) produces T(C) of pattern P', from which applying T' produces the original input C, or T'(T(C))=C.

Inverse programs are similar in spirit to the notion of inverse-functions in mathematics, and such pairs can be denoted as (P, P', T) and (P', P, T-<NUM>). If after applying T and T' sequentially, the original input data C is obtained, it is a good indication that (<NUM>) both T and T' are lossless transformation programs (for otherwise one could not regenerate an identical C); and (<NUM>) both T and T' are likely high-quality TBP transformation programs (because of the existence of an independently generated counter-party).

In the example graph <NUM> in <FIG>, many pairs of inverse programs can be identified, such as (P<NUM>, P<NUM>, T<NUM>) and (P<NUM>, P<NUM>, T<NUM>) for geo-coordinates, and the pair (P<NUM>, P<NUM>, T<NUM>) and (P<NUM>, P<NUM>, T<NUM>) for date-time strings, among many others. It can be verified that such transformation programs are lossless, because executing T and T-<NUM> produces output identical to the input. For instance, from P<NUM> to P<NUM> and applying T<NUM>, even though some tokens are dropped (e.g., from "Sun, Dec <NUM>, <NUM>) to "<NUM>/<NUM>/<NUM>", "Sun" and "Dec" are dropped), it is still lossless because when T<NUM> is applied in the other direction, the original input can be regenerated.

Even though the simple graph of <FIG> may suggest that inverse programs can be identified as cycles of length <NUM>, in general, this is not sufficient, many two TBP programs of the form (P, P', T) and (P', P, T) may form such a cycle. Whether the inverse-relationship holds on T and T' needs to be tested on real data using the above definition.

In some embodiments, when column pairs (C, C') from TCCT for which (P, P', T) is known to hold, such knowledge can be leveraged. (P', P, T) may then be applied in the other direction, by applying T' on each C' to test whether the original C can be recovered. For each candidate pair TBP (P, P', T) and (P', P, T'), a test can be performed on TCCT to compute a success rate for inversion. The success rate is denoted by Sinv((P, P', T), (P', P, T')), which may be defined in Equation (<NUM>) below.

In some embodiments, (P, P', T) and (P', P, T) are considered to be inverse programs if the inverse relationship test holds on a large fraction of real data tested (e.g., Sinv><NUM>). When two TBP programs are inverse programs, both of the TBP programs may be deemed as high-quality TBP programs.

Another type of special relationship is triangular equivalent programs. Three programs (P, P', T), (P', P", T') and (P, P", T") are defined as triangular equivalent programs, if applying T on column C matching P (or P ∈ P(C)) produces output T(C), which is identical to applying T' followed by T" sequentially on C, or T"(T'(C))=T(C).

As illustrated in <FIG>, a triangle is formed by P5, P6, and P7. The program T67 is lossy, thus it cannot be part of inverse programs. However, applying T67 on suitable input (e.g., <NUM>:38AM, <NUM> December <NUM>) produces output (Dec. <NUM>) that is identical to applying T65 followed by T57, suggesting a triangular equivalence relationship and making it possible to corroborate the validity of the lossy T65 using other programs.

Similar to inverse-programs, each program-triple (P, P", T), (P, P', T') and (P', P", T") may be tested on column data in TCCT. The success rate of such a test is denoted as Stri, , which may be defined using Equation (<NUM>) below:
<MAT>.

In some embodiments, if the test above holds on most column pairs of a program triple from TCCT (e.g., Stri > <NUM>), the program triple may be deemed as triangular-equivalence. In such a case, all three involved TBP programs are deemed as high-quality as they can corroborate each other's validity.

Inverse programs and triangular equivalent programs are merely two examples of special relationships amongst programs. Other special relationships may exist amongst multiple programs. Such special relationships, including (but not limited to) inversion and triangular equivalence, can be used to identify high-quality TBP programs. When high accuracy of TBP programs is not required, these high-quality TBP programs can be automatically applied to the target data set to automatically transform the target dataset to fit into the pattern of the source dataset.

However, in some application scenarios, the accuracy of TBP programs is required to be close to <NUM>%. Accuracy is often especially important in settings of enterprise software. In such a case, the harvested TBP programs may be further verified by human curators. In some embodiments, human curator(s) are tasked to inspect and verify up to k high-quality programs, and label them as correct or incorrect. In such a case, the optimizer <NUM> may further include a program selector <NUM>. The program selector <NUM> is tasked to select k high-impact and high-quality TBP programs and sends the selected k TBP programs to the human curator(s). The optimizer <NUM> later receives the labels from the human curator(s), indicating whether each of the k TBP programs is correct or incorrect.

One of the key technical challenges is to select programs of high impact for human curators to verify, so that the benefit of the k labels can be maximized. To identify the high impact programs, the system may again use the graph <NUM> and start with the edges (i.e., programs) that are determined to be in inverse or triangular-equivalence relationships. Further, each edge or program has a coverage score Cov (P, P', T), indicating the number of input/output column-pairs to which the program is applicable. Generally, coverage scores capture the popularity and/or importance of a program. For example, frequently-used programs often have high coverage scores and should be manually verified first.

Furthermore, because of the relationships amongst programs, verification of one edge may have additional benefits beyond this edge. Referring to <FIG> again, in a curation setting, many edges of the graph needs to be verified, and for each of these edges, a coverage score is then determined. If a human curator can verify T<NUM> to be correct, then T<NUM> is verified implicitly due to their strong inverse relationship. Similarly, if both T<NUM> and T<NUM> are verified by a human curator as correct, T<NUM> is also likely correct because of their triangular-equivalence relationship. Also, the coverage score on T<NUM> can be obtained based on the verification result of T<NUM> and T<NUM>.

In some embodiments, the goal of the program selector <NUM> is to identify a top k edges or programs that have the highest total coverage score. Given a TBP graph G = (V, E), where each edge e ∈ E has a coverage score Cov(e). The objective is to find a subset of edges Es ⊂ E to verify, with |Es| ≤ k, such that the total coverage score of these to-be-verified programs, together with ones implicitly verified through program relationships, is maximized. This principle is denoted in a coverage-maximizing program selection (CMPS), which may be defined by the equations (<NUM>) through (<NUM>) below:
<MAT>
<MAT>
<MAT>
<MAT>
<MAT>
<MAT>.

In the above equations (<NUM>) through (<NUM>), xi indicates whether ei is selected for human verification; ym indicates whether the mth inverse relationship, denoted by Invm, has a participating edge selected for verification; zn indicates whether nth triangular equivalence relationship, denoted by Trin, has more than two edges selected or verification; and vi indicates whether ei can be treated as correct, through explicit human verification, or program relationships. All of vi, xi, ym, and zn are {<NUM>, <NUM>} binary variables, denoted in Equation (<NUM>).

The objective function in Equation (<NUM>) calculates the sum of coverage scores of all programs implicitly or explicitly verified (denoted by vi). Equation (<NUM>) ensures that at most k edges are explicitly verified by human curators. Equation (<NUM>) and equation (<NUM>) check whether enough edges in each inverse or triangular relationship are explicitly verified by human curators, and if so the corresponding ym and zn is set to <NUM>. Finally, Equation (<NUM>) checks whether ci can be verified explicitly through xi or implicitly through ym or zn.

It can be proven that the above CMPS problem is super-modular and NP-hard. It can also be proven that the CMPS problem cannot be approximated with n<NUM>/polyloglog n, and no PTAS likely exists under standard complexity theoretic assumptions. Given the hardness of CMPS problem, in the curation setting, the program selector <NUM> may resort to a heuristic method, in which at each step, the edge with maximum benefit (from explicit and implicit verification) is picked, until the budget k is exhausted.

Additional embodiments may be implemented to formulate the curation problem. In some embodiments, the coverage score of each edge is considered as a set of column-pairs as opposed to a numeric count. Because the column-pairs covered by each program or edge can overlap, this method may reduce the redundancy of verifying related programs. In yet some other embodiments, the estimated program quality may be modeled as the likelihood of the edge verified correct, in addition to using coverage scores.

<FIG> illustrates a flowchart of an example method <NUM> for automatically identifying applicable TBP programs for data transformation and/or automatically transforming data using an identified applicable TBP program. The method <NUM> includes generating a plurality of TBP programs (<NUM>) or accessing the plurality of TBP programs (<NUM>). Each TBP program includes a combination of a source pattern, a target pattern, and a transformation program that is configured to transform data that fits into the target pattern into data that fits into the source pattern. The method <NUM> also includes receiving a source dataset and a target dataset (<NUM>) and identifying a subset of the source dataset and a subset of target dataset as related data (<NUM>).

Based on the identified related data, and the plurality of TBP programs, one or more applicable TBP programs amongst the plurality of TBP programs are identified (<NUM>). A TBP program is applicable to the related data, if at least one data unit of the subset of the source dataset fits into the source pattern of the TBP program, and at least one data unit of the subset of the target dataset fits into the target pattern of the TBP program.

The method <NUM> also includes suggesting or applying at least one of the one or more applicable TBP programs (<NUM>). In some embodiments, the applying at least one of the one or more applicable TBP programs includes automatically selecting one of the at least one applicable TBP programs to the subset of the target dataset (<NUM>), automatically transform the subset of the target dataset using a transformation program of the selected TBP program (<NUM>), and presenting the transformed data to the user (<NUM>). The transformed data may include (but not limited to) (<NUM>) a transformed subset of the target dataset that fits into the source pattern of the selected TBP program, (<NUM>) a transformed target dataset including the transformed subset of the target dataset, and/or (<NUM>) an integrated dataset including the source dataset and the transformed target dataset.

<FIG> illustrates a flowchart of an example method <NUM> for generating a plurality of TBP programs, which may correspond to the act <NUM> of <FIG>. The method <NUM> includes accessing a plurality of related datasets (<NUM>). The plurality of related datasets may be obtained based on query logs of search engines and/or various wiki links. The method <NUM> also includes pairing two subsets (i.e., a first subset and a second subset) of the related datasets (<NUM>). Each of the two subsets of related datasets may be obtained from a same dataset or a different datasets. The method <NUM> also includes link at least one data unit of the first subset with at least one data unit of the second subset of the related datasets (<NUM>). Based on the linked at least one data unit of the first subset and at least one data unit of the second dataset, one or more applicable transformation programs may be identified (<NUM>). In some embodiments, an existing TBE system may be leveraged to identify the one or more applicable transformation programs. In particular, the linked at least one data unit of the first subset and at least one data unit of the second subset may be input into the TBE system as paired input/output example(s) to cause the TBE system to retrieve a transformation program based on the paired input/output example(s) (<NUM>).

The method <NUM> also includes identifying one or more first patterns for the first subset (<NUM>). At least one data unit of the first subset fits into each of the one or more first patterns. Similarly, one or more second patterns for the second subset may also be identified (<NUM>). At least one data unit of the second subset fits into each of the one or more second patterns. Based on the one or more first patterns, one or more second patterns, and one or more applicable transformation programs, a plurality of combinations may be generated (<NUM>). Each of the plurality of combinations includes one of the one or more first patterns, one of the one or more second patterns, and one of the one or more applicable transformation programs. Each combination may be a candidate TBP program.

The method <NUM> also includes determining a coverage score for each candidate TBP program, indicating the applicability of the corresponding candidate TBP program (<NUM>). For each TBP program, a coverage score may be determined by applying the corresponding candidate TBP program to multiple data units of the first subset and the second subset (e.g., all the rows of columns of tables). For each of the multiple data units, it is determined whether the TBP program is applicable. The coverage score may be determined based on the number of the data units that the transformation program is applicable. Similarly, the method <NUM> may also include determining an accuracy score for each candidate TBP program, indicating the accuracy of each candidate TBP program (<NUM>). The accuracy score measures the fraction of first and second subsets matching P and P', for which T is applicable.

Based on the coverage score and/or the accuracy score of each combination, TBP programs may be identified (<NUM>). In some embodiments, when a coverage score and/or an accuracy score of a candidate TBP program is greater than a predetermined threshold (e.g., <NUM>%), the combination is identified to be a suitable TBP program.

<FIG> illustrates a flowchart of an example method <NUM> for identifying high-quality TBP programs using a directed graph. The method <NUM> includes accessing the plurality of TBP programs (<NUM>) and generating a directed graph based on the plurality of TPB programs (<NUM>). The plurality of TBP programs may be candidate or suitable TBP programs. Each of a first pattern and a second pattern of a TBP program corresponds to a vertex of the directed graph, and each of the transformation program corresponding to a directed edge of the directed graph.

Based on the directed graph, special relationships amongst the plurality of TPB programs may be identified (<NUM>). The special relationships include (but are not limited to) lossless inverse relationships between two TBP programs (<NUM>) and/or triangular equivalence relationships among three TBP programs (<NUM>). Based on the determined special relationships, high-quality TBP programs may be identified (<NUM>). For example, each of the two TBP programs that have a lossless inverse relationship may be deemed as high quality, and each of the three TBP programs that have a triangular equivalence relationship may be deemed as high quality.

The method <NUM> may also include selecting a predetermined number of top high-quality TBP programs (<NUM>). The selected predetermined number of top high-quality TBP programs may then be sent to a human curator for verification (<NUM>). For each of the selected top high-quality TBP programs, a label, indicating the corresponding TBP is correct or incorrect, may then be received from the human curator and recorded in the repository of the TBP programs (<NUM>).

Finally, because the principles described herein may be performed in the context of a computing system (e.g., the TBP system or some component of the TBP system may be a computing system) some introductory discussion of a computing system will be described with respect to <FIG>.

As illustrated in <FIG>, in its most basic configuration, a computing system <NUM> typically includes at least one hardware processing unit <NUM> and memory <NUM>. The processing unit <NUM> may include a general-purpose processor and may also include a field-programmable gate array (FPGA), an application-specific integrated circuit (ASIC), or any other specialized circuit. The memory <NUM> may be physical system memory, which may be volatile, non-volatile, or some combination of the two. The term "memory" may also be used herein to refer to non-volatile mass storage such as physical storage media. If the computing system is distributed, the processing, memory and/or storage capability may be distributed as well.

The computing system <NUM> also has thereon multiple structures often referred to as an "executable component". For instance, memory <NUM> of the computing system <NUM> is illustrated as including executable component <NUM>. The term "executable component" is the name for a structure that is well understood to one of ordinary skill in the art in the field of computing as being a structure that can be software, hardware, or a combination thereof. For instance, when implemented in software, one of ordinary skill in the art would understand that the structure of an executable component may include software objects, routines, methods, and so forth, that may be executed on the computing system, whether such an executable component exists in the heap of a computing system, or whether the executable component exists on computer-readable storage media.

In such a case, one of ordinary skill in the art will recognize that the structure of the executable component exists on a computer-readable medium such that, when interpreted by one or more processors of a computing system (e.g., by a processor thread), the computing system is caused to perform a function. Such a structure may be computer-readable directly by the processors (as is the case if the executable component were binary). Alternatively, the structure may be structured to be interpretable and/or compiled (whether in a single stage or in multiple stages) so as to generate such binary that is directly interpretable by the processors. Such an understanding of example structures of an executable component is well within the understanding of one of ordinary skill in the art of computing when using the term "executable component".

The term "executable component" is also well understood by one of ordinary skill as including structures, such as hardcoded or hard-wired logic gates, that are implemented exclusively or near-exclusively in hardware, such as within a field-programmable gate array (FPGA), an application-specific integrated circuit (ASIC), or any other specialized circuit.

In the description above, embodiments are described with reference to acts that are performed by one or more computing systems. For example, such computer-executable instructions may be embodied in one or more computer-readable media that form a computer program product. If such acts are implemented exclusively or near-exclusively in hardware, such as within an FPGA or an ASIC, the computer-executable instructions may be hardcoded or hard-wired logic gates.

While not all computing systems require a user interface, in some embodiments, the computing system <NUM> includes a user interface system <NUM> for use in interfacing with a user. The user interface system <NUM> may include output mechanisms 1712A as well as input mechanisms 1712B. The principles described herein are not limited to the precise output mechanisms 1712A or input mechanisms 1712B as such will depend on the nature of the device. However, output mechanisms 1712A might include, for instance, speakers, displays, tactile output, holograms and so forth. Examples of input mechanisms 1712B might include, for instance, microphones, touchscreens, holograms, cameras, keyboards, mouse or other pointer input, sensors of any type, and so forth.

Embodiments described herein may comprise or utilize a special purpose or general-purpose computing system including computer hardware, such as, for example, one or more processors and system memory, as discussed in greater detail below. Such computer-readable media can be any available media that can be accessed by a general-purpose or special purpose computing system.

Computer-readable storage media includes RAM, ROM, EEPROM, CD-ROM, or other optical disk storage, magnetic disk storage, or other magnetic storage devices, or any other physical and tangible storage medium which can be used to store desired program code means in the form of computer-executable instructions or data structures and which can be accessed by a general-purpose or special purpose computing system.

Transmissions media can include a network and/or data links which can be used to carry desired program code means in the form of computer-executable instructions or data structures and which can be accessed by a general-purpose or special-purpose computing system.

Computer-executable instructions comprise, for example, instructions and data which, when executed at a processor, cause a general-purpose computing system, special purpose computing system, or special purpose processing device to perform a certain function or group of functions. Alternatively or in addition, the computer-executable instructions may configure the computing system to perform a certain function or group of functions.

Those skilled in the art will appreciate that the invention may be practiced in network computing environments with many types of computing system configurations, including, personal computers, desktop computers, laptop computers, message processors, hand-held devices, multi-processor systems, microprocessor-based or programmable consumer electronics, network PCs, minicomputers, mainframe computers, mobile telephones, PDAs, pagers, routers, switches, data centers, wearables (such as glasses) and the like.

The remaining figures may discuss various computing system which may correspond to the computing system <NUM> previously described. The computing systems of the remaining figures include various components or functional blocks that may implement the various embodiments disclosed herein as will be explained. The various components or functional blocks may be implemented on a local computing system or may be implemented on a distributed computing system that includes elements resident in the cloud or that implement aspect of cloud computing. The various components or functional blocks may be implemented as software, hardware, or a combination of software and hardware. The computing systems of the remaining figures may include more or less than the components illustrated in the figures and some of the components may be combined as circumstances warrant. Although not necessarily illustrated, the various components of the computing systems may access and/or utilize a processor and memory, such as processor <NUM> and memory <NUM>, as needed to perform their various functions.

For the processes and methods disclosed herein, the operations performed in the processes and methods may be implemented in differing order. Furthermore, the outlined operations are only provided as examples, an some of the operations may be optional, combined into fewer steps and operations, supplemented with further operations, or expanded into additional operations without detracting from the essence of the disclosed embodiments.

Claim 1:
A computing system (<NUM>) comprising:
one or more processors (<NUM>); and
one or more computer-readable media (<NUM>) having stored thereon computer-executable instructions that are executable by the one or more processors (<NUM>) to cause the computing system (<NUM>) to perform the following in response to receiving a source dataset and a target dataset:
identify a subset of the source dataset (<NUM>) and a subset of the target dataset (<NUM>) as related data;
access a plurality of Transform-by-Pattern (TBP) programs (<NUM>), each of the plurality of the TBP programs (<NUM>) comprising a combination of a source pattern, a target pattern, and a transformation program, the transformation program configured to transform data that fits into the target pattern into data that fits into the source pattern;
identify one or more TBP programs (<NUM>) that are applicable to the related data, for each of the one or more TBP programs (<NUM>), at least one data unit of the subset of the source dataset (<NUM>) fits into the source pattern of the TBP program (<NUM>), and at least one data unit of the subset of the target dataset (<NUM>) fits into the target pattern of the TBP program (<NUM>), wherein the one or more TBP programs (<NUM>) are identified based on a determination that corresponding coverage scores (<NUM>) for the one or more TBP programs (<NUM>) are greater than a predetermined threshold, and wherein the coverage scores (<NUM>) indicate applicability rates for the one or more TBP programs (<NUM>); and
apply at least one (<NUM>) of the one or more applicable TBP programs (<NUM>) to the target dataset (<NUM>) , wherein at least one of the TBP programs has been generated from a query log, and wherein applying the at least one of the one or more applicable TBP programs to the target data set includes:
selecting one of at least one applicable TBP program; and
using a transformation program of the selected TBP program to automatically transform the subset of the target data set to transformed data, the transformed data comprising an integrated data set comprising the source data set and the transformed target data set.