Results 1 to 10 of about 86 (79)
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 +4 more sources
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
Diego Figueira +5 more
+8 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
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 ...
openaire +1 more source
Boundedness of Conjunctive Regular Path Queries
International Colloquium on Automata, Languages, and Programming (ICALP), 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.
Barceló, Pablo +2 more
+8 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
openaire +2 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
Size Bounds and Algorithms for Conjunctive Regular Path Queries
, 2023 Conjunctive regular path queries (CRPQs) are one of the core classes of queries over graph databases. They are join intensive, inheriting their structure from the relational setting, but they also allow arbitrary length paths to connect points that are to be joined.
Cucumides, Tamara +2 more
openaire +5 more sources
Complexity of Conjunctive Regular Path Query Homomorphisms
, 2019 15 pages. Short version appeared in the proceedings of the 15th Conference on Computability in Europe (CIE 2019)
Beaudou, Laurent +4 more
openaire +2 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
Diego Figueira +2 more
openaire +2 more sources