Results 11 to 20 of about 86 (79)
Expressiveness and static analysis of extended conjunctive regular path queries
Journal of Computer and System Sciences, 2013 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Freydenberger, Dominik D. +1 more
openaire +1 more source
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.
Figueira, Diego +3 more
openaire +2 more sources
Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries
We present an output-sensitive algorithm for evaluating an acyclic Conjunctive Regular Path Query (CRPQ). Its complexity is written in terms of the input size, the output size, and a well-known parameter of the query that is called the "free-connex fractional hypertree width". Our algorithm improves upon the complexity of the recently introduced output-
Khamis, Mahmoud Abo +4 more
openaire +2 more sources
Approximation and Semantic Tree-Width of Conjunctive Regular Path Queries
, 2023 We 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). A previous result by Barceló, Romero, and Vardi [Pablo Barceló et al., 2016] has shown decidability for the case k = 1, and here we show that decidability in ...
Figueira, Diego, Morvan, Rémi
openaire +2 more sources
Output-Sensitive Evaluation of Acyclic Conjunctive Regular Path Queries
Conjunctive Regular Path Queries, or CRPQs for short, are an essential construct in graph query languages. In this paper, we propose the first output-sensitive algorithm for evaluating acyclic CRPQs. It is output-sensitive in the sense that its complexity is a function of the sizes of the input graph and of the query output.
Khamis, Mahmoud Abo +5 more
openaire +2 more sources
A review of data abstraction. [PDF]
Front Artif Intell, 2023 Cima G, Console M, Lenzerini M, Poggi A.
europepmc +1 more source
Data structure set-trie for storing and querying sets: Theoretical and empirical analysis. [PDF]
PLoS One, 2021 Savnik I +3 more
europepmc +1 more source
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries. [PDF]
Proceedings VLDB Endowment, 2020 Tziavelis N +5 more
europepmc +1 more source
Ontologies and Data Management: A Brief Survey. [PDF]
Kunstliche Intell (Oldenbourg), 2020 Schneider T, Šimkus M.
europepmc +1 more source