Databases

• US 6,169,990 B1
• Filed: 10/26/1998
• Issued: 01/02/2001
• Est. Priority Date: 03/02/1996
• Status: Expired due to Term

• Current Assignee: University of Strathclyde
• Original Assignee: University of Strathclyde
• Inventors: Wilson, John Nugent, Cockshott, William Paul, McGregor, Douglas Robert
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): CHEUNG, MARY DA ZHI WANG
• Application Number:
  US09/142,018
• Time in Patent Office: 799 Days
• Field of Search: 707/100, 707/101, 707/102, 707/103, 707/509, 711/100
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A computer database for storing information in tuple form wherein each tuple comprises fields with corresponding fields in the tuples constituting a column, generates for each data domain a domain dictionary which matches each distinct data value in that domain with a corresponding distinct token, and stores each domain dictionary. A tokenised store for each data field column is created. All of the tokens for a domain are initially of the same size being substantially the minimum size necessary to provide the required plurality of distinct tokens for initialize size of that domain. When further tuples are received for storage for each field of the tuple, the data value is compared in the corresponding domain dictionary. If no match is found, a new token within the existing token size is generated and added to the domain dictionary, but if all tokens within the existing token size are utilised a new token is generated having a size which is at least 1-bit wider than previously, such broadened token being entered into a new tokenised store for that column.

Claims

1. A method of constructing a computer database for storing in compressed form information comprising a plurality of tuples, wherein each tuple comprises a data value in each of a plurality of fields with corresponding fields in the tuples constituting a column, the method comprising the steps of:

(a) defining a plurality of domains;

(b) receiving said information in an uncompressed form and assigning each data value into a corresponding domain, wherein data values in the same field are assigned to the same domain;

(c) generating for each domain a domain dictionary which matches each distinct data value assigned to that domain with a corresponding distinct token, and storing each domain dictionary in a domain-dictionary store;

(d) creating a tokenised store for each column and storing therein the corresponding distinct token for each pertaining field data value;

wherein the method further comprises arranging that;

(e) all of the tokens for a domain are initially of the same size and that size being substantially the minimum size necessary to provide the required plurality of distinct tokens for the initial size of that domain;

(f) when further tuples are received for storage for each field of the tuple the data value is compared in the corresponding domain dictionary and if no match is found a new token within the existing token size is generated and added to the domain dictionary but if all tokens within the existing token size are utilised a new token is generated having a size which is at least 1-bit wider than previously, such broadened tokens being entered into a new tokenised store for that column; and

(g) the tokenised stores and the domain dictionary stores are arranged in the computer memory as respective data blocks or respective sets of data blocks which are independently relocatable within the computer memory whereby ones of the data blocks may be modified in size to accommodate such broadened tokens without requiring consequential modifications to be made to others of the data blocks.

2. A method as claimed in claim 1, wherein when a broadened token is generated for a particular field all existing tokens within the pertaining column are broadened by the same amount and the corresponding tokenised stores are enlarged.

3. A method as claimed in claim 1, wherein when a broadened token is generated for a particular field only the new token and subsequent new tokens are broadened and such broadened tokens are entered into a new tokenised store for the pertaining column.

4. A method as claimed in claim 1, wherein the constructed database forms a portion of a larger database which is under construction, and wherein when the size of a tokenised store for a column reaches a predetermined threshold size a new additional tokenised store for that column is created using the domain dictionary created for the first tokenised store for that column.

5. A method as claimed claim 1, wherein the information is received as a bulk-load and the method set forth in any preceding claim is first applied and thereafter a set of hash access tables is generated.

6. A method as claimed in claim 5, wherein the set of hash access tables includes a composite hash table to which all or several fields contribute to enable a composite indexing method to be used for accessing the database.

7. A computer database when constructed in accordance with the method of claim 1.