Graphical query interfaces for semistructured data: the QURSED system

ABSTRACT

We describe the QURSED system for the declarative specification and automatic generation of Web-based query forms and reports (QFRs) for semistructured XML data. In QURSED, a QFR is formally described by its query set specification (QSS) which captures the complex query and reporting capabilities of the QFR and the associations of the query set specification with visual elements that implement these capabilities on a Web page. The design-time component of QURSED, called QURSED Editor, semi-automates the development of the query set specification and its association with visual elements by translating intuitive visual actions taken by a developer into appropriate specification fragments. The run-time component of QURSED produces XQuery statements by synthesizing fragments from the query set specification that have been activated during the interaction of the end-user with the QFR and renders the query results in interactive reports as specified by the QSS. We describe the techniques and algorithms employed by QURSED with emphasis on how it accommodates the intricacies introduced by the semistructured nature of the underlying data. We present the formal model of the query set specification, as well as its generation via the QURSED Editor, and focus on the techniques and heuristics the Editor employs for translating visual designer input into meaningful specifications. We also present the algorithms QURSED employs for query generation and report generation. An online demonstration of the system is available at http://www.db.ucsd.edu/qursed/.

REFERENCES

• 1: Abiteboul, S., Buneman, P., and Suciu, D. 2000. Data on the Web. Morgan Kaufman, San Francisco, CA.
• 2: Serge Abiteboul , Luc Segoufin , Victor Vianu, Representing and querying XML with incomplete information, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.150-161, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375571]
• 3: Sihem Amer-Yahia , SungRan Cho , Laks V. S. Lakshmanan , Divesh Srivastava, Minimization of tree pattern queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.497-508, May 21-24, 2001, Santa Barbara, California, United States
• 4: Paolo Atzeni , Giansalvatore Mecca , Paolo Merialdo, To Weave the Web, Proceedings of the 23rd International Conference on Very Large Data Bases, p.206-215, August 25-29, 1997
• 5: BEA Systems, Inc. 2005. Liquid Data for WebLogic. http://bea.com.
• 6: Phil Bernstein , Michael Brodie , Stefano Ceri , David DeWitt , Mike Franklin , Hector Garcia-Molina , Jim Gray , Jerry Held , Joe Hellerstein , H. V. Jagadish , Michael Lesk , Dave Maier , Jeff Naughton , Hamid Pirahesh , Mike Stonebraker , Jeff Ullman, The Asilomar report on database research, ACM SIGMOD Record, v.27 n.4, p.74-80, Dec. 1998 [doi>10.1145/306101.306137]
• 7: Biron, P. V. and Malhotra, A. 2004. XML Schema Part 2: Datatypes Second Edition. W3C Recommendation (Oct.). http://www.w3.org/TR/xmlschema-2/.
• 8: Boag, S., Chamberlin, D., Fernandez, M. F., Florescu, D., Robie, J., and Siméon, J. 2005. XQuery 1.0: An XML Query Language. W3C Working Draft 11 (Feb.). http://www.w3.org/TR/xquery/.
• 9: Michael J. Carey , Laura M. Haas , Vivekananda Maganty , John H. Williams, PESTO: An Integrated Query/Browser for Object Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.203-214, September 03-06, 1996
• 10: Sudarshan S. Chawathe , Thomas Baby , Jihwang Yoo, VQBD: exploring semistructured data, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.603, May 21-24, 2001, Santa Barbara, California, United States
• 11: Sophie Cluet , Claude Delobel , Jérǒme Siméon , Katarzyna Smaga, Your mediators need data conversion!, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.177-188, June 01-04, 1998, Seattle, Washington, United States
• 12: Cohen, S., Kanza, Y., Kogan, Y. A., Nutt, W., Sagiv, Y., and Serebrenik, A. 1999. EquiX---Easy querying in XML databases. In Proceedings of the 2nd International Workshop on the Web and Databases. 43--48.
• 13: Sara Comai , Ernesto Damiani , Piero Fraternali, Computing graphical queries over XML data, ACM Transactions on Information Systems (TOIS), v.19 n.4, p.371-430, October 2001 [doi>10.1145/502795.502797]
• 14: Deutsch, A., Fernandez, M. F., Florescu, D., Levy, A. Y., and Suciu, D. 1998. XML-QL. W3C Query Languages Workshop.
• 15: Deutsch, A., Papakonstantinou, Y., and Xu, Y. 2004. The NEXT logical framework for XQuery. In Proceedings of the 30th International Conference on Very Large Data Bases. 168--179.
• 16: Draper, D., Fankhauser, P., Fernandez, M., Malhotra, A., Rose, K., Rys, M., Siméon, J., and Walder, P. 2005. XQuery 1.0 and XPath 2.0 Formal Semantics. W3C Working Draft (Feb.). http://www.w3.org/TR/xquery-semantics/.
• 17: Denise Draper , Alon Y. Halevy , Daniel S. Weld, The nimble integration engine, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.567-568, May 21-24, 2001, Santa Barbara, California, United States
• 18: Dubinko, M., Klotz, L. L., Merrick, R., and Raman, T. V. 2003. XForms 1.0. W3C Recommendation (Oct.). http://www.w3.org/TR/2003/REC-xforms-20031014/.
• 19: Anat Eyal , Tova Milo, Integrating and customizing heterogeneous e-commerce applications, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.1, p.16-38, August 2001
• 20: Fallside, D. C. and Walmsley, P. 2004. XML Schema Part 0: Primer Second Edition. W3C Recommendation (Oct.). http://www.w3.org/TR/xmlschema-0/.
• 21: Fernandez, M., Malhotra, A., Marsh, J., Nagy, M., and Walsh, N. 2005. XQuery 1.0 and XPath 2.0 Data Model. W3C Working Draft (Feb.). http://www.w3.org/TR/xpath-datamodel/.
• 22: Mary Fernández , Daniela Florescu , Alon Levy , Dan Suciu, Declarative specification of Web sites with S, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.1, p.38-55, March 2000 [doi>10.1007/s007780050082]
• 23: Mary Fernandez , Atsuyuki Morishima , Dan Suciu, Efficient evaluation of XML middle-ware queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.103-114, May 21-24, 2001, Santa Barbara, California, United States
• 24: Piero Fraternali, Tools and approaches for developing data-intensive Web applications: a survey, ACM Computing Surveys (CSUR), v.31 n.3, p.227-263, Sept. 1999 [doi>10.1145/331499.331502]
• 25: Piero Fraternali , Paolo Paolini, Model-driven development of Web applications: the AutoWeb system, ACM Transactions on Information Systems (TOIS), v.18 n.4, p.323-382, Oct. 2000 [doi>10.1145/358108.358110]
• 26: Michael R. Genesereth , Nils J. Nilsson, Logical foundations of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 27: Roy Goldman , Jennifer Widom, Interactive Query and Search in Semistructured Databases, Selected papers from the International Workshop on The World Wide Web and Databases, p.52-62, March 27-28, 1998
• 28: Kay, M. 2005. XSL Transformations (XSLT) Version 2.0. W3C Working Draft (Feb.). http://www.w3.org/TR/xslt20/.
• 29: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 30: Alon Y. Levy , Anand Rajaraman , Joann J. Ordille, Querying Heterogeneous Information Sources Using Source Descriptions, Proceedings of the 22th International Conference on Very Large Data Bases, p.251-262, September 03-06, 1996
• 31: Alon Y. Levy , Anand Rajaraman , Jeffrey D. Ullman, Answering queries using limited external query processors (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.227-237, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237716]
• 32: Bertram Ludäscher , Yannis Papakonstantinou , Pavel Velikhov, Navigation-Driven Evaluation of Virtual Mediated Views, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.150-165, March 27-31, 2000
• 33: Macromedia, Inc. 2003. ColdFusion. http://www.macromedia.com/software/coldfusion/.
• 34: Macromedia, Inc. 2003. Dreamweaver UltraDev. http://www.macromedia.com/software/ultradev/.
• 35: Macromedia, Inc. 2003. HomeSite. http://www.macromedia.com/software/homesite/.
• 36: Malhotra, A., Melton, J., and Walsh, N. 2005. XQuery 1.0 and XPath 2.0 Functions and Operators. W3C Working Draft (Feb.). http://www.w3.org/TR/xpath-functions/.
• 37: Microsoft Corp. 2005. ASP.NET. http://www.asp.net/.
• 38: Microsoft Corp. 2004. BizTalk Server. http://www.microsoft.com/biztalk/.
• 39: Microsoft Corp. 2003. Visual InterDev. http://msdn.microsoft.com/vinterdev/.
• 40: Kevin D. Munroe , Yannis Papakonstantinou, BBQ: A Visual Interface for Integrated Browsing and Querying of XML, Proceedings of the Fifth Working Conference on Visual Database Systems: Advances in Visual Information Management, p.277-296, May 10-12, 2000
• 41: Oracle. 2004. XSQL. http://www.oracle.com.
• 42: Yannis Papakonstantinou , Vinayak Borkar , Maxim Orgiyan , Kostas Stathatos , Lucian Suta , Vasilis Vassalos , Pavel Velikhov, XML queries and algebra in the Enosys integration platform, Data & Knowledge Engineering, v.44 n.3, p.299-322, March 2003 [doi>10.1016/S0169-023X(02)00141-6]
• 43: 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]
• 44: Michalis Petropoulos , Vasilis Vassalos , Yannis Papakonstantinou, XML query forms (XQForms): declarative specification of XML query interfaces, Proceedings of the 10th international conference on World Wide Web, p.642-651, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372170]
• 45: Popa, L., Velegrakis, Y., Miller, R. J., Hernández, M. A., and Fagin, R. 2002. Translating Web data. In Proceedings of the 28th International Conference on Very Large Data Bases. 598--609.
• 46: Dallan Quass , Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman , Jennifer Widom, Querying Semistructured Heterogeneous Information, Proceedings of the Fourth International Conference on Deductive and Object-Oriented Databases, p.319-344, December 04-07, 1995
• 47: Raggett, D., Hors, A. L., and Jacobs, I. 1999. HTML 4.01 Specification. W3C Recommendation (Dec.). http://www.w3.org/TR/html4/.
• 48: Harald Schöning , Jürgen Wäsch, Tamino - An Internet Database System, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.383-387, March 27-31, 2000
• 49: Jayavel Shanmugasundaram , Eugene J. Shekita , Rimon Barr , Michael J. Carey , Bruce G. Lindsay , Hamid Pirahesh , Berthold Reinwald, Efficiently Publishing Relational Data as XML Documents, Proceedings of the 26th International Conference on Very Large Data Bases, p.65-76, September 10-14, 2000
• 50: Avi Silberschatz , Michael Stonebraker , Jeffrey D. Ullman, Database systems: achievements and opportunities, ACM SIGMOD Record, v.19 n.4, p.6-22, Dec. 1990 [doi>10.1145/122058.122059]
• 51: Sun Microsystems, Inc. 2005. JavaServer Pages. http://java.sun.com/products/jsp/.
• 52: Tibco Software Inc. 2005. XML Transform. http://tibco.com.
• 53: Vassalos, V. and Papakonstantinou, Y. 2000. Expressive capabilities description languages and query rewriting algorithms. J. Logic Program. 43, 1, 75--122.
• 54: Zloof, M. M. 1975. Query by example. In Proceedings of the AFIPS Conference. 431--438.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.7 Visual Programming

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications
          Subjects: Tools; Languages
      D.2.2 Design Tools and Techniques
          Subjects: User interfaces
      D.2.6 Programming Environments
          Subjects: Graphical environments

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages; Report writers
      H.2.5 Heterogeneous Databases
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering; Query formulation
      H.3.5 On-line Information Services
          Subjects: Web-based services
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Graphical user interfaces (GUI); Interaction styles (e.g., commands, menus, forms, direct manipulation)

General Terms:
Algorithms, Design, Human Factors, Languages