Advanced Search
Now showing items 1-4 of 4
The complexity of reverse engineering problems for conjunctive queries
(Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017)
D and an n-ary relation S+ over D.
It accepts if and only if:
1.
∏
a¯∈S+(D, a¯) is safe, and
2.
∏
a¯∈S+(D, a¯) 6→ (D, b¯) for each n-ary tuple b¯ over D that is not in S+.
The following characterizations are considered to be folklore...
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...
Expressive Path Queries on Graphs with Data
(Springer, 2015)