Flexible Query Processing for SPARQL

Tracking #: 1166-2378

Authors: 
Riccardo Frosini
Andrea Calì
Alexandra Poulovassilis
Peter T. Wood

Responsible editor: 
Guest Editors Question Answering Linked Data

Submission type: 
Full Paper
Abstract: 
Flexible querying techniques can enhance users' access to complex, heterogeneous datasets in settings such as Linked Data, where the user may not always know how a query should be formulated in order to retrieve the desired answers. This paper presents query processing algorithms for a fragment of SPARQL 1.1 incorporating regular path queries (property path queries), extended with query approximation and relaxation operators. Our flexible query processing approach is based on query rewriting and returns answers incrementally according to their "distance" from the exact form of the query. We formally show the soundness, completeness and termination properties of our query rewriting algorithm. We also present empirical results that show promising query processing performance for the extended language.
Full PDF Version: 
Tags: 
Reviewed

Decision/Status: 
Minor Revision

Solicited Reviews:
Click to Expand/Collapse
Review #1
By Aidan Hogan submitted on 26/Oct/2015
Suggestion:
Minor Revision
Review Comment:

I'm happy with everything else, but the editors asked me to have another look at the issue of the uniqueness of the extended reduction. Actually I'm not completely satisfied on that aspect.

First off thanks to the authors for clarifying why my example is problematic (sorry for giving a faulty example), but I am still not convinced about the more general issue of the extended reduction being unique (even after looking at the referenced paper by Hurtado et al.).

Aside from whatever rules are applied, if I have a rule application (1) A,B->C and a rule application (2) C,D->E, if I apply rule application (1) in reverse before rule application (2), I will end up with {A,B,D,E} as a fixpoint. If I apply rule (2) in reverse before rule (1), I will eventually end up with {A,B,D} as a fixpoint. Unless some order is specified on the reverse rule application, even in the case that the ontology is acyclical, I do not see how the extended reduction is unique. The specific example I chose was not applicable here, but the general issue still seems to be present.

Let's take an apparent counter-example for the rules/approach you follow to be more clear on my confusion. Say we have K, which is acyclical:

(a,sp,b)
(b,sp,c)
(c,sp,d)

"Given an ontology K, its extended reduction extRed(K) is computed as follows: (i) compute cl(K);"

(a,sp,b)
(a,sp,c)
(a,sp,d)
(b,sp,c)
(b,sp,d)
(c,sp,d)

"(ii) apply the rules of Figure 2 in reverse until no more rules can be applied;" [no change]

(a,sp,b)
(a,sp,c)
(a,sp,d)
(b,sp,c)
(b,sp,d)
(c,sp,d)

"(iii) apply rules 1 and 3 of Figure 1 in reverse until no more rules can be applied."

Only rule 1 applies. There does not appear to be any specified order in which the rules must be applied in reverse, so let's start by removing (a,sp,c), i.e., applying rule 1 in reverse for (a,sp,b),(b,sp,c)->(a,sp,c):

(a,sp,b)
(a,sp,d)
(b,sp,c)
(b,sp,d)
(c,sp,d)

Let's now likewise remove (b,sp,d):

(a,sp,b)
(a,sp,d)
(b,sp,c)
(c,sp,d)

We can no longer remove (a,sp,d) by applying rule 1 in reverse: there is no longer any way to infer (a,sp,d) from rule 1 in one step from the other triples.

If we instead started by removing (a,sp,d), we would end up with a different extended reduction.

For this reason, I am still not convinced that the extended reduction is unique, even in acyclical cases.

If I am not mistaken, I would like some clarification in the paper on how this affects the subsequent relaxation process or how it otherwise could be fixed.

If I am mistaken, my apologies: please just send a short explanation and I will accept the paper without delay.

(Likewise apologies for switching from Accept to Minor Revision but now it seems like an issue I would like having another look at. I will try to give fast feedback so as to not hold up the paper.)


Comments