Interactive query formulation over web service-accessed sources

ABSTRACT

Integration systems typically support only a restricted set of queries over the schema they export. The reason is that the participating information sources contribute limited content and limited access methods. In prior work, these limited access methods have often been specified using a set of parameterized views, with the understanding that the integration system accepts only queries which have an equivalent rewriting using the views. These queries are called feasible. Infeasible queries are rejected without an explanatory feedback. To help a developer, who is building an integration application, avoid a frustrating trial-and-error cycle, we introduce the CLIDE query formulation interface, which extends the QBE-like query builder of Microsoft's SQL Server with a coloring scheme that guides the user toward formulating feasible queries. We provide 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: Microsoft SQL Server. http://www.microsoft.com/sql/.
• 2: Amazon E-Commerce Service. http://www.amazon.com/gp/aws/sdk/.
• 3: Google Web APIs. http://www.google.com/apis/.
• 4: Web Services and Service-Oriented Architectures. http://www.service-architecture.com/.
• 5: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 6: O. Duschka, M. Genesereth, and A. Levy. Recursive query plans for data integration. Journal of Logic Programming, 43(1), 2000.
• 7: Jeffrey D. Ullman , Hector Garcia-Molina , Jennifer Widom, Database Systems: The Complete Book, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 8: 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]
• 9: K. LeFevre, R. Agrawal, V. Ercegovac, R. Ramakrishnan, Y. Xu, and D. J. DeWitt. Limiting disclosure in hippocratic databases. In VLDB, pages 108--119, 2004.
• 10: 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]
• 11: 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]
• 12: A. Nash and B. Ludaescher. Processing unions of conjunctive queries with negation under limited access patterns. In EDBT, 2004.
• 13: Jakob Nielsen. Designing Web Usability. New Riders Publishing, 2000.
• 14: 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
• 15: 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]
• 16: 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]
• 17: 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]
• 18: 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
• 19: L. A. Rowe. "fill-in-the-form" programming. In VLDB, 1985.
• 20: Edward R. Tufte, Visual explanations: images and quantities, evidence and narrative, Graphics Press, Cheshire, CT, 1997
• 21: 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
• 22: M. Yannakakis. Algorithms for acyclic database schemes. In VLDB, pages 82--94, 1981.
• 23: 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
• 24: M. Zloof. Query by example. AFIPS NCC, 44:431--438, 1975.

INDEX TERMS

Primary Classification:
  H. Information Systems
  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)

General Terms:
Algorithms, Design, Human Factors, Management

Keywords:
data integration, interactive query formulation, web services