Optimal distributed execution of join queries
type: Item
instance of: scholarly article
title: Optimal distributed execution of join queries
zbMATH Open document ID: 0834.68021
DOI: 10.1016/0898-1221(94)90094-9
publication date: 1994-08-08T00:00:00Z
review text: The author D. J. Reid solves the problem: how to execute a special class of queries in a distributed computer system? The queries are moved to contain the join operation only and are presupposed to compose a chain. That is the relations to be join can be arranged \(r = \{r_i \mid i = 1, \ldots, m\}\) such that the corresponding schemes \(R_i\), \(R_{i + n}\), \((i = 1, \ldots, u - 1)\) have attributes in common. The distributed network is represented by a directed graph, with a linear cost function of the amount of data sent and coefficients for the capacity limit of amount of data transmitted between two nodes. Each node (site) has allocated a subset of the relations named in the query. The processor cost are negligated. The author developed a solution of the above mentioned problem based on a tree search algorithm. The algorithm is outlined in pseudocode. It belongs to linear integer programming. Problem size and efficiency are considered. Because of the strong restrictions to the considered queries the results are especially of theoretical interest. The author intends to generalize his results in considering the costs of computation at processor facilities and the response time in answering a query.
Mathematics Subject Classification ID: 68P20
Mathematics Subject Classification ID: 68P15
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C08
zbMATH DE Number: 612184
zbMATH Keywords: distributed network
zbMATH Keywords: directed graph
zbMATH Keywords: tree search algorithm
author: Darryn J. Reid
MaRDI profile type: Publication
full work available at URL: 0898-1221(94)90094-9
OpenAlex ID: W2051476150
cites work: Using Semi-Joins to Solve Relational Queries
cites work: On the Desirability of Acyclic Database Schemes
cites work: Q4692527
cites work: Degrees of acyclicity for hypergraphs and relational database schemes
cites work: Q3347338
cites work: A tree-search algorithm for mixed integer programming problems
cites work: Investigation of some branch and bound strategies for the solution of mixed integer linear programs
cites work: Q3818127
cites work: Q4077727
cites work: Q4079613
cites work: Q5609054
cites work: Probabilistic analysis of optimization algorithms - some aspects from a practical point of view
cites work: Q4441489
cites work: Q3941433
cites work: Q4166568
cites work: Q5595961
cites work: Network flow, transportation and scheduling. Theory and algorithms
published in: Computers & Mathematics with Applications
Recommended article: Q3786042
Recommended article: Optimising the distributed execution of join queries in polynomial time
Recommended article: Incorporating processor costs in optimizing the distributed execution of join queries
Recommended article: A Global Heuristic For Distributed Join Operations
Recommended article: Executing join queries in an uncertain distributed environment
Recommended article: Q5688927
description: scientific article; zbMATH DE number 612184