Predicate rewriting for translating Boolean queries in a heterogeneous information system

Chen Chuan K. Chang, Héctor García-Molina, Andreas Paepcke

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)1-39
Number of pages39
JournalACM Transactions on Information Systems
Issue number1
StatePublished - Jan 1999
Externally publishedYes


  • Algorithms
  • Boolean queries
  • Content-based retrieval
  • Experimentation
  • Filtering
  • Languages
  • Measurement
  • Predicate rewriting
  • Query subsumption
  • Query translation

ASJC Scopus subject areas

  • Information Systems
  • General Business, Management and Accounting
  • Computer Science Applications


Dive into the research topics of 'Predicate rewriting for translating Boolean queries in a heterogeneous information system'. Together they form a unique fingerprint.

Cite this