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

• Current Assignee: NCR Corporation (NCR Voyix Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Agrawal, Rakesh, Jagadish, Hosagrahar V.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Kriess, Kevin A.
• Application Number:
  US07/091,236
• Time in Patent Office: 1,002 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/300
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24566 Recursive queries
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

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.

Claims

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.

2. The method of claim 1 where at least one of said partitions comprises a chosen set of more than one source node.

3. The method of claim 1 where said step of selecting is applied only to select head entries with a source node i and a destination node j that satisfy the conditions:

(a) that all entries with a source node i and a destination node k, where k is less than j in said ordering, have been previously selected as a head entry, and (b) that all entries with a source node j and a destination node k, where k is less than j in said ordering, have been previously selected as a head entry.

4. The method of claim 1 wherein said step of developing entries is followed by a step of storing developed entries in said secondary memory in order.

5. The method of claim 1 wherein the size of said chosen set of source nodes in each partition is selected to occupy not more than a preset portion of the memory size of said primary memory.

6. The method of claim 1, further including a step responsive to said step of developing an entry, for changing the size of said chosen set of source nodes in accordance with the number of entries created.

7. The method of claim 1 further comprising a step of updating labels when said step of developing an entry results in two paths in said database between a source node and a destination node.

8. The method of claim 1 wherein said step of developing an entry comprises:

a step of processing nodes within said partition followed by a step of processing nodes not in said partition.

9. The method of claim 8 wherein said step of processing nodes within said partition comprises:

a step A of selecting a head entry in said partition with a source node i and a destination node j such that the product-sum i+jK is the lowest achieved product-sum from among all entries in said partition not previously selected, where K is a preselected constant;

a step B of selecting a tail in said partition having a source node equal to the destination node of the head entry selected by said step A;

a step C of constructing a new entry having a source node equal to the source node of the head entry and a destination node equal to the destination node of the tail entry;

a step D of repeating steps B and C when another tail entry is found in said partition having a source node equal to the destination node of the head entry selected by said step A; and

a step E of repeating steps A through D when another head entry is found in said partition.

10. The method of claim 8 wherein said step of processing nodes not in said partition comprises:

a step A of selecting a source node not in said partition;

a step B of selecting a head entry having the selected source node and the earliest destination node in said ordering, not previously considered, that is also present as a source node in said partition;

a step C of constructing a new entry having a source node equal to the source node of the head entry and a destination node equal to the destination node of the tail entry;

a step D of repeating step C when another tail entry is found in said partition having a source node equal to the destination node of the head entry selected by said step B; and

a step E of repeating steps B through D when another head entry is found in said step B;

a step F of repeating steps A through E until all source nodes not in said partition have been utilized.

11. The method of claim 1, further comprising a step of maintaining a successor list for each node, specifying all entries for which said node is a source node, said successor list being employed in carrying out said step of selecting one entry in said partition and one entry in either said partition or said database.

12. The method of claim 1, further comprising:

a step of maintaining a successor list for each node, specifying all entries for which said node is source node, and

a step of maintaining a predecessor list for each node, specifying all entries for which said node is a destination node,

said successor list and predecessor list being employed in carrying out said step of selecting one entry in said partition and one entry in either said partition or said database.

13. The method of claim 1 wherein said step of developing an entry comprises modifying a label of an existing entry with a source node being the source node of said head entry and a destination node being the destination node of said tail entry.

14. The method of claim 1 further comprising a step of updating a label of an entry having one source node and another destination node when another entry having the same source node and the same destination node exists.

15. In a system comprising a secondary storage and a controller with a primary storage, a method for developing at least a portion of the transitive closure of a database stored in said secondary storage, said database containing entries with signal values attributed to preassigned fields of said database, and said transitive closure being developed with respect to a selected field or a set of fields of said database, designated as a source node, and a selected field or a set of 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 partitions of said database, where each partition contains all entries of said database that share a chosen set of source nodes;

a first pass of steps for developing entries for said database by considering all of said partitions, one at a time; and

in considering each partition, first developing entries for each destination node in said partition which associate the source nodes of entries in said partition having said destination node to destination nodes of entries in previously considered partitions having a source node that is the same node as said destination node, and next developing entries for each destination node in said partition which associate the source nodes of entries in said partition having said destination node to destination nodes of entries in said partition having a source node that is the same node as said destination node;

a second pass of steps for developing entries of said database by considering all of said partitions, one at a time; and

in considering each partition, creating new entries for each destination node in said partition not considered in said first pass of steps.

16. The method of claim 15 further comprising a step of updating labels when said step of developing results in two paths in said database between a source node and a destination node.

17. The method of claim 15 wherein said step of developing entries comprises modifying a label of an existing entry with a source node being the source node of said head entry and a destination node being the destination node of said tail entry.

18. The method of claim 15 further comprising a step of updating a label of an entry having one source node and another destination node when another entry having the same source node and the same destination node exists.

19. A method for developing a compressed store of a database containing entries with signal values attributed to preassigned fields of the database, said database being at least in part transitive-closure complete with respect to a selected field or a set of fields, designated as a source node, and a field or a set of fields designated, as a destination node, comprising:

a step of creating a set of chains, each chain comprising an ordered set of said database entries where the destination node of every entry in said chain, other than the last entry, is the same as the source node of to the next entry in said chain, with said set of chains being selected so that each node, whether a destination node or a source node, appears at least once in said set of chains as a source node or a destination node of some entry in some chain; and

for each source node in said database, from the set of entries in said database sharing said source node, a step of deleting entries in said set for which the destination node appears later in some chain than the destination node of some other entry in said set, developing thereby said compressed store.

20. The method of claim 19 further including a step, interposed between said step of creating and said step of deleting, for assigning an identifier for each node, to identify the chain of said node and the position of said node within the chain.

21. A system for developing an augmented database from an original database residing in storage, where

said original database contains a plurality of entries and each entry contains a plurality of fields, with 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 augmented database is realized through a sequence of transitory databases, the first transitory database being the original database and each subsequent transitory database being realized by a modification of the previous transitory database and where

said augmented database is at least a part of a transitive closure of said original database, said transitive closure being 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, said system including a controller having an associated memory, with said controller characterized by:

means for sorting said transitory database within said storage;

means for forming partitions in said transitory database, where each partition contains entries of the database being partitioned that share a common source node;

means for retrieving a partition of said transitory database from said storage and placing it in said memory;

means for developing entries for said augmented database in response to consideration of pairs of entries of said augmented database, with one member of said pair being an entry in said memory and the other member of said pair being an entry of said transitory database in said memory or in said storage, the developed entries being the modifications to said transitory database; and

means for placing in said storage entries developed by said means for developing entries to form the next transitory database;

where said means for retrieving retrieves each partition at most two times, and said means for developing develops said entries when the destination node of one member of a considered pair is also the source node of the other member of said pair.

22. An information-providing system comprising:

storage means for maintaining a database of information;

terminals for requesting information contained in said database;

an enhanced database manager responsive to said terminals and to said storage means, for developing at least a portion of a transitive closure of said database, and for querying said database to retrieve said information requested by said terminals;

means for modifying the information stored in said database; and

means for initiating a development of said portion of a transitive closure of said database when the information stored in said database is modified

wherein said enhanced database manager includes a controller and memory, and develops said portion of a transitive closure of said database by partitioning said database and loading each partition from said database and into said memory at most two times.