Incremental Maintenance of Shortest Distance and Transitive Closure in First-Order Logic and SQL

摘要

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 (APSD). We give incremental algorithms for APSD, 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 (< ) operations (FO(+, < )); they store O(n~2) number of tuples, where n is the number of vertices, and have AC~0 data complexity for integer weights. Since FO(+, < ) 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.