Querying structured information sources on the web

ABSTRACT

To provide access to distributed and heterogeneous sources, information integration systems have traditionally relied on the availability of a mediated schema, along with mappings between this schema and the schema of the information sources. Queries posed to the mediated schema are then reformulated in terms of the source schemas. On the Web, where sources are plentiful, autonomous and extremely volatile, a system based on the existence of a pre-defined mediated schema and mapping information presents several drawbacks. Notably, the cost of keeping the mappings up to date as new sources are found or existing sources change can be prohibitively high. In this paper, we propose a new querying mechanism for integrating a large number of sources that requires neither a mediated schema nor source mappings. In the absence of a mediated schema, the user formulates queries based on what she expects to find. These queries are rewritten using a best-effort approach: the rewriting component compares a user query against the source schemas and produces a set of rewritings based on the matches found. We demonstrate the feasibility of this approach by providing a query interface for integrating hundreds of (real) structured Web information sources. We also discuss experimental results which indicate that our query rewriting algorithm can be effective.

REFERENCES

• 1: Serge Abiteboul , Oliver M. Duschka, Complexity of answering queries using materialized views, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.254-263, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275516]
• 2: Luciano Barbosa , Juliana Freire, An adaptive crawler for locating hidden-Web entry points, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242632]
• 3: Soumen Chakrabarti , Kunal Punera , Mallela Subramanyam, Accelerated focused crawling through online relevance feedback, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511466]
• 4: S. Chawathe, H. Garcia-Molina, J. Hammer, K. Ireland, Y. Papakonstantinou, J. D. Ullman, and J. Widom. The TSIMMIS project: Integration of heterogeneous information sources. In 16th Meeting of the Information Processing Society of Japan, pages 7--18, Tokyo, Japan, 1994.
• 5: Chandra Chekuri , Anand Rajaraman, Conjunctive query containment revisited, Theoretical Computer Science, v.239 n.2, p.211-229, May 28, 2000 [doi>10.1016/S0304-3975(99)00220-0]
• 6: Hasan Davulcu , Juliana Freire , Michael Kifer , I. V. Ramakrishnan, A layered architecture for querying dynamic Web content, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.491-502, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 7: Oliver M. Duschka , Michael R. Genesereth, Answering recursive queries using views, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.109-116, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263674]
• 8: Marc Friedman , Alon Levy , Todd Millstein, Navigational plans for data integration, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.67-73, July 18-22, 1999, Orlando, Florida, United States
• 9: Hector Garcia-Molina , Yannis Papakonstantinou , Dallan Quass , Anand Rajaraman , Yehoshua Sagiv , Jeffrey Ullman , Vasilis Vassalos , Jennifer Widom, The TSIMMIS Approach to Mediation: Data Models and Languages, Journal of Intelligent Information Systems, v.8 n.2, p.117-132, March/April 1997 [doi>10.1023/A:1008683107812]
• 10: Alon Y. Halevy, Theory of answering queries using views, ACM SIGMOD Record, v.29 n.4, p.40-47, Dec. 2000 [doi>10.1145/369275.369284]
• 11: Bin He , Kevin Chen-Chuan Chang, Statistical schema matching across web query interfaces, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872784]
• 12: T. Kirk, A. Y. Levy, Y. Sagiv, and D. Srivastava. The Information Manifold. In C. Knoblock and A. Levy, editors, Information Gathering from Heterogeneous, Distributed Environments, Stanford University, Stanford, California, 1995.
• 13: 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
• 14: P. McBrien and A. Poulovassilis. Data integration by bi-directional schema transformation rules, 2003.
• 15: R. McCann, A. Doan, V. Varadaran, A. Kramnik, and C. Zhai. Building data integration systems: A mass collaboration approach. In WebDB, pages 25--30, 2003.
• 16: Rachel Pottinger , Alon Y. Levy, A Scalable Algorithm for Answering Queries Using Views, Proceedings of the 26th International Conference on Very Large Data Bases, p.484-495, September 10-14, 2000
• 17: 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]
• 18: Igor Tatarinov , Zachary Ives , Jayant Madhavan , Alon Halevy , Dan Suciu , Nilesh Dalvi , Xin (Luna) Dong , Yana Kadiyska , Gerome Miklau , Peter Mork, The Piazza peer data management project, ACM SIGMOD Record, v.32 n.3, September 2003 [doi>10.1145/945721.945732]
• 19: Jeffrey D. Ullman, Principles of Database and Knowledge-Base Systems: Volume II: The New Technologies, W. H. Freeman & Co., New York, NY, 1990
• 20: Jeffrey D. Ullman, Information integration using logical views, Theoretical Computer Science, v.239 n.2, p.189-210, May 28, 2000 [doi>10.1016/S0304-3975(99)00219-4]