A graph representation of a semi-join program and its optimization

Luk, Lydia Lai-Chu (1982) A graph representation of a semi-join program and its optimization. Masters thesis, Memorial University of Newfoundland.

[img] [English] PDF (Migrated (PDF/A Conversion) from original format: (application/pdf)) - Accepted Version
Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission.

Download (8MB)
  • [img] [English] PDF - Accepted Version
    Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission.
    (Original Version)

Abstract

A semi-join program is considered to be a strategy for processing a query in a distributed database system. To produce such a strategy for a general query, heuristics are required, as the problem of deriving an optimal solution is considered to be difficult. This thesis presents a semi-join program in graph-theoretic terms. In this framework, it seeks to improve the semi-join program by transforming it into one with non-increasing cost and non-decreasing benefit. The transformation algorithm runs in 0(n**3) time where n is the number of semi-joins in the program.

Item Type: Thesis (Masters)
URI: http://research.library.mun.ca/id/eprint/7558
Item ID: 7558
Additional Information: Bibliography: leaves 48-49
Department(s): Science, Faculty of > Computer Science
Date: 1982
Date Type: Submission
Library of Congress Subject Heading: Electronic data processing--Distributed processing; Network analysis (Planning)

Actions (login required)

View Item View Item

Downloads

Downloads per month over the past year

View more statistics