Incremental Maintenance of Shortest Distance and Transitive Closure in First Order Logic and SQL
Authors: C. Pang, G. Dong, K. Ramamohanarao
Date: June 2005
Abstract:
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 given 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 the 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(n2) number of tuples, where n is the number of vertices, and have AC0 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 non-database query type of maintenance algorithms.
Keywords: Database view, first-order logic, incremental algorithm, maintenance, SQL
Publisher: © 2005 ACM. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version is expected to be published in ACM Transactions on Database Systems, September 2005, http://www.acm.org/tods/
Download the paper (PDF: 418KB)