Pipelining: A Technique for Implementing Data Restructurers.

Barron C. Housel: Pipelining: A Technique for Implementing Data Restructurers. ACM Trans. Database Syst. 4(4): 470-492(1979)
  author    = {Barron C. Housel},
  title     = {Pipelining: A Technique for Implementing Data Restructurers},
  journal   = {ACM Trans. Database Syst.},
  volume    = {4},
  number    = {4},
  year      = {1979},
  pages     = {470-492},
  ee        = {, db/journals/tods/Housel79.html},
  bibsource = {DBLP,}


In the past several years much attention has been given to the problem of data translation. The focus has been mainly on methodologies and specification languages for accomplishing this task. Recently, several prototype systems have emerged, and now the issues of implementation and performance must be addressed. In general, a data restructuring specification may contain multiple source and target files. This specification can be viewed as a "process graph" which is a network of restructuring operations subject to precedence constraints. One technique used to achieve good performance is that of pipelining data in the process graph.

In this paper we address a number of issues pertinent to a pipelining architecture. Specifically, we give algorithms for resolving deadlock situations which can arise, and partitioning the process graph to achieve an optimal schedule for executing the restructuring steps. In addition, we discuss how pipelining has influenced the design of the restructuring operations and the file structures used in an actual system.

Copyright © 1979 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


CODASYL: Stored-data description and data translation: a model and language. Inf. Syst. 2(3): 95-148(1977) BibTeX
Barron C. Housel, Diane C. P. Smith, Nan C. Shu, Vincent Y. Lum: DEFINE: A Non-Procedural Data Description Language for Defining Information Easily. ACM Pacific 1975: 62-70 BibTeX
Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
Philip P. Macri: Deadlock Detection and Resolution in a CODASYL Based Data Management System. SIGMOD Conference 1976: 45-49 BibTeX
Shamkant B. Navathe, James P. Fry: Restructuring for Large Data Bases: Three Levels of Abstraction. ACM Trans. Database Syst. 1(2): 138-158(1976) BibTeX
Nan C. Shu, Barron C. Housel, Vincent Y. Lum: CONVERT: A High Level Translation Definition Language for Data Conversion. Commun. ACM 18(10): 557-567(1975) BibTeX
Nan C. Shu, Barron C. Housel, Robert W. Taylor, Sakti P. Ghosh, Vincent Y. Lum: EXPRESS: A Data EXtraction, Processing, amd REStructuring System. ACM Trans. Database Syst. 2(2): 134-174(1977) BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:38:41 2008