Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-01-22
2004-08-03
Robinson, Greta (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06772180
ABSTRACT:
FIELD OF THE INVENTION
The present invention is related to methods and apparatus for exchanging data between parties using different schemas to represent the data. More specifically, the invention is related to an apparatus and a set of processes that automatically translate between two different data representation schemas through the use one or more shared examples.
1. Background
In any applications involving the processing of data that is not centralized, one entity will have to send or receive data from other entities. The fundamental challenge is that different entities may use different schemas (or formats) to represent data. On the Internet, this data is often described using a structured markup language such as eXtensible Markup Language (or XML). The definition of the format of the data described using XML is captured by an associated Data Type Description (DTD). Consequently, the two entities may use different XML DTDs to represent the data formats of the corresponding data.
This invention describes a new solution in which the two entities, by sharing one or more examples, are able to perform the translation between the two schemas automatically.
The possible applications, in the Internet domain, include but are not limited to: EDI; search engines; content ingestion; content customization; data delivery; and data retrieval.
2. Statement of Problems With the Prior Art
There are some existing ways of solving this schema translation problem:
1. Explicit Translation Rules: In this case, translation rules between two schema are manually derived and coded (i.e., software). A new set of schema requires new translation rules. Furthermore, writing software is time consuming and expensive.
2. Standardized Schemas: In this case, both entities use a standard schema. Examples include numerous data formats such as Hypertext Markup Language (HTML), and Channel Data Format (CDF). Nevertheless, agreeing on a common schema is time consuming and difficult.
In summary, the existing techniques for solving the schema translation problem are time consuming and expensive. This does not allow them to be deployed in scenarios where the translation is required for short engagements.
ADVANTAGES & OBJECTIVES OF THE INVENTION
The present invention includes the advantages of:
1. No translation programs need to be written.
2. No standard schemas have to be agreed upon.
3. Examples may be needed anyway to explain the schemas.
An objective of this invention is to provide a mechanism for translating data between different representation schemas by automatic and simple means.
SUMMARY OF THE INVENTION
In accordance with the aforementioned needs, the present invention is directed to a method, computer program product or program storage device for software for automatically generating a translator adapted for translating data between different representation schemas using the translator.
An example of a method for data representation schema translation having features of the present invention, comprises the steps of: identifying data encoded in a first data representation schema; converting the data encoded in the first data representation schema to an encoding in a second data representation schema; and automatically generating a translator based on common data encoding, in response to the identifying and converting steps, wherein the translator is adapted for translating data between said first data representation schema and said second data representation schema.
Another example of a method for data representation schema translation having features of the present invention, comprises the steps of: identifying one or more shared examples encoded in two data representation schemas; and automatically generating a translator based on the shared examples, wherein the translator is adapted for translating data between said two data representation schemas.
One embodiment of the present invention comprises the further steps of: parsing data in said one or more shared examples into trees, each tree representing one of the data representation schemas; generating a path table for each tree, in response to the parsing step; wherein the step of automatically generating the translator comprises the step of generating a translation table from path tables generated for each tree.
In a preferred embodiment, the data representation is in the form of a tree and the same data example is encoded in the two different schemas, sA and sB. Let the example data D={x
1
,x
2
, . . . ,xi, . . . xn} be encoded as dA and dB in sA and sB, respectively. Each element xi in D, represented in schema sj, has a unique path pji from the root to xi.
We build a path conversion table T that has an entry {pAi, pBi} for each xi in D. This can be done, for example, by making a table of {xi, pAi} for dA in sA and {xi, pBi} for dB in sB. Rows of these tables with common element xi are merged to generate T.
When a new data Y={y
1
, y
2
, . . . ,yi, . . . ,ym} is encoded in sA as yA, and needs to be converted to yB represented in sB, we first compute the path pAi for each yi in Y. Then we use the path conversion table T to look up the entry with a matching path value in the first column which gives the resulting path pBi for yi in yB via the second column of T. We incrementally construct the tree for yB by adding the data item yi at path pBi in yB.
The path conversion table T acts as an automatic program for converting data between the two schemas sA and sB.
Alternatively, when the representation is in the form of a graph, a method is used to compute unique paths, for example, depth-first traversal. The depth-first traversal of a rooted graph will give us tree composed of the tree edges and the nodes, thus reducing the graph to an equivalent tree (reference “Knuth”). Other data representations can be converted to trees or graphs.
The path computed may be augmented by storing at each node along the path, its position among its siblings. This augmented path allows us to preserve ordering within siblings.
The example D, or a set of examples {D} needs to exercise each possible path p that is to be encountered in subsequent data exchanges. These paths p are the non augmented paths. Differences in augmented path can be automatically handled by using machine readable schemas sA and sB or, in the absence of schemas, using heuristics, such as defaults for repetitions of nodes (for example, the default could be that each node appears zero or more times).
Depending on the nature of the machine readable schemas sA and sB, data (format) conversions that can be deduced automatically from the two schemas, can also be added to this schema conversion process.
REFERENCES:
patent: 4680705 (1987-07-01), Shu
patent: 4951196 (1990-08-01), Jackson
patent: 5187787 (1993-02-01), Skeen et al.
patent: 5699415 (1997-12-01), Wagner
patent: 5897622 (1999-04-01), Blinn et al.
patent: 5915259 (1999-06-01), Murata
patent: 5960200 (1999-09-01), Eager et al.
patent: 6018743 (2000-01-01), Xu
patent: 6223168 (2001-04-01), McGurl et al.
patent: 6243451 (2001-06-01), Shah et al.
patent: 6253254 (2001-06-01), Erlenkoetter et al.
Li Chung-Sheng
Mohan Rakesh
Dang Thu Ann
Pannala S R
Robinson Greta
LandOfFree
Data representation schema translation through shared examples does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data representation schema translation through shared examples, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data representation schema translation through shared examples will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3308499