Incremental maintenance of shortest distance and transitive closure in first-order logic and SQL
Author
Pang, CY; Dong, GZ; Ramamohanarao, KDate
2005-09-01Source Title
ACM Transactions on Database SystemsPublisher
ASSOC COMPUTING MACHINERYUniversity of Melbourne Author/s
Kotagiri, RamamohanaraoAffiliation
Computer Science and Software EngineeringMetadata
Show full item recordDocument Type
Journal ArticleCitations
Pang, C. Y., Dong, G. Z. & Ramamohanarao, K. (2005). Incremental maintenance of shortest distance and transitive closure in first-order logic and SQL. ACM TRANSACTIONS ON DATABASE SYSTEMS, 30 (3), pp.698-721. https://doi.org/10.1145/1093382.1093384.Access Status
This item is currently not available from this repositoryAbstract
<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 (<) operations (
<jats:italic>FO</jats:italic>
(+,<)); 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>
(+,<) 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>
Keywords
Information SystemsExport Reference in RIS Format
Endnote
- Click on "Export Reference in RIS Format" and choose "open with... Endnote".
Refworks
- Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References