Automating the Design and Construction of Query Forms

Abstract

One of the simplest ways to query a database is through a form, where a user can fill in relevant information and obtain desired results by submitting the form. Designing good static forms is a non-trivial manual task, and the designer needs a sound understanding of both the data organization and the querying needs. Furthermore, form design has two conflicting goals: forms should be simple to understand, and at the same time must provide the broadest possible querying capability to the user. In this paper, we present a framework for generating forms in an automatic and principled way, given the database schema and a sample query workload. We design a tunable clustering algorithm for establishing form structure based on multiple "similar"queries, which includes a mechanism for extending form structure to support other "similar" queries the system may see in the future. The algorithm is adaptive and can incrementally adjust the form structure to reflect the addition or removal of queries in the workload. We have implemented our form generation system on a real database and evaluated it on a comprehensive set of query loads and database schemas. We observe that our system can significantly reduce the numbers of forms needed for various query loads by exploiting similarities across queries, even after placing a strict bound on form complexity.