Graph Databases for Fast Queries in UD Treebanks (2025)

Abstract: We investigate if labeled property graphs, and graph databases, can be an useful and efficient way of encoding UD treebanks, to facilitate searching for complex syntactic phenomena. We give two alternative encodings of UD treebanks into the off-the-shelf graph database Neo4j, and show how to translate syntactic queries into the graph query language Cypher. Our evaluation shows that graph databases can improve query times by several orders of magnitude, compared to existing approaches.

## motivation universal dependencies (ud; de @xcite has celebrated 10 years of existence and has become a mature framework for text annotation. currently there are almost 300 ud treebanks for almost 170 languages @xcite . one prominent use case of ud treebanks is to find examples of syntactic phenomena, within or across languages. e.g., @xcite investigated if it is possible to identify grammatical constructions in different languages by searching for morphosyntactic patterns. some of the queries they came up with were quite complexthey needed to cover all possible tree structures for a given construction, and at the same time rule out alternative interpretations. there are several tools for searching in syntactic treebanks, such as annis3 @xcite , alpinograph @xcite , pml tree query @xcite , and grew-match @xcite . they support complex queries and are usually efficient enough to be used on the existing ud treebanks. for example, grew-match returns results within a few seconds, even when running a complex query on the largest ud treebank @xcite . if we are only interested in performing searches in manually annotated treebanks, the current tools are probably good enough. however, there are plenty of automatically annotated very large corpora. 1 if we want to perform searches for complex syntactic phenomena in such large treebanks (10-100 million tokens or more), the current query tools are not efficient enough. so there is a need for alternative approaches. in this paper we investigate if existing off-theshelf graph databases can be useful and efficient as a backend for complex searches in treebanks. we do this by giving two possible ways of encoding ud trees as labelled property graphs, which is the format underlying the neo4j graph database @xcite . we also show how to translate grew-match queries into the graph query language cypher, and perform an extensive evaluation of the efficiency of both encodings, compared to each other, and to the grew-match query system. our results show that existing off-the-shelf graph databases such as neo4j can be very useful for performing large-scale complex syntactic searches in very large corpora. ## encoding ud as property graphs in order to store a ud-annotated treebank in a neo4j database, it first has to be encoded as a labelled property graph. in this section we present an encoding scheme for dependencies, word annotations and structures, which we call the propertybased encoding. then we discuss an alternative encoding for annotations, which will be called the node-based encoding. finally, we discuss how database constraints and indexes can be used to support the encoding. ## querying in encoded corpora to demonstrate the capabilities of the cypher query language, we will now describe a straightforward algorithmic approach to translate grew-match queries into cypher queries. for every word matched in a grew-match pattern, add a match clause for a word node with the same identifier. further, add a single return clause at the end of the query and add all introduced identifiers to that clause. while it is not necessary to match all words first, doing so simplifies the translation, as words can be referred to by their identifier afterwards. then, translate each of the clauses in a grew-match request as follows: clauses in grew-match accessing annotations have to be translated differently depending on the encoding scheme. we will consider how this is done on the example x [@xmath0. if multiple attribute-value pairs are specified, a match clause is added for each of them. values of properties in grew-match can also be specified in terms of a regular expression or a disjunction of values. in these cases a direct translation into a match clause is not possible and we use the where clause to represent these constraints. for the node-based encoding of annotations, the corresponding nodes have to be fetched via a match clause without specifying their value. a grew-match clause like x [@xmath1.lemma in ["der","die"], under the property-based annotation scheme. for the node-based annotation scheme it is instead translated into the following two clauses: match (x)-[:lemma]->(xlemma:lemma), and where xlemma.value in ["der","die"]. there are some special cases to consider when translating queries. a query for the root node of a sentence can be translated into a match clause with the root label. further, queries in grew-match consider each sentence as an individual graph. consequently, all words in a grew-match request are implicitly constrained to the same sentence. this restriction has to be translated as well, by adding a match clause relating otherwise unrelated words to the same dependency tree: (x)-[:deprel]-+(y). ## evaluation this section presents the performance of neo4j as a corpus system for ud-annoated treebanks in different scenarios to evaluate, (a) whether neo4j is a viable system for treebanks and (b) how the presented encoding schemes perform. we mainly consider two perspectives here: the perspective of an administrator encoding treebanks and provisioning the storage space for the database. and the perspective of users wanting to search treebanks with quick query response times. our evaluations cover encoding time, required disk space for encoded treebanks and query execution time. we developed a tool to automatically encode and import ud-annotated treebanks into a neo4j database using the presented encoding schemes. the tool and its source code is freely accessible online. 2 our tool accepts conll-u files as its input, encodes the treebank described by these files as a graph and stores this graph in a neo4j database. our measurements were obtained using neo4j version 5.26.0 and grew-match version 1.16.1, both running in docker on the same hardware. ## discussion our experiments clearly show that neo4j is a viable corpus search system for ud treebanks. ## conclusion our main conclusion from this evaluation is that graph databases are viable as backend storage for treebanks. the study is only done on ud treebanks, but there is nothing very ud-specific in our encodings or the graph databases, so we believe that this would be useful for all kinds of treebanks. using graph databases it will be possible to search for complex syntactic phenomena in very large treebanks with 100 million tokens and more. since we translate the treebanks to a general graph, it should definitely be possible to include more kinds of relations, such as anaphoric references, semantic databases, and morphological segmentation. including all kinds of relations in one single graph database opens up for doing largescale searching for complex queries on several linguistic levels at once.