Databases Reference
In-Depth Information
Fig. 2.
Prefix tree of equivalence classes
than subspace
S
2
, denoted as
S
1
S
2
, if the lexicographically smallest at-
tribute
a
i
that distinguishes
S
1
from
S
2
belongs to
S
2
. That is, there exists
a
i
∈
S
1
, and all attributes lexicographically smaller than
a
i
are
shared by
S
1
and
S
2
. Formally,
S
1
S
2
∧
a
i
∈
.
If we know the attribute
a
i
that distinguishes
S
1
and
S
2
,wesay
S
1
is
i
-smaller than
S
2
, denoted as
S
1
i
S
2
.
For example,
S
2
:
⇔∃
a
i
∈S
2
\S
1
S
1
∩{
a
1
,a
2
,...,a
i−
1
}
=
S
2
∩{
a
1
,a
2
,...,a
i−
1
}
because the lexicographically smallest at-
tribute that distinguishes them is
c
, and it belong to
{
ad
}
c
{
acd
}
.
We define
S
i
to be a subset of
S
which includes all the attributes in
S
that are lexicographically smaller than
a
i
, that is,
S
i
{
acd
}
.
Starting from an arbitrary subspace
S
, the next lectically smallest subspace
that is larger than
S
can be computed based on Lemma 2.
:=
S
∩{
a
1
,...,a
i−
1
}
Lemma 2.
The lectically smallest subspace that is lectically larger than S is
S
i
∪{
a
i
}
, where a
i
is the lexicographically largest attribute that is not contained
in S.
Proof.
Let
S
1
=
S
i
∪{a
i
}
, with
a
i
being the lexicographically largest attribute
that is not contained in
S
. Suppose the lemma is not true, then there must
exist
S
2
, such that
S
S
2
S
1
.Since
S
S
2
, there must exist an attribute
S
and
S
j−
1
=
S
j−
2
. We also know
that
a
i
is the smallest attribute that differentiates
S
and
S
1
,so
S
i−
1
=
S
i−
1
a
j
(
i
=
j
), which satisfies
a
j
∈
S
2
,
a
j
∈
.
1
We consider the following two possible relationships between
a
i
and
a
j
.
a
i
<
L
a
j
:Since
i<j
,
S
j
S
2
implies
a
j
is not contained in
S
,which
contradicts the fact that
a
i
is the largest attribute not contained in
S
.
a
i
>
L
a
j
:Since
i>j
,
S
i−
1
=
S
i−
1
implies
S
j−
1
=
S
j−
1
1
. And we also have
1
S
j−
1
=
S
j−
1
2
1
=
S
j−
2
. Since the smallest attribute that differenti-
ates
S
and
S
1
is
a
i
, which is larger than
a
j
,so
a
j
∈
,so
S
j−
1
S
1
.Since
S
j−
1
=
S
j−
1
2
,
1
a
j
∈
S
2
and
a
j
∈
S
1
,wehave
S
1
S
2
, which contradicts the assumption
S
S
2
S
1
.
Starting from the empty subspace, if we keep looking for the next lectically
smallest subspace, we actually perform a right-to-left pre-order depth-first
