A framework for the parallel processing of Datalog queries

ABSTRACT

This paper presents several complementary methods for the parallel, bottom-up evaluation of Datalog queries. We introduce the notion of a discriminating predicate, based on hash functions, that partitions the computation between the processors in order to achieve parallelism. A parallelization scheme with the property of non-redundant computation (no duplication of computation by processors) is then studied in detail. The mapping of Datalog programs onto a network of processors, such that the results is a non-redundant computation, is also studied. The methods reported in this paper clearly demonstrate the trade-offs between redundancy and interprocessor-communication for this class of problems.

REFERENCES

• 1: F. Afrati , C. Papadimitriou, The parallel complexity of simple chain queries, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.210-213, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28682]
• 2: Krzysztof R. Apt, Introduction to Logic Programming, University of Texas at Austin, Austin, TX, 1988
• 3: Bancflhon F "Naxve Evaluation of Recurslvely Defined Relations', MCC Techmcal Report Number DB-004-85
• 4: Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
• 5: Mani Chandy , Jayadev Misra, An example of stepwise refinement of distributed programs: quiescence detection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.3, p.326-343, July 1986 [doi>10.1145/5956.5958]
• 6: S. Cohen , O. Wolfson, Why a single parallelization strategy is not enough in knowledge bases, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.200-216, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73742]
• 7: Dijkstra E W and C S Scholten gTermmatlon Detection for Diffusing Computatmns", Informatwn Processing Letters, August 1980
• 8: Guozhu Dong, On distributed processibility of datalog queries by decomposing databases, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.26-35, June 1989, Portland, Oregon, United States
• 9: Ganguly S, Salberschatz A and S Tsur ~ Denymg Networks for the Parallel Evaluatmn of Datalog Queries", Techmcal Report, Unzvers:ty of Texas at Austin, m preparatmn
• 10: Houtsma M A W et al " A Logic Query Language and its Algebram Optlm~zatmn for a Multlprocessor Database Machine", Technical Report INF-88-52, Un~vers2ty of Twenete, December 1988
• 11: Kanellakls P ~Parallel Complexity of Logic Programs", In Foundatzons of Logic Proqrammzng and Deductive Databases, Morgan-Kauffmann 1988
• 12: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 13: Christos H. Papadimitriou , Jeffrey D. Ullman, A communication-time tradeoff, SIAM Journal on Computing, v.16 n.4, p.639-646, Aug. 1987 [doi>10.1137/0216044]
• 14: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 15: Ullman J and Van Gelder A "Parallel Complexlty of Logxc Programs", TR STAN-CS-85-1089, Stanford Unzvers~ty
• 16: Patrick Valduriez , Setrag Khoshafian, Parallel evaluation of the transitive closure of a database relation, International Journal of Parallel Programming, v.17 n.1, p.19-42, Feb. 1988 [doi>10.1007/BF01379321]
• 17: M. H. Van Emden , R. A. Kowalski, The Semantics of Predicate Logic as a Programming Language, Journal of the ACM (JACM), v.23 n.4, p.733-742, Oct. 1976 [doi>10.1145/321978.321991]
• 18: O. Wolfson, Sharing the load of logic-program evaluation, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.46-55, December 05-07, 1988, Austin, Texas, United States
• 19: Ouri Wolfson , Avi Silberschatz, Distributed processing of logic programs, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.329-336, June 01-03, 1988, Chicago, Illinois, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: Datalog
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Theory