Efficient Enumeration of Path Query Results for Graph Databases

图数据库路径查询结果的高效枚举

• 批准号: 416776735
• 负责人: Dr. Markus Schmid
• 金额: --
• 依托单位: Lehrstuhl Logik in der Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2019
• 资助国家: 德国
• 起止时间: 2018-12-31 至 2022-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/416776735?language=en
• 关键词: Efficient; Enumeration; Path; Query; Results

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.

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