US5603022A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data compression system and method representing records as differences between sorted domain ordinals representing field values
Assignee: University of Michigan (System)
•
Filing: 1994-09-23
•
Granted: 1997-02-11
•
Expires: 2014-09-23
Abstract
Abstract Records in the relational database are converted into ordinal numbers. The numbers are then sorted by a predetermined ordering rule. Next, for each record, the difference between the number and the preceding number is computed and this difference is then used to represent that record. The compression technique results in highly compressed data that can still be handled by conventional relational database software for record insertion, deletion and other standard database operations.
Inventors
- 👤 Wee-Keong Ng
- 👤 Chinya V. Ravishankar
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 13:15
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2246; G06F16/28; G06F16/284; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
174 words
A method for compressing a database consisting of a plurality of tuples, each tuple having predetermined fields arranged according to a predetermined schema, the method comprising: mapping said tuples according to predetermined mapping rules such that said fields are mapped to domain ordinals representing field values to thereby define a plurality of domain ordinal tuples; sorting domain ordinal tuples according to predetermined sorting rules; converting said domain ordinal tuples into a head tuple and a table of difference values by subtracting a domain ordinal from its succeeding neighbor; defining a data block of a predetermined size and performing said converting step on groups of domain ordinal tuples to fit said defined data block size, wherein said predetermined size of said data block is determined to physically conform to the data block size of a storage system used to store said database; storing said head tuple and said table of difference values according to predetermined storing rules, the stored head tuple and the stored table of difference values being a compressed representation of said database.
Claim 2
Independent Claim
174 words
A method for compressing a database consisting of a plurality of tuples, each tuple having predetermined fields arranged according to a predetermined schema, the method comprising: mapping said tuples according to predetermined mapping rules such that said fields are mapped to domain ordinals representing field values to thereby define a plurality of domain ordinal tuples; sorting domain ordinal tuples according to predetermined sorting rules; converting said domain ordinal tuples into a head tuple and a table of difference values by subtracting a domain ordinal from its succeeding neighbor; defining a data block of a predetermined size and performing said converting step on groups of domain ordinal tuples to fit said defined data block size, wherein said predetermined size of said data block is determined to physically conform to the data block size of a storage system used to store said database; storing said head tuple and said table of difference values according to predetermined storing rules, the stored head tuple and the stored table of difference values being a compressed representation of said database.
Claim 3
Dependent Claim
33 words
The method of claim 1 further comprising rearranging said plurality of domain ordinal tuples according to predetermined rearrangement rules to thereby alter the schema of said domain ordinal tuples from said predetermined schema.
Claim 4
Dependent Claim
20 words
The method of claim 1 wherein said sorting step is performed by a sorting operation upon said domain ordinal tuples.
Claim 5
Dependent Claim
35 words
The method of claim 1 wherein said database employs a primary index key, said method further comprising using said head tuple and said difference values as the key for the primary index of said database.
Claim 6
Dependent Claim
22 words
The method of claim 2 wherein said rearrangement rules alter the schema such that the fields are rearranged by ascending domain size.
Claim 7
Dependent Claim
21 words
The method of claim 1 wherein said sorting rules produce a table of domain ordinal tuples sorted in ascending mixed-radix order.
Claim 8
Dependent Claim
51 words
The method of claim 1 wherein said database employs a primary index key and wherein said head tuple and said difference values are represented as mixed-radix number, and using said mixed-radix number representations for said head tuple and said difference values as the key for the primary index of said database.
Claim 9
Dependent Claim
19 words
The method of claim 1 further comprising concealing said head tuple to thereby conceal the contents of said database.
References Cited (Backward Citations)
US4315105A
Cited
US4361893A
Cited
US4464650A
Cited
US5333313A
Cited
US5412384A
Cited
US5481472A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-02-11 | 2000-08-12 | 2001-02-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-02-11 | 2004-08-12 | 2005-02-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-02-11 | 2008-08-12 | 2009-02-11 | $7700.00 | Window Closed / Lapsed |