de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

A Theory of Inductive Query Answering

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44689

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44982

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

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

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