{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,28]],"date-time":"2024-12-28T07:10:08Z","timestamp":1735369808584,"version":"3.32.0"},"reference-count":68,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1993,10,1]],"date-time":"1993-10-01T00:00:00Z","timestamp":749433600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib Parallel Databases"],"published-print":{"date-parts":[[1993,10]]},"DOI":"10.1007\/bf01264013","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T02:00:54Z","timestamp":1111629654000},"page":"337-382","source":"Crossref","is-referenced-by-count":10,"title":["A survey of parallel execution strategies for transitive closure and logic programs"],"prefix":"10.1007","volume":"1","author":[{"given":"Filippo","family":"Cacace","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Ceri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maurice","family":"Houtsma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"CR1","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1145\/88636.88888","volume":"15","author":"R. Agrawal","year":"1990","unstructured":"R. Agrawal, S. Dar, and H.V. Jagadish, ?Direct transitive closure algorithms: Design and performance evaluation,?ACM Trans. Database Systems, vol. 15, no. 3, pp. 427?458, 1990.","journal-title":"ACM Trans. Database Systems"},{"issue":"4","key":"CR2","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1109\/69.43418","volume":"1","author":"R. Agrawal","year":"1989","unstructured":"R. Agrawal and P. Devanbu, ?Moving selections into linear least fixpoint queries,?IEEE Trans. Knowledge Data Engg., vol. 1, no. 4, pp. 424?432, 1989.","journal-title":"IEEE Trans. Knowledge Data Engg."},{"key":"CR3","unstructured":"R. Agrawal and H.V. Jagadish, ?Direct algorithms for computing the transitive closure of database relations,? inProc. 13th Int. Conf. Very Large Data Bases, Brighton, 1987, pp. 255?266."},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"R. Agrawal and H.V. Jagadish, ?Multiprocessor transitive closure algorithms,? inProc. Int. Symp. Databases in Parallel and Distributed Systems, Austin, TX, 1988.","DOI":"10.1109\/DPDS.1988.675002"},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"A.V. Aho, and J.D. Ullman, ?Universality of data retrieval languages,?Sixth ACM Symp. Principles of Programming Languages, San Antonio, 1979.","DOI":"10.1145\/567752.567763"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"P.M.G. Apers, A. Hevner, and B. Yao, ?Optimization algorithms for distributed queries,?IEEE Trans. Software Engg., vol. 9, no. 1, 1983.","DOI":"10.1109\/TSE.1983.236170"},{"key":"CR7","unstructured":"P.M.G. Apers, M.A.W. Houtsma, and F. Brandse, ?Processing recursive queries in relational algebra,? inData and Knowledge (DS-2), Proc. 2nd IFIP 2.6 Working Conf. Database Semantics, Albufeira, Portugal, 1986, R.A. Meersman and A.C. Sernadas (Eds.), North-Holland, 1988, pp. 17?39."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"P.M.G. Apers, M.L. Kersten, and H. Oerlemans, ?PRISMA database machine: a distributed main-memory approach,? inAdvances in Database Technology, Proc. Int. Conf. Extending Database Technology (EDBT), 1988, pp. 590?593.","DOI":"10.1007\/3-540-19074-0_82"},{"issue":"3","key":"CR9","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0743-1066(87)90004-5","volume":"4","author":"I. Balbin","year":"1987","unstructured":"I. Balbin and K. Ramamohanarao, ?A generalization of the differential approach to recursive query evaluation,?J. Logic Program., vol. 4, no. 3, pp. 259?262, 1987.","journal-title":"J. Logic Program."},{"key":"CR10","unstructured":"F. Bancilhon, ?Naive evaluation of recursively defined relations,? Technical Report DB-004-85, MCC, Austin, TX, 1985."},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"F. Bancilhon, D. Maier, Y. Sagiv, and J.D. Ullman, ?Magic sets and other strange ways to implement logic programs,?Proc. ACM SIGMOD-SIGACT Symp. Principles of Database Systems, Cambridge, MA, 1986.","DOI":"10.1145\/6012.15399"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"F. Bancilhon and R. Ramakrishnan, ?An amateur's introduction to recursive query processing,?Proc. ACM SIGMOD Conf. Washington DC, 1986.","DOI":"10.1145\/16894.16859"},{"key":"CR13","unstructured":"S. Ceri, G. Gottlob, and L. Lavazza, ?Translation and optimization of logic queries: the algebraic approach,? inProc. 12th Int. Conf. Very Large Data Bases, Kyoto, 1986, pp. 395?403."},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"S. Ceri, G. Gottlob, and L. Tanca,Logic programming and Databases, Springer-Verlag, 1990.","DOI":"10.1007\/978-3-642-83952-8"},{"key":"CR15","unstructured":"S. Ceri and G. Pelagatti,Distributed Databases: Principles and Systems, McGraw-Hill, 1984."},{"key":"CR16","unstructured":"S. Ceri and L. Tanca, ?Optimization of systems of algebraic equations for evaluating Datalog queries,? inProc. 13th Int. Conf. Very Large Data Bases, Brighton, 1987, pp. 31?42."},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"J.P. Cheiney and C. De Maindreville, ?A parallel strategy for transitive closure using double hash-based clustering,? inProc. 16th Int. Conf. Very Large Data Base, Brisbane, 1990.","DOI":"10.1007\/3-540-51324-8_43"},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"G. Copeland, W. Alexander, E. Boughter, and T. Keller, ?Data Placement in Bubba,? inProc ACM-SIGMOD Conf., 1988, pp. 99?108.","DOI":"10.1145\/971701.50213"},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"M.P. Consens and A.O. Mendelzon, ?GraphLog: a visual formalism for real life recursion,? inProc. ACM SIGMOD-SIGACT Symp. Principles of Database Systems, Nashville, 1990, pp. 404?416.","DOI":"10.1145\/298514.298591"},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"I.F. Cruz and T.S. Norvell, ?Aggregative closure: an extension of transitive closure,? inProc. 5th Inf. Conf. Data Engineering, Los Angeles, 1989, pp. 384?391.","DOI":"10.1109\/ICDE.1989.47239"},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"S. Dar, R. Agrawal, H.V. Jagadish, ?Optimization of generalized transitive closure queries,? inProc. 7th Int. Conf. Data Engineering, Kobe, 1991, pp. 345?354.","DOI":"10.1109\/ICDE.1991.131482"},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"D.J. De Witt, S. Ghandeharizadeh, and D. Schneider, ?A performance analysis of the Gamma database machine,? inProc. ACM-SIGMOD Conf., 1988, pp. 350?360.","DOI":"10.1145\/971701.50245"},{"key":"CR23","doi-asserted-by":"crossref","unstructured":"A.C. Fong and J.D. Ullman ?Induction variables in very high level languages,? inProc. 3rd ACM Symp. Principles of Programming Languages, Atlanta, pp. 104?112.","DOI":"10.1145\/800168.811544"},{"key":"CR24","doi-asserted-by":"crossref","unstructured":"S. Ganguly, A. Silberschatz, and S. Tsur, ?A framework for the parallel processing of Datalog queries,? inProc. ACM-SIGMOD Conf., Atlantic City, 1990.","DOI":"10.1145\/93597.98724"},{"key":"CR25","doi-asserted-by":"crossref","unstructured":"N. Goodman, P.A. Bernstein, E. Wong, C.L. Reeve, and J.B. Rothnie, ?Query processing in SDD-1?A system for distributed databases,?ACM Trans. Database Sys., vol. 6, no. 4, 1981.","DOI":"10.1145\/319628.319650"},{"issue":"4","key":"CR26","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0169-023X(92)90029-B","volume":"7","author":"M.A.W. Houtsma","year":"1992","unstructured":"M.A.W. Houtsma and P.M.G. Apers, ?Algebraic optimization of recursive queries,?Data Knowledge Engg. vol. 7, no. 4, pp. 299?325, 1992.","journal-title":"Data Knowledge Engg."},{"key":"CR27","unstructured":"M.A.W. Houtsma, P.M.G. Apers, and S. Ceri, ?Distributed transitive closure computation: the disconnection set approach,? inProc. 16th Int. Conf. Very Large Data Bases, Brisbane, 1990."},{"key":"CR28","doi-asserted-by":"crossref","unstructured":"M.A.W. Houtsma, P.M.G. Apers, and S. Ceri, ?Complex transitive closure queries on a fragmented graph,? inProc. 3rd Int. Conf. Database Theory, Paris, 1990, Lecture Notes in Comput. Sci., vol. 470, Springer-Verlag, New York.","DOI":"10.1007\/3-540-53507-1_96"},{"key":"CR29","doi-asserted-by":"crossref","unstructured":"M.A.W. Houtsma, P.M.G. Apers, and G.L.V. Schipper, ?Data fragmentation for parallel transitive closure strategies,? inProc. 9th Int. Conf. Data Engineering, Vienna, 1993, pp. 447?456.","DOI":"10.1109\/ICDE.1993.344036"},{"key":"CR30","unstructured":"M.A.W. Houtsma, F. Cacace, and S. Ceri, ?Parallel hierarchical evaluation of transitive closure queries,? inProc. 1st Int. Conf. Parallel and Distributed Information Systems, Miami Beach, 1991, IEEE Computer Science Press."},{"key":"CR31","unstructured":"M.A.W. Houtsma, A.N. Wilschut, and J. Flokstra,, ?Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA\/DB,? inProc. 19th Int. Conf. Very Large Data Bases, Dublin, 1993."},{"key":"CR32","unstructured":"G. Hulin, ?Parallel processing of recursive queries in distributed architectures,? inProc. 15th Int. Conf. Very Large Data Bases, Amsterdam, 1989, pp. 87?96."},{"key":"CR33","doi-asserted-by":"crossref","unstructured":"H.V. Jagadish, R. Agrawal, and L. Ness, ?A study of transitive closure as a recursion mechanism? inProc. ACM-SIGMOD Conf., 1987, pp. 331?344.","DOI":"10.1145\/38714.38750"},{"key":"CR34","doi-asserted-by":"crossref","unstructured":"B. Jiang, ?A suitable algorithm for computing partial transitive closures in databases, inProc. 6th Int. Conf. Data Engineering, Los Angeles, 1990, pp. 264?271.","DOI":"10.1109\/ICDE.1990.113477"},{"key":"CR35","unstructured":"Y.E. Ioannidis, ?On the computation of the transitive closure of relational operators,? inProc. 12th Int. Conf. Very Large Data Bases, Kyoto, 1986, pp. 403?411."},{"key":"CR36","unstructured":"Y.E. Ioannidis and R. Ramakrishnan, ?Efficient Transitive Closure Algorithms,? inProc. 14th Int. Conf. Very Large Data Bases, Los Angeles, 1988."},{"key":"CR37","doi-asserted-by":"crossref","unstructured":"Y.E. Ioannidis and E. Wong, ?Towards an algebraic theory of recursion?J. ACM, vol. 18, no. 2, 1991.","DOI":"10.1145\/103516.103521"},{"key":"CR38","unstructured":"P. Kanellakis ?Parallel complexity of logic programs.? inFoundations of Logic Programming and Deductive Databases, Morgan-Kauffman, 1988."},{"key":"CR39","doi-asserted-by":"crossref","unstructured":"M. Kifer and E.L. Lozinskii, ?Filtering data flow in deductive databases,? inProc. 1st Int. Conf. Database Theory, Rome, 1986.","DOI":"10.1007\/3-540-17187-8_37"},{"key":"CR40","volume-title":"Evaluation and simulation of parallel algorithms for the transitive closure operation","author":"G. Kleinhuis","year":"1989","unstructured":"G. Kleinhuis and K.R. Oskam, ?Evaluation and simulation of parallel algorithms for the transitive closure operation,? M.Sc. thesis, University of Twente, The Netherlands, 1989."},{"key":"CR41","doi-asserted-by":"crossref","unstructured":"I.S. Mumick, S.J. Finkelstein, and H. Pirahesh, ?Magic conditions,? inProc. ACM SIGMOD-SIGACT Symp. Principles of Database Systems, 1990.","DOI":"10.1145\/298514.298584"},{"key":"CR42","doi-asserted-by":"crossref","unstructured":"I.S. Mumick, S.J. Finkelstein, and H. Pirahesh, ?Magic is relevant,? inProc. ACM SIGMOD Conf., Atlantic City, 1990.","DOI":"10.1145\/93597.98734"},{"key":"CR43","unstructured":"I.S. Mumick, H. Pirahesh, and R. Ramakrishnan, ?The magic of duplicates and aggregates,? inProc. 16th Int. Conf. Very Large Data Bases, Brisbane, 1990."},{"key":"CR44","unstructured":"S. Naqvi and S. Tsur,A Logical Language for Data and Knowledge Bases, Computer Science Press, 1989."},{"key":"CR45","doi-asserted-by":"crossref","unstructured":"R. Paige and J.T. Schwartz, ?Reduction in strength of high level operations,? inProc. 4th ACM Symp. Principles of Programming Languages, Los Angeles, 1977, pp. 58?71.","DOI":"10.1145\/512950.512957"},{"key":"CR46","doi-asserted-by":"crossref","unstructured":"M.J. Quinn and N. Deo, ?Parallel graph algorithms,?ACM Comput. Surv., vol. 16, no. 3, 1984.","DOI":"10.1145\/2514.2515"},{"key":"CR47","unstructured":"R. Ramakrishnan ?Magic templates, a spellbinding approach to logical evaluation,? inProc. Logic Programming Conf. 1988."},{"key":"CR48","doi-asserted-by":"crossref","unstructured":"R. Ramakrishnan, C. Beeri, and R. Krishnamurty, ?Optimizing existential Datalog queries,? inProc. ACM SIGMOD-SIGACT Symp. Principles of Database Systems, Austin, TX, 1988.","DOI":"10.1145\/308386.308420"},{"key":"CR49","unstructured":"L. Raschid and S.Y.W. Su, ?A parallel strategy for evaluating recursive queries,?Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, 1986."},{"key":"CR50","doi-asserted-by":"crossref","unstructured":"J. Robinson and S. Lavington, ?A transitive closure and magic function machine,? inProc. 2nd Int. Symp. Databases in Parallel and Distributed Systems, Dublin, 1990, pp. 44?54.","DOI":"10.1109\/DPDS.1990.113697"},{"key":"CR51","doi-asserted-by":"crossref","unstructured":"J. Rohmer, R. Lescoeur, and J.M. Kerisit, ?The Alexander method: a technique for the processing of recursive axioms in deductive database,? inNew Generation Comput., vol. 4, Springer-Verlag, 1986.","DOI":"10.1007\/BF03037407"},{"key":"CR52","doi-asserted-by":"crossref","unstructured":"Y. Sagiv ?Optimizing Datalog programs? inProc. ACM SIGMOD-SIGACT Symp. Principles of Database Systems, San Diego, 1987.","DOI":"10.1145\/28659.28696"},{"key":"CR53","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BF02242140","volume":"30","author":"L. Schmitz","year":"1983","unstructured":"L. Schmitz ?An improved transitive closure algorithm,?Computing, vol. 30, 1983, pp. 359?371.","journal-title":"Computing"},{"key":"CR54","doi-asserted-by":"crossref","unstructured":"D.A. Schneider and D.J. De Witt, ?A performance analysis of four parallel join algorithms in a shared-nothing multiprocessor environment,? inProc. ACM SIGMOD Conf. Portland, 1989, pp. 110?121.","DOI":"10.1145\/66926.66937"},{"key":"CR55","doi-asserted-by":"crossref","unstructured":"J. Shao, D.A. Bell, and M.E.C. Hull, ?An experimental performance study of a pipelining recursive query processing strategy,? inProc. 2nd Int. Symp. on Databases in Parallel and Distributed Systems, Dublin, 1990, pp. 30?43.","DOI":"10.1109\/DPDS.1990.113696"},{"key":"CR56","unstructured":"The Tandem Database Group, ?NonStop SQL: a distributed, high-performance, highly-availability implementation of SQL,? inHigh Performance Transaction Systems, Lecture Notes in Computer Science, Springer-Verlag, 1987."},{"key":"CR57","unstructured":"Teradata Corporation, ?Teradata DBC\/1012 data base computer concepts and Facilities,? release 3.1 edition 1988, Teradata Document C02-0001-05."},{"key":"CR58","unstructured":"J.D. UllmanPrinciples of Data and Knowledge-Based Systems, Computer Science Press, 1989."},{"key":"CR59","unstructured":"J.D. Ullman and A. Van Gelder, ?Parallel complexity of logic programs,? Technical report STAN-CS-85-1089, Stanford University."},{"key":"CR60","unstructured":"P. Valduriez and H. Boral, ?Evaluation of recursive queries using join indices,? inProc. 1st Int. Conf. Expert Database Systems, Charleston, 1986; andExpert Database Systems, L. Kerschberg (Ed.), Benjamin-Cummings, 1987."},{"key":"CR61","doi-asserted-by":"crossref","unstructured":"P. Valduriez and S. Khoshafian, ?Parallel evaluation of the transitive closure of a database relation,?Int. J. Parallel Program., vol. 17, no. 1, 1988.","DOI":"10.1007\/BF01379321"},{"key":"CR62","unstructured":"P. Valduriez and S. Khoshafian, ?Transitive closure of transitively closed relations,? inProc. 2nd Int. Conf. Expert Database Systems, Vienna, VA., 1988; andExpert Database Systems, L. Kerschberg (Ed.), Benjamin-Cummings, 1988, pp. 377?400."},{"key":"CR63","doi-asserted-by":"crossref","unstructured":"A. Van Gelder, ?A message passing framework for logical query evaluation,? inProc. ACM SIGMOD Conf., pp. 155?165.","DOI":"10.1145\/16856.16870"},{"issue":"4","key":"CR64","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1145\/360715.360746","volume":"18","author":"H.S. Warren","year":"1975","unstructured":"H.S. Warren, ?A modification of Warshall's algorithm for the transitive closure of binary relations,?Comm. ACM, vol. 18, no. 4, pp. 218?220, 1975.","journal-title":"Comm. ACM"},{"issue":"1","key":"CR65","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/321105.321107","volume":"9","author":"S. Warshall","year":"1962","unstructured":"S. Warshall, ?A theorem on Boolean matrices,?J. ACM, vol. 9, no. 1, pp. 11?12, 1962.","journal-title":"J. ACM"},{"key":"CR66","unstructured":"O. Wolfson and A. Ozeri, ?A new paradigm for parallel and distributed rule-processing,? inProc. ACM SIGMOD Conf., pp. 113?142."},{"key":"CR67","doi-asserted-by":"crossref","unstructured":"O. Wolfson ?Sharing the load of logic program evaluation,?Int. Symp. Databases in Parallel and Distributed Systems, Austin, TX, 1988, pp. 46?55.","DOI":"10.1109\/DPDS.1988.675001"},{"key":"CR68","unstructured":"C. Zaniolo and D. Sacc\u00e0, ?Rule rewriting methods for efficient implementation of Horn logic,? MCC technical report DB-084-87, Austin, TX, 1987."}],"container-title":["Distributed and Parallel Databases"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01264013.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01264013\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01264013","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,28]],"date-time":"2024-12-28T06:49:46Z","timestamp":1735368586000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01264013"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,10]]},"references-count":68,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1993,10]]}},"alternative-id":["BF01264013"],"URL":"https:\/\/doi.org\/10.1007\/bf01264013","relation":{},"ISSN":["0926-8782","1573-7578"],"issn-type":[{"type":"print","value":"0926-8782"},{"type":"electronic","value":"1573-7578"}],"subject":[],"published":{"date-parts":[[1993,10]]}}}