Paper Info
Title
A Theory of Inductive Query Answering
Abstract
We introduce the boolean inductive query evaluationproblem, which is concerned with answering inductivequeries that are arbitrary boolean expressions over monotonicand anti-monotonic predicates. Secondly, we developa decomposition theory for inductive query evaluation inwhich a boolean query Q is reformulated into k sub-queriesQ_i= Q_A\wedge Q_Mthat are the conjunction of a monotonicand an anti-monotonic predicate. The solution to each sub-querycan be represented using a version space. We investigatehow the number of version spaces k needed to answerthe query can be minimized. Thirdly, for the pattern domainof strings, we show how the version spaces can berepresented using a novel data structure, called the versionspace tree, and can be computed using a variant of the famousApriori algorithm. Finally, we present some experi-mentsthat validate the approach.
Year
DOI
Venue
2002
10.1007/978-1-4419-7738-0_4
Inductive Databases and Constraint-Based Data Mining
Keywords
Field
DocType
boolean inductive query evaluationproblem,anti-monotonic predicate,arbitrary boolean expression,version space,experi-mentsthat validate,decomposition theory,version spaces k,inductive query answering,monotonicand anti-monotonic predicate,k sub-queriesq_i,inductive query evaluation,concept learning,database languages,boolean algebra,data structures,machine learning,database theory,a priori algorithm,association rules,data mining,database systems,database management systems,information technology,frequency,history,data structure
Query optimization,Data mining,Query language,RDF query language,Query expansion,Computer science,Sargable,Web query classification,Boolean expression,Boolean conjunctive query
Conference
ISBN
Citations 
PageRank 
0-7695-1754-4
51
2.04
References 
Authors
24
4
Name
Order
Citations
PageRank
Luc De Raedt15481505.49
Manfred Jaeger229729.61
Sau Dan Lee362970.44
Heikki Mannila465951495.69