Supporting Queries with Imprecise Constraints

Ullas Nambiar, Subbarao KambhampatiAAAI 2006 · OpenReview

Abstract

In this paper, we motivate the need for and challenges involved in supporting imprecise queries over Web databases. Then we briefly explain our solution, AIMQ - a domain independent approach for answering imprecise queries that automatically learns query relaxation order by using approximate functional dependencies. We also describe our approach for learning similarity between values of categorical attributes. Finally, we present experimental results demonstrating the robustness, efficiency and effectiveness of AIMQ.

Introduction

Traditional database systems operate on a rigid Boolean logic: a tuple either matches a query exactly, or it is excluded. However, as the web has opened databases to non-technical users, there is a growing demand for Information Retrieval (IR) style interactions. Users often have vague information needs—such as searching for "a car like a Camry"—but are forced into a tedious cycle of trial-and-error queries because standard databases do not understand similarity. AIMQ (Answering Imprecise Queries) seeks to solve this non-intrusively by extracting similarity and importance information directly from the data itself, providing a ranked list of relevant results rather than a binary match.

System Architecture

The AIMQ framework is designed to be domain-independent, allowing it to handle "fuzzy" queries without requiring users to hard-code similarity metrics. The system architecture consists of several specialized miners and engines that work in tandem to process imprecise constraints.

The AIMQ system architecture, highlighting the Data Collector, Query Engine, and Mining components.

Methodology

The AIMQ approach consists of three primary components:

  1. Estimating Attribute Importance (Dependency Miner): Not all database columns are equally significant to a user's intent. To decide which constraints to relax first, AIMQ mines Approximate Functional Dependencies (AFDs). If one attribute (like Year) strongly influences another (like Price), it is considered a "deciding" attribute. The system builds a dependence graph to identify the least important attributes, which become the first candidates for relaxation.
  2. Categorical Value Similarity (Similarity Miner): To determine if a "Honda Accord" is a suitable substitute for a "Toyota Camry," the system utilizes "Supertuples." A supertuple for a specific value is a bag of keywords representing all other attribute values associated with it in the database. Similarity is calculated using a weighted Jaccard Coefficient between these bags.
  3. Query Relaxation (GuidedRelax): When a precise query returns insufficient results, the system generates new queries by systematically relaxing constraints. It uses the importance rankings from the AFD miner to ensure that the most critical constraints are preserved as long as possible.

Experimental Results

The authors evaluated AIMQ using real-life datasets, including Yahoo Autos and the US Census Dataset. The core GuidedRelax algorithm was compared against RandomRelax and ROCK (a standard clustering algorithm) using Mean Reciprocal Rank (MRR) as the primary metric.

Performance comparison showing Average MRR across various queries for GuidedRelax, RandomRelax, and ROCK.

As shown in the performance analysis, GuidedRelax consistently outperformed the other methods. This suggests that the attribute ordering heuristic derived from AFDs closely matches the importance that human users actually ascribe to different features. Furthermore, the system successfully generated similarity graphs for categorical data that align with intuitive human expectations (e.g., identifying similarities between specific car makes based on their data distribution).

Conclusion

AIMQ demonstrates that a database's own distribution of data contains latent information about similarity and attribute importance. By using AFDs to partition attributes and supertuples to map categorical similarities, the system avoids the need for intrusive user feedback or manual expert definitions. While the system relies on representative data sampling, it offers a highly portable and effective solution for autonomous web databases where internal access is restricted.

Summary updated

Abstract

In this paper, we motivate the need for and challenges involved in supporting imprecise queries over Web databases. Then we briefly explain our solution, AIMQ - a domain independent approach for answering imprecise queries that automatically learns query relaxation order by using approximate functional dependencies. We also describe our approach for learning similarity between values of categorical attributes. Finally. we present experimental results demonstrating the robustness, efficiency and effectiveness of AIMQ.
BibTeX
@inproceedings{nambiar2006supporting,
  author = {Ullas Nambiar and Subbarao Kambhampati},
  title = {{Supporting Queries with Imprecise Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
  url = {https://openreview.net/forum?id=Hk4okkbu-H},
}
Figure