Databases Reference
In-Depth Information
The Tharp's theorem is but too general from the point of view of the asso-
ciation rules. A more intuitive criterion of classical definability of association
rules was proved in [4] see also [10].
The goal of this chapter is to show that this criterion can be further simpli-
fied for several important classes of association rules. The simplified criterion
is based on tables of critical frequencies (further we use only
TCF
instead
of
table of critical frequencies
). TCF's were introduced as a tool for avoiding
complex computation [2, 4] related to the association rules corresponding to
statistical hypotheses tests.
The chapter uses notions of association rules and classes of association
rules described in [11] in this topic. Tables of critical frequencies are introduced
in Sect. 2. Results concerning classical definability of the association rules are
presented in Sects. 3 and 4. Some concluding remarks are in Sect. 5.
2 Tables of Critical Frequencies
First we prove the theorem about
partial tables of maximal b
. Further we will
denote
+
=
N
{
0
,
1
,
2
,...
}∪{∞}
.
Theorem 1.
Let
be an equivalency quantifier. Then there is a non-negative
function Tb
≈
that assigns to each triple
≈
a,c,d
of non-negative natural num-
+
such that
bers a value Tb
≈
(
a,c,d
)
∈N
1. For each b
(
a,b,c,d
)=1
if and only if b<Tb
≈
(
a,c,d
)
.
2. If a
>athen Tb
≈
(
a
,c,d
)
≥
0
it is
≈
≥
Tb
≈
(
a,c,d
)
.
Proof. Let us define
Tb
≈
(
a,c,d
)=min
{
b
|≈
(
a,b,c,d
)=0
}
.
Let us remember that
≈
is equivalency. It means that
a
≥
b
c
≤
d
≥
≈
(
a,b,c,d
)=1
∧
a
∧
≤
b
∧
c
∧
d
implies
(
a
,b
,c
,d
)=1
≈
It means among other
I: If
≈
(
a,b,c,d
)=0
and v
≤
a then also
≈
(
v,b,c,d
)= 0
.
II: If
≈
(
a,b,c,d
)=0
and w
≥
b then also
≈
(
a,w,c,d
)=0
.
Point II means that it is
.
We prove that the function defined in the above given way has the properties
1. and 2.
≈
(
a,b,c,d
)=0
for all b
≥
min
{
b
|≈
(
a,b,c,d
)=0
}
