Results 1 to 10 of about 4,762 (250)
Fine-Grained Complexity of Regular Path Queries [PDF]
Logical Methods in Computer Science, 2023 A regular path query (RPQ) is a regular expression q that returns all node pairs (u, v) from a graph database that are connected by an arbitrary path labelled with a word from L(q). The obvious algorithmic approach to RPQ-evaluation (called PG-approach),
Katrin Casel, Markus L. Schmid
doaj +7 more sources
Containment of Simple Regular Path Queries [PDF]
CoRR, 2020 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 navigational query language extensively used in ontology and graph database querying. While it is known that containment of CRPQs is expspace-complete in general, we focus here
Diego Figueira +5 more
core +6 more sources
Rewriting of regular expressions and regular path queries [PDF]
Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, 1999 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
DIEGO CALVANESE +3 more
core +6 more sources
Conjunctive Regular Path Queries with Capture Groups [PDF]
ACM Transactions on Database Systems, 2022 In practice, regular expressions are usually extended by so-called capture groups or capture variables, which allow to capture a subexpression by a variable that can be referenced in the regular expression in order to describe repetitions of subwords. We investigate how this concept could be used for pattern-based graph querying; i.e., we investigate ...
Markus L Schmid
exaly +2 more sources
Datalog Rewritings of Regular Path Queries using Views [PDF]
Logical Methods in Computer Science, 2015 We consider query answering using views on graph databases, i.e. databases structured as edge-labeled graphs. We mainly consider views and queries specified by Regular Path Queries (RPQ).
Nadime Francis +2 more
doaj +2 more sources
The Dichotomy of Evaluating Homomorphism-Closed Queries on Probabilistic Graphs [PDF]
Logical Methods in Computer Science, 2022 We study the problem of query evaluation on probabilistic graphs, namely, tuple-independent probabilistic databases over signatures of arity two. We focus on the class of queries closed under homomorphisms, or, equivalently, the infinite unions of ...
Antoine Amarilli, İsmail İlkan Ceylan
doaj +1 more source
A Trichotomy for Regular Trail Queries [PDF]
Logical Methods in Computer Science, 2023 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 paths in G for which the sequence of labels is in the language of r. In order
Wim Martens +2 more
doaj +1 more source
2022 IEEE 38th International Conference on Data Engineering (ICDE), 2022 In the last decade, substantial progress has been made towards standardizing the syntax of graph query languages, and towards understanding their semantics and complexity of evaluation. In this paper, we consider temporal property graphs (TPGs) and propose temporal regular path queries (TRPQs) that incorporate time into TPG navigation.
Marcelo Arenas +3 more
openaire +2 more sources
Time-Series-Based Queries on Stable Transportation Networks Equipped with Sensors
ISPRS International Journal of Geo-Information, 2021 In this paper, we propose a formalism to query transportation networks that are equipped with sensors that produce time-series data. The core of the proposed query mechanism is a logic-based language that is capable to return time, value, and time-series
Erik Bollen +3 more
doaj +1 more source
Global Numerical Constraints on Trees [PDF]
Logical Methods in Computer Science, 2014 We introduce a logical foundation to reason on tree structures with constraints on the number of node occurrences. Related formalisms are limited to express occurrence constraints on particular tree regions, as for instance the children of a given node ...
Everardo Bárcenas, Jesús Lavalle
doaj +1 more source