Dyn-FO: A Parallel, Dynamic Complexity Class.

@inproceedings{DBLP:conf/pods/PatnaikI94,
  author    = {Sushant Patnaik and
               Neil Immerman},
  title     = {Dyn-FO: A Parallel, Dynamic Complexity Class},
  booktitle = {Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 24-26, 1994, Minneapolis,
               Minnesota},
  publisher = {ACM Press},
  year      = {1994},
  isbn      = {0-89791-642-5},
  pages     = {210-221},
  ee        = {http://doi.acm.org/10.1145/182591.182614, db/conf/pods/pods94-210.html},
  crossref  = {DBLP:conf/pods/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Traditionally, computational complexity has considered only static problems. Classical Complexity Classes such as NC, P, NP, and PSPACE are defined in terms of the complexity of checking - upon presentation of an entire input - whether the input satisfies a certain property.

For many, if not most, applications of computers including: databases, text editors, program development, it is appropriate to model the process as a dynamic one. There is a fairly large object being worked on over a period of time. The object is repeatedly modified by users and computations are performed.

Thus a dynamic algorithm for a certain class of queries is one that can maintain an input object, e.g. a database, and process changes to the database as well as answering queries about the current database.

Here, we introduce the complexity class, Dynamic First-Order Logic (Dyn-FO). This is the class of properties S, for which there is an algorithm that can perform inserts, deletes and queries from S, such that each unit insert, delete, or query is first-order compatible. This corresponds to the sets of properties that can be maintained and queried in first-order logic, i.e. relational calculus, on a relational database.

We investigate the complexity class Dyn-FO. We show that many interesting properties are in Dyn-FO including, among others, graph connectivity, k-edge connectivity, and the computation of minimum spanning trees. Furthermore, we show that several NP complete optimization problems admit approximation algorithms in Dyn-FO. Note that none of these problems is in static FO, and this fact has been used to justify increasing the power of query languages beyond first-order. It is thus striking that these problems are indeed dynamic first-order, and thus, were computable in first-order database languages all along.

We also define "bounded expansion reductions" which honor dynamic complexity classes. We prove that certain standard complete problems for static complexity classes, such as AGAP for P remain complete via these new reductions. On the other hand, we prove that other such problems including GAP for NP and 1GAP for L are no longer complete via bounded expansion reductions. Furthermore, we show that a version of AGAP called AGAP+ is not in Dyn-FO unless all of P is contained in parallel linear time.

Our results shed light on some of the interesting differences between static and dynamic complexity.

Copyright © 1994 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

Journal Version

References

[ACF90]

Bowen Alpern, Larry Carter, Ephraim Feig: Uniform Memory Hierarchies. FOCS 1990: 600-608 BibTeX

[A*90]

...

[BC89]

David A. Mix Barrington, James C. Corbett: On the Relative Complexity of Some Languages in NC. Inf. Process. Lett. 32(5): 251-256(1989) BibTeX

[BRS91]

Allan Borodin, Alexander A. Razborov, Roman Smolensky: On Lower Bounds for Read-K-Times Branching Programs. Computational Complexity 3: 1-18(1993) BibTeX

[CFI89]

Jin-yi Cai, Martin Fürer, Neil Immerman: An Optimal Lower Bound on the Number of Variables for Graph Identification. FOCS 1989: 612-617 BibTeX

[CH82]

Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX

[CT91]

...

[DS93]

...

[DST93]

Guozhu Dong, Rodney W. Topor: Incremental Evaluation of Datalog Queries. ICDT 1992: 282-296 BibTeX

[E*92]

David Eppstein, Zvi Galil, Giuseppe F. Italiano, Amnon Nissenzweig: Sparsification-A Technique for Speeding up Dynamic Graph Algorithms (Extended Abstract). FOCS 1992: 60-69 BibTeX

[Fa74]

...

[F83]

Greg N. Frederickson: Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees. FOCS 1991: 632-641 BibTeX

[GMS93]

Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166 BibTeX

[G83]

Yuri Gurevich: Algebras of Feasible Functions. FOCS 1983: 210-214 BibTeX

[I91]

...

[I89]

...

[IL89]

...

[I87]

Neil Immerman: Languages that Capture Complexity Classes. SIAM J. Comput. 16(4): 760-778(1987) BibTeX

[J92]

Håkan Jakobsson: On Materializing Views and On-Line Queries. ICDT 1992: 407-420 BibTeX

[LST87]

John W. Lloyd, Liz Sonenberg, Rodney W. Topor: Integrity Constraint Checking in Stratified Databases. J. Log. Program. 4(4): 331-343(1987) BibTeX

[M94]

...

[MSVT93]

Peter Bro Miltersen, Sairam Subramanian, Jeffrey Scott Vitter, Roberto Tamassia: Complexity Models for Incremental Computation. Theor. Comput. Sci. 130(1): 203-236(1994) BibTeX

[N82]

Jean-Marie Nicolas: Logic for Improving Integrity Checking in Relational Data Bases. Acta Inf. 18: 227-253(1982) BibTeX

[PY88]

Christos H. Papadimitriou, Mihalis Yannakakis: Optimization, Approximation, and Complexity Classes (Extended Abstract). STOC 1988: 229-234 BibTeX

[P]

...

[P94]

...

[PI94]

Sushant Patnaik, Neil Immerman: Dyn-FO: A Parallel, Dynamic Complexity Class. J. Comput. Syst. Sci. 55(2): 199-209(1997) BibTeX

[R92]

Monika Rauch: Fully Dynamic Biconnectivity in Graphs. FOCS 1992: 50-59 BibTeX

[STV93]

Sairam Sairam, Jeffrey Scott Vitter, Roberto Tamassia: A Complexity Theoretic Approach to Incremental Computation. STACS 1993: 640-649 BibTeX

[U]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX

[Var]

Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

Referenced by

1. Chaoyi Pang, Kotagiri Ramamohanarao, Guozhu Dong: Incremental FO(+, <) Maintenance of All-Pairs Shortest Paths for Undirected Graphs after Insertions and Deletions. ICDT 1999: 365-382
2. Guozhu Dong, Leonid Libkin, Limsoon Wong: Local Properties of Query Languages. ICDT 1997: 140-154
3. Leonid Libkin, Limsoon Wong: Incremental Recomputation of Recursive Queries with Nested Sets and Aggregate Functions. DBPL 1997: 222-238
4. Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995)
5. H. V. Jagadish, Inderpal Singh Mumick, Abraham Silberschatz: View Maintenance Issues for the Chronicle Data Model. PODS 1995: 113-124
6. Guozhu Dong, Jianwen Su: Space-Bounded FOIES. PODS 1995: 139-150
7. Ti-Pin Chang, Richard Hull: Using Witness Generators to Support Bi-directional Update Between Object-Based Databases. PODS 1995: 196-207
8. Guozhu Dong, Jianwen Su: Increment Boundedness and Nonrecursive Incremental Evaluation of Datalog Queries. ICDT 1995: 397-410
9. Guozhu Dong, Leonid Libkin, Limsoon Wong: On Impossibility of Decremental Recomputation of Recursive Queries in Relational Calculus and SQL. DBPL 1995: 7
10. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents