Adapting property path for polynomial-time evaluation and reasoning on semantic web

Abstract

Property path is the latest navigational extension of the standard query language SPARQL 1.1 for the Semantic Web. However, in the existing SPARQL query systems which support property path, the query efficiency is very low and does not support reasoning. This paper proposes a new existential semantics which has polynomial-time evaluation complexity and an equivalent relationship with the current semantics, and transforms the property path expressions to the extended nested regular expressions based on the existential semantics and proves the semantic equivalence after the transformation considering the RDFS semantics. The property path query engine is achieved by implementing the nested regular expressions algorithm and the transformation rules from the property path expressions to the nested regular expressions, which maintains the syntax simplicity of property path and the goal-oriented polynomial-time reasoning to avoid computing the RDF graph closure. The experiment results not only show the characteristics of query engine based on the existential semantics in efficiency and reasoning, but also further validate the equivalence between the results based on current semantics and those based on the existential semantics for property path after the removal of duplicate values.

Keywords

path / graph / semantics / reasoning / efficiency

References

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

[2] Prud’Hommeaux E, Seaborne A. SPARQL Query Language for RDF [EB/OL]. http://www.w3.org/TR/rdf-sparqlquery/, 2008-01-15.

[3] Arenas M, Pérez J. Querying semantic web data with SPARQL [C]. Proceedings of the Thirtieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2011

[4] Pérez J, Arenas M, Gutierrez C. Semantics and complexity of SPARQL [J]. ACM Transactions on Database Systems (TODS), 2009, 34(3): 1-45.

[5] Buil-Aranda C, Arenas M, Corcho O. Semantics and optimization of the SPARQL 1. 1 federation extension [C]. Proceedings of the 8th Extended Semantic Web Conference on the Semantic Web: Research and Applications, 2011

[6] Harris S, Seaborne A. SPARQL 1. 1 Query Language [EB/OL]. http://www.w3.org/TR/2011/WD-sparql11-query-20110512/, 2011-05-12.

[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]. Proceedings of the 21st International Conference on World Wide Web, 2012

[8] Losemann K, Martens W. The complexity of evaluating path expressions in SPARQL [C]. Proceedings of the 31st Symposium on Principles of Database Systems, 2012

[9] Alkhateeb F, Baget J F, Euzenat J. Constrained regular expressions in SPARQL [C]. Conference on Semantic Web and Web Services - SWWS, 2008

[10] Gelade W, Gyssens M, Martens W. Regular expressions with counting: Weak versus strong determinism [C]. Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science, 2009

[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] 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.

[13] Glimm B, Krötzsch M. SPARQL beyond subgraph matching [C]. The 9th International Semantic Web Conference, 2010

[14] Gutierrez C, Hurtado C A, Mendelzon A O, et al. Foundations of semantic web databases [J]. Journal of Computer and System Sciences, 2011, 77(3): 520 541

[15] Libkin L, Vrgoč D. Regular path queries on graphs with data [C]. Proceedings of the 15th International Conference on Database Theory-ICDT, 2012

[16] Mendelzon A O, Wood P T. Finding regular simple paths in graph databases [J]. SIAM Journal on Computing, 1995, 24(6): 1235 1258

[17] Gelade W. Succinctness of regular expressions with interleaving, intersection and counting [J]. Theoretical Computer Science, 2010, 411(31–33): 2987 2998

[18] Barceló P, Hurtado C, Libkin L, et al. Expressive languages for path queries over graph-structured data [C]. Symposium on Principles of Database Systems - PODS, 2010

[19] Sun X P, Zhuge H, Li Q. A framework for the massive knowledge Web [J]. Concurrency and Computation: Practice and Experience, 2009, 21(5): 705-723.

[20] Brickley Dan, Guha R V. RDF Vocabulary Description Language 1. 0: RDF Schema [EB/OL]. http://www.w3.org/TR/rdf-schema/, 2004-02-10.

[21] Munoz S, Pérez J, Gutierrez C. Minimal deductive systems for RDF [C]. Proceedings of the 4th European Conference on the Semantic Web: Research and Applications, 2007

[22] Bry F, Furche T, Linse B. The perfect match: Rpl and RDF rule languages [C]. Proceedings of the 3rd International Conference on Web Reasoning and Rule Systems, 2009

[23] Elliott B D. Hierarchical and Semantic Data Management and Querying for Patient Records and Personal Photos [D]. 2008, USA: Case Western Reserve University.