Dynamic Tree Isomorphism via First-Order Updates.

@inproceedings{DBLP:conf/pods/Etessami98,
  author    = {Kousha Etessami},
  title     = {Dynamic Tree Isomorphism via First-Order Updates},
  booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 1-3, 1998, Seattle, Washington},
  publisher = {ACM Press},
  year      = {1998},
  isbn      = {0-89791-996-3},
  pages     = {235-243},
  ee        = {http://doi.acm.org/10.1145/275487.275514, db/conf/pods/Etessami98.html},
  crossref  = {DBLP:conf/pods/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In databases, as in other computational settings, one would like to efficiently update answers to queries while minor changes are being made to the data. Dynamic complexity asks what resources are required to perform such updates.

In this paper our main focus will be a particular dynamic graph problem, tree isomorphism, and the efficiency of our update scheme will be measured in terms of how expressive a query language is required to express our update. Working in the framework developed by [DS93,PatImm94] for dynamic query evaluation, we show that dynamic tree isomorphism can be performed via first-order updates to a relational database (in [DS93] this framework is called a first-order incremental evaluation system, and in [PatImm94] it is called Dyn-FO).

In [EI95] it was shown that tree-isomorphism can not be expressed in first-order logic augmented with a transitive closure operator and counting, (FO + TC + COUNT) (but without ordering). We thus obtain a first example of a graph problem in Dyn-FO that is not expressible in this logic. Part of our proof shows how to build and maintain arithmetic predicates on a relevant part of the universe, from which we obtain a direct correspondence between Dyn-FO and dynamic constant parallel time. This provides some explanation for why it is so difficult to prove lower bounds for Dyn-FO.

Copyright © 1998 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

References

[Ajt83]

...

[BIS90]

David A. Mix Barrington, Neil Immerman, Howard Straubing: On Uniformity within NC¹. J. Comput. Syst. Sci. 41(3): 274-306(1990) BibTeX

[BLT86]

José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX

[Cai90]

Jin-yi Cai: Lower Bounds for Constant-Depth Circuits in the Presence of Help Bits. Inf. Process. Lett. 36(2): 79-83(1990) BibTeX

[CFI92]

...

[CH96]

...

[DS93]

Guozhu Dong, Jianwen Su: First-Order Incremental Evaluation of Datalog Queries. DBPL 1993: 295-308 BibTeX

[DS95]

Guozhu Dong, Jianwen Su: Incremental and Decremental Evaluation of Transitive Closure by First-Order Queries. Inf. Comput. 120(1): 101-106(1995) BibTeX

[DS97a]

Guozhu Dong, Jianwen Su: Space-Bounded FOIES. PODS 1995: 139-150 BibTeX

[DS97b]

...

[EI95]

Kousha Etessami, Neil Immerman: Tree Canonization and Transitive Closure. LICS 1995: 331-341 BibTeX

[Ete95]

...

[GL95]

Timothy Griffin, Leonid Libkin: Incremental Maintenance of Views with Duplicates. SIGMOD Conference 1995: 328-339 BibTeX

[GM95]

Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995) BibTeX

[GMS93]

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

[IL90]

...

[Imm89a]

...

[Imm89b]

Neil Immerman: Expressibility and Parallel Complexity. SIAM J. Comput. 18(3): 625-638(1989) BibTeX

[Imm98]

...

[KMW96]

...

[Lin92]

Steven Lindell: A Logspace Algorithm for Tree Canonization (Extended Abstract). STOC 1992: 400-404 BibTeX

[LW97]

Leonid Libkin, Limsoon Wong: Incremental Recomputation of Recursive Queries with Nested Sets and Aggregate Functions. DBPL 1997: 222-238 BibTeX

[Mil97]

...

[MSVT94]

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

[PI97]

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

[QW91]

Xiaolei Qian, Gio Wiederhold: Incremental Recomputation of Active Relational Expressions. IEEE Trans. Knowl. Data Eng. 3(3): 337-341(1991) BibTeX

[Via97]

...

Referenced by

1. Guozhu Dong, Jianwen Su: Incremental Maintenance of Recursive Views Using Relational Calculus/SQL. SIGMOD Record 29(1): 44-51(2000)