An efficient processing of a chain join with the minimum communication cost in distributed database systems

Lin X. and Orlowska M.E. (1995) An efficient processing of a chain join with the minimum communication cost in distributed database systems. Distributed and Parallel Databases, 3 1: 69-83. doi:10.1007/BF01263657


Author Lin X.
Orlowska M.E.
Title An efficient processing of a chain join with the minimum communication cost in distributed database systems
Journal name Distributed and Parallel Databases   Check publisher's open access policy
ISSN 0926-8782
Publication date 1995-01-01
Sub-type Article (original research)
DOI 10.1007/BF01263657
Volume 3
Issue 1
Start page 69
End page 83
Total pages 15
Publisher Kluwer Academic Publishers
Subject 2614 Theoretical Computer Science
1710 Information Systems
1703 Computational Theory and Mathematics
Abstract This paper investigates the optimization problem when executing a join in a distributed database environment. The minimization of the communication cost for sending data through links has been adopted as an optimization criterion. We explore in this paper the approach of judiciously using join operations as reducers in distributed query processing. In general, this problem is computationally intractable. A restriction of the execution of a join in a pre-defined combinatorial order leads to a possible solution in polynomial time. An algorithm for a chain query computation has been proposed in [21]. The time complexity of the algorithm is O(m2n2+m3n), where n is the number of sites in the network, and m is the number of relations (fragments) involved in the join. In this paper, we firstly present a proof of the intuitively well understood fact-that the "eigenorder" of a "chain" join will be the best pre-defined combinatorial order to implement the algorithm in [21]. Secondly, we show a sufficient and necessary condition for a chain query with the eigenordering to be a "simple" query. For the process of the class of simple queries, we show a significant reduction of the time complexity from O(m2n2+m3n) to O(mn+m2). It is encouraging that, in practice, the most frequent queries belong to the category of simple queries.
Keyword communication cost
Distributed databases
query processing optimization
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Unknown

Document type: Journal Article
Sub-type: Article (original research)
Collection: Scopus Import
 
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 4 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 12 Jul 2016, 12:39:13 EST by System User