Results 1 to 10 of about 90 (75)
Containment of Simple Conjunctive Regular Path Queries [PDF]
Proceedings of the Seventeenth International Conference on Principles of Knowledge Representation and Reasoning, 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
Wim Martens
exaly +10 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
Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queries [PDF]
Logical Methods in Computer ScienceWe show that the problem of whether a query is equivalent to a query of tree-width $k$ is decidable, for the class of Unions of Conjunctive Regular Path Queries with two-way navigation (UC2RPQs).
Diego Figueira, Rémi Morvan
doaj +5 more sources
Expressiveness and static analysis of extended conjunctive regular path queries [PDF]
Journal of Computer and System Sciences, 2013 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Dominik D Freydenberger
exaly +2 more sources
Conjunctive Regular Path Queries under Injective Semantics
Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2023 We introduce injective semantics for Conjunctive Regular Path Queries (CRPQs), and study their fundamental properties. We identify two such semantics: atom-injective and query-injective semantics, both defined in terms of injective homomorphisms. These semantics are natural generalizations of the well-studied class of RPQs under simple-path semantics ...
Diego Figueira, MIGUEL Romero
exaly +3 more sources
Minimizing Conjunctive Regular Path Queries
Proceedings of the ACM on Management of DataWe study the minimization problem for Conjunctive Regular Path Queries (CRPQs) and unions of CRPQs (UCRPQs). This is the problem of checking, given a query and a number k , whether the query is equivalent to one of size at most k . For CRPQs we consider the size to be the number of atoms, and
MIGUEL Romero
exaly +3 more sources
Boundedness for Unions of Conjunctive Regular Path Queries over Simple Regular Expressions
Proceedings of the TwentyFirst International Conference on Principles of Knowledge Representation and ReasoningThe problem of whether a recursive query can be rewritten as query without recursion is a fundamental reasoning task, known as the boundedness problem. Here we study the boundedness problem for Unions of Conjunctive Regular Path Queries (UCRPQs), a navigational query language extensively used in ontology and graph database querying.
Diego Figueira +3 more
exaly +3 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
Boundedness of Conjunctive Regular Path Queries
CoRR, 2019 We study the boundedness problem for unions of conjunctive regular path queries with inverses (UC2RPQs). This is the problem of, given a UC2RPQ, checking whether it is equivalent to a union of conjunctive queries (UCQ). We show the problem to be ExpSpace-complete, thus coinciding with the complexity of containment for UC2RPQs.
Pablo Barceló +2 more
+8 more sources
Expressive Path Queries on Graph with Data [PDF]
Logical Methods in Computer Science, 2015 Graph data models have recently become popular owing to their applications, e.g., in social networks and the semantic web. Typical navigational query languages over graph databases - such as Conjunctive Regular Path Queries (CRPQs) - cannot express ...
Pablo Barcelo +2 more
doaj +1 more source