Method and system for compressing a data stream in a database log so as to permit recovery of only selected portions of the data stream

• US 5,956,504 A
• Filed: 03/04/1996
• Issued: 09/21/1999
• Est. Priority Date: 03/04/1996
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Sudarshan, Sundararajarao, Jagadish, Hosagrahar Visvesvaraya, Kanneganti, Ramarao
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Homere, Jean R.
• Application Number:
  US08/607,987
• Time in Patent Office: 1,296 Days
• Field of Search: 395/612, 395/618, 395/617, 395/620, 395/182.13, 395/183.11
• US Class Current: 1/1
• 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: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

The invention relates to a system for maintaining a log of incoming records for a database system. Seek points are inserted into the compressed data log in a manner that allows recovery to start from a specified point without a need for decompressing earlier portions of the log. The initial block of data is used as the compression dictionary. A new compression sequence using the same initial compression dictionary is started at each seek point.

Claims

1. A method of compressing a data stream so as to permit decompression recovery of only selected portions of the data stream, comprising the steps of:

establishing an initial compression dictionary consisting of initial data in said data stream;

compressing the data stream according to a moving window dictionary starting with said initial compression dictionary by inserting into the data stream the location and length of any exact matches with data sequences in said moving window dictionary;

establishing seek points to identify the start of data blocks in the data stream set for selective recovery decompression;

using said initial dictionary for compression starting at each seek point so that a selected one of said data blocks can be recovered by decompression starting at a seek point and using said initial compression dictionary.

2. A method for incremental compression of data blocks in a data stream, comprising the steps of:

establishing data blocks in the data stream for selected recovery with a seek point identifying the start of each of said data blocks;

establishing an initial dictionary consisting of initial data in the data stream;

compressing each data block according to a moving window dictionary starting with said initial dictionary; and

decompression recovery of selected data blocks starting at one of said seek points and using said initial dictionary.

3. A database system comprising:

means for receiving incoming data for storage in records of the database;

means for compressing said incoming data as received to provide compressed data; and

means for storing said compressed data on a non-viable medium to provide a journal for said incoming data prior to processing said incoming data in the database system;

whereby, in the event of a power failure or service interruption, selected portions of said incoming data can be recovered by reading from said medium and decompressing selected portions of said stored compressed data.

4. A system according to claim 3 further comprising means for establishing an initial dictionary from the incoming data and for using a moving window dictionary starting with said initial dictionary to compress said incoming data.

5. A system according to claim 4 further comprising means for establishing seek points identifying the location of different data blocks and wherein said means for compressing incoming data compresses data using the same initial dictionary at each such point.