Incremental maintenance of shortest distance and transitive closure in first-order logic and SQL

Abstract

<jats:p> Given a database, the view maintenance problem is concerned with the efficient computation of the new contents of a given view when updates to the database happen. We consider the view maintenance problem for the situation when the database contains a weighted graph and the view is either the transitive closure or the answer to the all-pairs shortest-distance problem ( <jats:italic>APSD</jats:italic> ). We give incremental algorithms for <jats:italic>APSD</jats:italic> , which support both edge insertions and deletions. For transitive closure, the algorithm is applicable to a more general class of graphs than those previously explored. Our algorithms use first-order queries, along with addition (+) and less-than (&lt;) operations ( <jats:italic>FO</jats:italic> (+,&lt;)); they store <jats:italic>O</jats:italic> ( <jats:italic>n</jats:italic> <jats:sup>2</jats:sup> ) number of tuples, where <jats:italic>n</jats:italic> is the number of vertices, and have <jats:italic>AC</jats:italic> <jats:sup>0</jats:sup> data complexity for integer weights. Since <jats:italic>FO</jats:italic> (+,&lt;) is a sublanguage of SQL and is supported by almost all current database systems, our maintenance algorithms are more appropriate for database applications than nondatabase query types of maintenance algorithms. </jats:p>