Boots – shoes – and leggings
Patent
1987-08-31
1990-05-29
Shaw, Gareth D.
Boots, shoes, and leggings
364200, 3642821, 3642822, G06F 1540, G06F 1531
Patent
active
049300725
ABSTRACT:
A method and apparatus for creating a transitive closure of a database when the database is stored on a secondary storage in the form of links connecting nodes. The method consists of partitioning the database, transferring one partition at a time from the secondary storage to the main memory, and processing a partition in such a way that accesses to the portions of the database not in main memory are minimized. As much of the unprocessed database as would fit a predetermined fraction of main memory is fetched as one partition, and if, during the processing of this partition, the main memory becomes full, the size of the partition is reduced dynamically by discarding a portion of the database in the current partition, and including this portion in the next partition. The processing of a partition involves, for each node in the partition, the operation of creating a direct connection between every pair of nodes that are indirectly connected through this node.
REFERENCES:
patent: 4267568 (1981-05-01), Dechant et al.
patent: 4422158 (1983-12-01), Galie
patent: 4468732 (1984-08-01), Raver
patent: 4479196 (1984-10-01), Ferrer et al.
patent: 4484297 (1984-11-01), Maier et al.
patent: 4497039 (1985-01-01), Kitakami et al.
patent: 4611298 (1986-09-01), Schuldt
patent: 4627019 (1986-12-01), Ng
patent: 4745559 (1988-05-01), Willis et al.
patent: 4797810 (1989-01-01), McEntee et al.
patent: 4803642 (1988-02-01), Muranaga
patent: 4809158 (1989-02-01), McCauley
patent: 4814971 (1989-03-01), Thatte
patent: 4853842 (1989-08-01), Thatte et al.
Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries, R. Agrawal, Proc. 3rd Intl. Conf. on Data Engineering, Los Angeles, Calif., 2/87.
Traversal Recursion: A Practical Approach to Supporting Recursive Applications, A. Rosenthal, Proc. ACM-SIGMOD 1986 Intl. Conf. on Management of Data, Washington, D.C., 5/86.
Heuristic Search in Data Base Systems, R. Kung et al., Proc. 1st Intl. Workshop Expert Database Systems, Kiawah Island, S.C., Oct. 1984.
Naive Evaluation of Recursively Defined Relations, A. F. Bancillion, Tech. Rept. DB-004-85, MCC, Austin, Tex.
Evaluation of Recursive Queries Using Joint Indices, P. Valduriez et al., Proc. 1st Intl. Conf. Expert Database Systems, Charleston, S.C. 4/86.
On the Computation of the Transitive Closure of Relational Operators, Y. E. Ioannidis, Proc. 12th Intl. Conf. Very Large Data Bases, Kyota, Japan, 8/86.
On the Evaluation of Recursion in Deductive Database Systems by Efficient Differential Fixpoint Iteration, U. Guntzer et al., Proc. IEEE 3rd Intl. Conf. Data Engineering, Los Angeles, Calif. 2/87.
New Strategies for Computing the Transitive Closure of a Database Relation, H. Lu, Proc. 13th Intl. Conf. Very Large Data Bases, Brighton, England 9/87.
A Theorem on Boolean Matrices, S. Warshall, Journal of ACM, vol. 9, No. 1, 1/62.
A Modification of Warshall's Algorithm for the Transitive Closure of Binary Relations, H. S. Warren, Communications of ACM, vol. 18, No. 4, 4/75.
An Algorithm for Transitive Closure with Linear Expected Time, C. P. Schnorr, SIAM Journal of Computing, vol. 7, No. 2, 5/78.
Agrawal Rakesh
Jagadish Hosagrahar V.
AT&T Bell Laboratories
Brendzel Henry T.
Kriess Kevin A.
Shaw Gareth D.
LandOfFree
Method for computing transitive closure does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for computing transitive closure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for computing transitive closure will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-525316