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

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 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²) number of tuples, where n is the number of vertices, and have AC⁰ 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.

REFERENCES

• 1: Giorgio Ausiello , Giuseppe F. Italiano , Alberto Marchetti Spaccamela , Umberto Nanni, On-line computation of minimal and maximal length paths, Theoretical Computer Science, v.95 n.2, p.245-261, March 30, 1992 [doi>10.1016/0304-3975(92)90267-J]
• 2: Jose A. Blakeley , Per-Ake Larson , Frank Wm Tompa, Efficiently updating materialized views, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.61-71, May 28-30, 1986, Washington, D.C., United States
• 3: Adam L. Buchsbaum , Paris C. Kanellakis , Jeffrey S. Vitter, A data structure for arc insertion and regular path finding, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.22-31, January 22-24, 1990, San Francisco, California, United States
• 4: Stefano Ceri , Jennifer Widom, Deriving incremental production rules for deductive data, Information Systems, v.19 n.6, p.467-490, Sept. 1994 [doi>10.1016/0306-4379(94)90002-7]
• 5: Camil Demetrescu , Giuseppe F. Italiano, A new approach to dynamic all pairs shortest paths, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780567]
• 6: Djidjev, H., Pantziou, G. E., and Zaroliagis, C. D. 2000. Improved algorithms for dynamic shortest paths. Algorithmica 28, 4, 367--389.
• 7: Guozhu Dong , Kotagiri Ramamohanarao, Maintaining Constrained Transitive Closure by Conjunctive Queries, Proceedings of the 5th International Conference on Deductive and Object-Oriented Databases, p.35-51, December 08-12, 1997
• 8: Guozhu Dong , Chaoyi Pang, Maintaining transitive closure in first order after node-set and edge-set deletions, Information Processing Letters, v.62 n.4, p.193-199, May 28, 1997 [doi>10.1016/S0020-0190(97)00066-5]
• 9: Guozhu Dong , Jianwen Su, Space-bounded FOIES (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.139-150, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220204]
• 10: Guozhu Dong , Jianwen Su, Incremental maintenance of recursive views using relational calculus/SQL, ACM SIGMOD Record, v.29 n.1, p.44-51, March 2000 [doi>10.1145/344788.344808]
• 11: Guozhu Dong , Rodney W. Topor, Incremental Evaluation of Datalog Queries, Proceedings of the 4th International Conference on Database Theory, p.282-296, October 14-16, 1992
• 12: Even, S. and Gazit, H. 1985. Updating distances in dynamic graphs. Methods of Operations Research 49, 371--387.
• 13: Esteban Feuerstein , Alberto Marchetti-Spaccamela, Dynamic algorithms for shortest paths in planar graphs, Theoretical Computer Science, v.116 n.2, p.359-371, Aug. 16, 1993 [doi>10.1016/0304-3975(93)90328-Q]
• 14: Stéphane Grumbach , Jianwen Su, First-order Definability over Constraint Databases, Proceedings of the First International Conference on Principles and Practice of Constraint Programming, p.121-136, September 19-22, 1995
• 15: Gupta, A., Katiyar, D., and Mumick, I. S. 1992. Counting solutions to the view maintenance problem. In Proceedings of the JICSLP Workshop on Deductive Databases, Washington DC, November 1992, K. Ramamohanarao, J. Harland, and G. Dong, Eds. 185--194.
• 16: Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
• 17: Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
• 18: Harrison, J. V. and Dietrich, S. W. 1992. Maintenance of materialized views in a deductive database: An update propagation approach. In Proceedings of the JICSLP Workshop on Deductive Databases, K. Ramamohanarao, J. Harland, and G. Dong, Eds. 56--65.
• 19: Philip Klein , Satish Rao , Monika Rauch , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.27-37, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195092]
• 20: Kuchenhoff, V. 1991. On the efficient computation of the difference between consecutive database states. In Proceedings of the Second International Conference on Deductive Object-Oriented Databases, C. Delobel, M. Kifer, and Y. Masunaga, Eds. Lecture Notes in Computer Science, Springer-Verlag, vol. 566. Springer-Verlag, 478--502.
• 21: La Poutre, J. A. and van Leeuwen, J. 1987. Maintenance of transitive closures and transitive reductions of graphs. Tech. Rep. RUU-CS-87-25, Department of Computer Science, University of Utrecht, The Netherlands.
• 22: Chih-Chung Lin , Ruei-Chuan Chang, On the dynamic shortest path problem, Journal of Information Processing, v.13 n.4, p.470-476, 1990
• 23: Pang, C. 1999. Incremental maintenance reachability of graph in first-order and its extension. Ph.D. thesis, The University of Melbourne.
• 24: Chaoyi Pang , Kotagiri Ramamohanarao , Guozhu Dong, Incremental FO(+, <) Maintenance of All-Pairs Shortest Paths for Undirected Graphs after Insertions and Deletions, Proceeding of the 7th International Conference on Database Theory, p.365-382, January 10-12, 1999
• 25: Sushant Patnaik , Neil Immerman, Dyn-FO (preliminary version): a parallel, dynamic complexity class, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.210-221, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182614]
• 26: G. Ramalingam , J. van Leeuwen , J. Hartmanis , G. Goos, Bounded Incremental Computation, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 27: Liam Roditty, A faster and simpler fully dynamic transitive closure, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 28: Liam Roditty , Uri Zwick, A fully dynamic reachability algorithm for directed graphs with an almost linear update time, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007387]
• 29: Robert Sedgewick, Algorithms in C, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 30: Oded Shmueli , Alon Itai, Maintenance of views, ACM SIGMOD Record, v.14 n.2, June 1984
• 31: Toni Urpí , Antoni Olivé, A Method for Change Computation in Deductive Databases, Proceedings of the 18th International Conference on Very Large Data Bases, p.225-237, August 23-27, 1992

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.0 General

General Terms:
Algorithms, Languages, Performance

Keywords:
Database view, SQL, first-order logic, incremental algorithm, maintenance