Automated creation of a forms-based database query interface

ABSTRACT

Forms-based query interfaces are widely used to access databases today. The design of a forms-based interface is often a key step in the deployment of a database. Each form in such an interface is capable of expressing only a very limited range of queries. Ideally, the set of forms as a whole must be able to express all possible queries that any user may have. Creating an interface that approaches this ideal is surprisingly hard. In this paper, we seek to maximize the ability of a forms-based interface to support queries a user may ask, while bounding both the number of forms and the complexity of any one form. Given a database schema and content we present an automated technique to generate a good set of forms that meet the above desiderata. While a careful analysis of real or expected query workloads are useful in designing the interface, these query sets are often unavailable or hard to obtain prior to the database even being deployed. Hence generating a good set of forms just using the database itself is a challenging yet important problem. Our experimental analysis shows that our techniques can create a reasonable set of forms, one that can express 60--90% of user queries, without any input from the database administrator. Human experts, without support from software such as ours, are often unable to support as high a fraction of user queries.

REFERENCES

• 1: Geoquery Database: http://www.cs.utexas.edu/users/ml/geo.html.
• 2: Jobsquery Database: http://www.cs.utexas.edu/users/ml/nldata/jobquery.html.
• 3: MiMI - Michigan Molecular Interaction Database: http://mimi.ctaalliance.org.
• 4: NCBI BLAST: http://www.ncbi.nlm.nih.gov/blast/Blast.cgi.
• 5: XMark: An XML Benchmark Project: http://www.xml-benchmark.org/.
• 6: R. Abraham, FoXQ - XQuery by forms, Proceedings of the 2003 IEEE Symposium on Human Centric Computing Languages and Environments, p.289-290, October 28-31, 2003
• 7: Francesca Benzi, Dario Maio, and Stefano Rizzi. VISIONARY: a Viewpoint-based Visual Language for Querying Relational Databases. Journal of Visual Languages and Computing, 10(2), 1999.
• 8: Daniele Braga , Alessandro Campi , Stefano Ceri, XQBE (XQuery By Example): A visual interface to the standard XML query language, ACM Transactions on Database Systems (TODS), v.30 n.2, p.398-443, June 2005 [doi>10.1145/1071610.1071613]
• 9: Mary Elaine Califf and Raymond J. Mooney. Relational Learning of Pattern-Match Rules for Information Extraction. In AAAI, 1999.
• 10: Fabrizio Capobianco , Mauro Mosconi , Lorenzo Pagnin, Looking for convenient alternatives to forms for querying remote databases on the Web: a new iconic interface for progressive queries, Proceedings of the workshop on Advanced visual interfaces, May 27-29, 1996, Gubbio, Italy [doi>10.1145/948449.948467]
• 11: EquiX---a search and query language for XML, Journal of the American Society for Information Science and Technology, v.53 n.6, p.454-466, May, 2002 [doi>10.1002/asi.10058]
• 12: Ben Forta , Raymond Camden , Leon Chalnick , Angela C. Buraglia, Macromedia ColdFusion MX 7 Web Application Construction Kit, Macromedia Press, 2005
• 13: Shishir Gundavaram, CGI programming on the World Wide Web, O'Reilly & Associates, Inc., Sebastopol, CA, 1996
• 14: Michael Halvorson, Microsoft® visual basic® 2008 step by step, Microsoft Press, Redmond, WA, 2008
• 15: Harald Schöning. A Graphical Interface to a Complex-Object Database Management System. In IDS, 1992.
• 16: D. J. Helm and B. W. Thompson. An Approach for Totally Dynamic Forms Processing in Web-Based Applications. In ICEIS (2), 2001.
• 17: H. V. Jagadish , S. Al-Khalifa , A. Chapman , L. V. S. Lakshmanan , A. Nierman , S. Paparizos , J. M. Patel , D. Srivastava , N. Wiwatwattana , Y. Wu , C. Yu, TIMBER: A native XML database, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.274-291, December 2002 [doi>10.1007/s00778-002-0081-x]
• 18: Magesh Jayapandian, Adriane Chapman, et al. Michigan Molecular Interactions (MiMI): Putting the Jigsaw Puzzle Together. Nucleic Acids Research (Database Issue), 35, 2007.
• 19: Sergey Melnik. Generic Model Management: Concepts and Algorithms. Chapter 7. PhD thesis, University of Leipzig, 2004.
• 20: Kenneth J. Mitchell , Jessie B. Kennedy , Peter J. Barclay, A framework for user-interfaces to databases, Proceedings of the workshop on Advanced visual interfaces, May 27-29, 1996, Gubbio, Italy [doi>10.1145/948449.948462]
• 21: Norman Murray , Norman Paton , Carole Goble, Kaleidoquery: a visual query language for object databases, Proceedings of the working conference on Advanced visual interfaces, May 24-27, 1998, L'Aquila, Italy [doi>10.1145/948496.948529]
• 22: Yannis Papakonstantinou , Michalis Petropoulos , Vasilis Vassalos, QURSED: querying and reporting semistructured data, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564714]
• 23: Michalis Petropoulos , Yannis Papakonstantinou , Vasilis Vassalos, Graphical query interfaces for semistructured data: the QURSED system, ACM Transactions on Internet Technology (TOIT), v.5 n.2, p.390-438, May 2005 [doi>10.1145/1064340.1064344]
• 24: A. R. Schmidt , Florian Waas , Martin L. Kersten , D. Florescu , I. Manolescu , M. J. Carey , R. Busse, The XML benchmark project, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 2001
• 25: Arijit Sengupta , Andrew Dillon, Query by templates: a generalized approach for visual query formulation for text dominated databases, Proceedings of the IEEE international forum on Research and technology advances in digital libraries, p.36-47, May 07-09, 1997, Washington, D.C., United States
• 26: Lappoon R. Tang , Raymond J. Mooney, Using Multiple Clause Constructors in Inductive Logic Programming for Semantic Parsing, Proceedings of the 12th European Conference on Machine Learning, p.466-477, September 05-07, 2001
• 27: Anders Tornqvist , Chris Nelson , Mats Johnsson, XML and Objects-The Future for E-Forms on the Web, Proceedings of the 8th Workshop on Enabling Technologies on Infrastructure for Collaborative Enterprises, p.303-308, June 16-18, 1999
• 28: Cong Yu , H. V. Jagadish, Schema summarization, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 29: Moshé M. Zloof, Query-by-example: the invocation and definition of tables and forms, Proceedings of the 1st International Conference on Very Large Data Bases, September 22-24, 1975, Framingham, Massachusetts [doi>10.1145/1282480.1282482]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design, Management, Performance