Accession Number:

ADA454771

Title:

Online Query Relaxation via Bayesian Causal Structures Discovery

Descriptive Note:

Corporate Author:

SRI INTERNATIONAL MENLO PARK CA ARTIFICIAL INTELLIGENCE CENTER

Personal Author(s):

Report Date:

2005-01-01

Pagination or Media Count:

7.0

Abstract:

We introduce a novel algorithm, TOQR, for relaxing failed queries over databases i.e., 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 domains 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, TOQRs relaxed queries are highly similar to the original failed query.

Subject Categories:

  • Information Science
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE