Dynamic Tree Isomorphism via First-Order Updates

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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, PI971 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 ed u&ion JUstem, and in [PI971 it is called Dyn-FO). In (EI96] it was shown that tree-isomorphism can not be expressed in first-order logic augmented with a transitive closure operator and counting, (8’0 + TC +
COUNT) (but without ordering). We thus obtain a Rrst 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.
Original languageEnglish
Title of host publicationProceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington, USA
PublisherACM
Pages235-243
Number of pages9
ISBN (Electronic)0-89791-996-3
DOIs
Publication statusPublished - 1998

Fingerprint

Dive into the research topics of 'Dynamic Tree Isomorphism via First-Order Updates'. Together they form a unique fingerprint.

Cite this