18 citations · 39 across the 7 of their papers we have counts for
8 papers
A Unifying Perspective on Succinct Data Representations
Benny Kimelfeld, Wim Martens, Matthias Niewerth
Factorized representations (FRs) are a well-known tool to succinctly represent results of join queries and have been originally defined using the named database perspective. We def…
MSO Queries on Trees: Enumerating Answers under Updates Using Forest Algebras
Sarah Kleest-Meißner, Jonas Marasus, Matthias Niewerth
We describe a framework for maintaining forest algebra representations that are of logarithmic height for unranked trees. Such representations can be computed in O(n) time and upda…
Representing Paths in Graph Database Pattern Matching
Wim Martens, Matthias Niewerth, Tina Popp +2
Modern graph database query languages such as GQL, SQL/PGQ, and their academic predecessor G-Core promote paths to first-class citizens in the sense that paths that match regular p…
Containment of Simple Regular Path Queries
Diego Figueira, Adwait Godbole, S. Krishna +3
Testing containment of queries is a fundamental reasoning task in knowledge representation. We study here the containment problem for Conjunctive Regular Path Queries (CRPQs), a na…
A Trichotomy for Regular Trail Queries
Wim Martens, Matthias Niewerth, Tina Popp
Regular path queries (RPQs) are an essential component of graph query languages. Such queries consider a regular expression r and a directed edge-labeled graph G and search for pat…
Enumeration on Trees with Tractable Combined Complexity and Efficient Updates
Antoine Amarilli, Pierre Bourhis, Stefan Mengel +1
We give an algorithm to enumerate the results on trees of monadic second-order (MSO) queries represented by nondeterministic tree automata. After linear time preprocessing (in the…
Constant-Delay Enumeration for Nondeterministic Document Spanners
Antoine Amarilli, Pierre Bourhis, Stefan Mengel +1
We consider the information extraction framework known as document spanners, and study the problem of efficiently computing the results of the extraction from an input document, wh…
On the state complexity of closures and interiors of regular languages with subwords and superwords
Prateek Karandikar, Matthias Niewerth, Philippe Schnoebelen
The downward and upward closures of a regular language are obtained by collecting all the subwords and superwords of its elements, respectively. The downward and upward interio…