An algebra for inductive query evaluation

Inductive queries are queries that generate pattern sets. We study properties of Boolean inductive queries, i.e. queries that are Boolean expressions over monotonic and antimonotonic constraints. More specifically, we introduce and study algebraic operations on the answer sets of such queries and show how these can be used for constructing and optimizing query plans. Special attention is devoted to the dimension of the queries, i.e. the minimum number of version spaces needed to represent the answer sets. The framework has been implemented for the pattern domain of strings and experimentally validated.