Boolean Query Translation

Boolean Query Translation is an ongoing project in the Stanford Digital Library Project. It deals with the problem of translating Boolean queries into different native languages supported by various search services to make distributed search possible and mask the users from the details of different query languages.

Until now, searching over heterogeneous information sources is difficult because of the non-uniform query languages. Our approach is to allow a user 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 result.

Current Status

We have completed the theoretic work of the algorithms that generate minimal subsuming queries and optimal filters. We have implemented prototype versions of these algorithms and demonstrated them on heterogeneous Boolean systems including Stanford-Folio, Knight -Ridder's DIALOG, and DEC's AltaVista.

Currently, we have been focusing on the following aspects of the query translation problem:

• Metadata specification
  How the metadata about the underlying service's query capability can be specified generally and flexibly.
• Common schema construction
  In additional to the differences in their query languages, dfferent sources also export different set of searchable fields and how they are queried. GIven multiple services as targets of a distributed search, what should be the "common schema" exported to the users?
• Approximate translation
  Sometimes an exact translation, although theoretically correct, may be too strict to be useful. E.g., when the query degenerates to True. If that happens, approximate translation may helps out.
• Translation to non-Boolean services
  Not all search services support Boolean queries...

Publications

Presentation

Comming soon ...

Chen-Chuan Kevin Chang

Hector Garcia-Molina

Andreas Paepcke

Last update: May 13, 1997

Chen-Chuan Kevin Chang
kevin@db.stanford.edu