A method for computing transitive closure
作者： Hosagrahar Visvesvaraya Jagadish , Rakesh Agrawal
DOI:
关键词:
摘要: A method and apparatus for creating a transitive closure of database when the is stored on secondary storage in form links connecting nodes. The consists partitioning database, transferring one partition at time from to main memory, processing such way that accesses portions not memory are minimized. As much unprocessed as would fit predetermined fraction fetched partition, if, during this becomes full, size reduced dynamically by discarding portion current including next partition. involves, each node operation direct connection between every pair nodes indirectly connected through node.
google.de 参考文章(23)
Donald W. Oxley, Satish M. Thatte, Computer memory system having persistent objects ,(1988)
Michael A. Heffron, James J. Maier, John V. Ferrante, Jeffrey P. Woodard, Variable data base generator apparatus ,(1981)
Louis M. Galie, Method and means for interrogating a layered data base ,(1980)
Hongjun Lu, New Strategies for Computing the Transitive Closure of a Database Relation very large data bases. pp. 267- 274 ,(1987)
Yannis E. Ioannidis, On the Computation of the Transitive Closure of Relational Operators very large data bases. pp. 403- 411 ,(1986)
Masayoshi Tezuka, Susumu Adachi, Hiroshi Ishikawa, Hazime Kitakami, Akifumi Makinouchi, Join operation processing system in relational model ,(1982)
Donald W. Oxley, Satish M. Thatte, Timothy J. McEntee, Robert W. Bloemer, Incremental, multi-area, generational, copying garbage collector for use in a virtual address space ,(1986)
Robert S. Genshaft, Richard A. Willis, Alan Markham, Method and system for dynamically controlling the content of a local receiver data base from a transmitted data base in an information retrieval communication network ,(1985)
C. P. Schnorr, An Algorithm for Transitive Closure with Linear Expected Time SIAM Journal on Computing. ,vol. 7, pp. 127- 133 ,(1978) , 10.1137/0207011
Henry S. Warren, A modification of Warshall's algorithm for the transitive closure of binary relations Communications of The ACM. ,vol. 18, pp. 218- 220 ,(1975) , 10.1145/360715.360746