A Theory of Inductive Query Answering Luc De Raedt, Manfred Jaeger, Sau Dan Lee, and Heikki Mannila   View Paper (PDF)   Return to Main-Track Regular Papers Abstract We introduce the boolean inductive query evaluation problem, which is concerned with answering inductive queries that are arbitrary boolean expressions over monotonic and anti-monotonic predicates. Secondly, we develop a decomposition 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 algorithm. Finally, we present some experi-ments that validate the approach. DiSC'03 © 2003 Association for Computing Machinery