Biology Reference
In-Depth Information
then P is parent of
X
but it is not necessary that every parent of
X
is a predecessor
of
X
.
Note that for
S
∈
Succ
(
X
),thenbydefinition
XS
is
closed. It is easy to check that the converse is also true. Namely, if
XS
is closed,
then
XS
∈
AttrChild
(
X
),if
XS
∈
Succ
(
X
). In other words, we have the following proposition.
Proposition 8.2.
Succ
(
X
)=
{
XS
:
XS
is closed,
S
∈
AttrChild
(
X
)
}
.
8.3.2.
Characterizations of Closure
By definition, an attribute set
X
is closed if
attr
(
obj
(
X
)) =
X
. In the follow-
ing we give two characterizations for an attribute set being closed based on its
relationship with its siblings.
Proposition 8.3.
Fo r
S
∈
AttrChild
(
X
)
,
XS
is not closed if and only if there
exists
T
∈
AttrChild
(
X
)
,
T
=
S
, such that
obj
(
XS
)
⊂
obj
(
XT
)
.Further-
⊂
obj
(
XT
)
, there exists
S
∈
more, for all
T
∈
AttrChild
(
X
)
with
obj
(
XS
)
S
,
obj
(
XS
)=
obj
(
XTS
)
and
XS
XTS
.
AttrChild
(
XT
)
such that
S
⊆
⊂
Proof.
If
XS
is not closed, by definition, there exists
i
∈
res
(
X
)
\
S
such that
i
∈
attr
(
obj
(
XS
)).As
AttrChild
(
X
) is a partition of
res
(
X
), there exists a
T
∈
AttrChild
(
X
) such that
i
∈
T
, and thus
obj
(
XT
)=
obj
(
X
)
∩
nbr
(
i
)
⊃
obj
(
XS
).
Conversely, suppose there exists
T
∈
AttrChild
(
X
) such that
obj
(
XS
)
⊂
obj
(
XT
).
n
attr
(
obj
(
XS
))
⊇
XTS
.
t i ,
XS
⊂
XTS
⊆
attr
(
obj
(
XS
)), which implies
XS
is not closed.
Suppose that
obj
(
XS
)
⊂
obj
(
XT
) with
T
∈
AttrChild
(
X
).For
i
∈
S
,
obj
(
XT
)
∩
nbr
(
i
)=
obj
(
XT
)
∩
obj
(
X
)
∩
nbr
(
i
)=
obj
(
XT
)
∩
obj
(
XS
)=
obj
(
XS
). Thus, there exists
S
∈
AttrChild
(
XT
) such that
S
⊆
S
,
obj
(
XS
)=
obj
(
XTS
).Since
X,S,T
are disjoint,
XS
⊂
XTS
⊆
XTS
.
Basedonthefirst part of this proposition (first characterization), we can test
if
XS
is closed, for
S
∈
AttrChild
(
X
),byusing
subset testing
of its object set
against its siblings' object set. Namely,
XS
is closed if and only
obj
(
XS
) is not
a proper subset of its siblings' object set. In our running example in Fig. 8.1, 3 is
not closed because its object set
obj
(3) =
ac
is a proper subset of the object set of
its sibling,
obj
(1) =
abc
.
In general, subset testing operations are expensive. We, however, can make
use of the second part of the proposition (second characterization) for testing clo-
sure using set exact matching operations instead of subset testing operations. This
is because if we process the children in the decreasing order of their object-set
size, we can test the closure of
XS
by comparing its size against the size of the
Search WWH ::
Custom Search