System and method for multirecord compression in a relational database

• US 6,006,232 A
• Filed: 10/21/1997
• Issued: 12/21/1999
• Est. Priority Date: 10/21/1997
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Lyons, Kenneth Brent
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): Colbert, Ella
• Application Number:
  US08/954,965
• Time in Patent Office: 791 Days
• Field of Search: 707/103, 707/1, 707/100, 707/2, 707/101, 711/112, 341/106, 341/87
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

The invention is a system and method for database compression which creates partial indexing into compressed sub table blocks of databases. Table rows with the same or related indexing parameters are grouped as "sub-table blocks" and are stored as compressed binary objects, with the indexing fields stored in the same row, external to the binary block. The binary object expands to multiple database rows when accessed via the sub table block interface, thus forming a hierarchical, pre-joined database organization. Mechanisms are provided for creating, accessing, and manipulating the data blocks, and a date-based versioning mechanism. The compression employed is the known Vdelta package, which operates at a byte level to provide a useful compromise between speed and compression efficiency, even for relative short compression blocks. In realistic tests, the I/O time gained through compression results in a time saving which exceeds the processing penalty. The overall compression ratio is data dependent, but in a realistic test it averages about 4.

Claims

1. A method of processing information, comprising the steps of:

a) constructing a plurality of binary objects, each binary object including portions of multiple records of a first unnormalized database table, the multiple records being related by shared attribute values;

b) compressing each of the binary objects constructed in step (a) independently, in a manner that allows the exact reconstruction of original data; and

c) constructing a second database table which is still unnormalized from the binary objects constructed in step (a), each row of the second database table comprising the shared attribute values and a corresponding compressed binary object constructed in step b), wherein the second database table stores the shared attribute values and information required to access the compressed binary objects.

2. The method of claim 1, further comprising the step of including a subset of the shared attribute values in each binary object.

3. The method of claim 1, further comprising the step of constructing indices using the shared attribute values.

4. The method of claim 1, further comprising the steps of compressing the binary objects and decompressing the binary objects.

5. The method of claim 1, further comprising the step of providing an application programming interface to access rows of the binary objects.

6. The method of claim 1, wherein the records of the first unnormalized database themselves contain one or more further binary objects representing multiple rows of a database from which the first unnormalized database is derived.

7. The method of claim 1, further comprising the step of storing the first unnormalized database table and the second database table in a storage medium including a hard disk or an electronic memory.

8. The method of claim 1, further comprising the step of recording version information in the second database table.

9. The method of claim 5, further comprising the step of outputting the accessed rows of the binary objects, the binary objects being compressed or not compressed.

10. The method of claim 9, wherein the outputting step outputs decompressed rows when the binary objects are compressed.

11. The method of claim 9, wherein the the outputting step outputs the accessed rows of the binary object over a network.

12. The method of claim 1, wherein the first unnormalized database table represents call detail information.

13. A system for processing information, comprising:

a first unnormalized database table;

a plurality of binary objects, the binary objects including portions of multiple records of the first unnormalized database table, the multiple records being related by shared attribute values;

a compression unit for independently compressing the binary objects so that the compressed binary objects can be exactly reconstructed into the binary objects; and

a second database table, comprising the binary objects, each row of the second database table comprising the shared attribute values and a corresponding compressed binary object, wherein the second database table stores the shared attribute values and information required to access the compressed binary objects.

14. The system of claim 13, wherein the compression unit independently compresses the binary objects and includes a subset of the shared attribute values in the compressed binary objects.

15. The system of claim 13, further comprising indices constructed using the shared attribute values.

16. The system of claim 14, further comprising a decompression unit for decompressing the compressed binary objects.

17. The system of claim 13, further comprising an application programming interface for accessing rows of the binary objects.

18. The system of claim 13, wherein the records of the source database themselves contain one or more further binary objects representing multiple rows of a database from which the first database is derived.

19. The system of claim 13, further comprising a storage medium including a hard disk or an electronic memory, the storage medium storing the first unnormalized database table and the second database table.

20. The system of claim 13, wherein the binary objects comprise version information.

21. The system of claim 17, further comprising an output unit for outputting the accessed rows of the binary objects as an output.

22. The system of claim 21, wherein the output comprises decompressed rows.

23. The system of claim 21, wherein the output comprises the accessed rows of the binary objects transmitted over a network.

24. The system of claim 13, wherein the first unnormalized database table represents call detail information.