Exporting and interactively querying Web service-accessed sources: The CLIDE System

ABSTRACT

The CLIDE System assists the owners of sources that participate in Web service-based data publishing systems to publish a restricted set of parameterized queries over the schema of their sources and package them as WSDL services. The sources may be relational databases, which naturally have a schema, or ad hoc information/application systems whereas the owner publishes a virtual schema. CLIDE allows information clients to pose queries over the published schema and utilizes prior work on answering queries using views to answer queries that can be processed by combining and processing the results of one or more Web service calls. These queries are called feasible. Contrary to prior work, where infeasible queries are rejected without an explanatory feedback, leading the user into a frustrating trial-and-error cycle, CLIDE features a query formulation interface, which extends the QBE-like query builder of Microsoft's SQL Server with a color scheme that guides the user toward formulating feasible queries. CLIDE guarantees that the suggested query edit actions are complete (i.e., each feasible query can be built by following only suggestions), rapidly convergent (the suggestions are tuned to lead to the closest feasible completions of the query), and suitably summarized (at each interaction step, only a minimal number of actions needed to preserve completeness are suggested). We present the algorithms, implementation, and performance evaluation showing that CLIDE is a viable on-line tool.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Biron, P. V. and Malhotra, A. 2004. XML Schema part 2: Datatypes second edition. W3C Recommendation 28 October 2004. Go online to http://www.w3.org/TR/xmlschema-2/.
• 3: Boag, S., Chamberlin, D., Fernandez, M. F., Florescu, D., Robie, J., and Siméon, J. 2007. XQuery 1.0: An XML query language. W3C Recommendation 23 January 2007. Go online to http://www.w3.org/TR/xquery/.
• 4: Vinayak Borkar , Michael Carey , Dmitry Lychagin , Till Westmann , Daniel Engovatov , Nicola Onose, Query processing in the aqualogic data services platform, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 5: 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]
• 6: Michael Carey, Data delivery in a service-oriented world: the BEA aquaLogic data services platform, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142551]
• 7: 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
• 8: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 9: Christensen, E., Curbera, F., Meredith, G., and Weerawarana, S. 2001. Web Services Description Language (WSDL) 1.1. W3C Note 15 March 2001. Go online to http://www.w3.org/TR/wsdl.
• 10: Xin Dong , Alon Halevy , Jayant Madhavan , Ema Nemes , Jun Zhang, Similarity search for web services, Proceedings of the Thirtieth international conference on Very large data bases, p.372-383, August 31-September 03, 2004, Toronto, Canada
• 11: Duschka, O. M., Genesereth, M. R., and Levy, A. Y. 2000. Recursive query plans for data integration. J. Log. Program. 43, 1, 49--73.
• 12: Fallside, D. C. and Walmsley, P. 2004. XML schema part 0: Primer second edition. W3C Recommendation 28 October 2004. Go online to http://www.w3.org/TR/xmlschema-0/.
• 13: Wenfei Fan , Chee-Yong Chan , Minos Garofalakis, Secure XML querying with security views, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007634]
• 14: Jeffrey D. Ullman , Hector Garcia-Molina , Jennifer Widom, Database Systems: The Complete Book, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 15: Alon Y. Halevy, Answering queries using views: A survey, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.270-294, December 2001 [doi>10.1007/s007780100054]
• 16: Jordan, D. and Evdemon, J. 2006. Web Services Business Process Execution Language Version 2.0. OASIS Public Review Draft, 23th August, 2006. Go online to http://docs.oasis-open.org/wsbpel/2.0/wsbpel-specification-draft.html.
• 17: Kristen LeFevre , Rakesh Agrawal , Vuk Ercegovac , Raghu Ramakrishnan , Yirong Xu , David DeWitt, Limiting disclosure in hippocratic databases, Proceedings of the Thirtieth international conference on Very large data bases, p.108-119, August 31-September 03, 2004, Toronto, Canada
• 18: 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]
• 19: Chen Li , Edward Chang, Answering queries with useful bindings, ACM Transactions on Database Systems (TODS), v.26 n.3, p.313-343, September 2001 [doi>10.1145/502030.502032]
• 20: Melton, J. 2003a. Database languages---SQL---part 14: XML-related specifications (SQL/XML). In Proceedings of ISO/IEC 9075-14:2003.
• 21: Melton, J. 2003b. Database languages---SQL---part 2: Foundation (SQL/foundation). In Proceedings of ISO/IEC 9075-2:2003.
• 22: Microsoft, Inc. Native XML Web services for Microsoft SQL server. 2005. Go online to http://msdn2.microsoft.com/en-us/library/ms345123.aspx.
• 23: Microsoft, Inc. 2004. Microsoft BizTalk Server. Go online to http://www.microsoft.com/biztalk/.
• 24: Nash, A. and Ludaescher, B. 2004. Processing unions of conjunctive queries with negation under limited access patterns. In Proceedings of EDBT.
• 25: Jakob Nielsen, Designing Web Usability: The Practice of Simplicity, New Riders Publishing, Thousand Oaks, CA, 1999
• 26: Lucian Popa , Yannis Velegrakis , Mauricio A. Hernández , Renée J. Miller , Ronald Fagin, Translating web data, Proceedings of the 28th international conference on Very Large Data Bases, p.598-609, August 20-23, 2002, Hong Kong, China
• 27: Rachel Pottinger , Alon Halevy, MiniCon: A scalable algorithm for answering queries using views, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.2-3, p.182-198, September 2001
• 28: Erhard Rahm , Philip A. Bernstein, A survey of approaches to automatic schema matching, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.334-350, December 2001 [doi>10.1007/s007780100057]
• 29: Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman, Answering queries using templates with binding patterns (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.105-112, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220199]
• 30: Shariq Rizvi , Alberto Mendelzon , S. Sudarshan , Prasan Roy, Extending query rewriting techniques for fine-grained access control, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007631]
• 31: Mary Tork Roth , Peter M. Schwarz, Don't Scrap It, Wrap It! A Wrapper Architecture for Legacy Data Sources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.266-275, August 25-29, 1997
• 32: David W. Shipman, The functional data model and the data languages DAPLEX, ACM Transactions on Database Systems (TODS), v.6 n.1, p.140-173, March 1981 [doi>10.1145/319540.319561]
• 33: Edward R. Tufte, Visual explanations: images and quantities, evidence and narrative, Graphics Press, Cheshire, CT, 1997
• 34: Vasilis Vassalos , Yannis Papakonstantinou, Describing and Using Query Capabilities of Heterogeneous Sources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.256-265, August 25-29, 1997
• 35: Mihalis Yannakakis, Algorithms for acyclic database schemes, Proceedings of the seventh international conference on Very Large Data Bases, p.82-94, September 09-11, 1981, Cannes, France
• 36: Ramana Yerneni , Chen Li , Hector Garcia-Molina , Jeffrey Ullman, Computing capabilities of mediators, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.443-454, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 37: Zloof, M. 1975. Query by example. AFIPS NCC 44, 431--438.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: User interfaces

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing; Relational databases
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Selection process; Query formulation; Information filtering
      H.3.5 On-line Information Services
          Subjects: Data sharing; 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: Interaction styles (e.g., commands, menus, forms, direct manipulation); Graphical user interfaces (GUI)

General Terms:
Algorithms, Design, Performance

Keywords:
Middleware, Web services, limited access patterns, query rewriting