Incremental Evaluation SQL Tips by Donald Burleson

Transitive closure enjoys a lot of attention in the database research community. Proving the impossibility of doing things in a certain way is one of the favorite theoretical topics. Not surprisingly, it was established very early that transitive closure cannot be expressed by simple means of relational algebra, even enhanced with aggregation and grouping.

We have already seen the power of the incremental evaluation idea in the database implementation world. Indexes and materialized views are the most familiar incremental evaluation structures. Dong et al proved that transitive closure can be efficiently maintained via an incremental evaluation system. In this section Dong's approach is explored, although with some deviation that would simplify the matter.

Let's revisit the transitive closure expression in terms of the adjacency matrix:

From a mathematical perspective this is quite a handsome series. It could be made even prettier if we consider the identity matrix - the matrix with ones on the main diagonal and zeros elsewhere. A common notation for the identity matrix is symbol 1. Perhaps the most important equality involving the identity matrix is:

There it shows that the identity matrix literally begs to be added in front of the series for the transitive closure:

Speaking in graph language, what happened is the loops were included at each node. Formally, T is now both a reflexive and transitive closure.

Are there any immediate benefits? Let's multiply T by 1 - A

All the nonzero powers of A at the right side cancel out:

Multiplying both sides by the inverse of 1 - A gives an explicit formula for the transitive closure:

Therefore, we might be able to calculate transitive closure (of directed acyclic graphs, at least), if we know how to invert matrices in SQL! Unfortunately, inverting matrices in SQL is difficult. The matrix approach, however, still shows its practical merit in the scope of an incremental evaluation system.

In the incremental evaluation method, the original graph is stored together with another graph -- its transitive closure. Every time the original graph is updated that is a new edge is inserted or deleted; the transitive closure graph has to be changed as well so that the information in both structures remains consistent. The problem of transitive closure graph maintenance essentially is finding an efficient SQL expression for the insertions and deletions in the transitive closure graph. 

Let's continue pursuing the adjacency matrix approach. Inserting an edge (x,y) into the original graph produces a new graph with the adjacency matrix that is the original matrix A incremented by S, the latter being a matrix with a single nonzero entry in column x, row y. How would this increment of the adjacency matrix affect the transitive closure matrix? Well, let's calculate. The new transitive closure matrix is:

Expanding powers into polynomials the result is:

Let's rearrange terms more suggestively:

The first series is the familiar transitive closure matrix T of the original not incremented adjacency matrix A. The second series could be factored into

which reduces to T S T. The last series vanishes if the scope is limited to directed acyclic graphs. Indeed, each term in that series is multiplied by S at least twice. In other words, each term in the series corresponds to a path in the graph that goes through the edge (x,y) twice, which implies a cycle.

Summarizing, the new transitive closure matrix reduces to:

This is a very succinct result. The result is double checked by comparing it with the query computing the transitive closure increment in Dong's paper:

SELECT *
FROM (
      SELECT VALUES (a, b)
    UNION
      SELECT Start = TC.Start, End = b
      FROM TC
      WHERE TC.End = a
    UNION
      SELECT Start = a, End = TC.End
      FROM TC
      WHERE b = TC.Start
    UNION
      SELECT Start = TC1.Start, End = TC2.End
      FROM TC AS TC1, TC AS TC2
      WHERE TC1.End = a AND TC2.Start = b
) AS T;  

SELECT *
FROM TC?NEW AS T
WHERE NOT EXISTS (SELECT *
                  FROM TC
                  WHERE TC.Start=T.Start AND TC.End=T.End)
INTO TEMP DELTA;
 

INSERT INTO TC
SELECT *
FROM DELTA;

The first part of the query, which is a union of four blocks is supposed to correspond to the transitive closure matrix increment T S T. It appears that they are very dissimilar. How can this be?

Remember, however, that we conveniently decided to operate the reflexive transitive closure matrices. If we go back and represent T as 1+T?, where T? is not reflexive anymore, then the increment matrix has to be written as (1+T?) S (1+T?) which can be expanded into with four terms as in Dong's method.

Now that we are confident with the matrix solution, it can be finalized in terms of SQL. It has already been shown the operating matrices of integers that count paths in the directed acyclic graph offers an exceptional clarity. Therefore, let's represent the transitive closure relation directly after the transitive closure matrix that was investigated earlier:

table TRC (     -- transitive, reflexive closure
   i   integer, -- tail
   j   integer, -- head
   val integer  -- weight
)

Once again, it is the reflexive property and the additional information in the val column that distinguishes this method formally from Dong's.

However, there is an ambiguity. What about zero matrix entries? There is an option available to either store it as (i,j,0) or ignore such rows. The first option simplifies SQL that maintains the table TRC. The second option provides a natural means for compressing sparse matrices.

Now all the ground work for transitive closure maintenance in SQL is complete. Inserting an edge (x,y) into the adjacency graph has to trigger a conforming change in the transitive closure table TRC. The values in the TRC.val column should be incremented accordingly by the entries of the product of three matrices T S T.

Knowing how to write a product of two arbitrary matrices in SQL, the product of three matrices -- A B C -- can be written as a composition of two binary product operations (A B) C. Alternatively, matrix elements are summed up at once

which is easy to translate into SQL:

select A.i AS i, C.j AS j, sum(A.val*B.val*C.val) AS val
from A, B, C
where A.j=B.i and B.j=C.i
group by A.i, C.j

Please note how naturally the matrix associativity property goes along with the relational join associativity.

Actually, the goal is a simpler matrix product -- T S T. There is no challenge adapting the general case to our needs:

select t1.i AS i, t2.j AS j, sum(t1.val*t2.val) AS val
from TRC t1, TRC t2
where t1.j = :x and t2.i = :y
group by t1.i, t2.j

If the option of storing zero matrix entries is chosen, then the above query fits naturally into an update statement to the TRC table:

update TRC
set val = (
   select val + sum(t1.val*t2.val)
   from TRC t1, TRC t2
   where t1.j = :x and t2.i = :y
   and t1.i = trc.i, t2.j = trc.j
   group by t1.i, t2.j  
) 

It is fascinating that the transitive closure table maintenance is solvable with a single update, but this answer is unrealistic for two reasons. First, the TRC table has to grow at some moment, and this issue is left out of scope. Second, from a performance perspective, updating or trying to update all the rows in the TRC table smells a disaster. It would be helpful to know which rows require update, and formalize it within the where clause (which is entirely missing).

Therefore, let's materialize updates to the TRC table in a designated table TRCDelta:

insert into TRCDelta
select t1.i AS i, t2.j AS j, sum(t1.val*t2.val) AS val
from TRC t1, TRC t2
where t1.j = :x and t2.i = :y
group by t1.i, t2.j

To keep this table small, matrix entries should not be stored with zero values any longer. On the other hand, by just storing a sparse matrix stored in the TRC table, the TRCDelta is automatically calculated as a sparse matrix either.

It is the TRC table update step that has to be adjusted. There are two cases:

1        All the rows in TRCDelta that do not match TRC rows have to be inserted:

insert into TRC
select * from TRCDelta
where (i,j) not in (select i,j from TRC)

1        The rows that match have to increment their values:

update TRC
set val = val + (select val from TRCDelta td
                 where td.i = trc.i and td.j = trc.j)
where (i,j) in (select i,j from TRCDelta)

This completes the program in the case of an insertion of an edge. What about a deletion? From the matrix perspective the cases of inserting an edge and deleting it are symmetric. Following the earlier development, the same matrix S that corresponds to a single edge (x,y) could be used, except that it must be subtracted everywhere. The final result in the matrix form is that transitive closure matrix T is decremented by T S T.

In the first na?e update solution for the TRC table all that must be done is to reverse the sign:

update TRC
set val = (
   select val - sum(t1.val*t2.val)
   from TRC t1, TRC t2
   where t1.j = :x and t2.i = :y
   and t1.i = trc.i, t2.j = trc.j
   group by t1.i, t2.j   
)

Please note, that this symmetry is made possible because of the extra information that was stored in the TRC table. Since the number of paths that are going from node i to node j is known, all the paths that are affected by the deletion of an edge (x,y) can simply be subtracted. In Dong's approach, maintenance under deletion is more complicated.

Carrying over the solution to sparse matrices requires little insight. The TRCDelta table that stores the T S T matrix is calculated the same way as in the edge insertion scenario. Thus, subtracting the T S T from T brings up two possibilities:

1        An entry in the transitive closure matrix T is the same as the corresponding entry in the T S T.

2        An entry in the transitive closure matrix T is bigger than the corresponding entry in the T S T.

In the first case the entry in the difference matrix T - T S T is 0. Therefore, all these entries have to be deleted: 

delete from TRC
where (i,j, val) in (select i,j, val from TRCDelta)

All the other entries have to be adjusted:

update TRC
set val = val - (select val from TRCDelta td
                 where td.i = trc.i and td.j = trc.j)
where (i,j) in (select i,j from TRCDelta)

Now that several methods for transitive closure calculation/ maintenance has been shown, let's again return to applications. Perhaps the most significant problem that can be expressed in terms of transitive closure is aggregation on graphs.