Online Query Relaxation via Bayesian Causal Structures Discovery

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 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2005
Accession Number
ADA454771

Entities

People

  • Ion Muslea
  • Thomas J. Lee

Organizations

  • SRI International

Tags

Communities of Interest

  • Autonomy

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Artificial Intelligence Software
  • Bayesian Networks
  • Breast Cancer
  • Data Mining
  • Databases
  • Information Science
  • Information Systems
  • Learning
  • Machine Learning
  • Test Sets
  • Topology

Fields of Study

  • Computer science

Readers

  • Mathematics or Statistics
  • Neural Network Machine Learning.
  • Operations Research

Technology Areas

  • AI & ML
  • AI & ML - Information Retrieval
  • AI & ML - Machine Learning Algorithms
  • AI & ML - Neural Networks