Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

A Theory of Inductive Query Answering


Jaeger,  Manfred
Programming Logics, MPI for Informatics, Max Planck Society;


Mannila,  Heikki
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

de Raedt, L., Jaeger, M., Lee, S. D., & Mannila, H. (2002). A Theory of Inductive Query Answering. In Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02) (pp. 123-130). Los Alamitos, USA: IEEE.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2F15-A
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.