An overview of parallel strategies for transitive closure on algebraic machines

Filippo Cacace, Stefano Ceri, M.A.W. Houtsma, Maurice A.W. Houtsma

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

8 Citations (Scopus)
13 Downloads (Pure)

Abstract

An important feature of database technology of the nineties is the use of distributed computation for speeding up the execution of complex queries. Today, the use of parallelism is tested in several experimental database architectures and a few commercial systems for conventional select-project-join queries. In particular, hash-based fragmentation is used to distribute data to disks under the control of different processors, in multi-processor architectures without shared memory, in order to perform selections and joins in parallel. With the development of new (logic) query languages and deductive databases, the new dimension of recursion has been added to query processing. Transitive closure queries, such as bill-of-material, allow important database problems to be solved by the database system itself; and more general logic programming queries allow us to study queries not considered before. Although recursive queries are very complex, their regular structure makes them particularly suited for parallel execution. Well-considered use of parallelism can give a high efficiency gain when processing recursive queries. In this paper, we give an overview of approaches to parallel execution of recursive queries as they have been presented in recent literature. After showing that the most typical Datalog queries have exactly the same expressive power as the transitive closure of simple algebraic expressions, we focus on describing algebraic approaches to recursion. To give a good overview of the problems that are inherent to parallel computation, we introduce a graphical formalism to describe parallel execution. This formalism enables us to clearly show the behaviour of parallel execution strategies. We first review algorithms developed in the framework of algebraic transitive closures that operate on entire relations; then we introduce fragmentation, distinguishing between hash-based and semantic fragmentation. This research is partially supported by the LOGIDATA + Project of the National Research Council of Italy
Original languageUndefined
Title of host publicationPRISMA Workshop on Parallel Database Systems
EditorsPierre America
Place of PublicationLondon
PublisherSpringer
Pages44-62
Number of pages19
ISBN (Print)3-540-54132-5
DOIs
Publication statusPublished - Sep 1990

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume503
ISSN (Print)0302-9743

Keywords

  • EWI-11057
  • DB-PDB: PARALLEL DATABASES
  • IR-61916
  • METIS-141432

Cite this

Cacace, F., Ceri, S., Houtsma, M. A. W., & Houtsma, M. A. W. (1990). An overview of parallel strategies for transitive closure on algebraic machines. In P. America (Ed.), PRISMA Workshop on Parallel Database Systems (pp. 44-62). [10.1007/3-540-54132-2_49] (Lecture Notes in Computer Science; Vol. 503). London: Springer. https://doi.org/10.1007/3-540-54132-2_49