Context-free Navigational Queries On RDF Graphs

Navigational graph queries on RDF are based on regular expressions.They have limited power of navigational queries since regular expressions have limited expressivity and some natural queries,like same generations-queries,are not expressible with regular expressions.At the same time,navigational graph queries usually have high complexity.Improving the ability of navigation queries on RDF graph without higher computational complexity has been an open problem to be solved.This paper proposed context-free navigational queries on RDF graphs which benefit from more expressivity of context-free grammar than regular expressions.It improved the ability of navigation queries without higher computational complexity.The syntax and semantics of context-free path queries proposed by this paper were formally defined.This paper proposed two algorithms and analysed the computational complexity of them.It's shown that context-free path queries have more power of navigational queries than regular path queries.The context-free path queries on RDF were implemented and then some practical queries over classical RDF graphs were performed.The experimental results show that context-free path queries get more answers in the expected time which can not be returned by regular path queries.This paper further proposed context-free SPARQL(cfSPARQL for short)that extended the standard SPARQL by adding context-free path queries for further strengthening navigational queries without higher complexity.The syntax and semantics of cfSPARQL were also shown in paper.This paper proposed context-free navigational queries on RDF graphs which improved the ability of navigation queries without higher computational complexity.Based on context-free navigational queries,SPARQL breaks the limitation of regular path query and broadens the application range.The additional expressivity can be used for modeling graph similarities,ontology alignment and extracting hypernym in field of natural language processing.