EP0306197A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
A method for computing transitive closure
Assignee: AT&T Inc
•
Filing: 1988-08-23
•
Granted: —
•
Expires: 2008-08-23
Abstract
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.
Inventors
- 👤 Rakesh Agrawal
- 👤 Hosagrahar Visvesvaraya Jagadish
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-29 09:34
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2455; G06F16/24564; G06F16/24566; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
286 words
In a system comprising a secondary memory and a controller with a primary memory, a method for developing 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, 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 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.
Claim 2
Dependent Claim
286 words
In a system comprising a secondary memory and a controller with a primary memory, a method for developing 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, 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 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.
Claim 3
Dependent Claim
22 words
The method of claim 1 where at least one of said partitions comprises a chosen set of more than one source node.
Claim 4
Dependent Claim
94 words
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.
Claim 5
Dependent Claim
26 words
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.
Claim 6
Dependent Claim
36 words
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.
Claim 7
Dependent Claim
36 words
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.
Claim 8
Dependent Claim
34 words
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.
Claim 9
Dependent Claim
32 words
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.
Claim 10
Dependent Claim
179 words
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 entry 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 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.
Claim 11
Dependent Claim
171 words
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.
Claim 12
Dependent Claim
55 words
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.
Claim 13
Dependent Claim
80 words
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, 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.
Claim 14
Dependent Claim
44 words
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.
Claim 15
Dependent Claim
38 words
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.
Claim 16
Dependent Claim
289 words
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 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.
Claim 17
Dependent Claim
289 words
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 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.
Claim 18
Dependent Claim
32 words
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.
Claim 19
Dependent Claim
43 words
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.
Claim 20
Dependent Claim
38 words
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.
Claim 21
Independent Claim
204 words
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, designed 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 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.
Claim 22
Independent Claim
204 words
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, designed 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 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.
Claim 23
Dependent Claim
43 words
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.
Claim 24
Independent Claim
345 words
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 the 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 with 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 entires 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.
Claim 25
Independent Claim
345 words
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 the 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 with 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 entires 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.
Claim 26
Independent Claim
50 words
A system for storing a database that represents at least a portion of a transitive closure of another database comprising: means for storing said database; and means for storing an identification of entries in said database that participate in the creation or modification of entries in said transitive-closure complete database.
Claim 27
Independent Claim
50 words
A system for storing a database that represents at least a portion of a transitive closure of another database comprising: means for storing said database; and means for storing an identification of entries in said database that participate in the creation or modification of entries in said transitive-closure complete database.
Claim 28
Independent Claim
157 words
A method for storing a database containing entries with signal values attributed to preassigned fields of said database comprising: storing at least a portion of a transitive-closure complete database (TCC-DB) corresponding to said database, 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; and storing an identification of entries in said database that participate in the development of entries in said stored portion of said TCC-DB by associating with each entry of the stored portion of said TCC-DB a set of identifiers that relate the source node of the TCC-DB entry with the destination nodes of those entries in said database that a) have the same source node as said TCC-DB entry, and b) may be employed in cooperation with other entries in said database to form said TCC-DB entry.
Claim 29
Independent Claim
157 words
A method for storing a database containing entries with signal values attributed to preassigned fields of said database comprising: storing at least a portion of a transitive-closure complete database (TCC-DB) corresponding to said database, 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; and storing an identification of entries in said database that participate in the development of entries in said stored portion of said TCC-DB by associating with each entry of the stored portion of said TCC-DB a set of identifiers that relate the source node of the TCC-DB entry with the destination nodes of those entries in said database that a) have the same source node as said TCC-DB entry, and b) may be employed in cooperation with other entries in said database to form said TCC-DB entry.
Claim 30
Dependent Claim
23 words
The method of claim 23, further comprising a label associated with each identifier is said set of identifiers associated with said TCC-DB entries.
Claim 31
Dependent Claim
93 words
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.
Claim 32
Dependent Claim
93 words
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.
Claim 33
Dependent Claim
45 words
The system of claim 25 where 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.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.