Databases Reference
In-Depth Information
Table 7.2
Characterization of Commonly Used SQL-Based
Pattern Pruning Constraints
Constraint AntimonotonicMonotonic Succinct
v
2
S
no
yes
yes
S
V
no
yes
yes
S
V
yes
no
yes
min
.
S
/
v
no
yes
yes
min
.
S
/
v
yes
no
yes
max
.
S
/
v
yes
no
yes
max
.
S
/
v
no
yes
yes
count
.
S
/
v
yes
no
weakly
count
.
S
/
v
no
yes
weakly
sum
.
S
/
v
(8
a
2
S
,
a
0)
yes
no
no
sum
.
S
/
v
(8
a
2
S
,
a
0)
no
yes
no
range
.
S
/
v
yes
no
no
range
.
S
/
v
no
yes
no
avg
.
S
/
v
,
2f , g
convertible
convertible
no
support
.
S
/
yes
no
no
support
.
S
/
no
yes
no
all confidence
.
S
/
yes
no
no
all confidence
.
S
/
no
yes
no
Specifically, such a set must consist of a nonempty set of items that have a price no less
than $50. It is of the form
S
, where
S
6D; is a subset of the set of all items with prices no
less than $50. Because there is a precise “formula” for generating all the sets satisfying
a succinct constraint, there is no need to iteratively check the rule constraint during
the mining process. The succinctness of the list of SQL primitives-based constraints is
indicated in the fourth column of Table 7.2.
2
The fourth category is
convertible constraints
. Some constraints belong to none of
the previous three categories. However, if the items in the itemset are arranged in a par-
ticular order, the constraint may become monotonic or antimonotonic with regard to
the frequent itemset mining process. For example, the constraint “
avg
/
$
10”
is neither antimonotonic nor monotonic. However, if items in a transaction are added
to an itemset in price-ascending order, the constraint becomes
antimonotonic
, because
if an itemset
I
violates the constraint (i.e., with an average price greater than $10),
then further addition of more expensive items into the itemset will never make it
.
I
.
price
2
For constraint
count
/
v
), we can have a member generation func-
tion based on a cardinality constraint (i.e., f
X
j
X
Itemset
^ j
X
j
v
g). Member generation in this
manner is of a different flavor and thus is called
weakly succinct
.
.
S
/
v
(and similarly for
count
.
S
