Parallel evaluation of a deductive query with a breadth-first search strategy

Sang H. Oh, Won S. Lee

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


The query evaluation in a deductive database system requires not only a number of deductive laws to be processed but also a large volume of facts to be matched. To achieve more parallelism embedded in the logical representation of deductive databases, this paper proposes a parallel execution method that expands an AND-OR query tree with a breadth-first strategy. In order to cope with the recursive invocation of a query, the AND/OR tree is expanded in an incremental way. As a result, the two major operations, fact-matching and law-expanding, of the query evaluation can be performed separately. Compared with other approaches to parallelize the query evaluation process, the proposed method eliminates the producer-consumer dependency among shared variables and provides a convenient way to collect all alternative answers by the late binding of the variables in a query.

Original languageEnglish
Pages (from-to)89-99
Number of pages11
JournalUnknown Journal
Issue number2
Publication statusPublished - 2000

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Parallel evaluation of a deductive query with a breadth-first search strategy'. Together they form a unique fingerprint.

Cite this