Predicate rewriting for translating Boolean queries in a heterogeneous information system

ABSTRACT

Searching over heterogeneous information sources is difficult in part because of the nonuniform query languages. Our approach is to allow users to compose Boolean queries in one rich front-end language. For each user query and target source, we transform the user query into a subsuming query that can be supported by the source but that may return extra documents. The results are then processed by a filter query to yield the correct final results. In this article we introduce the architecture and associated mechanism for query translation. In particular, we discuss techniques for rewriting predicates in Boolean queries into native subsuming forms, which is a basis of translating complex queries. In addition, we present experimental results for evaluating the cost of postfiltering. We also discuss the drawbacks of this approach and cases when it may not be effective. We have implemented prototype versions of these mechanisms and demonstrated them on heterogeneous Boolean systems.

REFERENCES

• 1: Michelle Q. Wang Baldonado , Terry Winograd, SenseMaker: an information-exploration interface supporting the contextual evolution of a user's interests, Proceedings of the SIGCHI conference on Human factors in computing systems, p.11-18, March 22-27, 1997, Atlanta, Georgia, United States [doi>10.1145/258549.258563]
• 2: BALDONADO, M., CHANG, C.-C. K., GRAVANO, L., AND PAEPCKE, A. 1997a. The Stanford Digital Library metadata architecture. Int. J. Dig. Lib. 1, 2 (Sept.), 108-121.
• 3: Michelle Baldonado , Chen-Chuan K. Chang , Luis Gravano , Andreas Paepcke, Metadata for digital libraries: architecture and design rationale, Proceedings of the second ACM international conference on Digital libraries, p.47-56, July 23-26, 1997, Philadelphia, Pennsylvania, United States [doi>10.1145/263690.263791]
• 4: Chen-Chuan K. Chang , Héctor García-Molina, Evaluating the cost of Boolean query mapping, Proceedings of the second ACM international conference on Digital libraries, p.103-112, July 23-26, 1997, Philadelphia, Pennsylvania, United States [doi>10.1145/263690.263802]
• 5: Chen-Chuan K. Chang , Héctor García-Molina, Mind your vocabulary: query mapping across heterogeneous information sources, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.335-346, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 6: Kevin Chen-Chuan Chang , Hector Garcia-Molina , Andreas Paepcke, Boolean Query Mapping Across Heterogeneous Information Sources, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.515-521, August 1996 [doi>10.1109/69.536244]
• 7: Kevin C Chang , Hector Garcia-Molina , Andreas Paepcke, Boolean Query Mapping Across Heterogeneous Information Sources (Extended Version), Stanford University, Stanford, CA, 1997
• 8: CRYSTAL, M. I. AND JAKOBSON, G. E. 1982. FRED, a front end for databases. Online 6, 5 (Sept.), 27-30.
• 9: Ronald Fagin, Combining fuzzy information from multiple systems (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.216-226, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237715]
• 10: Chris Faloutsos, Access methods for text, ACM Computing Surveys (CSUR), v.17 n.1, p.49-74, March 1985 [doi>10.1145/4078.4080]
• 11: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 12: GARC A-MOLINA, H., HAMMER, J., IRELAND, K., PAPAKONSTANTINOU, Y., ULLMAN, J., AND WIDOM, J. 1995. Integrating and accessing heterogeneous information sources in TSIMMIS. In Proceedings of the AAAI Spring Symposium on Information Gathering (Stanford, CA, Mar.). AAAI Press, Menlo Park, CA, 61-64.
• 13: Capability-Sensitive Query Processing on Internet Sources, Proceedings of the 15th International Conference on Data Engineering, p.50, March 23-26, 1999
• 14: Luis Gravano , Hector Garcia-Molina, Merging Ranks from Heterogeneous Internet Sources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.196-205, August 25-29, 1997
• 15: Luis Gravano , Chen-Chuan K. Chang , Héctor García-Molina , Andreas Paepcke, STARTS: Stanford proposal for Internet meta-searching, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.207-218, May 11-15, 1997, Tucson, Arizona, United States
• 16: Luis Gravano , Héctor García-Molina , Anthony Tomasic, The effectiveness of GIOSS for the text database discovery problem, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.126-137, May 24-27, 1994, Minneapolis, Minnesota, United States
• 17: HARMAN, D. 1993. Document detection overview. In Proceedings of the TIPSTER Text Program (Phase I) (Fredricksburg, VA, Sept.). Morgan Kaufmann Publishers Inc., San Francisco, CA.
• 18: HAWKINS, D. T. AND LEVY, L. R. 1985. Front end software for online database searching Part 1: Definitions, system features, and evaluation. Online 9, 6 (Nov.), 30-37.
• 19: HOWE, D. 1997. The free on-line dictionary of computing. Available via http://wombat.doc. ic.ac.uk/.
• 20: IEE. 1991. INSPEC Thesaurus. The Institution of Electrical Engineers, London, UK.
• 21: ISO. 1993. Information and Documentation--Commands for Interactive Text Searching. 1st ed. IOS Press, Amsterdam, The Netherlands.
• 22: Steven P. Ketchpel , Hector Garcia-Molina , Andreas Paepcke, Shopping models: a flexible architecture for information commerce, Proceedings of the second ACM international conference on Digital libraries, p.65-74, July 23-26, 1997, Philadelphia, Pennsylvania, United States [doi>10.1145/263690.263795]
• 23: KIRK, T., LEVY, A. Y., SAGIV, Y., AND SRIVASTAVA, D. 1995. The information manifold. In Papers from the AAAI Spring Symposium on Information Gathering in Distributed Heterogenous Environments (Menlo Park, CA, Mar.), C. Knoblock and A. Levy, Eds. AAAI Press, Menlo Park, CA, 85-91.
• 24: Arjan Loeffen, Text databases: a survey of text models and systems, ACM SIGMOD Record, v.23 n.1, p.97-106, March 1994 [doi>10.1145/181550.181565]
• 25: LOVINS, J. B. 1968. Development of a stemming algorithm. Mech. Trans. Comput. Ling. 11, 1-2, 22-31.
• 26: MARCUS, R. S. 1982. User assistance in bibliographic retrieval networks through a computer intermediary. IEEE Trans. Syst. Man Cybern. SMC-12, 2, 116-133.
• 27: MARTIN, T. H. 1974. A feature analysis of interactive retrieval systems. Rep. SU-COMM-ICR-74-1. Institute of Communication Research, Stanford University, Stanford, CA.
• 28: Edward J. McCluskey, Logic design principles with emphasis on testable semicustom circuits, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 29: Patrick C. Mitchell, A note about the proximity operators in information retrieval, Proceedings of the 1973 meeting on Programming languages and information retrieval, p.177-180, November 04-06, 1973, Gaithersburg, Maryland
• 30: NISO. 1993. Z39.58-1992 Common Command Language for Online Interactive Information Retrieval. NISO Press, Bethesda, MD.
• 31: NISO. 1995. Information Retrieval (Z39.50): Application service definition and protocol specification. Tech. Rep. ANSI/NISO Z39.50-1995. NISO Press, Bethesda, MD. Available via http://lcweb.loc.gov/z3950/agency/.
• 32: Gonzalo Navarro , Ricardo Baeza-Yates, A language for queries on structure and contents of textual databases, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.93-101, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215336]
• 33: NEGUS, A. E. 1979. Development of the Euronet-Diane Common Command Language. In Proceedings of the 3rd International Online Information Meeting. Learned Information Ltd., Oxford, UK, 95-98.
• 34: Andreas Paepcke, An Object-Oriented View Onto Public, Heterogeneous Text Databases, Proceedings of the Ninth International Conference on Data Engineering, p.484-493, April 19-23, 1993
• 35: Yannis Papakonstantinou , Ashish Gupta , Hector Garcia-Molina , Jeffrey D. Ullman, A Query Translation Scheme for Rapid Implementation of Wrappers, Proceedings of the Fourth International Conference on Deductive and Object-Oriented Databases, p.161-186, December 04-07, 1995
• 36: PORTER, M. F. 1980. An algorithm for suffix stripping. Program 14, 3 (July), 130-137.
• 37: PREECE, S. AND WILLIAMS, M. 1980. Software for the searcher's workbench. In Proceedings of the 43rd American Society for Information Science Annual Meeting (Palo Alto, CA, Oct.). Knowledge Industry Publications, Inc., White Plains, NY, 403-405.
• 38: RAO, R. AND RAJARAMAN, A. 1994. GAIA technical overview. Tech. Rep. Xerox PARC, Palo Alto, CA.
• 39: Ramana Rao , Daniel M. Russell , Jock D. Mackinlay, System components for embedded information retrieval from multiple disparate information sources, Proceedings of the 6th annual ACM symposium on User interface software and technology, p.23-33, December 1993, Atlanta, Georgia, United States [doi>10.1145/168642.168645]
• 40: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 41: SELBERG, E. AND ETZIONI, O. 1995. Multi-service search and comparison using the MetaCrawler. In Proceedings of the 4th International WWW Conference (Boston, MA, Dec.).
• 42: TOLIVER, D. E. 1982. OL'SAM: An intelligent front-end for bibliographic information retrieval. Inf. Technol. Libr. 1, 4, 317-326.
• 43: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 44: Jeffrey D. Ullman, Information Integration Using Logical Views, Proceedings of the 6th International Conference on Database Theory, p.19-40, January 08-10, 1997
• 45: Ellen M. Voorhees , Richard M. Tong, Multiple search engines in database merging, Proceedings of the second ACM international conference on Digital libraries, p.93-102, July 23-26, 1997, Philadelphia, Pennsylvania, United States [doi>10.1145/263690.263800]
• 46: Gio Wiederhold, Mediators in the Architecture of Future Information Systems, Computer, v.25 n.3, p.38-49, March 1992 [doi>10.1109/2.121508]
• 47: Martha E. Williams, Transparent information systems through gateways, front ends, intermediaries, and interfaces, Journal of the American Society for Information Science, v.37 n.4, p.204-214, July 1986 [doi>10.1002/(SICI)1097-4571(198607)37:4<204::AID-ASI5>3.0.CO;2-P]
• 48: Stephan Zinn , Martin Sellers , Debra Bohli, OCLC's intelligent gateway service: online information access for libraries, Library Hi Tech, v.4 n.3, p.25-29, Oct. 1986 [doi>10.1108/eb047653]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation; Search process
      H.3.7 Digital Libraries
          Subjects: Systems issues

General Terms:
Algorithms, Experimentation, Languages, Measurement

Keywords:
Boolean queries, content-based retrieval, filtering, predicate rewriting, query subsumption, query translation