Efficient path query and reasoning method based on rare axis

Abstract

A new concept of rare axis based on statistical facts is proposed, and an evaluation algorithm is designed thereafter. For the nested regular expressions containing rare axes, the proposed algorithm can reduce its evaluation complexity from polynomial time to nearly linear time. The distributed technique is also employed to construct the navigation axis indexes for resource description framework (RDF) graph data. Experiment results in DrugBank and BioGRID show that this method can improve the query efficiency significantly while ensuring the accuracy and meet the query requirements on Web-scale RDF graph data.

Keywords

graph / path / regular expression / complexity / distribution

References

[1] Berners-Lee T, Hendler J, Lassila O. The semantic web [J]. Scientific American, 2001, 284(5): 34-43.

[2] Bizer C, Heath T, Berners-Lee T. Linked data-The story so far [J]. International Journal on Semantic Web and Information Systems, 2009, 5(3): 1-22.

[3] Horrocks I, Patel-Schneider P F, van Harmelen F. From SHIQ and RDF to OWL: The making of a web ontology language [J]. Web Semantics: Science, Services and Agents on the World Wide Web, 2003, 1(1): 7-26.

[4] Jiang Y, Feng Z Y, Wang X. A multikeyrank model based on ontology for large-scale semantic data [J]. Chinese Journal of Electronics, 2014, 23(1): 119-123.

[5] Koschmieder A, Leser U. Regular path queries on large graphs [C]. Proceedings of the 24th International Conference on Scientific and Statistical Database Management. Crete, Greece, 2012.

[6] Pérez J, Arenas M, Gutierrez C. nSPARQL: A navigational language for RDF [J]. Web Semantics: Science, Services and Agents on the World Wide Web, 2010, 8(4): 255-270.

[7] Arenas M, Conca S, Pérez J. Counting beyond a Yottabyte, or how SPARQL 1. 1 property paths will prevent adoption of the standard [C]. In: Proceedings of the 21st International Conference on World Wide Web. Lyon, France, 2012.

[8] Jiang Y, Feng Z Y, Wang X, et al. Adapting property path for polynomial-time evaluation and reasoning on semantic web [J]. Transactions of Tianjin University, 2013, 19(2): 130-139.

[9] Alkhateeb F, Baget J F, Euzenat J, et al. Constrained regular expressions in SPARQL [C]. International Conference on Semantic Web and Web Services. Las Vegas, USA, 2008.

[10] Gelade W, Gyssens M, Martens W. Regular expressions with counting: Weak versus strong determinism [J]. SIAM Journal on Computing, 2012, 41(1): 160-190.

[11] Alkhateeb F, Baget J-F, Euzenat J. Extending SPARQL with regular expression patterns (for querying RDF) [J]. Web Semantics: Science, Services and Agents on the World Wide Web, 2009, 7(2): 57-73.

[12] Barceló P, Pérez J, Reutter J L. Relative expressiveness of nested regular expressions [C]. Proceedings of the 6th Alberto Mendelzon International Workshop on the Foundations of Data Management. Ouro Preto, Brazil, 2012.

[13] Furche T, Weinzierl A, Bry F. Labeling RDF graphs for linear time and space querying. In: Semantic Web Information Management[M]. Springer, Berlin, Germany, 2010.

[14] Przyjaciel-Zablocki M, Schätzle A, Hornung T et al. RDFPath: Path query processing on large RDF graphs with MapReduce [C]. In: Proceedings of the 8th Extended Semantic Web Conference. Heraklion, Greece, 2011.

[15] Dean J, Ghemawat S. MapReduce: Simplified data processing on large clusters [J]. Communications of the ACM, 2008, 51(1): 107-113.

[16] Zauner H, Linse B, Furche T, et al. A RPL through RDF: Expressive navigation in RDF graphs [C]. Proceedings of the Fourth International Conference on Web Reasoning and Rule Systems. Brixen, Italy, 2010.

[17] Open Data Drug & Drug Target Database [EB/OL]. http://www.drugbank.ca/, 2013. 08.

[18] Biological General Repository for Interaction Datasets [EB/OL]. http://thebiogrid.org/, 2013. 07.