Online Query Relaxation via Bayesian Causal Structures Discovery

Ion Muslea, Thomas J. Lee

We introduce a novel algorithm, TOQR, for relaxing failed queries over databases, that is, over-constrained DNF queries that return an empty result. TOQR uses a small dataset to discover the implicit relationships among the domain attributes, and then it exploits this domain knowledge to relax the failed query. TOQR starts with a relaxed query that does not include any constraint, and it tries to add to it as many as possible of the original constraints or their relaxations. The order in which the constraints are added is derived from the domain’s causal structure, which is learned by applying the TAN algorithm to the small training dataset. Our experiments show that TOQR clearly outperforms other approaches: even when trained on a handful of examples, it successfully relaxes more that 97% of the failed queries; furthermore, TOQR’s relaxed queries are highly similar to the original failed query.

Content Area: 12. Machine Learning

Subjects: 12. Machine Learning and Discovery

Submitted: May 6, 2005

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.