Database Reference
In-Depth Information
Original data: a
l
, c, c, a
2
, c, c, c, a
3
.
Compressed data
Bit map: 10010001.
Physical database: a
l
, a
2
, a
3
.
The access time for both forward and backward
mapping for the bitmap scheme is O(N), where N
is the number of bits in the bitmap, or equivalently
the number of elements in the database.
sional for an n dimensional extendible array the
linearization function F becomes
Fx x
(, ,...,
x
)
=
dd
...
dx
1 2
n
−
1
1
2
n
−
2
n
−
1
+
dd ddx
...
+ ++
...
d xx
12 3
n n
−−
3
2
1
2
1
The coefficients of above function F is n-2
dimensional. As the extendible array is two di-
mensional in Figure 7 the coefficient table is void
is there. When the number of dimension is more
than two in an extendible array then the coeffi-
cients are computed and stored in the coefficient
table. The actual data is stored in the subarrays
that construct the extendible array. The three
kinds of tables are auxiliary tables only. With the
cost of the small auxiliary tables the multidimen-
sional array can be extended dynamically in any
direction without reallocation of the data already
stored. Such advantages make it possible to apply
the extendible array in a wide area of application
where dynamic treatment of the array is necessary
(Hasan et, al; 2007).
Using these three kinds of auxiliary table, the
address of an array element can be computed as
follows. Consider the element <4,3> of the extend-
ible array in Figure 7. Compare
H
1
47
history offset compression
The history offset compression scheme (Hasan
et al; 2005, 2006) is based on extendible array
proposed by Rosenberg, 1974 and Otoo & Mer-
rett, 1983. Conventional schemes for storing
arrays do not support easy dynamic extension of
an array. An extendible array, however, does not
store an individual array; rather, it stores an array
and all its potential extensions. The scheme is an
n
-dimensional rectangular array that grows by ad-
joining blocks, which are subarrays of dimension
n-1
, within which each subarray storage allocation
is in row-major or lexicographic order.
The Notion of Extendible Array
[]=
and
An
n
dimensional extendible array
A
has a his-
tory counter
h
and three kinds of auxiliary tables
for each extendible dimension
i
(
[] [>
, it can be proved
that the element <4,3> is involved in the extended
subarray
S
occupying the address from 60 to 63.
The first address of
S
is known to be 60, which
is stored in
L
1
[]
. Since the offset of <4, 3> from
the first address of S is 3, the address of the ele-
ment is determined as 63. Note that such a simple
computational scheme can be used to access an
extendible array element only by preparing small
auxiliary tables. The superiority of this scheme in
element accessing speed and memory utilization
is shown by Otoo & Merrett 1983 comparing
with other schemes such as hashing (Rosenberg
& Stockmeyer, 1977).
H
2
[]=
. Since
HH
1
36
4
3
2
=1
. See
Figure 7. These tables are history table
H
i
, address
table
L
i
, and coefficient table
C
i
. The history tables
memorize extension history
h
. If the size of
A
is
[, ,...,
i
,..., )
n
n
-1 1
and the extended dimension is
i
,
for an extension of
A
along dimension
i
, contigu-
ous memory area that forms an
n
-1
dimensional
subarray
S
of size
[, ,...,
dd
d
]
1 1 1 2 1
is dynamically allocated. Then the current history
counter value is incremented by one, and it is
memorized on the history table
H
i
, also the first
address of
S
is held on the address table
L
i
. Since
h
increases monotonously,
H
i
is an ordered set of
history values. As the subarrays are n-1 dimen-
dd
dd
,
,...,
dd
,]
nn
-
i
+
i
-
Search WWH ::
Custom Search