Databases Reference
In-Depth Information
row
P
1
P
2
... P
n
P
1
∨ P
3
P
2
∧ P
4
of
M f
1
f
2
... f
n
max(
f
1
,f
3
)min(
f
2
,f
4
)
o
1
10
...
1
0
1
o
2
01
...
1
1
0
.
.
.
.
.
.
.
.
.
o
n
10
...
0
0
1
Fig. 1.
Example of
{
0,1
}
- data matrix
The rule (
≈
x
)(
P
1
(
x
)
∨
P
3
(
x
)
,P
2
(
x
)
∧
P
4
(
x
)) can be written in various
forms, e.g. (
≈
)(
P
1
∨
P
3
,P
2
∧
P
4
)or
P
1
∨
P
3
≈
P
2
∧
P
4
. Its evaluation is in
any case based on the value
≈
(
a,b,c,d
)where
a,b,c,d
is the 4ft-table of
P
1
(
x
)
P
4
(
x
) in the data matrix in question. The same is
true for each association rule of the form (
∨
P
3
(
x
)and
P
2
(
x
)
∧
x
)(
ϕ
(
x
)
,ψ
(
x
)).
Let us remark that the association rule of the form like
A
(1
,
2
,
3)
≈
≈
B
(4
,
5)
can be understood (informally speaking) like the rule
A
1
∨
B
5
where
A
1
is a predicate corresponding to the basic Boolean attribute
A
(1) etc.
A
2
∨
A
3
≈
B
4
∨
3.2 Definability and Associated Function
The natural question is what association rules are classically definable. We say
that the association rule (
≈ x
)(
ϕ
(
x
)
,ψ
(
x
)) - formula of MOPC is classically
definable if there is a formula
Φ
of CMOPC with equality such that
Φ
is log-
ically equivalent to (
≈
x
)(
ϕ
(
x
)
,ψ
(
x
)). It means e.g. that the association rule
(
P
4
(
x
)) is equivalent to the formula created from
the predicates
P
1
(
x
),
P
2
(
x
),
P
3
(
x
),
P
4
(
x
), propositional connectives
≈
x
)(
P
1
(
x
)
∨
P
3
(
x
)
,P
2
(
x
)
∧
¬
,
∨
,
∧
,
classical quantifiers
, and from the binary predicate of equality =. The
precise formal definition is given in [2], see also [10]. If the association rule
(
∃
,
∀
≈
x
)(
ϕ,ψ
) is classically definable then we also say that the 4ft-quantifier
≈
x
is classically definable and vice-versa.
The question of classical definability of (not only) association rules is solved
by the Tharp's theorem proved in [2]. The Tharp's theorem is but too complex
and general from the point of view of association rules. A more intuitive
criterion of classical definability of association rules is proved in [4] see also
[10]. This criterion is based on the associated function
≈
(
a,b,c,d
)ofthe
4ft-quantifier
.
The criterion uses the notion of interval in
≈
4
N
where
N
is the set of all
4
is defined as the set
natural numbers. The
interval in
N
I
=
I
1
×
I
2
×
I
3
×
I
4
suchthatitis
I
j
=
k,l
)or
I
j
=
k,
∞
)for
j
=1
,
2
,
3
,
4and0
≤
k<l
are
4
.
The criterion of classical definability of association rules is given by the
following theorem proved in [4], see also [10].
natural numbers. The empty set
∅
is also the interval in
N
