Advanced Search
Now showing items 1-2 of 2
Semantic Acyclicity on Graph Databases
(SIAM, 2016)
such
that there is a path ρ in G± from n to n′ for which it is the case that the word label(ρ)
is accepted by A.
A folklore result (see, e.g., [3]) establishes that the problem of computingA(G), for
a given graph database G and 2RPQ A, can be solved in polynomial time...
.e., this is the problem of checking whether n¯ belong to Γ(G), given a UC2RPQ Γ(x¯), a graph database G, and a tuple n¯ of nodes in G such that |n¯| = |x¯|. It is folklore that evaluating UC2RPQs is not more expensive than evaluating CQs, i.e., NP-complete (see, e.g., [4...
.e., this is the problem of checking whether n¯ belong to Γ(G), given a UC2RPQ Γ(x¯), a graph database G, and a tuple n¯ of nodes in G such that |n¯| = |x¯|. It is folklore that evaluating UC2RPQs is not more expensive than evaluating CQs, i.e., NP-complete (see, e.g., [4...
On the data complexity of consistent query answering over graph databases
(Elsevier, 2017)
≤ i ≤ m it is the case that (h(xi), h(yi)) ∈ Li(G). The evaluation q(G) of q(x¯) over G
rresponds then to the set of all tuples of the form h(x¯), for h a homomorphism from q to G .
The following result is considered to be folklore (cf., [4...