Graph databases in many applications-semantic web, transport or biological networks among others-are not only large, but also frequently modified. Evaluating graph queries in this dynamic context is a challenging task, as those queries often combine first-order and navigational features. Motivated by recent results on maintaining dynamic reachability, we study the dynamic evaluation of traditional query languages for graphs in the descriptive complexity framework. Our focus is on maintaining regular path queries, and extensions thereof, by first-order formulas. In particular we are interested in path queries defined by non-regular languages and in extended conjunctive regular path queries (which allow to compare labels of paths based on word relations). Further we study the closely related problems of maintaining distances in graphs and reachability in product graphs. In this preliminary study we obtain upper bounds for those problems in restricted settings, such as undirected and acyclic graphs, or under insertions only, and negative results regarding quantifier-free update formulas. In addition we point out interesting directions for further research. Keywords and phrases Dynamic descriptive complexity, graph databases, graph products, reachability, path queries Digital Object Identifier 10.4230/LIPIcs.xxx.yyy.p Graph databases are important in applications in which the topology of data is as important as the data itself. Intuitively, a graph database represents objects (by nodes), and relationships between those objects (often modeled by labeled edges-see [1] for a survey on graph database models). The last years have witnessed an increasing interest in graph databases, due to the uprise of applications that need to manage and query massive and highly-connected data, as for example the semantic web, social networks or biological networks. In most of these applications, databases are not only large, but also highly dynamic. Data is frequently * Parts of this work are also included in the dissertation thesis of the third author [23] . Dynamic Graph Queries inserted and deleted, and hence so is its network structure. The goal of this work is to explore how query languages for graph databases can be evaluated in this dynamic context. Many query languages for graph databases combine traditional first-order features with navigational ones. Already basic languages (such as regular path queries, see e.g. [21, 2] ) allow to test the existence of paths satisfying constraints on their labels (e.g. adherence to a regular expression in regular path queries). Computing the answers to this kind of queries on large, highly dynamic graphs is a big challenge. It is conceivable, though, for answers to a query before and after small modifications to be closely related. Thus a reasonable hope is to be able to update the answer to a query in a more efficient way than recomputing it from scratch after each modification. Even more so if we allow to store extra auxiliary data that might ease the updating task. To what extent this is possible, and in which precise conditions, is the subject of dynamic computational complexity. Here we are interested in studying the dynamic complexity of query languages for graph databases from a descriptive approach. In the dynamic descriptive complexity setting, proposed independently by Dong, Su and Topor [9, 8] and by Patnaik and Immerman [16], a dynamic program maintains auxiliary relations with the intention to help answering a query over a (relational) database subject to small modifications (insertions or deletions of tuples). When a modification occurs, the query answers and every auxiliary relation are updated by first-order formulas (or, equivalently, by core SQL queries) evaluated over the current database and the available auxiliary data. Such programs benefit therefore from being both highly parallelizable (due to the close connection of first-order logic and small depth boolean circuits) and readily implementable in standard relational database engines. The class of queries maintainable by first-order update formulas is called DynFO. Query languages for graphs have, so far, not been studied systematically in the dynamic descriptive complexity setting. Very likely the main reason is that until recently it was not even known whether reachability in directed graphs could be maintained by first-order update formulas. That this indeed is possible was shown in [6] , with the immediate consequence that all fixed (conjunctions of) regular path queries can also be maintained. Thus regular path queries can be evaluated in a highly parallel fashion in dynamic graph databases. Motivated by this result we study the dynamic maintainability of more expressive query languages. Our focus is on regular path queries and extensions thereof-non-regular path queries and extended conjunctive regular path queries (short: ECRPQs). Some previous work on non-regular path queries has been done. Weber and Schwentick exhibited a context-free path query (the Dyck language D 2 ) that can be maintained in DynFO on acyclic graphs [20] . Also, for the simple class of path-shaped graph databases, formal language results can be transferred. Already Patnaik and Immerman pointed out that regular languages can be maintained in DynFO [16]. Later, Gelade et al. systematically studied the dynamic complexity of formal languages [11] . They showed, among other results, that regular languages can be maintained by quantifier-free update formulas, and that all context-free languages can be maintained in DynFO. The second extension of regular path queries to be studied here are extended conjunctive regular path queries. In previous work it has been noticed that conjunctions of regular path queries (CRPQs) fall short in expressive power for modern applications of graph databases [4] . A feature commonly demanded by these applications is the comparison of P. Muñoz, N. Vortmeier, T. Zeume 3 labels of paths defined by CRPQs based on relations of words (e.g. prefix, length constraints, fixed edit-distance). ECRPQs have been introduced to fulfill this requirement [4] , that is, they generalize CRPQs by allowing to test whether multiple labels of paths adhere to given regular relations. Two basic properties expressible by ECRPQs are whether two pairs of nodes are connected by paths of the same length and if so, whether also paths with the same label sequence exist. In general, maintaining the result of ECRPQs seems to be a difficult task. In this article we therefore explore the maintenance of ECRPQs in restricted settings. Finally, there is also a close connection between the evaluation of graph queries and the reachability problem in unlabeled and labeled product graphs. We discuss this connection (see Section 2), and exploit it in several of our results. Contributions First we study path queries and show that all regular path queries can be maintained by quantifier-free formulas when only insertions are allowed, all context-free path queries can be maintained by first-order formulas on acyclic graphs, and there are non-context-free path queries maintainable by first-order formulas on undirected and acyclic graphs, as well as on general graphs under insertions only. As a first step towards maintaining ECRPQs we explore for which graph classes the lengths of paths between nodes can be maintained. We exhibit dynamic programs for maintaining all distances for undirected and acyclic graphs, as well as for directed graphs when only insertions are allowed. It remains open, whether distances can be maintained in DynFO for general directed graphs, but we show that quantifier-free update formulas do not suffice. The techniques used to maintain all distances can be used to maintain variants of ECRPQs in restricted settings. Denote the extension of a class of queries by linear constraints on the number of occurrences of symbols on paths by +LC. This extension was introduced and studied in [4] . We show that all CRPQ+LCs can be maintained by first-order formulas when only insertions are allowed, and all ECRPQ+LCs can be maintained by first-order formulas on acyclic graphs. An immediate consequence of our results for distances is that reachability can be maintained in products of (unlabeled) graphs for those restrictions. By using the dynamic program for maintaining the rank of matrices from [6], we extend this result to more general graph products. Furthermore we show that pairs of nodes connected by paths with the same label sequence can be maintained in acyclic graphs using first-order update formulas. The maintenance of problems has also been studied from an algorithmic point of view. A good starting point for readers interested in upper bounds for dynamic algorithms is [18, 7] ; a good starting point for lower bound techniques is the survey by Miltersen on cell probe complexity [14] . The upper bounds for reachability obtained in [18, 7] immediately transfer to dynamic algorithmic evaluation of regular path queries (using the reduction exhibited in [6] ). Outline The dynamic setting and the basic graph query languages are introduced in Section 2. There we also discuss the connection between query evaluation and reachability in product graphs. Section 3 contains the results on maintaining graph queries. Our results for maintaining distances and ECRPQs are presented in Section 4. In Section 5 some of the results for maintaining graph queries are transferred to reachability in graph products, and we also provide results for reachability in generalized graph products. We conclude in Section 6. This is a full version of [15] . Acknowledgements We thank Pablo Barceló, Samir Datta and Thomas Schwentick for stimulating and illuminating discussions.
This is a full version of REF .
Dynamic Graph Queries
ArXiv
ArXiv
Computer Science Mathematics