{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T06:41:25Z","timestamp":1697956885757},"reference-count":7,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":7384,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp; Computers in Japan"],"published-print":{"date-parts":[[1987,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>It has already been shown that the problem of obtaining an optimal strategy for a general query on a distributed database system is NP\u2010hard. On the other hand, simple queries have been known as one class of queries for which an optimal strategy can be obtained efficiently. So far, it has been shown that if the topology of a computer network is a complete graph, then a strategy with the minimum response time for simple queries can be obtained in <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>), where <jats:italic>n<\/jats:italic> is the number of sites of the network.<\/jats:p><jats:p>This paper discusses the problem of obtaining a strategy with the minimum response time for simple queries when the topology of a computer network is a star (in brief, problem RT). We assume that each communication channel of a star network has equal communication capacity, and that each site has an equal capability for data processing. Here, we also assume that the center of a star network is capable of performing so\u2010called broadcasting. In this paper, we present an algorithm called RT of <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>) time for solving problem RT. Algorithm RT constructs a schedule graph that represents an optimal strategy by using the dynamic programming method.<\/jats:p>","DOI":"10.1002\/scj.4690180402","type":"journal-article","created":{"date-parts":[[2007,7,7]],"date-time":"2007-07-07T13:33:11Z","timestamp":1183815191000},"page":"11-23","source":"Crossref","is-referenced-by-count":1,"title":["Response time minimization for processing simple queries in star networks"],"prefix":"10.1002","volume":"18","author":[{"given":"Jun'Ichi","family":"Miyao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tohru","family":"Kikuno","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Noriyoshi","family":"Yoshida","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1983.236170"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1676081"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"A. R.Hevner.The optimization of query processing on distributed database systems Ph. D. Dissertation Purdue Univ. (1979).","DOI":"10.1109\/TSE.1979.234179"},{"key":"e_1_2_1_5_2","unstructured":"K\u2010T.Huang.Minimizing communication cost in distributed query processing is NP\u2010complete Proc. Annual Allerton Conference on Communication Control and Computing pp.842\u2013851(1983)."},{"key":"e_1_2_1_6_2","article-title":"Compressed semi\u2010joins and their applications to distributed query processing","volume":"81","author":"Kambayashi Y.","year":"1981","journal-title":"I. E. C. E. Tech. Reports"},{"key":"e_1_2_1_7_2","article-title":"Processing strategy for simple queries in distributed database systems","volume":"82","author":"Sugihara K.","year":"1982","journal-title":"I. E. C. E. Tech. Reports"},{"key":"e_1_2_1_8_2","volume-title":"Principles of Database Systems","author":"Ullman J. D.","year":"1982"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690180402","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690180402","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T06:40:23Z","timestamp":1697870423000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690180402"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,1]]},"references-count":7,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1987,1]]}},"alternative-id":["10.1002\/scj.4690180402"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690180402","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,1]]}}}