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.

A holistic and principled approach for the empty-answer problem / Mottin, Davide; Marascu, Alice; Roy, Senjuti Basu; Das, Gautam; Palpanas, Themis; Velegrakis, Ioannis. - In: VLDB JOURNAL. - ISSN 1066-8888. - 25:(2016), pp. 597-622. [10.1007/s00778-016-0431-8]

A holistic and principled approach for the empty-answer problem

Velegrakis, Ioannis
2016

Abstract

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.
Mottin, Davide; Marascu, Alice; Roy, Senjuti Basu; Das, Gautam; Palpanas, Themis; Velegrakis, Ioannis
A holistic and principled approach for the empty-answer problem / Mottin, Davide; Marascu, Alice; Roy, Senjuti Basu; Das, Gautam; Palpanas, Themis; Velegrakis, Ioannis. - In: VLDB JOURNAL. - ISSN 1066-8888. - 25:(2016), pp. 597-622. [10.1007/s00778-016-0431-8]
File in questo prodotto:
File Dimensione Formato  
vldbj16-emptyanswer.pdf

Solo gestori archivio

Descrizione: Articolo principale
Tipologia: Pre-print non referato (Non-refereed preprint)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.34 MB
Formato Adobe PDF
1.34 MB Adobe PDF   Visualizza/Apri
Mottin2016_Article_AHolisticAndPrincipledApproach.pdf

Solo gestori archivio

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 2.92 MB
Formato Adobe PDF
2.92 MB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11572/163276
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 3
social impact