Efficient Enumeration of Path Query Results for Graph Databases

该研究项目的主要目标是开发和理论研究用于图数据库(在形式设置中，图数据库是有限的、有向的、边标记的图)的路径查询的高效求值(特别是枚举)算法，包括静态设置(即，数据库被解释为静态对象)和动态设置(即，数据库可以通过插入和删除来更新)。我们的重点是使用正则表达式(及其变体)作为其主要导航功能的路径查询语言。算法的质量(即，渐近的最坏情况运行时间)是在预处理时间和两个连续元素的枚举之间的延迟(在动态情况下，还包括所需的更新时间)中测量的，并且相对于数据复杂性，即，仅取决于数据库的大小，而查询的大小被认为是恒定的。我们的目标是具有低次运行时间多项式的多项式预处理时间、恒定延迟和多对数、次线性或线性更新时间。对于某些类型的路径查询，如果我们不能满足这些强烈的要求，我们将尝试用较低的复杂性界(就细粒度复杂性而言)来证实这一点；通常，我们专注于寻找路径查询的易于处理的子类并证明各自的二分法结果。概念上的重点将放在形式语言理论、自动机理论、词的组合学和字符串算法的算法技术的适用性上；在这方面，我们强调这样一个事实，在我们的形式化中，图形数据库与没有初始状态或接受状态的非确定有限自动机重合。数据库理论文献已经提供了基本的基于自动机的算法方法来评估(基于正则表达式的)路径查询，但对这种联系的全面和系统的研究似乎仍处于起步阶段。特别是，对成功应用于字符串算法领域的众多算法技术、组合结果和数据结构的潜力的研究仍处于非常初级的状态。此外，路径查询求值的动态情况自然会导致不确定自动机作为动态数据结构的问题，这是经典自动机理论中迄今很少关注的一个方面。

The main objective of the proposed research project is the development and theoretical investigation of efficient evaluation (especially enumeration) algorithms for path queries for graph databases (which, in a formal setting, are finite, directed, edge-labelled graphs), both in the static setting (i.e., the database is interpreted as a static object) and the dynamic setting (i.e., the database can be updated by insertions and deletions). Our focus is on path query languages that use regular expressions (and variants thereof) as their main navigational feature. The quality of the algorithms (i.e., the asymptotic worst-case running-time) is measured in the preprocessing-time and the delay between the enumeration of two consecutive elements (and, in the dynamic case, also the required update-time), and with respect to the data complexity, i.e., only depending on the size of the database, whereas the size of the query is considered as constant. We aim at polynomial preprocessing-time with low-degree running-time polynomials, constant delay and polylogarithmic, sublinear, or linear update-times. If, for some classes of path queries, we are unable to achieve these strong requirements, we try to substantiate this with lower complexity-bounds (in terms of fine-grained complexity); in general, we concentrate on finding tractable subclasses of path queries and to prove respective dichotomy results.A conceptional focus will be on the applicability of algorithmic techniques of formal language theory, automata theory, combinatorics on words, and string-algorithmics; in this regard, we stress the fact that, in our formalisation, graph databases coincide with nondeterministic finite automata without initial state or accepting states. The database theory literature already provides elementary automaton-based algorithmic approaches to the evaluation of (regular expression based) path queries, but a thorough and systematic investigation of this connection seems to be still in its beginnings. In particular, a study of the potential of the numerous algorithmic techniques, combinatorial results, and data structures, that are successfully applied in the field of string-algorithmics, is still in a very rudimentary state. Moreover, the dynamic case of path query evaluation naturally leads to questions about nondeterministic automata as dynamic data structures, which is an aspect that so far has found little attention in classical automata theory.