Organising data in a database

• US 7,577,673 B2
• Filed: 02/19/2002
• Issued: 08/18/2009
• Est. Priority Date: 02/26/2001
• Status: Expired due to Fees

• Current Assignee: Bernard Consulting Limited
• Original Assignee: Coppereye Limited
• Inventors: Pauly, Duncan Gunther
• Primary Examiner(s): Breene, John E
• Assistant Examiner(s): MYINT, DENNIS Y
• Application Number:
  US10/469,123
• Publication Number:
  US 20040073559A1
• Time in Patent Office: 2,737 Days
• Field of Search: 706/55, 706/20, 707/200, 707/101, 707/100, 707/5, 370/395.64
• US Class Current: 1/1
• 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 computer-implemented method of organizing storage of data in a database, using a data processor, in which conclusion sets for the database are arranged in a hierarchical structure with a plurality of levels of significance including a first level of significance and a very least significant level of significance, the conclusion sets storing data which matches search criteria or pointers which point to the location of the data which matches the search criteria, and in which the conclusion sets are arranged such that items are inserted into a selected conclusion set at the 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, and wherein following migration of the contents from the selected conclusion set, further insertions can be made into that conclusion set, wherein the conclusion sets are distributed throughout a decision graph of the database, the decision graph comprising a plurality of branch nodes at which a search key is matched with decision criteria in order to define which decision path should be taken through the decision graph, each conclusion set being reached by one, and only one, decision path through the decision graph;

wherein conclusion sets are formed at some but not all of the branch nodes; and

wherein the branch nodes at which conclusion sets are not formed define decision paths extending between the branch nodes at which conclusion sets are formed, in which the decision graph is constructed so as to maintain a specified inter conclusion set distance throughout the majority of the decision graph, and in which the decision graph comprises a plurality of branch nodes., and wherein the decision graph is constructed so as to maintain a specified inter conclusion set distance defined by an integer Q throughout the majority of the decision graph by forming a conclusion set at every other branch node if Q=1, at every second branch node if Q=2, and at every n^th branch node if Q=n, wherein Q is greater than zero.

2. A method as claimed in claim 1, 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.

3. A method as claimed in claim 1, in which conclusion sets having a hierarchical significance above a predetermined value are stored, in use, in fast memory.

4. A method as claimed in claim 1, 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.

5. A method as claimed in claim 1, in which the contents of a conclusion set are migrated en masse.

6. A method as claimed in claim 1, in which once a given conclusion has a predetermined number of entries in it, its contents are migrated to its immediately subordinate conclusion sets.

7. A method as claimed in claim 1, wherein when querying the database for data or pointers which match a search criterion, each conclusion set in a single path running to the very least significant conclusion set must be queried, since the data or pointers may reside at any level of the hierarchy.

8. A method as claimed in claim 1, wherein the contents of the selected conclusion set are migrated to subordinate conclusion sets by following the decision graph.

9. A method as claimed in claim 1, wherein the decision graph is constructed so as to maintain a specified inter conclusion set distance by:

establishing a first conclusion set at the first level of significance (level

     1);

establishing one or more temporary conclusion sets; and

migrating the contents of the first conclusion set to the temporary conclusion set(s) until such time as a second conclusion set is established at the specified inter conclusion set distance from the first conclusion set, whereupon the temporary conclusion set(s) are removed and their contents are moved to the second conclusion set.

10. A computer-implemented database encoded in a computer storage medium, in which conclusion sets of the database are arranged in a hierarchical structure with a plurality of levels of significance including a first level of significance and a very least significant level of significance, the conclusion sets storing data which matches search criteria or pointers which point to the location of the data which matches the search criteria, 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, wherein following migration of the contents from the selected conclusion set, further insertions can be made into that conclusion set, wherein the conclusion sets are distributed throughout a decision graph of the database, the decision graph comprising a plurality of branch nodes at which a search key is matched with decision criteria in order to define which decision path should be taken through the decision graph, each conclusion set being reached by one, and only one, decision path through the decision graph;

wherein conclusion sets are formed at some but not all of the branch nodes; and

wherein the branch nodes at which conclusion sets are not formed define decision paths extending between the branch nodes at which conclusion sets are formed, in which the decision graph is constructed so as to maintain a specified inter conclusion set distance throughout the majority of the decision graph, and in which the decision graph comprises a plurality of branch nodes, and wherein the decision graph is constructed so as to maintain a specific inter conclusion set distance defined by an integer Q throughout the majority of the decision graph by forming a conclusion set at every other branch node if Q=1, at every second branch node if Q=2, and at every n^th branch node if Q=n, wherein Q is greater than zero.