hide
Free keywords:
-
Abstract:
We introduce the boolean inductive query evaluation problem, which is
concerned with answering inductive que
ries
that are arbitrary boolean expressions over monotonic and anti-monotonic
predicates. Secondly, we develop a d
ecomposition theory for inductive query evaluation in which
a boolean query $Q$ is reformulated into $k$ sub-queries $Q_i = Q_A \wedge Q_M$
that are the conjunction of a
monotonic and an anti-monotonic predicate.
The solution to each sub-query can be represented using a version space.
We investigate how the number of version spaces $k$ needed to answer the query
can be minimized.
Thirdly, for the pattern domain of strings, we show how the version spaces can
be represented using a novel
data structure, called the version space tree, and can be computed using a
variant of the famous Apriori alg
orithm.
Finally, we present some experiments that validate the approach.
