Data compression system and method representing records as differences between sorted domain ordinals representing field values

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.

BACKGROUND AND SUMMARY OF THE INVENTION 
Many applications deal with large amounts of data organizable as tuples, an 
example of such applications being databases. As the amount of data to be 
dealt with by such applications increases, their performance becomes 
constrained by the speed at which data can be read or written. Such an 
application is said to be input-output (I/O) bound. Unfortunately, 
technological progress in the computing arena has produced dramatic 
improvements in all aspects except I/O. I/O-bound applications are 
therefore the hardest to design and manage. 
The usual approach when confronted with an I/O-bound application is to 
reduce the amount of I/O required. This goal may be realized sometimes by 
cleverly designing the application, so that it computes some of the data 
instead of reading it. However, this approach is limited in applicability 
and is often impossible to realize. A far more effective approach is 
usually to reduce the volume of data to be read by compressing it prior to 
I/O. The information content of the data is preserved, but the volume it 
occupies is greatly reduced. 
A number of approaches are available for compressing data. Unfortunately, 
they are generally unsuitable for database-like applications, which 
require random access to data. Our method is specially designed to work 
for this class of applications. Most other existing methods assume that 
data are produced and consumed serially in a pipelined fashion. That is 
not always a valid assumption, and is definitely invalid in the database 
domain. 
The present invention provides a method to compress and store data in 
relational databases that overcomes some of the deficiencies of prior art 
systems. In our method, each record R.sub.i is converted to a number 
n.sub.i. These numbers (or records) are next sorted according to some 
predetermined ordering rule (usually ascending or descending order). Next, 
for each record R.sub.i, we compute the difference d.sub.i between the 
number ni and the preceding number n.sub.i-1. Each such record R.sub.i is 
then represented by the corresponding difference d.sub.i. 
This method exploits the characteristic that records share common field 
values. Arranging them in this fashion makes explicit the amount of 
similarity among records; records that are closer together have more 
common field values. Such commonality represents a redundancy that can be 
eliminated by capturing the distances among records. Thus, the set of 
records are replaced by their distances. 
The invention has the following advantages: (1) differences between records 
are smaller than the records themselves, so using differences requires 
fewer bits of storage, achieving compression; (2) the original records can 
all be recovered, so information is not lost; (3) the encoding and 
decoding processes can be localized, so that only relevant records desired 
in a database query need be decoded and processed, avoiding costly 
decoding of the entire table when only a small subset of records are 
needed; (4) the method continues to support standard database operations 
such as insertions, deletions and updates; and (5) the encoding and 
decoding processes are efficient so that fast retrieval is possible.

DESCRIPTION OF THE PREFERRED EMBODIMENT 
Encoding/Decoding Algorithm 
We first define some terminology. A database is relational if the data it 
contains is tabular in form. A record or tuple is a row in such a table. 
Each record represents a real-world entity (e.g., an employee, a 
department, an auto part, and so on) and comprises a fixed number of 
fields that contain information relevant to the entity. Thus, a tuple 
(record) representing an employee may have social security numbers as a 
field. The term relation is synonymous with the term table. 
Our method and apparatus involves the reorganization of records at the 
physical level (the disk-storage level) of a database. It exploits 
relationships among records to compress and store them. The encoding 
process, which we call Tuple Differential Coding (TDC), proceeds in 
several steps: (1) each field value is mapped into a number, thus 
transforming a record into a collection of numeric fields, (2) each record 
is converted to a single number and the table of records is sorted in some 
predetermined order, (3) each record is replaced with the numerical 
difference between itself and the preceding record. The result of TDC is a 
single head tuple and a difference table, as will be explained further. 
The above steps are elaborated below. Throughout this section and this 
disclosure, we shall be using the relation in the following example to 
illustrate the concepts involved. 
EXAMPLE 1 
Table (a) in FIG. 1 shows a relation R with five field domains A1, A2, A3, 
A4, A5 denoting the employee number, department, job title, insurance 
grade and income in thousands respectively. The size of each domain, i.e., 
the number of different field values, is 128, 4, 4, 4, and 128 
respectively. Table (b) shows the same relation, except that the field 
values have all been mapped to numbers. This is usually the raw form in 
which a statistical data set is available; i.e., a file of numerals 
corresponding to contiguous records. We preserve tuple identity by 
displaying them as individual tuples. The relation in the figure has been 
partitioned into blocks. 
Field Value Mapping (Step 1) 
The ability to map every domain systematically to a set of integers is 
fundamental to TDC. This seems a tall order because certain field domains 
appear unmappable at first blush, an example being the address domain. 
However, the following explains how this mapping is possible. 
Descriptive Fields 
Fields A2, A3, A4 in Table (a) of FIG. 1 are descriptive domains. These 
non-numeric field domains are usually used inqueries to set certain 
criteria for retrieving tuples. An example is: .sigma..sub.dept=marketing 
(R), which retrieves all tuples whose department field is marketing. The 
domains of these fields are usually known in advance. Hence, mapping them 
is easy as the domain size places a limit on the number of possible values 
the field may assume. 
Numeric Fields 
Numeric domains are usually the target of queries, i.e., they constitute 
the results of queries. Field A5 in Table (a) is a numeric domain. Since 
the field values of these domains are numeric, an automatic upper bound is 
already set on the domain size. Consider a five character income field. 
The range of values is from 0 to 99999. Clearly, each of the fields in the 
range is already mapped to an integer. So numeric domains are naturally 
mapped. 
Variable-Length Fields 
Fields like address and name are seemingly difficult to map. There are 
several approaches to handling variable-length fields. One possible 
approach is to use the following two steps: (1) fix a maximum length for 
the characters constituting the field; any field value that is greater 
than the maximum length is truncated, and (2) establish a sub-domain for 
each character up to the maximum length. The code of a field value is then 
the radix m integer where m is the size of these character domains. 
Example 2 below illustrates this concept. 
EXAMPLE 2 
Consider the following name occurring in a maximum space of twenty 
characters: 
EQU JAMES.hoarfrost.K..hoarfrost.MADISON.hoarfrost..hoarfrost..hoarfrost..hoarf 
rost. 
where .hoarfrost. represents an empty space. Let each character be a 
domain. Since the number of possible characters is no more than 256 
(including the special characters), we can generously set 256 as the size 
of each domain. Let the ordinal position of a character within the domain 
be its code. Then the code for the entire name is simply the name 
expressed as a radix 256 number. For instance, let the integer code for 
the field James K. Madison be k. Then, 
##EQU1## 
However large k may be, it is a string of bits in binary representation, 
and is no different in principle from James K. Madison as characters. We 
shall see in the next section that every tuple is bit-compacted so that 
the numeric field values comprising the tuple are squeezed together. After 
compaction, a tuple may be taken as a string of bits; its constituent 
fields may be ignored. 
Record mapping (Step 2) 
In this subsection, we describe the mapping and differencing method more 
formally. There are two main concepts discussed in this section: record 
mapping and field ranking. 
First, we explain how to treat each tuple as a number. Commonly used number 
representation systems are based on the assumption of a fixed radix or 
base b. Digits are always in the range 0, . . . (b-1). For example, the 
decimal system uses a radix of 10, with digits 0 . . . 9, and the binary 
system uses a radix of 2, with digits 0, 1. However, it is also possible 
to use mixed-radix systems in which the base varies for each digit. In the 
preferred embodiment each tuple is treated as a mixed radix number, with 
the value in each field representing a digit. The radix or base for each 
such digit is the size of the corresponding field domain (the number of 
possible values for that field). 
Second, we discuss the concept of field ranking for tuples. The information 
content of a record is unaffected by the order in which its fields appear. 
Thus, fields may be permuted arbitrarily. However, the order in which 
fields appear has a very significant effect on the compression achievable 
by sorting and differencing the tuples. Thus, the preferred embodiment 
rearranges the fields in records, as described below, to achieve the 
maximum compression. 
The remainder of this subsection is a more formal description of the 
concepts outlined above. The next subsection describes how to support 
standard database operations using our method. 
A relation scheme R=((A,A2, . . . ,A.sub.n)) is the Cartesian product of 
the set of fields, i.e., R=A.sub.1 .times.A.sub.2 .times.. . . 
.times.A.sub.n, It is an n-dimensional space where each tuple is a point 
in the space. A relation R is a subset of R, i.e., R is a set points in 
the n-dimensional space. Tuples in a relation exhibit cluster locality in 
that tuples share certain fields with other tuples. For instance, one 
finds many people (tuples) belonging to the same department (field) or 
sharing having the same job-title (field) in an employee relation. 
Geometrically, tuples form clusters in the n-dimensional space. In order 
to map a record, which is now a collection of numbers, into a numeric 
number, we need (1) a field ranking rule and (2) a tuple ordering rule. 
Tuple Ordering Rule 
All points in R may be totally ordered via an ordering rule. One example is 
the lexicographical order defined by function .phi.:R.fwdarw.N.sub.R, 
where N.sub.R ={0,1, . . . , .parallel.R.parallel.-1} and 
##EQU2## 
for all (a.sub.1, a.sub.2, . . . , a.sub.n) .epsilon.R. A tuple is 
generally enclosed in angle brackets. When used as an argument of a 
function, the angle brackets are omitted when no confusion arises. The 
inverse of .phi. is defined as: 
EQU .phi..sup.-1 (e)=(a'.sub.1, a'.sub.2, . . . , a'.sub.n) (A.2) 
for all e .epsilon.N.sub.R and i=1,2 . . . , n-1, 
##EQU3## 
where a.sub.0.sup.r =e and a.sub.n.sup.' =a.sub.n-1.sup.r. 
Given a tuple t .epsilon.R, .phi. converts it to a unique integer .phi.(t) 
which represents its ordinal position within the R space. Given two tuples 
t.sub.i,t.sub.j .epsilon. R, we may define a total order based on .phi., 
denoted by t.sub.i &lt;t.sub.j, such that t.sub.i precedes t.sub.j if and 
only if .phi.(t.sub.i)&lt;.phi.(t.sub.j). 
Field Ranking Rule 
In relational database, a tuple is a collection of fields. The ordering of 
fields within a tuple is irrelevant to the definition of the tuple. 
However, this ordering or ranking is important in the context of the tuple 
ordering rule. For instance, the ranking of fields affect the result of 
Equation A.1. Therefore, the preferred embodiment uses both a tuple 
ordering rule and a field ranking rule to completely map a tuple into a 
numeric value. 
EXAMPLE 3 
Continuing with the example relation R in FIG. 1, the results of the 
subsequent operations of TDC is illustrated in FIG. 2. The tuples are 
lexicographically ordered into Table (a). Notice that the fields have been 
reordered under the permutation .tau. defined as: 
##EQU4## 
Column N.sub.R shows the ordinal numbers of the corresponding tuples. 
Differential Coding (Step 3) 
Due to the similarity among tuples of a cluster, one may capture the 
difference among these tuples instead of storing the tuples explicitly. 
Since these differences require less space for storage on average than the 
original tuples, compression is achieved. An example is given below: 
EXAMPLE 4 
Table (b) of FIG. 2 is the result of computing the differences between 
consecutive pairs of tuples in Table (a). For instance, the first 
difference 
##EQU5## 
Since the differences are numerically smaller than the tuples, they 
require fewer bytes of storage, as illustrated by the leading zeroes in 
each tuple difference. One may use a variety of methods, including 
run-length coding to encode these zeroes, so compression is achieved. For 
instance, the difference (0, 0, 0, 120,008) is coded into (3,120,008) 
where the three leading zeroes are replaced by the count 3. 
In essence, TDC performs differential coding on pairwise consecutive tuples 
of a relation that is totally ordered by a function .phi., hence giving 
rise to its name. The result of encoding is the set of differences as 
illustrated by column R.sub.d Of Table (b) in FIG. 2. The differences, 
which are stored in binary representation, are actually the bit-wise 
concatenation of the respective tuple-differences in binary 
representations. For instance, the first tuple-difference is: 
##EQU6## 
Supporting Standard Database Operations 
Since our compression method is designed for use at the lowest levels of a 
database system, it is important to understand how it might interact with 
other system components, and particularly, whether its use might require 
changes to their structure. In this section, we demonstrate that no 
re-thinking or re-design of other database system components is required, 
and that our method may be integrated cleanly with standard approaches to 
structuring them. In particular, we now consider how access mechanisms may 
be constructed on the coded tuples, and how the tuples may be retrieved 
and modified. We focus on demonstrating the use of our method with 
standard access and retrieval mechanisms. 
We have restricted our attention to these basic operations rather than to 
queries for several reasons: (1) All queries, simple or complex, reduces 
to a set of basic tuple operations. (2) The variety of queries is too 
large to derive a set of representative, typical queries. The feasibility 
of these operations on a compressed database carries over to more complex 
queries which are built upon them. 
Access method 
The record mapping, of which function .phi. (Equation A.1) is one instance, 
defines a clustering order among tuples. FIG. 3 shows the placement of the 
difference-tuples of Table (b) in FIG. 2 into 10 data blocks, 
corresponding to the demarcations shown in the table. 
Each block begins with a head tuple which is the numerically smallest tuple 
in the block. All tuples following the head tuple are difference tuples. 
Notice that when using run-length coding the leading zeroes of the 
difference tuples are replaced by a number indicating the counts of the 
number of leading zero (run-length coding). Thus, the first difference 
tuple (2,2,021,012) in block 1 may be decoded into (0,0,2,021,012). The 
head tuple can be arithmetically added (via mixed-radix addition) to the 
differences to derive the actual tuples. For instance, block 2 begins with 
head tuple (0,2,1,031,035) because the first difference tuple 
(0,0,1,007,010)=(0,2,2,038,045)-(0,2,1,031,035) (see Table(a) of FIG. 2). 
The purpose of starting a block with a head tuple is to restrict the scope 
of decompression to within a data block. If only a block is searched, the 
difference tuples may be decoded immediately without decompressing an 
preceding blocks. Hence, access is localized. 
In order to permit random access, an index scheme is constructed. FIG. 4 
shows an order-3 B.sup.+ tree index where A.sub.4 is the search key. 
Since the relation is physically clustered via .phi., the index is 
non-clustering and secondary. This explains the extra level of indirection 
provided by the buckets in the figure. Suppose we wish to execute 
.sigma..sub.A4=34 (R). Starting with the root index node, we follow the 
pointer to the last index node (36) since 34 is after the last key 29 in 
the root node. Following the first link in this index node, bucket 5 is 
reached, indicating that the tuple resides in disk block 9. The 
combination of head tuples and indices realize random localized access to 
a compressed database. 
For the other two techniques, the same mechanism is applicable. Assuming 
the tuples are ordered on some field A.sub.k, there is a key associated 
with each compressed data block. A tree index may then be defined upon 
A.sub.k. 
Tuple Insertion and Deletion 
How are tuple insertion and deletion supported in a compressed database? 
Suppose we wish to insert in our previous database the tuple 
t=(1,1,0,016,021), which differs from (1,1,0,016,020) in the last field 
value. We need a means of locating the block which contains tuples that 
are physically ordered in the neighborhood of t. We realize this by 
constructing an order-3 B.sup.+ tree index using .phi. as the search key, 
as shown in FIG. 3. Since .phi. orders the tuples physically, this is a 
primary index, which we call the basic index. Key comparison while 
traversing the index is accomplished by comparing entire tuples. With this 
index, data block 3 is found to be the candidate block for inserting t, 
and is updated as shown in FIG. 5. 
Notice that only tuples succeeding t are re-computed, and that the changes 
are confined to the affected block. For tuple deletion, the basic index is 
similarly used to locate the data block, and changes made within the 
block. Tuple modification may simply be defined as a combination of tuple 
insertion and deletion. 
In summary, standard database operations are the same even when the 
database is compressed. The only difference is that the search key of the 
primary index is the entire tuple. All other indices are non-clustering 
and secondary, as in standard databases. An advantage of a compressed 
database is that the storage requirements for the indices will be reduced 
because the number of data blocks for storing the database has been 
reduced by compression. Although we have illustrated the use of tree 
indices as the access mechanisms, we do not preclude the use of other 
methods such as hashing. 
Working Models 
We have implemented TDC and applied it to the compression of census data. 
The 1990 Public User Microdata Samples (PUMS) from the US Bureau of Census 
[9] contain records representing 5% and 1% samples of the housing units in 
the U.S. and of persons residing in them. The 5% PUMS comes in a set of 52 
ASCII text files with a total size of approximately 4 gigabytes, each 
corresponding to the samples taken from a state. 
With TDC, we achieve a compression ratio of approximately 80% consistently 
on each of the text files comprising the 1% PUMS. Let B and A.sub.TDC be 
the size of a text file before and after compression by TDC respectively. 
Then A.sub.TDC /B=0.2. With bit-compression on the text file alone, a 
compression ratio of approximately 70% is achieved. Let A.sub.bit be the 
size of the text file after it is bit-compressed. That is, A.sub.bit 
/B=0.3. We deduce that A.sub.TDC /A.sub.bit =0.2/0.3=0.66. Therefore TDC 
achieves a compression ratio of approximately 33% over the bit-compression 
method and reduces the size of the files to around 800 megabytes. 
We have also compressed the files using the Unix "compress" utility, which 
uses a variant of the Ziv and Lempel class of algorithms. We obtained a 
compression ratio of approximately 85%. Although this ratio is higher, we 
have noted above that LZ algorithms are unsuitable for database 
compression. The most important reason is that it is a global compression 
technique that is unable to support random tuple access and modification 
(including insertion and deletion) that are required for general database 
operations. 
From the foregoing, the TDC method of the invention provides a new method 
for compressing tables, i.e., data organizable as tuples. TDC achieves its 
objectives without violating any operational requirements. It exhibits the 
following features: 
Field mapping: Arbitrary field values may be mapped into numeric values. 
This step itself achieves compression. A record now becomes a collection 
of numbers. 
Tuple ordering and field ranking: A record may be mapped into a single 
numeric value. In order to do so, the collection of fields may be ranked, 
and a tuple ordering rule must be chosen. Thus, different mappings are 
available, depending on the field ranking and ordering rule chosen. 
Tuple differencing: A tuple may be represented as the numerical difference 
between itself and its preceding tuple. Since any two consecutive tuples 
share common fields, their numerical correspondences are close. Hence, 
their difference is numerically small, much smaller than the tuples 
themselves. With less storage required to store the difference, further 
compression is achieved. 
Localized access: By partitioning the differences into blocks, with each 
block beginning with a full tuple rather than a tuple difference, 
decompression is localized to within a disk block. This prevents the 
costly operation of decompressing the entire table when only a small 
portion of the table is accessed. 
Access methods: As TDC retains the tuple-structure within a table, 
conventional access methods may be used to provide random access to the 
compressed tuples, with little or no changes. 
While the presently preferred form of the invention has been described, the 
following are potential variants of the technique: 
(a) The difference relation may be represented in various different ways. 
For example, the differences may be expressed as tuples rather than as 
integers. Other innovative variants may be possible. 
(b) Variations are also possible in the lower-level representations for the 
difference relation. Different codes may be used to represent or store the 
numerical difference (or tuple difference). For example, if a 
variable-length code were used, the number of bytes allocated to store 
each difference could be indicated by a count field such that if the count 
value is x, then the number of bytes allocated is some function f(x). The 
function f(x) determines the semantics of the count field. There are two 
commonly used classes of f: linear and exponential. In the former case, 
f(x)=ax for some integer a. Generally, a=1 so that x gives the number of 
bytes directly. In the latter case, f(x) =a.sup.x for a=2,3, . . . . Other 
variants are possible. 
(c) There are many possible definitions for the field ranking and tuple 
ordering rule. Each potential combination gives rise to different a tuple 
mapping rule, which naturally affects the amount of achievable compression 
from tuple differencing. 
The invention is applicable to the compression and storage of very large 
databases where data are organizable as tables of tuples. During normal 
database operations, multiple accesses are made to the database where each 
access retrieves a large portion of the database, thus incurring many disk 
I/Os. The invention not only reduces the amount of I/Os, but also 
increases the efficiency of each I/O transfer because more data are 
fetched during each I/O. 
The invention is also suitable for reducing the size of very large database 
to so that it can be stored on a relatively inexpensive mass storage 
medium, such as a hard disk of a personal computer, so that the database 
may be made available to more users. 
Exemplary Computer-Implemented Software Embodiment 
The principles of the invention may be applied in a variety of database and 
computer software applications. The next section describes one possible 
software implementation. The software implementation comprises an encoding 
module which compresses data according to the principles of the invention. 
Naturally, the decoding module to decompress the data follows the 
described process in reverse. Also, while the invention has particular 
utility as a data compression system and method, it can also serve as a 
data encryption system and method, by hiding or encrypting the head tuple. 
Without access to the head tuple, the difference tables are useless in 
recovering the original table. 
FIG. 6 is the data and process flowchart of the encoding module. This 
figure shows how the encoding module of the invention interfaces with the 
relational database management system application 20. Examples of a 
relational database management system application 20 include Ingres, 
Oracle or SyBase. 
The encoding module may be made up of several lower level modules which 
will now be described. The first module, domain mapping module 24 has as 
its primary function the mapping of field values to domain ordinals. 
Module 24 requires two principal inputs: (1) table to be compressed 22; 
and (2) domain range for each table field. For variable length fields, 
additional information may be needed. The table to be compressed 22 will 
contain: the table name or some type of a table identifier; field names; 
and the values for each of those fields, namely field values. 
As described above, each field name has an associated domain value. This 
domain value specifies the number of possibilities of the values that a 
particular field can assume. The domain mapping module 24 determines the 
ordinal position of a particular field value within the field's domain. 
This module 24 produces the domain mapped table 26. The domain mapped 
table 26 comprises the table name/identifier, the field names, and the 
domain ordinal tuples. The domain mapped table 26 and the other 
intermediate tables which will be discussed below may be stored in memory 
if the tables are not too large. If the intermediate tables are too large 
to be stored in memory, then they can be stored on the hard drive. To 
further save room on the hard drive, each intermediate table can be 
deleted after it has served its appropriate function. 
After the domain mapped table 26 is produced, the field rearranging module 
28 alters the order of the fields within the table. Field rearrangement is 
based upon each field's domain value. One example may be that the field 
with the lowest domain value is placed first. The field with the next 
lowest domain value is placed second. This process continues until all the 
fields have been accordingly rearranged. The goal of the rearrangement 
process is to increase the likelihood of zero values being in the 
beginning fields for each tuple. As will be shown below, greater 
compression will occur for those tuples with the greater amount of leading 
zeros for a given tuple. The field rearranging module 28 outputs the 
result into the field rearranged table 30. 
Next, the tuple sorting module 32 sorts the tuples that are in the field 
rearranged table 30 based on each tuple's mixed radix value. A single 
mixed radix number is calculated for each tuple. The following pseudocode 
is one implementation method for producing the mixed radix value. The 
pseudocode below illustrates how to transform the domain ordinals of a 
single tuple into its mixed radix representation. There are five fields 
that have the following domain ordinal values. The first field has a 
domain ordinal value of 0; the second has a value of 0; the third a value 
of 3; the fourth a value of 32; the fifth has a value of 32. The domain 
values for each field within that tuple are as follows: 4; 4; 4; 128; 128. 
COMMENT: n=# of fields within a Table. 
n=5 
COMMENT: A.bigO is an array which contains the field's Domain Value. 
A.big(1)=4 
A.big(2)=4 
A.big(3)=4 
A.big(4)=128 
A.big(5)=128 
Comment: a.smallO is an array which contains the tuple's Domain Ordinals. 
a.small(1)=0 
a.small(2)=0 
a.small(3)=3 
a.small(4)=32 
a.small(5)=32 
______________________________________ 
sum = 0 
product = 1 
phi = 0 
FOR i = 1 TO n 
product = 1 
FOR j = (i + 1) TO n 
product = product * ABS(A.big(j)) 
NEXT j 
sum = sum + (a.small(i) * product) 
NEXT i 
phi = sum 
END 
______________________________________ 
The input values described above will generate the number 53,280, which is 
the single mixed radix representation of that entire tuple. The tuple 
sorting module 32 performs this type of calculation for each tuple within 
the field rearranged table 30. The tuples are then sorted according to 
their single mixed radix number in ascending order and placed in the 
tuple-sorted table 34. 
The TDC calculating module 36 calculates the tuple differences within a 
predefined block. Thus the TDC calculating module 36 requires two inputs: 
the first being the block size of the data which can usually be obtained 
from the RDBMS application 20; and the second being the tuples from the 
tuple-sorted table labeled 34. The TDC calculating module 36 takes the 
first tuple of the tuple-sorted table 34 and stores that tuple as the head 
tuple within the TDC table 38 for the first block. The module 36 then 
reads in the next tuple and subtracts from it the previous tuple, which in 
this case is the head tuple. This difference is then stored in the TDC 
table 38. The next tuple from the tuple-sorted table 34 will be read and 
will have subtracted from it the preceding tuple's value. 
The resulting tuple difference is stored in the TDC table 38. This 
differencing process will continue until the sum of the sizes of the 
difference tuples has reached the block size. When the number of tuples 
has reached the block size, then the TDC calculating module 36 begins a 
new head tuple from which subsequent differences will ultimately be based. 
The following pseudocode illustrates how the head tuple and the subsequent 
differencing is accomplished within a block. Please note that the domain 
ordinal values of each tuple are used in the differencing operation. 
______________________________________ 
size = 0 
n = # of total tuples within the table 
i = 1 
WHILE (i &lt;= n) 
IF (blocksize&gt;size) THEN 
Set this tuple as the head tuple and store it in the 
TDC Table 
size = size of this head tuple 
ELSE 
Store the result of the difference between Tuple(i) 
and Tuple(i+1) 
size = size + (size of this difference) 
ENF IF 
i = i + 1 
END WHILE 
______________________________________ 
Finally the storing module 40 takes the values from TDC table 38 and 
variably encodes them to achieve further compression. These variably 
encoded tuples are then stored within the RDBMS application 20. Both the 
head tuples and the difference tuples are variably encoded. Many encoding 
techniques exist to achieve the variably encoded result. The technique 
used here replaces any leading zeros of a tuple with an integer value 
representative of the number of leading zeros it had replaced. 
By way of summary, the software embodiment of FIG. 6 performs the 
operations illustrated in FIG. 7. The input database, comprising a 
plurality of tuples having predefined field values according to a 
predefined schema, is mapped (operation 100) according to the predefined 
mapping rules 102. This mapping operation produces tuples with fields 
mapped to domain ordinals, Next, a rearrange operation 104 is performed 
according to predefined rearrangement rules 106. This produces tuples with 
fields rearranged into a permuted schema. The tuples are then sorted 
(operation 108) according to predefined sorting rules 110. This produces a 
sorted table. Then, if desired a block of predefined size may be 
established (operation 112) so that the sorted tuples are further operated 
upon in block-sized increments. These further operations involve 
difference operation 114, which produces a head tuple and a table of 
difference values to represent the remaining tuples in the block. This 
entire tuple may be used as the key for the primary index to the database. 
The tuple is then stored (operation 116) according to the predefined 
storing rules 118 of the database system. 
While the invention has been described in its presently preferred form, 
with several examples and an exemplary software implementation given, it 
will be understood that the invention is not limited to these examples or 
this software implementation. Rather, the invention is capable of 
modification without departing from the spirit of the invention as set 
forth in the appended claims.