×

Method for computing transitive closure

  • US 4,930,072 A
  • Filed: 08/31/1987
  • Issued: 05/29/1990
  • Est. Priority Date: 08/31/1987
  • Status: Expired due to Term
First Claim
Patent Images

1. In a system comprising a secondary memory and a controller with a primary memory, a method carried out in said controller for developing and storing in said second memory at least a portion of the transitive closure of a database stored in said secondary memory, where said database contains a plurality of entries and each entry contains a plurality of fields, whith each of said fields being assigned to a preselected attribute of said database, and the signal value in each of said fields specifies the value associated with the corresponding attribute for that entry, and where said transitive closure is developed with respect to a selected field or fields of said database designated as a source node and a selected field or fields of said database designated as a destination node comprising:

  • a step of developing an ordering of said nodes in said database;

    a step of developing a partition of said database and retrieving said partition from said secondary memory and placing it in said primary memory, where said partition contains all entries of said database that share a chosen set of source nodes;

    a step of an entry by selecting one entry in said partition and one entry in either said partition or said database, where one entry is a head entry and one entry is a tail entry, and developing an entry for said transitive closure of said database with a source node being the source node of said head entry and a destination node being the destination node of said tail entry, when the destination node of said head entry is the same as the source node of said tail entry; and

    a step of returning to said step of developing and retrieving a partition until the entire database has been partitioned.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×