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.