Optimal distributed execution of join queries

DOI10.1016/0898-1221(94)90094-9MaRDI QIDQ1328829zbMATH OpenOpenAlexFDO

Authors Darryn J. Reid

Publication date 8 August 1994

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0898-1221(94)90094-9

zbMATH Keywords

directed graphdistributed networktree search algorithm

Mathematics Subject Classification ID

Database theory (68P15) Information storage and retrieval of data (68P20) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Integer programming (90C10)

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.

Recommendations

• scientific article; zbMATH DE number 4049161
• Optimising the distributed execution of join queries in polynomial time
• Incorporating processor costs in optimizing the distributed execution of join queries
• A Global Heuristic For Distributed Join Operations
• Executing join queries in an uncertain distributed environment
• scientific article; zbMATH DE number 970736

Cites work

• A tree-search algorithm for mixed integer programming problems
• Degrees of acyclicity for hypergraphs and relational database schemes
• scientific article; zbMATH DE number 3890770 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3495856 (Why is no real title available?)
• scientific article; zbMATH DE number 3497901 (Why is no real title available?)
• scientific article; zbMATH DE number 3599820 (Why is no real title available?)
• scientific article; zbMATH DE number 2021555 (Why is no real title available?)
• scientific article; zbMATH DE number 194561 (Why is no real title available?)
• scientific article; zbMATH DE number 3314878 (Why is no real title available?)
• scientific article; zbMATH DE number 3332133 (Why is no real title available?)
• Investigation of some branch and bound strategies for the solution of mixed integer linear programs
• Network flow, transportation and scheduling. Theory and algorithms
• On the Desirability of Acyclic Database Schemes
• Probabilistic analysis of optimization algorithms - some aspects from a practical point of view
• Using Semi-Joins to Solve Relational Queries

Cited in

(16)

• Taxonomy and formal properties of distributed joins
• Incorporating processor costs in optimizing the distributed execution of join queries
• Minimizing the response time of executing a join between fragmented relations in a distributed database system
• Evaluating multiple join queries in a distributed database system
• Extension of the one-shot semijoin strategy to minimize data transmission cost in distributed query processing
• Executing join queries in an uncertain distributed environment
• Allocating relations in a distributed database system
• The propagation of updates to relational tables in a distributed database system
• Optimising the distributed execution of join queries in polynomial time
• On the optimality of strategies for multiple join
• Tie-breaking strategies for fast distance join processing
• scientific article; zbMATH DE number 970736 (Why is no real title available?)
• Computational Science – ICCS 2005
• Optimal Broadcasting Strategies for Conjunctive Queries over Distributed Data
• scientific article; zbMATH DE number 7650999 (Why is no real title available?)
• A distributed join algorithm

This page was built for publication: Optimal distributed execution of join queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1328829)