Querying Knowledge Graphs with Extended Property Paths

Tracking #: 2071-3284

Valeria Fionda
Giuseppe Pirrò
Mariano P. Consens

Responsible editor: 
Guest Editors Knowledge Graphs 2018

Submission type: 
Full Paper
The increasing number of Knowledge Graphs (KGs) available today calls for powerful query languages that can strike a balance between expressiveness and complexity of query evaluation, and that can be easily integrated into existing query processing infrastructures. We present Extended Property Paths (EPPs), a significant enhancement of Property Paths (PPs), the navigational core included in the SPARQL query language. We introduce the EPPs syntax, which allows to capture in a succinct way a larger class of navigational queries than PPs and other navigational extensions of SPARQL, and provide formal semantics. We describe a translation from non-recursive EPPs (nEPPs) into SPARQL queries and provide novel expressiveness results about the capability of SPARQL sub-languages to express navigational queries. We prove that the language of EPPs is more expressive than that of PPs; using EPPs within SPARQL allows to express things that cannot be expressed when only using PPs. We also study the expressiveness of SPARQL with EPPs in terms of reasoning capabilities. We show that SPARQL with EPPs is expressive enough to capture the main RDFS reasoning functionalities and describe how a query can be rewritten into another query enhanced with reasoning capabilities. We complement our contributions with an implementation of EPPs as the SPARQL- independent iEPPs language and an implementation of the translation of nEPPs into SPARQL queries. What sets our approach apart from previous research on querying KGs is the possibility to evaluate both nEPPs and SPARQL with nEPPs queries under the RDFS entailment regime on existing query processors. We report on an experimental evaluation on a variety of real KGs.
Full PDF Version: 


Solicited Reviews:
Click to Expand/Collapse
Review #1
By Peter T. Wood submitted on 25/Jan/2019
Review Comment:

I have read the revised paper as well as the authors' responses. I am happy that all my comments have been addressed, so I recommend acceptance of the paper.

I found the following typos which should be corrected in the final version:

p 1: "not friend" -> "not friends"

p 2: "since do" -> "since they do"

p 4: "translation to SPARQL this query" -> "translation of this query to SPARQL".
"The contribution of the paper" -> "The contributions of the paper"

p 20: "Indictive step" -> "Inductive step"

p 21: "that capture this kind" -> "that captures these kinds".
"an expressions" -> "an expression".
"where authors" -> "where the authors".

p 23: "being it based" -> "being based"

p 24: "into existing" -> "using existing"

p 25: "an traversed" -> "and traversed".
"at distance 3 times" -> "at distance 3, the times"

p 26: "have schema" -> "have a schema"

p 27: Fig 18 caption - "Average number of results reported in the inner boxes". In fact the results are in Table 11.
footnote 20 seems to have disappeared (perhaps because it is nested)

p 29: "enough expressive" -> "expressive enough"

Review #2
By Bo Fu submitted on 25/Jan/2019
Minor Revision
Review Comment:

I had trouble looking for the various changes that would directly address previously raised concerns... Would it be possible for the authors to correspond to each review comment with an outline of the changes made to the exact page/section please?
I have no other comments otherwise.

Review #3
Anonymous submitted on 27/Feb/2019
Major Revision
Review Comment:

Thank you for your spirited response to my review. However, your attempt to slander me so as to down-play my review is not appreciated. I guess any review can by characterized as "personal opinions", and indeed, I have given you my expert personal opinion on your paper (again, isn't that what a review is??).

I completely agree with you that EPPs (and even PPs) certainly have the "right to exist" (they are extremely important, in fact!). It is not really my opinion, however, that they *already exist*, essentially since the 1940's (the value section, i.e., Tests, is arguably new, but this is a very lightweight extension). To reiterate: this is not an opinion -- it is a fact. I agree that my phrasing "it doesn't really complicate the study" is a bit indirect. What I mean here is *these features have largely already been proposed and extensively studied*. Sorry for being indirect.

My technical review is not a gross oversimplification. I greatly appreciated the care that was put into presenting your results (in fact, the writing and presentation quality is excellent), and I in turn carefully read the technical parts of the paper (and found everything to be straightforward and correct). My job as a reviewer is not necessarily, however, to provide you with extensive proofreading and editorial comments or to rubber stamp your submission (modulo such comments). My job is primarily to determine whether or not you are advancing scientific knowledge. Sometimes a review is more on the editorial side, but this is only after the bar for advancing knowledge is met.
In the case of your submission, I am still concerned about the limited innovation, and so stand by my original "personal opinion". In doing so, in fact, I feel that I am doing my best to faithfully do "justice to Semantic Web journal".

The current revision further improves the presentation and does an excellent job of presenting your results. Since I am coming more from the query language execution side of things I can understand if I don't appreciate the full impact of your results on pushing forward SPARQL standarization efforts in the W3C.

Based upon your rebuttal and my comments above, I would only request the following two revisions:

-- greatly improve the introduction to make clear the limited scope of your contributions to a feasibility/impact study of adding the EPP features to SPARQL and SPARQL engines (there are statements to this effect here and there in the paper, but they should also be up front), making clear that the language itself builds upon established results in the study of path algebras.

-- Improve the discussion of related work/context to position EPP with respect to Tarski's Algebra. Two key recent reference here would be:
Dimitri Surinx et al. Relative expressive power of navigational querying on graphs using transitive closure. Logic Journal of the IGPL 23(5): 759-788 (2015).

George Fletcher et al. Relative expressive power of navigational querying on graphs. Inf. Sci. 298: 390-406 (2015).