Interrogation index file comparison

• US 5,604,901 A
• Filed: 10/03/1995
• Issued: 02/18/1997
• Est. Priority Date: 04/13/1992
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Paleveda, John F., Kelley, Edward E.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Lintz, Paul R.
• Application Number:
  US08/538,377
• Time in Patent Office: 504 Days
• Field of Search: 395/600, 364/419.19
• US Class Current: 1/1
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence

Abstract

A method of comparing files takes three passes through data tables in memory to generate tables containing pointers to matches and mismatches by employing a method of keyword-index translation in which a keyword is taken from a first data table in a first pass and used as the index in loading an index table containing a pointer to the record containing that keyword. In a symmetric operation, a keyword is fetched from one table and used to interrogate the corresponding index table in a second pass. If there is a match, the record in the index table contains the pointer; and if there is a mismatch, the record contains a null. In an optional third pass, keywords are fetched from the other table and used to find records in the other table that are mismatches.

Claims

1. A method of comparing in a data processing system a first file of data and a second file of data in only one pass through each of said first and second files, each of said first and second files comprising a set of records, each record including a key, comprising the steps of:

initializing and loading a set of at least one data table including at least the step of loading a first key-index table with a first key-index record corresponding to each record in said first file in a first data pass, said first key-index record having a first interrogation index element related in a one to one correspondence to a first-file key of said first file;

sequentially fetching a second-file key from a record in said second file in a second data pass;

interrogating a corresponding record in said first key-index table having a second interrogation index element related to said second-file key and to said first interrogation index element; and

storing data representative of a matching relationship between said record of said first file and said record of said second file.

2. A method according to claim 1, in which said interrogation index, said first-file key, and said second-file key are alphanumeric.

3. A method according to claim 1, in which at least one of said first-file key and second-file key are formed from at least two non-contiguous characters selected from records in said first file or said second file.

4. A method according to claim 2, in which at least one of said first-file key and said second-file key are formed from at least two non-contiguous characters selected from records in said first file or said second file.

5. A method according to claim 1, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of match pointers pointing to matching records in said first file and said second file.

6. A method according to claim 2, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of match pointers pointing to matching records in said first and second files.

7. A method according to claim 1, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of mismatch pointers pointing to records in said second file lacking a matching record in said first file.

8. A method according to claim 2, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of mismatch pointers pointing to records in said second file lacking a matching record in said first file.

9. A method according to claim 5, in which said data representative of the relationship between said record of said first file and said record of said second file further comprises a set of mismatch pointers pointing to records in said second file lacking a matching record in said first file.

10. A method according to claim 6, in which said data representative of the relationship between said record of said first file and said record of said second file further comprises a set of mismatch pointers pointing to records in said second file lacking a matching record in said first file.

11. A method according to claim 1, in which at least one of said first-file key and second-file key are formed from at least one field selected from records in said first file or said second file containing a plurality of fields.

12. A method according to claim 11, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of match pointers pointing to matching records in said first and second files.

13. A method according to claim 11, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of mismatch pointers pointing to records in said second file lacking a matching record in said first file.

14. A method according to claim 2, in which at least one of said first-file key and second-file key are formed from at least one field selected from records in said first file or said second file containing a plurality of fields.

15. A method according to claim 14, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of match pointers pointing to matching records in said first and second files.

16. A method according to claim 14, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of mismatch pointers pointing to records in said second file lacking a matching record in said first file.

17. A method according to any of claims 1-16, further including the step of forming a new file containing only records common to both said first and said second files.

18. A method according to claim 1, further comprising the steps of:

loading a second key-index table with a second key-index record corresponding to each record in said second file in said second data pass, said second key-index record having an interrogation index related to a second-file key of said second file;

sequentially fetching a first-file key from a record in said first file in a third data pass;

interrogating a corresponding record in said second key-index table having an interrogation index element related in a one to one correspondence to said first-file key; and

storing data representative of the relationship between said record of said first file and said record of said second file.

19. A method according to claim 18, in which said interrogation index, said first-file key, and said second-file key are alphanumeric.

20. A method according to claim 18, in which at least one of said first-file key and second-file key are formed from at least two non-contiguous characters selected from records in said first file or said second file.

21. A method according to claim 19, in which at least one of said first-file key and second-file key are formed from at least two non-contiguous characters selected from records in said first file or said second file.

22. A method according to claim 18, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of pointers pointing to corresponding records in said first and second files.

23. A method according to claim 19, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of corresponding pointers pointing to corresponding records in said first and second files.

24. A method according to claim 18, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of mismatch pointers pointing to records in said second file lacking a corresponding record in said first file and to records in said first file lacking a corresponding record in said second file.

25. A method according to claim 19, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of mismatch pointers pointing to records in said second file lacking a corresponding record in said first file and to records in said first file lacking a corresponding record in said second file.

26. A method according to claim 22, in which said data representative of the relationship between said record of said first file and said record of said second file further comprises a set of mismatch pointers pointing to records in said second file lacking a corresponding record in said first file and to records in said first file lacking a corresponding record in said second file.

27. A method according to claim 23, in which said data representative of the relationship between said record of said first file and said record of said second file further comprises a set of mismatch pointers pointing to records in said second file lacking a corresponding record in said first file and to records in said first file lacking a corresponding record in said second file.

28. A method according to any of claims 18-27, further including the step of forming a new file containing only records common to both said first and said second files.

29. A method of comparing in a data processing system a first file of data and a second file of data, each of said first and second files comprising a set of records, each record including a key, comprising the steps of:

in a first data pass initializing and loading a set of at least one data table including at least the step of loading a first key-index table with a first key-index record corresponding to each record in said first file, said first key-index record having a first interrogation index element related in a one to one correspondence to a first-file key of said first file;

in a second data pass, sequentially fetching a second-file key from a record in said second file;

interrogating a corresponding record in said first key-index table having a second interrogation index element related in a one to one correspondence to said second-file key and to said first interrogation index element; and

storing data representative of a matching relationship between said record of said first file and said record of said second file;

in a third data pass, initializing and loading a set of at least one data table including at least the step of loading a second key-index table with a second key-index record corresponding to each record in said second file, said second key-index record having an interrogation index related in a one to one correspondence to a second-file key of said second file;

in a fourth data pass, sequentially fetching a first-file key from a record in said first file;

interrogating a corresponding record in said second key-index table having an interrogation index element related in a one to one correspondence to said first-file key; and

storing data representative of the relationship between said record of said first file and said record of said second file.

30. A method according to claim 29, in which said second data pass is effected by reading said second file from non-volatile storage to fetch said second-file key;

and

said fourth data pass is effected by reading said first file from non-volatile storage to fetch said first-file key, whereby said first and second files are not loaded into said memory.

31. A method according to claim 30, in which said first data pass is effected by reading said first file from non-volatile storage to load said first key-index table;

and

said third data pass is effected by reading said second file from non-volatile storage to load said second key-index table, whereby said first and second files are not loaded into said memory.

32. A method according to any of claims 29-31, in which said interrogation index, said first-file key, and said second-file key are alphanumeric.

33. A method according to claim 29, in which at least one of said first-file key and second-file key are formed from at least two non-contiguous characters selected from records in said first file or said second file.

34. A method according to claim 32, in which at least one of said first-file key and second-file key are formed from at least two non-contiguous characters selected from records in said first file or said second file.

35. A method according to claim 29, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of pointers pointing to corresponding records in said first and second files.

36. A method according to claim 32, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of corresponding pointers pointing to corresponding records in said first and second files.

37. A method according to claim 29, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of mismatch pointers pointing to records in said second file lacking a corresponding record in said first file.

38. A method according to claim 32, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of mismatch pointers pointing to records in said second file lacking a corresponding record in said first file.

39. A method of comparing in a data processing system a first file of data and a second file of data, each of said first and second files comprising a set of records, each record including a key, comprising the steps of:

in a first data pass, reading said first file from non-volatile storage and loading a set of at least one data table in memory including at least the step of loading a first key-index table with a first key-index record corresponding to each record in said first file, said first key-index record having a first interrogation index element related in a one to one correspondence to a first-file key of said first file;

in a second data pass, reading said second file from non-volatile storage and loading a set of at least one data table in memory including at least the step of loading a second key-index table with a second key-index record corresponding to each record in said second file, said second key-index record having a second interrogation index element related in a one to one correspondence to a second-file key of said second file and to said first interrogation index element;

in a third data pass, sequentially fetching from non-volatile storage a first-file key from a record in said first file;

interrogating a corresponding record in said second key-index table having an interrogation index element related in a one to one correspondence to said first-file key; and

storing data representative of a matching relationship between said record of said first file and said record of said second file;

in a fourth data pass, sequentially fetching from non-volatile storage a second-file key from a record in said second file;

interrogating a corresponding record in said first key-index table having an interrogation index element related in a one to one correspondence to said second-file key; and

storing data representative of the relationship between said record of said first file and said record of said second file.

40. A method according to claim 39, in which said second data pass is effected by reading said second file from non-volatile storage to fetch said second-file key;

and

said fourth data pass is effected by reading said first file from non-volatile storage to fetch said first-file key, whereby said first and second files are not loaded into said memory.

41. A method according to claim 40, in which said first data pass is effected by reading said first file from non-volatile storage to load said first key-index table;

and

said third data pass is effected by reading said second file from non-volatile storage to load said second key-index table, whereby said first and second files are not loaded into said memory.

42. A method according to any of claims 39-41, in which said interrogation index, said first-file key, and said second-file key are alphanumeric.

43. A method according to claim 39, in which at least one of said first-file key and second-file key are formed from at least two non-contiguous characters selected from records in said first file or said second file.

44. A method according to claim 42, in which at least one of said first-file key and second-file key are formed from at least two non-contiguous characters selected from records in said first file or said second file.

45. A method according to claim 39, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of pointers pointing to corresponding records in said first and second files.

46. A method according to claim 42, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of corresponding pointers pointing to corresponding records in said first and second files.

47. A method according to claim 39, in which said data representative of the relationship between said record of said first file and said record of said second file comprises a set of mismatch pointers pointing to records in said second file lacking a corresponding record in said first file.

48. A method of comparing in a data processing system a first file of data and a second file of data located in non-volatile storage media, each of said first and second files comprising a set of records, each record including a key, comprising the steps of:

initializing and loading a set of data tables in memory including first and second key-index tables, a match table for storing data representative of records in said first file having a counterpart record in said second file, a first mismatch table for storing data representative of records in said first file lacking a counterpart record in said second file and a second mismatch table for storing data representative of records in said second file lacking a counterpart record in said first file;

sequentially fetching a second-file keyword from a record in said second file, interrogating a corresponding record in said first key-index table having an index element equal to said second-file keyword, and adding a record containing identifying data to said match table when said corresponding record has a non-null entry and adding a record containing identifying data to said second mismatch table when said corresponding record has a null entry; and

sequentially fetching a first-file keyword from a record in said first file, interrogating a corresponding record in said second key-index table having an index element equal to said first-file keyword, and adding a record containing identifying data to said first mismatch table when said corresponding record has a null entry.

49. A method according to claim 48, including a preliminary step of reading said first and second files of data from nonvolatile storage into corresponding first and second data tables in memory, each record of said first and second data tables containing at least said key of a corresponding file record;

said step of loading said first key-index table is effected by reading said key for said first data table in a first pass through one of said set of data tables in memory;

said step of repetitively fetching a second-file keyword and interrogating a corresponding record in said first key-index file is effected by reading through said second data table in a second pass through one of said set of data tables in memory; and

said step of repetitively fetching a first-file keyword and interrogating a corresponding record in said second key-index file is effected by reading through said first data table in a third pass through one of said set of data tables in memory.

50. A method according to claim 49, in which said first-file keyword, and said second-file keyword are alphanumeric.

51. A method according to claim 50, in which said first-file keyword, and said second-file keyword are alphanumeric.

52. A method according to claim 49, in which at least one of said first-file keyword and second-file keyword are formed from at least two non-contiguous characters selected from records in said first file or said second file.