Servicenavigation

Project Details

Back

Projekt Print View

Efficient Enumeration of Path Query Results for Graph Databases

Applicant Dr. Markus Schmid
Subject Area Theoretical Computer Science
Term from 2019 to 2023
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 416776735
 
Final Report Year 2023

Final Report Abstract

The main objective of the research project was the development and theoretical investigation of efficient evaluation algorithms (including enumeration) for path queries for graph databases. We were also interested in other data models and their respective query classes. The project’s results can be structured into three main branches. Graph databases and path queries: With respect to graph databases, a special focus of the project was on query languages that use regular expressions (and variants thereof) as their main navigational feature. In this regard, we provide an in-depth analysis of how the well-known concept of capture groups (also called backreferences) of practical regular expression engines can be added to the regular expression-based navigational features of practically relevant path query languages. In addition, we analysed the classical regular path queries (a core-feature of academical and commercial graph database systems) in the modern complexity framework of fine-grained complexity. Information Extraction and Document Spanners: Document spanners – a current hot-topic in database theory – extract tuples of intervals (which are called spans) from text documents. We formulated a class of document spanners that, in terms of expressive power, covers a large portion of the rather powerful yet mostly intractable class of core spanners, while at the same time exhibit evaluation complexities much closer to the well-behaved class of regular spanners. Moreover, we designed algorithms for evaluating (including enumerating) spanners on documents that are compressed by straight-line programs (SLPs) – a grammar-based compressions scheme that is famous in different areas of theoretical computer science, while also having many practical applications. The running times of our algorithms only depend linearly on the compressed size of the documents, which, in the best case, might be exponentially smaller compared to the uncompressed data. Due to the high compressibility of textual data in practical settings and due to the fact that many algorithms for SLP-compression exist, our approach is of practical relevance. Moreover, we were able to extend our algorithms to the dynamic setting, where we can perform updates to our compressed textual data without the need for decompression. Complex Event Processing and Subsequence Queries: The processing and analysis of traces of events that are generated on runtime by large software systems is a rather recent topic of both applied as well as theoretical research on databases. Based on classical results on the inductive inference of Angluin-style pattern languages, we formulated a class of subsequence-based queries for event traces, and provided an algorithm that infers the common structure of a given set of such event traces. This work also inspired new algorithmic challenges that are of independent interest within the field of string algorithms that we were able to partly solve.

Publications

 
 

Additional Information

© 2025 DFG Disclaimer / Copyright / Privacy Policy

Textvergrößerung und Kontrastanpassung