Scheduling tasks of multi-join queries in a multiprocessor

This paper deals with the problem of scheduling spawned tasks when a query is issued to a database which resides on a MIMD multiprocessor. These tasks have the property that their associated dependency scheme can be presented as a directed tree. We present a theoretical framework with extensive expe rimental simulations which increase the throughput of database applications . We derive a family of algorithms for scheduling tasks, Their performance is tested on several common multiprocessor configurations. For better perfo rmance the adaptation of the scheduling algorithm to the multiprocessor con figuration is examined and analyzed. The scheduling algorithms are divided into two cases: (a) permitted changes in the resources connection scheme of the multiprocessor, and (b) no chang es allowed. The algorithms are scalable and their complexity is computed. I n particular, we present an algorithm for scheduling tasks in the case wher e the construction of a central storage location is permitted. One of the m ain tools for the construction of the above algorithms is the notion of (t, 1)-domination and k-domination sets. Copyright (C) 1999 John Wiley & Sons, Ltd.