Data fragmentation for parallel transitive closure strategies

Maurice A.W. Houtsma, M.A.W. Houtsma, Peter M.G. Apers, Gideon L.V. Schipper

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)
42 Downloads (Pure)

Abstract

A topic that is currently inspiring a lot of research is parallel (distributed) computation of transitive closure queries. In [lo] the disconnection set approach has been introduced as an effective strategy for such a computation. It involves reformulating a transitive closure query on a relation into a number of transitive closure queries on smaller fragments; these queries can then execute independently on the fragments, without need for communication and without computing the same tuples at more than one processor. Now that effective strategies as just mentioned have been developed, the next problem is that of developing adequate data fragmentation strategies for these approaches. This is a dificult problem, but of paramount importance to the success of these approaches. We discuss the issues that influence data fragmentation. We present a number of algorithms, each focusing on one of the important issues. We discuss the pros and cons of the algorithms, and we give some results of applying the algorithms to different types of graphs. This last aspect shows to what respect the algorithms indeed conform to the goals we set out.
Original languageUndefined
Title of host publicationProceedings of the 9th International Conference on Data Engineering (ICDE 1993)
Place of PublicationLos Alamitos
PublisherIEEE
Pages447-456
Number of pages10
ISBN (Print)0-8186-3570-3
DOIs
Publication statusPublished - Apr 1993
Event9th International Conference on Data Engineering, ICDE 1993 - Vienna, Austria
Duration: 19 Apr 199323 Apr 1993
Conference number: 9

Publication series

Name
PublisherIEEE
ISSN (Print)1063-6382

Conference

Conference9th International Conference on Data Engineering, ICDE 1993
Abbreviated titleICDE
CountryAustria
CityVienna
Period19/04/9323/04/93

Keywords

  • EWI-7260
  • METIS-119786
  • DB-PDB: PARALLEL DATABASES
  • IR-19263

Cite this

Houtsma, M. A. W., Houtsma, M. A. W., Apers, P. M. G., & Schipper, G. L. V. (1993). Data fragmentation for parallel transitive closure strategies. In Proceedings of the 9th International Conference on Data Engineering (ICDE 1993) (pp. 447-456). Los Alamitos: IEEE. https://doi.org/10.1109/ICDE.1993.344036
Houtsma, Maurice A.W. ; Houtsma, M.A.W. ; Apers, Peter M.G. ; Schipper, Gideon L.V. / Data fragmentation for parallel transitive closure strategies. Proceedings of the 9th International Conference on Data Engineering (ICDE 1993). Los Alamitos : IEEE, 1993. pp. 447-456
@inproceedings{adee0ecf55e348bb8f2ece81b3b09fc0,
title = "Data fragmentation for parallel transitive closure strategies",
abstract = "A topic that is currently inspiring a lot of research is parallel (distributed) computation of transitive closure queries. In [lo] the disconnection set approach has been introduced as an effective strategy for such a computation. It involves reformulating a transitive closure query on a relation into a number of transitive closure queries on smaller fragments; these queries can then execute independently on the fragments, without need for communication and without computing the same tuples at more than one processor. Now that effective strategies as just mentioned have been developed, the next problem is that of developing adequate data fragmentation strategies for these approaches. This is a dificult problem, but of paramount importance to the success of these approaches. We discuss the issues that influence data fragmentation. We present a number of algorithms, each focusing on one of the important issues. We discuss the pros and cons of the algorithms, and we give some results of applying the algorithms to different types of graphs. This last aspect shows to what respect the algorithms indeed conform to the goals we set out.",
keywords = "EWI-7260, METIS-119786, DB-PDB: PARALLEL DATABASES, IR-19263",
author = "Houtsma, {Maurice A.W.} and M.A.W. Houtsma and Apers, {Peter M.G.} and Schipper, {Gideon L.V.}",
note = "Imported from EWI/DB PMS [db-utwente:inpr:0000003127]",
year = "1993",
month = "4",
doi = "10.1109/ICDE.1993.344036",
language = "Undefined",
isbn = "0-8186-3570-3",
publisher = "IEEE",
pages = "447--456",
booktitle = "Proceedings of the 9th International Conference on Data Engineering (ICDE 1993)",
address = "United States",

}

Houtsma, MAW, Houtsma, MAW, Apers, PMG & Schipper, GLV 1993, Data fragmentation for parallel transitive closure strategies. in Proceedings of the 9th International Conference on Data Engineering (ICDE 1993). IEEE, Los Alamitos, pp. 447-456, 9th International Conference on Data Engineering, ICDE 1993, Vienna, Austria, 19/04/93. https://doi.org/10.1109/ICDE.1993.344036

Data fragmentation for parallel transitive closure strategies. / Houtsma, Maurice A.W.; Houtsma, M.A.W.; Apers, Peter M.G.; Schipper, Gideon L.V.

Proceedings of the 9th International Conference on Data Engineering (ICDE 1993). Los Alamitos : IEEE, 1993. p. 447-456.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Data fragmentation for parallel transitive closure strategies

AU - Houtsma, Maurice A.W.

AU - Houtsma, M.A.W.

AU - Apers, Peter M.G.

AU - Schipper, Gideon L.V.

N1 - Imported from EWI/DB PMS [db-utwente:inpr:0000003127]

PY - 1993/4

Y1 - 1993/4

N2 - A topic that is currently inspiring a lot of research is parallel (distributed) computation of transitive closure queries. In [lo] the disconnection set approach has been introduced as an effective strategy for such a computation. It involves reformulating a transitive closure query on a relation into a number of transitive closure queries on smaller fragments; these queries can then execute independently on the fragments, without need for communication and without computing the same tuples at more than one processor. Now that effective strategies as just mentioned have been developed, the next problem is that of developing adequate data fragmentation strategies for these approaches. This is a dificult problem, but of paramount importance to the success of these approaches. We discuss the issues that influence data fragmentation. We present a number of algorithms, each focusing on one of the important issues. We discuss the pros and cons of the algorithms, and we give some results of applying the algorithms to different types of graphs. This last aspect shows to what respect the algorithms indeed conform to the goals we set out.

AB - A topic that is currently inspiring a lot of research is parallel (distributed) computation of transitive closure queries. In [lo] the disconnection set approach has been introduced as an effective strategy for such a computation. It involves reformulating a transitive closure query on a relation into a number of transitive closure queries on smaller fragments; these queries can then execute independently on the fragments, without need for communication and without computing the same tuples at more than one processor. Now that effective strategies as just mentioned have been developed, the next problem is that of developing adequate data fragmentation strategies for these approaches. This is a dificult problem, but of paramount importance to the success of these approaches. We discuss the issues that influence data fragmentation. We present a number of algorithms, each focusing on one of the important issues. We discuss the pros and cons of the algorithms, and we give some results of applying the algorithms to different types of graphs. This last aspect shows to what respect the algorithms indeed conform to the goals we set out.

KW - EWI-7260

KW - METIS-119786

KW - DB-PDB: PARALLEL DATABASES

KW - IR-19263

U2 - 10.1109/ICDE.1993.344036

DO - 10.1109/ICDE.1993.344036

M3 - Conference contribution

SN - 0-8186-3570-3

SP - 447

EP - 456

BT - Proceedings of the 9th International Conference on Data Engineering (ICDE 1993)

PB - IEEE

CY - Los Alamitos

ER -

Houtsma MAW, Houtsma MAW, Apers PMG, Schipper GLV. Data fragmentation for parallel transitive closure strategies. In Proceedings of the 9th International Conference on Data Engineering (ICDE 1993). Los Alamitos: IEEE. 1993. p. 447-456 https://doi.org/10.1109/ICDE.1993.344036