Data structure and management system for a superset of relational databases

• US 7,305,404 B2
• Filed: 10/21/2003
• Issued: 12/04/2007
• Est. Priority Date: 10/21/2003
• Status: Active Grant

• Current Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Original Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Inventors: Owens, Timothy C., Harrison, Bruce E.
• Primary Examiner(s): NGUYEN, CAM LINH T
• Application Number:
  US10/690,322
• Publication Number:
  US 20050086256A1
• Time in Patent Office: 1,505 Days
• Field of Search: 707100-1041, 707/10, 707/201
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A data structure, database management system, and methods of validating data are disclosed. A data structure is described that includes a superset of interconnected relational databases containing multiple tables having a common data structure. The tables may be stored as a sparse matrix linked list. A method is disclosed for ordering records in hierarchical order, in a series of levels from general to specific. An example use with address databases is described, including a method for converting an input address having a subject representation into an output address having a preferred representation. Preferred artifacts may be marked with a token. Alias tables may be included. This Abstract is provided to comply with the rules, which require an abstract to quickly inform a searcher or other reader about the subject matter of the application. This Abstract is submitted with the understanding that it will not be used to interpret or limit the scope or meaning of the claims.

Claims

1. An address management system for converting a subjective representation of an address into a preferred representation of the address, comprising:

a plurality of relational databases comprising;

a first relational database comprising one or more first tables;

a second relational database comprising one or more second tables for storing source data comprising address records as a sparse matrix linked list; and

a third relational database comprising one or more third tables storing standardized representations for a plurality of discrete artifacts;

an interface; and

a computer program module configured to;

receive a subjective representation of the address from said first relational database, wherein said subjective representation of the address comprises a plurality of discrete artifacts;

re-format the subjective representation of the address according to a set of standardization rules, wherein said standardization rules at least comprise amending punctuation in said subjective representation of the address;

parse said subjective representation of the address into the plurality of discrete artifacts, including name, street address, city, state, and zip code;

locate one or more candidate representations of the address;

select a preferred representation of the address from among said one or more of candidate representations of the address;

store said preferred representation of the address in said third relational database; and

,

communicate the preferred representation of the address to the interface.

2. The address management system of claim 1, wherein said one or more second tables comprises a plurality of address records, and wherein said computer program module is further configured to arrange said address records in hierarchical order based upon the values of said data stored in said address records.

3. The address management system of claim 1, further comprising a local server computer and one or more client computers wherein said computer program module is further configured to distribute a duplicate of said source data comprising address records as a sparse matrix linked list from said local server computer to said one or more client computers.

4. The address management system of claim 1, wherein said computer program module, configured to locate one or more candidate representations of the address, is further configured to:

select one of said plurality of discrete artifacts in an address record;

locate one or more candidate artifacts from among said source data by comparing said one of said plurality of discrete artifacts to said source data;

select a preferred artifact from among said one or more candidate artifacts; and

combine said preferred artifact with one or more preferred artifacts to form one of said one or more candidate representations of the address.

5. The address management system of claim 1, wherein said computer program module is further configured to:

review alias data to identify a preferred alias representation of the address; and

,

record a preferred alias token to said preferred alias representation of the address.

6. The address management system of claim 5, wherein said computer program module configured to review alias data to identify a preferred alias representation of the address is further configured to:

(a) parse said subjective representation of the address into a plurality of discrete artifacts;

(b) select one of said plurality of discrete artifacts;

(1) locate one or more candidate alias artifacts from said source data by comparing said one of said plurality of discrete artifacts to said alias data;

(2) select a preferred alias artifact from said one or more candidate alias artifacts;

(3) store said preferred alias artifact in said third relational database;

(c) repeat step (b) for each discrete artifact in said plurality of discrete artifacts of said subjective representation of the address; and

(d) combine said preferred alias artifacts to form one of said one or more candidate representations.

7. The address management system of claim 1, wherein said computer program module is further configured to:

parse the subjective representation of the address into a plurality of discrete artifacts;

retrieve standardization data from said third relational database, said standardization data comprising one or more standardized representations for each discrete artifact in said plurality of discrete artifacts; and

retrieve alias data from a fourth relational database, said alias data comprising one or more equivalent representations of each respective artifact in said plurality of artifacts.

8. The address management system of claim 1, wherein the interface is configured to govern interaction between said computer program module and one or more external applications.

9. The address management system of claim 8, wherein said interface communicates with a printer.

10. The address management system of claim 8, wherein said interface communicates with a display device.

11. The address management system of claim 8, wherein said interface communicates with an application residing on a computer system.

12. A method of processing a subjective representation of an address to obtain a preferred representation of the address, said method comprising the steps of:

receiving the subjective representation of the address;

parsing said subjective representation of the address into a plurality of discrete artifacts, wherein at least one of said discrete artifacts comprises a street address;

re-formatting the subjective representation of the address according to a set of standardization rules, wherein said re-formatting comprises at least altering punctuation of the subjective representation of the address;

locating one or more candidate artifacts from source data received as a sparse matrix linked list by comparing said one discrete artifact to said source data;

selecting a preferred artifact from said one or more candidate artifacts;

repeating the step of selecting a preferred artifact from said one or more candidate artifacts to generate a plurality of preferred artifacts;

combining said plurality of preferred artifacts to form a candidate representation of the address;

repeating the step of said combining said plurality of preferred artifacts to form a candidate representation of the address step to generate a plurality of candidate representations of the address;

selecting a preferred representation of the address from said plurality of candidate representations of the address based on the presence of a preferred token; and

communicating said preferred representation of ate address to an interface.

13. A method of processing a subjective representation of an address to obtain a preferred representation of tile address, in an address management system comprising a plurality of relational databases including a first relational database comprising one or more first tables, a second relational database comprising one or more second tables, wherein each of said one or more second tables further comprises a plurality of records comprising source data and a third relational database comprising one or more third tables, said method comprising the steps of;

receiving a subjective representation of the address stored in said first relational database, said subjective representation of the address comprising a plurality of artifacts including a name, street address, city, state, and zip code;

re-formatting the subjective representation of the address according to a set of standardization rules;

arranging said plurality of records in hierarchical order based upon the values of said source data stored in said plurality of records;

transforming one or more of said second tables into a sparse matrix linked list;

locating one or more candidate representations of the address from source data stored in said second relational database by recognizing that a preferred token is present among any of said one or more candidate representations of the address;

selecting a preferred representation of the address from among said one or more candidate representations of the address based an file presence of the preferred token; and

communicating said preferred representation of the address from said third relational database to an interface.

14. The method of claim 13, further comprising:

storing said one or more second tables as a sparse matrix linked list in said second relational database.

15. The method of claim 13, further comprising:

(a) parsing said subjective representation of the address into a plurality of discrete artifacts;

(b) selecting one of said plurality of discrete artifacts;

(1) locating one or more candidate artifacts from among said source data by comparing said one of said plurality of discrete artifacts to said source data;

(2) selecting a preferred artifact from among said plurality of candidate artifacts;

(c) repeating step (b) for each of said plurality of discrete artifacts; and

(d) combining the plurality of preferred artifacts to form one of said one or more candidate representations of the address.

16. The method of claim 13, further comprising:

reading standardization data from the third relational databases, said standardization data comprising one or more standardized representations of said plurality of discrete artifacts.

17. The method of claim 13, further comprising:

(a) parsing said subjective representation of the address into the plurality of discrete artifacts;

(b) selecting one of said plurality of discrete artifacts;

(1) locating one or more candidate alias artifacts from among said source data by comparing said one of the plurality of discrete artifacts to said alias data;

(2) selecting a preferred alias artifact from among said one or more candidate alias artifacts;

(c) repeating step (b) for each of said one or more discrete artifacts to generate a plurality of selected preferred alias artifacts; and

(d) combining said plurality of selected preferred alias artifacts to form one of said one or more candidate representations of the address.

18. The method of claim 13, further comprising the steps of:

presenting said one or more candidate representations of the address to a user; and

receiving an indication from the user identifying one of the one or more candidate representations of the address as the preferred representation of the address.

19. The method of claim 13, further comprising:

parsing said subjective representation of the address into a plurality of discrete artifacts;

reading standardization data in the third relational database, said standardization data comprising one or more standardized representations of said plurality of discrete artifacts; and

reading alias data in a fourth relational database, said alias data comprising one or more equivalent representations of said plurality of discrete artifacts.

20. The method of claim 13, said method further comprising:

reading a plurality of rule sets, each correlated to one of said one or more external applications;

receiving a request from a first external application;

retrieving a first rule set correlated to said first external application; and

applying said first rule set to govern the interaction between said first external application and said one or more computer program modules.