ACM SIGMOD Anthology VLDB dblp.uni-trier.de

A Parallel Processing Strategy for Evaluating Recursive Queries.

Louiqa Raschid, Stanley Y. W. Su: A Parallel Processing Strategy for Evaluating Recursive Queries. VLDB 1986: 412-419
@inproceedings{DBLP:conf/vldb/RaschidS86,
  author    = {Louiqa Raschid and
               Stanley Y. W. Su},
  editor    = {Wesley W. Chu and
               Georges Gardarin and
               Setsuo Ohsuga and
               Yahiko Kambayashi},
  title     = {A Parallel Processing Strategy for Evaluating Recursive Queries},
  booktitle = {VLDB'86 Twelfth International Conference on Very Large Data Bases,
               August 25-28, 1986, Kyoto, Japan, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1986},
  isbn      = {0-934613-18-4},
  pages     = {412-419},
  ee        = {db/conf/vldb/RaschidS86.html},
  crossref  = {DBLP:conf/vldb/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The set of resolvents generated by a recursive intension in a first-order database is treated as a set of concurrent database queries. A strategy for efficiently evaluating these concurrent queries in a multi-processor environment is presented. The strategy combines three query processing techniques, namely, query decomposition, intermediate result sharing and data-flow and pipelined query execution to achieve a high degree of parallelism. An analytical study uses the response time for each resolvent and the execution time for a set of resolvents as a performance measure to examine the performance gain due to the data-flow and pipelined approach to query processing.

Copyright © 1986 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, Yahiko Kambayashi (Eds.): VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings. Morgan Kaufmann 1986, ISBN 0-934613-18-4
Contents BibTeX

References

[AST76]
Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
[BIC81]
...
[BOR80]
Haran Boral, David J. DeWitt: Design Considerations for Data-flow Database Machines. SIGMOD Conference 1980: 94-104 BibTeX
[BOR84]
Haran Boral, David J. DeWitt: A Methodology for Database System Performance Evaluation. SIGMOD Conference 1984: 176-185 BibTeX
[BRO84]
Michael L. Brodie, Matthias Jarke: On Integrating Logic Programming and Databases. Expert Database Workshop 1984: 191-207 BibTeX
[CHA81]
Chin-Liang Chang: On Evaluation of Queries Containing Derived Relations in a Relational Data Base. Advances in Data Base Theory 1979: 235-260 BibTeX
[CHO85]
Hong-Tai Chou, David J. DeWitt: An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB 1985: 127-141 BibTeX
[DEW84]
David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8 BibTeX
[FIN82]
Sheldon J. Finkelstein: Common Subexpression Analysis in Database Applications. SIGMOD Conference 1982: 235-245 BibTeX
[GAL83]
...
[HAN86]
Jiawei Han, Hongjun Lu: Some Performance Results on Recursive Query Processing in Relational Database Systems. ICDE 1986: 533-541 BibTeX
[HON84]
Yang-Chang Hong: A Pipeline and Parallel Architecture for Supporting Database Management Systems. ICDE 1984: 152-159 BibTeX
[JAR84]
Matthias Jarke, James Clifford, Yannis Vassiliou: An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984: 296-306 BibTeX
[KEL82]
Charles Kellogg: Knowledge Management: A Practical Amalgam of Knowledge and Data Base Technology. AAAI 1982: 306-309 BibTeX
[KER84]
Allan Shepherd, Larry Kerschberg: PRISM: A Knowledge Based System for Semantic Integrity Specification and Enforcement in Database Systems. SIGMOD Conference 1984: 307-315 BibTeX
[KIM85]
Won Kim, Daniel Gajski, David J. Kuck: A Parallel Pipelined Relational Query Processor. ACM Trans. Database Syst. 9(2): 214-242(1984) BibTeX
[MIK85]
...
[MIN81]
...
[NAQ84]
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
[RAS85]
...
[REI78a]
Raymond Reiter: Deductive Question-Answering on Relational Data Bases. Logic and Data Bases 1977: 149-177 BibTeX
[REI78b]
Raymond Reiter: On Closed World Data Bases. Logic and Data Bases 1977: 55-76 BibTeX
[ROB65]
John Alan Robinson: A Machine-Oriented Logic Based on the Resolution Principle. J. ACM 12(1): 23-41(1965) BibTeX
[ROT80]
James B. Rothnie Jr., Philip A. Bernstein, Stephen Fox, Nathan Goodman, Michael Hammer, Terry A. Landers, Christopher L. Reeve, David W. Shipman, Eugene Wong: Introduction to a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 1-17(1980) BibTeX
[SIC76]
...
[STO76]
Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX
[SU85]
...
[SU86a]
Stanley Y. W. Su, Krishna P. Mikkilineni, Raymond A. Liuzzi, Yuan-Chieh Chow: A Distributed Query Processing Strategy Using Decomposition, Pipelining and Intermediate Result Sharing Techniques. ICDE 1986: 94-102 BibTeX
[ULL85]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases (Abstract). SIGMOD Conference 1985: 444 BibTeX
[WIE84]
Michele Missikoff, Gio Wiederhold: Towards a Unified Approach for Expert and Database Systems. Expert Database Workshop 1984: 383-399 BibTeX
[WON76]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX

Referenced by

  1. Keh-Chang Guh, Clement T. Yu: Efficient Query Processing for a Subset of Linear Recursive Binary Rules. IEEE Trans. Knowl. Data Eng. 6(5): 842-849(1994)
  2. Keh-Chang Guh, Clement T. Yu: Efficient Management of Materialized Generalized Transitive Closure in Centralized and Parallel Environments. IEEE Trans. Knowl. Data Eng. 4(4): 371-381(1992)
  3. Keh-Chang Guh, Chengyu Sun, Clement T. Yu: Real Time Retrieval and Update of Materialized Transitive Closure. ICDE 1991: 690-697
  4. Weining Zhang, Clement T. Yu, Daniel Troy: Necessary and Sufficient Conditions to Linearize Double Recursive Programs in Logic Databases. ACM Trans. Database Syst. 15(3): 459-482(1990)
  5. Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Distributed Transitive Closure Computations: The Disconnection Set Approach. VLDB 1990: 335-346
  6. Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Complex Transitive Closure Queries on a Fragmented Graph. ICDT 1990: 470-484
  7. Wolfgang Nejdl: Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy. VLDB 1987: 43-50
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:32 2009