QUERY BY OUTPUT

Abstract

While database system research has made tremendous advances on functionality and performance related issues over the years, research on improving database usability has not attracted as much attention as it deserves. In this work, we propose a novel data-driven approach, called Query by Output (QBO), targeted at improving the usability of database management systems. The central goal of Query by Output is as follows: given a database D and a result table T = Q(D), which is the output of some query Q on D, the goal of QBO is to construct an alternative query Q' such that the output of query Q' on database D is equal to Q(D). We consider the following three variants of QBO.

In the first variant of QBO, the input query Q may be known or unknown, and the result table T contains a set of specific tuples. One useful application of this variant is to help users better understand their query results by augmenting the result of a query Q (w.r.t. a database D) with instance-equivalent queries Q', each of which produces the same result as Q (w.r.t. D) and thus describing alternative characterizations of tuples in Q(D).

The second variant of QBO requires the input query Q to be explicitly given and the result table to be in the form T = Q(D) U S, where S is a non-empty set of expected tuples that are missing from Q(D). The problem is to derive some refined query Q' of Q such that Q'(D) includes all the tuples in Q(D) as well as the missing tuples in S. This variant of QBO presents a new paradigm for explaining why a set of tuples is missing in the result of a query Q w.r.t. a database D by automatically generating one or more refined query Q', whose result includes both the original query result and the missing tuples.

The third variant of QBO takes the following as inputs: (1) a database D, (2) a query Q that is partially specified (e.g., only the from-clause and the join predicates of Q are specified), and (3) a set C of aggregation constraints that must be satisfied by the query result of each derived query Q' from Q. The goal is to either (1) evaluate Q by returning a subset of tuples of Q(D) satisfying all the constraints in C, or (2) instantiate Q into one or more complete relational queries Q' such that the execution of Q' on D satisfies all the constraints in C. One useful application of this setting is in the Targeted Query Generation problem to generate test queries for database testing.