A framework for query refinement with user feedback

SQL queries in the existing relational data model implement the binary satisfaction of tuples. That is, a data tuple is filtered out from the result set if it does not satisfy the constraints expressed in the predicates of the user submitted query. Posing appropriate queries for ordinary users is very difficult in the first place if they lack knowledge of the underlying dataset. Therefore, imprecise queries are commonplace for many users. In connection with this, this paper presents a framework for capturing user intent through feedback for refining the initial imprecise queries that can fulfill the users’ information needs. The feedback in our framework consists of both unexpected tuples currently present in the query output and expected tuples that are missing from the query output. We show that our framework does not require users to provide the complete set of feedback tuples because only a subset of this feedback can suffice. We provide the point domination theory to complement the other members of feedback. We also provide algorithms to handle both soft and hard requirements for the refinement of initial imprecise queries. Experimental results suggest that our approach is promising compared to the decision tree based query refinement approach.

► We present the point domination theory for complementing the incomplete user feedback and capturing the query intent.
► We develop greedy-based approximation algorithms for the selection of subset of query conditions through which query refinement is achieved.
► We show how we can achieve query refinement when selection predicates are overlapped for expected and unexpected tuples.
► We present thorough experimentation of the proposed algorithms and compare our results with decision tree based query refinement.