Ramana Yerneni, Hector Garcia-Molina
Data sources over the Web publish their query interfaces through forms or templates. In order to keep the query interfaces simple and efficient, it is desirable to design concise template sets for data sources. In this paper, we study the problem of minimizing the number of templates required to represent the query interface of a Web source. We show that the problem is intractable in general. However, we develop efficient minimization algorithms for problem instances that occur often in practice. We also present techniques that yield approximate solutions to the general case of the problem.