Distributing a database for parallel processing is NP-hard

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


In a database the response time to a query can be reduced if certain concurrent operations are provided. In order to maximize the degree of concurrency, data has to be carefully allocated. The complexities of the following two problems are studied in this paper: one is to allocate a database onto a multiple-disk system which maximizes the disk access concurrency; the other one is to allocate a database over a network which minimize the number of nodes being used and a complete parallel searching is possible for a set of queries. Both are shown to be NP-hard (computational intractable) problems.

Original languageEnglish (US)
Pages (from-to)55-60
Number of pages6
JournalACM SIGMOD Record
Issue number1
StatePublished - Jan 9 1983


  • NP-hard
  • database
  • parallel Processing

Cite this