A Holistic and Principled Approach for the Empty-Answer Problem

D. Mottin, S. Basu Roy, A. Marascu, G. Das, T. Palpanas, Y. Velegrakis

FrameworkInteractive Framework

We propose a principled optimization-based interactive query relaxation framework for queries that return no answers. Given an initial query that returns an empty answer set, our framework dynamically computes and suggests alternative queries with fewer conditions than those the user has initially requested, in order to help the user arrive at a query with a non-empty answer, or at a query for which no matter how many additional conditions are ignored, the answer will still be empty. Our proposed approach for suggesting query relaxations is driven by a novel probabilistic framework based on optimizing a wide variety of application-dependent objective functions. We describe optimal and approximate solutions of different optimization problems using the framework. Moreover, we discuss two important extensions to the base framework: the specification of a minimum size on the number of results returned by a relaxed query and the possibility of proposing multiple conditions at the same time. We analyze the proposed solutions, experimentally verify their efficiency and effectiveness, and illustrate their advantages over the existing approaches.

VLDB'13 Paper


We present IQR, a system that demonstrates optimization based interactive relaxations for queries that return an empty answer. Given an empty answer, IQR dynamically suggests one relaxation of the original query conditions at a time to the user, based on certain optimization objectives, and the user responds by either accepting or declining the relaxation, until the user arrives at a non-empty answer, or a non-empty answer is impossible to achieve with any further relaxations. The relaxation suggestions hinge on a probabilistic framework that takes into account the probability of the user accepting a suggested relaxation, as well as how much that relaxation serves towards the optimization objective. IQR accepts a wide variety of optimization objectives - user centric objectives, such as, minimizing the number of user interactions (i.e., effort) or returning relevant results, as well as seller centric objectives, such as, maximizing profit. IQR offers principled exact and approximate solutions for generating relaxations that are demonstrated using multiple, large real datasets.

SIGMOD'14 Demo Paper


We registered a short video of the demo

Source Code

The source code is released open-source, under GPLv2.0 license and comes without any guarantee.

Github repository


Our methods have been tested on two boolean datasets: one from Yahoo! Autos and another from Realtor. We summarize below the main characteristics of these datasets and provide the download links.

Dataset # Attributes # Tuples Link
Cars 31 100,000 Download
Homes 16 38,095 Download