An Intelligent Search Method for Query Optimization by Semijoins

Hyuck Yoo, Stephane Lafortune

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)


Query optimization strategies based on the reduction of the referenced relations by means of semijoins have received considerable attention. The limitations of such strategies have to do with computational efficiency (very large search space of semijoin reduction sequences), optimality of the solution (when heuristics are used), and generality of the class of queries allowed (e.g., simple queries, chain queries, tree queries). We consider the problem of finding an optimal semijoin sequence that fully reduces a given tree query. We present a new method that “intelligently” navigates the space of all semijoin sequences and returns an optimal solution. We report on experiments that show that our method performs very efficiently; on average, less than five percent of the search space is searched before an optimal solution is found. Other advantages of the method are: 1) ease of implementation, 2) generality of the cost model considered, and 3) ability to handle tree queries with arbitrary target lists.

Original languageEnglish
Pages (from-to)226-237
Number of pages12
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number2
Publication statusPublished - 1989 Jun
Externally publishedYes


  • Distributed databases
  • heuristic search
  • optimal
  • query optimization
  • semijoin sequences
  • semijoins

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'An Intelligent Search Method for Query Optimization by Semijoins'. Together they form a unique fingerprint.

Cite this