A new paradigm for parallel and distributed rule-processing

ABSTRACT

This paper is concerned with the parallel evaluation of datalog rule programs, mainly by processors that are interconnected by a communication network. We introduce a paradigm, called data-reduction, for the parallel evaluation of a general datalog program. Several parallelization strategies discussed previously in [CW, GST, W, WS] are special cases of this paradigm. The paradigm parallelizes the evaluation by partitioning among the processors the instantiations of the rules. After presenting the paradigm, we discuss the following issues, that we see fundamental for parallelization strategies derived from the paradigm properties of the strategies that enable a reduction in the communication overhead, decomposability, load balancing, and application to programs with negation. We prove that decomposability, a concept introduced previously in [WS, CW], is undecidable.

REFERENCES

• ABW: K R Apt, H Blatr, A Walker "Towards a Theory of Declarative Knowledge," unpubhshed memorandum, IBM Yorktown Hexghts, NY
• AJ: R. Agrawal , H. V. Jagadish, Multiprocessor transitive closure algorithms, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.56-66, December 05-07, 1988, Austin, Texas, United States
• AP: 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]
• Ban: F Bancllhon "Naive Evaluation of Recursxvely Defined Relatxons", m On Knowledge Base Management Systems - Integrated Database and AI Systems, Bro&e and Mylopoulos, Eds, Sprmger-Verlag
• Bay: R Bayer, "Query Evaluataon and Recursion m Deductave Database Systems", unpubhshed manuscript, 1985
• BBDW: Dina Bitton , Haran Boral , David J. DeWitt , W. Kevin Wilkinson, Parallel algorithms for the execution of relational database operations, ACM Transactions on Database Systems (TODS), v.8 n.3, p.324-353, Sept. 1983 [doi>10.1145/319989.319991]
• BR: F. Bancilhon , R. Ramakrishnan, Performance evaluation of data intensive logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• CK: S Cosmadakis , P Kanellakis, Parallel evaluation of recursive rule queries, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.280-293, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15421]
• CM: K M Chandy and J Mlsra "On Proofs of Distributed Algor~thrns with Application to the problem of Terminauon Detection", Manuscript, Dept of CS, Umverslty of Texas
• CW: 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]
• D: 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
• DL: Doug DeGroot , Gary Lindstrom, Logic programming: functions, relations, and equations, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• F: Nissim Francez, Distributed Termination, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.1, p.42-55, Jan. 1980 [doi>10.1145/357084.357087]
• GST: Sumit Ganguly , Avi Silberschatz , Shalom Tsur, A Framework for the Parallel Processing of Datalog Queries, University of Texas at Austin, Austin, TX, 1989
• GMSV: H Galfman, H Malrson, Y Sagw, M Y Vardl, " Undec~dable Opttmlzatlon Problems for Database Logic. Programs," IBM Technical Report RI 5583 (56702) 4/3/87
• HAC: M W Houtsma, P M GApers, and S Cen, "Parallel Computat~ort of Transxtwe Closure Quenes on Fragmented Databases", Umversay of Twente, TR INF-88-56, Dec 1988
• K: Paris C. Kanellakis, Logic Programming and Parallel Complexity, Proceedings of the International Conference on Database Theory, p.1-30, September 08-10, 1986
• MW: D Maler and D S Warren "Compulang with Logic Introduction to Logic Programming", Benjamin- Cummings Pubhshmg Co, 1987
• M1: F Mattern, "Algonthms for Distributed Termmauon Detection", Dzstmbuted Computing, pp 161-175, 1987
• M2: Friedemann Mattern, Global quiescence detection based on credit distribution and recovery, Information Processing Letters, v.30 n.4, p.195-200, February 1989 [doi>10.1016/0020-0190(89)90212-3]
• P: Alexander J. Pasik, A methodology for programming production systems and its implications on parallelism, 1989
• R: R Ramaknshnan, "Parallelism m Logic Programs", Umv of Wisconsin, Computer Sci Dept, TR #892, Nov 89
• RSL: L. Raschid , T. Sellis , C. C. Lin, Exploiting concurrency in a DBMS implementation for production systems, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.34-45, December 05-07, 1988, Austin, Texas, United States
• S: O. Shmueli, Decidability and expressiveness aspects of logic queries, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.237-249, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28685]
• Sh: E. Shapiro, Concurrent prolog: collected papers, MIT Press, Cambridge, MA, 1987
• SDSWY: S Sengupta, A Dupuy, J" Schwartz, O Wolfson, Y Yemllu, 'q"he Net-mate Model for Network Management", m IEEE Network Operations and Management Sympostum, Feb 1990
• SMM: S J Stolfo , D M Miranker , R C Mills, A simple preprocessing scheme to extract and balance implicit parallelism in the concurrent match of production rules, Proc. of the IFIP TC 10 working conference on Fifth generation computer architectures, p.55-65, October 1986, Manchester, United Kingdom
• U: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• UV: J D Ullman and A Van Gelder, "Parallel Complexity of Logic Programs", TR STAN-CS-85-1089, Stanford Umverslty
• VK: 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]
• WS: 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
• W: 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

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: Datalog

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.4 Systems
          Subjects: Concurrency

General Terms:
Algorithms, Design, Languages