Allocating relations in a distributed database system
type: Item
instance of: scholarly article
title: Allocating relations in a distributed database system
zbMATH Open document ID: 0835.68033
DOI: 10.1016/0895-7177(95)00153-S
published in: Mathematical and Computer Modelling
publication date: 1996-04-16T00:00:00Z
review text: A model is proposed that allocates tables of a relational database to the sites of a distributed system in order that the total cost of executing a given collection of join queries is minimized. This model is presented in the convenient form of an integer linear program. Each individual query specifies that several logically distinct data sets, or relations, are to be amalgamated and presented to the particular user that issued the request. Performing this task requires the utilization of limited system resources; both processors, and the communications facilities that interconnect them, may be used. An optimal strategy for executing a single query is, therefore, defined to be one that minimizes a weighted sum of the costs of computation, and those of information interchange, incurred during the computation. The total cost of executing an entire group of such queries depends upon the way in which the relevant information is allocated to the sites of the network. Several copies of any particular relation may be dispersed across the network; the replication of data increases its availability, and potentially decreases the costs of answering the given requests. However, only limited storage capacities are available, and increased replication commands greater overheads in maintaining consistency. An optimization program is developed to design a data allocation plan that achieves a minimal total cost for the execution of a given group of requests, while maintaining restraints on the levels of data replication considered permissible.
Mathematics Subject Classification ID: 68P15
zbMATH DE Number: 821731
zbMATH Keywords: distributed database system
zbMATH Keywords: integer program
zbMATH Keywords: join query
zbMATH Keywords: relational database
author: Darryn J. Reid
author: M. E. Orlowska
MaRDI profile type: Publication
cites work: Incorporating processor costs in optimizing the distributed execution of join queries
cites work: Q4746812
cites work: Optimal File Allocation in a Multiple Computer System
cites work: A Nested Dual Ascent Procedure For The Dynamic Single File Allocation Problem
cites work: Optimal distributed execution of join queries
cites work: Evaluating multiple join queries in a distributed database system
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: An improved branch and bound algorithm for mixed integer nonlinear programs
cites work: A tree-search algorithm for mixed integer programming problems
cites work: Nonlinear integer programming algorithms: A survey
cites work: Q5595961
cites work: Quadratic Binary Programming with Application to Capital-Budgeting Problems
cites work: Branch-and-Bound Methods: A Survey
cites work: Investigation of some branch and bound strategies for the solution of mixed integer linear programs
cites work: Q3818127
cites work: Q4077727
description: scientific article; zbMATH DE number 821731