Distributing a database for parallel processing is NP-hard
- 1 September 1983
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record
- Vol. 14 (1) , 55-60
- https://doi.org/10.1145/984540.984545
Abstract
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.Keywords
This publication has 4 references indexed in Scilit:
- Disk allocation for Cartesian product files on multiple-disk systemsACM Transactions on Database Systems, 1982
- Algorithms to Distribute a Database for Parallel SearchingIEEE Transactions on Software Engineering, 1981
- Distributing a Data Base with Logical Associations on a Computer Network for Parallel SearchingIEEE Transactions on Software Engineering, 1976
- The Complexity of Near-Optimal Graph ColoringJournal of the ACM, 1976