Process for providing transitive closure using fourth generation structure query language (SQL)5819257Abstract 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 What is claimed is: Description TECHNICAL FIELD
TABLE 1
______________________________________
edge
parent
child
______________________________________
V.sub.1
V.sub.2
V.sub.1
V.sub.3
V.sub.3
V.sub.4
V.sub.3
V.sub.5
V.sub.4
V.sub.6
______________________________________
According to this database approach, the following is a typical 3GL SQL function to compute the descendants of a vertex, V.sub.i, from Table 1, the edge table. ##EQU2## This function according to this database approach is elegant and concise, but solves only one specific query involving all descendants. It does not provide the ability to ask other questions. For example, if the vertices represented tasks in a project plan and contained dates representing when each task was expected to be complete, a manager might want to pose the question "tell me all tasks that are late". Since the above function is written in 3GL, any modifications will require a recompilation of the function. An equivalent database approach using standard 4GL SQL cannot be implemented. The reason for this is because standard 4GL SQL does not include recursion operations. Some non-standard extension is then sometimes used to provided the recursion. One such a non-standard approach is shown in U.S. Pat. No. 5,201,046 issued Apr. 6, 1993 to R. Goldberg et al. mentioned above. Another example of such non-standard SQL extensions is known from the commercial relational database system of Oracle Corporation which has a "connected by" recursive operator. A non-recursive 4GL SQL solution can be implemented using an edge table, provided the depth of the directed graph is known in advance. The following non-recursive 4GL SQL statement computes the set of descendants of a vertex, V.sub.i, from the edge table shown in Table 1. select child from edge where parent=V.sub.i union select level2.child from edge level1, edge level2 where level1.parent=V.sub.i and level2.parent=level1.child union select level3.child from edge level1, edge level2, edge level3 where level1.parent=V.sub.i and level2.parent=level1.child and level3.parent=level2.child Note the above presented algorithm has hard-coded knowledge about the fact that Tree T shown in FIG. 1 does not descend beyond 3 levels. An increase or decrease in the number of levels in T potentially breaks the algorithm. It is an object of the present invention to provide a transitive closure, if such exists, using a non-procedural, declarative method with 4GL SQL. It is another object of the invention to provide a method for achieving a transitive closure, if one exists, without prior knowledge of the number of required levels. It is another object of the invention to provide a method for achieving a transitive closure, if one exists, without prior knowledge of the table and key names. SUMMARY OF THE INVENTION Briefly stated, in accordance with one aspect of the invention, the foregoing objects are achieved by providing a method for finding a transitive closure existing in a database by deriving and storing the transitive closure at the time that the number of edges of the graph of the database changes. Each newly derived transitive closure is stored for use in future graph queries. In accordance with one aspect of the invention, the foregoing objects are achieved by providing a method for use with a computer having a processor, a plurality of storage elements and a display unit, for determining a transitive closure between two verticies of a tree graph in standard SQL which includes the steps of determining all verticies of the tree graph, determining an edge table from all of the verticies, deriving a path table from the verticies and the edge table, and from the path table determining at least one transitive closure path between the two if such transitive closure exists. In accordance with another aspect of the invention, the foregoing objects are achieved by providing a method for use with a computer having a processor, a plurality of storage elements and a display unit, for determining a transitive closure between two verticies of a directed acyclic graph in standard SQL which includes the steps of determining all verticies of the directed acyclic graph, determining an edge table from all of the verticies, deriving a path table from the verticies and the edge table, and from the path table determining at least one transitive closure path between the two if such transitive closure exists. BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a diagram of a tree of verticies. FIG. 2 is an edge table of the tree shown in FIG. 1. FIG. 3 is a table showing by binary representation the transitive closures between the verticies of the tree shown in FIG. 1. FIG. 4 is a table showing by binary representation the reflective closures between the verticies of the tree shown in FIG. 1. FIG. 5 shows another tree of verticies and the creation of an edge in this tree upon adding verticies to this tree. FIG. 6 illustrates a directed graph. FIG. 7 illustrates a directed cyclic graph. FIG. 8 illustrates the directed cyclic graph shown in FIG. 7 after an additional edge has been created. DETAILED DESCRIPTION Referring again to FIG. 1, the reflexive transitive closure of tree T according to the present invention can be represented by path table 2. Each record represents the existence of a path from a source vertex to a destination vertex.
TABLE 2
______________________________________
path
source
destination
______________________________________
V.sub.1
V.sub.2
V.sub.1
V.sub.2
V.sub.1
V.sub.3
V.sub.1
V.sub.4
V.sub.1
V.sub.5
V.sub.1
V.sub.6
V.sub.2
V.sub.2
V.sub.3
V.sub.3
V.sub.3
V.sub.4
V.sub.3
V.sub.5
V.sub.3
V.sub.6
V.sub.4
V.sub.4
V.sub.4
V.sub.6
V.sub.5
V.sub.5
V.sub.6
V.sub.6
______________________________________
This innovative representation of reflexive transitive closure permits a standard SQL statement to now be written to derive the descendants of a vertex, V.sub.i, as follows. select destination from path where source=V.sub.i It is noteworthy that the query immediately above does not break if vertices are added to or deleted from the graph. This query has the advantage of always being correct regardless of the number of levels added or deleted. Having explained the value of representing the reflexive transitive closure of a directed graph as a table in a relational database, it will be appreciated that powerful general queries can be written using standard SQL. Such queries require little or no maintenance because unlike the known methods, hard-coded knowledge about the corresponding graph does not have to be specified in the queries. The challenge that remains, however, is providing the ability to maintain the reflexive transitive closure of such a graph as vertices and edges are added to and deleted from a graph. The maintenance operations that are commonly necessary include: creating a vertex, creating an edge, deleting an edge, and deleting a vertex. Each of these four maintenance operations will be described below in the context of examining trees and directed acyclic graphs using the path and edge tables, i.e. Tables 2 and 1 respectively. Creating a New Vertex in a Tree Creating a new vertex in a tree requires one record inserted into the path table (Table 2) as follows. insert into path (source, destination) values (V.sub.i, V.sub.j) Creating an Edge in a Tree Creating an edge in a tree between vertices and requires an insertion into the edge table (Table 1) as follows. insert into edge (parent, child) values (V.sub.i, V.sub.j) Modifications are also required in the path table (Table 2) reflecting the creation of a new edge. To understand the needed modifications, consider the following example. Suppose there are 2 graph components, T1 and T2, and you wish to connect of T1 to of T2 in order to form T3 as in FIG. 5. Let V.sub.i V.sub.j symbolize the change in the path table representing an edge from V.sub.i to V.sub.j. Table 3 shows the corresponding path table for T1 and T2 and the records added to it representing V.sub.3 V.sub.4.
TABLE 3
______________________________________
path
source destination
______________________________________
V.sub.1 V.sub.1
V.sub.1 V.sub.3
V.sub.2 V.sub.2 T1
V.sub.2 V.sub.3
V.sub.3 V.sub.3
V.sub.4 V.sub.4
V.sub.4 V.sub.5 T2
V.sub.5 V.sub.5 T3
V.sub.1 V.sub.4
V.sub.1 V.sub.5
V.sub.2 V.sub.4
V.sub.2 V.sub.5 V.sub.3 V.sub.4
V.sub.3 V.sub.4
V.sub.3 V.sub.5
______________________________________
To compute V.sub.i V.sub.j, every source vertex where V.sub.i is a destination is crossed with every destination vertex where V.sub.j is a source. For the example in FIG. 5, this corresponds to: V.sub.i V.sub.j ={V.sub.1, V.sub.2, V.sub.3 }.times.{V.sub.4, V.sub.5 }={(V.sub.1, V.sub.4), (V.sub.1, V.sub.5), (V.sub.2, V.sub.4), (V.sub.2, V.sub.5), (V.sub.3, V.sub.4), (V.sub.3, V.sub.5) } which is exactly V.sub.3 V.sub.4 as shown in path table 3. The 4GL SQL required to insert records into the path table (Table 3) corresponding to V.sub.i V.sub.j is as follows. insert into path select p1.source, p2.destination from path p1,path p2 where p1.destination=V.sub.i and p2.source=V.sub.j Deleting an Edge in a Tree Deleting an edge in a tree from vertex V.sub.i to vertex V.sub.j requires a delete from the edge table (Table 1) as follows. delete from edge where parent=V.sub.i and child=V.sub.j The same cross product used in supporting insertion of records into the path table is used to support deletion of records from the path table (Table 3). The corresponding 4GL SQL is as follows. delete from path select p1.source, p2.destination from path p1, path p2 where p1.destination=V.sub.i and p2.source=V.sub.j Deleting a Vertex in a Tree Deleting a vertex in a tree requires record deletes in the edge table (Table 1) as follows. delete from edge where parent=V.sub.i or child=V.sub.i The records to delete in the path table (Table 3), reflecting the deletion of an edge from V.sub.i to V.sub.i, are derived as follows. delete from path select p1.source, p2.destination from path p1, path p2 where p1.destination=V.sub.i and p2.source=V.sub.i Directed Acyclic Graphs It can be shown that attempting to apply the tree maintenance algorithms to a directed acyclic graph in which the path between a source vertex and destination vertex is not unique causes the algorithms to break. For example, consider the directed acyclic graph shown in FIG. 6. If the path table already has unique indices and an attempt is made to create an edge from V.sub.3 to V.sub.4, the insert will fail because the tuple (V.sub.3, V.sub.4) already exists for the path V.sub.1 V.sub.2 V.sub.4. If the path table is not uniquely indexed, the tuple (V.sub.1, V.sub.4) will appear twice in the Table 4 path table.
TABLE 4
______________________________________
path
source
destination
______________________________________
V.sub.1
V.sub.1
V.sub.2
V.sub.2
V.sub.3
V.sub.3
V.sub.4
V.sub.4
V.sub.1
V.sub.2
V.sub.1
V.sub.3
V.sub.2
V.sub.4
V.sub.3
V.sub.4
V.sub.1
V.sub.4
V.sub.1
V.sub.4
______________________________________
A problem is revealed when attempting to delete the edge from V.sub.3 to V.sub.4. The delete edge process will delete both (V.sub.1, V.sub.4) tuples from the path table (Table 4), even though the path V.sub.1 V.sub.2 V.sub.4 still exists. To address this problem for directed graphs in which a (source, destination) tuple is not unique, a path.sub.-- count attribute is used. In the following sections, the use of path.sub.-- count to support reflexive transitive closure maintenance of directed acyclic graphs is explained. Creating a New vertex in a Directed Acyclic Graph Creating a new vertex in a directed acyclic graph requires one record inserted into the path table (with path.sub.-- count) as follows. insert into path (source, destination, path.sub.-- count) values (V.sub.i, V.sub.i, 1) Creating an Edge in a Directed Acyclic Graph Creating an edge in a directed acyclic graph between vertices V.sub.i and V.sub.j requires an insertion into the edge table as follows. insert into edge (parent, child) values (V.sub.i, V.sub.j) Once the path.sub.-- count attribute is introduced, one can no longer simply insert records into the path table reflecting the creation of an edge. Instead, an update to increment the path.sub.-- count of any pre-existing paths must be performed. In creating an edge from vertex V.sub.i to vertex V.sub.j, an attempt is made to find all (V.sub.s, V.sub.t) tuples in the path table where V.sub.s is an ascendant of V.sub.t and V.sub.j is a descendant of V.sub.j. For each (V.sub.s, V.sub.t) tuple found, its current path.sub.-- count value is incremented by the path.sub.-- count of (V.sub.s, V.sub.i) times the path.sub.-- count of (V.sub.j, V.sub.t). The following SQL statements modify the path table in representing the creation of an edge from source vertex V.sub.i to destination vertex V.sub.j. update path p1 from path p2, path p3 set path.sub.-- count=p1.path.sub.-- count+(p2.path.sub.-- count*p3.path.sub.-- count) where p2.destination=V.sub.i and p1.source=p2.source and p3.source=V.sub.j and p1.destination=p3.destination The update handles pre-existing paths. To represent paths that are not pre-existing, inserts must be performed as follows. insert into path select p1.source, p2.destination, p1.path.sub.-- count*p2.path.sub.-- count from path p1, path p2 where p1.destination=V.sub.i and p2.source=V.sub.j and not exists (select source, destination from path where source=p1.source and destination=p2.destination) Deleting an Edge in a Directed Acyclic Graph Deleting an edge in a directed acyclic graph from vertex V.sub.i to vertex V.sub.j requires a delete from the edge table as follows. delete from edge where parent=V.sub.i and child=V.sub.j In deleting an edge from vertex V.sub.i to vertex V.sub.j, an attempt is made to find all (V.sub.s, V.sub.t) tuples in the path table where V.sub.s is an ascendant of V.sub.i and V.sub.j is a descendant of V.sub.t. For each (V.sub.s, V.sub.t) tuple found, its current path.sub.-- count value is decremented by the path.sub.-- count of (V.sub.s, V.sub.i) times the path.sub.-- count of (V.sub.t). The following SQL statements modify the path table in representing the deletion of an edge from source vertex V.sub.i to destination vertex V.sub.j. update path p1 from path p2, path p3 set path.sub.-- count=p.sub.1.path.sub.-- count-(p2.path.sub.-- count*p3.path.sub.-- count) where p2.destination=V.sub.i and p1.source=p2.source p3.source=V.sub.j and p1.destination=p3.destination Having decremented the path.sub.-- count of all affected paths, next all path tuples where path.sub.-- count=0 are deleted, reflecting the deletion of paths. The 4GL SQL statement to perform this is as follows. delete from path where source in (select source from path where destination=V.sub.i) and destination in (select destination from path where source=V.sub.j) and path.sub.-- count=0 Deleting a Vertex in a Directed Acyclic Graph Deleting a vertex in a directed acyclic graph requires record deletes in the edge table as follows. delete from edge where parent=V.sub.i or child=V.sub.i The records to delete in the path table are equivalent to the deleting an edge from V.sub.i to V.sub.i as follows. update path p1 from path p2, path p3 set path.sub.-- count=p1.path.sub.-- count-(p2.path.sub.-- count*p3.path.sub.-- count) where p2.destination=V.sub.i and p1.source=p2.source and p3.source=V.sub.i and p1.destination=p3.destination delete from path where source in (select source from path where destination=V.sub.i) and destination in (select destination from path where source=V.sub.i) and path.sub.-- count=0 Directed Cyclic Graphs It can be shown that the procedures to maintain reflexive transitive closure for directed acyclic graphs break when applied to directed cyclic graphs. Consider the directed graph shown in FIG. 7 which shows a graph with two vertices (V.sub.1, V.sub.2) and a directed path from V.sub.1 to V.sub.2. The corresponding path table (Table 5) appears as follows.
TABLE 5
______________________________________
source destination
path.sub.-- count
______________________________________
V.sub.1 V.sub.1 1
V.sub.2 V.sub.2 1
V.sub.1 V.sub.2 1
______________________________________
Now assume an edge from V.sub.2 to V.sub.1 as shown in FIG. 8 is added to FIG. 9. The path table corresponding to FIG. 8 will appear as follows in Table 6.
TABLE 6
______________________________________
source destination
path.sub.-- count
______________________________________
V.sub.1 V.sub.1 2
V.sub.2 V.sub.2 2
V.sub.1 V.sub.2 2
V.sub.2 V.sub.1 4
______________________________________
Note that even though the graph in FIG. 9 visually appears symmetric, the path table shows a bias in path.sub.-- count for tuple (V.sub.2, V.sub.1). This looks bothersome and, indeed, becomes troublesome if the edge from V.sub.2 to V.sub.1 is deleted. The corresponding path table (Table 7) will appear as follows.
TABLE 7
______________________________________
source destination
path.sub.-- count
______________________________________
V.sub.1 V.sub.1 -2
V.sub.2 V.sub.2 -2
V.sub.1 V.sub.2 -2
______________________________________
The expectation was to assume that the operations of creating an edge from V.sub.2 to V.sub.1 and deleting the edge from V.sub.2 to V.sub.1 were inverse operations that would leave the path table as shown in Table 5. The fact that the state of the path table is different indicates that the maintenance procedures for directed acyclic graphs don't work for directed cyclic graphs. This is shown as a limit of the present invention in that maintenance of the reflexive transitive closure for directed cyclic graphs is beyond the immediate scope of the present invention. Graph Representation Analysis If a directed graph contains N vertices, the number of edges is bound by the following. N-1<=#of edges<=N.sup.2 The number of (source, destination) vertex pairs required to represent the reflexive transitive closure of a directed graph containing N vertices is bound by the following. 2N-1<=#of (source, destination) vertex pairs<=N.sup.2 The number of (source, destination) vertex pairs required to represent the reflexive transitive closure of a directed acyclic graph containing N vertices is bound by the following. 2N-1<=#of (source, destination) vertex pairs<=(N+1)(N)/2 For a decomposition directed acyclic graph of N vertices in which the length between any (source, destination) vertex pair is unique and less than K, the number of (source, destination) vertex pairs required to represent the reflexive transitive closure is bound by the following. 2N-1<=#of (source, destination) vertex pairs<=›(N/K).sup.2 !.multidot.K(K-1)/2+N Automation of Path Table Maintenance Most commercial relational databases support rules and procedures for automation of path maintenance. Each of the path table SQL statements described previously can be encapsulated into SQL procedures, all in accordance with the present invention. One way to automate is to define database rules that are activated whenever a vertex or edge is added or deleted. The activation of a rule then causes the appropriate path table maintenance procedures, also known as update procedures, to start executing. For instance, if the following rule is defined in a database system, such as Ingres.RTM., the rule is activated into action whenever a record is inserted into the edge table.
______________________________________
create rule edge.sub.-- insert after insert of edge table
execute procedure path.insert (parent=NEW.parent,
child=NEW.child)
with path.sub.-- insert also defined in a database system (such as
Ingres)
as follows:
create procedure path.sub.-- insert (parent integer4, child integer4)
BEGIN
insert into path
select p1.source, p2.destination
from path p1, path p2
where p1.destination=:parent
and p2.source=:child;
END;
______________________________________
While the invention has been particularly illustrated and described with reference to preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form, details, and applications may be made therein. It is accordingly intended that the appended claims shall cover all such changes in form, details and applications which do not depart from the true spirit and scope of the invention.
|
Same subclass Same class Consider this |
||||||||||