{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T04:19:57Z","timestamp":1759033197422,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2005,9,1]],"date-time":"2005-09-01T00:00:00Z","timestamp":1125532800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2005,9]]},"abstract":"<jats:p>\n            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 (\n            <jats:italic>APSD<\/jats:italic>\n            ). We give incremental algorithms for\n            <jats:italic>APSD<\/jats:italic>\n            , 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 (\n            <jats:italic>FO<\/jats:italic>\n            (+,&lt;)); they store\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) number of tuples, where\n            <jats:italic>n<\/jats:italic>\n            is the number of vertices, and have\n            <jats:italic>AC<\/jats:italic>\n            <jats:sup>0<\/jats:sup>\n            data complexity for integer weights. Since\n            <jats:italic>FO<\/jats:italic>\n            (+,&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.\n          <\/jats:p>","DOI":"10.1145\/1093382.1093384","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T16:00:45Z","timestamp":1131379245000},"page":"698-721","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Incremental maintenance of shortest distance and transitive closure in first-order logic and SQL"],"prefix":"10.1145","volume":"30","author":[{"given":"Chaoyi","family":"Pang","sequence":"first","affiliation":[{"name":"CSIRO ICT Center\/E-Health Research Center, Australia"}]},{"given":"Guozhu","family":"Dong","sequence":"additional","affiliation":[{"name":"Wright State University, Dayton, Ohio"}]},{"given":"Kotagiri","family":"Ramamohanarao","sequence":"additional","affiliation":[{"name":"University of Melbourne, Australia"}]}],"member":"320","published-online":{"date-parts":[[2005,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90267-J"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/16894.16861"},{"volume-title":"Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 22--31","author":"Buchsbaum A. L.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4379(94)90002-7"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780567"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010043"},{"key":"e_1_2_1_7_1","first-page":"35","article-title":"Maintaining constrained transitive closure by conjunctive queries. In Proceedings of International Conference on Deductive and Object-Oriented Databases (DOOD)","volume":"1341","author":"Dong G.","year":"1997","journal-title":"LNCS"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00066-5"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.220204"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/344788.344808"},{"volume-title":"Proceedings of the International Conference on Database Theory","author":"Dong G.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","first-page":"371","article-title":"Updating distances in dynamic graphs","volume":"49","author":"Even S.","year":"1985","journal-title":"Methods of Operations Research"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90328-Q"},{"volume-title":"Proceedings of Conference on Constraint Programming.]]","author":"Grumbach S.","key":"e_1_2_1_14_1"},{"volume-title":"Proceedings of the JICSLP Workshop on Deductive Databases, Washington DC","year":"1992","author":"Gupta A.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170066"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170066"},{"volume-title":"Proceedings of the JICSLP Workshop on Deductive Databases, K. Ramamohanarao, J. Harland, and G. Dong, Eds. 56--65","author":"Harrison J. V.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195092"},{"volume-title":"Proceedings of the Second International Conference on Deductive Object-Oriented Databases","author":"Kuchenhoff V.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_22_1","article-title":"On the dynamic shortest path problem","author":"Lin C. C.","year":"1990","journal-title":"J. Inf. Proc. 13(4).]]"},{"key":"e_1_2_1_23_1","unstructured":"Pang C. 1999. Incremental maintenance reachability of graph in first-order and its extension. Ph.D. thesis The University of Melbourne.]]  Pang C. 1999. Incremental maintenance reachability of graph in first-order and its extension. Ph.D. thesis The University of Melbourne.]]"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Pang C. Ramamohanarao K. and Dong G. 1999. Incremental FO(&plus; &lt;) maintenance of all-pairs shortest paths for undirected graphs after insertions and deletions. In Proceedings of the International Conference on Database Theory. Lecture Notes in Computer Science Springer-Verlag.]]   Pang C. Ramamohanarao K. and Dong G. 1999. Incremental FO(&plus; &lt;) maintenance of all-pairs shortest paths for undirected graphs after insertions and deletions. In Proceedings of the International Conference on Database Theory. Lecture Notes in Computer Science Springer-Verlag.]]","DOI":"10.1007\/3-540-49257-7_23"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/182591.182614"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Ramalingam G. 1996. Bounded Incremental Computation. LNCS 1089.]]   Ramalingam G. 1996. Bounded Incremental Computation. LNCS 1089.]]","DOI":"10.1007\/BFb0028290"},{"volume-title":"Proceedings of the 14th annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 404--412","year":"2003","author":"Roditty L.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007387"},{"key":"e_1_2_1_29_1","unstructured":"Sedgewick R. 1990. Algorithms in C. Addison-Wesley Publishing Company.]]   Sedgewick R. 1990. Algorithms in C. Addison-Wesley Publishing Company.]]"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/971697.602293"},{"key":"e_1_2_1_31_1","unstructured":"Urpi T. and Olive A. 1992. A method for change computation in deductive databases. In VLDB.]]   Urpi T. and Olive A. 1992. A method for change computation in deductive databases. In VLDB.]]"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1093382.1093384","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1093382.1093384","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:12Z","timestamp":1750278132000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1093382.1093384"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,9]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,9]]}},"alternative-id":["10.1145\/1093382.1093384"],"URL":"https:\/\/doi.org\/10.1145\/1093382.1093384","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2005,9]]},"assertion":[{"value":"2005-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}