A theory of inductive query answering

Luc De Raedt, Martin Jaeger, Sau Dan Lee, Heikki Mannila

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 Qi- QA∧ QMthat are the conjunction of a monotonic and an anti-monotonic predicate. The solution to each subquery 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 experiments that validate the approach. © 2002 IEEE.
BibTeX
@inproceedings{raedt2002theory,
  author = {Luc De Raedt and Martin Jaeger and Sau Dan Lee and Heikki Mannila},
  title = {{A theory of inductive query answering}},
  booktitle = {ICDM},
  year = {2002},
  url = {https://openreview.net/forum?id=qe-1nQHIue},
}

Loading related content...

Figure