Item

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.