{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,17]],"date-time":"2025-03-17T04:12:44Z","timestamp":1742184764286,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540508946"},{"type":"electronic","value":"9783642745713"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/978-3-642-74571-3_18","type":"book-chapter","created":{"date-parts":[[2011,12,21]],"date-time":"2011-12-21T13:41:40Z","timestamp":1324474900000},"page":"231-245","source":"Crossref","is-referenced-by-count":3,"title":["Making the Partial Transitive Closure an Elementary Database Operation"],"prefix":"10.1007","author":[{"given":"Bin","family":"Jiang","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"R. Agrawal and P. Devanbu. Moving selection into linear least fixpoint queries. In Proceedings of the IEEE International Conference on Data En-gineering, pages 452\u2013461, 1988.","DOI":"10.1109\/ICDE.1988.105491"},{"key":"18_CR2","volume-title":"Data Structures and Algorithms","author":"AV Aho","year":"1985","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman. Data Structures and Algorithms. Addison-Wesley, 1985."},{"key":"18_CR3","unstructured":"R. Agrawal and H. V. Jagadish. Direct algorithms for computing the transitive closure of database relations. In Proceedings of the International Conference on Very Large Databases, pages 255\u2013266, 1987."},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"A. Aho and J. Ullman. Universality of data retireval languages. In Proceedings of the ACM Symposium on Principles of Programming Languages, pages 110\u2013117, 1979.","DOI":"10.1145\/567752.567763"},{"key":"18_CR5","volume-title":"Computer Algorithms: Introduction to Design and Analysis","author":"S Baase","year":"1983","unstructured":"S. Baase. Computer Algorithms: Introduction to Design and Analysis. Addison-Wesley, 1983."},{"key":"18_CR6","first-page":"165","volume-title":"On Knowledge Base Management Systems","author":"F Bancilhon","year":"1985","unstructured":"F. Bancilhon. Naive evaluation of recursively defined relations. In On Knowledge Base Management Systems, pages 165\u2013178, Spring-Verlag, 1985."},{"key":"18_CR7","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"RE Bellman","year":"1958","unstructured":"R. E. Bellman. On a routing problem. Quart Appl. Math., 16:87\u201390, 1958.","journal-title":"Quart Appl. Math."},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"F. Bancilhon and R. Ramakrishnan. An amateur\u2019s introduction to recursive query processing strategies. In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 16\u201352, 1986.","DOI":"10.1145\/16894.16859"},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"C. Beeri and R. Ramakrishnan. On the power of magic. In Proceedings of the ACM Symposium on Principles of Database Systems, pages 269\u2013283, 1987.","DOI":"10.1145\/28659.28689"},{"key":"18_CR10","volume-title":"Graph Algorithms","author":"S Even","year":"1979","unstructured":"S. Even. Graph Algorithms. Computer Science Press, 1979."},{"issue":"1","key":"18_CR11","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1145\/4078.4080","volume":"17","author":"C Faloutsos","year":"1985","unstructured":"C. Faloutsos. Access methods for text. ACM Computing Surveys, 17(1):49\u201374, January 1985.","journal-title":"ACM Computing Surveys"},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"U. G\u00fcntzer, W. Kiessling, and R. Bayer. On the evaluation of recursion in (deductive) database systems by efficient differential fixpoint iteration. In Proceedings of the IEEE International Conference on Data Engineering, 1987.","DOI":"10.1109\/ICDE.1987.7272365"},{"issue":"2","key":"18_CR13","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/356924.356929","volume":"16","author":"H Gallaire","year":"1985","unstructured":"H. Gallaire, J. Minker, and J.-M. Nicolas. Logic and databases: a deductive approach. ACM Computing Surveys, 16(2):153\u2013185, 1985.","journal-title":"ACM Computing Surveys"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"G. Grahne, S. Sippu, and E. Soisalon-Soininen. Efficient evaluation for a subset of recursive queries. In Proceedings of the ACM Symposium on Principles of Database Systems, pages 284\u2013293, 1987.","DOI":"10.1145\/28659.28690"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"J. Han and L. J. Henschen. Handling redundancy in the processing of recursive database queries. In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 73\u201381, 1987.","DOI":"10.1145\/38713.38727"},{"key":"18_CR16","volume-title":"Structural Models: An Introduction to the Theory of Directed Graphs","author":"F Harary","year":"1965","unstructured":"F. Harary, R. Z. Norman, and D. Cartwright. Structural Models: An Introduction to the Theory of Directed Graphs. John Wiley\/Sons, Inc., 1965."},{"key":"18_CR17","doi-asserted-by":"crossref","unstructured":"J. Han, G. Qadah, and C. Chaou. The processing and evaluation of transitive closure queries. In Proceedings of the International Conference on Extending Database Technology, pages 49\u201375, 1988.","DOI":"10.1007\/3-540-19074-0_47"},{"key":"18_CR18","unstructured":"Y. Ioannidis. A time bound on the materialization of some recursively defined views. In Proceedings of the International Conference on Very Large Databases, pages 219\u2013435, 1985."},{"key":"18_CR19","unstructured":"Y. Ioannidis. On the computation of the transitive closure of relational operators. In Proceedings of the International Conference on Very Large Databases, pages 403\u2013411, 1986."},{"key":"18_CR20","unstructured":"Y. Ioannidis and R. Ramakrishnan. Efficient transitive closure algorithms. In Proceedings of the International Conference on Very Large Databases, pages 382\u2013394, 1988."},{"key":"18_CR21","doi-asserted-by":"crossref","unstructured":"H. V. Jagadish, R. Agrawal, and L. Ness. A study of transitive closure as a recursion mechanism. In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 331\u2013344, 1987.","DOI":"10.1145\/38713.38750"},{"key":"18_CR22","unstructured":"B. Jiang. Computing partial transitive closures as an elementary operation for processing linearly recursive queries. 1988. In preperation."},{"issue":"2","key":"18_CR23","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/51708.51709","volume":"17","author":"B Jiang","year":"1988","unstructured":"B. Jiang. Deadlock detection is really cheap. ACM-SIGMOD Record, 17(2):2\u201313, June 1988.","journal-title":"ACM-SIGMOD Record"},{"key":"18_CR24","volume-title":"Graphentheoretische Methoden und ihre Anwendungen","author":"W K\u00f6del","year":"1969","unstructured":"W. Kn\u00f6del. Graphentheoretische Methoden und ihre Anwendungen. Springer-Verlag, 1969."},{"key":"18_CR25","doi-asserted-by":"crossref","unstructured":"S. Lee and J. Han. Semantic query optimization in recursive databases. In Proceedings of the IEEE International Conference on Data Engineering, pages 444\u2013451, 1987.","DOI":"10.1109\/ICDE.1988.105490"},{"key":"18_CR26","unstructured":"H. Lu. New strategies for computing the transitive closure of a database relations. In Proceedings of the International Conference on Very Large Databases, pages 267\u2013274, 1987."},{"key":"18_CR27","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69897-2","volume-title":"Data Structures and Algorithms 2: Graph Algorithms and NP- Completeness","author":"K Mehlhorn","year":"1984","unstructured":"K. Mehlhorn. Data Structures and Algorithms 2: Graph Algorithms and NP- Completeness. Springer-Verlag, 1984."},{"key":"18_CR28","first-page":"285","volume-title":"Proceedings of the International Symposium on the Theory of Switching, 1957","author":"EF Moore","year":"1959","unstructured":"E. F. Moore. The shortest path through a maze. In Proceedings of the International Symposium on the Theory of Switching, pages 285\u2013292, 1957. Also in Annals of the Computation Laboratory of Harvard University, 30, Harvard Uni. Press, Cambridge, MA, 1959."},{"key":"18_CR29","doi-asserted-by":"crossref","unstructured":"J. F. Naughton. Data independant recursion in deductive databases. In Proceedings of the ACM Symposium on Principles of Database Systems, pages 267\u2013279, 1986.","DOI":"10.1145\/6012.15420"},{"key":"18_CR30","doi-asserted-by":"crossref","unstructured":"J. F. Naughton. One-sided recursions. In Proceedings of the ACM Symposium on Principles of Database Systems, pages 340\u2013348, 1987.","DOI":"10.1145\/28659.28695"},{"key":"18_CR31","volume-title":"Graphentheorie mit Algorithmen und Anwendungen","author":"H Noltemeier","year":"1976","unstructured":"H. Noltemeier. Graphentheorie mit Algorithmen und Anwendungen. Walter de Gruyter, 1976."},{"key":"18_CR32","volume-title":"Discrete Mathematical Structures for Computer Science","author":"RE Prather","year":"1976","unstructured":"R. E. Prather. Discrete Mathematical Structures for Computer Science. Houghton Mifflin Company, 1976."},{"key":"18_CR33","unstructured":"G. Qadah. An efficient algorithm for the processing of transitive closure queries. 1988. In preperation."},{"key":"18_CR34","doi-asserted-by":"crossref","unstructured":"A. Rosenthal, S. Heiler, U. Dayal, and F. Manola. Traversal recursion: a practical approach to supporting recursive applications. In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 155\u2013165, 1986.","DOI":"10.1145\/16894.16871"},{"key":"18_CR35","volume-title":"Algorithms","author":"R Sedgewick","year":"1984","unstructured":"R. Sedgewick. Algorithms. Addison-Wesley, 1984."},{"key":"18_CR36","doi-asserted-by":"crossref","unstructured":"S. Sippu and E. Soisalon-Soininen. An optimization strategy for recursive queries in logic databases. In Proceedings of the IEEE International Conference on Data Engineering, pages 470\u2013479, 1988.","DOI":"10.1109\/ICDE.1988.105493"},{"key":"18_CR37","doi-asserted-by":"crossref","unstructured":"D. Sacc\u00e0 and C Zaniolo. Magic counting methods. In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 49\u201359, 1987.","DOI":"10.1145\/38713.38725"},{"issue":"2","key":"18_CR38","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"R. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146\u2013160, June 1972.","journal-title":"SIAM Journal on Computing"},{"key":"18_CR39","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"RE Tarjan","year":"1983","unstructured":"R. E. Tarjan. Data Structures and Network Algorithms. SIAM, 1983."},{"key":"18_CR40","unstructured":"P. Valduriez and H. Boral. Evaluation of recursive queries using join indices. In Proceedings of the International Conference on Expert Database Systems, pages 197\u2013208, April 1986."},{"key":"18_CR41","unstructured":"L. Vieille. Recursive axioms in deductive databases: the query\/subquery approach. In Proceedings of the International Conference on Expert Database Systems, pages 179\u2013193, 1986."},{"issue":"1","key":"18_CR42","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/321105.321107","volume":"9","author":"S Warshall","year":"1962","unstructured":"S. Warshall. A theorem on boolean matrices. Journal of the ACM, 9(1):11\u201312, January 1962.","journal-title":"Journal of the ACM"},{"key":"18_CR43","doi-asserted-by":"crossref","unstructured":"C Youn, L. J. Henschen, and J. Han. Classification of recursive formulas in deductive databases. In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 320\u2013328, 1988.","DOI":"10.1145\/50202.50241"}],"container-title":["Informatik-Fachberichte","Datenbanksysteme in B\u00fcro, Technik und Wissenschaft"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-74571-3_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,16]],"date-time":"2025-03-16T08:44:18Z","timestamp":1742114658000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-74571-3_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540508946","9783642745713"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-74571-3_18","relation":{},"ISSN":["0343-3005"],"issn-type":[{"type":"print","value":"0343-3005"}],"subject":[],"published":{"date-parts":[[1989]]}}}