Database Reference
In-Depth Information
with code table
CT
, a cover function
cover
(
CT
,
t
) is required that identifies which elements of
CT
are used to encode
t
. The parameters are a code table
CT
and a tuple
t
, the result is a disjoint set of
elements of
CT
that cover
t
. Or, more formally, a cover function is defined as follows.
To encode a tuple
t
from database
D
Definition 8.3
Let
D
be a database over a universe of possible tuples
T
,
t a tuple
drawn from
D
, let
CT
be the set of all possible code tables over
X
,
and CT a code
.
Then,
cover
:
table with CT
∈
CT
CT
×
T
→
P
(
X
)
is a cover function iff it
returns a set of patterns such that
1.
cover
(
CT
,
t
)
is a subset of PS, the pattern set of CT
, i.e.,
X
cover
(
CT
,
t
)
∈
→
X
∈
CT
2.
together all X
cover
(
CT
,
t
)
cover t completely, i.e., t can be fully reconstructed
from cover
(
CT
,
t
)
∈
We say that cover
(
CT
,
t
)
covers t.
Observe
that
this
cover
function
is
very
generic
and
allows
many
dif-
ferent
instances.
In
general,
finding
a
subset
of
a
pattern
set
that
covers
T
a tuple can be a hard combinatorial problem. Depending on the data universe
,
X
pattern language
and requirements imposed by the task, it may therefore be ben-
eficial to impose additional constraints to make the cover function fast and efficient
to compute. Also, note that without any further requirements on code tables, it may
be possible that a code table cannot cover any tuple. To remedy this, a common
approach is to require that any 'valid' code table should contain at least all primitive
patterns, i.e., singletons, required to cover any tuple from
T
.
Example 8.4 We continue the example of
KRIMP
and present its cover function in
Algorithm 4. To allow for fast and efficient covering of transactions,
KRIMP
considers
non-overlapping covers. Its mechanism is very simple: look for the first element in
the code table that occurs in the tuple, add it to the cover and remove it from the
tuple, and repeat this until the tuple is empty. Recalling that tuples and patterns are
both itemsets, we have that a cover is a set of itemsets, s.t
.
∀
X
,
Y
∈
cover
(
t
,
CT
)
X
∩
Y
=∅
,
and
∪
X
∈
cover
(
t
,
CT
)
X
=
t.
