The physical model includes
the kind of indices
that are potentially available
for each relation.
This corresponds to
the types of indices available
from the DBMS.
Since Model D is not modeling an actual commercial
the choice of access methods was somewhat arbitrary
-- defined to some extent to test the extensibility of
(discussed in section 6.5)
will include a mechanism to
describe the actual indices defined
for a particular database.
index types include
Stored relations are modeled
on either a B-tree or hash index.
B-tree indices are used for range predicates.
(with the physical operator, INDEXED-FILTER).
hash or B-tree index on join condition attributes
could support the LOOPS_INDEX_JOIN physical operator.
The hash, B-tree and clustering aspects
of this model are standard approaches
and will not be described further.
are less standard.
Model D has
two types of
Both could be used
to implement the SELECT logical operator.
In Model D,
they are used,
only in conjunction with a join,
by the BIT_SEMIJOIN physical operator.
Both types of bit-index
on a dense indexing attribute
is a candidate key of the relation.
A dense attribute
all of the values
are packed within a range
with few absent values.
it is further assumed
that the minimum value
of the attribute is zero.
an index would be considered dense
if the minimum key value was 0,
the maximum was 10000
and 9000 unique keys
were contained in the relation.
An example of a dense attribute would be
a serial column.
store a single bit
for every tuple in the relation.
The length (number of bits)
of each bit vector
is the maximum value of the indexing attribute.