Database Reference
In-Depth Information
Index Type:
A subset of the attributes of a record that can uniquely iden-
tify a record of the dataset is referred to as the
primary key
. An index
constructed using the
primary key
attributes is called the
primary in-
dex
, otherwise it is a
secondary index
. An index may also be classified
as either
clustered
or
nonclustered
according to whether records whose
primary keys are closely similar to each other are also stored in close
proximity to each other. A metric of similarity of two keys is defined by
the collating sequence order of the index keys.
Class of Queries:
The adoption of a particular index scheme is also highly
dependent on the types of queries that the dataset is subsequently
subjected to. Let the records of a dataset have
k
attributes
A
=
{
A
1
,
A
2
,
...
A
k
}
, such that a record
r
i
=
a
1
,
a
2
,
...
a
k
, where
a
i
∈
A
i
.
Typical classes of queries include the following:
Exact Match:
Given
k
values
v
1
,
v
2
,
...v
k
an exact-match query asks
for the retrieval of a record
r
i
=
a
1
,
a
2
,
...
a
k
such that
a
i
=
v
i
,1
≤
k
.
Partial Match:
Let
A
⊆
i
≤
A
with
a
j
∈
A
j
and
a
j
∈
A
j
, respectively, for
for the
k
attributes of
A
, a partial-match query asks for the retrieval of all
records whose attribute values match the corresponding specified
value, that is,
a
j
A
|
A
|=
k
≤
j
≤|
, where
|
k
. Given values
{
v
1
,
v
2
,
...v
k
}
k
. The exact-match
query is a special class of a partial-match query.
Orthogonal Range:
For categorical attributes we assume that an or-
dering of the attribute values is induced by the collating sequence
order of the values, and for numeric attribute values the ordering
is induced by their respective values. Then, given
k
closed inter-
vals of values
j
, for
a
j
A
j
,1
=
v
∈
≤
j
≤
[
l
1
,
h
1
], [
l
2
,
h
2
],
...
[
l
k
,
h
k
]
, an orthogonal-range query
=
...
asks for the retrieval of all records
r
i
a
1
,
a
2
,
a
k
such that
≤
≤
≤
≤
k
.
Partial Orthogonal Range:
This is similar to orthogonal-range
query but only a subset of the attributes is mentioned in
the query. The orthogonal-range query is a special case of
a partial-orthogonal-match query. Since partial-orthogonal-range
query subsumes the preceding classes, we will use the measure
of the eciency of processing partial-orthogonal-range queries and
the measure of the eciency of processing partial-match queries as
the comparative measures of the eciencies of the various index-
ing schemes to be addressed. If the columns involved in a partial-
orthogonal-range query vary from one query to the next, such
queries are also known as
ad hoc range queries
. In the above defini-
tion, the condition on each column is of the form
l
j
≤
l
i
a
i
h
i
,1
i
h
j
. Since
it specifies two boundaries of the query range, we say it is a two-
sided range. If the query range only involves one boundary, for ex-
ample,
l
j
a
j
≤
≤
a
j
,
a
j
≤
h
j
,
l
j
<
a
j
, and
a
j
>
h
j
, it is a one-sided range.
