Process for providing transitive closure using fourth generation structure query language (SQL)

• US 5,819,257 A
• Filed: 01/31/1997
• Issued: 10/06/1998
• Est. Priority Date: 01/31/1997
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Schultz, Thomas Alan, Monge, Daryl Lee
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Loomis, John C.
• Application Number:
  US08/790,302
• Time in Patent Office: 613 Days
• Field of Search: 707/1, 707/2, 707/3, 707/101, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24566 Recursive queries
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Any existing transitive closure in a database can be found using a method based on standard 4th Generation Structured Query Language (SQL) without non-standard extensions to perform recursion analysis. There are no requirements to stay within a preset number of levels in the database to prevent breakdown as in previous known methods. The method represents each database as a graph and builds path and edge tables which are updated as data, that is verticies and edges, are added or deleted. Since this method uses instructions that are entirely within standard 4GL SQL, it can be used over multiple platforms as long as the platforms are 4GL SQL compliant.

Claims

1. A method, for use in a computer having a processor, a plurality of storage elements and a display device, for determining a transitive closure between two verticies of a tree graph in standard SQL comprising the steps of:

determining all verticies of said tree graph;

determining an edge table from all of the verticies;

deriving a path table from said verticies and said edge table, and

from said path table determining at least one transitive closure path between said two if such transitive closure exists.

2. A method according to claim 1, wherein upon a vertex being added to the tree graph said path table deriving step further comprises:

inserting into said path table a source vertex and a destination vertex of said vertex which is added.

3. A method according to claim 1, wherein upon an edge being added to the tree graph said path table deriving step further comprises:

inserting into said path table a source vertex and a destination vertex.

4. A method according to claim 1, wherein upon an edge being removed from the tree graph said path table deriving step further comprises:

deleting from said edge table an edge between parent vertex V_i and child vertex V_j ; and

deleting from said path table vertex V_i and vertex V_j.

5. A method according to claim 1, wherein upon a vertex being removed from the tree graph said path table deriving step further comprises:

recording deletion of either said parent vertex or said child vertex from said edge table in the edge table by deleting from edge table the edge where parent is V_i or child is V_i ;

recording deletions in the path table the deletion of an edge from vertex V_i to vertex V_i.

6. A method, for use in a computer having a processor, a plurality of storage elements and a display device, for determining a transitive closure between two verticies of a directed acyclic graph in standard SQL comprising the steps of:

determining all verticies of said directed acyclic graph;

determining an edge table from all of the verticies;

deriving a path table from said verticies and said edge table, and

from said path table determining at least one transitive closure path between said two if such transitive closure exists.

7. A method according to claim 6, wherein upon a vertex being added to the directed acyclic graph said path table deriving step further comprises:

inserting into said path table a source vertex and a destination vertex of said vertex which was added and a path count quantity.

8. A method according to claim 6, wherein upon an edge being added to the directed acyclic graph said path table deriving step further comprises:

inserting into said path table a source vertex and a destination vertex of said added edge.

9. A method according to claim 6, wherein upon an edge being removed from the directed acyclic graph said path table deriving step further comprises:

deleting from the edge table an edge between parent vertex V_i and child vertex V_j ;

finding all (V_s, V_t) tuples in the path table where V_s is an ascendant of V_i and V_j is a descendant of V_t and for each (V_s, V_t) tuple found decrementing a current path_-- count value thereof by a path_-- count of (V_s, V_i) times the path_-- count of (V_t); and

deleting any path tuples where path_-- count is 0.

10. A method according to claim 6, wherein upon a vertex being removed from the directed acyclic graph said path table deriving step further comprises:

recording in the edge table the deletion of an edge between parent vertex V_i or child vertex V_i.