Journal of Applied Intelligence 4, 205-218 (1994) © 1994 Kluwer Academic Publishers, Boston. Manufactured in The Netherlands.
An Efficient Database Transitive Closure Algorithm I. H. TOROSLU Middle East Technical University, Computer Engineering Department, 06531 Ankara, TURKEY
[email protected]
G. Z. QADAH AT&T Bell Labs, 480 Red Hill Road, Middletown, New Jersey 07748
[email protected]
L. HENSCHEN Northwestern University, Department of EECS, Evanston, Illinois 60208
[email protected]
Abstract. The integration of logic rules and relational databases has recently emerged as an important
technique for developing knowledge management systems. An important class of logic rules utilized by these systems is the so-called transitive closure rules, the processing of which requires the computation of the transitive closure of database relations referenced by these rules. This article presents a new algorithm suitable for computing the transitive closure of very large database relations. This algorithm proceeds in two phases. In the first phase, a general graph is condensed into an acyclic one, and at the same time a special sparse matrix is formed from the acyclic graph. The second phase is the main one, in which all the page I/O operations are minimized by removing most of the redundant operations that appear in previous algorithms. Using simulation, this article also studies and examines the performance of this algorithm and compares it with the previous algorithms. Key words: Knowledge bases, deductive databases, recursive rules, recursive query processing, transitive closure queries
1. Introduction
cursive. A TC rule is a linearly recursive rule of
the following form: The development of efficient algorithms to process the transitive closure (TC) rules and queries within the context of large database systems has recently attracted a large amount of research efforts [1-18] due to the important role of the TC rules in improving the intelligence of database systems and extending them into knowledgebase systems. One of the main features of these intelligent database systems, namely, deductive databases, is their ability to define recursive rules (views) and to process queries on them directly. In deductive databases, most recursive queries appear in a very simple form in which the rule's head appears only once in the body. In general, this type of logic rule is called linearly re-
R(X, Y) : - A(X, Z), R(Z, Y)
[1]
where A(X, Z) is an extensional (base) predicate. Within the context of deductive databases [19], A(X, Z) is defined by a two-attribute normalized database relation with very many tuples, as shown in figure la. Another common view for the base relation is shown in figure lb, where the base relation is represented as a directed (tree, acyclic, or cyclic) graph (with the possibility of having more than one component). For every tuple of the base relation, there exists, in the corresponding digraph, a directed edge from node x to node y. The nodes in such a graph are the set of distinct values in the two columns of the base relation (i.e., the domain).
206
Toroslu, Qadah, and Henschen
a) Table Form
b) Graph Form
Fig. 1. The binary relation A in (a) table form and (b) graph form.
To generate solutions from the above recursire rule, another non-recursive rule, the exit rule, that defines the predicate R(X, Y) must exist. The following rule is an exit rule for relation R:
R(X, Y): - A(X, Y)
[2]
A query on a predicate that is defined by the recursive rule as in (1) and by the exit rule as in (2) is called a transitive closure query. A transitive closure query on R is a headless rule of the following form:
: - R(X, Y)
[3]
In general, a two-place unit query, such as (3), may have different forms depending on the instantiation status of the query's variables [11]. In this article, we propose an algorithm for solving the full TC problem that corresponds to the TC query form, where both of the query variables are uninstantiated. A number of algorithms have been developed to compute the full transitive closure (FTC) problem within the database context. That is, the graphs representing relations are assumed to be too large to fit into main memory, and therefore the most important consideration of the developed algorithms is the reduction of the page I/O traffic between main memory and the secondary memory. The FTC problem is a well-known and
classical problem in graph theory. Therefore, several algorithms have been developed to compute the transitive closure of the graph efficiently. However, most of these algorithms have been developed for main memory residing graphs. Some of those algorithms have been adopted to a database environment, and recently many new algorithms have been developed especially for the database transitive closure problem [6]. Some of the transitive closure algorithms are called Iterative algorithms (like semi-naive and logarithmic algorithms [4, 9, 17]). As their name implies, these algorithms solve the transitive closure problem by computing a relational algebraic expression(s) repeatedly. Because the relation size is finite, after a finite number of iterations have been performed, no more new tuples will be generated. Therefore, for these algorithms the processing time (and the number of iterations also) depends on the characteristics of the underlying database relation. In another group of transitive closure algorithms, called direct algorithms, each element (a node or an edge) is processed a constant number of times. Therefore, the termination of the algorithms is independent of the underlying database. The algorithms stop when the processing of all the elements in the graph is completed. Two types of direct algorithms exist, namely, matrixbased and graph-based algorithms. Matrix-based direct algorithms represent relations using matrix structure. Some examples are Warren's [20] and Warshall's [21] algorithms. Graph-based direct algorithms, on the other hand, are defined in terms of graph traversal operations on the relation graph. Usually, graphbased algorithms are developed for acyclic graphs, and therefore, cyclic graphs are converted into acyclic ones by condensing the strongly connected components into one node. Some graph-based direct algorithms are [10, 22, 231. The most recent algorithms for the TC problem are the hybrid ([1]) and the spanning tree algorithms ([7]). The hybrid algorithm combines the matrix representation technique of a relation with the graph traversal operations. The spanning tree algorithm improves upon the hybrid algorithm by storing the successor list in a form of
Efficient Database Transitive Closure Algorithm
a spanning tree instead of a flat list. In [7], it is shown that the spanning tree algorithm outperforms all the other database transitive closure algorithms. Therefore, in this article we will present and discuss the spanning tree algorithm only and compare it with our newly proposed algorithm. In section 2, we present the spanning tree algorithm and discuss its drawbacks. Section 3 presents the new algorithm. In section 4, we compare the performance of these two algorithms and show the superiority of the new algorithm over the spanning tree one. Finally, section 5 presents some concluding remarks.
2. The Spanning Tree Algorithm The most recent transitive closure algorithm (proposed by S. Dar and H. V. Jagadish in [7]) is called the spanning tree algorithm. In this algorithm, successors of the nodes in a relation graph are kept in the form of spanning trees instead of flat lists. In the spanning tree structure, the successors of each node are stored to create paths from the root node to all the nodes reachable from that root node. The spanning tree algorithm is developed for (directed) acyclic graphs. However, by using Tarjan's algorithm ([24]), a general graph with cycles can be converted into an acyclic one by collapsing all the nodes in a strongly connected compo-
nent into one node. At the same time, a topological ordering of the nodes in the condensed graph nodes, to be used during the main phase of the spanning tree algorithm, is computed. In the main phase of the spanning tree algorithm, shown in figure 2, the nodes of a graph are processed in a topological order. However, the immediate successor of each one of these nodes is processed in a reverse topological order to add (merge) their already computed spanning trees to the node's own spanning tree. Since, in the main phase, nodes are processed in a topological order, it is guaranteed that before starting to process one node, all its immediate sucessor's spanning trees will have been generated. Because the successor sets are stored in a form of a tree rather than a flat list, instead of adding one entire successor list to another, one spanning tree is merged recursively to another, stopping when a node that has already been recorded is reached. The function m e r g e _ t r e e ( i , k, l, j ) merges the subtree rooted at k in the successor spanning tree o f j into the successor spanning tree of i as a new child of node l. To maintain a successor spanning tree, a third field is added to the tuples representing the "parent" information. Therefore, a tuple represents a closure edge ij, where / is the parent of j in the successor spanning tree of i. Figure 3 shows how the spanning tree algorithm computes the TC of the relation shown in figure 1. The successors of node f are computed
procedure spanning_tree_algorithm() Sort the nodes in reverse topological order
A--+
fori= lton forj=i-ldownto 1 if j is an immediate successor o f i
B --+
merge_tree(i, j, i, j)
end
C--+
procedure merge_tree(i, k, l, j ) if < i , k , _ > return /, else
k is in tree(i) then return , /
D ~
insert < i , k , l >
E--+
for each node m such that there is a tuple < j , m , k > / ,
B --+
207
/ * add edge lk to tree(i) , /
merge_tree(i~ m, k , j )
end Fig. 2. The spanning tree algorithm.
k m E tree(j) * /
208 A Tree b
Toroslu, Qadah, and Henschen B Merge
(h,~,b,~) I
C D E Check Insert List [ ~ (}
c
d d d e e e e e g g g g g g g f f f f f f
I
(d,c,d,c) (d,a,c,c) (d,a,d,a) (e,d,e,d) (e,c,d,d) (e,a,c,d) (e,b,e,b) (e,a,b,b) (g,e,g,e) (g,d,e,e) (g,c,d,e) (g,~,c,e) (g,b,e,e) (g,d,g,d) (g,b,g,b) (f,d,f,d)
(f,c,d,d) (f,a,e,d) (f,b,f,b) (f,a,b,b) (f,a,f,a)
--+{a} --+ {}
-+ {c} -+ {a} --+ {} -+ {a}
~ {d,b} --+ {c} --+{2} --+{} --+ {}
-+ {c} -+ {a} --+ {} --+ {2}
Fig. 3. Execution of the spanning tree algorithm on relation A.
as follows: Before computing node f's successors, the spanning trees of each one of its immediate successors (nodes d, b, and a) will have already been generated in previous steps (refer to figure 3). Because immediate successors are processed in reverse topological order, first, node d is processed, and its spanning tree is merged to the spanning tree of node f (which is empty at the beginning) by adding d itself and e and a from node d's spanning tree. Then the second immediate successor, node h, is processed. During the merge of its spanning tree, node a, which has already been added to the spanning tree of node f from node d, is encountered again. Therefore, that merge is terminated at that point after adding only the root node b. The last immediate successor of node f is node a. However, even without scanning its spanning tree, the merge is halted because node a is already in the spanning tree of node f. As a result, nodes d, e, a, and b are added to the spanning tree of node f. During this computation, two redundant operations have been performed to stop the merging of the spanning
trees, both at node a. One of these operations is used to stop the merging of the spanning tree of node b to the spanning tree of node f, and the other is used to stop the merging of the spanning tree of node a (itself) to the spanning tree of node f. This means that the tuple is created three times in the whole process, two of which are redundant. The redundant tuple creations are used to stop the merge of the trees to minimize further redundant tuple generations.
3. The New FTC Algorithm Although the spanning tree algorithm has been shown to outperform every one of its competitors in computing the transitive closure of a database relation, it still involves some redundant computations such as the creation of redundant tuples. If we can guarantee that each one of the transitive closure tuples will be generated only once, then all the generated tuples can be added directly to the transitive closure in a sequential manner. Similar to the spanning tree algorithm, the algorithm to be presented here includes an initial phase where the general graph is condensed into an acyclic graph. Such a graph reduction is achieved by using a depth-first search procedure that stores the resulting acyclic graph in a special matrix form. The main phase of the algorithm, which executes after the initial phase is completed, does not have any redundant tuple creation. After presenting the special matrix structure and the way it is created using the depth-first search, we compare the algorithm's main phase with that of the spanning tree and show its superior performance over that of the spanning tree algorithm. The structure used in our algorithm is a special matrix in which rows represent the paths in the graph. Basically, depth-first search is used to create the paths of the graph. In a simple graph with no backward, cross, or forward edges (a simple tree), paths can be stored as a sequence of nodes starting from the root node (the node with no incoming edges) and ending at the leaf nodes. However, if the paths are directly stored, some of the nodes that participate in different paths must be repeated. Instead of storing every
Efficient Database Transitive Closure Algorithm
node in all the paths, the c o m m o n parts of these paths can be stored only once to avoid duplications. If two paths P1 = < al . . . . . an, br . . . . . b m > a n d P 2 = have the c o m m o n parts < a~, . . . , an > , then P~ and P2 can be stored in the two consecutive rows of the matrix as < al . . . . . a , , b~ . . . . . b m > and < - - n e m p t y e n t r i e s - - , c~. . . . . c¢ > where the first n entries of the second row are empty. Simply, each row represents a path starting from the first column of the row. The empty entries at the beginning of the rows inherit the paths from the non-empty entries of their nearest upper row(s). In this way, trees (the simplest forms of graphs) can be stored in the matrix form without repeating any node. The matrix on the left in figure 4b represents the tree in figure 4a created by doing a depth-first search on the tree starting at the root node a. The last row of this matrix represents the path < a, e, g > (e comes from the third row and a comes from the first one). For complicted graphs with backward, forward, and cross edges, some more information must be added to this structure in order to prevent the repetition of nodes in the matrix structure. Depth-first search visits each edge once, and one entry is created for each edge in the matrix for the corresponding depth-first tree (plus one entry for each root node). When an edge is
a) Graph Form Representations
12 3
b) Matrix Form Representations
Tree and graph in (a) graph form representations and (b) matrix form representations. F i g . 4.
209
visited, the destination node is entered into the matrix. This is simple for the tree case, because each node has only one incoming edge. Therefore, each node is visited only once and entered into the appropriate location in the matrix. However, if there is more than one incoming edge to a node, the depth-first search will visit the same node more than once (as many times as the number of the node's incoming edges). In such a case, to prevent the duplicate storage of the nodes in the matrix, a different technique is used; for the first visit to the node, it is entered into the matrix, and the coordinates of its location is recorded. On subsequent visits, instead of the node itself, its coordinates are entered into the matrix (a pointer to the already stored node). In this way, we guarantee that only a single copy of each one of the graph's nodes is entered into the matrix. Moreover, we guarantee that only one entry (either a node or a pointer) is created in the matrix for each edge in the graph. In figure 4, a complex graph (the graph on the right of figure 4a) and its associated matrix (the matrix on the right of figure 4b) are presented. The graph has forward (a, d), backward (c, b), and cross (f, d) edges. These edges are represented by pointers in the matrix on the right of figure 4b. In this graph there are eight edges, and in its matrix representation there are 8 + 1 = 9 non-empty entires (one for root node a). If every node in the graph has at least one incoming edge, then any node in that graph can be chosen to be the root node from which the depth-first search process of the graph can begin. In the implementation of this sparse matrix, the empty entries do not need to be explicitly stored. The matrix can be stored sequentially row by row. For each row, storing the column number of its fi;st non-empty entry and the sequence of non-empty entries in the row is sufficient. Thus, the size of the stored matrix is much smaller than the original relation. After the special matrix form is created, finding the transitive closure of the graph involves the processing of each node one by one to compute the successor lists. The matrix is sequentially searched top-down. If the entry currently searched has a node (pointers are skipped), say n o d e i with coordinates (rowi, c o O , then its successors are determined as follows: starting from
210
Toroslu, Qadah, and Henschen
the next non-empty entry, the matrix is scanned until reaching a row that starts with a column whose number is smaller or equal to cole. During this scan, all the nodes found are directly added to the successor list (succe) of the node nodee. All the successor lists, which form the transitive closure of the processed graph, are stored on disk. Successor lists can be created sequentially as the nodes are added to them. Meanwhile, pointers pointing to the coordinates above (rowe, coli) are added, without repetitions, to the pointer list (poinO of nodee in ascending order. Therefore, pointer lists will be sorted using the coordinates to which they are pointing. Because pointer lists are very small, as will be seen in the next section of this article, these lists are kept in the main memory. When the scanning of one segment of the matrix is over, the pointer list of nodee, pointe, is processed to find the rest of the successors of nodee. Because the processed graph is restricted to be acyclic, pointers in pointe may represent forward or cross edges (but not backward ones). Forward edges are not processed, since they do not generate any additional nodes to the successor lists (they do not point to coordinates above the node's own coordinate). One pointer can point to a node that is a successor of a node pointed at by another pointer. In this case, processing the second pointer will be sufficient, because it will scan the other one and its successors anyway. To be able to achieve this, the pointer that will be processed next is selected as follows: all the pointers in pointi are scanned bottom-up to find the one for which all the pointers below it are its successors. It is easy to determine whether a coordinate is a successor of another one. A coordinate (ri, cj) is a successor of (rk, ck) if
pointer list. Then the processing of the node pointed to by the selected pointer is done in the same way as for the original node nodee. The only difference is that the node itself is also added to the successor list succe, together with its own p r o c e d u r e ftc_algorithm 0 for (x, y) = (1, 1) u n t i l E O F do { s w i t c h (type of matrix[x, y]) POINTER END-ROW
:
x=x+l; y = row_begin[x]; NODE : i = matrix[x, y].node; pointi = O; succi = O; n_pointers = O; find_successors(i, x, y); w h i l e pointi 5~ 0 do { pointerw = select_pointer(); n_pointers = n_pointers - 1; (xp, yp ) = pointerw .coord; succi = succi • matrix[xp, yp].node find_successors(i, xv , yp ); }
y=y+l;} end p r o c e d u r e find_successors(i, xi , Yi )
(x, y) = (x. ~, + 1); while y > yi do { s w i t c h (type of matrix[x, y]) POINTER : if (matrix[x, y].pointer f~ pointi ) a n d (matrix[x, y].pointer.coord < (xi, yl)) t h e n { pointi = pointi Usorted matrix[x, y].pointer; n_pointers = n_pointers + 1; }
y=y+l; END_ROW
:
x--x+l; y = row_begin[x]; NODE : succl = succi • m a t r i x [ z , y].node;
y=y+l;} end p r o c e d u r e select_pointer 0 flag = TRUE;
either rj = r~ and cj < ck; or V(rl) where r~ ck. For this computation, another small array is used that has the column numbers of the first nonempty entries for each row (called row beginnings). This array is also scanned bottom-up to find whether a given pointer is a successor of another one. After the pointer is selected, that pointer and all its successor pointers are removed from the
:
y=y+l;
w h i l e flag = T R U E do { flag = F A L S E ; control_col = row-begin[points [n_pointers].row]; for k = pointi[n_pointers].row - 1 d o w n t o pointi[n_pointers - 1].row + 1 do { if row_begin[k] < control_col t h e n control_col = row_begin[k]; } i f pointi[n_pointers - 1].col < control_col t h e n { flag = T R U E ; n_pointers = n_pointers - 1; }}
return(point, In_pointers]); end
Fig. 5. The new FTC algorithm.
Efficient Database Transitive Closure Algorithm
successors. Meanwhile, the new pointers are also added to pointi. The algorithm is shown in figure 5. Because there is no backward edge in the graph, a pointer cannot point at a node such that the pointer or any of its ancestors is a successor of that node. Also, all locations (the nodes and the pointers) visited in a scan are successors of the beginning coordinate of that scan. Therefore, when the pointer is processed, it is guaranteed to stop before scanning over the previously scanned part of the matrix where the pointer is encountered. Also, because when a pointer is selected all the pointers below it (which are successors of that pointer) are removed from the pointer list, there will not be any duplicate scan on any part of the matrix. The main procedure ftc_algorithm is the outmost loop that visits all the entries of the matrix and, if there is a node in an entry, calls the find_successors to compute the successor list of that node. After the first call of this procedure, if any pointer is visited, it is also processed in the same way as the node itself. If there are more than one pointers to select the next pointer to be processed, another procedure, select_pointer, is called. As an example, consider the computation of the transitive closure of the graph in figure 1. Figure 6 shows the matrix created for the graph in figure 1. The matrix of figure 6 is created during the first phase of the algorithm. In the second phase, the successor lists of each node are computed by searching the matrix sequentially from top to bottom. If the entry visited is a node, then its successors are computed using the algorithm in figure 5. Figure 7 shows the execution of the new FTC algorithm for the matrix in figure 6. During the execution, for example, the successors of node f are computed as follows: there are only three
g
b
a
e
d
c
1,3
1,3 1,2
f
2,3 1,2 1,3 2,3
Fig. 6. Matrix representation.
2l l
pointers that can be visited as the successors of f, and they are added to the sorted pointer list. Then these pointers are searched from the bottom up to find the one that will be processed next. Among these pointers, (1, 3) is a successor of (1, 2), but (2, 3) is not a successor of (1, 2) or (1, 3) (because the second row starts at column 2). Therefore, first, (2, 3) must be processed. When the coordinate (2, 3) and its successors are visited, nodes d and e are added to the successor list of f, and one pointer, (1, 3), is added to the pointer list again. Next, the two pointers (1, 2) and (1, 3) are scanned to find the next one to be processed, and (l, 2) is selected because (1, 3) is its successor. When the coordinate (1, 2) and its successors are visited, a and b are also added to the successor list of node f. Finally, no more pointers are left, and therefore the computation of the successors of node f is completed. Only the nodes that participate in the successor list of node f are visited, and no redundant tuple is created. We can also show the generation of the successors of node f in figure 8, where the matrix is shown as a one-dimensional array (which is the way it is stored in real implementation). When the function find_successors is first called for node f, the matrix locations (6, 1) to (8, 2) are scanned (part I in figure 8). In this scan, no node is visited to add the successor list of f. Then, when the pointer (2, 3) is processed by the same function, locations (2, 3) through (3, 4) are scanned (part II in figure 8). In this part, two nodes are visited and added to the successor list of node f. After that, the pointer (1, 2)is selected and processed by scanning locations (1, 2) to (1, 3) (part III in figure 8). Two pointers visited during this scan are also added to the successor list of node f. Note that those parts (i.e., scans on the matrix) always go top-down (or left-to-right) when they are executed, and they are processed in bottom-up (or right-to-left) order. Also they never go over each other; therefore, no parts of the matrix are visited more than once to find the successor of one node. Finally, all the nodes encountered in these parts are added to the successor list sequentially. Because there is only one copy of each node in the matrix, there is no need to check when a node is added to the successor list.
212
Toroslu, Qadah, and Henschen Node Processed
Values
V i s i t coordinate 1, 1 Successors o f g Pointer list V i s i t coordinate 1, 2 Successors o f b Pointer list V i s i t coordinate 1,3 Successors o f a Pointer list V i s i t coordinate 2, 2 Successors o f e Pointer list Process [1, 2] Pointer list F i n a l successors o f e V i s i t coordinate 2, 3 Successors o f d Pointer list Process [1, 3] Pointer list Final successors o f d V i s i t coordinate 2,4 Successors o f c Pointer list Process [1, 3] Pointer list Final successors o f c V i s i t coordinate 2, 5 V i s i t coordinate 3, 4 V i s i t coordinate 4, 3 V i s i t coordinate 5, 2 V i s i t coordinate 6, 1 Successors o f f Pointer list Process [2, 3] Pointer list Process [1, 2] Final successors o f f V i s i t coordinate 6, 2 V i s i t coordinate 7, 2 V i s i t coordinate 8, 2
node g b~a, e, d, e
Comments
no pointer pointing above 111 node b a node a
node e d,e
[1, 2], [1, 3]
[1, 3] is a successor o f [1, 2]
b,a d,c,b,a node d c
[1,3] a
c~a node c
[1,3] a
a
pointer pointer pointer pointer node f
skip skip skip skip
[1, 2], [1,3], [2, 3] [2,3]
is not a successor o f [1,3]
d,c
[1, 2], [1,3]
[1, 3] is a successor o f [1, 2]
b,a d, c, b, a pointer pointer pointer
skip skip skip
Fig. 7. Execution of the new FTC algorithm.
I 1,1] 1,2 I 1,3 I 2,2 I 2,3 I 2,4 I 2,5 I 3,4 I 4,3 I 5,2 ] 6,11 6,2 I 7,2 I 8,2 I I g
I b
I a
i P a r t III*
I e
I d
i
I e
]1,3]1,3]1,212,3
P a r t II * Fig. 8. Matrix as linear array.
I f '
I1,211,312,3I Part I
Efficient Database Transitive Closure Algorithm
213
4. Comparison of the Two Algorithms
N,/Na = Nr). However, some of the nodes in a
Because the relation and the resulting transitive closure are too large to fit into main memory, they are stored on disk. Therefore, in database algorithms, the most important performance measure is the number of page I/O occurring between the main memory and the disk. For a given algorithm X, page-IO(X) is defined as the total number of disk I/O pages performed by X. To compute the page-IO of different algorithms, several simulation models have been developed. These models make use a set of basic (input) parameters. These parameters, together with their meanings and the values that they assume throughout our performance studies, are presented in table 1. Very similar techniques are also used in related studies presented in [11, 25, 263. The base relation A is a binary relation with attributes X and Y. Its cardinality, as shown in table I, is iV,. The values in the attributes X and Y are randomly drawn with r e p l a c e m e n t from the same domain. This domain is assumed to be finite with a size Nd, and the probability to draw its values is uniform. By fixing the value of Aft and changing the value of N t / N d ( = N r ) , one can generate directed cyclic and acyclic graphs with fixed numbers of arcs (i.e., base relations of the same cardinality) but variable out-degree nodes. Note that in generating random graphs in this fashion, the total number of nodes in the graph is N~ (i.e., the expected graph O u t _ D e g r e e =
generated graph will not have any outgoing/incoming arcs, and although these nodes are part of the graph and contribute to the value of its (expected) Out__Degree, nevertheless, they cannot be (and are not) included in the base relation A. For our simulations we only need to generate acyclic graphs, because the first phases of the spanning tree algorithm and our algorithm are almost identical, and therefore we are only interested in finding the performance of the second (main) phases of these two algorithms. After the first phase of the two algorithms is completed, the relation graph is reduced to an acyclic graph; meanwhile, this new acyclic graph is stored in a special structure. In the spanning tree algorithm, immediate successor lists are stored for each node in a topological order. On the other hand, in our algorithm the whole acyclic relation is stored in a special matrix form (explained in the previous section) created by using the depth-first search operation performed as a part of Tarjan's algorithm, which is used to determine the strongly connected components and to convert the general (cyclic) graph into an acyclic one. To compute the performance measure page-IO for the studied algorithms, we have used simulation. Our simulator consists of two parts, the database generator and the algorithm simulator. The database generator takes the values of the relation-related parameters of table ! as input and generates the tuples of the binary base relation (graph) A as output. Throughout our perfor-
Table 1. The basic parameters characterizing the performance models. Parameters
Definition
Typical _values
N, W,,,p¢,, W,,,,r,,,,,. Wpo,.......
The The The The
1000 tuples 32 bytes 16 bytes 4 bytes
Wr,,,,_~,,~,o Nd Nr
MM P
cardinality of the base relation A length of a tuple in A length of an attribute in A size of a pointer to point at a matrix element (row i, column j) The size of an array element used to keep the row-beginning column numbers The size of the domain underlying A's X and Y attributes The Tuple-Domain ratio (= N J N d ) , also called the ( E x p e c t e d ) O u t - D e g r e e . Main Memory size as a percentage of the base relation size Page size For simplicity we assumed x = l
1 byte Variable 1-5 . I(N,* W,,,p~,,)
W,,,p:e * x
214
Toroslu, Qadah, and Henschen
mance study, the Out__Degrees of the generated graphs are varied between l and 5. The program simulator, on the other hand, takes the tuples of the generated base relation, the hardware-related parameters, and some of the relation-related parameters as input and simulates the studied algorithms. To obtain a more accurate value of the performance measure for each one of the evaluated algorithms, the above process is repeated 10 times. The final value of page-IO is the average of the performance values obtained during these repetitions. Even without applying more sophisticated performance evaluation techniques, we can still show the superiority of our algorithm over the spanning tree algorithm by simply comparing one of the basic operations performed by these two algorithms: generation of tuples. Figure 9 shows the number of tuples generated by these two algorithms. Because our algorithm does not generate any redundant transitive closure tuple, in this figure the difference between the algorithms shows the number of redundant tuples generated by the spanning tree algorithm. Even though the number of redundant tuples increases with the outdegree in the spanning tree algorithm, still, this comparison technique does not show all the performance improvement that we have obtained in our algorithm. Because the actual performance of database algorithms is directly related to the number of page I/Os, we have also determined the number of page swaps between the main memory and the disk to get a better estimate on the performances of these algorithms. Note that increasing the page-size parameter in our simulations will also be in favor of
20000
I
I
our algorithm, because our algorithm scans the matrix and creates the tuples in a sequential manner, but the spanning tree algorithm needs direct access to the transitive closure tuples and writes the tuples created in random way. Figure 10 compares our algorithm with the spanning tree algorithm in terms of the number of page I/O performed by these algorithms using the simulation technique explained above. Instead of using the real number of page swaps that is obtained by using the parameters described in table 1, the curves of figure 10 show the ratio of the number of page swaps after normalizing them to the number of page swaps performed by our algorithm for graphs with outdegree of 1 (i.e., for both algorithms, the number of page swaps obtained for any outdegree is divided by the number of page swaps performed by our algorithm for graphs with outdegree of 1 to show the ratio of the increase in the number of page swaps). As can be seen from this figure, the performance of our algorithm is almost two times better than the spanning tree algorithm, except for very small outdegrees. We can explain the reasons behind this performance improvement of our algorithm against the spanning tree algorithm as follows: • In our algorithm, there is no redundant tuple creation. Each transitive closure tuple is created only once. Therefore, when a new tuple is generated, it can be directly recorded into the transitive closure. However, in the spanning tree algorithm, some tuples are recreated. When the successors of one node are being computed (in the form of a spanning tree) in order to prevent the addition of the same node
I
I
I
I
I
16000
# o f Tuples Generated
I
I
S.T. Alg. ~,-New Alg.
12000 8000 4000 I
0 0
1
I
I
2
I
I
3 Out Degree
I
I
I
4
Fig. 9. Performance comparisons of the algorithms (number of tuples generated for different out-degrees).
Efficient Database Transitive Closure Algorithm
10 8
I
I
I
I
I
I
S.T. Alg. ~ New Alg. ~
I
~
I
215
I
~
6 Page I / 0 Ratios
4 2 0
I
I
I
1
I
I
2
I
3
I
I
4
I
|
5
Out Degree
Fig. 10. N u m b e r of page I/O ratios.
more than once into the spanning tree, each successor node is checked against the partially generated spanning tree of that node (if it already exists in that spanning tree, the recursive merge of the spanning trees from that branch is terminated). Normally, for smaller outdegrees, we can easily keep all the successors generated for one node in the main memory, and each time a new successor is created it can be checked without requiring any page I/O operation. However, when outdegree gets larger, for some nodes the number of successors becomes close to the total number of nodes in the graph, and during the computation of the sucessors of this kind of nodes, storing the whole spanning trees in the main m e m o r y corresponding to the successors of these nodes becomes impossible. In this case creation of each new tuple generates some I/O operation. Because our algorithm does not have a problem of recreating the same tuple more than once, when a tuple is created it can simply be put into a main m e m o r y page with other tuples, and when that page becomes full it can be written into the disk without any need to reaccess any tuples in that page. Therefore, in our algorithm only one page will be sufficient to create the transitive closure tuples and write them into the disk. On the other hand, the performance of the spanning tree algorithm depends on the n u m b e r of main m e m o r y pages allocated to store one successor list.
the previously completed successor lists of lower-topological-order nodes in the computation of the successor lists of the higher-topological-order nodes. Basically, to generate new transitive closure tuples in our algorithm, only the matrix created from the base relation is used. The matrix is scanned, and all the nodes encountered during the scan are used to generate new tuples. E x c e p t for the pointers, there is no redundant access to the matrix elements to create the successors of a node. Because the size of the pointers (from table 1) is very small compared to the size of the nodes, the pointers' effect on the performance of the algorithm is very small. Also, because the matrix is scanned in a sequential manner (except after one segment is completed and the next pointer is selected, the scanning resumes by jumping to the location pointed to by that pointer), only one page in main m e m o r y will be enough to do all the accesses to the matrix, generating very few page read operations. On the other hand, because previously computed successor lists are used in the spanning tree algorithm, the spanning tree algorithm needs to keep the successor lists in some directly accessible form. This also creates transitive closure page read operations, which do not exist in our algorithm. Also, some part of these successor lists that are read into the main m e m o r y does not result in generating new transitive closure tuples.
• The second and the most important reason (probably surprisingly) for getting the superior performance in our algorithm is that our algorithm, unlike the spanning tree one, is not using
As we have mentioned earlier while describing our algorithm, there are two structures, namely, pointer lists and the row beginning array (which keeps the column number of the first nonempty
216
Toroslu,Qadah, and Henschen 10%
I
,
,
I
I
,
,
I
i
,
;
I
I
,
,
I
I
8% 6% MM sizes 4%
2% 0%
I
0
1
2
3
4
Out Degree Fig. 11. The size of the main memory needed by the new algorithm to store pointer-list and row-beginnings arrays as a percentage of the size of the base relation.
entry of each row of the matrix), that must reside in main memory during the entire computation in order to achieve the highest performance in our algorithm. Figure 11 shows the size of the sum of the largest pointer list and row beginning arrays required as a percentage of the size of the base relation. Because we have assumed the size of the main memory as 10% of the size of the base relation, these two structures can easily be stored in the main memory during the whole computation. Because only one page is needed to read the matrix (input) and only one page is needed to write the transitive closure tuples (output), the rest of the available main memory can be used to store the pointer list and the row beginnings array.
5. Conclusion
Deductive databases extend traditional relational databases into knowledge-base systems by adding features like defining recursive rules (views) and processing queries on them directly. The computation of transitive closures is one of the most frequently used operations in recursive query processing in deductive databases. Therefore, a large volume of research has been devoted to solve this problem, and as a result, a good number of new algorithms have been developed. The latest algorithm proposed in [7] has been shown to possess better performance than all its competitors. However, it still has some drawbacks. In this article, we have proposed a new transitive closure algorithm for deductive data-
base query processing. Our algorithm overcomes all the drawbacks encountered by the spanning tree algorithm. We have also compared the new algorithm with the spanning tree algorithm and showed the superior performance of the new algorithm over that of the spanning tree algorithm.
References 1. R. Agrawal and H. V. Jagadish, "Hybrid transitive closure algorithms," in Proc. 16th VLDB Conf., Brisbane, Australia, 1990, pp. 326-334. 2. R. Agrawal and H. V. Jagadish, "Multiprocessor transitive closure algorithms," in Proc. Int. Syrup. Databases in Parallel and Distributed Syst., Austin, TX, 1988, pp. 56-66. 3. R. Agrawal and H. V. Jagadish, "Direct algorithms for the transitive closure of database relations," in Proc. 13th Int. Conf. Very Large Databases, San Francisco, CA, September 1987, pp. 255-266. 4. F. Banchilon, "Naive evaluations of recurively defined relations," in Proc. Islamorada Workshop on Large Scale Knowledge Base and Reasoning Systems, Technical Report DB-004-85, MCC, Austin, TX, February 1985. 5. F. Bancilhon and R. Ramakrishnan, " A n amateur's introduction to recursive query processing strategies," in Proc. 1986 ACM-SIGMOD Conf., Washington, DC, 1986, pp. 16-52. 6. J. Biskup and H. Stiefeling, "Transitive closure algorithms for very large databases," in Workshop on Graph Theoretical Concepts in Computer Sci., Amsterdam, June 1988. 7. S. Dar and H. V. Jagadish, " A spanning tree transitive closure algorithm," Proc. Eighth Data Eng., pp. 2-11, 1992. 8. J. Han, G. Qadah, and C. Chaou, "The processing of the transitive closure queries," in Proc. 1988 Int. Conf.
Efficient Database Transitive Closure Algorithm
9.
10.
11.
12.
13.
14.
15.
16.
17.
Extending Database Technol., Venice, Italy, 1988, pp. 48-75. Y. E. Ioannidis, "On the computation of the transitive closure of relational operators," in Proc. 12th Int. Conf. VLDB, Kyoto, Japan, 1986, pp. 403411. Y. E. Ioannidis and R. Ramakrishnan, "Efficient transitive closure algorithms," in Proc. 14th VLDB Conf., Long Beach, CA, 1988, pp. 382-394. G. Z. Qadah, L. Henschen, and J. Kim, "Efficient algorithms for the instantiated transitive closure queries," IEEE TSE, vol. 17, no. 3, pp. 296-309, March 1991. G. Z. Qadah and J. Kim, "The processing of instantiated transitive-closure queries on uniprocessor and shared-nothing multiprocessor systems," J. Data Knowledge Eng., vol. 8, pp. 57-89, August 1992. I. H. Toroslu and G. Z. Qadah, " N e w transitive closure algorithm for recursive query processing in deductive databases," in Proc. Fourth Int. Conf. Tools with AI, Washington, DC, 1992, pp. 268-275. I. H. Toroslu and G. Z. Qadah, "The efficient computation of strong partial transitive closures," in Proc. Ninth Data Eng., Vienna, Austria, pp. 530-537, 1993. I. H. Toroslu and L. Henchen, " A n efficient transitive closure algorithm for distributed databases," in Fifth Int. Conf. Comput. Inf., Sudbory, Canada, 1993. J. D. Ullman and M. Yannakakis, "The input/output complexity of transitive closure," in Proc. ACM-SIGMOD Int. Conf. Management of Data, Atlantic City, NJ, 1990, pp. 44-53. P. Valduriez and H. Boral, "Evaluation of recursive
217
queries using join indices," in Proc. 1st Int. Expert Database Syst. Conf., Charleston, SC, April 1986, pp. 197-208. 18. P. Valduriez and S. Khoshafian, "Parallel evaluation of the transitive closure of a database relation," Int. J. Parallel Programming, vol. 17, no. 1, pp. 19-37, February 1988. 19. H. Gallaire, J. Minker, and J. Nicolas, "Logic and databases: A deductive approach," Comput. Surv., vol. 16, no. 2, pp. 153-185, June 1984. 20. H. S. Warren, " A modification of Warshall's algorithm for the transitive closure of binary relation," CACM, vol. 18, no. 4, pp. 218-220, April 1975. 21. S. Warshall, " A theorem on Boolean matrices," J. ACM, vol. 9, no. 1, pp. 11-12, January 1962. 22. J. Ebert, " A sensitive transitive closure algorithm," Inf. Process. Lett., vol. 12, no. 5, pp. 255-258, 1981. 23. J. Eve and R. Kurki-Suonia, "On computing the transitive closure of a relation," Acta Inf., vol. 8, pp. 303314, 1977. 24. R. Tarjan, "Depth-first search and linear graph algorithms," SIAM J. Comput., no. 1, pp. 146-160, 1972. 25. D. J. DeWitt et al., "Implementation techniques for main memory database systems," in Proc. Third ACM-SIGMOD, Waterloo, Ontario, Canada, pp. 1-8, 1984. 26. L. D. Shapiro, "Join processing in database systems with large main memories," ACM TODS, vol. l l, no. 3, pp. 239-264, September 1986.
218
Toroslu, Qadah, and Henschen
// . gg~k~
ismail tt. Toroslu received the B.S. degree from METU, Turkey, in 1987, the M.S. degree from Bilkent University, Turkey, in 1989 and the Ph.D. degree from Northwestern University, Illinois, in 1993, all in computer engineering and computer science areas. After his graduation he joined, as an Assistant Professor, the Computer Engineering Department of METU, Ankara, Turkey. His research interests include deductive databases, query processing, object oriented databases, and deductive object oriented databases.
Ghassen Z. Qadah received the B.Sc. degree in Electrical Engineering from Ain-shams University, Cairo, Egypt, in 1974 and the M.S. and Ph.D. degrees in Electrical and Computer Engineering from the University of Michigan, Ann Arbor, in 1977 and 1983, respectively. Between 1983 and 1991, Dr. Qadah was on the Faculty of the Electrical Engineering and Computer Science Department at Northwestern University. Between 1985 and 1987, he was on sabbatical leave at the Federal Institute of Technology, Zurich/ Switzerland. Dr. Qadah is now with AT&T Bell Labs. His current interest includes traditional and deductive databases, logic-base and AI machines, and parallel/distributed algorithms for data-intensive operations. Dr. Qadah has published and lectured widely in these areas. Dr. Qadah is a member of the Association for Computing Machinery and the I E E E Computer Society.
....
L. Hensehen is currently at Northwestern University and has been a professor there since 1971. He received his B.A., M.A., and Ph.D. degrees from the University of Illinois at Urbana in 1966, 1968, and 1971, respectively. His main research interests lie in the areas of artificial intelligence, automated reasoning, and the application of these to "intelligent" databases.
