Organising data in a database

• US 20040073559A1
• Filed: 08/26/2003
• Published: 04/15/2004
• Est. Priority Date: 02/26/2001
• Status: Active Grant

• Current Assignee: Bernard Consulting Limited
• Original Assignee: Coppereye Limited
• Inventors: Pauly, Duncan Gunther
• Granted Patent: US 7,577,673 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A database is provided in which conclusion sets (20, 22, 24, 26, 28 and 30) are divided into a hierarchical series of levels (level 1, level 2, level 3). Data is added to a conclusion set at the first level (level 1) until such time as that conclusion set is full. Data is then migrated from the conclusion set (20) to its subordinate conclusion sets (24, 26) therefore reducing the amount of disc access required to add data to the database since multiple entries are migrated in relatively few disc access operations.

Claims

1. A method of organising storage of data in a database (2), in which conclusion sets (20, 24, 26, 28, 30;

40;

50, 60) for the database are arranged in a hierarchical structure, and in which the conclusion sets are arranged such that items are inserted into a selected conclusion set at a first level of significance (level

     1) until the number of items reaches a threshold value for the selected conclusion set, and then the contents of the selected conclusion set are migrated to subordinate conclusion sets, thereby emptying the selected conclusion set.

2. A method as claimed in claim 1, in which each conclusion (20, 24, 26, 28, 30) set, has zero, one or two immediately subordinate conclusion sets.

3. A method as claimed in claim 1 or 2, in which, during migration the data in the selected conclusion set is compared with a search criterion in order to select which of the immediately subordinate conclusion sets an entry is transferred to.

4. A method as claimed in claim 3, in which the database includes a decision graph and the search criterion is effectively an extension of the decision graph.

5. A method as claimed in any one of the preceding claims, in which the hierarchical structure of conclusion sets is arranged into a layered structure.

6. A method as claimed in claim 5, in which the layered structure comprises L levels, with each conclusion set in the 1st to (L−

1)th level having two immediately subordinate conclusion sets in the 2nd to Lth level, respectively.

7. A method as claimed in claim 6, in which once a given conclusion set in the Nth level, where N is an integer from 1 to (L−

1) has a predetermined number of entries in it, its contents are migrated to it'"'"'s immediately subordinate conclusion sets.

8. A method as claimed in any one of the preceding claims, in which conclusion sets having a hierarchical significance above a predetermined value are stored, in use, in fast memory.

9. A method as claimed in claim 1, in which the conclusion sets (40, 50, 60) are distributed through a decision graph of the database.

10. A method as claimed in claim 1 or 9, in which the decision graph is constructed so as to maintain a specified inter conclusion set distance throughout the majority of the decision graph.

11. A method as claimed in claim 9 or 10, in which during migration of data from a conclusion set, the data is migrated to subordinate conclusion sets on the basis of the specific data content.

12. A method as claimed in claim 1, 9, 10 or 11 in which the contents of a conclusion set are migrated en masse.

15. A computer program product for causing a data processor to implement the method of any one of claims 1 to 12.

13. A database in which conclusion sets of the database are arranged in a hierarchical structure, and in which the conclusion sets are arranged such that items are inserted into a selected conclusion set at a first level of significance until the number of items reaches a threshold value for the selected conclusion set, and then the contents of the selected conclusion set are migrated to subordinate conclusion sets, thereby emptying the selected conclusion set.

14. A database as claimed in claim 13, in which the conclusion sets (40, 50, 60) are distributed throughout a decision graph.