Databases Reference
In-Depth Information
Definability of Association Rules and Tables
of Critical Frequencies
Jan Rauch
Department of Information and Knowledge Engineering, University of Economics,
Prague, nam. W. Churchilla 4, 130 67 Praha 3, Czech Republic
rauch@vse.cz
Summary.
Former results concerning definability of association rules in classical
predicate calculi are summarized. A new intuitive criteria of definability are pre-
sented. The presented criteria concern important classes of association rules. They
are based on tables of critical frequencies of association rules. These tables were in-
troduced as a tool for avoiding complex computation related to verification of rules
corresponding to statistical hypotheses tests.
1 Introduction
Goal of this chapter is to contribute to theoretical foundations of data mining.
We deal with association rules of the form
ϕ
ψ
where
ϕ
and
ψ
are Boolean
attributes derived from columns of the analysed data matrix
≈
. The asso-
ciation rule
ϕ ≈ ψ
says that
ϕ
and
ψ
are associated in a way given by the
symbol
M
is called
4ft-quantifier
. It corresponds to a condition
concerning a fourfold contingency table of
ϕ
and
ψ
in
≈
. The symbol
≈
. Association rules
of this form were introduced and studied in [2]. They were further studied
among others in [4, 8], the results were partly published in [5-7, 9, 10].
This chapter concerns definability of the association rules in classical pred-
icate calculi. The association rules can be understood as formulae of monadic
predicate observational calculi defined in [2]. The monadic predicate obser-
vational calculus is a modification of classical predicate calculus: only finite
models are allowed and generalized quantifiers are added. 4ft-quantifier
M
≈
is
an example of the generalized quantifier.
There is a natural question of classical definability of the association rules
i.e. the question
which association rules can be expressed by means of classical
predicate calculus
(predicates, variables, classical quantifiers
,Boolean
connectives and the predicate of equality). This question is solved by the
Tharp's theorem proved in [2, 13].
∀
and
∃
