US6560608B1

Movatterモバイル変換

Info

Publication number: US6560608B1
Application number: US09/590,916
Authority: US
Inventors: Douglas Cameron Tomm; Donald Albert Leckie
Original assignee: Contivo Inc
Current assignee: Open Text Holdings Inc
Priority date: 2000-06-09
Filing date: 2000-06-09
Publication date: 2003-05-06
Also published as: WO2001097078A8; WO2001097078A2; AU2001224723A1

Abstract

A method and apparatus for automatically selecting a rule during the mapping process, and storing the rule independently of message type, is provided. The method and apparatus allow these rules to be inferred during the mapping process, and to be manipulated easily by a user.

Description

FIELD OF INVENTION

This invention is related generally to processing data with computers, and in particular to converting data from one format to another.

BACKGROUND OF THE INVENTION

Two organizations that wish to conduct business with one another electronically find they can send electronic messages to each other, but that the messages are in different formats. The messages sent by a company to one of its suppliers will not be understood unless a mechanism is in place to translate the message from the company's format to the supplier's format. The set of rules for doing such a translation is called a map.

Traditionally, maps had to be developed manually by human experts such as business analysts by documenting the field names of the messages. Traditional Software tools can also do mappings, however, the field names must be identical in order for the traditional software tools to work.

These tools are deficient in the degree of automation with which the maps may be produced. Two message format-types that are being mapped may have a complex relationship that requires a sophisticated conversion procedure or calculation. Such a conversion procedure is called a rule.

However, using traditional mapping methods, a human operator must intervene in the mapping process to enter the rules manually. It is in the specification of rules that current software tools are found wanting. If the same kind of conversion has to be done in different maps, or several times within the same map, the same rule has to be manually entered each time.

It is desirable to have a system that allows these rules to be more easily manipulated. It is further desirable to copy the procedures, eliminating the error-prone and tiresome process of entering the procedure manually each time it is needed. Furthermore, a need exists to store a procedure in a persistent storage system such as a database, and retrieve it automatically. Finally, the procedures should be available to the mapping mechanism, and retrievable in such a way as to require minimal intervention from a human operator.

SUMMARY OF THE INVENTION

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention is illustrated by way of example and not limitation in the figures of the accompanying drawings, in which like references indicate similar elements, and in which:

FIG. 1 illustrates host and remote computers connected over a network;

FIG. 2 is a block diagram of a host computer system which may be used to implement an embodiment of the present invention;

FIG. 3 is an example of a translation for two different message formats.

FIG. 4 is an example of a synonym dictionary.

FIG. 5 is a flow diagram of a method for translating from a first format to a second format.

FIG. 6 is a flow diagram of a method for automatically selecting a rule used to convert one or more fields from a first format to a second format.

FIG. 7 is an embodiment of a data structure for a dictionary used to map a message in a first format to a second format.

DETAILED DESCRIPTION

These and other embodiments of the present invention may be realized in accordance with the following teachings and it should be evident that various modifications and changes may be made in the following teachings without departing from the broader spirit and scope of the invention. The specification and drawings are, accordingly, to be regarded in an illustrative rather than restrictive sense and the invention measured only in terms of the claims.

Hardware Overview

According to the present invention, a host computer system transmits and receives data over a computer network or standard telephone line. According to one embodiment, the steps of accessing, downloading, and manipulating the data, as well as other aspects of the present invention are implemented by a central processing unit (CPU) in the host computer executing sequences of instructions stored in a memory. The memory may be a random access memory (RAM), read-only memory (ROM), a persistent store, such as a mass storage device, or any combination of these devices. Execution of the sequences of instructions causes the CPU to perform steps according to the present invention.

The instructions may be loaded into the memory of the host computer from a storage device, or from one or more other computer systems over a network connection. For example, a server computer may transmit a sequence of instructions to the host computer in response to a message transmitted to the server over a network by the host. As the host receives the instructions over the network connection, it stores the instructions in memory. The host may store the instructions for later execution or execute the instructions as they arrive over the network connection. In some cases, the downloaded instructions may be directly supported by the CPU. In other cases, the instructions may not be directly executable by the CPU, and may instead be executed by an interpreter that interprets the instructions. In other embodiments, hardwired circuitry may be used in place of, or in combination with, software instructions to implement the present invention. Thus, the present invention is not limited to any specific combination of hardware circuitry and software, nor to any particular source for the instructions executed by the host computer.

FIG. 1 illustrates asystem100 in which ahost computer102 is connected to aremote computer104 through anetwork110. The network interface betweenhost computer102 and remote104 may also include one or more routers, such as

routers

106 and108, which serve to buffer and route the data transmitted between the host and client computers. Network110 may be the Internet, a Wide Area Network (WAN), a Local Area Network (LAN), or any combination thereof. Theremote computer104 may be a World-Wide Web (WWW) server that stores data in the form of ‘web pages’ and transmits these pages as Hypertext Markup Language (HTML) files over theInternet network110 to hostcomputer102. To access these files,host computer102 runs a ‘web browser’, which is simply an application program for accessing and providing links to web pages available on various Internet sites.Host computer102 is also configured to communicate totelephone system112 through a telephone interface, typically a modem.

FIG. 2 is a block diagram of a representative networked computer, such ashost computer102 illustrated in FIG.1. Thecomputer system200 includes aprocessor202 coupled through abus201 to a random access memory (RAM)204, a read only memory (ROM)206, and amass storage device207.Mass storage device207 could be a disk or tape drive for storing data and instructions. Adisplay device220 for providing visual output is also coupled toprocessor202 throughbus201. Keyboard221 is coupled tobus201 for communicating information and command selections toprocessor202. Another type of user input device iscursor control unit222, which may be a device such as a mouse or trackball, for communicating direction commands that control cursor movement ondisplay220. Also coupled toprocessor202 throughbus201 is anaudio output port224 for connection to speakers that output audio signals produced bycomputer200.

Further coupled toprocessor202 throughbus201 is an input/output (I/O)interface225, and anetwork interface device223 for providing a physical and logical connection betweencomputer system200 and a network.Network interface device223 is used by various communication applications running oncomputer200 for communicating over a network medium and may represent devices such as an ethernet card, ISDN card, or similar devices.

Modem

226

interfaces computer system

200 to a telephone line and translates digital data produced by the computer into analog signals that can be transmitted over standard telephone lines, such as bytelephone system112 in FIG.1. In an embodiment of the present invention,modem226 provides a hardwired interface to a telephone wall jack, howevermodem226 could also represent a wireless modem for communication over cellular telephone networks. It should be noted that the architecture of FIG. 2 is provided only for purposes of illustration, and that a host computer used in conjunction with the present invention is not limited to the specific architecture shown.

The network and computer systems shown in FIGS. 1 and 2 are used by the present invention to automatically convert the format of a first message into the format of a second message. Messages are composed of discrete data elements called fields. A map is a recipe that describes how the fields of one message (the source) are transformed into the fields of another (the target). Different message formats have many abstract concepts in common, even though they may represent these abstractions in different ways. For example, dates and postal addresses are commonly represented in a variety of message formats, where the representation of each format may be different. One advantage of the present invention is to extract these common notions from various message formats. Another advantage of the present invention is providing a database of these common traits, which are called concepts.

Each field in each format is described in a database. The fields are grouped into sets in the database, where each set corresponds to a concept. The database itself is called the synonym dictionary. The set contains every field from all business objects where the corresponding concept is represented. For example, the concept BIRTH_DATE will have a set that contains every field that represents a birth date, from all business objects or business formats. The set of field names associated with the corresponding concept is called the synonym set.

The synonym dictionary is used to create a translation map. The translation map is used by a translation engine to convert, or translate a message from a first format, such as a source format, to a second format, such as a target format.

FIG. 3 shows an example of the fields of two different message formats, asource message format310 and atarget message format320. In this embodiment, the message is a purchase order, for example. However, the message may convey any information that one person or business wants to send to another person or business. The source fields325 are name, address, city, description, price, quantity, and total. The target fields315 are name, location, information, cost, number, and amount. Although the formats of the source and target fields are structurally different, they have similarities and common abstractions such as name, amount, and place to ship the goods. Thus, the names of the

fields

315 and325 may be different, such as “price” and “cost,” for example, but the

data

317 and327 contained in these fields is the same.

A synonym dictionary assigns an abstract meaning to the different names of similar fields, and captures this abstract meaning in a set of fields called a concept. Structurally, the synonym dictionary has a list ofconcepts410, as shown in FIG. 4. A set of synonym fields420 is associated with each concept. For example, theconcept NAME415 has a corresponding set ofsynonyms425. Each synonym field corresponds to a data field for a given format. For example, thesynonym field425 contains the data fields EDI, NAME, and XML, REQUISITIONER. Thus, the concept can be mapped onto EDI field “NAME” or XML Field “REQUISITIONER.” All fields of business objects (e.g., formats or forms), can be associated with corresponding concepts and synonyms. The business objects can be any kind of business document, such as an order form, a time sheet, or any other type of business form.

After the synonym dictionary is created, it can be used to map each field in one message to a corresponding field in another message. For example, given one target field in the target message, a synonym dictionary is searched for the synonym set in which that field appears. The synonym dictionary guarantees that there is exactly one set that contains the target field. Next, the method iterates over every field in the source message, examining the set of synonyms associated with the source field. If the sets with the source and target fields have at least one common synonym, the source and target fields are said to be mapped.

An example of a method for performing an auto-mapping process is shown in FIG.5. The method shown in FIG. 5 uses the synonym dictionary to convert, or translate, a message from a source format to a target format. A target field in the target message is received,step510. The concept for the received target field is identified in the synonym dictionary,step520. The set of synonym fields associated with the identified concept are received,step530. The method then identifies a field in the synonym set that matches a source field in the source message,step540. The matched source field is then mapped to the received target field,step550. The method repeats step for each field in the synonym set. Then, the method is repeated for each field in the target message,step560.

The method is applied once for each field in the target. The method is applied to each field in the target message type, and works backwards, deriving one or more fields in the source that map to the target.

The method shown in FIG. 5 provides several advantages over the prior art. For example, suppose a user desires to produce two maps, one between message format-types A and B, and another between message format-types A and C. The prior approach requires the user to either create the map between A and C by hand, or to delete the logical associations that have been established for A and B, and create new ones between A and C. Both of these steps require actions to be taken by a user.

In contrast, the method described herein permits logical associations between all of A, B, and C, and allows a user to automatically generate maps between any pair of message format-types without the human intervention steps. This method is far superior to attempting textual matches, because it will not produce wrong associations, and has a much higher success rate in locating matches.

A rule is a procedure that produces a single output from one or more inputs. The output and each of the inputs have a specific data type. The number and type of the inputs, and the type of the output, are the rule's signature. A rule also has a name and a short description, but the rule engine is structured to refer to a rule by its signature. The method determines what rule is to be applied when two fields are to be mapped, and inserts the proper rule into the map.

The method of selecting mapping rule is shown in FIG.6. The method begins at the point in the auto-mapping process when it has been determined that a field, or set of fields, in a source message are to be mapped to a field in the target message,step610. From the source and target fields, the method determines the signature of the rule that can perform the data conversions needed to map the source and target fields,step620. Once the signature is determined, the rules dictionary is searched for any rules that match that signature,step630. If no rule matches,step640, an editor that allows the user to create a suitable rule is invoked,step650. If there is more than one match, the user interface presents the user with a list of rules that match,step660, showing the names and descriptions of the matching rules. The user may select a rule from this list or create a new one with the rule editor,step680. If there is exactly one match, the matching rule is inserted into the generated map,step670.

FIG. 7 shows an embodiment of the data structure, or data tables, and the relationship between data structures, for the synonym and rule dictionaries. This data structure can store the synonym and rule data for all business objects. This data structure provides several advantages. One advantage is to allow efficient automatic mapping of disparate business objects. Another advantage is to make it possible to look up rules based on the types of data that the rules are intended to convert, rather than by name.

Concept data structure

710 stores all information necessary to represent a concept. Table 1 provides a description of the concept ofdata structure710.

TABLE 1

Name	Type	Notes

NAME	CHARACTER	Name of the concept
	(40)
DESCRIPTION	CHARACTER	Description of the concept
	(80)
CATEGORY_ID	NUMBER	Foreign key reference to the
		category table
WRITABLE	NUMBER	Can the user change this concept?
SAVED	YES/NO	Have changes to this concept been
		saved to the database?
DELETED	YES/NO	Has this concept been removed
		from the database?
COMPANY_ID	NUMBER	ID of the company that owns this
		concept.
CONCEPT_ID	NUMBER	Primary key (system-generated)
LAST_UPDATE	DATE	When was this concept last written
		to the database?

Category data structure

720 stores basic information about a concept category. Table 2 provides a description of thecategory data structure720.

TABLE 2

Name	Type	Notes

NAME	CHARACTER (40)	Name of this concept category.
DESCRIPTION	CHARACTER (80)	Description of this concept
		category.
CATEGORY_ID	NUMBER	Primary key (system-generated)

Rule data structure

730 stores basic information for a rule, such as the ID of the company that owns it. Table 3 provides a description of thedata structure730.

TABLE 3

Name	Type	Notes

NAME	CHARACTER	Name of this rule.
	(40)
DESCRIPTION	CHARACTER	Description of what the rule does
	(80)
COMPANY_ID	NUMBER	ID of the company that owns the
		rule.
RULE_ID	NUMBER	Primary key (system-generated)

Arguments data structure

740 stores this information necessary to pass arguments to rules. Table 4 shows a description ofarguments data structure740.

TABLE 4

Name	Type	Notes

RULE	NUMBER	Foreign key reference to the rule
		table
CATEGORY_ID	NUMBER	Foreign key reference to the
		category table
POSITION	NUMBER	Binding order of this argument
TYPE	NUMBER	Data type of this argument

Business objectsdata structure750 stores the information that is needed to identify a business object. Table 5 provides a description of businessobject data structure750.

TABLE 5

Name	Type	Notes

APPLICATION	CHARACTER (16)	EDI, Idoc, XML,
		CBL, etc.
APP_VERSION	CHARACTER (16)	Application version,
		eg EDI 850
TRANSACTION	CHARACTER (16)	Name of the business
		object, eg invoice
COMPANY_ID	NUMBER	ID of the company that
		owns the business
		object.
DESCRIPTION	CHARACTER (16)	Description of this
		business object
BUSINESS_OBJECT_ID	NUMBER	Primary key (system-
		generated)

Field data structure

760 stores all of the synonyms for a given concept. Table 6 provides a description offield data structure760.

TABLE 6

Name	Type	Notes

NAME	CHARACTER (256)	Fully-qualified name of the field
CONCEPT_ID	NUMBER	Foreign key to concept table
DELETED	YES/NO	Has this field been removed from
		a concept?
BUSINESS_OBJECT_ID	NUMBER	Foreign key to business_object
		table.
LAST_UPDATE	DATE	When was this field last saved to
		database?

Command data structure

770 links a rule's signature information with the set of commands that implements the rule, described in Table 7.

TABLE 7

Name	Type	Notes

RULE_ID	NUMBER	Foreign key reference to the rule
		table
TRANSLATOR_ID	NUMBER	Identifier of the command translator
		(interpreter).
COMMAND_BLOB	LONG	Binary representation of the rule's
	RAW	commands.

Translation data structure

780 refers to the translators necessary to invoke the commands for a rule, as described in Table 8.

TABLE 8

Name	Type	Notes

NAME	CHARACTER (40)	Name of this command
		translator
DESCRIPTION	CHARACTER (80)	Description of this
		command translator
TRANSLATOR_ID	NUMBER	Primary key (system-
		generated)

There are several advantages of the present invention over the prior art. For example, prior art methods do not automatically determine what rule is needed in order to perform a conversion. Prior solutions require human intervention during the mapping process to specify the rule that is necessary to implement a conversion. In contrast, the present invention limits actions required of users to adding new rules, which are available for subsequent mapping operations.

The present invention uses a knowledge base in order for the method to work. This knowledge base allows a user to leverage expertise in this knowledge base domain. Additional advantages of the present invention include providing maps that correctly perform the conversions between data fields; and providing greater convenience to users, because it is not necessary to re-enter a rule multiple times. In addition, rules are not bound to the fields of any format of a message. The same rule may be applied to different message formats. This makes the rules dictionary very memory space efficient.

A method and apparatus for automatically selecting rules is described. In the description, numerous details have been set forth. It will be apparent, however, to one skilled in the art, that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form, rather than in detail, in order to avoid obscuring the present invention.

Some portions of the detailed descriptions are presented in terms of algorithms and symbolic representations of operations on data bits within a computer memory. These algorithmic descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. An algorithm is here, and generally, conceived to be a self-consistent sequence of steps leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like.

It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the following discussion, it is appreciated that throughout the description, discussions utilizing terms such as “processing” or “computing” or “calculating” or “determining” or “displaying” or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.

The present invention also relates to apparatus for performing the operations herein. This apparatus may be specially constructed for the required purposes, or it may comprise a general purpose computer selectively activated or reconfigured by a computer program stored in the computer. Such a computer program may be stored in a computer readable storage medium, such as, but is not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, and magnetic-optical disks, read-only memories (ROMs), random access memories (RAMs), EPROMs, EEPROMs, magnetic or optical cards, or any type of media suitable for storing electronic instructions, and each coupled to a computer system bus.

The algorithms and displays presented herein are not inherently related to any particular computer or other apparatus. Various general purpose systems may be used with programs in accordance with the teachings herein, or it may prove convenient to construct more specialized apparatus to perform the required method steps. The required structure for a variety of these systems will appear from the description below. In addition, the present invention is not described with reference to any particular programming language. It will be appreciated that a variety of programming languages may be used to implement the teachings of the invention as described herein.

In the foregoing specification, the invention has been described with reference to specific exemplary embodiments thereof. It will, however, be evident that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention as set for in the appended claims. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.