Multikeyed table implementable on a personal digital assistant

• US 6,535,885 B1
• Filed: 10/16/2000
• Issued: 03/18/2003
• Est. Priority Date: 10/16/2000
• Status: Active Grant

• Current Assignee: TeleCommunication Systems Inc (Comtech Telecommunications Corporation)
• Original Assignee: Aether Systems, Inc. (Comtech Telecommunications Corporation)
• Inventors: Nardone, Joseph R., Mason, Larry D.
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/688,160
• Time in Patent Office: 883 Days
• Field of Search: 707/10, 707/100, 707/102, 707/2, 707/3, 707/4, 707/101, 707/104, 707/103, 707/5, 707/6, 707/7
• US Class Current: 707/752
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A multikeyed table utilizing a number of primary and secondary keys is implementable on a personal digital assistant. The table includes one or more records with each record having a plurality of fields. A number of fields in the records are designated as primary and secondary keys, which in turn are used for sorting and ordering the records. A target position in the multikeyed table may be identified by first receiving target primary and secondary keys from, for example, an application user. Subsequently, an operating system implemented in the personal digital assistant is prompted to select and return one record stored in the table. In response, the record selected by the operating system is received. The record received from the operating system is then compared with the target'"'"'s primary and secondary keys, after which the target is indicated as having keys greater than, less than, or equal to the keys of the received record. This procedure is repeated until a record with primary and secondary keys equal to the target'"'"'s primary and secondary keys is located, at which point the returned record is identified as the target position. Alternatively, the procedure is repeated until all records stored in the table have been identified as having primary and secondary keys greater than or less than the target'"'"'s primary and secondary keys, at which point the target position is identified as falling between a highest record having primary and secondary keys less than the target primary and secondary keys and a lowest record having primary and secondary keys greater than the target primary and secondary keys.

Claims

1. A method for managing information on a personal digital assistant, said method comprising the steps of:

(1) executing an application which utilizes a multikeyed table for maintaining a sorted list of records on said personal digital assistant, wherein each record of said sorted list of records is capable of storing information and comprises a plurality of fields, wherein one field of said plurality of fields is designated as a primary key and at least one additional field of said plurality of fields is designated as a secondary key;

(2) receiving a target record to be added, deleted, or manipulated within said table and comparing primary and secondary keys of said received record to be added, deleted, or manipulated with primary and secondary keys of a record retrieved from said table.

2. The method of claim 1, further comprising repeating said step of sorting (2) until a record having primary and secondary keys equal to said primary and secondary keys of said record to be added, deleted, or manipulated is identified, or until all records in said table are identified as having primary and secondary keys greater than or equal to said primary and secondary keys of said record to be added, deleted, or manipulated.

3. The method of claim 1, wherein said comparing comprises indicating whether primary and secondary keys of said record to be added, deleted, or manipulated are greater than, less than, or equal to the primary and secondary keys of said record retrieved from said table.

4. A method for identifying a target position in a multikeyed table, wherein said table is implemented in a personal digital assistant and comprises one or more records with each record comprising a plurality of fields, wherein one field of said plurality of fields is designated as a primary key and at least one additional field of said plurality of fields is designated as a secondary key, and wherein said primary and secondary keys of each record are used in ordering said records, said method comprising the steps of:

(1) receiving target primary and secondary keys for identifying said target position;

(2) selecting and returning one record stored in said table;

(3) receiving said one record selected in step (2);

(4) comparing and indicating whether said target primary and secondary keys are greater than, less than, or equal to the primary and secondary keys of said one record; and

(5) repeating steps (3)-(4) until a record with primary and secondary keys equal to said target primary and secondary keys is located, at which point said one record is identified as said target position, or until all records stored in said table have been identified as having primary and secondary keys greater than or less than said target primary and secondary keys, at which point said target position is identified as falling between a largest record having primary and secondary keys less than said target primary and secondary keys and a smallest record having primary and secondary keys greater than said target primary and secondary keys.

5. The method of claim 4, further comprising the step of:

adding a record to, deleting a record from, returning a record stored at, or returning a record stored after said target position.

6. The method of claim 4, wherein said one or more records of said multikeyed table are sorted first by primary key order then by secondary key order.

7. The method of claim 4, wherein said one or more records are indexed only by primary and secondary keys.

8. The method of claim 4, further comprising the step of reading data from said target position and comparing said primary and secondary keys from said target position against said target primary and secondary keys entered in step (1).

9. The method of claim 8, further comprising deleting a record from said target position only if said primary and secondary keys read from said target position are equal to said target primary and secondary keys entered in step (2).

10. The method of claim 8, further comprising adding a record to said target position only if said primary and secondary keys read from said target position are not equal to said target primary and secondary keys entered in step (2).

11. A method for identifying a target position in a multikeyed table, wherein said table is implemented in a personal digital assistant and comprises one or more records with each record comprising a plurality of fields, wherein one field of said plurality of fields is designated as a primary key and at least one additional field of said plurality of fields is designated as a secondary key, and wherein said primary and secondary keys of each record are used in ordering said records, said method comprising the steps of:

(1) receiving target primary and secondary keys for identifying said target position;

(2) identifying said target position by;

(a) selecting one record from said table according to a selection process;

(b) comparing and indicating whether said target primary and secondary keys are greater than, less than, or equal to the primary and secondary keys of said one record;

(c) refining said selection process, if said target primary and secondary keys are not equal to the primary and secondary keys of said one record, by using said indication of whether said target primary and secondary keys are greater than or less than said primary and secondary keys of said one record;

(d) identifying said one record as occupying said target position if said target primary and secondary keys are equal to the primary and secondary keys of said one record; and

(e) repeating steps (a)-(c), if said target primary and secondary keys are not equal to the primary and secondary keys of said one record, until all records have been retrieved and compared with said target primary and secondary keys, at which point said target position is identified as falling between a largest record having primary and secondary keys less than said target primary and secondary keys and a smallest record having primary and secondary keys greater than said target primary and secondary keys.

12. The method of claim 11, wherein said selection process of step (a) comprises a binary sorting routine.

13. A system for managing information comprising:

a personal digital assistant comprising a memory and a processor, wherein said processor is capable of;

(1) executing an application which utilizes a multikeyed table, implementable in said memory, for maintaining a sorted list of records, wherein each record of said sorted list of records is capable of storing information and comprises a plurality of fields, wherein one field of said plurality of fields is designated as a primary key and at least one additional field of said plurality of fields is designated as a secondary key; and

(2) receiving a target record to be added, deleted, or manipulated within said table and comparing primary and secondary keys of said received target record to be added, deleted, or manipulated with primary and secondary keys of a record retrieved from said table.

14. The system of claim 13, wherein said processor is capable of repeating said sorting until a record having primary and secondary keys equal to said primary and secondary keys of said record to be added, deleted, or manipulated is identified, or until all records in said table are identified as having primary and secondary keys greater than or equal to said primary and secondary keys of said record to be added, deleted, or manipulated.

15. The system of claim 13, wherein said processor is capable of indicating whether primary and secondary keys of said record to be added, deleted, or manipulated are greater than, less than, or equal to the primary and secondary keys of said record retrieved from said table.

16. A system for identifying a target position in a multikeyed table comprising:

a personal digital assistant comprising a memory and a processor, wherein said table is implemented in said memory and comprises one or more records with each record comprising a plurality of fields, wherein one field of said plurality of fields is designated as a primary key and at least one additional field of said plurality of fields is designated as a secondary key, wherein said primary and secondary keys of each record are used in ordering said records, and wherein said processor is capable of;

(1) receiving target primary and secondary keys for identifying said target position;

(2) selecting and returning one record stored in said table;

(3) receiving said one record selected step (2);

(4) comparing and indicating whether said target primary and secondary keys are greater than, less than, or equal to the primary and secondary keys of said one record; and

(5) repeating steps (3)-(4) until a record with primary and secondary keys equal to said target primary and secondary keys is located, at which point said one record is identified as said target position, or until all records stored in said table have been identified as having primary and secondary keys greater than or less than said target primary and secondary keys, at which point said target position is identified as falling between a largest record having primary and secondary keys less than said target primary and secondary keys and a smallest record having primary and secondary keys greater than said target primary and secondary keys.

17. The system of claim 16, wherein said processor is capable of:

adding a record to, deleting a record from, returning a record stored at, or returning a record stored after said target position.

18. The system of claim 16, wherein said one or more records of said multikeyed table are sorted first by primary key order then by secondary key order.

19. The system of claim 16, wherein said one or more records are indexed only by primary and secondary keys.

20. The system of claim 16, wherein said processor is capable of reading data from said target position and comparing said primary and secondary keys from said target position against said target primary and secondary keys entered in step (1).

21. The system of claim 20, wherein said processor is capable of deleting a record from said target position only if said primary and secondary keys read from said target position are equal to said target primary and secondary keys entered in step (2).

22. The system of claim 20, wherein said processor is capable of adding a record to said target position only if said primary and secondary keys read from said target position are not equal to said target primary and secondary keys entered in step (2).

23. A system for identifying a target position in a multikeyed table comprising:

a personal digital assistant comprising a memory and a processor, wherein said table is implemented in said memory and comprises one or more records with each record comprising a plurality of fields, wherein one field of said plurality of fields is designated as a primary key and at least one additional field of said plurality of fields is designated as a secondary key, wherein said primary and secondary keys of each record are used in ordering said records, and wherein said processor is capable of;

(1) receiving target primary and secondary keys for identifying said target position;

(2) identifying said target position by;

(a) selecting one record from said table according to a selection process;

(b) comparing and indicating whether said target primary and secondary keys are greater than, less than, or equal to the primary and secondary keys of said one record;

(c) refining said selection process, if said target primary and secondary keys are not equal to the primary and secondary keys of said one record, by using said indication of whether said target primary and secondary keys are greater than or less than said primary and secondary keys of said one record;

(d) identifying said one record as occupying said target position if said target primary and secondary keys are equal to the primary and secondary keys of said one record; and

(e) repeating steps (a)-(c), if said target primary and secondary keys are not equal to the primary and secondary keys of said one record, until all records have been retrieved and compared with said target primary and secondary keys, at which point said target position is identified as falling between a largest record having primary and secondary keys less than said target primary and secondary keys and a smallest record having primary and secondary keys greater than said target primary and secondary keys.

24. The system of claim 23, wherein said selection process of step (a) comprises a binary sorting routine.

25. A computer program embodied on a computer-readable medium for managing information on a personal digital assistant, said program comprising:

computer-readable instructions for executing an application which utilizes a multikeyed table for maintaining a sorted list of records on said personal digital assistant, wherein each record of said sorted list of records is capable of storing information and comprises a plurality of fields, wherein one field of said plurality of fields is designated as a primary key and at least one additional field of said plurality of fields is designated as a secondary key; and

computer-readable instructions for receiving a target record to be added, deleted, or manipulated within said table and comparing primary and secondary keys of said received target record to be added, deleted, or manipulated with primary and secondary keys of a record retrieved from said table.

26. The computer program of claim 25, wherein said instructions comprises instructions for repeating said sorting until a record having primary and secondary keys equal to said primary and secondary keys of said record to be added, deleted, or manipulated is identified, or until all records in said table are identified as having primary and secondary keys greater than or equal to said primary and secondary keys of said record to be added, deleted, or manipulated.

27. The computer program of claim 25, wherein said instructions for comparing comprises instructions for indicating whether primary and secondary keys of said record to be added, deleted, or manipulated are greater than, less than, or equal to the primary and secondary keys of said record retrieved from said table.

28. A computer program embodied on a computer-readable medium for identifying a target position in a multikeyed table, wherein said table is implemented in a personal digital assistant and comprises one or more records with each record comprising a plurality of fields, wherein one field of said plurality of fields is designated as a primary key and at least one additional field of said plurality of fields is designated as a secondary key, and wherein said primary and secondary keys of each record are used in ordering said records, said computer program comprising instructions for:

(1) receiving target primary and secondary keys for identifying said target position;

(2) selecting and returning one record stored in said table;

(3) receiving said one record selected in step (2);

(4) comparing and indicating whether said target primary and secondary keys are greater than, less than, or equal to the primary and secondary keys of said one record; and

(5) repeating steps (3)-(4) until a record with primary and secondary keys equal to said target primary and secondary keys is located, at which point said one record is identified as said target position, or until all records stored in said table have been identified as having primary and secondary keys greater than or less than said target primary and secondary keys, at which point said target position is identified as falling between a largest record having primary and secondary keys less than said target primary and secondary keys and a smallest record having primary and secondary keys greater than said target primary and secondary keys.

29. The computer program of claim 28, further comprising instructions for:

adding a record to, deleting a record from, returning a record stored at, or returning a record stored after said target position.

30. The computer program of claim 28, wherein said one or more records of said multikeyed table are sorted first by primary key order then by secondary key order.

31. The computer program of claim 28, wherein said one or more records are indexed only by primary and secondary keys.

32. The computer program of claim 28, further comprising instructions for reading data from said target position and comparing said primary and secondary keys from said target position against said target primary and secondary keys entered in step (1).

33. The computer program of claim 32, further comprising instructions for deleting a record from said target position only if said primary and secondary keys read from said target position are equal to said target primary and secondary keys entered in step (2).

34. The computer program of claim 32, further comprising instructions for adding a record to said target position only if said primary and secondary keys read from said target position are not equal to said target primary and secondary keys entered in step (2).

35. A computer program embodied on a computer-readable medium for identifying a target position in a multikeyed table, wherein said table is implemented in a personal digital assistant and comprises one or more records with each record comprising a plurality of fields, wherein one field of said plurality of fields is designated as a primary key and at least one additional field of said plurality of fields is designated as a secondary key, and wherein said primary and secondary keys of each record are used in ordering said records, said computer program comprising instructions for:

(1) receiving target primary and secondary keys for identifying said target position;

(2) identifying said target position by;

(a) selecting one record from said table according to a selection process;

()b) comparing and indicating whether said target primary and secondary keys are greater than, less than, or equal to the primary and secondary keys of said one record;

(c) refining said selection process, if said target primary and secondary keys are not equal to the primary and secondary keys of said one record, by using said indication of whether said target primary and secondary keys are greater than or less than said primary and secondary keys of said one record;

(d) identifying said one record as occupying said target position if said target primary and secondary keys are equal to the primary and secondary keys of said one record; and

(e) repeating steps (a)-(c), if said target primary and secondary keys are not equal to the primary and secondary keys of said one record, until all records have been retrieved and compared with said target primary and secondary keys, at which point said target position is identified as falling between a largest record having primary and secondary keys less than said target primary and secondary keys and a smallest record having primary and secondary keys greater than said target primary and secondary keys.

36. The computer program of claim 35, wherein said selection process of step (a) comprises a binary sorting routine.

37. A system for managing a information on a personal digital assistant, said system comprising:

means for executing an application which utilizes a multikeyed table for maintaining a sorted list of records on said personal digital assistant, wherein each record of said sorted list of records is capable of storing information and comprises a plurality of fields, wherein one field of said plurality of fields is designated as a primary key and at least one additional field of said plurality of fields is designated as a secondary key; and

means for receiving a target record to be added, deleted, or manipulated within said table and comparing primary and secondary keys of said received target record to be added, deleted, or manipulated with primary and secondary keys of a record retrieved from said table.

38. The system of claim 37, further comprising means for repeating said sorting until a record having primary and secondary keys equal to said primary and secondary keys of said record to be added, deleted, or manipulated is identified, or until all records in said table are identified as having primary and secondary keys greater than or equal to said primary and secondary keys of said record to be added, deleted, or manipulated.

39. The system of claim 37, wherein said means for comparing comprises means for indicating whether primary and secondary keys of said record to be added, deleted, or manipulated are greater than, less than, or equal to the primary and secondary keys of said record retrieved from said table.

40. A system for identifying a target position in a multikeyed table, wherein said table is implemented in a personal digital assistant and comprises one or more records with each record comprising a plurality of fields, wherein one field of said plurality of fields is designated as a primary key and at least one additional field of said plurality of fields is designated as a secondary key, and wherein said primary and secondary keys of each record are used in ordering said records, said system comprising:

means for receiving target primary and secondary keys for identifying said target position;

means selecting and returning one record stored in said table;

means for receiving said one record selected by said means for selecting and returning;

means for comparing and indicating whether said target primary and secondary keys are greater than, less than, or equal to the primary and secondary keys of said one record; and

means for repeating said receiving and said comparing and indicating until a record with primary and secondary keys equal to said target primary and secondary keys is located, at which point said one record is identified as said target position, or until all records stored in said table have been identified as having primary and secondary keys greater than or less than said target primary and secondary keys, at which point said target position is identified as falling between a largest record having primary and secondary keys less than said target primary and secondary keys and a smallest record having primary and secondary keys greater than said target primary and secondary keys.

41. The system of claim 40, further comprising means for adding a record to, deleting a record from, returning a record stored at, or returning a record stored after said target position.

42. The system of claim 40, wherein said one or more records of said multikeyed table are sorted first by primary key order then by secondary key order.

43. The system of claim 40, wherein said one or more records are indexed only by primary and secondary keys.

44. The system of claim 40, further comprising means for reading data from said target position and comparing said primary and secondary keys from said target position against said target primary and secondary keys.

45. The system of claim 44, further comprising means for deleting a record from said target position only if said primary and secondary keys read from said target position are equal to said target primary and secondary keys.

46. The system of claim 44, further comprising means for adding a record to said target position only if said primary and secondary keys read from said target position are not equal to said target primary and secondary keys.

47. A system for identifying a target position in a multikeyed table, wherein said table is implemented in a personal digital assistant and comprises one or more records with each record comprising a plurality of fields, wherein one field of said plurality of fields is designated as a primary key and at least one additional field of said plurality of fields is designated as a secondary key, and wherein said primary and secondary keys of each record are used in ordering said records, said system comprising:

means for receiving target primary and secondary keys for identifying said target position;

means for identifying said target position by;

(a) selecting one record from said table according to a selection process;

(b) comparing and indicating whether said target primary and secondary keys are greater than, less than, or equal to the primary and secondary keys of said one record;

(c) refining said selection process, if said target primary and secondary keys are not equal to the primary and secondary keys of said one record, by using said indication of whether said target primary and secondary keys are greater than or less than said primary and secondary keys of said one record;

(d) identifying said one record as occupying said target position if said target primary and secondary keys are equal to the primary and secondary keys of said one record; and

(e) repeating steps (a)-(c), if said target primary and secondary keys are not equal to the primary and secondary keys of said one record, until all records have been retrieved and compared with said target primary and secondary keys, at which point said target position is identified as falling between a largest record having primary and secondary keys less than said target primary and secondary keys and a smallest record having primary and secondary keys greater than said target primary and secondary keys.

48. The system of claim 47, wherein said selection process of step (a) comprises a binary sorting routine.